Промежуточные вычислении 10 страница

2. Американский университет формирует комитет по рассмотрению жалоб студен­тов. В соответствии с указаниями, полученными из администрации, в эту комис­сию необходимо включить по крайней мере одну женщину, одного мужчину, од­ного студента, одного администратора и одного преподавателя. Выдвинуты десять кандидатур (обозначенных для удобства буквами от а до;'). Принадлеж­ность этих кандидатур к различным категориям отражена в следующей таблице.

Категория	Кандидатуры
Женщины	а, £>, с, d, в
Мужчины	f, 9, h, i, j
Студенты	a, b, c, j
Администраторы	e, f
Преподаватели	d, g, h, i

Университет заинтересован создать наименьшую по составу комиссию, га­рантирующую представительство каждой из указанных категорий. Сформу­лируйте задачу в виде задачи ЦЛП и найдите ее оптимальное решение, ис­пользуя программу TORA.

3. Округ Вашингтон определил шесть городов, которые нуждаются в службе скорой помощи. Станции скорой помощи могут быть расположены в некото­рых или во всех шести городах. Однако в силу территориальной близости не­которых городов одна станция может обслуживать более одного населенного пункта. Единственным условием является время поездки; оно не должно превышать 15 минут. Приведенная ниже таблица содержит время поездки в минутах между шестью городами.

Глава 9. Целочисленное линейное программирование

Сформулируйте задачу в виде задачи ЦЛП, оптимальное решение которой определит наименьшее количество станций и их расположение. Найдите оп­тимальное решение, используя программу TORA.

4. Сокровища короля Тута находятся в музее в Новом Орлеане. План музея, со­стоящего из нескольких комнат, соединенных открытыми дверями, показан на рис. 9.2. Сторож, находящийся у двери, может наблюдать за двумя смеж­ными комнатами. Администрация музея заинтересована, чтобы в каждой комнате присутствовал сторож, но число сторожей должно быть минималь­ным. Сформулируйте задачу в виде задачи ЦЛП и найдите ее оптимальное решение, используя программу TORA.

I II

—I г

-±-1-¹ ^

_ Т т

Рис. 9.2. План музея

Пример 9.1.4. Ограничения типа "или-или"

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

Заказ	Время выполнения заказа (дни)	Срок сдачи заказа (дни)	Штраф за задержку заказа (долл./день)

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

Определим переменную х как дату завершения заказа /, измеряемую в днях от на­чальной даты. Задача имеет два типа ограничений: 1) ограничения, которые гаран­тируют, что никакие два заказа не выполняются одновременно; 2) ограничения по срокам сдачи заказов. Сначала рассмотрим первый тип ограничений.

Два заказа i и /, время выполнения которых р, и p_jt не будут выполняться одновре­менно, если

или x_t > Xj + Pj, или Xj > x_t + p_t,

в зависимости от того, будет ли заказ i предшествовать выполнению заказа или наоборот.

9.1. Примеры задач целочисленного программирования

Поскольку все математические модели имеют дело лишь с совместными ограниче­ниями, мы преобразуем ограничения типа или-или, введя дополнительную двоич­ную переменную

fl, если заказ i предшествует заказу у, ^уи⁼\п

(0, если заказ j предшествует заказу i.

При достаточно большом М ограничение типа или-или преобразуется в следующие два совместных ограничения.

My,j + [x,-x_t)>_Pj и M(\-y_il) + {x_j-x_i)>p,.

Указанное преобразование гарантирует, что лишь одно из двух ограничений может быть активным в любой момент времени. Если y_tj = 0, первое ограничение является активным, а второе — избыточным (так как его левая часть будет содержать вели­чину М, которая намного больше р). Если у, =1, первое ограничение является из­быточным, а второе — активным.

Рассмотрим теперь ограничения по срокам сдачи заказов. При заданной дате cl сда­чи заказа j введем в рассмотрение неограниченную по знаку переменную Sj. Тогда соответствующее ограничение примет вид

*,+Р,+ ',-<*,■

Если Sj > 0, то заказ сдается в срок, если же s_y < 0, получаем убытки, связанные с за­держкой сдачи заказа. Используя стандартную замену

Sj=s'j-s-, о,

приводим ограничение к виду

Xj+s)-S-j=dj-_Pj.

Штраф за задержку сдачи заказа пропорционален s].

Математическая модель рассматриваемой задачи принимает следующий вид. Минимизировать z = 19л," + 12л; +34^

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

