3.1. метод ветвей и границ решения целочисленных задач линейного программирования (цзлп)

3.1. метод ветвей и границ решения целочисленных задач линейного программирования (цзлп)

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

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

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

Согласно общей идее метода, сначала решается задача с ослабленными ограничениями (задача линейного программирования). Пусть хг — целочисленная переменная, значение x* которой в оптимальном решении ослабленной задачи является дробным. Интервал

[x*] < xr < [x*] + і

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

xr > [ x*] или хг < [ x*] + і

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

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

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

Рассмотрим задачу целочисленного линейного программирования (ЗЦЛП ) :

Найти вектор x є En, максимизирующий линейную форму

f(x) = ±сЛ (3.1)

и удовлетворяющий условиям:

n

J a,jXj = bt, і = 1, m (3.2)

j=1

xj >0 j = 1,n (3.3)

X1,X2,...,xp целые (p<n) (3.4)

Пусть, для каждой целочисленной переменной можно указать

верхнюю и нижнюю границы, в пределах которых безусловно

содержатся ее оптимальные значения, то есть

V<x-;xv ; J=Lp (3.5)

При этом в систему функциональных ограничений необходимо

включить р неравенств (3.5).

В начале любой S-й итерации метода ветвей и границ необходимо иметь:

Основной список задач линейного программирования, каждая из которых должна быть решена в последующих итерациях ( на первой итерации список содержит одну ЗЛП задачу 1 (3.13.3) и (3.5).

Нижнюю границу оптимального значения линейной формы задачи (3.1) (3.3), (3.5) Z0(s). На первой итерации в качестве Z0(1) можно взять значение функции f (x) в любой целочисленной точке x, лежащей внутри области (3.2) (3.5). Если такую точку указать трудно, то можно положить Z0(1) = -со, но это приводит к значительному увеличению числа итераций.

Алгоритм S-й итерации метода ветвей и границ.

Пусть в результате S итераций метода получили список из Z задач: 1,2,...,Z и имеем Z0(s).

Шаг 1. Выбираем из списка ЗЛП одну задачу для решения, задачу R (1 < R < Z) и решаем ее.

Шаг 2. Если задача R имеет решение xr s), то переходим к шагу 3. В противном случае исключаем задачу R из списка и, полагая Z0(s+1)=Z0(s), возвращаемся к шагу 1. При S = 0, то есть на первой итерации, делаем вывод, что исходная задача (3.1)-(3.4) не имеет решения и процесс решения заканчивается.

Шаг 3. Если f(xr())> Z0(s), то переходим к шагу 4. В противном случае задачу R исключаем из списка и, полагая Z0(s+1)=Z0(s), возвращаемся к шагу 1.

Шаг 4. Если не все компоненты вектора xr(s) удовлетворяют условиям целочисленности (3.4), то переходим к шагу 5. В противном случае задачу R из списка исключаем, план xr(s) запоминаем и, полагая

Z0(s+1)= f (xr(возвращаемся к шагу 1. При S = 0 вектор х °является решением и исходной задачи и процесс решения заканчивается.

Шаг 5. Задачу R выбрасываем из списка, включая в него две новые задачи линейного программирования задачу (Z+1) и задачу (Z+2). Далее, полагая Z0(s+1)=Z0(s), возвращаемся к шагу 1. Процесс разбиения задачи R на две новые ЗЛП осуществляется следующим образом: Пусть Xj(s) дробная компонента в полученном оптимальном плане xr(s) и [ Xj(s)] ее целая часть. Тогда задача Z+1 имеет вид:

n

f (х) = Yj CjXj max

j=1

при условиях

n

Yavxj = b , i = 1-m

j=1

X1, X2,...., Xn > 0

Задача Z+2:

n

f (x) = J c jxj — max

/=1

при условиях

-і

j=1

V1 < x1 < W1

J ajxj = b , i = 1-.m

V < x < W

p p T p

x1, x2,...., xn > 0

Процесс решения продолжаем до тех пор, пока не будут решены все задачи линейного программирования из списка. Тогда решением задачи (3.1)-(3.5) будет Z0(s) на последней итерации. Пример. Решить ЗЦЛП

f ( x) = 2x1 +x2 — max (3.6) 7x1 + 3x2 < 21

x1 + x2 < 5 (3.7) x1,2 целые (3.8)

0<x1<3 (3.9) 0<x2<5 (3.10)

В качестве Z0(1) возьмем f (x) в точке x =(0,0), то есть Z0(1)=0. Итерация 1. Имеем:

1) В списке задач линейного программирования одна задача задача 1 (3.6)-(3.7),(3.9),(3(1.)10).

2) Нижняя граница Z0(1)=0.

