МО_3_ЦП

1. Методы оптимизации Тема «Целочисленное программирование»

Граецкая Оксана Владимировна, к.т.н., доцент
кафедры системного анализа и управления

2. Постановка задачи ЦП

Целочисленное линейное программирование (ЦЛП)
ориентировано
на
решение
задач
линейного
программирования, в которых все или некоторые
переменные должны принимать целочисленные (или
дискретные) значения.
Постановка задачи целочисл. программирования (ЗЦП):
Найти такое решение (план) X=(x1,…,xn), чтобы
(1)
, i=1,…,m (2)
xj ≥ 0
(3)
xj Z
(4)
В общем случае условие целочисленности (4), добавляемое
к обычным задачам линейного программирования,
существенно усложняет ее решение.
2

3. Методы решения ЗЦП

Обычно алгоритмы целочисленного программирования включают три
шага.
Шаг 1. "Ослабление" пространства допустимых решений задачи
целочисленного линейного программирования путем отбрасывания
требования целочисленности для переменных. В результате получается
обычная задача линейного программирования.
Шаг 2. Решение задачи линейного программирования и определение ее
оптимального решения.
Шаг 3. Имея полученное (непрерывное) оптимальное решение,
добавляем специальные ограничения, которые итерационным путем
изменяют пространство допустимых решений задачи линейного
программирования таким образом, чтобы в конечном счете получилось
оптимальное решение, удовлетворяющее требованиям целочисленности.
Разработаны два общих метода генерирования специальных
ограничений, о которых идет речь при реализации шага 3:
1) метод ветвей и границ;
2) методы отсечений (отсекающих плоскостей), наиболее известным из
которых является метод Гомори.
3

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

Идея метода: последовательное разбиение (ветвление)
исходного множества допустимых значений переменных
задачи X на подмножества и вычисление оценок (границ)
значений целевой функции на каждом выделенном
подмножестве. Это позволяет отбрасывать подмножества,
заведомо не содержащие решений задачи.
На нулевом шаге решения задачи (1)-(4) отбрасывается
условие целочисленности (4) и решается задача линейного
программирования (1)-(3).
Если
оказалось целочисленным, т.е.
множеству
целых чисел, то
- решение задачи целочисленного
программирования (1)-(4).
Если множеству целых чисел, то Z*≤ Z( ), так как при
исключении
(4)
область
допустимых
значений
расширяется, то есть можно считать, что
- это
верхняя оценка (граница) значений целевой функции Z.4

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

Пусть найденная в результате решения задачи (1)-(3)
компонента вектора
оказалась нецелочисленной, тогда в
промежутке от [ ] до [ ]+1 не будет лежать целочисленных
решений исходной задачи.
Поэтому допустимое решение целочисленной переменной xr
должно удовлетворять одному из неравенств:
xr ≤ [ ] или xr ≥ [ ]+1
Данные условия 1) и 2) порождают две задачи, т.е. решение
задач (1)-(4) является решением одной из следующих задач:
Задача 1: (1)-(3), xr ≤ [ ]
(5)
Задача 2: (1)-(3), xr ≥ [ ]+1
(6)
Ограничения задач (5) и (6) за счет введения дополнительного
неравенства приводят к разбиению исходного множества X
решения задачи на два пересекающихся
подмножества:
Х
5

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

Если решение одной из задач линейного программирования (5) и (6) является
целочисленным, то оно может рассматриваться в качестве претендента на
решение исходной задачи (1)-(4). При этом выполняется разделение множества
допустимых решений той из задач (5) и (6), которая не имеет целочисленного
решения. Если оптимальное решение (5) и (6) не является целочисленными, то
(1)
(1)
1) для оптимальных решений