Пример решения задачи целочисленного линейного программирования методом ветвей и границ

Требуется решить следующую задачу:

 

max 2х₁ + х₂

5х₁ + 2х₂ 10

3х₁ + 8х₂ 13

х_1,2 0

х_1,2 Z

 

Вначале решим эту задачу графически без ограничений целочисленности. Решение может быть найдено как симплекс-методом, так и графически. Найдем его графически (рисунок 4). Координаты точки оптимума можно найти, решив систему уравнений:
5х₁ + 2х₂ = 10 х₁=27/17

3х₁ + 8х₂ = 13 х₂=35/34

Х_G = (27/17;35/34), z_G=143/34

 

 

 

Рисунок 4 - Графическое решение задачи без ограничений целочиелейности

Начнем строить дерево, первая вершина которого будет соответствовать всей ОДП нецелочисленной задачи (G), а ее оценка будет равна z_G (рис.5).

 

 

 

Рисунок 5 - Схема метода ветвей и границ

 

Полученный план не является целочисленным, поэтому возьмем его произвольную нецелочисленную компоненту, например, первую (х₁ Z; [х₁] = [27/17] = 1) и разобьем ОДП на две части следующим образом:

G₁={X G: х₁ 1}

G₂={X G: х₁ 2}

 

Это означает, что в область G₁ войдут все точки из G, у которых абсцисса не больше 1, а в G₂ - у которых она не меньше 2. Точки с дробными значениями абсциссы от 1 до 2 исключены из рассмотрения.

Изобразим эти области на графике (рисунок 6).

Из рисунка 6 видно, что G₂ представляет собой одну точку Х_G2=(2;0), следовательно, на этом множестве оптимум задачи равен 4 ( ₂=4).

План Х_G2 является целочисленным, следовательно, решение целочисленной задачи уже, возможно, найдено. Однако, следует еще найти оценку множества G₁|. Она может оказаться не менее 4 (но обязательно не более 143/34). Если это так, то нужно проверить, не является ли целочисленным решение задачи на G_1. Если оно целое, то является решением задачи, а если нет, то процесс решения необходимо продолжить, разбивая G₁

 

Рисунок 6 - Разбиение множества на части

 

На G₁ точку оптимума можно найти, решив систему уравнений:

х₁ = 1 х₁=1

3х₁ + 8х₂ = 13 х₂=5/4

Х_G1 = (1; 5/4), z_G=13/4

Оценка меньше 4, следовательно, решением задачи является Х^*=Х_G2=(2;0),z^*=4.

3.4 Решение задачи целочисленного линейного программирования методом ветвей и границ с помощью ППП «Система деловых задач»

ЗЦЛП можно решить с помощью пакета прикладных программ “Quantitative Systems for Business” ("Система деловых задач") [3]. Соответствующая программа запускается файлом intlprog.ехе. Она решает как частично, так и полностью целочисленные задачи линейного программирования с числом переменных и ограничений до 20, используя метод ветвей и границ. В том числе решаются и задачи с булевыми переменными (т.е. с переменными, которые могут принимать одно из двух значений - 0 или 1; как, например, в задаче о назначениях [1]). По умолчанию все переменные неотрицательны. Программа позволяет ввести целочисленные границы для переменных, не включая их в общее число ограничений. По умолчанию нижняя граница 0, а верхняя 32000. Если необходимо установить нецелочисленные границы, их вводят, как обычные ограничения.

Если в задаче имеется несколько оптимальных планов, из них находится только один. Информация о наличии множественного решения не выводится.

Режим 2 (ввод новой задачи) включает три этапа. На первом этапе осуществляют ввод информации о размерности задачи, направлении экстремизации и именах переменных (по умолчанию XI, Х2,..., Хn).

На втором этапе необходимо определить, являются ли все переменные целочисленными, являются ли все переменные булевыми, и будут ли вводиться границы для переменных. При ответе «нет» на первый вопрос или «да» на третий, выводится таблица (рисунок 7):

	Введите предел и границы для переменных (По умолчанию значения нижней границы 0 и верхней границы 32000)   № перем. Имя Предел (I/C) Нижняя гр. Верхняя гр. 1 X1 <C> <0 > <0 > 2 X2 <C> <0 > <0 >

 

Рисунок 7 - Определение пределов и границ

Установив I (integer) в столбце «Предел», на переменную накладывают ограничение целочисленности. В противном случае (С, continuous) -переменная может принимать и нецелые значения, т.е. является непрерывной.

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

На третьем этапе вводятся коэффициенты при переменных и знаки в ограничениях.

В меню решений имеется возможность исправить целочисленную погрешность (по умолчанию она 0,001).

Решение задачи методом ветвей и границ не сопровождается графической иллюстрацией (изображением дерева) в программе, но для пояснения алгоритма приведем такую иллюстрацию на рисунок 8.

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