Шаг 1. Выбираем задачу 1, решаем ее, получим оптимальный план x(1)=(1,5 ; 3,5), f (x(1)) = 6,5.

Шаг 2. Так как задача 1 имеет конечное решение, то переходим к шагу 3.

Шаг 3. Так как f (x()) = 6,5 > Z0(1), то переходим к шагу 4.

Шаг 4. Не все компоненты вектора x() удовлетворяют условию целочисленности, поэтому переходим к шагу 5.

Шаг 5. Задачу 1 из списка выбрасываем, включая в него две новые задачи задачу 2 и задачу 3. Разбиение задачи 1 производим по переменной х1:

задача 2

f (x) = (2x1 + x2) — max

x1 + x2 < 5 0 < x1 < і 0 < x2 < 5

задача 3

f(x)

(2 x1 + x2) — max 7x1 + 3x2 < 2і x1 + x2 < 5

2 < x1 < 3

0 < x2 < 5

Полагаем Z0(2) = = 0, возвращаемся к шагу і. Итерация 2. і) Список ЗЛП включает 2, 3.

2) Z0(2) = 0.

Шаг і. Выбираем из списка одну задачу задачу 2. Решаем ее,

~ —(2) —(2)

оптимальный план x = (і,4), f (x ) = 6.

Шаг 2. Задача 2 имеет конечное решение, переходим к шагу 3.

Шаг 3. Сравниваем f (x(2)) > Z0(2) = 0, следовательно, переходим к шагу 4.

Шаг 4. Все компоненты вектора x удовлетворяют условию целочисленности, поэтому задачу 2 из списка исключаем, план

x

(2)

запоминаем и, полагая

Z0(3) = f (x(2)) = 6, возвращаемся к шагу і.

Итерация 3.

Шаг і. Выбираем из списка ЗЛП задачу 3, решаем ее, получим

~ —(3)

оптимальный план x = (2, 7/ 3).

Шаг 2. Задача 3 имеет конечное решение, следовательно, переходим к шагу 3.

Шаг 3. Сравниваем f (x(3)) и Z0(3), так как f (x (3))= 6і> Z0(3) = 6, то

переходим к шагу 4.

Шаг 4. Компоненты вектора x не удовлетворяют условию целочисленности, следовательно, задачу 3 из списка выбрасываем и переходим к шагу 5.

Шаг 5. Вместо задачи 3 включаем в список две задачи 4 и 5.

Разбиение задачи 3 производим по переменной х2: задача 4

f (х) = (2 х1 + х2) — max 7х1 + 3х2 < 21 х1 + х2 < 5 2 < х1 < 3 0 < х2 < 2

задача 5

f (х) = (2 х1 + х2) — max 7х1 + 3х2 < 21 х1 + х2 < 5

< х1 < 3

< х2 < 5

Полагая Z0(4) = Z0(3) = 6, возвращаемся к шагу 1.

Итерация 4. Выбираем из списка ЗЛП задачу 5. Она не имеет решения, следовательно, выбрасываем ее из списка. Полагая Z0(5) = Z0(4) , возвращаемся к шагу 1.

Итерация 5. Имеем: 1) Список ЗЛП задача 5. 2) Z.(5) = Z0(4) = 6.

Шаг 1. Выбираем задачу 4. Решая ее , получаем оптимальный план

X(5) = (15/7, 2).

Шаг 2. Задача 4 имеет конечное решение х(5) = (15/7, 2) и f (х(5)) = 6-7,

переходим к шагу 3.

Шаг 3. Так как f (х(5)) > Z0(6) = 6, то переходим к шагу 4.

Шаг 4. Компоненты плана х() не целочисленные, следовательно, задачу 4 из списка выбрасываем и, полагая Z0(5) = Z0(6), переходим к шагу

5.

Шаг 5. Задачу 4 выбрасываем из списка, а вместо нее включаем в него две новые ЗЛП, производя разбиение задачи 4 по переменной х1: задача 6

