Целочисленного линейного программирования

 

Цель работы

 

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

 

Метод ветвей и границ решения задач

целочисленного линейного программирования

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

 

Задача линейного программирования, переменные которой могут принимать только целые значения, является задачей целочисленного линейного программирования:

где ; x_j - переменные, a_ij, b_i, c_j - константы.

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

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

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

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

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

2. Методы отсечения.

3. Методы динамического программирования.

Здесь будет рассмотрен метод из первой группы.

 

2.2. Метод ветвей и границ. Общая схема

 

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

Пусть существует некоторая функция f(X), экстремум которой (например, максимум) необходимо найти при некоторой системе ограничений.

Этой системой определяется ОДП задачи - обозначим ее G. Пусть некоторым способом мы можем определить верхнюю границу функции на этой области ₀, т.е. ₀ f(X), X G.

Затем проверяют, не существует ли какой-нибудь очевидный способ нахождения точки X⁰, для которой f(X⁰)= ₀. Если он есть, то искомый максимум найден.

Если такого способа нет, то множество G разбивают на подмножества G₁ и G₂ и для каждого из них находят верхнюю границу ₁ и ₂ (при этом _{0 1} и _{0 2}). Далее оптимальный план ищут в наиболее перспективном множестве, т.е. в том, которому соответствует наибольшая оценка.

 

 

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

Если попытка найти Х: f(X) = _k удалась, то это будет оптимальный план для всего исходного множества G (поскольку для остальных подмножеств верхние границы заведомо меньше).

При решении задачи на минимум схема та же, но рассматриваются вершины с наименьшей оценкой.

Этот метод всегда сходится, если мы имеем дело с ограниченной дискретной областью.

Чтобы конкретизировать метод ветвей и границ, необходимо установить:

1) алгоритм поиска границ ;

2) алгоритм разбиения множества на части;

3) алгоритм поиска Х, реализующего границу ;

4) установить сходимость.

 

2.3. Применение метода ветвей и границ

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

 

Рассмотрим задачу ЦЛП в матричной форме записи. Обозначим ОДП этой задачи D, а ОДП ЗЛП без ограничений целочисленности - G. Точно так же обозначим соответствующие системы ограничений, а сами задачи будем называть D-задача и G-задача.

max CX

D представляет собой часть G. G будем рассматривать в качестве исходного множества (рис.2).

 

Решим вначале G-задачу. Пусть при решении этой задачи получен оптимальный план Х_G. Значение целевой функции на нем z_G - оптимум G-задачи - будем использовать в качестве границы . В самом деле,

z_G СХ Х G

z_G СХ Х D

Если план Х_G целочисленный, то решение задачи окончено. Таким образом, мы ответили на первый и третий вопросы, конкретизирующие метод ветвей и границ.

Предположим, что хотя бы одна компонента Х_G нецелочисленна: х_Gi Z.

Целой частью числа называют наибольшее целое число, меньшее или равное данному.

Обозначим целую часть числа х_Gi [х_Gi].

Конкретизируем второй вопрос.

Разобьем D на D₁ и D₂ следующим образом:

D₁={X D: х_i [х_Gi]}

D₂={X D: х_i [х_Gi] + 1}

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

Разбивая D, мы одновременно разбиваем и G (рис.3).

Это разбиение обладает следующими свойствами:

G₁ G₂ G (объединение этих множеств содержится в G, но не равно ему)

D₁ D₂ = D (в устраненном «коридоре» нет ни одной точки с целочисленными координатами)

 

 

 

 

При этом устраняется и план Х_G.

Далее решение задачи продолжается для каждого из подмножеств G₁ и G₂.

Сходимость алгоритма основана на том, что в ограниченной ОДП множество дискретных точек конечно.

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

 

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

 

Например,

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

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

 

 

 

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

G₁={X G: х₁ 1}

G₂={X G: х₁ 2}

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

 

 

 

 

 

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

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

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

х₁ = 1 х₁=1

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

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

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

 

2.5. Решение задачи целочисленного линейного программирования методом ветвей и границ с помощью пакета QSB

 

Соответствующая программа запускается файлом intlprog.exe. Она решает как частично, так и полностью целочисленные задачи линейного программирования с числом переменных и ограничений до 20, используя метод ветвей и границ. В том числе решаются и задачи с булевыми переменными. По умолчанию все переменные неотрицательны. Программа позволяет ввести целочисленные границы для переменных, не включая их в общее число ограничений. По умолчанию нижняя граница 0, а верхняя 32000. Если необходимо установить нецелочисленные границы, их вводят, как обычные ограничения.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

 

 

Для задачи с булевыми переменными алгоритм метода ветвей и границ будет тот же, но разбиение проводится по первой по счету переменной, значение которой не равно 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 итераций) проиллюстрирован рисунком 8.

		Рис.8

 

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

 

Содержание работы

 

1. Изучение основных понятий целочисленного линейного программирования и экономической интерпретации задачи.

2. Изучение основ метода ветвей и границ.

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

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