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

в нашем примере сырье А и соотношение спроса на выпуска­ емую продукцию Пх и ^2 являются дефицитными ресурсами (в табл. 7.3 — ресурсы 1, 3).

Рассмотрим сначала ресурс - сырье А. На рис. 7.7 при увеличе­ нии запаса этого ресурса прямая Li перемещается вверх, парал­ лельно самой себе, до точки К^ в которой пересекаются линии ог­ раничений L2, 1з и ^4- ^ точке АГ ограничения (2), (3) и (4) стано­ вятся связываюихими; оптимальному решению при этом соответст­ вует точка К, di пространством (допустимых) решений становится многоугольник АКДО, В точке К ограничение (1) (для ресурса А) становится избыточным, так как любой дальнейший рост запаса соответствующего ресурса не влияет ни на пространство решений, ни на оптимальное решение.

Таким образом, объем ресурса А не следует увеличивать сверх того предела, когда соответствующее ему ограничение (1) стано­ вится избыточным, т. е. прямая (1) проходит через новую опти­ мальную точку К. Этот предельный уровень определяется следую-

Хо ж

2 = 0

Рис. 7.7. Геометрическая интерпретация решения задачи линейного программирования (изменение ресурса А)

210

щим образом. Устанавливаются координаты точки К, в которой пе­ ресекаются прямые ^2, ^3 и ^4' т. е. находится решение системы уравнений

3x1+2x2=13;

Х) ~ Х2 = 1;

Х2 = 2 .

В результате получается Xj = 3 и Х2 = 2. Затем, путем подста­ новки координат точки /Г в левую часть ограничения (1), определя­ ется максимально допустимый запас ресурса А:

2x1 -Ь 3X2 =^ 2 . 3 + 3 • 2 =12.

Рис. 7.8 иллюстрирует ситуацию, когда рассматривается вопрос об изменении соотношения спроса на продукцию Я1 и Я2.

Рис. 7.8. Геометрическая интерпретация решения задачи линейного программирования (изменение спроса на продукцию)

2U

Новой оптимальной точкой становится точка Е, где пересека­ ются прямые Li и Z/2. Координаты данной точки находятся путем решения системы уравнений (1) и (2) следующим образом:

2x1+3x2=9;

3x1+2x2=13.

В результате получается Х| = 4,2; Х2 = 0,2, причем суточный спрос на продукцию Щ не должен превышать спрос на продукцию Я2 на величину Xj - Х2 = 4,2 - 0,2 = 4 ед.

Дальнейшее увеличение разрыва в спросе на продукцию Пу и III не будет влиять на оптимальное решение.

Рассмотрим вопрос об уменьшении правой части несвязывающих ограничений. Ограничение (4) Х2 < 2 фиксирует предельный уровень спроса на продукцию Я2. Из рис. 7.5 следует, что, не изме­ няя оптимального решения, прямую Ц (АВ) можно опускать вниз до пересечения с оптимальной точкой С. Так как точка С имеет ко­ ординаты Xi = 2,4; Х2 = 1,4, уменьшение спроса на продукцию IT2 до величины Х2 = 1,4 никак не повлияет на оптимальность ранее полученного решения.

Рассмотрим ограничение (2) 3xi + 2x2 < 13, которое представля­ ет собой ограничение на недефицитный ресурс — сырье В, Ив этом случае правую часть — запасы сырья В — можно уменьшать до тех пор, пока прямая £2 не достигнет точки С. При этом правая часть офаничения (2) станет равной 3xi + 2x2 = 3 • 2,4 + 2 • 1,4 = 1^,0, что позволяет записать это ограничение в виде: 3xi + 2x2 < 10. Этот результат показывает, что ранее полученное оптимальное решение не изменится, если суточный запас ресурса В уменьшить на 3 ед.

Результаты проведенного анализа можно свести в табл. 7.3:

212

Задана 2, Определение наиболее выгодного ресурса.

В задаче 1 анализа на чувствительность мы исследовали влия­ ние на оптимум увеличения объема дефицитных ресурсов. При ог­ раничениях, связанных с дополнительным привлечением ресур­ сов, естественно задать вопрос: какому из ресурсов следует отдать предпочтение при вложении дополнительных средств? Для этого вводится характеристика ценности каждой дополнительной еди­ ницы дефицитного ресурса, выражаемая через соответствующее приращение оптимального значения целевой функции. Такую ха­ рактеристику для рассматриваемого примера можно получить не­ посредственно из таблицы, в которой приведеш>1 результаты реше­ ния задачи 1 на чувствительность. Обозначим ценность дополни­ тельной единицы ресурса / через у^. Величина у^ определяется из соотношения

