Каждая из которых не является допустимой, т.е. попытка найти решение ЗЦЛП путем округления соответствующего решения ЗЛП является несостоятельной.

Пример 5.3:

Существует принципиальная возможность свести решение задачи

(5.1)-(5.4) к нахождению оптимального плана некоторой задачи

Линейного программирования (без условия целочисленности переменных).

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

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

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

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

(5.9)

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

(5.10)

(5.11)

- целые (5.12)

При p = n (p < n) задача (5.9)-(5.12)- называется полностью (частично) целочисленной задачей линейного программирования.

Для решения ЗЦЛП обычно применяются методы типа отсечений, например, метод Гомори и методы типа возврата - метод ветвей и границ.

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

, (5.13)

которые являются функциональными ограничениями.

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

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

нижнюю границу оптимального значения линейной формы задачи (5.9-5.11) и (5.13) - , S = 2, 3,....... На первой итерации в качестве можно взять значение функции в любой целочисленной точке, лежащей внутри области (5.10)- (5.11) и (5.13). Если такую точку указать трудно, то можно положить = - , но это приводит к значительному увеличению числа итераций.

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

- Пусть в результате S итераций метода получили список из N задач: 1, 2,..., Z, …N и имеем .

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

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

- Шаг 3. Если > , то переходим к шагу 4. В противном случае - задачу Z исключаем из списка и, полагая , возвращаемся к шагу 1.

- Шаг 4. Если не все компоненты вектора удовлетворяют условиям целочисленности (5.12), то переходим к шагу 5. В противном случае - задачу Z из списка исключаем, план - запоминаем и, полагая = , возвращаемся к шагу 1. При S = 0 вектор является решением и исходной задачи (5.9)-(2.12) и процесс решения заканчивается.

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

,

………………

……………….

Задача Z+2:

,

………………

………………..

Процесс решения продолжаем до тех пор, пока не будут решены все задачи линейного программирования из списка. Тогда решением задачи (5.9)-(5.12) и (5.13) будет вектор для которого = на последней итерации.

Пример 5.4. Решить ЗЦЛП.

- целые числа (3)

(4)

(5)

Основной список содержит ЗI – (1), (2), (4), (5). Положим =0, т.к. точка (0, 0) – целочисленный план этой задачи.

Итерация 1. Шаг 1.

Решаем задачу (1), (2), (4), (5). Ее решением будет точка = C = (4, 5; 2.5),

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

Шаг 3. Так как , то переходим к шагу 4.

Шаг 4. Так как обе компоненты вектора не целые, то переходим к шагу 5.

Шаг 5. ЗI исключаем из ОС и включаем в него 2 новые задачи ЗII и ЗIII.

Пусть -дробная компонента, ее целая часть [4, 5]=4. Следовательно, ЗII и ЗIII будут иметь вид:

ЗII	ЗIII
(4) (5)	(4) (5)

Далее полагая = , переходим к шагу 1.

Итерация 2.

ОС содержит ЗII и ЗIII, =0.

Шаг1. Выбираем из ОС ЗII и решаем ее. Ее решением будет =К=(4; 8/3)

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

Шаг 3. Т.к. > , то переходим к шагу 4.

Шаг 4. Т.к. -дробная, то переходим к шагу 5.

Шаг 5. ЗII выбрасываем из ОС и включаем в него 2 новые задачи ЗIV и ЗV.

Т.к. [8/3]=2, то. Следовательно, ЗIV и ЗV будут иметь вид:

ЗIV	ЗV
(4) (5)	(4) (5)

Далее полагая = , переходим к шагу 1

Итерация 3.

ОС содержит ЗIII, ЗIV и ЗV, =0.

Шаг 1. Выбираем из ОС ЗIII и решаем ее. Ее решением будет =L=(5; 20/9)

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

Шаг 3. Т.к. > , то переходим к шагу 4.

Шаг 4. Т.к. -дробная, то переходим к шагу 5.

Шаг 5. ЗIII исключаем из ОС и включаем в него 2 новые задачи ЗVI и ЗVII.

Т.к. [20/9]=2, то, следовательно, ЗVI и ЗVII будут иметь вид:

ЗVI	ЗVII
(4) (5)	(4) (5)

Далее полагая = , переходим к шагу 1.

Итерация 4.

ОС содержит ЗIV и ЗV, ЗVI и ЗVII =0.

Шаг 1. Выбираем из ОС ЗIV и решаем ее. Ее решением будет =M=(4; 2)

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

Шаг 3. Т.к. > , то переходим к шагу 4.

Шаг 4. Т.к. обе компоненты целочисленные, то задачу ЗIV из ОС исключаем, план запоминаем и, полагая =8= , переходим

к шагу 1.

Итерация 5.

ОС содержит ЗV, ЗVI и ЗVII =8.

Шаг 1. Решаем ЗV. Ее решением будет =D=(3; 3).

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

Шаг 3. Т.к. > , то переходим к шагу 4.

Шаг 4. Т.к. обе компоненты целочисленные, то задачу ЗV из ОС исключаем, план запоминаем и, полагая =9= , переходим к шагу 1.

