Бережная_Матметоды моделирования эк cистем

Пример 7.15.

Дана следующая система:

|х1+2х2+хз>9;

[2х1+хз>4;

xi > 0; Х2 > 0; х^ > 0; ^min = л:1 + Х2 + Ху

Проверяем условие: целевая функция стремится к min, а знак неравенства должен быть >. Исходная задача соответствует данно­ му условию, и можно сразу приступить к построению симметрич­ ной двойственной пары.

Так как в прямой задаче в системе ограничений два неравенст­ ва, то в двойственной будет две переменных wj и «2» причем Wj > О, «2 > 0.

Целевая функция

^тах = 9Wi + 4W2.

Учитывая, что целевая функция на max и в прямой задаче Xi > 0; Х2 ^ 0; х^ ^ О, то система ограничений запишется в следу­ ющем виде:

[wi+2w2<l; 2wi <1; lwi+W2<l.

Пример 7.16.

Имеем систему

Xj > 0; Хз > 0; Х5 > 0; Х2 и Х5 не имеют ограничения знака; ^min = ^1 — 2X2 + Х3 — Х4 + ^5-

Так как целевая функция на min, то в исходной задаче ограни­ чения неравенства должны иметь знак >. Умножим второе неравен­ ство системы на —1:

—2xi — 3x2 + 2x3 + Х4 — Х5 > — ^•

240

в прямой задаче число ограничений равно 3, значит, в двойст­ венной будет три переменных: Ui; Ui, uy Так как «2 и «з соответст­ вуют неравенствам, то Ui > 0; W3 ^ 0. Параметр и^ соответствует ра­ венству, поэтому «1 — переменная без ограничения знака.

Число ограничений в двойственной задаче равно 5, так как в прямой задаче пять переменных, в том числе первое, третье и пя­ тое ограничения будут неравенствами, потому что они соответству­ ют неотрицательным переменным, а второе и четвертое офаничения будут уравнениями, так как соответствуют переменным без ог­ раничения знака. Запишем двойственную задачу с учетом вышеиз­ ложенного:

целевая функция

^тах = 6wi - 4W2 + 8W3;

ограничения

щ - 2«2 + «3^1; -2ui - 3«2 = - 2; щ н- 2^2 + 3^3 < 1; Swj + ^2 = —1;

—lux — «2 ~ 4^3 ^ 1.

Решение симметричных двойствеш1ых задач. Сформулируем без доказательства теорему, справедливую для любых двойственных задач.

Теорема (первая теорема двойственности). Если одна из двойственных задан имеет оптимальное решение, то и другая его имеет. Причем экстремальные значения целевых функций совпа­ дают. Если же в одной задаче целевая функция не ограничена, то двойственная ей задача противоречива.

Запишем в общем виде прямую и двойственную задачи линей­ ного программирования:

1) прямая задача:

^ 1 Л +«12^2 + - +«l/T^Ai^«i;

(7.63)

^т\^\ "^ ^/я2^2 "^ ••• "*• ^тгР^п ^ ^т'у

^тах = CiXi + С2Х2 + ... + С^пу

X/ > 0; / = ГГТГ;

241

Преобразуем задачи (7.63) и (7.64) к виду, допускающему при­ менение симплекс-алгоритма. Для этого введем выравнивающие переменные y^j = 1,/« в прямую задачу и V/, / = 1,« — в двойствен­ ную задачу:

1) прямая:

У! = fli - (^11^1 + ^12>^2 + . . . + «lA^/,);

(7.630

2) двойственная:

