Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
/ Методичка по методам оптимизации.doc
Скачиваний:
64
Добавлен:
02.05.2014
Размер:
1.18 Mб
Скачать

Задача целочисленного линейного программирования. Метод ветвей и границ.

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

Найти вектор x=(x1...,xn), что минимизирует целевую функцию

L(x)= c1x1 + ... + cnxn (13.1)

и удовлетворяет систему ограничений

a11x1 + . . . + a1n xn R1 a10

. . . . . . . . . . . . . . . . . . . . . . . (13.2)

am1x1 + . . . + amnxn Rm am0

xj0, j=1...,n (13.3)

xj — цели, j=1...,n. (13.4)

где символ Ri (i=1...,m) заменяет один из знаков: , =, .

Считается также, что многогранное множество, которое определяется соотношениями (13.2)(13.3), ограниченная, а коэффициенты cjцелевой функции (13.1) — целые числа.

Дальше приводится алгоритм метода Ленд-Дойг, который представляет собой реализацию метода ветвей и границ для сформулированной выше задачи.

Изложение метода Ленд-Дойга.

Решается вспомогательная ЗЛП (13.1)(13.3), которая получена из исходной ЦЗЛП (13.1)(13.4) отбрасыванием условия целочисленности переменных (13.4) (ветка 0;1). Если ее решение x(0;1) — целочисленный, то он же является и решением исходной ЦЗЛП. Иначе величина (0;1)=L(x(0;1)) дает нижнюю оценку (границу) целевой функции ЦЗЛП на множестве D(0;1)=D, что определяется соотношениями (13.2) (13.3).

Пусть некоторая координата xj(0;1) (j=1...,n) решения x(0;1) не является целочисленной. В этом случае осуществляется разветвление множества D(0;1) на два подмножества D(1;1) и D(1;2) добавлениемк ограничениям, которые задают D(0;1), ограниченийxj[xj(0;1)] но xj[xj(0;1)]+1 соответственно, где [z] — целая часть числа z. Дальше Решаются новые вспомогательные ЗЛП с ограничениями, которые определяются подмножествами D(1;1) и D(1;2), находятся границе (1;1) но (1;2) и т.д.

Для последующего разветвления выбирается перспективное множество D(k;r) с наименьшей границею (k;r). Процесс продолжается до тех пор, пока не будет получено решение, которое удовлетворяет условие целочисленности и для которого выполняется признак оптимума (см. п. 4 алгоритма). В результате ограниченности допустимого множества ЗЛП (конечности допустимого множества ЦЗЛП) метод Ленд-Дойга конечный.

Алгоритм метода Ленд-Дойга.

1. Определяются множества D(k;r) условиями (13.2), (13.3) и дополнительными ограничениями, которые возникают в процессе разветвления (см. пункт 5). На 0-м шаге возлагаемD(0;1)=D, гдеD задаетсяусловиями (13.2) (13.3).

2. Решаются вспомогательные ЗЛП на множествах D(k;r). Пусть x(k;r) — оптимальные решения указанных ЗЛП.

3. Вычисляются границы на множествах D(k;r) за формулой (k;r)= ]L(x(k;r))[, где ]z[ — наименьшее целое число, не меньше z.

4. Если существуют k, l такие, что x(k;l) — целочисленное решение и для всех веток r на k-у шаге выполняются соотношения

L(x(k;l))= (k;l)  (k;r)

то x* = x(k;l) — оптимальное решение ЦЗЛП.

5. Разветвление осуществляется по нецелочисленной компоненте xj(k;r) (с минимальным j) решения x(k;r), что отвечаетперспективной ветке k;r (если такихветок несколько, то выбирается ветка с минимальным r), добавлениемк D(k;r) одного из подмножеств xj[xj(k;r)] или xj[xj(k;r)]+1.

Программное обеспечение.

Обучающий модуль, с помощью которого задача целочисленного линейного программирования. Решается в диалоге с пользователем за выбранным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПОМО.

Задание.

Решить методом ветвей и границ задачи целочисленного линейного программирования, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1№9), а также следующие задачи (без использования программного обеспечения).

Во всех задачах выполняются условия: xj0, xj — целое, j=1,2.

1)

x1 + x2  max

2)

2 x1 x2  min

3)

6 x1 + 4 x2  min

2 x1 + 11 x238

6 x1 + 4 x224

2 x1 + x23

x1 + x27

x1 x23

x1 2 x22

4 x1 5 x25;

x1 + 3 x23;

3x1 + 2x21;

4)

x1 + x2  min

5)

5 x1 + 7 x2  min

6)

2 x1 x2  max

x1 x2 1

10 x1 + x2 16

2 x1 + x28

2 x1 + 2 x2 2

3 x1 3 x2 12

x1 + 3 x26

4 x1 + 2 x2 1;

6 x1 2 x2 17

3 x1 + x23;

7)

x1 + 4 x2  min

8)

5 x1 7 x2  max

9)

x1 + 2 x2 min

x1 3 x21

2 x1 + x23

2 x1 + 2 x25

8 x1 x26

20 x1 x215

x1 3 x21

3 x1 11 x27;

x1 x22;

x1 x22.

Ответы:

1) x* = (3; 2) или x* = (2; 3), L(x*)= 5.

2) x* = (3; 1), L(x*)= 7.

3) x* = (1; 1), L(x*)= 10.

4) x* = (1; 0), L(x*)= 1.

5) x* = (4; 0), L(x*)=20.

6) x* = (3; 1), L(x*)= 5.

7) x* = (1; 1), L(x*)= 5.

8) x* = (1; 3), L(x*)= 26.

9) x* = (4; 2), L(x*)= 8.

Соседние файлы в предмете Методы оптимизации