х_х-х₂ + Му₁₂>20, -ж, + х₂ - Му₁₂ > 5 - М, х,-х₃ + Му,₃>15, -х, + х₃- Му₁₃ > 5 - М, х₂ - х₃ + М у₂₃ > 15, -*₂ + *₃-M</₂₃>20-M, х, + sl - si =25-5,

x₂ + sl -s; =22-20,

x₃ + sl -s~ = 35-15,

X,, X₂, X₃, si, Sl, si, Sl, Sj, s₃ >0, Ух2> УXV </₂3 ^{= 0иЛи1}-

408 Глава 9. Целочисленное линейное программирование

Целочисленные переменные у₁₂, у₁₃ и у₂₃ введены для преобразования ограничений типа или-или в совместные ограничения. Конечная задача является частично-целочисленной задачей линейного программирования.

Для решения задачи выберем М = 100 — число, которое больше суммы времени изготовления всех трех заказов.

Оптимальным решением (полученным с помощью программы TORA, файл Ch9ToraEitherOrEx9-l-4.txt) является х_г = 20, х₂ = 0 и х₃ = 25. Следовательно, оп­тимальной последовательностью выполнения заказов будет 2 —> 1 —> 3. В соответст­вии с оптимальным решением заказ 2 выполняется за время 0 + 5 = 5, заказ 1 — за время 20 + 5 = 25 и заказ 3 — за 25 + 15 = 40 дней. В результате выполнение заказа 3 задержано на 40 - 35 = 5 дней, что приводит к штрафу в размере 5 х 34 = 170 долл.

УПРАЖНЕНИЯ 9.1.4

1. Игральная доска состоит из девяти равных квадратов, расположенных 3x3. Требуется заполнить каждый квадрат числом из интервала от 1 до 9 таким об­разом, чтобы сумма чисел каждой строки, каждого столбца и каждой диагона­ли была равна 15. Определите числа в каждом квадрате для следующих случаев.

a) Числа в каждой строке и каждом столбце различны.

b) Числа во всех квадратах различны.

Запишите сформулированную задачу в виде задачи ЦЛП с ограничениями и решите ее с помощью программы TORA.

2. Станок используется для производства двух взаимозаменяемых видов про­дукции. Производительность станка позволяет за день изготовить не более 20 единиц продукции первого вида и 10 единиц второго вида. Существует альтернативная наладка станка, позволяющая ежедневно изготовлять не бо­лее 12 единиц продукции вида 1 и 22 единицы вида 2. Анализ рынка показы­вает, что максимальный суммарный спрос на два вида продукции составляет 35 единиц ежедневно. Предположим, что прибыль от производства единицы продукции первого и второго вида составляет 10 и 12 долл. соответственно. Какая из двух возможных настроек станка должна быть выбрана? Сформу­лируйте задачу в виде задачи ЦЛП и решите ее с помощью программы TORA. (Примечание. Сформулированная двухмерная задача может быть решена пу­тем перебора возможных решений после графического построения простран­ства допустимых решений. Этого нельзя сделать в «-мерной задаче.)

3. Некая компания производит три вида продукции. Ежедневные временные затраты и потребности сырья, необходимые на изготовление одной единицы продукции, приведены в следующей таблице.

Продукция Необходимое время (час./ед.) Необходимое сырье (фунты/ед.)

1 3 4

2 4 3

3 5 6

Доходы от производства единицы каждого вида продукции равны 25, 30 и 22 долл. соответственно. Компания имеет возможность организовать выпуск

9.1. Примеры задач целочисленного программирования

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

Цех	Ресурс рабочего времени (часов в рабочий день)	Ресурс сырья (фунты в день)

Сформулируйте задачу в виде задачи частично-целочисленного линейного программирования и используйте программу TORA для оптимального раз­мещения производства по цехам.

4. Рассмотрите задачу планирования производственной линии, связанной с из­готовлением двух различных изделий на одном станке. Последовательность выполнения необходимых для этого восьми операций изображена на рис. 9.3. Пусть Pj— время выполнения j-й операции 0 = 1, 2, п). Сроки сдачи изделий типа 1 и 2, которые определяются на основе некоторого ис­ходного момента, равны d_l и d₂ соответственно. Предполагается, что любая выполняемая на станке операция должна быть завершена до начала другой операции. Сформулируйте задачу в виде задачи частично-целочисленного линейного программирования.

Изделие 1 Изделие 2

Рис. 9.3. Отношения предшествования опера­ций для упражнения 4

