Модели целочисленного линейного

ПРОГРАММИРОВАНИЯ

 

Рассмотренные ранее модели линейного программирования предполагали, что управляющие переменные – объемы выпуска продукции – представляют собой непрерывные параметры. Вместе с тем, существует большое число задач управления, в которых управляющие переменные по самому смыслу решаемой проблемы могут быть только целыми числами. Примерами могут служить задачи, связанные с определением численности трудовых ресурсов (число работающих должно выражаться целым числом), решение задач об оптимальном распределении единиц подвижного состава на транспортных маршрутах города (на маршруте не может находиться, скажем, 3,5 трамвая), оптимизация распределения станочного парка между цехами предприятия и т.п. Такого рода задачи должны формулироваться как задачи целочисленного программирования. Следует заметить, что зачастую такого рода задачи на практике решают как обычные, с непрерывными параметрами, поскольку используемые методы оптимизации в таком случае гораздо более просты. Однако, несмотря на эффективность такого подхода, в ряде ситуаций он может привести к существенным ошибкам, поскольку полученное таким способом решение может даже оказаться недопустимым.

Рассмотрим модель оптимизации (3.13) из раздела 3.5

 

c₁x₁ + c₂x₂ + c₃x₃ +... + c_nx_n ® max

a₁₁x₁ +a₁₂x₂ + a₁₃x₃ +... + a_1nx_n £ b₁

a₂₁x₁ +a₂₂x₂ + a₂₃x₃ +... + a_2nx_n £ b₂ (3.19)

a₃₁x₁ +a₃₂x₂ + a₃₃x₃ +... + a_3nx_n £ b₃

..............................

a_m1x₁ +a_m2x₂ + a_m3x₃ +... + a_mnx_n £ b_m

 

x_j ³ 0 (j = 1,n)

 

Если наряду с ограничениями задачи (3.19) потребовать, чтобы все переменные x_j (j = 1,n) были целыми, то задача становится задачей целочисленного линейного программирования.

Ограничения задачи (3.19) определяют в n-мерном пространстве выпуклую область OABCD. На рис.3.6 эта область изображена в плоскости двух координат – X_k и X_i. Узлы целочисленной решетки показаны точками. Такие точки, расположенные внутри области OABCD, являются допустимыми решениями задачи целочисленного программирования. Как было показано ранее, оптимальные решения задачи линейного программирования всегда располагаются на границе допустимой области. В данном случае граничные точки не являются даже допустимыми решениями, поскольку ни одна из них не целочисленна. Предположим, что допустимая область сужена до выпуклого многогранника допустимых целочисленных точек внутри допустимой области. На рис.3.6 часть этого выпуклого многогранника изображена в плоскости переменных X_k, X_i в виде заштрихованной области OEFGH, которую можно рассматривать как область допустимых решений некоторой другой задачи линейного программирования. Действительно, если к задаче линейного программирования, определяющей допустимую область OABCD, добавить ограничения типа RR₁, как показано на рис.3.6, то для вновь полученной задачи многоугольник OEFGH будет областью допустимых решений.

Эта область обладает двумя важными свойствами: 1) содержит все допустимые целочисленные точки исходной задачи линейного программирования (поскольку является выпуклым многогранником этих точек); 2) все крайние точки новой области целочисленны. Поэтому любое базисное решение модифицированной задачи линейного программирования имеет своими компонентами целые числа и является искомым оптимальным решением задачи целочисленного линейного программирования.

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

Рассмотрим в качестве примера следующую задачу.

 

Для приобретения оборудования по изготовлению комбикормов фирма может выделить 36 тыс.руб. Оборудование должно быть размещено на производственных площадях, не превышающих 60 кв.м. Фирма может заказать оборудование двух видов: менее мощные машины типа A стоимостью 3 тыс.руб., каждая из которых требует для размещения производственную площадь 3 кв.м. и обеспечивает производительность за смену 2 т комбикормов, и более мощные машины B стоимостью 4 тыс.руб., каждая из которых занимает площадь 5 кв.м. и обеспечивает производительность 2,7 т кормов за смену.

Требуется составить оптимальный план приобретения оборудования, обеспечивающий максимальную общую производительность при условии, что фирма может приобрести не более 8 машин типа B.