Максимальное приращение Z

Полученные результаты свидетельствуют о том, что дополни­ тельные вложения в первую очередь следует направить на увеличе­ ние ресурса А и лишь затем — на формирование соотношения спро­ са на продукцию Я^ и продукцию Я2. Что касается недефицитных ресурсов, то, как и следовало ожидать, их объем увеличивать не следует.

Задача 3, Определение пределов изменения коэффициентов целевой функции.

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

213

При анализе модели на чувствительность рассмотрение коэф­ фициентов целевой функции необходимо дополнить исследо­ ванием следующих вопросов:

1) каков диапазон изменения того или иного коэффициента це­ левой функции, при котором не происходит изменения оптималь­ ного решения?

2) на сколько следует изменить тот или иной коэффициент целевой функции, чтобы сделать некоторый недефицитный ре­ сурс дефицитным, и, наоборот, дефицитный ресурс сделать не­ дефицитным?

Ответим на поставленные вопросы на нашем примере. Рассматривая первый вопрос, обозначим через С] и С2 доходы

предприятия от продажи единицы продукции П^ и IIi соответст­ венно. Тогда целевую функцию можно представить в следующем виде:

Z = С^Хх + 02^2'

На рис. 7.5 видно, что при увеличении с^ или уменьшении Ci прямая, представляющая целевую функцию Z, вращается (вокруг точки С) по часовой стрелке. Если же с^ уменьшается или С2 увели­ чивается, эта прямая вращается в противоположном направлении — против часовой стрелки. Таким образом, точка С будет оставаться оптимальной точкой до тех пор, пока наклон прямой не выйдет за пределы, определяемые наклонами прямых для ограничений (1) и(3).

Когда наклон прямой Z станет равным наклону прямой L^, по­ лучим две альтернативные оптимальные угловые точки - С и В. Аналогично, если наклон прямой Z станет равным наклону прямой для ограничения (3), будем иметь альтернативные оптимальные уг­ ловые точки С и D. Наличие альтернативных оптимумов свидетель­ ствует о том, что одно и то же оптимальное значение Z может до­ стигаться при различных значениях переменных Ху и Х2. Как толь­ ко наклон прямой выйдет за пределы указанного выше интервала Cj, получим некоторое новое оптимальное решение.