Основное различие заключается в том, что здесь на каждом этапе не выбирается наиболее «перспективное» подмножество. После того, как очередное подмножество разбито на две части, не подсчитывают сразу оценку обеих частей, а вместо этого каждая ветвь дерева последовательно рассматривается до конца. Исходная ОДП разбивается на подмножества по первой нецелочисленной переменной в оптимальном плане нецелочисленной задачи. Затем рассматривают ту вершину, которой соответствует знак , разбивают соответствующее подмножество так же, как и исходную ОДП, снова рассматривают ту вершину, которой соответствует знак , и т.д. до тех пор, пока не будет получен целочисленный план, или задача окажется неразрешимой. Только после этого возвращаются к рассмотрению вершин, которым соответствовал знак .

 

При этом на каждой итерации выводится информация о текущих целочисленных границах (определяющих рассматриваемое подмножество), оптимальном плане нецелочисленной задачи, о том, является ли он целочисленным, о значении целевой функции (ЦФ) на нем и о величинах ZL или ZU. Для задачи на максимум выводится значение нижней границы ZL, а на минимум верхней ZU. До тех пор, пока не найдено какое-нибудь целое решение, ZL =-1*10²⁰, а ZU = 1*10²⁰.

После нахождения целочисленного плана нельзя сразу судить о том, является ли он оптимальным, так как рассматривались не наиболее перспективные вершины. Но можно в уверенностью утверждать, что искомый максимум не меньше (а минимум не больше) значения целевой функции на целочисленном плане. Поэтому значения границ ZL и ZU изменяются (если только ранее не был найден целочисленный план с не меньшим (не большим) значением целевой функции).

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

Поясним это на примере (рис.8):

max 3х₁ + 2х₂

7х₁ + 5х₂ 35

9х₁ + 4х₂ 36

х_1,2 0

х_1,2 Z

На первой итерации найдено нецелочисленное решение Х=(2,353; 3,706). Вся ОДП (множество G) разбивается на два подмножества - G₁ и G₂ следующим образом:

G₁={X G: х₁ 3}

G₂={X G: х₁ 2}.

На второй итерации решают задачу на подмножестве G₁. Полученное решение также нецелочисленно. Далее, вместо того, чтобы рассмотреть подмножество G₂, продолжают рассматривать G₁. В соответствующем плане выбирают первую по счету нецелочисленную компоненту (это х₂) и разбивают G₁ на G₃ и G₄. На третьей итерации рассматривают G₃ - на этом подмножестве допустимых планов нет. Только после этого на четвертой итерации рассматривается вторая ветвь, выходящая из G₁ - подмножество G₄. Далее аналогично.

На пятой итерации на подмножестве G₅ найдено целочисленное решение, которому соответствует значение целевой функции 12. На следующей итерации это значение присваивается величине ZL, которая до этого была равна -1*10²⁰. Соответствующий план запоминается - он может оказаться оптимальным. Но на шестой итерации снова получен целочисленный план, целевая функция на котором равна 13 (больше 12) - ZL снова изменяется, запоминается новый план.

После этого, на седьмой итерации, переходят к рассмотрению подмножества G₂, которое разбивают на G₇ и G₈.

На тринадцатой итерации (подмножество G₁₄) снова найдено целочисленное решение Х=(0; 7), целевая функция на нем равна 14. Снова изменяется ZL и запоминается соответствующий план.

План, найденный на четырнадцатой итерации, также является целочисленным, но его не запоминают, так как 13<14 (ZL=14). План, найденный на пятнадцатой итерации, тоже, к сожалению, не запоминается, так как 14 14, а программа ставит своей целью найти хотя бы одно решение.

Наличие других оптимальных планов здесь игнорируется.

Таким образом, решение Х=(0; 7) получено за 15 итераций.

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

 

 

Рисунок 8 – Метод ветвей и границ («Система деловых задач»)

 

Для задачи с булевыми переменными алгоритм метода ветвей и границ будет тот же, но разбиение проводится по первой по счету переменной, значение которой не равно 0 или 1. На одном подмножестве эта переменная приравнивается 1 (эта ветвь рассматривается вначале), а на другом - нулю.

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

 

 

Рассмотрим решение задачи с булевыми переменными в данной программе на следующем примере:

max 4x₁ + 2x₂ - 5x₃ - 2x₄ + 3x₅

x₁ + x₂ + x₃ + 2x₄ + x₅ 4

7x₁ + 3x₃ - 4x₄ + 3x₅ 8

11x₁ - 6x₂ + 3x₄ - 3x₅ 3

Ход решения (7 итераций) проиллюстрирован рисунком 9

 

 

 

Рисунок 9 – Метод ветвей и границ для задачи с булевыми переменными

 

Возможности корректировки исходных данных в данной программе рекомендуется изучить самостоятельно.