Контрольные вопросы:

1. В чем состоит особенность ТЗ как частного случая 3ЛП?

2. Что называется перевозками и планом перевозок в ТЗ?

3. Чему соответствует число уравнений ТЗ и каково число независимых уравнений?

4. Что такое базисные и свободные переменные ЗЛП? Что такое несбалансированная или открытая ТЗ?

5. Как находилась целевая функция?

6. На основании чего делаются выводы в изменениях условий?

Задача 2 (дальнобойщик). Требуется распределить автомобили трех типов по транспортным линиям так, чтобы при минимальных суммарных эксплуатационных расходах перевезти по каждой из четырех линий соответственно не менее 300, 200, 900 и 600 т. груза.

Ниже в табл. 2,3 приведены исходные данные.

Таблица 2

Зависимость числа рейсов от типа автомобиля

Тип автомобиля	Число автомобилей этого типа	Число рейсов в месяц автомобилем одного типа по линиям:
		1	2	3	4
1	30	5	4	6	8
2	45	4	6	4	5
3	40	7	8	8	7

Таблица 3

Зависимость эксплуатационных расходов от типа автомобиля

Тип автомобиля	Эксплуатационные расходы на один рейс по данному маршруту, долл.
	1	2	3	4
1	20	30	15	30
2	60	32	25	35
3	50	30	30	75

Необходимо так распределить автомобили по линиям, чтобы суммарные эксплуатационные расходы были минимальны.

Решение: Экономико-математическая модель задачи

- матрица назначений автомобилям по линиям,

- матрица объемов перевозок,

- матрица эксплуатационных расходов, .

Целевая функция имеет вид:

Ограничения:

- Ограничения по числу автомобилей,

По смыслу задачи: - целые неотрицательные числа.

- Ограничения по объемам перевозок,

Полученную ЗЛП будем решать средствами Excel, используя надстройку Сервис \ Поиск решения.

Выполним последовательно следующие действия в среде Excel:

1. Создадим форму для ввода условий задачи и введем в нее исходные данные (рис.6).

2. Укажем адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки). Оптимальные значения компонент матрицы решений будут помещены в ячейках I12:L14, оптимальное значение целевой функции – в ячейке H16.

	A	B	C	D	E	F	G	H	I	J	K	L	M
	Тип автомобиля	Число автомобилей этого типа	Месячный объем перевозок автомобилем одного типа по линиям					Тип автомобиля	Эксплуатационные расходы на один рейс по данному маршруту, долл.
4			1	2	3	4			1	2	3	4
5	1	30	25	20	30	40		1	20	30	15	30
6	2	45	20	30	20	27		2	60	32	25	35
7	3	40	35	40	40	35		3	50	30	30	75

Рис.6. Форма для ввода условий задачи.

3. Введем зависимость для целевой функции, для этого нужно: установить курсор в ячейку H16, на панели инструментов нажать кнопку Мастер функций. В диалоговом окне Мастер функций выбрать категорию Математические и функцию СУМПРОИЗВ;

Рис.7. Диалоговое окно функции СУМПРОИЗВ.

В диалоговом окне Аргументы функций в строку «Массив 1» ввести C5:F7, в строку «Массив 2» ввести I5:L7, в строку «Массив 3» ввести I12:L14 (рис.7).

4. Введем зависимости для ограничений:

- в ячейки В10, В11, В12 нужно ввести функции СУММ(I12:L12), СУММ(I13:L13), СУММ(I14:L14) соответственно; в ячейки D 10, D 11, D 12 введем соответственно значения 30, 45, 40.

- в ячейки В13, В14, В15, В16 нужно ввести функции СУММПРОИЗВ(C5:C7;I12:I14), СУММПРОИЗВ(E5:E7;K12:K14), СУММПРОИЗВ(F5:F7;L12:L14), СУММПРОИЗВ(D5:D7;J12:J14) соответственно; в ячейки D 13, D 14, D15, D16 введем соответственно значения 300, 200, 900, 600.