5. Компания владеет фабрикой, которая производит изделия трех типов. Необ­ходимые трудовые затраты и потребности сырья для производства одной единицы каждого из трех типов изделий приведены в следующей таблице.

Тип изделия	Необходимое время (час./ед.)	Необходимое сырье (фунты/ед.)
Наличный дневной объем

Доходы от производства единицы каждого из трех типов изделий равны 25, 30 и 45 долл. соответственно. Если будет производиться изделие типа 3, то его ежедневный объем производства должен быть не менее 5 единиц. Сформули­руйте задачу в виде задачи частично-целочисленного линейного программиро­вания и используйте программу TORA, чтобы найти оптимальное решение.

6. Опишите невыпуклые заштрихованные области допустимых решений, кото­рые изображены на рис. 9.4, в виде набора одновременно выполняющихся

Глава 9. Целочисленное линейное программирование

ограничений. Используйте программу TORA, чтобы найти оптимальное ре­шение, которое максимизирует целевую функцию г = 2л;, + Зл:₂ при ограни­чениях, определяющих область, изображенную на рис. 9.4, а.

^2 ^2

а б в

Рис. 9.4. Пространства решений для упражнения 6

7. Пусть требуется, чтобы любые k ограничений из следующих т ограничений были активными.

g,(x_vx₂.....*„)^Ь„ i = l,2,.... т.

Покажите, как это сделать.

8. Правая часть следующего ограничения может принимать одно из значений ^bi> ^Ь2> ^ъ_т> ^т-^е-

gix_lt х₂.....х_п) < Ь„ Ъ₂,... или Ъ_т.

Покажите, как можно представить это ограничение.

9.2. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ

Методы решения задач целочисленного линейного программирования основаны на использовании вычислительных возможностей методов линейного программиро­вания. Обычно алгоритмы целочисленного программирования включают три шага.

Шаг 1. "Ослабление" пространства допустимых решений задачи цело­численного линейного программирования путем замены любой двоичной переменной у непрерывным ограничением 0 < у < 1 и от­брасывания требования целочисленности для всех остальных пе­ременных. В результате получается обычная задача линейного программирования.

Шаг 2. Решение задачи линейного программирования и определение ее оптимального решения.

Шаг 3. Имея полученное (непрерывное) оптимальное решение, добавляем специальные ограничения, которые итерационным путем изме­няют пространство допустимых решений задачи линейного про­граммирования таким образом, чтобы в конечном счете получи­лось оптимальное решение, удовлетворяющее требованиям целочисленности.

Разработаны два общих метода генерирования специальных ограничений, о ко­торых идет речь при реализации шага 3.

9.2. Методы решения задач целочисленного программирования

1. Метод ветвей и границ.

2. Метод отсекающих плоскостей.

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

9.2.1. Метод ветвей и границ

Впервые метод ветвей и границ был предложен в 1960 году А. Лэндом (A. Land) иДж. Дойгом (G. Doig) для решения полностью целочисленных и частично-целочисленных задач линейного программирования. Позднее в 1965 году Э. Бэлес (Е. Balas) разработал аддитивный алгоритм для решения задач с двоичными пере­менными. Этот алгоритм с вычислительной точки зрения оказался настолько прост (в основном используя только операции сложения и вычитания), что его рассматривали как возможный прорыв в методах решения задач ЦЛП общего вида.³ К сожалению, этот алгоритм не оправдал возлагаемые на него надежды. Более того, если первона­чально алгоритм не был связан с методом ветвей и границ, то вскоре было установле­но, что аддитивный алгоритм является частным случаем метода ветвей и границ.

В этом разделе мы представим только метод ветвей и границ и основы этого ме­тода объясним на численном примере.

Пример 9.2.1

Рассмотрим следующую задачу целочисленного линейного программирования.

Максимизировать z = 5*, + 4х₂

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

х_х + х₂< 5, 10*, + 6х₂ < 45, х_1Г х₂> 0 и целые.

На рис. 9.5 пространство допустимых решений задачи целочисленного линейного про­граммирования представлено точками. Соответствующая начальная задача линейного программирования (обозначим ее ЛПО) получается путем отбрасывания условий цело­численности. Ее оптимальным решением будет х_х = 3,75, х₂ = 1,25 и z = 23,75.

