Методы оптимальных решений
Лекция 4
Тема лекции 4: «Целочисленное программирование и дискретная оптимизация»
Разделы лекции:
1. Задача целочисленного линейного программирования. Постановка задачи, примеры задач ЦЛП в экономике.
2. Метод ветвей и границ и его применение для решения задачи ЦЛП.
3. Метод отсекающих плоскостей. Пример решения задачи ЦЛП методом Гомори.
РАЗДЕЛ 1. ЗАДАЧА ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. ПОСТАНОВКА ЗАДАЧИ, ПРИМЕРЫ ЗАДАЧ ЦЛП В ЭКОНОМИКЕ.
Целочисленным (иногда его называют также дискретным) программированием называется раздел математического программирования, изучающий экстремальные задачи, в которых на искомые переменные накладывается условие целочисленности, а область допустимых решений конечна. Изучение этого раздела в курсе «Методы оптимальных решений» вызывается тем, что огромное количество экономических задач носит дискретный, чаще всего целочисленный характер, что связано, как правило, с физической неделимостью многих элементов расчета: например, нельзя построить два с половиной завода, купить полтора автомобиля и т.д. В ряде случаев такие задачи решаются обычными методами, например, симплексным методом, с последующим округлением до целых чисел. Однако такой подход оправдан, когда отдельная единица составляет очень малую часть всего объема (например, товарных запасов); в противном случае он может внести значительные искажения
в действительно оптимальное решение. Поэтому разработаны специальные методы решения целочисленных задач, среди которых можно выделить два направления: методы отсечения
(отсекающих плоскостей) и комбинаторные методы.
Метод отсекающих плоскостей состоит в построении дополнительных ограничений и применении двойственного симплексного метода. Представление о комбинаторных методах дает широко используемый на практике метод ветвей и границ.
На этой лекции мы рассмотрим примеры задач целочисленного программирования, а затем методы их решения.
ПРИМЕРЫ ЗАДАЧ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ.
Рассмотрим сначала простые практические задачи, которые сводятся к задачам ЦЛП, затем обратимся к более сложным. Целочисленное линейное программирование (ЦЛП) ориентировано на решение задач линейного программирования, в которых все или некоторые переменные должны принимать целочисленные (или дискретные) значения. Для удобства, задачи, в которых все переменные должны быть целочисленными, называются полностью целочисленными, а задачи, в которых лишь некоторые переменные должны принимать целочисленные значения, частично-целочисленные.
ПРИМЕР 1. (РАСПРЕДЕЛЕНИЕ КАПИТАЛОВЛОЖЕНИЙ).
Оценивается пять проектов с точки зрения их возможного финансирования на предстоящий трехлетний период. Следующая таблица 1 содержит ожидаемую прибыль от реализации каждого проекта и распределение необходимых капиталовложений по годам.
Таблица 1.
Проект Расходы (млн. долл./год) Прибыль (млн. долл.)
1-й год 2-й год 3-й год
1 5 1 8 20
2 4 7 10 40
3 3 9 2 20
4 7 4 1 15
5 8 6 10 30
Доступный капитал (млн. долл.) 25 25 25
Предполагается, что каждый утвержденный проект будет реализован за трехлетний период. Необходимо определить совокупность проектов, которой соответствует максимум суммарной прибыли. Задача сводится к решению типа «да-нет» относительно каждого проекта. Определим двоичные переменные хj: хj=1, если проект j утвержден,
xj=0, если проект j не утвержден.
Задача ЦЛП будет записана следующим образом. Максимизировать функцию z=20x1+40х2+20х3+15х4+30х5, при ограничениях:
5х1 + 4х2 +3х3 + 7х4 + 8х5 ≤25,
х1+ 7х2 + 9х3 + 4х4 + 6х5 ≤25,
8х1+ 19х2+2х3 + х4 +10х5 ≤25,
х1,х2,х3,х4,х5 = 0 или 1.
Оптимальным целочисленным решением является: х1=х2=х3=х4=1, х5=0 со значением z=95 (млн. долл.). Это решение означает, что необходимо выбрать для финансирования все проекты, кроме пятого.
Интересно сравнить решение данной задачи ЦЛП с решением «обычной» задачи ЛП с теми же ограничениями, но без условия целочисленности переменных. Задача линейного программирования получается в результате замены условия xj =0 или 1 на ограничение 0≤xj≤1 для всех j. Эта задача имеет решение: х1= 0,5789, х2=х3=х4=1, х5= 0,7368, и значение z=108,68 (млн. долл.). Такое решение с точки зрения целочисленной задачи лишено смысла, так как две переменные принимают дробное значение. Можно было бы попытаться округлить полученный результат, что привело бы к: х1=х5=1. Полученное при этом решение является недопустимым, так как нарушаются ограничения задачи (например, при подстановке в левую часть неравенства ограничений 5х1+4х2+3х3+7х4+8х5≤25 значений х1=x2=x3=x4=х5=1 получим: 27≤25). Более существенным в этой ситуации является то, что округление применять нельзя, так как xj представляет решение типа «да—нет», для которого дробные значения лишены смысла.
ПРИМЕР 2. (ЗАДАЧА С ПОСТОЯННЫМИ ЗАТРАТАМИ).
Три сотовых оператора предоставляют услуги мобильной связи. Услуги компании «Три поросенка» стоят 16 рублей в месяц плюс 25 копеек за каждую минуту разговора. Компания «Волк и семеро козлят» оценивает свои услуги в 25 рублей в месяц, но имеет поминутную оплату в 21 копейку. Что касается компании «Маша и медведи», то месячная плата равна 18 рублей, а стоимость минуты разговора – 22 копейки. Пользователь, получивший эти предложения, делает звонки в среднем обычно 200 минут в месяц. Предполагается, что он не вносит помесячной платы за услуги связи, если не пользуется мобильным телефоном для звонков, и что пользователь может распределять звонки между тремя указанными компаниями, как ему захочется. Как он должен использовать три компании, чтобы минимизировать свою помесячную плату за услуги мобильной связи? Эта задача может быть легко решена без использования методов ЦЛП. Тем не менее, поучительно сформулировать ее как целочисленную задачу.
Пусть
x1 - количество минут разговора в месяц через оператора мобильной связи «Три поросенка»;
х2 - количество минут разговора в месяц через оператора мобильной связи «Волк и семеро козлят»;
х3 - количество минут разговора в месяц через оператора мобильной связи «Маша и медведи»;
y1 = 1, если х1>0, и у1=0 при х1=0;
y2 =1, если х2>0, и у2=0 при х2=0,
y3=1, если х3>0, и y3=0 при х3=0.
Для обеспечения равенства уj=1 при положительном значении переменной xj, используем ограничение: xj ≤M•yj; j=1,2,3, где М достаточно большое число, которое не должно ограничивать величину xj. Так как звонки по мобильному телефону занимают около 200 минут в месяц, т.е. хj≤200 для всех j, поэтому достаточно положить М=200.
Теперь можно сформулировать следующую задачу.
Минимизировать z=0,25х1+0,21х2+0,22х3+16y1+25y2+18y3;
при ограничениях:
х1+х2+х3=200;
х1≤200y1;
х2≤200у2;
х3≤ 200у3;
х1≥ 0, х2≥0, х3≥0,
у1, у2, у3 = 0 или 1.
Формулировка задачи показывает, что помесячная j-я оплата за пользование услугами связи является частью целевой функции z лишь при условии уj=1, которое по определению может выполняться лишь тогда, когда xj>0. Если в оптимальном решении будет xj=0, то минимума функции z (с учетом положительности коэффициента при yj) можно достигнуть только при равенстве нулю уj, что и требуется.
Оптимальным решением данной задачи является: х3=200, у3=1, все остальные переменные равны нулю. Это значит, что компания «Маша и медведи» должна быть выбрана оператором услуг мобильной связи. Следует подчеркнуть, что информация, которую несет значение переменной y3=1 , является избыточной, так как такой же результат следует из х3>0 (= 200). В самом деле, основной причиной использования переменных y1, y2 и y3 является лишь учет месячной платы за пользование услугами связи. В сущности, только эти двоичные переменные преобразуют исходную нелинейную задачу в частично-целочисленную, поддающуюся аналитическому решению.
ПРИМЕР 3. (ЗАДАЧА КОММИВОЯЖЕРА).
Дневной график работы предприятия «Яркие краски», производящего краски, включает изготовление партий белой (Б), желтой (Ж), красной (К) и синей (С) красок. Так как предприятие использует одно и то же оборудование для изготовления всех четырех типов краски, необходима его надлежащая чистка между изготовлением различных партий краски. Приведенная ниже таблица 2 содержит время чистки оборудования в минутах, если за изготовлением краски, указанной в строке, следует изготовление краски, указанной в столбце. Например, если за белой краской следует желтая, то время чистки равно 10 минут. Так как за определенным цветом краски не может следовать такой же цвет, то соответствующее время чистки полагается равным бесконечности. Необходимо определить оптимальную последовательность дневного производства четырех типов краски, которая минимизирует суммарное время чистки оборудования.
Таблица 2.
Текущий цвет Время чистки в мин., если следующий цвет
Белый Желтый Синий Красный
Белый ∞ 10 17 15
Желтый 20 ∞ 19 18
Синий 50 44 ∞ 25
Красный 45 40 20 ∞
На рисунке 1 графически представлены условия данной задачи. Каждый цвет краски представлен узлом сети, числа возле дуг, соединяющих узлы, соответствуют времени чистки. Задача, таким образом, сводится к определению кратчайшего контура, который начинается в одном узле, проходит через оставшиеся три узла в точности по одному разу, перед тем как возвратиться в начальный узел. Задачи такого типа известны под общим названием задача коммивояжера, в «классической» формулировке которой коммивояжер пытается определить кратчайший маршрут для посещения n городов, посещая каждый из них только один раз.
Рисунок 1. Задача коммивояжера.
Эту задачу можно решить путем полного перебора шести [(4—1)!=3!= 6] возможных контуров сети. Приведенная ниже таблица 3 показывает, что последовательность узлов Б→Ж→К→С→Б определяет оптимальный контур.
Таблица 3.
Производственный цикл (контур) Суммарное время чистки
Б→Ж→С→К→Б 10+19+25+45=99
Б→Ж→К→С→Б 10+18+20+50=98
Б→С→Ж→К→Б 17+44+18+45=124
Б→С→К→Ж→Б 17+25+40+20=102
Б→К→С→Ж→Б 15+20+44+20=99
Б→К→Ж→С→Б 15+40+19+50=124
Метод полного перебора контуров практически применим лишь для задач малой размерности. Например, сеть с 11 узлами имеет 10!=3628800 контуров. Следовательно, требуется более эффективный подход к решению таких задач.
Определим переменные xij равными 1, если узел j достигается с узла i, и 0 в противном случае. Необходимым условием для контура (маршрута) является то, что узел i связывается лишь с одним узлом и узел j достигается лишь из одного узла. Считая М достаточно большим положительным числом, мы можем записать задачу предприятия «Яркие краски» следующим образом.
Минимизировать функцию z=M•xББ+10•xБЖ+17•хБС+15•хБК+20•xЖБ+M•xЖЖ+19•хЖС+
18•хЖК+50•хСБ+44•хСЖ+M•хСС+25•хСК+45•хКБ+40•хКЖ+20•хКС+M•хКК;
при ограничениях
xББ+xБЖ+хБС+хБК=1;
xЖБ+xЖЖ+хЖС+хЖК=1;
хСБ+хСЖ+хСС+хСК=1;
хКБ+хКЖ+хКС+хКК=1;
xББ+xЖБ+хСБ+хКБ=1;
xБЖ+xЖЖ+хСЖ+хКЖ=1;
хБС+хЖС+хСС+xКС=1;
хБК+хЖК+хСК+хКК=1;
xij =0 или 1 для всех i и j; решение должно быть контуром (маршрутом).
Как видим, формулировка задачи совпадает с таковой для задачи об оптимальных назначениях, за исключением требования, что решение должно образовывать маршрут. В общем случае нет гарантии, что оптимальное решение задачи коммивояжера может быть получено путем решения соответствующей задачи о назначениях, т.е., что оптимальное решение задачи о назначениях образует маршрут. Более вероятно, что оно будет содержать неполные маршруты, соединяющие вместе некоторые подмножества узлов сети. Поэтому были разработаны точные алгоритмы решения задачи коммивояжера, основу которых составляет алгоритм решения задачи о назначениях. Эти алгоритмы отличаются друг от друга сложностью и вычислительной эффективностью.
ПРИМЕР 4. (ЗАДАЧА О ПОКРЫТИИ).
Для обеспечения безопасности студентов отдел безопасности университета устанавливает кнопки экстренного вызова на территории студенческого городка. Отделу желательно установить минимальное количество «тревожных кнопок» таким образом, чтобы на каждой из основных улиц этого городка была расположена, по крайней мере, одна кнопка экстренного вызова. На рисунке 2 представлены основные улицы (от А до К) студенческого городка. Логично расположить «тревожные кнопки» на пересечениях улиц так, чтобы каждая кнопка могла обслуживать, по меньшей мере, две улицы. Из рисунка 2 видно, что данное расположение улиц требует не более восьми «тревожных кнопок».
Определим, что переменная xj равна 1, если «тревожная кнопка» расположена на перекрестке j (j=1, 2, ..., 8), и 0 в противном случае.
Рисунок 2. Задача о покрытии.
Условия задачи требуют установки по меньшей мере одной кнопки экстренного вызова на каждой из 11 улиц (от А до К). Поэтому задачу можно сформулировать следующим образом.
Минимизировать z= х1+х2+х3+х4+х5+х6+х7+х8,
при ограничениях:
(x1+x2≥1) (улица A);
(x2+x3≥1) (улица В);
(x4+x5≥1) (улица С);
(x7+x8≥1) (улица D);
(x6+x7≥1) (улица E);
(x2+x6≥1) (улица F);
(x1+x6≥1) (улица G);
(x4+x7≥1) (улица H);
(x2+x4≥1) (улица I);
(x5+x8≥1) (улица J);
(x3+x5≥1) (улица K);
xj=0 или1; j=1,2,..., 8.
В соответствии с оптимальным решением задачи необходимо установить «тревожные кнопки» на перекрестках 1, 2, 5 и 7.
Рассмотренная выше модель является типичным представителем общего класса задач, именуемых ЗАДАЧАМИ О ПОКРЫТИИ. В этой модели все переменные являются ДВОИЧНЫМИ. Все коэффициенты левой части каждого ограничения равны 0 или 1, а правая часть ограничений имеет вид « ≥ 1». Целевая функция z всегда имеет вид с1х1+с2х2+ … +cnxn, где cj>0 для всех j=1,2,...,n, и подлежит минимизации. В рассмотренном примере сj=1 для всех j. Однако, если величина сj будет равна стоимости установки «тревожной кнопки» j-м перекрестке, то эти коэффициенты могут принимать значения, отличные от 1.
ПРИМЕР 5. (ОГРАНИЧЕНИЯ ТИПА «ИЛИ-ИЛИ»).
Машиностроительная компания «Дед Мазай и зайцы» использует один станок для выполнения трех заказов. Время выполнения, а также срок сдачи каждого заказа даны в приведенной ниже таблице 4. Сроки сдачи заказов вычисляются от начальной даты, т.е. предполагаемого начала выполнения первого заказа. Требуется определить последовательность выполнения заказов, которая минимизирует штраф за задержку сдачи заказов.
Таблица 4.
Заказ Время выполнения заказа (дни) Срок сдачи заказа (дни) Штраф за задержку заказа ($/день)
1 5 25 19
2 20 22 12
3 15 35 34
Определим переменную хj как дату завершения заказа j, измеряемую в днях от начальной даты. Задача имеет два типа ограничений:
(1) ограничения, которые гарантируют, что никакие два заказа не выполняются одновременно;
(2) ограничения по срокам сдачи заказов.
Сначала рассмотрим первый тип ограничений (1).
Два заказа i и j, время выполнения которых pi и рj, соответственно, не будут выполняться одновременно, если:
или xi≥xj+pj; или xj≥xi+pi,
в зависимости от того, будет ли заказ i предшествовать выполнению заказа j или наоборот.
Так как все математические модели имеют дело лишь с совместными ограничениями, мы преобразуем ограничения типа «или—или» путем введения дополнительной двоичной переменной:
yij =1 если заказ i предшествует заказу j, yij=0, если заказ j предшествует заказу i.
При достаточно большом М ограничение типа «или-или» преобразуется в следующие два совместных ограничения. M•yij +(хi – xj) ≥рj и M•(1 – yij) +(хj – xi) ≥рi .
Указанное преобразование гарантирует, что лишь одно из двух ограничений может быть активным в любой момент времени. Если yij=0, первое ограничение является активным, а второе – избыточным: так как его левая часть будет содержать величину М, которая намного больше pi. Если yij=1, первое ограничение является избыточным, а второе активным.
Рассмотрим теперь ограничения по срокам сдачи заказов (2).
При заданной дате dj сдачи заказа j введем в рассмотрение неограниченную по знаку переменную sj. Тогда соответствующее ограничение примет вид: хj+рj+sj=dj.
Если sj ≥0, то заказ сдается в срок, если же sj≤0, получаем убытки, связанные с задержкой сдачи заказа.
Используя стандартную замену: sj=(sj+) – (sj-), где (sj+), (sj-)≥0, приводим ограничение к виду: хj+(sj+)–(sj-)=dj–pj.
Штраф за задержку сдачи заказа пропорционален (sj-). Математическая модель рассматриваемой задачи принимает следующий вид. Минимизировать
Целочисленные переменные y12, y13 и y23 введены для преобразования ограничений типа «или—или» в совместные ограничения. Конечная задача является частично-целочисленной задачей линейного программирования.
Для решения задачи выберем М=100 - число, которое больше суммы времени изготовления всех трех заказов. Оптимальным решением является: х1=20, х2=0 и х3=25. Следовательно, оптимальной последовательностью выполнения заказов будет: 2→1→3. В соответствии с оптимальным решением заказ 2 выполняется за время 0+5=5, заказ 1 - за время 20+5=25 и заказ 3 - за 25+15= 40 дней. В результате выполнение заказа 3 задержано на 40 – 35 = 5 дней, что приводит к штрафу в размере 5• 34=170 долларов.
НА ЧЕМ ОСНОВАНЫ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ?
Методы решения задач целочисленного линейного программирования основаны на использовании вычислительных возможностей методов линейного программирования. Обычно алгоритмы целочисленного программирования включают три шага.
ШАГ 1. «Ослабление» пространства допустимых решений задачи целочисленного линейного программирования путем замены любой двоичной переменной y непрерывным ограничением 0≤у≤1 и отбрасывания требования целочисленности для всех остальных переменных. В результате получается обычная задача линейного программирования.
ШАГ 2. Решение задачи линейного программирования и определение ее оптимального решения.
ШАГ 3. Имея полученное (непрерывное) оптимальное решение, добавляем специальные ограничения, которые итерационным путем изменяют пространство допустимых решений задачи линейного программирования таким образом, чтобы, в конечном счете, получилось оптимальное решение, удовлетворяющее требованиям целочисленности.
Рассмотрим два общих метода генерирования специальных ограничений, о которых идет речь при реализации шага 3.
1 . Метод ветвей и границ.
2. Метод отсекающих плоскостей.
РАЗДЕЛ 2. МЕТОД ВЕТВЕЙ И ГРАНИЦ И ЕГО ПРИМЕНЕНИЕ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ЦЛП.
Основы этого метода объясним на численном примере.
ПРИМЕР 6. Рассмотрим следующую задачу целочисленного линейного программирования.
Максимизировать целевую функцию z=5х1+4х2 при ограничениях: x1+х2 ≤5, 10х1+6х2≤45, переменные x1 ≥0, x2≥0, и целые.
На рисунке 3 пространство допустимых решений задачи целочисленного линейного программирования представлено точками. Соответствующая начальная задача линейного программирования (обозначим ее ЛП0) получается путем отбрасывания условий целочисленности. Ее оптимальным решением будет: х1=3,75; х2=1,25 и z=23,75.
Рисунок 3. Решение начальной задачи линейного программирования ЛП0.
Так как оптимальное решение задачи ЛПО не удовлетворяет условия целочисленности, метод ветвей и границ изменяет пространство решений задачи линейного программирования, так что, в конечном счете, получается оптимальное решение задачи целочисленного линейного программирования. Для этого сначала выбирается одна из целочисленных переменных, значение которой в оптимальном решении задачи ЛП0 не является целочисленным. Например, выбирая х1 (=3,75), замечаем, что область 3≤ х1≤ 4 пространства допустимых решений задачи ЛП0 не содержит целочисленных значений переменной х1 и, следовательно, может быть исключена из рассмотрения, как бесперспективная. Это эквивалентно замене исходной задачи ЛП0 двумя новыми задачами линейного программирования ЛП1 и ЛП2, которые определяются следующим образом:
{Пространство допустимых решений ЛП1}={Пространство допустимых решений ЛП0∩(х1≤3)};
{Пространство допустимых решений ЛП2}={Пространство допустимых решений
ЛП0∩(х1≥4)}.
На рисунке 4 изображены пространства допустимых решений задач ЛП1 и ЛП2. Оба пространства содержат все допустимые решения исходной задачи ЦЛП. Это означает, что задачи ЛП1 и ЛП2 «не потеряют» решения начальной задачи ЛП0.
Если мы продолжим разумно исключать из рассмотрения области, не содержащие целочисленных решений (такие, как 3≤ х1≤ 4), путем введения надлежащих ограничений, то в конечном счете получим задачу линейного программирования, оптимальное решение которой удовлетворяет требованиям целочисленности. Другими словами, будем решать задачу ЦЛП путем решения последовательности непрерывных задач линейного программирования.
Рисунок 4. Пространства допустимых решений задач ЛП1 и ЛП2.
Новые ограничения х1≤3 и х1≥4 взаимоисключаемы, так что задачи ЛП1 и ЛП2 необходимо рассматривать как независимые задачи линейного программирования, что и показано на рисунке 5. Дихотомизация задач ЛП - это основа концепции ветвления в методе ветвей и границ. В этом случае переменная х1 называется переменной ветвления.
Рисунок 5.
Оптимальное решение задачи ЦЛП находится в пространстве допустимых решений либо задачи ЛП1, либо ЛП2. Следовательно, обе подзадачи ДОЛЖНЫ быть решены.
Выбираем сначала задачу ЛП1 (выбор произволен), имеющую дополнительное ограничение х1≤3.
Максимизировать целевую функцию z=5х1+4х2 при ограничениях: x1+х2 ≤5, 10х1+6х2≤45, x1≤3, переменные x1≥0, x2≥0.
Оптимальным решением задачи ЛП1 (которое можно получить с помощью метода решения задач с ограниченными переменными) является: х1=3, х2=2 и z=23.
Оптимальное решение задачи ЛП1 удовлетворяет требованию целочисленности переменных х1 и х2. В этом случае говорят, что задача ЛП1 ПРОЗОНДИРОВАНА. Это означает, что задача ЛП1 не должна больше зондироваться, так как она не может содержать лучшего решения задачи ЦЛП.
Мы не можем в этой ситуации оценить качество целочисленного решения, полученного из рассмотрения задачи ЛП1, так как решение задачи ЛП2 может привести к лучшему целочисленному решению (с большим значением целевой функции). Пока мы можем лишь сказать, что значение z=23 является нижней границей оптимального (максимального) значения целевой функции исходной задачи ЦЛП. Это значит, что любая не рассмотренная подзадача, которая не может привести к целочисленному решению с большим значением целевой функции, должна быть исключена из рассмотрения, как бесперспективная. Если же не рассмотренная подзадача может привести к лучшему целочисленному решению, то нижняя граница должна быть надлежащим образом изменена.
При значении нижней границы z=23 исследуем задачу ЛП2 (единственную оставшуюся не рассмотренную подзадачу). Так как в задаче ЛП0 оптимальное значение целевой функции равно z=23,75, и все ее коэффициенты являются целыми числами, то невозможно получить целочисленное решение задачи ЛП2 (пространство решений которой более узко, чем в задаче ЛП0), которое будет лучше имеющегося. В результате мы отбрасываем подзадачу ЛП2 и считаем ее прозондированной. Реализация метода ветвей и границ завершена, так как обе подзадачи ЛП1 и ЛП2 прозондированы (рассмотрение первой привело к нахождению целочисленного решения, а второй к заключению, что ее возможное целочисленное решение не может быть лучше имеющегося). Следовательно, мы заключаем, что оптимальным решением задачи ЦЛП является решение, соответствующее нижней границе, а именно: х1=3, х2=2 и z= 23.
Остались без ответа два вопроса, связанные с реализацией описанной вычислительной процедуры.
1 . Можно ли было в задаче ЛП0 выбрать переменную х2 в качестве переменной ветвления вместо х1?
2. Можно ли было при выборе подзадачи для зондирования решить сначала задачу ЛП2 вместо ЛП1?
Ответы на оба вопроса положительные. Однако последующие вычисления могут значительно отличаться. Ситуация, когда первой решается задача ЛП2, иллюстрируется схемой вычислений (рисунок 6), подтверждающей высказанную мысль. Оптимальным решением задачи ЛП2 является: х1=4; х2=0,83 и z=23,33.
Рисунок 6.
Поскольку значение переменной х2 (=0,83) не является целым числом, задача ЛП2 исследуется дальше. Рассматриваем подзадачи ЛП3 и ЛП4, используя ветви x2≤0 и х2≥1 соответственно. Это означает, что
{Пространство решений ЛП3}={Пространство решений ЛП2 ∩ (x2≤0)}={Пространство решений ЛП0 ∩ (х1≥4) ∩(x2≤0)};
{Пространство решений ЛП4}={Пространство решений ЛП2 ∩ (х2≥1)}={Пространство решений ЛП0 ∩ (х1≥4)∩(х2≥1)}.
У нас есть три не рассмотренные подзадачи, которые должны быть решены: ЛП1, ЛП3 и ЛП4. Предположим, что мы произвольно выбрали первой задачу ЛП4. Эта задача не имеет решения и, следовательно, является прозондированной. В качестве следующей задачи выберем подзадачу ЛП3. Ее оптимальным решением является: х1=4,5; х2=0 и z=22,5. Нецелочисленное значение переменной х1(x1=4,5) порождает две ветви решений при х1≤4 и х1≥5, и соответствующие им подзадачи ЛП5 и ЛП6. При этом
{Пространство решений ЛП5}={Пространство решений ЛП0 ∩ (х1≥4) ∩ (х2≤0) ∩ (х1≤4)};
{Пространство решений ЛП6}={Пространство решений ЛП0 ∩ (х1≥4) ∩ (х2≤0) ∩ (х1≥5)}.
Теперь не рассмотрены лишь подзадачи ЛП1, ЛП5 и ЛП6. Подзадача ЛП6 прозондирована, так как не имеет допустимых решений. Далее, подзадача ЛП5 имеет целочисленное решение (х1=4, х2=0, z=20) и, следовательно, порождает нижнюю границу (z=20) оптимального значения целевой функции задачи ЦЛП. Теперь остается лишь подзадача ЛП1, решение которой также является целочисленным (х1=3, х2=2, z=23). Следовательно, нижнюю границу значений целевой функции полагаем равной 23. Так как все подзадачи прозондированы, оптимальным решением задачи ЦЛП является решение, соответствующее последней нижней границе, а именно: х1=3, х2=2 и z=23.
Последовательность решения подзадач, показанная на рисунке 6 (ЛП0, ЛП2, ЛП4, ЛП3,ЛП6, ЛП5, ЛП1), является наихудшей; тем не менее, она встречается на практике. Этот пример указывает на основную слабость метода ветвей и границ: как выбирать следующую подзадачу для исследования и как выбирать для нее переменную ветвления?
В процессе решения, представленного на рисунке 5, мы случайно наткнулись на хорошую нижнюю границу значений целевой функции Z на самой первой подзадаче ЛП1, что позволило прозондировать ЛП2 без детальных исследований и закончить вычисления. По существу, мы завершили вычисления, решив лишь одну подзадачу. В процессе решения, представленном на рисунке 6, мы были вынуждены исследовать семь подзадач, и лишь тогда завершились вычисления метода ветвей и границ. Хотя имеются эвристические соображения, позволяющие «угадать», какая из ветвей может привести к улучшенному решению задачи ЦЛП.
Теперь сформулируем алгоритм метода ветвей и границ в общем случае. Предположим, что рассматривается задача максимизации. Зададим нижнюю границу оптимального значения целевой функции z задачи ЦЛП равной (– ∞). Положим i=0.
ШАГ 1. (ЗОНДИРОВАНИЕ И ОПРЕДЕЛЕНИЕ ГРАНИЦЫ).
Выбираем i-ю подзадачу линейного программирования ЛПi для исследования. Решаем ЛПi и зондируем ее, при этом возможна одна из трех ситуаций.
(а) Оптимальное значение целевой функции задачи ЛПi не может улучшить текущей нижней границы.
(b) ЛПi приводит к лучшему допустимому целочисленному решению, чем текущая нижняя граница.
(с) ЛПi не имеет допустимых решений.
Возможны два случая.
Случай 1. Если задача ЛПi прозондирована, нижняя граница изменяется только при условии, что найдено лучшее решение задачи ЦЛП. Если все подзадачи прозондированы, необходимо закончить вычисления: оптимальным решением задачи ЦЛП является то, которое соответствует текущей нижней границе, если такая существует. Иначе положить i=i+1 и повторить ШАГ 1.
Случай 2. Если задача ЛПi не прозондирована, переходим к ШАГУ 2 для выполнения ветвления.
ШАГ 2. (ВЕТВЛЕНИЕ). Выбираем одну из целочисленных переменных хj, оптимальное значение x*j которой в оптимальном решении задачи ЛПi не является целым числом. Исключаем из пространства допустимых решений область: [x*j] <xj<[x*j]+1 (где [v] – целая часть числа v, то есть наибольшее целое число, не превосходящее v) путем формирования двух подзадач ЛП, которые соответствуют ограничениям: хj≤[x*j] и хj≥[x*j]+1.
Положим i =i+1 и переходим к ШАГУ 1.
Описанный алгоритм применим для решения задач максимизации. Для решения задач минимизации в алгоритме необходимо заменить нижнюю границу верхней (начальное значение которой равно z=+∞).
Алгоритм метода ветвей и границ непосредственно распространяется на задачи частично-целочисленного ЛП (в которых лишь некоторые из переменных должны принимать целочисленные значения). Если некоторая переменная является непрерывной, мы просто никогда не выбираем ее в качестве переменной ветвления. Допустимая подзадача определяет новую границу для значения целевой функции, если значения дискретных переменных являются целочисленными и значение целевой функции улучшено по сравнению с текущей границей.
РАЗДЕЛ 3. МЕТОД ОТСЕКАЮЩИХ ПЛОСКОСТЕЙ. МЕТОД ГОМОРИ.
Метод отсекающих плоскостей, как и метод ветвей и границ, начинает работу с оптимального решения (непрерывной) задачи линейного программирования. Однако, вместо ветвления и построения границ, этот метод видоизменяет пространство допустимых решений, последовательно прибавляя специальным образом построенные ограничения (именуемые отсечениями). Рассмотрим идею этого метода на графическом примере. Данный метод путем добавления отсечений (отсекающих плоскостей) преобразует пространство допустимых решений соответствующей задачи линейного программирования в выпуклый многогранник, вершина которого, соответствующая оптимуму, является целочисленной, и представляет решение исходной задачи.
ПРИМЕР 7.
Продемонстрируем применение метода отсекающих плоскостей для решения следующей задачи ЦЛП.
Максимизировать целевую функцию z=7х1+10х2 при ограничениях: (—х1+3х2≤6, 7х1+х2≤ 35, x1≥0, x2≥0, и целые).
На рисунке 7 показан пример двух таких отсечений.
Рисунок 7. Метод отсекающих плоскостей.
Мы начинаем с оптимального решения непрерывной задачи линейного программирования (х1; х2) = (4,5; 3,5) и z=66,5. Затем прибавляем отсечение I, которое вместе с ограничениями исходной задачи линейного программирования приводит к оптимальному решению (х1; х2) =(32/7;3) с z=62. После этого прибавляется отсечение II, которое вместе с отсечением I и исходными ограничениями приводит к оптимальному решению (х1;х2)=(4;3) с z=58. Последнее решение является полностью целочисленным, как и требуется.
Прибавленные отсечения не отбрасывают ни одной исходной допустимой целочисленной точки, но должны проходить, по меньшей мере, через одну целочисленную точку (допустимую или недопустимую). Этим основным требованиям должно удовлетворять любое отсечение. В общем случае может потребоваться любое (конечное) число отсечений для достижения полностью целочисленной экстремальной точки. В действительности количество необходимых для этого отсечений не зависит от размерности задачи в том смысле, что для решения задачи с небольшим количеством переменных и ограничений может потребоваться больше отсечений, чем для задачи большой размерности.
ЧТО ТАКОЕ МЕТОД ГОМОРИ?
Один из методов отсекающих плоскостей известен как метод Гомори. Метод Гомори для линейных задач целочисленного программирования основан на понятии конгруэнтности действительных чисел. Любое действительное число можно представить в виде суммы его целой и дробной частей: х = [х] + {x}, где квадратные скобки [] означают целую часть числа, а фигурные {} – дробную. Например, 7,5 = [7,5] + {7,5}=7+0,5. Неотрицательные числа (для простоты мы будем рассматривать только их) называются КОНГРУЭНТНЫМИ, если равны их дробные части. Если обозначать конгруэнтность чисел символом ~, то, например, 7,5~0,5; 6,3~2,3; в частности, все целые числа конгруэнтны нулю, поэтому условие целочисленности переменной xi можно записать: xi~0.
По методу Гомори первый этап решения целочисленных задач не отличается от обычного расчета по симплексному алгоритму. Если среди значений переменных в оптимальном плане есть дробные, то составляется дополнительное ограничение, отсекающее дробную часть решения, но оставляющее в силе все прочие условия, которым должен удовлетворять оптимальный план. Это дополнительное ограничение присоединяется к исходным ограничениям задачи, и вновь применяется процедура симплексного метода. Алгоритм Гомори позволяет прийти к оптимальному целочисленному решению за конечное число шагов.
ПРИМЕР 8. Пусть для приобретения оборудования, размещаемого на производственной площади 38м2, фирма «Буратино» выделяет 20 млн. руб. Имеются единицы оборудования двух типов: типа А стоимостью 5 млн. руб., требующее производственную площадь 8м2 и имеющее производительность 7 тыс. единиц продукции за смену; и типа Б — стоимостью 2 млн. руб., занимающее площадь 4м2 и дающее за смену 3 тыс. единиц продукции. Требуется рассчитать оптимальный вариант приобретения оборудования, обеспечивающий максимум производительности участка.
Сформулируем экономико-математическую модель задачи.
Пусть х1, x2 — количество приобретаемых машин типа А и типа Б соответственно. Тогда целевая функция задачи будет иметь вид:
z(x1,x2) = 7x1+3х2 → max,
при ограничениях:
5x1 + 2х2 ≤20;
8x1+4x2 ≤ 38;
x1≥0; х2≥0, x1~0, , x2~0.
Сформулирована задача линейного целочисленного программирования. Введем дополнительные переменные х3, х4, с помощью которых исходные неравенства преобразуются в равенства:
5x1 + 2х2 + x3 =20;
8x1+4x2 + x4 = 38.
Решая данную задачу симплекс-методом, получим оптимальный план: x1=1, x2=7,5; z=29,5 (тыс. ед. продукции).
Таблица 5.
Базисные переменные План x1 x2 x3 x4
x1 1 1 0 1 -0,5
x2 7,5 0 1 -2 1,25
Δ=Zj – cj 29,5 0 0 1 0,25
Для нецелочисленной переменной х2 составляем из приведенной симплексной таблицы 5 уравнение:
7,5=x2–2x3+1,25x4;
откуда, x2=7,5+2x3–1,25x4.
Так как x2 — целое число, то целой должна быть и правая часть последнего уравнения (~ есть символ конгруэнтности):
7,5+2x3–1,25x4~0;
Отсюда можно получить, что
0,25x4 ~0,5.
То есть выражение 0,25x4 может быть равно 0,5 или 1,5, или 2,5 и т.д. Следовательно, появляется дополнительное ограничение:
0,25x4 ≥0,5;
которое путем ввода дополнительной неотрицательной целочисленной переменной x5 преобразуется в равенство, так что система ограничений исходной задачи в каноническом виде содержит три уравнения:
5x1 + 2х2 + x3 =20;
8x1+4x2 + x4 = 38;
0,25x4 – x5= 0,5.
Повторив процесс решения симплексным методом для данной расширенной системы ограничений, получим новый оптимальный план, в котором переменные, входящие в базис, принимают целые значения: х1=2; x2=5; x4= 2.
Таким образом, приобретение двух машин типа А и пяти машин типа Б обеспечивает максимум производительности участка, равный 29 тыс. единиц продукции в смену. Заметим, что если бы в качестве плана был выбран вариант, получаемый в результате округления первоначального решения задачи симплексным методом (x1=1; x2=7), то суммарная производительность была бы равна лишь 28 тыс. единиц продукции.
К задачам целочисленного программирования приводят также многие оптимальные задачи теории расписаний, в которой рассматриваются методы оптимизации оперативно- календарного планирования. В качестве примера таких задач можно привести задачу определения оптимальной очередности обработки изделий на различных станках или других рабочих местах.
СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ.
[1] Абчук В.А. Экономико-математические методы: Элементарная математика и логика. Методы исследования операций. СПб.: Союз, 1999. — 320 с.
[2] Таха Х.А. Введение в исследование операций. — 6-е изд. Пер. с англ. — М.: Издательский дом «Вильямс», 2001. — 912 с: ил.
[3] Шелобаев С. И. Математические методы и модели в экономике, финансах, бизнесе: Учебное пособие для вузов. — М.: ЮНИТИ - ДАНА, 2001. - 367 с.
[4] Шикин Е. В., Чхартишвили А. Г. Математические методы и модели в управлении: Учебное пособие. — 3-е изд. — М.: Дело, 2004. — 440 с. — (Серия «Классический университетский учебник»).
[5] Экономико-математические методы и прикладные модели: Учебное пособие для вузов/ В.В. Федосеев, А.Н. Гармаш, Д.М. Дайитбегов и др.; Под ред. В.В. Федосеева. — М.: ЮНИТИ, 1999. - 391 с.