В результате получим следующую форму для решения задачи (рис.8):

	A	B	C	D	E	F	G	H	I	J	K	L	M
	Тип автомобиля	Число автомобилей этого типа	Месячный объем перевозок автомобилем одного типа по линиям					Тип автомобиля	Эксплуатационные расходы на один рейс по данному маршруту, долл.
4			1	2	3	4			1	2	3	4
5	1	30	25	20	30	40		1	20	30	15	30
6	2	45	20	30	20	27		2	60	32	25	35
7	3	40	35	40	40	35		3	50	30	30	75
8
9			Ограничения				Матрица назначений автомобилей по линиям
10		0	<=	30			Тип автомобиля		Транспортные линии
11		0	<=	45					1	2	3	4
12		0	<=	40				1	0	0	0	0
13		0	>=	300				2	0	0	0	0
14		0	>=	200				3	0	0	0	0
15		0	>=	900		Целевая			изменяемые ячейки
16		0	>=	600		Функция F =		0
17

Рис. 8. Форма для решения задачи.

5. Выполним команду меню Сервис \ Поиск решения. В диалоговом окне Поиск решения нужно:

• назначить целевую ячейку – в данном случае H16;

• ввести направление целевой функции – Минимальному значению;

• в строке Изменяя ячейки ввести диапазон I12:L14 (адреса искомых переменных);

• ввести ограничения, для этого нажать на кнопку Добавить и ввести данные в диалоговое окно Добавление ограничения;

В результате диалоговое окно Поиск решения выглядит следующим образом (рис. 9-10):

Рис. 9. Диалоговое окно Поиск решения Рис. 10. Диалоговое окно Параметры поиска решения

6. Введем параметры для решения ЗЛП. Для этого в диалоговом окне Поиск решения нужно нажать на кнопку Параметры и в диалоговом окне Параметры поиска решения установить флажки в окнах Линейная модель и Неотрицательные значения (рис.10). После этого нужно нажать на кнопку Выполнить.

Через некоторое время появляется диалог Результаты поиска решения и исходная таблица с заполненными ячейками I12:L14, для значений и ячейка H16 с минимальным значением целевой функции (рис.11).

	A	B	C	D	E	F	G	H	I	J	K	L	M
	Тип автомобиля	Число автомобилей этого типа	Месячный объем перевозок автомобилем одного типа по линиям					Тип автомобиля	Эксплуатационные расходы на один рейс по данному маршруту, долл.
4			1	2	3	4			1	2	3	4
5	1	30	25	20	30	40		1	20	30	15	30
6	2	45	20	30	20	27		2	60	32	25	35
7	3	40	35	40	40	35		3	50	30	30	75
8
9			Ограничения			Матрица назначений автомобилей по линиям
10		30	<=	30					Транспортные линии
11		41	<=	45			Тип автомобиля		1	2	3	4
12		5	<=	40				1	12	0	18	0
13		300	>=	300				2	0	0	18	23
14		200	>=	200				3	0	5	0	0
15		900	>=	900		Целевая			изменяемые ячейки
16		621	>=	600		Функция F =		50835
17

Рис.11. Исходная таблица с Результатами поиска решения

Матрица решений имеет вид:

транспортные линии
1	2	3	4
12	0	18	0
0	0	18	23
0	5	0	0

Полученное решение означает, что на 1-ю транспортную линию нужно назначить 12 автомобилей 1-го типа; на 2-ю транспортную линию нужно назначить 5 автомобилей 3-го типа; на 3-ю транспортную линию – по 18 автомобилей 1-го и 2-го типов соответственно; на 4-ю линию – 23 автомобиля 2-го типа.

В этом случае будут задействованы все 30 автомобилей 1-го типа и 41 автомобиль 2-го и 5 автомобилей 3-го типов соответственно. По каждой из четырех транспортных линий будет перевезено соответственно 300, 200, 900 и 600 т. груза.

Минимальные суммарные эксплуатационные расходы составят 50835 долл.