Рассмотрим на нашем примере, каким образом можно найти допустимый интервал изменения Cj, при котором точка С остается оптимальной. Исходное значение коэффициента С2 = 4 оставим не­ изменным. На рис. 7.5 видно, что значение с^ можно уменьшать до тех пор, пока прямая Zne совпадет с прямой Zj (отрезок BQ.

Это крайнее минимальное значение коэффициента Cj можно определрггь из равенства углов наклонов прямой Zn прямой Lj. Так

как тангенс угла наклона для прямой Z равен —, а для прямой (1) 4

214

равен —, то минимальное значение Cj определим из равенства

- j = T, откуда mm q =—. На рис 7.5 видно, что значение с^ мож-

но увеличивать беспредельно, так как прямая Z при С2 = 4 и Cj -> + с» не совпадает с прямой ^з (отрезок DQ и, следовательно,

8

точка С при всех значениях коэффициента ^i > -• будет единствен­ ной оптимальной.

Интервал изменения Cj, в котором точка С по-прежнему оста­ ется единственной оптимальной точкой, определяется неравенст-

будут как точка С, так и точка В. Как только коэффициент Cj становится меньше — , оптимум смещается в точку В.

Можно заметить, что, как только коэффициент Cj оказывается

меньше ^ , ресурс 3 становится недефицитным, а ресурс 4 - де-

3 фицитным. Для предприятия это означает следующее: если доход

от продажи единицы продукции Щ станет меньше — д. е., то наи- 3

более выгодная производственная программа предприятия должна предусматривать выпуск максимально допустимого количества про­ дукции П2 (полностью удовлетворять спрос на продукцию IIj).

При этом соотношение спроса на продукцию Щ и II2 не будет лимитировать объемы производства, что обусловит недефицитность

о

ресурса (3). Увеличение коэффициента Ci свыше — д. е. не снима­ ет проблему дефицита ресурсов (1) и (3). Точка С — точка пересе­ чения прямых Zj и ^3 ~" остается все время оптимальной.

7.5. Симплекс-метод

Общая идея симплекс-метода

Для начала работы требуется, чтобы заданная система ограни­ чений выражалась равенствами, причем в этой системе ограниче­ ний должны быть выделены базисные неизвестные. Решение зада­ чи при помощи симплекс-метода распадается на ряд шагов. На каждом шаге от данного базиса В переходят к другому, новому ба­ зису В^ с таким расчетом, чтобы значение функции Z уменьшалось,

215

т. е. Z^\ < Z^. Для перехода к новому базису из старого базиса уда­ ляется одна из переменных и вместо нее вводится другая из числа свободных. После конечного числа шагов находится некоторый ба­ зис Б^\ для которого Z^k) есть искомый минимум для линейной функции Z, а соответствующее базисное решение является опти­ мальным либо выясняется, что задача не имеет решения.

Алгоритм симплекс-метода

Рассмотрим систему ограничений и линейную форму вида:

Используя метод Жордана—Гаусса (приложение И), приведем записанную систему к виду, где выделены базисные переменные.

Введем условные обозначения:

Xj, Х2, ..., х^ — базисные переменные; Xf^i, х^2^ ..., Xfj — свободные переменные.

По последней системе ограничений и целевой функции Z пост­ роим табл. 7.5.

Данная таблица называется симплекс-таблицей. Все дальнейшие преобразования связаны с изменением содержания этой таблицы.

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

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

216

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

3.На пересечении разрешающей строки и разрешающего столб­ ца находится разрешающий элемент.

4.Если имеется несколько одинаковых по величине симп­ лекс-отношений, то выбирают любое из них. То же самое отно­ сится к положительным элементам последней строки симлекстаблицы.

5.После нахождения разрешающего элемента переходят к сле­ дующей таблице. Неизвестные переменные, соответствующие раз­ решающей строке и столбцу, меняют местами. При этом базисная переменная становится свободной переменной, и наоборот. Симп­ лекс-таблица преобразована следующим образом (табл. 7.6).

6.Элемент табл. 7.6, соответствующий разрешающему элемен­ ту табл. 7.5, равен обратной величине разрешающего элемента.

7.Элементы строки табл. 7.6, соответствующие элементам раз­ решающей строки табл. 7.5, получаются путем деления соответст­ вующих элементов табл. 7.5 на разрешающий элемент.

8.Элементы столбца табл. 7.6, соответствующие элементам раз­ решающего столбца табл. 7.5, получаются путем деления соответст­ вующих элементов табл. 7.5 на разрешающий элемент и берутся с противоположным знаком.

9.Остальные элементы вычисляются по правилу прямоуголь­ ника: мысленно вычерчиваем прямоугольник в табл. 7.6, одна вер-

217

Таблица 7.6

Преобразование симплекс-таблицы

шина которого совпадает с разрешающим элементом, а другая — с элементом, образ которого мы ищем; остальные две вершины оп­ ределяются однозначно. Тогда искомый элемент из табл. 7.6 будет равен соответствующему элементу табл. 7.5 минус дробь, в знаме­ нателе которой стоит разрешающий элемент, а в числителе — про­ изведение элементов из двух неиспользованных вершин прямо­ угольника.

10.Как только получится таблица, в которой в последней стро­ ке все элементы отрицательны, считается, что минимум найден. Минимальное значение функции равно свободному члену в строке целевой функции, а оптимальное решение определяется свободны­ ми членами при базисных переменных. Все свободные переменные

вэтом случае равны нулю.

11.Если в разрешающем столбце все элементы отрицательны, то задача не имеет решений (минимум не достигается).

Пример 7.12. Решение задачи симплекс-методом:

Xj — ^2 + Х4 = 1; xi + Х2 + Х5 = 2.

218

^max — 2Xi — X2 + ЗХ3 ~ 2x^ + X5.

Приведем задачу к виду, допускающему применение симплекс-

Разыскиваем в последней строке наименьший положительный элемент, в нашем примере он равен + 6, первый столбец коэффи­ циентов будет разрешающим. Определим отношение свободных членов к положительным элементам разрешающего столбца. Ми­ нимальное симплекс-отношение равно 1. Разрешающий элемент находится на пересечении строки переменной х^ и столбца - Xj.

Переходим к следующей таблице, используя правило прямо­ угольника (табл. 7.8):

219