ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 02.02.2026
Просмотров: 812
Скачиваний: 2
Прямая задача (задача нахождения оптимального плана производства):
Целевая функция (функция прибыли)
z(x1,x2) := 17 × x1 + 25 × x2
x1:= 0 |
x2:= 0 |
Заданные ограничения
Given
Ограничения на объем имеющихся ресурсов
4x1 + 2 × x2 £ 50
2 × x1 + 5x2 £ 30
3x1 + 4x2 £ 60
Условия неотрицательности выпуска производства
x1 ³ 0 x2 ³ 0
Необходимо найти план производства, обеспечивающий максимум
функции прибыли
æ |
x1 ö |
:= Maximizez(,x1, x2) |
|
|
|
|
|
è |
x2 ø |
æ x1 ö |
|
æ |
11.875 ö |
||
|
= |
||||||
Оптимальный план производства è x2 ø |
è |
1.25 ø |
|||||
|
|||||||
Максимальная прибыль |
z(x1,x2) = 233.125 |
|
|||||
Таким образом, в результате решения прямой задачи получили оптимальный план производства: x1 = 11,875 x2 = 1,25
Х, при котором следует производить оба вида продукции, и прибыль от реализации будет максимальной Zmax = 233,125
рублей.
41
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
Двойственная задача (задача нахождения оптимального набора оценок на ресурсы):
Оптимальный план производства æ x1 |
ö |
æ 11.875 ö |
||||
|
|
ç |
x2 |
÷ |
= ç |
÷ |
|
|
è |
ø |
è 1.25 |
ø |
|
Максимальная прибыль |
z(x1, x2) = 233.125 |
|
||||
Целевая функция (функция затрат) |
|
|
|
|
||
f(y1, y2,y3) := 50 × y1 |
+ 30 × y2 + 60y3 |
|
|
|
|
|
y1 := 0 y2 := 0 y3 |
:= 0 |
|
|
|
|
|
Заданные ограничения
Given
Создаваемая прибыль при производстве единицы каждого вида продукции должны быть не меньше прибыли от реализации единицы этой продукции
4y1 + 2 × y2 + 3y3 ³ 17
2 × y1 + 5y2 + 4y3 ³ 25
Условия неотрицательности цен (оценок) ресурсов
y1 ³ 0 y2 ³ 0 y3 ³ 0
Необходимо найти набор оценок на ресурсы, обеспечивающий
минимальные общие затраты на ресурсы
Решая двойственную задачу, нашли оптимальный набор оценок на ресурсы y1 = 2,188, y2 = 4,125, y3 = 0 , т.е. ресурсы R1
и R2 по оптимальному плану полностью использованы, и
объективно обусловленные оценки этих ресурсов ненулевые (данные ресурсы являются дефицитными). Ресурс R3 не
полностью используется, и объективно условленная оценка этого ресурса нулевая (ресурс недефицитный).
7. Двойственный симплекс-метод
Двойственный симплекс-метод является методом, при
котором сначала симплексным методом решается исходная
42
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
задача, а затем оптимальное решение двойственной задачи находится с помощью теорем двойственности.
П р и м е р . Составить и решить задачу, двойственную следующей задаче:
Z = 6 × x1 + x2 ® max
ì3× x1 - x2 ³ 9 ïí2 × x1 + 3× x2 £ 50 ïî- x1 + 4 × x2 ³ 18
x1³ 0, x2 ³ 0
Р е ш е н и е .
Сформулируем задачу, двойственную для исходной
задачи.
Поскольку исходная задача является задачей на отыскание максимума целевой функции, то для составления двойственной задачи, первоначально необходимо все ограничения-неравенства исходной задачи привести к виду, когда они имеют знак «≤». Для этого обе части неравенств со знаком «≥» умножим на (-1).
|
|
|
Тогда двойственная задача (задача минимизации |
|||||||||||
целевой функции |
при ограничениях-неравенствах со знаком |
|||||||||||||
«≥») будет иметь вид: |
|
|
|
|
|
|||||||||
|
|
|
Исходная задача |
|
|
|
|
Двойственная задача |
||||||
|
линейного программирования |
линейного программирования |
||||||||||||
Z = 6 × x1 + x2 ® max |
Z = 6× x1 + x2 ® max |
F = -9 × y1 + 50 × y2 -18 × y3 ® min |
||||||||||||
ì3 × x1 - x2 ³ 9 |
|
× (-1) |
ì- 3× x + x |
2 |
£ -9 |
|||||||||
|
||||||||||||||
ï |
|
|
|
|
|
|
|
ï |
1 |
|
|
ì- 3 × y1 + 2 × y2 + y3 ³ 6 |
||
× x1 + 3 × x2 £ 50 |
+ 3 |
× x2 £ 50 |
||||||||||||
í2 |
í2× x1 |
í |
||||||||||||
ï- x + 4 × x ³ 18 |
|
× (-1) |
ïx - 4× x |
2 |
£ -18 |
îy1 + 3 × y2 - 4 × y3 ³1 |
||||||||
|
||||||||||||||
ï |
1 |
|
2 |
|
|
|
|
î 1 |
|
|
|
|
||
î |
|
|
|
|
|
x1³ 0, x2 ³ 0 |
|
y1³ 0, y2 ³ 0, y3 ³ 0 |
||||||
x ³ 0, x |
2 |
³ 0 |
|
|
|
|
|
|||||||
1 |
|
|
|
|
|
|
|
|
|
|
|
|
||
Используя теоремы двойственности, можно не решая двойственную задачу симплексным методом, на основе последней симплекс-таблицы оптимального решения исходной
43
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
задачи получить последнюю симплекс-таблицу оптимального решения двойственной задачи.
В результате решения исходной задачи линейного программирования симплексным методом следующую симплекс-таблицу соответствующую оптимальному решению
(см. Таб.3.).
Согласно первой теореме двойственности, если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и другая задача, причем оптимальные значения их
функций равны: Fmin = Zmax = 87 115 .
Установим соответствие между переменными исходной и двойственной задач (базисным переменным одной задачи соответствуют свободные переменные другой, и наоборот):
{x1 |
x 2 |
x 3 |
x 4 |
x 5 } |
{y4 |
y5 |
y1 |
y2 |
y3} |
Положительным |
компонентам |
оптимального решения |
||
одной из взаимно двойственных задач соответствуют нулевые компоненты оптимального решения другой задачи.
ì |
|
3 |
|
|
|
9 |
|
|
|
|
|
ü |
|||
í x1 |
= 13 |
|
|
x 2 |
= |
7 |
|
|
x 3 = 23 |
x 4 |
= 0 x 5 |
= |
0 |
ý |
|
11 |
11 |
||||||||||||||
î |
|
|
|
|
|
|
|
|
|
þ |
|||||
ì |
|
|
|
|
|
3 |
|
|
|
5 |
ü |
|
íy4 |
= 0 |
y5 = 0 |
y1 = 0 |
y2 |
= 2 |
|
|
|
y3 |
= 1 |
|
ý |
11 |
|
|||||||||||
î |
|
|
|
|
|
|
|
11þ |
||||
|
Подставив найденные значения Y* = (0; 2 |
3 |
; 1 |
5 |
; 0; 0) в |
||||||||
|
11 |
|
|||||||||||
|
|
|
|
|
|
|
|
|
F, |
11 |
|||
целевую |
функцию |
|
|
|
|
|
получим |
||||||
F = -9×0 + 50×2 |
3 |
-18×1 |
5 |
= 87 |
5 |
, что |
и подтверждается |
||||||
|
|
|
|||||||||||
min |
11 |
11 |
11 |
|
|
|
|
|
|||||
первой теоремой двойственности. |
|
|
|
|
|
||||||||
|
Составим последнюю симплекс-таблицу оптимального |
||||||||||||
решения двойственной задачи по следующим правилам: |
|||||||||||||
|
ü Компоненты оптимального решения |
двойственной |
|||||||||||
задачи равны абсолютным |
значениям |
коэффициентов при |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
44 |
||
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com