Построим для задач (7.630 и (7.640 общую симплекс-таблицу (табл. 7.23), причем эта таблица имеет дополнительные столбец и строку для двойственной задачи:

242

Задачи, представленные в общей симплекс-таблице (табл. 7,23), решаются обычным симплекс-методом, алгоритм которого приве­ ден выше.

Сформулируем признаки оптимальности двойственной пары задач:

• планы X— {xi, ^2, ..., Xf^) и f/= (wj, «2» •••» ^т) оптимальны, ес­ ли Z^^(X) = X^in(f/);

• решения Л'= (xj, Х2, ..., x„) и f/= (W|, W2, ..., w^;,) оптимальны, если все произведения сопряженных условий для этих решений равны 0.

Запишем следующие сопряженные условия: I группа:

(^1 - ^ 1 Л - ^12^2 - - ~ ^in^n) Щ = 0;

(^т - ^ml^l - ^m2^2 - - ^ ^тп^п) ^т = О-

II группа получается, если умножить naxi, Х2, ..., х„ выражения для базисных переменных двойственной задачи:

(«11^1 + «21^2 + ... + ат\^т " ^l) ^1 = 0; (^1л«1 + ^2/2«2 + ... + «m««m " О ^л = 0.

Пример 7.17. По исходной задаче построить двойственную и найти оптимальное решение обеих задач.

^тах ^ -3Xi + 5X2 + ^3 + ^4>

Ъхх + 8x2 + ^3 "^ ^4 - 50; 5xi — 4x2 — ^3 "^ .^4 ~ 14; Ху>0,у=Г74.

Согласно общему правилу составления двойственных задач за­ пишем:

3^1 + 5«2 ^ - 3 ; 8MI - 4«2 > 5;

^min = 50«1 + 14«2; Wj И «2 ^ 0.

Решим задачи в единой симплекс-таблице. Для этого предста­ вим их в виде, позволяющем применить симплекс-метод:

243

1) прямая задача:

вводим выравнивающие переменные х^, х^;,

Хз = 50 — (Зх] + 8x2 "^ ^3 "^ ^4)i Хб = 14 ~ (Sxj - 4x2 -~ ^3 "^ МУУ

^тж "= О ~" (3Xi — 5X2 ~ ^3 ~ ^4)5

2) двойственная задача:

вводим в левую часть ограничений выравнивающие перемен­ ные Vj, V2, V3, V4 со знаком «—»:

vi = 3 - (-3^1 -5^2); V2 = -5-(-8^/i+4«2);

^min = 0 - (-50^1 - 14w2).

Итак, составим таблицу, внешний контур которой образует двойственную задачу, внутренний - прямую задачу (табл. 7.24):

t

*Б - базисные переменные. **С — свободные переменные.

Будем работать по симплекс-методу, но так как записанная в последней строчке функция стремится к максимуму, то в этой строчке мы будем искать наименьший отрицательный элемент.

Построим итоговую таблицу (табл. 7.25):

244

Итак, мы получили итоговую таблицу (табл. 7.25), в последней строчке которой нет отрицательных элементов, следовательно, за­ дачи решены:

прямая задача X = (0; 0; 18; 32), Zj^g^ ^ 50; двойственная задача U= (1; 0), Z^j^ = 50.

245

проверим полученное решение на оптимальность: условие 1) выполнено: Z {X) = L {U) "= 50.

Для выполнения условия 2) составим произведения сопряжен­ ных условий:

xivi = xj (3 - (-3wi - 5w2)) = О (3 - (-3 • 1 - 5 • 0)) = 0; X2V2 = X2 ( - 5 - (-8wi + 4w2)) = 0 ( - 5 - (-8 • 1 + 4 . 0)) = 0; X3V3 = X3 (-1 - (-wi + «2)) = 18 (-1 - (~1 + 0)) ^ 0;

X4V4 = X4 (-1 - (-«1 - U2)) = 18 ( - 1 - (-1 - 0)) ^ 0;

Итак, оба условия выполняются, значит, полученный план — оптимальный.

Рассмотренную задачу примера 7.17 можно решить иначе. Для этого необходимо:

1) решить прямую задачу обычным симплекс-методом. Реше­ ние получим следующее: Z^^^ = 50; А" = (0; 0; 18; 32);

2) составить произведение сопряженных условий и приравнять ихО:

XjVi = xi (3 - (~3wi - 5^2)); X2V2 = Х2 ( - 5 - (-8wi + 4^2));

^3^3 = ^3 ( - 1 - (-«1 + «2)); X4V4 = X4 (~ 1 - (-Wj - W2));

W1X5 = Wi (50 - (3xi + 8x2 + X3 + X4));

