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

Рассмотрим идеализированный случай, когда все трансакции коммерсанта N выполняются одновременно. Ограничения опреде­ ляются единственным требованием — трансакция возможна лишь при условии, если коммерсант Л'^ располагает наличными ценными бумагами. Другими словами, количество проданных ценных бумаг не должно превышать количество приобретенных. Данные ограни­ чения имеют вид

ГцХ1 + Г12Х2 + ^13^3 "^ ^14^4 "^ ''15^5 ""^6 "" -^7 - Oi

-Х2 + r^-jX-j + Г38Х8 > 0;

-Х3 - xg + Г49Х9 > 0; -Х4 + Г58Х8 > 0;

-Х5 + /-57X7 - Х9 > 0;

Xj>0,J=T79.

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

Пример 7.9. Транспортная задача.

Имеется три поставщика и четыре потребителя однородной продукции. Известны затраты на перевозку груза от каждого поставщика каждому потребителю. Обозначим их с^-, / = 1,3; у = 1,4. Запасы грузов у поставщиков равны GJ, / = 1,3. Известны потреб­ ности каждого потребителя bj,j =1,4. Будем считать, что суммар­ ные потребности равны суммарным запасам:

3 4

Требуется составить такой план перевозок, чтобы обеспечить минимальные суммарные затраты при полном удовлетворении по­ требностей.

Введем переменные Xjj — количество груза, перевозимого от /-ГО поставщика у-му потребителю.

Ограничения задачи выглядят следующим образом:

• потребности всех потребителей должны быть удовлетворены полностью:

200

• условие неотрицательности переменных: ху > О, / = ITI, J = 174.

Целевая функция должна минимизировать суммарные затраты на перевозку:

/=1у=1

Количество поставщиков и потребителей в общем случае может быть произвольным (> 2).

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

1. Ограничения в задачах линейного программирования могут быть выражены как равенствами, так и неравенствами.

2.Линейная функция может стремиться как к максимуму, так и

кминимуму.

3.Переменные в задачах всегда неотрицательны.

Напомним, что от любой из вышеперечисленных задач можно перейти к канонической (основной) задаче линейного программи­ рования.

201

7.3. Графическое решение задачи линейного программирования

Графический способ решения задач линейного программирова­ ния целесообразно использовать для:

•решения задач с двумя переменными, когда ограничения вы­ ражены неравенствами;

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

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

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

ограничения:

