XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 23
Текст из файла (страница 23)
4.3). Поэтому возникает естественный вопрос: какое из них является наиболее эффективным (т.е. за меньшее число итераций приводит к оптимальному решению исходной задачи)? Накопленный практический опыт решения задач целочисленного программирования предписывает строить отсечение Гомори по переменному у;, соответствующему индексу 4 из множества 7 индексов базисных переменных в оптимальной симплекс-таблице, для которого выполняется одно из следующих условий: а) 7; = шах уГН б) = шах 71 7ь леу Йеу ~ Уе уеп г'ЕЯ где 7ьу и Уь определяются соотношениями (4.9), а з — множе- ство индексов свободных переменных.
Пример 4,4. Вернемся к анализу решения полностью целочисленной задачи, рассмотренной в примере 4.3. После двух итераций симплекс-метода (см. табл. 4.3) 7 = = (1, 21,о = (3, 41 и в оптимальном решении У4 — — 9/2, уг — — 7/2, т.е. 74 — — 7г = 1/2 и условие а) не позволяет сделать выбор одного из двух возможных отсечений. А так как (см.
табл. 4.3) у1 1/2 11 11 1/2 -уг < 'угз + 'угд 21/22+ 3/22 24 8 7/22+ 1/22 угз+ 'уг4 то, согласно условию б), следует выбрать базисное перемен- ное уг. 166 4. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ Не останавливаясь на доказательстве сходимости метода Гомори, заметим, что он может быть использован и для решения частаично целочисленных задач, которые отличаются от задачи (4.6) лишь видом требования целочисленности: (4.17) ул Е 1%0(0), Й 6 д, где д — множество индексов переменных модели, на которые накладывается требование целочисленности. При этом д С С ),1, 2, ..., и~ и (1, 2, ..., н) ~,71~ И.
Действительно, пусть 16 д и в оптимальном решении задачи линейного программироваыия с ослабленными ограничениями, которая соответствует рассматриваемой частично целочисленной задаче, базисное переменное у; принимает нецелое значение. Как и в случае полностью целочисленной задачи, из оптимальной симплекс-таблицы выписываем уравнение (4.7). Но теперь некоторые из переменных У, у 6 5, могут не быть целочисленными, поэтому необходимо построить отсечение другого типа, нежели (4.11). Согласно (4.7), (4.9), получаем (4.18) У; — 1пс(11,) = 7; — ~> сеНУ1- эея При этом для переменного модели у;, удовлетворяющего требованию целочисленности, выполняет~я адью из условий: а) у; < < 1пс(Р;); б) У > 1п1(А) + 1. Согласно (4.18), эти условия могут быть представлены в следующем виде: 4 е Метод отсемающнх пдоскостеи (метод 1еме и) 167 о; < О.
В этом случае 5 = 5+ 1з 5 и, согласно (4.19), получаем „'1 Ж,У,)70 (4.21) 4ел+ Кроме того, неравенство (4.20) может быть преобразовано к следующему неравенству: Е оуУ <7; — 1, 1ел или, что то же самое, (4.23) — ~~) оп У >7;. (4.22) уел Неравенства (4.19), (4.20) и, как следствие, неравенства ( . ), (4.22) не могут выполняться одновременно. Но ыеза- ~4.211 висимо от того, какой случай имеет место, для каждого допустимого решения рассматриваемой частично целочисленной задачи будет выполняться ограничеыие Е + 7* ч~;- > 1ея+ 1ел 73 Неравенство (4.23) определяет новое дополнительное ограничение, которое называют отисечеиием Гомори дл.я частинчно целочисленной задачи.
Это ограничение получено без учета требования целочислеыности (4.17) для некоторых переменных модели и может быть заменено более эффективным отсечением '~ АУ,>7;, (4.24) хез где (4.19) об<0, уу1Е; (4.20) оИ>0, уу1Е; 7;; < 7;, Уу 6 Е; 7о~ 7'(1 7' ') 7еу>71 УусЕ. 1-7, оУУУ с 7е Е уел Е сеИуу < 7' 1. уея Пусть 5+ — множество значеыий индекса 7', для которых ац > О, а Я вЂ” множество значений иыдекса у, для которых о07' 7,— 1' ол11 4.3. Метод ветвеи и границ 169 168 4. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ 1 3 9 У1 Уз+ У4 22 22 2' для которого, согласно (4.18), т1 = 1/2, 441з= — 1/22 и э =13) о14 = 3/22 и Я+ = (4).
Таким образом, отсечение Гомори (4.23) для рассматриваемой частично целочисленной задачи принимает следующий вид: или, что то же самое, 1 3 1 УЗ+, У4 ~Э 22 22 2 (4. 25) При переходе к стандартной форме записи ограничения (4.25) 1 3 1 — Уз+ У4 — Уз+ Ув =— 22 22 2 вводим новое переменное ув и искусственное переменное ув. Так же как в методе Гомори для полностью целочисленной задачи, новое ограничение вводим в задачу линейного программирования с ослабленными ограничениями (см. пример 4.3) и симт плекс-методом находим оптимальное решение Х" = (4 10/3) . Графическое решение рассматриваемой задачи цредставлено на рис. 4.6.
Оптимальному решению соответствует точка О(4;10/3). Отсечение Гомори (4.25) записано в переменных х1 = У1 и хз = узл 10х1 + Зхз ( 50. Пример 4.5. Вернемся к задаче целочисленного программирования, рассмотренной в примере 4.3, и предположим, что при ее постановке требование целочисленности х1, хз б 1Ч О (О) заменено требованием х1 б 1ц 0101. Рассмотрим процедуру решения этой частично целочисленной задачи методом Гомори.
Из оптимальной симплекс-таблицы задачи линейного программирования с ослабленными ограничениями (см. табл. 4.3) выписываем уравнение, соответствующее переменному у11 © -х +Зх =В ОЗ х1+(1/7)хе— - 5 СЗ) х1— - 0 04 ха=о 1 05 10х1+Зхз=50 Рис. 4.0 При решении практических задач целочисленного программирования используют различные типы отсечений Гомори, два из которых рассмотрены выше, Тем не менее ни один из известных типов отсечений не обеспечивает высокой эффективности соответствующих вычислительных процедур.
Несмотря на то что метод Гомори является надежным средством решения некоторых задач целочисленного программирования, его практическое использование нецелесообразно, если исходная задача имеет большую размерность. Более того, известны случаи, когда непреднамеренное изменение порядка следования дополнительных ограничений при решении задачи целочисленного программирования небольшой размерности приводило к резкому и неоправданному возрастанию объема вычислений при нахождении оптимального решения. 4.3. Метод ветвей и границ Метод ветвей и границ, основная идея которого рассмотрена в 4.1, является одним из наиболее широко применяемых номбинаторных методов.
Его можно использовать для решения как полностью, так и частично целочисленных задач. Для уяснения специфических особенностей метода ветвей и границ обратимся к полностью целочисленной задаче (4.6). Согласно общей идее метода, сначала решают задачу линейного програланированил е ослабленными ограничениями, соот- 4.3. Метод ветвей и гранма 171 170 4. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ ветствующую исходной задаче целочисленного программирования, и находят ее оптимальное решение У*.
Затем выбирают базисное переменное у;, значение которого )3; в оптимальном решении У" не является целым числом. Так как интервал (ЫЩ, 1вс(Д) + 1) не содержит целых значений у,, то любое допустимое целое значение этого переменного (значение у, в допустимом решенци У е Ч) удовлетворяет одному из неравенств: а) у, < 1в$(р';); б) у; ) 1вФ(11;)+ 1. Введение этих неравенств в задачу линейного программирования с ослабленными ограничениями порождает две новые задачи, множества допустимых решений которых не пересекаются (говорят, что исходная задача разветвляется на две новые задачи, а саму процедуру ее замены совокупностью двух задач, эквивалентных ей в смысле оптимального решения, называют процессом вепзаленця).
Проводимый в процессе ветвления учет требованцл целочцсленностц позволяет исключить из рассмотрения часть множества допустимых решений (см. 4.1 и рис. 4.3). Выбрав любую из двух задач, порожденных исходной задачей, решают соответствующую задачу линейного программирования с ослабленными ограничениями (с целевой функцией из рассматриваемой задачи целочисленного программирования).
Если полученное решение удовлетворяет требованию целочисленности, то оно является оптимальным решением порожденной задачи целочисленного программирования. Это решение фиксируют как наилучшее, дальнейшего ветвления рассмотренной задачи не проводят и переходят к рассмотрению второй порожденной задачи. В противном случае задача разветвляется на две новые задачи. В список задач, порожденных исходной задачей целочисленного программирования, вместо уже рассмотренной вносят две порожденные ею задачи. В этот список внесено уже три задачи, каждую из которых исследуют по той же схеме, что и первую. Как только получают оптимальное решение задачи линейного программирования с ослабленными ограничениями, удовлетворяющее требованию целочисленности, его сопоставляют с уже имеющимся (если таковое есть) н фиксируют наилучшее из них (в смысле оптимального значения целевой функции). Процесс ветвления продолжают до тех пор, пока каждая порожденная задача не приведет к оптимальному решению, удовлетворяющему требованию целочисленности, или пока не будет установлена невозможность улучшения (в смысле оптимального значения целевой функции) уже зафиксированного наилучшего решения.
Для повышения эффективности рассмотренной процедуры вводят понятие границы, на основе которого можно судить о необходимости дальнейшего ветвления каждой иэ задач, порожденных исходной задачей целочисленного программирования. Пусть на каждой итерации 1 определена нижняя граница 1е длЯ оптимального значениЯ целевой фУнкции 1. На пеР- вой итерации значение 7ее выбирают равным значению 7' для любого известного допустимого решения исходной задачи целочисленного программирования, а при отсутствии априорной информации просто полагают Д~ = — оо.
Помимо нижней границы имеется список порожденных задач, подлежащих решению, который на первой итерации содержит лишь исходную задачу целочисленного программирования (4.6). Реализация каждой итерации 1 предполагает последовательное выполнение следующих этапов. Этап 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
