Экономико-математический практикум (стр. 3 из 9)

Вектор А₃ выводимый из базиса, исключаем из рассмотрения (вычеркиваем). Получаем первое опорное решение

с базисом

(табл. 2.3). Целевая функция

=31,33М -10. Это решение не является оптимальным, так как имеются положительные оценки.

Таблица 2.3

1	-5	6	8	-2	М	M	M
Б	С_б	А₀	А₁	А₂	А₃	А₄	А₅	А₆	A₇	A₈
А₆	М	14,33	9,56	6,78	0,00	11,56	4,33	1,00	0,00	-0,11
A₇	M	17,00	14,00	10,00	0,00	3,00	8,00	0,00	1,00	0,00
←	А₃	6	1,67	1,44	0,22	1,00	0,44	0,67	0,00	0,00	0,11
		10,00	-7,67	-6,33	0,00	5,33	-6,00	0,00	0,00	-0,67
31,33	13,56	16,78	0,00	14,56	12,33	0,00	0,00	-1,11

Вводим вектор А₄ в базис, получаем второе опорное решение (таблица 2.4)

с базисом

. Целевая функция

= 3,38+13,28M. Далее в таблице 2.4 приведены расчеты с третьей по пятую итерации.

Таблица 2.4

4	2	-1	5	1	М	M	M
Б	Сб	А0	А1	А2	А3	А4	А5	А6	A7	A8
a4	8	1,24	0,83	0,59	0,00	1,00	0,38	0,09	0,00	-0,01
a7	M	13,28	11,52	8,24	0,00	0,00	6,88	-0,26	1,00	0,03
a3	6	1,12	1,08	-0,04	1,00	0,00	0,50	-0,04	0,00	0,12
		3,38	-12,08	-9,46	0,00	0,00	-8,00	-0,46	0,00	-0,62
13,28	1,52	8,24	0,00	0,00	6,88	-1,26	0,00	-0,97
a4	8	0,52	0,20	0,14	0,00	1,00	0,00	0,10	-0,05	-0,01
a5	-2	1,93	1,68	1,20	0,00	0,00	1,00	-0,04	0,15	0,00
a3	6	0,15	0,24	-0,64	1,00	0,00	0,00	-0,02	-0,07	0,11
18,84	1,33	0,13	0,00	0,00	0,00	-0,76	1,16	-0,58
0,00	-10,00	0,00	0,00	0,00	0,00	-1,00	-1,00	-1,00
a1	1	2,60	1,00	0,69	0,00	5,04	0,00	0,51	-0,27	-0,06
a5	-2	-2,42	0,00	0,04	0,00	-8,44	1,00	-0,89	0,61	0,10
a3	6	-0,47	0,00	-0,80	1,00	-1,20	0,00	-0,14	-0,01	0,13
4,19	0,00	-0,79	0,00	-6,68	0,00	-1,44	1,53	-0,51
25,99	0,00	6,90	0,00	50,35	0,00	4,07	-3,75	-1,56

Целевая функция после пятой итерации равна

= 4,19. Положительных оценок нет, план оптимален. Ответ: minZ(X^*) =4,2.

3.Построим двойственную задачу

Используя вторую симметричную пару двойственных задач, составим задачу, двойственную к исходной:

Вводим неотрицательные дополнительные переменные у₄, у₅, у₆ у₇, у₈ для приведения задачи к каноническому виду:

Находим начальное опорное решение Y₁ = (0,0,0,1,-5,6,8,-2) с базисом Б₁ = (А₄, А₅, А₆, А₇, А₈). Решение задачи симплексным методом приведено в табл. 2.5. (расчеты табл.2.2. и табл.2.4.)

Таблица 2.5

1	-5	6	8	-2	М	M	M
Б	С_б		А₀	А₁	А₂	А₃	А₄	А₅	А₆	A₇	A₈
←	А₆	М		16	11	7	1	12	5	1	0	0
A₇	M		17	14	10	0	3	8	0	1	0
А₈	М		15	13	2	9	4	6	0	0	1
			0	-1	5	-6	-8	2	0	0	0
			48	28	19	10	19	19	0	0	0
a1		1	2,60	1,00	0,69	0,00	5,04	0,00	0,51	-0,27	-0,06
a5		-2	-2,42	0,00	0,04	0,00	-8,44	1,00	-0,89	0,61	0,10
a3		6	-0,47	0,00	-0,80	1,00	-1,20	0,00	-0,14	-0,01	0,13

4,19 0,00 -0,79 0,00 -6,68 0,00 -1,44 1,53 -0,51

25,99 0,00 6,90 0,00 50,35 0,00 4,07 -3,75 -1,56

Приведем оптимальное решение прямой задачи

Окончательный базис, соответствующий оптимальному решению прямой задачи, состоит из векторов А₂А₃А₄ поэтому базисная матрица имеет вид

Решение прямой задачи начиналось с единичного базиса А_6,А₇,А₈. Поэтому в окончательной таблице указанные столбцы преобразуются в матрицу

, обратную к базисной матрице

, следовательно,

Оптимальный план двойственной найдем из соотношения

Откуда

При этом плане максимальное значение функции двойственной задачи составляет величину равную

Максимальное значение целевой функции двойственной задачи совпадает с минимальным значением целевой функции прямой задачи.

5. Проанализируем решение задачи, используя условия дополняющей нежесткости (вторую теорему двойственности).

Подставляем координаты оптимального решения двойственной задачи

в систему ограничений.

Первое, третье и пятое ограничения выполняются как строгие неравенства, следовательно, их координаты оптимального решения исходной задачи равны нулю:

. Учитывая это, первую, вторую и пятую координаты оптимального решения Х^* находим при совместном решении уравнений-ограничений исходной задачи:

Ответ: Z(X) = 4,2 при Х* = (0;1,6; 0;4,9;0).

Задача № 3

Транспортная задача

Ниже приведены числовые данные транспортных задач. Стоимость перевозки единицы продукции записаны в клетках таблицы. Запасы указаны справа от таблиц, а потребности – снизу. Требуется построить начальный план методами: «северо-западного угла», «минимального элемента», «двойного предпочтения», методом Фогеля. Из каждого плана найти оптимальный план методом потенциалов.