Смекни!
smekni.com

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

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

с базисом
(табл. 2.3). Целевая функция
=31,33М -10. Это решение не является оптимальным, так как имеются положительные оценки.

Таблица 2.3

1 -5 6 8 -2 М M M
Б Сб А0 А1 А2 А3 А4 А5 А6 A7 A8
А6 М 14,33 9,56 6,78 0,00 11,56 4,33 1,00 0,00 -0,11
A7 M 17,00 14,00 10,00 0,00 3,00 8,00 0,00 1,00 0,00
А3 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

Вводим вектор А4 в базис, получаем второе опорное решение (таблица 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.Построим двойственную задачу

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

Вводим неотрицательные дополнительные переменные у4, у5, у6 у7, у8 для приведения задачи к каноническому виду:

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

Таблица 2.5

1 -5 6 8 -2 М M M
Б Сб А0 А1 А2 А3 А4 А5 А6 A7 A8
А6 М 16 11 7 1 12 5 1 0 0
A7 M 17 14 10 0 3 8 0 1 0
А8 М 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

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

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

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

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

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

Откуда

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

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

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

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

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


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

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

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

Задача № 3

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

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