XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 25
Текст из файла (страница 25)
4.7). Каждая вершина дерева решений отображает одну задачу в списке задач, порожденных исходной задачей целочисленного программирования, а каждая ветвь инцидентна одной из задач, вносимой в список на этапе 4 каждой итерации. Связь с графическим представлением объясняет использование термина „ветвь" в названии рассмотренного метода, а термин „граница" в этом названии появился благодаря использованию оценочного (граничного) значения для целевой функции на этапе 2 реализации каждой итерации. Метод ветвей и границ можно было бы назвать методом обрыва ветвей, так как наличие оценочного (граничного) значения для целевой функции позволяет обрывать ветвь на дереве решений даже тогда, когда оптимальное решение соответствующей порожденной задачи не удовлетворяет требованию целочисленности.
Следует также отметить, что метод ветвей и границ можно было бы назвать и мееподом воэвратпа, так как при обрыве некоторых ветвей необходимо вернуться к списку задач, порожденных исходной задачей целочисленного программирования. 4.4. Задачи целочисленного программирования В этом параграфе рассмотрены три задачи математического программированиц которые в их исходных постановках не являются задачами целочисленного программирования, но становятся ими после введения новых переменных. 4.4.
Задачи цело численного лр охрам мир о 179 1. . Задача планирования производства с постояннымн злементамн затрат. Рассмотрим задачу планирования производства и различных видов промышленной продукции П, . О начим: х — объем производства продукции Пй '= 1 и. Г1боз ач 41 в соответствующих единицах измерения; К вЂ” постполнкые элеменепы эагпраеп, т.е. затраты, связанные с производством — текущие продукции П и не зависящие от его объема х", с — текущие затраты на производство единицы продукции П .
(в единицах измерения объема ее производства х ). В этом случае суммарные затраты, связанные с производством продукции П, определяются следующим образом: К+ах, х >О; О, х=О, и естественным является желание, лица, принимаюи4его решее нил, минимизировать общие затраты 4~(Х)= ) 4,(х,), Х=(х4 ... х„), 1=1 при планировании производства. Не останавливаясь на описании множества С допустимых решений и полагая, что оно соответствует задаче линейного программирования, отметим специфическую особенность рассматриваемой задачи планирования производства с постоянными элементами затрат. Эта особенность связана с нелинейностью ел й ц ево укнции по переменным х.
1, и, и не позволяет использовать мето ы д линейного программирования для нахождения оптимального решения. Для преодоления возникших трудностей введем булевы переменные ) 1, х > О; 1О ~1=0, виде: СЬХ»с -+ »наХ; Е Ь=» ~~» аслхю < й;, 1= 1, и, 1=1 алена в следующем виде: (4.26) х»с > О, и =1,п. ~~» х 1=0, ~~» х,ь>Ы. имеют место неравенства и Е егьхь — дг < Мг.
»с=! ~~~,е»ьхь — д» < М», »с=» (4.27) 180 4. ЦЕЛО ЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ Если положительная константа М удовлетворяет условию х, < < М для любого у = 1, и, то х < Му, у = 1, и, и математическал модель рассматриваемой задачи планирования производства с постоянными элементами затрат может быть предста- ~с х, + ~» Кьуь-+ пйп; 1=1 Ь=» 0<х,<Муу, у=1,п, у Е(0, 1~, у=1,п. Из неравенства х < Му» при х, > 0 следует, что уг = 1 и целевою функцию 1" учитывает постоянные элементы затрат К».
Если х = О, то у может принимать значения 0 или 1, однако, поскольку К, > 0 и целевую функцию требуется минимизировать, переменное у должно быть равно нулю. Еще раз напомним, что в исходной постановке задача планирования производства с постоянными элементами затрат не имеет никакого отношения к целочисленному программированию, но после ее преобразования с использованием булевых переменных она превращается в частично целочисленную задачу.
2. Задача с альтернативными ограничениями, Прежде чем переходить к рассмотрению нового класса задач математического программирования, напомним, что под альюперпаспивоб (от латинского а11ег — один из двух) обычно понимают ситуацию, в которой необходимо выбрать одну из двух исключающих друг друга возможностей (эти возможности нередко называют альтернативами). Задачи с альюперпаюпнвнымн (т.е, взаимоисключающими) овраьнчениями внешне очень похожи на задачи линейного программирования, но ими не являются.
Тем более они в своей изначальной постановке не имеют никакого отношения к задачам целочисленного программирования. Задачу с альтернативными ограничениями можно представить в следующем 4лк Задачи целочисленного программирования 181 (~Е»»сХЬ < д»)»с'* (ЯЕгЬХЬ < аг), »с=» е=» Задачи с альтернативными ограничениями, в частности, естественным образом возникают из задач о распределении ограниченных ресурсов при появлении дополнительного требования типа: если продукт П вообще производится, то в количестве, не меньшем д1 (задан минимальный обьем партии).
В этом случае, если х ь — обьем производства продукта П. с использованием к-й технологии, то должно выполняться одно из двух ограничений: Пусть определены такие числа М» и Мг, что для переменных х», ..., х„, удовлетворяющих ограничениям ~~» асяхю <(»;, 1=1,т, хю>0, к=1,п, »с=1 183 4.4, Задачи целочисленного программировании 182 4. ЦЕЛО ЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ Тогда задача (4.2б) может быть преобразована к частично целочисленной задаче: СЬХЬ -+ гоаХ; Ьм1 о Е1 аеяхг < 6;, 1 = 1, п1, Ьм1 о е1ьхь — М1у < д1, Ьм1 о ,'> езьхь — (1 — у)Мз < дз, Ь=1 ха~)0, Й=1,п, уб(0, 1).
(4.28) Действительно, если у =О, то должно выполняться ограничение е11х1+... + е1„х„< д1. Ограничение ез1х1 +... + ез„х„— — Мз < 4(з можно не учитывать, так как оно выполняется автоматически согласно второму неравенству (4.27). Если у = 1, то должно выполняться ограничение ез1х1+... + езпх„< дз, а ограничение еых1+... + е1„х„— М1 < д1 можно не учитывать, так как оно выполняется автоматически согласно первому неравенству в (4.27). Анализ задач (4.26), (4.27) позволяет уяснить следующее: а) задачу с альтернативными ограничениями можно рассматривать как совокупность задач линейного программирования, которые различаются лишь одним (альтернативным) ограничеием' б) решением задачи с альтернативными ограничениями является оптимальное решение той задачи линейного программирования из соответствующей совокупности задач, опти44альное значение целевой у1ункции которой является наибольшим в этой совокупности; в) задача (4.28) позволяет использовать методы целочисленного программирования для решения задач с альтернативными ограничениями.
Замечание 4.2, Возможны и более сложные варианты постановок задач с альтернативными ограничениями, которые могут быть преобразованы к частично целочисленным задачам. Примером подобных задач может служить задача о максимизации целевой функции 7' = с1х1+ ...+ с„х„при условии, что будут выполнены любые й (/с < т) из следующих т ограничений: а;, х, < 6„4 = 1, 1п, Е (4.29) с4ху — 1 тпах; Е 4=1 а, х — Му1<6,, Е 1=1 ~'у, =т-й, еа1 хз ) О, л = 1 и, у, с (О, 1), 1 = 1 т. 3. Задача с взаимозависимыми альтернативами.
Пожалуй, наиболее важными организационными решениями, приводящими к задачам целочисленного программирования, являются альтернативы „да — нет". Альтернативы такого рода часто возникают в задачах организационного управления. Известно [ХУ1], что й из т различных элементов можно выбрать С~ способами, где С~ — число сочетаний (без повторений) из т элементов по х.
Поэтому рассматриваемая задача с альтернативными ограничениями может быть представлена как совокупность С задач линейного программирования. Но е можно для каждого ограничения в (4.29) ввести новое булево переменное у;, которое принимает значение О, если это ограничение выполняется, и значение 1 в противном случае. Затем нужно выбрать достаточно большое число М ) 0 и перейти к решению следующей частично целочисленной задачи: 184 4. ЦЕЛОЧИСПЕННОЕ ПРОГРАММИРОВАНИЕ Обычно в этих задачах переменное модели х определяет выбор конкретного проекта, операции или варианта капиталовложения: ~ 1, ~-й проект выполняется; х.= ( О, у-й проект не выполняется.
А так как переменные ху являются булевыми переменными, то их можно использовать для формализации ограничений, часто возникающих в задачах распределения капиталовложений. Для иллюстрации сказанного предположим, что необходимо формализовать ограничение, допускаюшее выбор не более Й из Х имеющихся проектов. В этом случае имеем Если же необходимо выбрать ровно й проектов из Х имеющих- ся, то ограничение принимает вид х1+ хэ +... + х,~ = й.
Возможными являются ситуации, когда необходимо учитывать ограничение, состоящее в том, что 1-й проект может приниматься лишь при условии принятия у'-го проекта. Такое ограничение можно записать следующим образом: х; — з <О. Действительно, если х = О, то и х; = О. Если же х = 1, то ач < 1, т.е.
возможны оба варианта: х; = О или х, = 1. Предположим теперь, что 1-й и у-й проекты являются взаимоисключающими (альтернативными), а й-й проект может быть принят лишь при условии принятия одного из альтернативных проектов. В этом случае ограничение может быть представлено в следующем виде: хь — х; — я <О. х,+я =1, Таким образом, разнообразные зависимости между решениями о принятии проектов могут быть выражены с помощью линейных ограничений, накладываемых на булевы переменные модели. Вопросы и эадачи Вопросы и задачи 185 4.1 В чем заключается основная идея метода округления и почему этот метод нельзя использовать для точного решения задач целочисленного программированияэ 4 2™ожет ли оптимальное значение целевой функции полностью целочисленной задачи быть больше (для задачи максимизации) оптимального значения целевой функции соответствующей задачи линейного программирования с ослабленными ограничениями? 4.ч.
3. Что объединяет методы отсечений и в чем заключается их принципиальное различие' ? 4.4. ь .. Может ли отсечение Гомори исключить некоторое допустимое решение, удовлетворяюшее требованию целочисленности, но заведомо не являющееся оптимальным? 4.5. Че .. Ч м определяется вид отсечения Гомори и с чем связан основной недостаток методов отсечений? 4.6. М .. Можно ли решить полностью целочисленную задач У путем введения отсечений Гомори для частично целочисленной задачи? 4.7. Чт о объединяет методы отсечений с методом ветвей и границ? В чем заключается их принципиальное различие? 4.8. и ..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
