Методы условной оптимизации: Рекомендации к выполнению лабораторных и практических работ. Шипилов С.А. - 21 стр.

UptoLike

Составители: 

Рубрика: 

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