Целочисленное программирование

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

Формулировка задачи целочисленного программирования: найти наибольшее значение функции

Целочисленное программирование - student2.ru

при ограничениях:

Целочисленное программирование - student2.ru ,

Целочисленное программирование - student2.ru , хj - целые, Целочисленное программирование - student2.ru .

Если k=n, то задача полностью целочисленная.

Если k не равно n, то задача является частично целочисленной.

Методы решения задач линейного программирования не гарантируют целочисленности решения.

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

Метод Гомори

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

Дополнительное ограничение отсекает часть области, содержащую нецелочисленное оптимальное решение.

Вновь полученную задачу решают методом линейного программирования. Процесс построения сечений и решения задачи повторяется до получения целочисленного оптимального решения. Общий систематический способ построения сечений разработал Гомори в 1958 г.

Алгоритм метода Гомори

Пусть дана полностью целочисленная задача линейного программирования: найти максимальное значение функции

Целочисленное программирование - student2.ru

при ограничениях:

Целочисленное программирование - student2.ru ,

Целочисленное программирование - student2.ru , хj - целые, Целочисленное программирование - student2.ru .

1) Отбросив условие целочисленности, решаем исходную задачу симплексным методом. Если получится целочисленное оптимальное решение, то задача решена. Если в оптимальном решении не все переменные целочисленны, то строим сечения.

2) Пусть в оптимальном решении переменная xt - дробное число, т.е. xt=ft. Рассмотрим уравнение, в котором xt - базисная переменная.

Целочисленное программирование - student2.ru , (1)

где J - множество индексов свободных переменных.

Разобьем все коэффициенты и свободный член (1) на два слагаемых: целую и дробную часть. Целой частью числа а называется наибольшее целое число, не превышающее а. Дробной частью числа а называется разность между числом а и его целой частью. Целую часть числа обозначим [а], а дробную часть – {а}, т.е. а = [а]+{а}. Тогда уравнение (1) примет вид

Целочисленное программирование - student2.ru , (2)

или

Целочисленное программирование - student2.ru .

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

Неравенство

Целочисленное программирование - student2.ru (3)

является сечением Гомори.

Покажем, что любое целочисленное решение задачи удовлетворяет этому неравенству, а нецелочисленное решение ему не удовлетворяет. Пусть Целочисленное программирование - student2.ru - целочисленное решение, и предположим, что оно не удовлетворяет неравенству (3), т.е.

Целочисленное программирование - student2.ru , или Целочисленное программирование - student2.ru

по условию lj > 0, Целочисленное программирование - student2.ru , отсюда Целочисленное программирование - student2.ru , кроме того, Целочисленное программирование - student2.ru . Получим

Целочисленное программирование - student2.ru , или Целочисленное программирование - student2.ru , т.е. является дробным числом.

Подставив Целочисленное программирование - student2.ru в уравнение (2), получим

Целочисленное программирование - student2.ru .

Правая часть уравнения - дробное число, а левая часть - целое число. Получили противоречие. Следовательно, любое целочисленное решение задачи удовлетворяет неравенству (3).

Покажем, что нецелочисленное оптимальное решение не удовлетворяет неравенству (3).

Пусть Целочисленное программирование - student2.ru - нецелочисленное оптимальное решение задачи. Подставим его в неравенство (3):

Целочисленное программирование - student2.ru , но Целочисленное программирование - student2.ru

Следовательно, Целочисленное программирование - student2.ru не удовлетворяет неравенству (3).

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

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

Пример. Найти наибольшее значение функции

Целочисленное программирование - student2.ru

при ограничениях:

Целочисленное программирование - student2.ru

х1 > 0, х2 > 0, х1, х2 - целые.

Решим задачу симплексным методом без учета целочисленности, для этого приведем ее к каноническому виду

Целочисленное программирование - student2.ru

хj > 0, Целочисленное программирование - student2.ru .

№ п/п сj Б.п.  
x1 x2 x3 x4 bi
x4 x5 2 -1 -1
Dj Целочисленное программирование - student2.ru -2 -2
x1 x4 -1/2 3/2 1/2 1/2 7/2 13/2
Dj Целочисленное программирование - student2.ru -3
x1 x2 2/3 1/3 1/3 2/3 17/3 13/3
Dj Целочисленное программирование - student2.ru

Целочисленное программирование - student2.ru max L = 20.

Решение нецелочисленное, поэтому строим сечение Гомори. Возьмем первое уравнение из последней симплексной таблицы, так как у х1 наибольшая дробная часть Целочисленное программирование - student2.ru .

Целочисленное программирование - student2.ru .

Сечение примет вид Целочисленное программирование - student2.ru или

Целочисленное программирование - student2.ru , где х5>0.

Присоединив это дополнительное ограничение к ограничениям последней симплексной таблицы, получим новую задачу:

Целочисленное программирование - student2.ru

Целочисленное программирование - student2.ru

Решим эту задачу симплексным методом.

№ п/п сj Б.п.  
x1 x2 x3 x4 х5 bi
х1 x2 2/3 1/3 2/3 1/3 2/3 1/3 -1 17/3 13/3 2/3
x1 x2 х3 1/2 1/2 1/2 -3/2
Dj Целочисленное программирование - student2.ru

Целочисленное программирование - student2.ru max L = 18.

Это решение целочисленное, значит исходная задача решена.

max L = 18, Целочисленное программирование - student2.ru .

Дадим геометрическую иллюстрацию метода Гомори. Областью допустимых решений является четырехугольник ОАВС. Оптимальное решение задачи совпадает с точкой Целочисленное программирование - student2.ru .

Построили сечение х1 < 5, оно отсекает нецелочисленное оптимальное решение. Получили область допустимых решений ОАDЕС. Оптимально решение второй задачи будет в точке D (5, 4). Решение получилось целочисленным, следовательно, исходная задача решена.

Целочисленное программирование - student2.ru

Наши рекомендации