3. Решите задачи из предыдущего упражнения, предполагая, что на переменную Xj не налагается условие целочисленности.

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

Максимизировать z = 2х1 + х2

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

Юх, + 10х2 < 9, 10х, + 5х2> 1, хр х2 > 0 и целые.

5. Решите следующую задачу методом ветвей и границ. Максимизировать z = 18х, + 14х2 + 8х3 + 4х4

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

15х, + 12х2 + 7х3 + 4х4 + хь < 37, х х2, х3, х4, х5 = 0 или 1.

9.2.2. Метод ветвей и границ в системе TORA

Модуль целочисленного программирования системы TORA позволяет интерактивно генерировать деревья подзадач в методе ветвей и границ. Чтобы воспользоваться этой возможностью, в выходном окне модуля целочисленного программирования выберите опцию User-guided В&В (Учебный режим метода ветвей и границ). В этом окне представлена вся информация, необходимая для создания дерева подзадач. На рис. 9.9 показан внешний вид окна, в котором представлен корень N10 дерева подзадач, которое соответствует задаче ЛПО на рис. 9.6 (файл ch9ToraB&BEx9-2-l.txt). Каждый узел определяется двумя цифрами, перед которыми стоит буква N. Левая цифра определяет строку таблицы, в которой находится узел, а правая цифра представляет порядковое значение в пределах той же строки. Например, обозначение N10 на рис. 9.9 указывает, что узел 0 расположен в строке 1 (это единственный узел в этой строке). В программе TORA может быть не более 10 подзадач в одной строке. Но помните, что в автоматическом режиме нет каких-либо ограничений на количество генерируемых подзадач.

Далее следует выбрать переменную ветвления, щелкнув на любом из узлов, помеченных х? . Эти узлы выделены зеленым цветом. Если щелкнуть на записи одного узла над областью, где расположено дерево, появится соответствующее решение. Как показано на рис. 9.10, из решения для узла N10 видно, что х, = 3,75 и х2 = 1,25. Также следует обратить внимание на то, какие переменные ограничены целыми значениями. Щелчок на любой из переменных приведет к автоматическому созданию двух подзадач, которые соответствуют выделенной переменной ветвления. На рис. 9.11 показан результат выбора х, в качестве переменной ветвления в узле N10. К дереву были добавлены узлы N20 (соответствует новому ограничению х, < 3) и N21 (соответствует новому ограничению х, > 4). В узле N20 получено целочисленное решение, поэтому он считается прозондированным. Прозондированные узлы выделяются красным или пурпурным цветом. Пурпурный цвет используется тогда, когда в прозондированном узле была достигнута текущая нижняя граница значения целевой функции, что в данном случае произошло с узлом N20. Узел N21 пока не прозондирован. Поэтому щелчок на нем приведет к созданию следующих узлов в строке 3 дерева. Этот процесс продолжается до тех пор, пока не будут прозондированы все узлы (т.е. пока все они не будут выделены красным или пурпурным цветами).

Рис. 9.10. Выбор переменной ветвления

В верхнем правом углу выходного окна автоматически отслеживается нижняя и верхняя границы целевой функции. Эти границы вычисляются автоматически при зондировании узлов. TORA отбрасывает подзадачи, значения целевых функций которых выходят за текущие границы. Тем не менее можно убрать границы (т.е. снять флажок с опции) для создания полного дерева подзадач. В этом случае узел будет прозондирован только тогда, когда будет получено целочисленное решение или если оно будет недостижимо.

Важно отметить, что в автоматическом режиме TORA выполняет последовательное решение подзадач по принципу первым пришел - первым ушел . Поэтому, вероятнее всего, поиск вручную может привести к более эффективному дереву подзадач, поскольку пользователь может осуществить лучший выбор следующего зондируемого узла.

УПРАЖНЕНИЯ 9.2.2

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

Минимизировать у

при выполнении условий

2(х, + х2 + ...+xls) + y=\b. Все переменные двоичные.