f (х) = (2 х1 + х2) — max 7х1 + 3х2 < 21 х1 + х2 < 5 3 < х1 < 3; х1 = 3 0 < х2 < 2

задача 7

f (x) = (2 x1 + x2) — max 7x1 + 3x2 < 2і x1 + x2 < 5 2 < x1 < 2; x1 = 2 0 < x2 < 2

Полагая Z0(6) = Z0(5), возвращаемся к шагу і.

Итерация 6. Имеем і) Список ЗЛП включает задачи 6 и 7. 2) Z0(6) = 6.

Шаг і. Выбираем из списка задачу 6 и решая ее, находим оптимальный план x6) = (2, 2). Так как компоненты плана

x6) целочисленные и f (x(б)) = 6=Z0(6), то задачу 6 из списка выбрасываем,

-(6)

а план x запоминаем.

Полагая Z0(7) = Z0(6) = 6 возвращаемся к шагу і.

Итерация 7. Имеем: і) Список ЗЛП одна задача 7.

2) Z0(7) = 6.

Шаг і. Решаем задачу 7 и получаем оптимальный план x = (3, 0).

Шаг 2. Компоненты плана x целочисленные и значение функции f (x()) = Z0(7) = 6. Задачу 7 из списка выбрасываем, план x() запоминаем.

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

—(2) —(6) —(7) —(2) —(6) —(7)

плана x , x , x , причем f(x ) = f(x ) = f(x ) = 6. Решением исходной задачи является f (x ) = 6; x ={(3,0); (2,2); (і,4)}.

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

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

у.е., при этом оно может купить оборудование двух видов. Комплект оборудования 1 вида стоит 1000 у.е., а II вида—3000 у.е. Приобретение одного комплекта оборудования 1 вида позволяет увеличить выпуск продукции в смену на 2 ед., а одного комплекта оборудования II вида — на 3 ед. Зная, что для установки одного комплекта оборудования 1 вида

2 2

требуется 2 м площади, а оборудования II вида — 1м площади, определить такой набор дополнительного оборудования, который дает возможность максимально увеличить выпуск продукции.

Решение. Составим математическую модель задачи. Предположим, что предприятие приобретет х1 комплектов оборудования 1 вида и х2 комплектов оборудования II вида. Тогда переменные х1 и х2 должны удовлетворять следующим неравенствам:

|2х1 + x2 < 19/3, ( )

[x, + 3x2 < 10. (.)

Если предприятие приобретет указанное количество оборудования, то общее увеличение выпуска продукции составит

F= 2х, +3х2.

(3.12)

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

хЬх2 > 0

х1,х2—целые.

(3.13)

(3.14)

Таким образом, задача (3.11)-(3.14) представляет собой задачу

ЦЛП.

Домашнее задание 3.1.

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

1. max(3x1 + 3x2)

4x1 + 5x2 < 20 x1 + 6x2 < 12 0 < x1 < 5 0 < x2 < 4

2. max(3x1 + 2 x2)

3x1 + 7x2 < 21 x1 + x2 < 4 0 < x1 < 4 0 < x2 < 3

3. max( x1 + 3x2)

3x1 + 4x2 < 12 3x1 + 2x2 < 6 0 < x1 < 4 0 < x2 < 2

4. max(4x1 + x2)

2x1 3x2 < 6 4 x1 + 9 x2 < 18 0 < x1 < 2 0 < x2 < 3

5. max(3x1 + x2)

4x1 + 3x2 < 18 x1 + 2 x2 < 6 0 < x1 < 5 0 < x2 < 3

6. max( x1 + 2 x2)

x1 + x2 < 5 3x1 + 8x2 < 24 0 < x1 < 5 0 < x2 < 3

7. max(2 x1 + x2)

5x1 + 2x2 < 30 3x1 + 8x2 < 48 0 < x1 < 6 0 < x2 < 6

8. max(3x1 2x2)

2x1 + 3x2 < 6

0 < x1 < 3 0 < x2 < 3

9. max(3x1 + 2 x2)

2 x1 + x2 > 6 4 x1 + 3x2 > 6

< x1 < 3

< x2< 2

10. max(x1 + 2x2)

5x1 + 9 x2 < 45 x1 + 3x2 < 12 0 < x1 < 9 0 < x2 < 4