Пример решения двойственной задачи симплексным методом.
Ниже приведено условие и решение задачи. Закачка решения в формате doc начнется автоматически через 10 секунд.
Z = 2X1 + 6X2 + X3 (min)
5X1 + X2 + 4X3 ≥5,
X1 + 3X2 + 7X3 ≥3.
X1≥0, X2≥0, X3≥0.
Решение.
Запишем матрицу исходной задачи в виде.
5 |
1 |
4 |
5 |
1 |
3 |
7 |
3 |
2 |
6 |
1 |
φ min |
Транспонируем составленную матрицу. В результате получим матрицу двойственной задачи:
5 |
1 |
2 |
1 |
3 |
6 |
4 |
7 |
1 |
5 |
3 |
f max |
По полученной матрице запишем двойственную задачу.
F = 5Y1 + 3Y2 (max)
5Y1 + Y2 ≤ 2,
Y1 + 3Y2 ≤ 6,
4Y1 + 7Y2 ≤1.
Y1≥0, Y2≥0.
Задача записана в симметричной фоме записи. Приведем задачу к канонической форме записи, для этого введем дополнительные переменные Y3, Y4, Y5. Расширенная система задачи имеет вид:
5Y1 + Y2 + Y3 = 2
Y1 + 3Y2 + Y4 = 6
4Y1 + 7Y2 + Y5 = 1
Условия неотрицательности примут вид:
Yj≥0 (j=1,..,5).
Заполним первую симплексную таблицу (Табл. 1), в которой переменные Y3, Y4, Y5 являются базисными, переменные Y1, Y2 свободными. Последняя строка заполняется коэффициентами целевой функции с противоположным знаком.
Таблица 1. Первая (начальная) симплексная таблица
Базис |
C |
Свободный член |
Переменные |
Оценочное отношение |
||||
Y1 |
Y2 |
Y3 |
Y4 |
Y5 |
||||
5 |
3 |
0 |
0 |
0 |
|
|||
Y3= |
0 |
2 |
5 |
1 |
1 |
0 |
0 |
0,4 |
Y4= |
0 |
6 |
1 |
2 |
0 |
1 |
0 |
6 |
Y5= |
0 |
1 |
4 |
7 |
0 |
0 |
1 |
0,25 |
F |
0 |
-5 |
-3 |
0 |
0 |
0 |
|
В полученной таблице в F-строке есть отрицательные элементы, следовательно план не является оптимальным. Производим симплексное преобразование с разрешающим элементом 4 и переходим к таблице 2.
Таблица 2. Вторая симплексная таблица.
Базис |
C |
Свободный член |
Переменные |
Оценочное отношение |
||||
Y1 |
Y2 |
Y3 |
Y4 |
Y5 |
||||
5 |
3 |
0 |
0 |
0 |
|
|||
Y3= |
0 |
0,75 |
0 |
-7,75 |
1 |
0 |
-1,25 |
|
Y4= |
0 |
5,75 |
0 |
0,25 |
0 |
1 |
-0,25 |
|
Y1= |
5 |
0,25 |
1 |
1,75 |
0 |
0 |
0,25 |
|
F |
1,25 |
0 |
5,75 |
0 |
0 |
1,25 |
|
Получаем табл. 2. в F-строке которой нет отрицательных элементов.
Следовательно, опорный план (0,25; 0; 0,75; 5,75; 0) является оптимальным, а соответствующее ему значение 1,25 целевой функции будет максимальным.
Запишем соответствия между переменными двойственных задач:
Y3 X1, Y4 X2, Y5 X3, Y1 X4, Y2 X5.
Используя соответствие между переменными двойственных задач и полученные значения в таблице 2, находим решение двойственной задачи.
X1 = 0; X2 = 0; X3 = 1,25; X4 = 0; X5 = 5,75. Экстремальные значения целевых функций двойственных задач совпадают Fmax = Zmin = 1,25.
Имя файла: mathprog9.doc
Размер файла: 51 Kb
Если закачивание файла не начнется через 10 сек, кликните по этой ссылке