1 Цель работы

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

2 Приборы и материалы

Для выполнения лабораторной работы необходим персональный компьютер. Программное обеспечение экономических расчетов – ППП “Quantitative Systems for Business”, также можно использовать средства электронной таблицы Мicrosoft Ехсеl.

3 Описание работы

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

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

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

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

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

Если такого способа нет, то множество О разбивают на подмножества О] и О₂ и для каждого из них находят верхнюю границу (X ] и ОС₂ (при этом а₀>а, и а₀>а₂). Далее оптимальный план ищут в наиболее перспективном множестве, т.е. в том, которому соответствует наибольшая оценка.

Рисунок 1 - Общая схема метода ветвей и границ

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

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

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

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

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

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

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

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

г) сходимость метода.

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

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

max CX

(2)

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

Рисунок 2 – ОДП ЗЛП без ограничений целочисленности

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

z_G СХХG

z_G СХХD

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

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

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

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

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

Конкретизируем ответ на вопрос (в).

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

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

D₂={XD: х_i[х_Gi] + 1} (3)

Это означает, что к одному множеству отнесли все допустимые планы, у которых i-я координата не больше целой части х_Gi, а к другому - у которых не меньше следующего целого числа. Разбивая D, мы одновременно разбиваем и G по аналогичным формулам (рисунок 3). Из рассмотрения исключаются все планы, в которых Gi-я координата принимает дробные значения на открытом промежутке ][ х_Gi];[ х_Gi] + 1[.

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

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

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

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

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

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

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

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