W2X6 = W2 (14 - (5xi - 4x2 - ^3 "^ ^4))-

Подставим вектор X в записанные условия, тогда будем иметь:

После преобразований получим:

Откуда Wj = 1; «2 "^ О» ^min "^ 50» так как Z^^ax ^ ^min» значит, за­ дача решена верно.

246

7.9. Экономико-математический анализ полученных оптимальных решений

Оптимальное решение задачи линейного программирования су­ щественно зависит от реальной экономической ситуации, склады­ вающейся на предприятии. На решение задачи могут повлиять сле­ дующие экономические ситуации:

1)изменение запасов ресурсов;

2)внедрение нового технологического способа производства, позволяющего снизить расход сырья А и В]

3)произошедшие изменения в ценовой политике на предприя­

тии;

4)предполагается выпуск нового вида продукции.

Результаты влияния данных экономических ситуаций на опти­ мальное решение можно получить в ходе проведения экономикоматематического анализа модели на чувствительность.

Анализ на чувствительность оптимального решения базируется на следующих свойствах двойственных оценок.

1. Двойственные оценки характеризуют дефицитность ресур­ сов. Величина W/ в оптимальном решении двойственной задачи яв­ ляется оценкой /-Г0 ресурса; чем больше значение оценки W/, тем выше дефицитность ресурса. Для недефицитного ресурса W/ = 0.

2.Двойственные оценки показывают, как влияют изменения правой части ограничений (запасов ресурсов) на значение целевой функции. Практический интерес представляют границы (нижняя и верхняя) изменения ресурсов, в которых величины оценок остают­ ся неизменными.

3.Двойственные оценки являются показателем эффективности производства отдельных видов продукции с позиции критерия оп­ тимальности. С этой точки зрения в оптимальный план может быть включена лишь та продукция у-го вида, для которой выполняется условие

т

lciyl4.<cj,

/=1

где Uj — оптимальное значение двойственной оценки /-го ресурса; Оу — технологические коэффициенты;

Cj — доход, получаемый с единицы продукции у-го вида; т — количество видов ресурсов.

4. Двойственные оценки позволяют провести сравнение сум­ марных условных затрат и результатов.

Это свойство следует из принципа двойственности, в котором устанавливается связь между значениями функции прямой и двой-

247

ственной задач, т. е. Z^^ = Z^^^ (подразд. 7.8). Это означает, что оценка всех затрат производства должна равняться оценке произ­ веденного продукта.

Используя данные свойства двойственных оценок, проведем анализ изменений исходной задачи, которые могут привести к не­ допустимости и неоптимальности решения.

Обратимся к конкретной задаче и проиллюстрируем примене­ ние анализа оптимального решения на чувствительность на приме­ ре задачи оптимизации ассортимента выпускаемой продукции (пример 7.2).

Составим математические модели прямой и двойственной задач. 1) прямая задача:

максимизировать доход

Установив соответствие между переменными обеих задач и ре­ шая задачи симплекс-методом, запишем итоговую таблицу с опти­ мальным решением (табл. 7.26).

В таблице vi, V2 — выравнивающие переменные двойственной задачи; хз, Х4, Х5, х^ — выравнивающие переменные прямой задачи; Ui — двойственная оценка /-го ресурса (/ = 1, 4).

248

ные

члены

Изменение запасов ресурсов. Значение двойственной оценки то­ го или иного ресурса показывает, насколько возросло бы значение целевой функции, если бы объем данного ресурса (запас) увели­ чился на 1 ед. На основе вышеизложенных свойств двойственных оценок можно записать следующее:

Двойственная оценка для недефицитного ресурса равна нулю, так как ресурс используется не полностью и увеличение его запа­ сов (Abi) не повлияет на оптимальное решение. В нашем примере «2 = «4 ~ О, следовательно, ресурсы 2 и 4 недефицитные. Избыток ресурса 2 (сырья В) составляет 3 ед. (^4 = 3 ед.), а ресурса 4 - 0,6 ед. (Хб = 0,6 ед.).

Используя аналитическое выражение (7.71), мы можем выявить только направление деятельности по устранению «узких» м.ест, обеспечивающее наибольшее изменение целевой функции. Это из­ менение определяется величиной W/ и может быть установлено лишь тогда, когда при изменении величин Ь^ значения переменных и^, соответствующих двойственной задаче, в оптимальном плане оста­ ются неизменными. В связи с этим необходимо определить такие интервалы изменения каждого из свободных членов системы ли-

249