Поскольку оптимальное решение задачи ЛПО не удовлетворяет условию целочис­ленности, метод ветвей и границ изменяет пространство решений задачи линейного программирования так, что в конечном счете получается оптимальное решение за­дачи целочисленного линейного программирования. Для этого сначала выбирается одна из целочисленных переменных, значение которой в оптимальном решении задачи ЛПО не является целочисленным. Например, выбирая х_х (= 3,75), замечаем,

³ Общую задачу ЦЛП можно выразить через двоичные переменные следующим образом. Любая целочисленная переменная х, значения которой не превышают конечной верхней границы и (т.е. 0 < х < и), может быть выражена через двоичные переменные с помощью представления х = 2°у₀ + 2'у, + 2²у₂ +... + 2^кy_t, где к — наименьшее целое число, удовлетво­ряющее условию 2'*'-1>и,а y₀,y,,...,yj —двоичные переменные.

Глава 9. Целочисленное линейное программирование

что область 3 < jc, < 4 пространства допустимых решений задачи ЛПО не содержит целочисленных значений переменной и, следовательно, может быть исключена из рассмотрения, как бесперспективная. Это эквивалентно замене исходной задачи ЛПО двумя новыми задачами линейного программирования ЛП1 и ЛП2, которые определяются следующим образом:

Рис. 9.5. Пространство решений задачи ЦЛП

пространство допустимых решений ЛП1 = пространство допустимых решений ЛПО

+ (х, < 3),

пространство допустимых решений ЛП2 = пространство допустимых решений ЛПО

+ (х, > 4).

На рис. 9.6 изображены пространства допустимых решений задач ЛП1 и ЛП2. Оба пространства содержат все допустимые решения исходной задачи ЦЛП. Это озна­чает, что задачи ЛП1 и ЛП2 "не потеряют" решения начальной задачи ЛПО.

Если мы продолжим разумно исключать из рассмотрения области, не содержащие целочисленных решений (такие как 3 < ж, < 4), путем введения надлежащих огра­ничений, то в конечном счете получим задачу линейного программирования, опти­мальное решение которой удовлетворяет требованиям целочисленности. Другими словами, будем решать задачу ЦЛП путем решения последовательности непрерыв­ных задач линейного программирования.

Новые ограничения х,<3 и х,>4 взаимоисключаемы, так что задачи ЛП1 и ЛП2 необходимо рассматривать как независимые задачи линейного программирования, что и показано на рис. 9.7. Дихотомизация задач ЛП — основа концепции ветвле­ния в методе ветвей и границ. В этом случае х_х называется переменной ветвления.

Оптимальное решение задачи ЦЛП находится в пространстве допустимых решений либо задачи ЛП1, либо ЛП2. Следовательно, обе подзадачи должны быть решены.

9.2. Методы решения задач целочисленного программирования

ЛШ-

0 1 2 3 4 5

Рис. 9.6. Пространства решений задач ЛП1 и ЛП2

Выбираем сначала задачу ЛП1 (выбор произволен), имеющую дополнительное ог­раничение < 3.

Максимизировать z = 5х, + 4х₂

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

х, + х₂ < 5, Юх, + 6х₂<45, *,<3, x_lt х₂>0.

ЛПО

х₁=3,75,х₂= 1,25, z = 23,75

ЛП1

х₁ = 3,х₂=2, z = 23 Нижняя граница (оптимум)

ЛШ

х, = 4, х₂= 0,83, z = 23,33

Рис. 9.7. Ветвление по переменной х_; для создания задач ЛП1 и ЛП2

Оптимальным решением задачи ЛП1 (которое можно получить с помощью метода решения задач с ограниченными переменными, изложенного в разделе 7.3) являет-ся = 3, х₂ = 2 и 2 = 23.

Глава 9. Целочисленное линейное программирование

Оптимальное решение задачи ЛП1 удовлетворяет требованию целочисленности пе­ременных Xj и х₂. В этом случае говорят, что задача ЛП1 прозондирована. Это оз­начает, что задача ЛП1 не должна больше зондироваться, так как она не может со­держать лучшего решения задачи ЦЛП.

Мы не можем в этой ситуации оценить качество целочисленного решения, полу­ченного из рассмотрения задачи ЛП1, ибо решение задачи ЛП2 может привести к лучшему целочисленному решению (с большим значением целевой функции г). Пока мы можем лишь сказать, что значение г = 23 является нижней границей оп­тимального (максимального) значения целевой функции исходной задачи ЦЛП. Это значит, что любая нерассмотренная подзадача, которая не может привес­ти к целочисленному решению с большим значением целевой функции, должна быть исключена из рассмотрения, как бесперспективная. Если же нерассмотренная подзадача может привести к лучшему целочисленному решению, то нижняя гра­ница должна быть надлежащим образом изменена.

