Выдержка из текста работы
Если прямая задача является задачей максимизации, то во всех неравенствах двойственной задачи будут стоять знаки ≥, и знаки ≤, если прямая задача является задачей минимизации.
Число ограничений прямой задачи равно числу переменных двойственной задачи.
Прямая задача в канонической форме
Двойственная к ней задача будет иметь вид
Двойственная задача решается симплекс-методом до достижения оптимального решения.
Решение прямой задачи
Все ограничения прямой задачи — это равенства с неотрицательными правыми частями, когда все переменные неотрицательны.
Приведем прямую задачу к стандартному виду:
Подставим значение в целевую функцию:
Таким образом, прямая задача в стандартной форме имеет следующий вид:
Строим симплекс таблицу:
Итерация №1
|
Базис |
Решение |
Оценка |
||||||
|
0 |
0 |
|
||||||
|
5 |
-2 |
1 |
0 |
0 |
0 |
4 |
— |
|
|
-1 |
2 |
0 |
1 |
0 |
0 |
4 |
2 |
|
|
1 |
1 |
0 |
0 |
-1 |
1 |
4 |
4 |
— ведущий столбец
— ведущая строка
Итерация №2
|
Базис |
|
|
|
|
|
|
Решение |
Оценка |
|
|
0 |
0 |
0 |
|||||
|
|
4 |
0 |
1 |
1 |
0 |
0 |
8 |
2 |
|
|
1 |
0 |
0 |
0 |
2 |
— |
||
|
|
0 |
-1 |
1 |
2 |
— ведущий столбец
— ведущая строка
Итерация №3
|
Базис |
|
|
|
|
|
|
Решение |
Оценка |
|
|
0 |
0 |
0 |
|||||
|
|
0 |
0 |
1 |
|||||
|
|
0 |
1 |
0 |
— |
||||
|
|
1 |
0 |
0 |
— |
— ведущий столбец
— ведущая строка
Итерация №4
|
Базис |
|
|
|
|
|
|
Решение |
|
|
0 |
0 |
0 |
8 |
|||
|
|
0 |
0 |
1 |
-1 |
1 |
||
|
|
0 |
1 |
0 |
0 |
3 |
||
|
|
1 |
0 |
0 |
0 |
2 |
Оптимальное решение прямой задачи:
, Х = {2 , 3}
Решение двойственной задачи
Двойственная задача имеет вид:
Мы получили двойственную задачу и будем решать ее М-методом. Приведем систему линейных неравенств к стандартному виду, перед этим сделав замену:
Подставим значения в функцию:
Таким образом, двойственная задача в стандартной форме имеет следующий вид:
Симплекс-таблица, итерация 1
|
Базис |
|
Решение |
Оценка |
||||||||
|
0 |
0 |
||||||||||
|
-5 |
5 |
1 |
-1 |
-1 |
-1 |
0 |
1 |
0 |
1 |
||
|
2 |
-2 |
-2 |
2 |
-1 |
0 |
-1 |
0 |
1 |
2 |
— |
— ведущий столбец
— ведущая строка
Симплекс-таблица, итерация 2
|
Базис |
Решение |
Оценка |
|||||||||
|
0 |
0 |
0 |
|||||||||
|
-1 |
1 |
|
0 |
0 |
— |
||||||
|
0 |
0 |
-1 |
1 |
— ведущий столбец
— ведущая строка
Симплекс-таблица, итерация 3
|
Базис |
Решение |
|||||||||
|
0 |
0 |
1 |
0 |
1 |
2 |
3 |
-8 |
|||
|
1 |
1 |
0 |
0 |
|||||||
|
0 |
0 |
-1 |
1 |
Оптимальное решение двойственной задачи:
, , ,
Ответ
Для двойственной задачи: , , ,