Каждое из неравенств (7.35) — (7.36) системы ограничений за­ дачи геометрически определяет полуплоскость соответственно с граничными прямыми a^Xi + ^[/2^2 ~ */» (^ ~ Ь^); Xi = 0; Х2 = 0. В том случае, если система неравенств (7.35) — (7.36) совместна, об­ ласть ее решений есть множество точек, принадлежащих всем ука­ занным полуплоскостям. Так как множество точек пересечения данных полуплоскостей — выпуклое, то областью допустимых ре­ шений является выпуклое множество, которое называется много­ угольником решений. Стороны этого многоугольника лежат на пря­ мых, уравнения которых получаются из исходной системы ограни­ чений заменой знаков неравенств на знаки равенств.

Областью допустимых решений системы неравенств (7.35) — (7.36) может быть:

•выпуклый многоугольник;

•выпуклая многоугольная неограниченная область;

•пустая область;

•луч;

•отрезок;

•единственная точка.

202

Целевая функция (7.34) определяет на плоскости семейство па­ раллельных прямых, каждой из которых соответствует определен­ ное значение Z.

Вектор С = (cj; С2) с координатами Ci и С2, перпендикулярный этим прямым, указывает направление наискорейшего возрастания Z, а противоположный вектор - направление убывания Z.

Если в одной и той же системе координат изобразить область допустимых решений системы неравенств (7.35) - (7.36) и семей­ ство параллельных прямых (7.34), то задача определения максиму­ ма функции Z сведется к нахождению в допустимой области точки, через которую проходит прямая из семейства Z = const, и которая соответствует наибольшему значению параметра Z.

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

Для определения данной вершины построим линию уровня

Z = CiXi + С2Х2 = О, проходящую через начало координат и перпен­ дикулярную вектору С = (Ci;c2), и будем передвигать ее в направ­ лении вектора С = (ci;c2) до тех пор, пока она не коснется послед­ ней крайней (угловой) точки многоугольника решений. Коорди­ наты указанной точки и определяют оптимальный план данной задачи.

Заканчивая рассмотрение геометрической интерпретации зада­ чи (7.34) — (7.36), отметим, что при нахождении ее решения могут встретиться случаи, изображенные на рис. 7.1 — 7.4. Рис. 7.1 харак-

203

теризует такой случай, когда целевая функция принимает макси­ мальное значение в единственной точке А. Из рис. 7.2 видно, что максимальное значение целевая функция принимает в любой точ­ ке отрезка АВ.

На рис. 7.3 изображен случай, когда максимум недостижим, а на рис. 7.4 — случай, когда система офаничений задачи несовмест­ на. Отметим, что нахождение минимального значения Z при дан­ ной системе ограничений отличается от нахождения ее максималь­ ного значения при тех же ограничениях лишь тем, что линия уров­ ня Z передвигается не в направлении вектора С = (ci;c2), а в про­ тивоположном направлении. Таким образом, отмеченные выше случаи, встречающиеся при нахождении максимального значения целевой функции, имеют место и при определении ее минималь­ ного значения.

Для практического решения задачи линейного программирова­ ния (7.34) — (7.36) на основе ее геометрической интерпретации не­ обходимо следующее.

1. Построить прямые, уравнения которых получаются в резуль­ тате замены в ограничениях (7.35) - (7.36) знаков неравенств на знаки равенств.

2.Найти полуплоскости, определяемые каждым из ограниче­ ний задачи.

3.Определить многоугольник решений.

4.Построить вектор С = (с^.с-^.

5.Построить прямую Z = с^Хх + С'^^ = О, проходящую через на­ чало координат и перпендикулярную вектору С.

204

_ 6. Передвигать прямую Z = CiXj + с-^^ в направлении вектора С, в результате чего либо находят точку (точки), в которой целевая функция принимает максимальное значение, либо устанавливают неограниченность функции сверху на множестве планов.

7. Определить координаты точки максимума функции и вычис­ лить значение целевой функции в этой точке.

Пример 7.10. Рассмотрим решение задачи об ассортименте продукции (пример 7.2) геометрическим способом.

Решение

Построим многоугольник решений (рис. 7.5). Для этого в сис­ теме координат X^f^X-i на плоскости изобразим фаничные прямые:

Взяв какую-либо точку, например начало координат, установим, какую полуплоскость определяет соответствующее неравенство. По­ луплоскости, определяемые неравенствами, на рис. 7.5 показаны стрелками. Областью решений является многоугольник OABCD.

Для построения прямой Z = 3xi н- 4x2 ~ О строим вектор-гради­ ент С = (3;4) и через точку О проводим прямую, перпендикулярную ему. Построенную прямую Z_= О перемещаем параллельно самой себе в направлении вектора С. Из рис. 7.5 следует, что по отноше­ нию к многоугольнику решений опорной эта прямая становится в точке С, где функция принимает максимальное значение. Точка С лежит на пересечении прямых Ь^у^ Ly Для определения ее коорди­ нат решим систему уравнений:

2XI+3JC2=9;

X i - X 2 = l .

Оптимальный план задачи х^ = 2,4; Х2=1,4. Подставляя значе­ ния Xj и ^2 в линейную функцию, получим:

2тах=3.2,4 + 4 . 1,4=12,8.

Полученное решение означает, что объем производства продук­ ции Пх должен быть равен 2,4 ед., а продукции Я2 — 1,4 ед. Доход, получаемый в этом случае, составит: Z = 12,8 д. е.

205

Хо ж

z=o

Рис. 7.5. Решение задачи линейного профаммирования геометрическим способом

Геометрическим способом можно также решать задачи линей­ ного программирования с числом переменных более двух. Для это­ го исходную задачу преобразуют методом Жордана—Гаусса (прило­ жение И).

Пример 7.11.

Xi -Х2 +4хз -2X4 =2

Х/>0, / = 1,4

2тах = 4X1 - 2X2 + Хз - ^4-

Используя метод Жордана—Гаусса, произведем два полных ис­ ключения Xi и Х4:

206

В результате приходим к системе

Х]+1,4x3 =1,4; 0,5x2 - 1,3хз + Х4 = -0,3,

откуда

Х1=1,4-1,4хз;

Х4 = -0,3-0,5x2 +1,3x3.

Подставляя эти значения в линейную функцию Z и отбрасывая в последней системе базисные переменные, получим задачу, выра-

-61

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

207

женную только через свободные неизвестные Xi и Ху Найдем мак­ симальное значение линейной функции

Z = 5,9 - 5,9хз - 1,5x2

при следующих ограничениях:

JC3< 1; 0,5x2 - 1,3хз<0,3.

Построим многоугольник решений и линейную функцию в си­ стеме координат Х'^Х^ (рис. 7.6). Согласно рис. 7.6 линейная функ­ ция принимает максимальное значение в точке А, которая лежит на пересечении прямых ^2 и А'2 = 0. Ее координаты (0;0,23).

Максимальное значение функции ^тах = 5,9 - 5,9 • 0,23 - 1,5 • О - 4,54.

Для отыскания оптимального плана исходной задачи подстав­ ляем в преобразованную систему Х2 и Хз-Окончательно получаем Х= (1,078; 0; 0,23; 0,001).

7.4. Анализ моделей на чувствительность

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

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

208

за модели на чувствительность с успехом могут быть использованы графические методы^.

Рассмотрим основные задачи ана.мза на чувствительность на примере 7.10.

Задача 1. Анализ изменений запасов ресурсов.

После нахождения оптимального решения представляется впол­ не логичным выяснить, как отразится на оптимальном решении изменение запасов ресурсов. Для этого необходимо ответить на два вопроса:

1. На сколько можно увеличить запас некоторого ресурса для улучшения полученного оптимального значения целевой функ­ ции Z?

2. На сколько можно снизить запас некоторого ресурса при сохранении полученного оптимального значения целевой функ­ ции Z?

Прежде чем ответить на поставленные вопросы, классифици­ руем ограничение линейной модели как связывающие (активные) и несвязывающие (неактивные) ограничения. Прямая, представля­ ющая связывающее ограничение, должна проходить через опти­ мальную точку, в противном случае, соответствующее ограничение будет несвязывающим. На рис. 7.5 связывающими ограничениями являются ограничения (1) и (3), представленные прямыми L^ и L^ соответственно, т. е. те, которые определяют запасы исходных ре­ сурсов. Ограничение (1) определяет запасы сырья А. Ограничение

(3) определяет соотношение спроса на выпускаемую продукцию. Если некоторое ограничение является связывающим, то соот­

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

При анализе модели на чувствительность к правым частям ог­ раничений определяются:

1) предельно допустимое увеличение запаса дефицитного ре­ сурса, позволяющее улучшить найденное оптимальное решение;

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

Таха X, Введение в исследование операций: В 2-х т. - М.: Мир, 1985.

209