При значении нижней границы z = 23 исследуем задачу ЛП2 (единственную остав­шуюся нерассмотренную подзадачу). Так как в задаче ЛПО оптимальное значение целевой функции равно 23,75 и все ее коэффициенты являются целыми числами, то невозможно получить целочисленное решение задачи ЛП2 (пространство реше­ний которой более узко, чем в задаче ЛПО), которое будет лучше существующего. В результате мы отбрасываем подзадачу ЛП2 и считаем ее прозондированной.

Реализация метода ветвей и границ завершена, так как обе подзадачи ЛП1 и ЛП2 про­зондированы (рассмотрение первой привело к целочисленному решению, а второй — к заключению, что ее возможное целочисленное решение не может быть лучше сущест­вующего). Следовательно, мы заключаем, что оптимальным решением задачи ЦЛП яв­ляется решение, соответствующее нижней границе, а именно х, = 3, х₂ = 2 и z = 23.

Остались без ответа два вопроса, связанные с реализацией описанной вычисли­тельной процедуры.

1. Можно ли было в задаче ЛПО выбрать переменную х_г в качестве переменной ветвления вместо х,?

2. Можно ли было при выборе подзадачи для зондирования решить сначала задачу ЛП2 вместо ЛП1?

Ответы на оба вопроса положительные. Однако последующие вычисления могут значительно отличаться. Ситуация, когда первой решается задача ЛП2, иллюстри­руется схемой вычислений (рис. 9.8), подтверждающей высказанную мысль. Оп­тимальным решением задачи ЛП2 является х_г = 4, х₂ = 0,83 и z = 23,33 (проверьте с помощью программы TORA).

Поскольку значение переменной х₂ (= 0,83) не является целым числом, задача ЛП2 исследуется дальше. Рассматриваем подзадачи ЛПЗ и ЛП4, используя ветви х₂<0 и х₂ > 0 соответственно. Это означает, что

пространство решений ЛПЗ = пространство решений ЛП2 + (х₂ < 0) = = пространство решений ЛПО + (х, > 4) +(х₂ < 0),

пространство решений ЛП4 = пространство решений ЛП2 + (х₂ > 1) = = пространство решений ЛПО + (х, > 4) +(х₂ > 1).

9.2. Методы решения задач целочисленного программирования

Рис. 9.8. Другой путь решения задачи примера 9.2.1

У нас есть три нерассмотренные подзадачи, которые должны быть решены, — ЛП1, ЛПЗ и ЛП4. Предположим, что мы произвольно выбрали первой задачу ЛП4. Эта за­дача не имеет решения и, следовательно, является прозондированной. В качестве следующей выберем подзадачу ЛПЗ. Ее оптимальным решением является jc, = 4,5, х₂ = 0 и 2 = 22,5. Нецелочисленное значение переменной х, (= 4,5) порождает две вет­ви решений при ж, < 4 и х, > 5 и соответствующие им подзадачи ЛП5 и ЛП6. При этом

пространство решений ЛП5 = пространство решений ЛПО + (ж, > 4) + (х₂ < 0) + + (х, < 4) = пространство решений ЛПО + (х, = 4) + (х₂ < 0),

пространство решений ЛП6 = пространство решений ЛПО + (х, > 4) + (х₂ < 0) + + (х, > 5) = пространство решений ЛПО + (ж, > 5) + (х₂ < 0).

Теперь не рассмотрены подзадачи ЛП1, ЛП5 и ЛП6. Подзадача ЛП6 прозондирова­на, так как не имеет допустимых решений. Подзадача ЛП5 имеет целочисленное решение (х, = 4, *₂ = 0, 2 = 20) и, следовательно, порождает нижнюю границу (г = 20) оптимального значения целевой функции задачи ЦЛП. Теперь остается лишь подзадача ЛП1, решение которой также является целочисленным (х, = 3, х₂ = 2, 2 = 23). Следовательно, нижнюю границу значений целевой функции пола­гаем равной 23. Так как все подзадачи прозондированы, оптимальным решением задачи ЦЛП является решение, соответствующее последней нижней границе, а именно х_х = 3, х₂ = 2 и z = 23.

Глава 9. Целочисленное линейное программирование