Итерация 6.

ОС содержит ЗVI и ЗVII =9.

Шаг 1. Выбираем из ОС ЗVI и решаем ее. Ее решением будет =N=(27/5; 2)

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

Шаг 3. Т.к. > , то переходим к шагу 4.

Шаг 4. Т.к. -дробная, то переходим к шагу 5.

Шаг 5. ЗVI выбрасываем из ОС и включаем в него 2 новые задачи ЗVIII и ЗIX.

Т.к. [27/5]=5, то. Следовательно, ЗVIII и ЗIX будут иметь вид:

ЗVIII	ЗIX
(4) (5)	(4) (5)

Далее полагая = , переходим к шагу 1.

Итерация 7.

ОС содержит ЗVII, ЗVIII и ЗIX =9.

Шаг 1. Выбираем из ОС ЗVII и решаем ее. Она не имеет решения, т.к. множество ее планов пусто.

Шаг 2. Т.к. ЗVII не имеет решения, то исключаем её из ОС и переходим к шагу 1, полагая что = .

Итерация 8.

ОС содержит, ЗVIII и ЗIX =9.

Шаг1. Выбираем из ОС ЗVIII и решаем ее. Ее решением будет =О=(5; 2),

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

Шаг 3. Т.к. = , то переходим к шагу 4.

Шаг 4. Т.к. обе компоненты целочисленные, то ЗVIII из ОС исключаем, план запоминаем и, полагая =9= , переходим к шагу 1.

Итерация 9.

ОС содержит ЗIX =9.

Шаг 1. Выбираем из ОС ЗIX и решаем ее. Ее решением будет =P=(6; 15/9)

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

Шаг 3. Т.к. > , то переходим к шагу 4.

Шаг 4. Т.к. -дробная, то переходим к шагу 5.

Шаг 5. ЗIX исключаем из ОС и включаем в него 2 новые задачи ЗX и ЗXI.

Т.к. [15/9]=1, то. Следовательно, ЗX и ЗXI будут иметь вид:

ЗX	ЗXI
(4) (5)	(4) (5)

Далее полагая = , переходим к шагу 1.

Итерация 10.

ОС содержит ЗX и ЗXI =9.

Шаг 1. Выбираем из ОС ЗX и решаем ее. Ее решением будет =Q=(36/5; 1)

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

Шаг 3. Т.к. > , то переходим к шагу 4.

Шаг 4. Т.к. -дробная, то переходим к шагу 5.

Шаг 5. ЗX исключаем из ОС и включаем в него 2 новые задачи ЗXII и ЗXIII.

Т.к. [36/5]=7, то. Следовательно, ЗXII и ЗXIII будут иметь вид:

ЗXII	ЗXIII
(4) (5)	(4) (5)

Далее полагая = , переходим к шагу 1.

Итерация 11.

ОС содержит ЗXI, ЗXII и ЗXIII = 9.

Шаг1. Выбираем из ОС ЗXI и решаем ее. Она не имеет решения, т.к. множество ее планов пусто.

Шаг 2. Т.к. ЗXI не имеет решения, то исключаем её из ОС и переходим к шагу 1, полагая что = .

Итерация 12.

ОС содержит ЗXII и ЗXIII =9.

Шаг 1. Выбираем из ОС ЗXII и решаем ее. Ее решением будет = R (7; 1)

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

Шаг 3. Т.к. = , то переходим к шагу 4.

Шаг 4. Т.к. обе компоненты целочисленные, то задачу ЗXII из ОС исключаем, план запоминаем и, полагая =9= переходим к шагу 1.

Итерация 13.

ОС содержит ЗXIII =9.

Шаг 1.Выбираем из ОС ЗXIII и решаем ее. Ее решением будет = T = (8; 5/9)

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

Шаг 3. Т.к. > , то переходим к шагу 4.

Шаг 4. Т.к. -дробная, то переходим к шагу 5.

Шаг 5. ЗXIII исключаем из ОС и включаем в него 2 новые задачи ЗXIV и ЗXV.

Т.к. [5/9]=0, следовательно, ЗXIV и ЗXV будут иметь вид:

ЗXIV	ЗXV
(4) (5)	(4) (5)

Далее полагая = , переходим к шагу 1.

Итерация 14.

ОС содержит ЗXIV и ЗXV =9.

Шаг 1. Выбираем из ОС ЗXIV и решаем ее. Ее решением будет = Z =(9; 0)

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

Шаг 3. Т.к. = , то переходим к шагу 4.

Шаг 4. Т.к. обе компоненты целочисленные, то задачу ЗXIV из ОС исключаем, план запоминаем и, полагая =9, переходим к шагу 1.

Итерация 15.

ОС содержит ЗXV =9.

Шаг1. Выбираем из ОС ЗXV и решаем ее. Она не имеет решения, т.к. множество ее планов пусто.

Шаг 2. Т.к. ЗXV не имеет решения, то переходим к шагу 1, полагая что = .

Итерация 16.

Шаг1. Т.к. ОС пуст, то задача решена.

Задача (1)-(5) имеет 4 оптимальных плана: