XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 21
Текст из файла (страница 21)
Если в рассматриваемой полностью целочисленной задаче множество С допустимых решений заменить множеством С*, то это не может привести к изменению ее оптимального решения, так как С* получено из С путем отсечения от него подмножества, заведомо не содержащего допустимых решений, удовлетворяющих требованию целочисленности. Но в этом случае оптимальное решение задачи линейного программирования с ослабленными ограничениями и множеством С' допустимых решений соответствует крайней точке множества С'.
Как следствие, оно удовлетворяет требованию целочисленности и обеспечивает экстремальное значение целевой функции не только на С*, но и на С, т.е. является оптимальным решением исходной полностью целочисленной задачи. Основные различия в методах отсечений связаны с процедурами выделения подмножества С' множества допустимых решений задачи целочисленного программирования.
В основе ттомбттматтторттых лтетподое решения задач целочисленного программирования лежит идея перебора всех элементов С множества допустимых решений, удовлетворяющих требованию целочисленности, с целью нахождения оптималь- 4ок Методы решение задач целочисленного программирования 151 ного решения. При этом за счет использования различных специальных процедур, как правило, непосредственно рассматривают лишь часть элементов С, удовлетворяющих требованию целочисленности, а оставшиеся элементы учитывают некоторым косвенным образом.
Наиболее известным комбинаторным методом является лтетттод еетпвей и ерпмпт4, использующий процедуру решения задачи линейного программирования с ослабленными ограничениями, соответствующей исходной задаче целочисленного программирования. Если оптимальное решение Х* задачи линейного программирования с ослабленными ограничениями не удовлетворяет требованию целочисленности 1на рис. 4.3 этому решению соответствует точка В), то из множества С допустимых решений выделяют два непересекающихся выпуклых подмножества Кт и Кз, содержаших все допустимые решения из С, удовлетворяющих требованию целочисленности и ие содержащих Х' (см.
рис. 4.3). Это позволяет заменить рассматриваемую задачу целочисленного программирования совокупностью двух эквивалентных ей (в смысле оптимального решения Х е С) задач с множествами допустимых решений Кт и Кз соответственно, так как Х 6 Кт или Х е Кз. Различные аспекты практической реализации метода ветвей и границ для решения задач целочисленного программирования рассмотрены в 4.3.
Рис. 4.3 152 4. ЦЕЛО ЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ Комбинаторные методы широко используют для решения задач булева програлеленрования, т.е. для решения полностью целочисленных задач, переменные которых принимают значения из множества 10, 1). Эти переменные называют булевыми кеременкыми. Свойства булевых переменных позволяют существенно упростить процедуры поиска оптимального решения. К настоящему времени разработано значительное количество частных методов решения конкретных типов задач целочисленного программирования*.
Тем не менее почти все эти методы и их модификации можно описать на основе единой принципиальной схемы, состоящей иэ трех элементов. Элемент 1. Предусматривается процедура формирования и решения последовательности взаимосвязанных задач, которые называют задачами, корожденкыми исходной задачей, или задачами-катионами, При этом оптимальное решение по крайней мере одной из задач-истоков должно совпадать с оптимальным решением породившей их задачи. Э л е м е н т 2 . Каждой задаче, порожденной исходной задачей, ставится в соответствие так называемая ослабленна* задача 1задача с ослабленнылен ограиаченнялеи), оптимальное решение которой может быть найдено с гораздо меньшими затратами, чем оптимальное решение соответствующей ей задачи-истока.
Специфика ослабленной задачи чаще всего заключается в том, что ее система ограничений является менее жесткой по сравнению с системой ограничений задачи-истока и определяет множество допустимых решений, содержащее все допустимые решения задачи-истока. Как правило, в целочисленном программировании ослабленная задача представляет собой задачу линейного программирования с ограничениями, более слабыми, чем в соответствующей целочисленной задаче- истоке. Очевидно, что если ослабленная задача не имеет допу- 'Смл Вагнер Г., т.
2 или Аиоф Р., Сосиени М., а также; Исследование операций: модели и применение / Под ред. Д. Моудеро и С. Элмограбо. 4 е Метод отсенагипих плосностеи (метод Гомори) 153 стимых решений, то их не имеет и задача-исток. В некоторых модификациях методов целочисленного программирования целевая функция ослабленной задачи также может отличаться от целевой функции задачи-истока. В этом случае окктималькое значение целевой фуккции ослабленной задачи (т.е. значение, соответствующее оптимальному решению) должно быть не меньше оптимального значения целевой функции задачи-истока, если речь идет о задаче максимизации.
Кроме того, оптимальное значение целевой функции ослабленной задачи определяет (для задачи максимизации) верхнюю границу для оптимального значения целевой функции задачи-истока. Эл е м е н т 3. В результате анализа решения ослабленной задачи в зависимости от специфики метода, как правило, принимается решение, относящееся к задаче-истоку: а) исключить ее из рассмотрения; б) заменить одной порожденной задачей 1 выбранной по специальному правилу из определенной совокупности; в) заменить системой порожденных задач. Следует отметить, что существуют и другие подходы к решению задач целочисленного программирования, которые в общем случае не гарантируют нахождения оптимального решения, но приводят к допустимому решению, близкому (в смысле значения целевой функции) к оптимальному, а иногда и совпадающему с ним.
В основе одного из таких подходов лежит идея использования случайной выборки допустимых решений с последующим улучшением (в смысле значения целевой функции) каждого из них, когда возможность улучшения допустимого решения достаточно просто обнаружить. 4.2. Метод отсекающих плоскостей (метод Гомори) Метпод отасекающих клоскостаей, известный также как метпод Гомори, относится к методам отсечений и является одним из наиболее широко используемых методов решения 2х1+ хз -+ шах; 0,75х, + 1,5хт < 4,8; хы хт > О, хм хт Е 1к4О (О).
(4. 1) 15ут+ 30ут+ уз = 96, х +1,5х =4„8 2хт=б Таблица 4.1 Рис. 4.4 96 1 у1 = — — 2ут - — уз 15 15 (4.2) 154 4, ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ задач целочисленного программирования. Для уяснения специ- фических особенностей метода Гомори сначала обратимся к рассмотрению следующего элементарного примера. Пример 4.2.
Пусть необходимо найти решение полностью целочисленной задачи Понятно, что в данном случае можно воспользоваться геометричесним методом решения задач линейного программирот ванил (рис. 4.4) и найти как решение Хо = (6 О) исходной задачи целочисленного программирования, так и решение Х' = = (32/5 О) соответствующей ей задачи линейного программирования с ослабленными ограничениями.
Всвязи со спецификой задачи целочисленного программирования реализация метода Гомори предполагает преобразование ограничений задачи к эквивалентным им ограничениям, содержащим лишь целые коэффициенты. Это необходимый шаг. Из дальнейшего будет видно, что как исходные, так и новые переменные должны быть целочисленными. Между тем наличие дробных коэффициентов может приводить к нарушению целочисленности новых переменных. В этом случае метод 4.2. Метод отсекаюппст плоскостей (метод Гомори) 155 отсекающих плоскостей может не давать допусп1имого целочисленного решения даже тогда, когда исходная задача такое решение имеет (см., например, задачу 4.13).
В рассматрива; емом случае ограничение 0,75х~+ 1,5хэ < 4,8 преобразуется к эквивалентному ограничению 15хт+ 30хз < 96, а при переходе к задаче линейного программирования в стандартной форме с ослабленными ограничениями, соответствующей исходной полностью целочисленной задаче, оно принимает следующий вид: где у1 — — хы ут = хт и уз — новое неотрицательное переменное. Получив оптимальное решение Х* задачи линейного программирования с ослабленными ограничениями, которое не удовлетворяет требованию целочисленности (табл. 4.1), конструируем дополнительное ограничение.
Этому ограничению должны удовлетворять все допустимые решения рассматриваемой задачи линейного программирования с ослабленными ограничениями, для которых выполнено требование целочисленности, и не должно удовлетворять решение Х*, т.е. Х' перестает быть допустимым решением (см.
рис. 4.4). С первой строки оптпимальной симплекс-тпаблицы, т.е. той таблицы, которая соответствует заключительной итерации симплекс-метода и приводит к оптимальному решению (см. табл, 4.1, итерацию 1), считываем уравнение 157 1 96 2уз+ уз Е Е 15 15 Таблица 4.2 1 6 — уз = а+ —, а Е Е. 15 15' (4.4) 156 4. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ фактически представляющее собой исходное ограничение (4.1) после его умножения на 1/15. Поэтому оно должно удовлетворяться для всех допустимых решений, в том числе и для тех, для которых выполнено требование целочисленности. Для рассматриваемой полностью целочисленной задачи имеем уг, уз, уз Е Я0 (0).
Поэтому, согласно (4.2), и, как слеДствие, Длн любых аг, аз, аз Е Е сУЩествУет а Е Е, такое, что (2 — аг)уз — ( — — аз/уз — ( — — аз) = а. (4.3) (,15,) (,15 Каждое действительное число х можно разложить в сумму его целой части 1пФ(х) и дробной части )гас(х). Напомним, что целая часть действительного числа х — это наибольшее целое число, не превосходящее х. Дробную часть числа х можно определить как действительное число )гас(х) Е [О, 1), для которого разность х — вегас(х) есть целое число. Полагаем аг — — 1пЦ2) = 2, аз = 1п1(1/15) = 0 и аз — — 1п1(96/15) = = 6. В этом случае соотношение (4.3) может быть преобразовано к следующему уравнению: А так как уз > О, то из (4.4) следует, что а > О, и можно выписать новое ограничение, которое называют огпсенаюмдей гзлосмосгггью: 1 6 — Уз > (4.5) 15 15 Использование неравенства (4.5) для нахождения решения рассматриваемой полностью целочисленной задачи предполагает введение нового переменного у4 и представление полученно- 4ль метод отсекагоигик плоскостей (метод Гоиори) го ограничения в стандартной форме: ! 6 Уз У4 15 15' а также введение искусственного переменного уя и целевой функции гс = — уз вспомогательной задачи линейного программирования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
