Решение задачи целочисленного линейного программирования

Методом «ветвей и границ».

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

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

Для преобразованного многоугольника решений построим новую систему ограничений.

Запишем систему ограничений в виде равенств, для решения алгебраическим методом.

В результате решения найден оптимальный план задачи: х₁ =9/4, х₂ = 5/2, F =-41/4. Это решения не отвечает условию целочисленности, поставленному в задаче. Разобьем исходный многоугольник решений на две области, исключив из него область 3<x₁<4. Новый многоугольник решений представлен на рисунке ниже.

Измененный многоугольник решений задачи

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

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

Правая область представляет собой точку С.

Система ограничений для правой области решений представлена ниже.

х₁ =4

х₂ = 1

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

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

,

В результате решения найден оптимальный план задачи: х₁ = 3, х₂ = 3, F = -12. Этот план удовлетворяет условию целочисленности переменных в задаче и может быть принят в качестве оптимального опорного плана для исходной задачи целочисленного линейного программирования. Проводить решение для правой области решений нет смысла. На рисунке ниже представлен ход решения целочисленной задачи линейного программирования в виде дерева.

x1 =9/4 x2 = 5/2 F = 41/4

Бесперспективное

направление решения

X₁ ≤ 3 X₁ ³ 4

x1 = 3 x2 = 3 F = -12

x1 = 4 x2 = 1 F = 0

Оптимальный план

Ход решения целочисленной задачи ЛП методом «ветвей и границ»

Х1 = 3, Х2 = 3, Fmin = -12

8. Ход решения целочисленной задачи линейного программирования
методом Гомори.

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

(1)

(2)

Требуется найти целочисленное решение системы (1), которое минимизирует целевую функцию F, причем, все коэффициенты - целые.

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

1)Определяется с помощью симплекс-метода решение задачи (1), (2), у которой снято требование целочисленности решения; если решение оказывается целочисленным, то искомое решение целочислен­ной задачи будет также найдено;

2) В противном случае, если некоторая координата - не целая, полученное решение задачи проверяется на возможность существования целочисленного решения (наличие целых точек в допустимом многограннике):

- если в какой-либо строке с дробным свободным членом , все остальные коэффициенты окажутся целыми, то в допустимом многограннике нет целых, точек и задача целочисленного программирования решения не имеет;

- в противном случае вводится дополнительное линейное ограничение, которое отсекает от допустимого многогранника часть, бесперспектив­ную для поиска решения задачи целочисленного программирования;

3) Для построения дополнительного линейного ограничения, выбираем l-тую строку с дробным свободным членом и записываем дополнительное ограничение

(3)

где и - соответственно дробные части коэффициентов и свободного

члена . Введем в ограничение (3) вспомогательную переменную :

(4)

Определим коэффициенты и , входящие в ограничение (4):

(5)

где и - ближайшие целые снизу для и соответственно.

4) Далее с помощью симплекс-метода снова решается задача линейного программирования при наличии дополнительного ограничения и т.д.

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

Решение: Приведем систему линейных ограничений и функцию цели к канонической форме:

Определим оптимальное решение системы линейных ограничений, времен­но отбросив условие целочисленности. Используем для этого симплекс-метод. Ниже последовательно в таблицах представлены исходное решение задачи, и приведены преобразования исходной таблицы с целью получения оптимального решения задачи:

Свободные   Базисные
		-2 -2/3	1/3
	-1	2/3	-1/3
		-2/3	-1 1/3
		-2/3	-1 1/3
	-5	-1   10/3	-5/3

Свободные   Базисные
		-2/3 1/4	1/3   -1/12
		8/3 3/8	-1/3 -1/8
	-1	1/3 -1/8	1/3   1/24
	-1	1/3 -1/8	1/3   1/24
	-5 -7	7/3 -7/8	-5/3   7/24

Свободные   Базисные
		1/4	1/4
		3/8	-1/8
		-1/8	9/24
		-1/8	9/24
	-12	-7/8	-11/8

Из таблицы видно, что получено следующее оптимальное решение системы линейных ограничений:

Fmax = -12

X^T=[3,3,0,0,3,1]

Найденная оптимальная точка является целочисленной. Целочисленность решения не нарушается по всем координатам.