Составители:
Рубрика:
21
Каждая из задач двойственной пары (табл. 2) фактически является само-
стоятельной задачей ЛП и может быть решена независимо одна от другой. Од-
нако при определении симплексным методом оптимального плана одной из за-
дач тем самым находится решение и другой задачи. При этом
max f(
x)= min
ϕ
(y).
Следует отметить, что на практике для непосредственного решения двой-
ственной задачи используется специальный
двойственный симплексный ме-
тод
. Это связано с тем, что в двойственной задаче система ограничений пред-
ставляет неравенства типа ≥, и при приведении задачи ЛП к канонической фор-
ме правые части ограничений получаются отрицательными.
Для нашего примера двойственная задача в канонической форме будет
выглядеть следующим образом:
()
min203040
321
→
+
+
= yyyy
ϕ
⎩
⎨
⎧
−=+−−−
−=+−−−
40565
50258
5321
4321
yyyy
yyyy
y
1
, y
2
, y
3
, y
4
, y
5
≥ 0 .
Двойственный симплексный метод может применяться при решении за-
дачи ЛП, свободные члены системы уравнений которой могут быть любыми
числами (при решении задачи симплексным методом эти числа предполагались
неотрицательными). Мы же рассмотрим решение двойственной задачи с помо-
щью табличного процессора
Exel.
Решение можно произвести в том же листе рабочей книги, где решалась
исходная задача (рис. 6). Предварительно упростим этот лист, записав обо-
значения в общем, математическом виде (хотя это и не обязательно), оставив
формулы без изменения.
1
2
3
4
5
6
7
8
9
10
ABC D EF
Целевая ф-я
имя
x
1
x
2
f (
x
)
значение
00
=СУММПРОИЗВ(B3:C3;B4:C4)
коэф-ты
f (
x
)
50 40 макс
№
x
1
x
2
левая часть знак прав.часть
185=СУММПРОИЗВ(B$3:C$3;B8:C8) <= 40
256=СУММПРОИЗВ(B$3:C$3;B9:C9) <= 30
325=СУММПРОИЗВ(B$3:C$3;B10:C10) <= 20
Ограничения
Переменные
Рис 7. Данные исходной задачи линейного программирования
К имеющимся данным добавим следующие: ячейки G8:G10 отведем под
значения двойственных переменных; в ячейку G12 введем формулу целевой
функции
=СУММПРОИЗВ(F8:F10;G8:G10) ;
в ячейки диапазона B12:C12 –формулы
=СУММПРОИЗВ(B8:B10;$G$8:$G$10)
Каждая из задач двойственной пары (табл. 2) фактически является само- стоятельной задачей ЛП и может быть решена независимо одна от другой. Од- нако при определении симплексным методом оптимального плана одной из за- дач тем самым находится решение и другой задачи. При этом max f(x)= min ϕ(y). Следует отметить, что на практике для непосредственного решения двой- ственной задачи используется специальный двойственный симплексный ме- тод. Это связано с тем, что в двойственной задаче система ограничений пред- ставляет неравенства типа ≥, и при приведении задачи ЛП к канонической фор- ме правые части ограничений получаются отрицательными. Для нашего примера двойственная задача в канонической форме будет выглядеть следующим образом: ϕ (y ) = 40 y1+30 y 2 + 20 y3 → min ⎧− 8 y1 − 5 y 2 − 2 y3 + y 4 = −50 ⎨ ⎩− 5 y1 − 6 y 2 − 5 y3 + y5 = −40 y1, y2, y3, y4, y5 ≥ 0 . Двойственный симплексный метод может применяться при решении за- дачи ЛП, свободные члены системы уравнений которой могут быть любыми числами (при решении задачи симплексным методом эти числа предполагались неотрицательными). Мы же рассмотрим решение двойственной задачи с помо- щью табличного процессора Exel. Решение можно произвести в том же листе рабочей книги, где решалась исходная задача (рис. 6). Предварительно упростим этот лист, записав обо- значения в общем, математическом виде (хотя это и не обязательно), оставив формулы без изменения. A B C D E F 1 Переменные Целевая ф-я 2 имя x1 x2 f (x) 3 значение 0 0 =СУММПРОИЗВ(B3:C3;B4:C4) 4 коэф-ты f (x) 50 40 макс 5 6 Ограничения 7 № x1 x2 левая часть знак прав.часть 8 1 8 5 =СУММПРОИЗВ(B$3:C$3;B8:C8) <= 40 9 2 5 6 =СУММПРОИЗВ(B$3:C$3;B9:C9) <= 30 10 3 2 5 =СУММПРОИЗВ(B$3:C$3;B10:C10) <= 20 Рис 7. Данные исходной задачи линейного программирования К имеющимся данным добавим следующие: ячейки G8:G10 отведем под значения двойственных переменных; в ячейку G12 введем формулу целевой функции =СУММПРОИЗВ(F8:F10;G8:G10) ; в ячейки диапазона B12:C12 –формулы =СУММПРОИЗВ(B8:B10;$G$8:$G$10) 21
Страницы
- « первая
- ‹ предыдущая
- …
- 19
- 20
- 21
- 22
- 23
- …
- следующая ›
- последняя »