Лекция 10 Целочисленное программирование

Общая формулировка задачи

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

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

целое,

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

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

x1	1	0	…	0	…	0	h1,r+1	…	h1,n	f1
x2	0	1	…	0	…	0	h2.r+1	…	h2,n	f2
…	…	…	…	…	…	…	…	…	…	…
xi	0	0	…	1	…	0	hi,r+1	…	hi,n	fi
…	…	…	…	…	…	…	…	…	…	…
xr	0	0	…	0	…	1	hr,r+1	…	hr,r+1	fr

где r – ранг системы ограничений; h_i,r+1 – коэффициенты симплексной таблицы i-й строки, (r+1)-го столбца; f_i – свободный член i-й строки.

Пусть f_i и хотя бы одно h_ij ( ) – дробные числа.

Обозначим через [f_i] и [h_ij] целые части чисел f_i и h_ij.

Определение 1. Целой частью числа f_i называют наибольшее целое число, не превосходящее числа f_i.

Дробную часть чисел f_i и h_ij обозначим { f_i } { h_ij }, она определяется следующим образом:

{ f_i } = f_i - [f_i], { h_ij } = h_ij - [h_ij].

Пример.

Если f_i и хотя бы одно значение h_ij дробны, то с учётом введённых обозначений целых и дробных чисел дополнительное ограничение по целочисленности примет вид

Примечания. 1) Если f_i – дробное число, а все h_ij – целые числа, то задача линейного программирования не имеет целочисленного решения.

2) Ограничение целочисленности может быть наложено не на все переменные, а лишь на их часть. В этом случае задача является частично целочисленной.

Графический метод решения задач

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

В системе координат Х₁ОХ₂ находят область допустимых решений, строят и линию уровня. Перемещая линию уровня по направлению для задач на максимум, находим наиболее удалённую от начала координат точку и её координаты.

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

Аналогично решается задача на минимум.

Прогнозирование эффективного использования производственных площадей

Задача. Для улучшения финансового положения фирма приняла решение об увеличении выпуска конкурентоспособной продукции, для чего принято решение об установке в одном из цехов дополнительного оборудования, занимающего 19/3 м² площади. На приобретение дополнительного оборудования фирма выделила 10 усл. ед., при этом она может купить оборудование двух видов. Приобретение 1-го комплекта оборудования 1-го вида стоит 1,0 усл. ед., 2-го вида – 3 усл. ед. Приобретение одного комплекта оборудования 1-го вида позволяет увеличить выпуск продукции в смену на 2 шт., а одного комплекта оборудования 2-го вида – на 4 шт. Зная, что для установки одного комплекта оборудования 1-го вида требуется 2 м² площади, а для оборудования 2-го вида – 1 м² площади, определить такой набор дополнительного оборудования, который даёт возможность максимально увеличить выпуск продукции.

РЕШЕНИЕ. Составим математическую модель задачи. Предположим, что фирма приобретает х₁ комплектов дополнительного оборудования 1-го вида и х₂ комплектов оборудования 2-го вида. Математическая модель задачи будет иметь вид

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

- целые.

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

ОТВЕТ. Фирме следует приобрести один комплект оборудования 1-го вида и три комплекта оборудования 2-го вида, что обеспечит её при имеющихся ограничениях на производственные площади и денежные средства максимальное увеличение выпуска продукции, равное 14 усл.ед. в смену.

Метод Гомори

Решим эту же задачу методом Гомори.

сi	БП	2	4	0	0
		х1	х2	х3	х4	bi
0 0	x3 x4	2 1	1 3	1 0	0 1	19/3 10
∆j		-2	-4	0	0	0
0 4	x3 x2	5/3 1/3	0 1	1 0	-1/3 1/3	3 10/3
∆j		-2/3	0	0	4/3	40/3
2 4	x1 x2	1 0	0 1	3/5 -1/5	-1/5 2/5	9/5 41/15
∆j		0	0	2/5	6/5	218/15

Получим

Найдём дробные части чисел 9/15 и 41/15:

Учитывая дробные части чисел 3/5 и -1/5:

составляем дополнительное ограничение целочисленности для 1-й строки:

или

которое вводим в таблицу:

сi	БП	2	4	0	0	0
		х1	х2	х3	х4	х5	bi
2 4	x1 x2	1 0 0	0 1 0	3/5 -1/5 3/5	-1/5 2/5 4/5	0 0 -1	9/5 41/15 4/5
2 4 0	x1 x2 х3	1 0 0	0 1 0	0 0 1	-1 2/3 4/3	1 -1/3 -5/3	1 3 4/3
∆j		0	0	0	2/3	2/3	14

Получили