Решение. В качестве управляющих переменных данного бизнес-проекта выбираем: x₁ – количество приобретаемых машин типа A и x₂ – количество приобретаемых машин типа B. Тогда, определив целевую функцию Z, выражающую суммарную производительность, которую требуется максимизировать, получим математическую модель задачи в виде

 

Z = 2x₁ + 2,7x₂ ® max (3.20)

 

при ограничениях

 

3x₁ + 5x₂ £ 60 (1)

3x₁ + 4x₂ £ 36 (2)

x₂ £ 8 (3) (3.21)

x₁ ³ 0, x₂ ³ 0

 

x₁, x₂ – целые числа (3.22)

Решим эту задачу графически (рис.3.7). Здесь OKLM – область допустимых решений задачи (3.21), ограниченная прямыми (1), (2), (3) и осями координат. Точками представлена сетка целочисленных значений параметров. Точка L с координатами (4/3, 8) – это точка оптимального, но не являющегося целочисленным, решения задачи (3.21). Прямая (4) является прямой, отсекающей два целочисленных решения, лежащих в допустимой области. При добавлении в систему ограничений условия, соответствующего прямой (4), получим допустимую область расширенной задачи. Эта область на рис.3.7 представлена многоугольником OKNM. В данном случае отсеченное прямой (4) целочисленное решение – точка N(4,6) и является оптимальным решением целочисленной задачи. Таким образом, решение поставленной задачи: Z* = 24,2 при x₁* = 4, x₂* = 6, то есть максимальную производительность 24,2 тонн комбикорма за смену можно достичь приобретением 4 машин малой производительности и 6 машин большой производительности. При этом, поскольку ограничение (1) оказалось неактивным, останется незанятой часть помещения площадью 60 – (12 + 30) = 18 кв.м.

Следует заметить, что если использовать оптимальное решение нецелочисленной задачи – (4/3, 8) и округлить (как это часто делается на практике) до ближайшей допустимой точки, то мы получили бы x₁* =1, x₂ =8. При этих значениях x величина производительности Z = 23,6, что, как видим, не является лучшим решением.

 

 

МОДЕЛИ СЕТЕВОГО ПЛАНИРОВАНИЯ

 

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

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

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

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

 

 

2.7.1. КЛАССИЧЕСКАЯ ТРАНСПОРТНАЯ ЗАДАЧА

 

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

Рассмотрим классическую транспортную задачу. В обычной интерпретации этой модели принято считать, что имеется m различных поставщиков (предприятий или пунктов отправления), располагающих некоторыми изделиями, которые они могут отправить n потребителям (в n пунктов назначения, складов). В частности, предполагается, что предприятие i может отгрузить не более S_i изделий (наличные ресурсы предприятия), а потребителю k требуется не менее D_k изделий (спрос потребителя). Затраты на перевозку единицы груза из пункта отправления i в пункт назначения k равны c_ik. Задача заключается в том, чтобы минимизировать транспортные расходы при перевозке готовой продукции с предприятий на пункты сбыта (склады). Таким образом, в данной задаче управляющими переменными являются объемы перевозок продукции с i-того завода на k-тый склад. Назовем эти переменные x_ik, где индекс i соответствует предприятию, на котором произвели продукцию объемом x, а индекс k отвечает определенному складу, на который эта продукция поступает.

Предприятия и склады (пункты сбыта) можно представить в виде графа, где узлы соответствуют предприятиям и складам, а дуги – маршрутам, связывающим предприятия, с которых вывозят продукцию, со складами, на которые эта продукция поступает (рис.3.8).

 

Тогда каждая переменная x_ik соответствует потоку единиц продукции вдоль ориентированной дуги, соединяющей i-тый и k-тый узлы – "предприятие" – "склад" (именно поэтому такие модели часто называют потоковыми). Каждое такое перемещение продукции сопряжено с определенными затратами. Удельные затраты (на единицу потока), как сказано ранее, обозначены c_ik, где индексы имеют тот же смысл, что и у переменной x_ik.

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

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

Математически задача формулируется следующим образом

 

min (3.22)

 

при ограничениях

