Занятие 8 Целочисленное программирование

Цель:

• научиться осуществлять постановку задачи целочисленного программирования;

• освоить метод отсечения плоскостей (Гомори) для решения задач полностью целочисленного программирования.

Ход работы

Пример 8.1.

Компания может инвестировать средства по четырем направлениям: инвестиции №1 принесут доход в 16 тыс. грн., инвестиции №2 – в 22 тыс., №3 – 12 тыс., №4 – 8 тыс.

Каждая из инвестиций требует вложения денег в настоящее время: для инвестиции №1 – 5 тыс., №2 – 7 тыс., №3 – 4 тыс., №4 – 3 тыс.

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

Решение

Определим переменные:

Тогда доход компании будет описываться выражением

,

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

Данную задачу целочисленного программирования с булевыми переменными совершенно не имеет смысла решать симплекс методом: решение z = 44,8 при x₁ = 2,8, x₂ = x₃ = x₄ = 0 нас устроить не может, поскольку по смыслу нельзя 2,8 раз осуществить одну и ту же инвестицию. Если дополнить эту задачу ограничением x_j  1, , решение тоже нас не удовлетворит (z = 44 при x₁ = x₂ = 1, x₃ = 0,5, x₄ = 0), поскольку инвестицию №3 нельзя осуществить наполовину. Если же округлить x₃ до 1, получим недопустимое решение (нужно потратить 16 тыс.), округление же x₃ до 0 даст решение, далекое от оптимального (z = 38).

Оптимальным же решением будет x₁ = 0, x₂ = x₃ = x₄ = 1, которое дает z = 42 тыс.

Одним из методов решения задачи целочисленного программирования является методов отсекающих плоскостей (Гомори).

Задача 8.2.

Решить полностью целочисленную задачу:

Решение

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

Здесь переменные S₁ и S₂ также считаем целочисленными.

Для решения задачи методом Гомори сначала решается линейно-ослабленная задача – то есть задача, у которой не наложено ограничение на целочисленность переменных. Решим симплекс-методом линейно-ослабленную задачу:

Базис	cj		x1	x2	S1	S2
			-1	-1	0	0
S1	0	5	3	2	1	0
S2	0	2	0	1	0	1
		0	1	1	0	0

Базис	cj		x1	x2	S1	S2
			-1	-1	0	0
S1	0	1	3	0	1	-2
x2	-1	2	0	1	0	1
		-2	1	0	0	-1

Базис	cj		x1	x2	S1	S2
			-1	-1	0	0
x1	-1	1/3	1	0	1/3	-2/3
x2	-1	2	0	1	0	1
		–7/3	0	0	-1/3	-1/3

Итак, в последней таблице получен оптимальный результат (1/3, 2). К сожалению, первая компонента этого решения не отвечает требованию целочиленности. Поэтому нам придется вводить отсечение. Для базисной переменной x₁ в первой строке таблице мы имеем следующее уравнение:

Запишем его иначе, оставив слева целые части, а справа дробные:

По отношению к этому уравнению построим отсечение:

Приведем это ограничение к стандартному виду и добавим в это ограничение в последнюю симплекс таблицу:

Базис	cj		x1	x2	S1	S2	S3
x1	-1	1/3	1	0	1/3	-2/3	0
x2	-1	2	0	1	0	1	0
S3	0	-1/3	0	0	-1/3	2/3	1
		-7/3	0	0	-1/3	-1/3	0
отн.			–	–	1	–	–

Заметим, что данное решение недопустимо, поскольку S₃ = –1/3 является отрицательным. Поэтому данная строка выбирается в качестве разрешающей. Чтобы выбрать разрешающий столбец рассчитаем отношения (алгоритм двойственного симплекс метода): отрицательные элементы разрешающей строки разделить на элементы строки целевой функции. Из полученных отношений выбирается минимальное.

Таким образом, переменная S₁ должна войти в базис. Пересчет приводит нас к следующей таблице:

Базис	cj		x1	x2	S1	S2	S3
x1	-1	0	1	0	0	0	1
x2	-1	2	0	1	0	1	0
S1	0	1	0	0	1	–2	–3
		–2	0	0	0	–1	–1

Этой таблице уже соответствует оптимальный целочисленный ответ (0, 2). При этом .