Последовательность решения подзадач, показанная на рис. 9.8 (ЛПО, ЛП2, ЛП4, ЛПЗ, ЛП6, ЛП5, ЛП1), является наихудшей; тем не менее, она встречается на практике. Этот пример указывает на основную слабость метода ветвей и границ: как выбирать следующую подзадачу для исследования и как выбирать для нее пе­ременную ветвления?

В процессе решения, представленного на рис. 9.7, мы случайно наткнулись на хорошую нижнюю границу значений целевой функции на самой первой подзада­че ЛП1, что позволило прозондировать ЛП2 без детальных исследований и за­кончить вычисления. По существу, мы завершили вычисления, решив лишь одну подзадачу. В процессе решения, представленном на рис. 9.8, мы были вынужде­ны исследовать семь подзадач, и лишь тогда завершились вычисления метода ветвей и границ. Хотя имеются эвристические соображения, позволяющие "угадать", какая из ветвей может привести к улучшенному решению задачи ЦЛП (см., например, [3]), не существует строгой теории, которая всегда обеспе­чивала бы надежные результаты.

Теперь сформулируем алгоритм метода ветвей и границ в общем случае. Пред­положим, что рассматривается задача максимизации. Зададим нижнюю границу оптимального значения целевой функции z задачи ЦЛП равной Положим i = 0.

Шаг 2. (Зондирование и определение границы). Выбираем i-ю подзадачу линей­ного программирования ЛГО для исследования. Решаем ЛШ и зондируем ее, при этом возможна одна из трех ситуаций.

a) Оптимальное значение целевой функции задачи ЛГО не может улучшить текущей нижней границы.

b) ЛГО приводит к лучшему допустимому целочисленному решению, чем те­кущая нижняя граница.

c) ЛГО не имеет допустимых решений. Возможны два варианта.

a) Если задача ЛГО прозондирована, нижняя граница изменяется только при условии, что найдено лучшее решение задачи ЦЛП. Если все подзадачи прозондированы, необходимо закончить вычисления: оптимальным ре­шением задачи ЦЛП является то, которое соответствует текущей нижней границе, если такая существует. Иначе положить i = i + 1 и повторить шаг 1.

b) Если задача ЛГО не прозондирована, переходим к шагу 2 для выполнения ветвления.

Шаг 2. Ветвление. Выбираем одну из целочисленных переменных х_:, оптималь­ное значение x'_f которой в оптимальном решении задачи ЛГО не является

целым числом. Исключаем из пространства допустимых решений область [jty]<jt;<[jt]] + l (где [у]— наибольшее целое, не превосходящее v) путем

формирования двух подзадач ЛП, которые соответствуют ограничениям

^хИ +

Положим i = i + 1 и переходим к шагу 1.

9.2. Методы решения задач целочисленного программирования

Описанный алгоритм применим для решения задач максимизации. Для реше­ния задач минимизации в алгоритме необходимо заменить нижнюю границу верх­ней (начальное значение которой равно z = +°°).

Алгоритм метода ветвей и границ непосредственно распространяется на задачи частично-целочисленного ЛП (в которых лишь некоторые из переменных должны принимать целочисленные значения). Если некоторая переменная является непре­рывной, то она никогда не выбирается в качестве переменной ветвления. Допусти­мая подзадача определяет новую границу для значения целевой функции, если значения дискретных переменных являются целочисленными и значение целевой функции улучшено по сравнению с текущей границей.

УПРАЖНЕНИЯ 9.2.1

1. Решите задачу ЦЛП из примера 9.2.1 методом ветвей и границ, начиная с пере­менной х₂ как переменной ветвления. Решите подзадачи с помощью программы TORA, используя опцию MODIFY (Изменить) для задания верхней и нижней границ. Начните с решения подзадачи, включающей ограничение х₂ ^ГхЛ.

2. Постройте дерево подзадач, получаемое при использовании метода ветвей и границ для каждой из приведенных ниже задач. Для удобства в нулевом узле в качестве переменной ветвления всегда выбирайте х_х.

а) Максимизировать z = Зх_х + 2х₂

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

2*, + 5х₂ < 9, 4х, + 2х₂ < 9, х_х, х₂ > О и целые.

Ь) Максимизировать z = 2х_х + Зх₂

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

5х, + 7х₂<35, 4ж, + 9х₂ < 36, х_х, х₂>Ои целые.

с) Максимизировать z = х_х + х₂ при ограничениях

2х_х + 5х₂< 16, 6х_х + Ъх₂ < 27, х_х, х₂ > О и целые.