(i = 1, 2,..., m) (наличные ресурсы) (3.23)

(k = 1, 2,..., n) (спрос) (3.24)

 

x_ik ³ 0 (i = 1, 2,..., m; k = 1, 2,..., n) (3.25)

 

Величины S_i и D_k на рассматриваемом интервале времени или плановом периоде принимаются постоянными.

Один из важнейших результатов, полученных в теории транспортных сетей, состоит в том, что среди всех оптимальных решений задачи (3.22) – (3.25) существует, по крайней мере, одно решение, в котором все значения x_ik являются целочисленными, если все величины S_i и D_k – положительные целые числа. Поэтому введение вместо условия (3.25) более сильного условия

 

x_ik = 0, 1, 2,... (3.26)

 

не оказывает влияния на значение целевой функции (3.22).

Если затраты, связанные с производством одного изделия, неодинаковы для различных предприятий, то они включаются в величины c_ik. Если, в силу каких-либо физических причин или экономических соображений, некоторое предприятие недоступно для определенного потребителя, то соответствующая величина x_ik исключается из задачи или, когда это более удобно, соответствующая величина c_ik принимается сколь угодно большой.

Чтобы задача имела допустимое решение, естественно, требуется, чтобы общие ресурсы (общая мощность) поставщиков были, по крайней мере, не меньше общего спроса потребителей, то есть, чтобы выполнялось условие . Существует ряд ситуаций, когда можно ожидать, что общая мощность поставщиков превышает общий спрос потребителей. Так, например, величины S_i иногда соответствуют производственным мощностям предприятий для определенного планового периода, а не количеству фактически выпущенной к началу этого периода продукции, предназначенной для распределения между потребителями. Однако при анализе обычной транспортной задачи и построении алгоритма ее решения удобно принять, что общая мощность поставщиков равна общему спросу потребителей, то есть

(3.27)

 

Без потери общности, введением так называемого фиктивного потребителя можно показать, что условие (3.27) всегда выполняется. Пользуясь этим приемом, условия (3.23) также можно записать в виде равенств. Таким образом, в транспортной задаче обычно предполагается, что выполняется условие (3.27), а ограничения (3.23) и (3.24) являются равенствами (если только в конкретной задаче не предполагается что-либо иное). Отсюда модель транспортной задачи принимает вид

min (3.28)

 

при ограничениях

(i = 1, 2,..., m) (предложение) (3.29)

(k = 1, 2,..., n) (спрос) (3.30)

x_ik = 0, 1, 2,... для всех i и k, (3.31)

 

где S_i и D_k – положительные целые числа, удовлетворяющие условию (3.27).

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

 

Применение модели

В математическом выражении модели (3.28) – (3.31) в неявном виде предполагается, что в качестве транспортируемого груза рассматривается только один вид продукции (так называемая однопродуктовая модель). Чем это объясняется? Дело в том, что при удовлетворении требований потребителей в модели не различаются источники поставок. Весь груз, поступающий в пункт назначения k, считается однородным в смысле удовлетворения ограничения по спросу.

Следует обратить особое внимание на допущение об однородности продукта, ибо может показаться, что в силу этого допущения модель имеет лишь весьма ограниченную практическую ценность. В самом деле, разве есть фирмы, имеющие несколько промышленных предприятий, которые распределяют между потребителями всего один вид продукции? Иногда такая "многопродуктовая" фирма, владеющая несколькими предприятиями, может разрабатывать отдельные планы перевозок для каждого из основных видов своей продукции. Однако, как правило, экономически выгодно ограничить число предприятий, снабжающих один склад или район сбыта. Поэтому большинство фирм пользуется планами распределения своей продукции, включающими в явном виде всю ее номенклатуру. Как можно легко себе представить, требуется немалая изобретательность, чтобы "подогнать" реальную распределительную задачу к условиям классической транспортной модели. Отдельные практические подходы такого рода будут рассмотрены в третьей части этой книги. Вместе с тем, следует заметить, что, в случае затруднений с трансформацией исходной задачи в транспортную модель, целесообразно использовать общую модель линейного программирования, опираясь на возможности современных программных средств, реализующих эффективные алгоритмы решения оптимизационных задач в общем виде.