Целочисленное программирование ориентировано на решение задач математического программирования, в которых все или некоторые переменные должны принимать только целые значения.
Если условие целочисленности наложено на все переменные, то задача является полностью целочисленной; когда это условие относится лишь к некоторым переменным, задача является частично целочисленной.
Если целевая функция и функции, входящие в ограничения, линейные, то задача является линейной целочисленной.
ЛИНЕЙНЫЕ ПОЛНОСТЬЮ ЦЕЛОЧИСЛЕННЫЕ ЗАДАЧИ
Такие задачи формулируются следующим образом:
найти минимальное значение линейной функции
при ограничениях , , целые.
Примерами задач ЦЧП являются задачи раскроя материалов, загрузки оборудования, распределения судов по линиям, самолётов по рейсам, а также задачи по производству неделимой продукции.
Допустим, что задача линейного программирования имеет многоугольник решений, приведённый на рисунке.
Если наложить требование целочисленности, то допустимыми решениями такой задачи будут не все точки фигуры , а лишь те, координаты которых являются целыми числами (эти точки выделены на рисунке).
Задачи целочисленного программирования нельзя решать путём простого округления значений переменных, полученных при решении задачи без учёта требования целочисленности. Найденное таким образом решение может даже не удовлетворять ограничениям задачи, а если и будет удовлетворять, то может быть совсем не оптимальным.
Методы решения ЗЦЧП подразделяются на:
1) методы отсечений;
2) комбинаторные методы.
При решении задач методами отсечений сначала находят оптимальное решение задачи, которая получается из исходной, если отбросить требование целочисленности. Затем вводят специальные дополнительные ограничения (по одному на каждой итерации). Эти дополнительные ограничения учитывают требования целочисленности. Они деформируют многоугольник решений задачи до тех пор, пока координаты оптимального решения не станут целыми.
Одним из наиболее широко используемых методов отсечений является метод Гóмори (метод отсекающих плоскостей). Название «метод отсекающих плоскостей» связано с тем обстоятельством, что вводимые дополнительные ограничения отсекают (исключают) области многоугольника (многогранника) решений, в которых отсутствуют точки с целочисленными координатами.
В основе комбинаторных методов лежит идея перебора всех допустимых целочисленных решений. Разумеется, перебирать все решения очень сложно и долго, поэтому разработаны тестовые процедуры, позволяющие непосредственно рассматривать лишь относительно небольшую часть решений, а остальные – учитывать некоторым косвенным образом.
Наиболее известным комбинаторным методом является метод ветвей и границ, который также опирается на процедуру решения задачи без учёта требования целочисленности. Далее из рассматриваемой задачи получаются две подзадачи путём специального разбиения пространства решений и отбрасывания областей, не содержащих допустимых целочисленных решений.
Метод Гóмори (метод отсекающих плоскостей)
Необходимым условием применения данного метода является целочисленность всех коэффициентов и правых частей ограничений исходной задачи.
(1)Нахождение решения ЗЦЧП начинают с определения оптимального решения задачи без учёта требования целочисленности переменных.
После того, как это решение найдено, просматривают его компоненты. Если среди них нет дробных чисел, то найденное решение является оптимальным решением ЗЦЧП.
Если же некоторая переменная принимает дробное значение, то к системе уравнений необходимо добавить дополнительное ограничение.
(2) Составляют дополнительное неравенство: ,
где и - преобразованные исходные величины и , значения которых взяты из последней симплексной таблицы;
и - дробные части чисел[1].
Если дробные значения принимают несколько переменных, то дополнительное неравенство составляют для переменной, имеющей максимальную дробную часть (дополнительное ограничение может составляться и для целевой функции).
(3) Используя двойственный симплекс-метод, находят решение задачи, полученной в результате присоединения дополнительного ограничения.
(4) Если в найденном решении задачи переменные опять принимают дробные значения, то снова добавляют одно дополнительное ограничение, и процесс вычислений повторяют.
Если на некотором шаге при использовании двойственного симплекс-метода обнаружится отсутствие допустимого решения, то рассматриваемая ЗЦЧП не имеет допустимого целочисленного решения.
Пример 1.
Р е ш е н и е. Обе части первого неравенства системы ограничений умножим на 2 (чтобы коэффициенты при переменных стали целыми):
ОЗЛП
-1
-18
-3
-63
-63
-63
Дополнительное ограничение составим для переменной . Из последней симплексной таблицы имеем: ,
.
Дополнительное ограничение имеет вид:
,
или .
Умножим неравенство на и преобразуем его в уравнение:
,
.
Переменную введём в базис:
.
Использование двойственного симплекс-метода приводит
к таблице 5.
-63
-59
-1
-8
-59
-59
Так как решение опять не является целочисленным, необходимо продолжить процесс введения отсечений.
Из последней таблицы: ,
.
,
или .
Умножим неравенство на и преобразуем его в уравнение:
,
,
.
Добавим это уравнение к последней таблице.
Использование двойственного симплекс-метода приводит к таблице 7.
-1
-4
-7
-59
-1
-8
-55
-7
-2
Таблица 7 даёт оптимальное целочисленное решение исходной задачи:
при , .
Графическое решение
Область допустимых решений задачи без учёта требования целочисленности приведена на рисунке.
Изобразим полуплоскости, соответствующие дополнительным ограничениям, и покажем, как изменится многоугольник решений задачи (а, следовательно, и оптимальное решение).
Первое дополнительное неравенствоумножим на 22.
Получим: .
Запишем это неравенство в переменных и :
,
, , , .
Второе дополнительное неравенствоумножим на 7.
Получим: .
Запишем это неравенство в переменных и :
, ,
, ,
, .
Пример 2.В цехе предприятия решено установить дополнительное оборудование, для размещения которого выделено 19/3 м2 площади.
На приобретение оборудования предприятие может израсходовать 10 000 ден.ед., при этом оно может купить оборудование двух видов.
Комплект оборудования I вида стоит 1 000 ден.ед., а II вида – 3 000 ден.ед.
Приобретение одного комплекта оборудования I вида позволяет увеличить выпуск продукции в смену на 2 ед., а одного комплекта оборудования II вида – на 4 ед.
Зная, что для установки одного комплекта оборудования I вида требуется 2 м2 площади, а оборудования II вида – 1 м2 площади, определить такой набор дополнительного оборудования, который даёт возможность максимально увеличить выпуск продукции.
Математическая модель задачи
ОЗЛП
Решение методом Гомори
др.ч.
3,33
0,33
0,33
2,73
-0,07
0,4
0,73
-1
1,8
0,2
-0,2
0,8
-13,33
0,67
-1,33
-14,53
-0,13
-1,2
0,47
Дополнительное ограничение:
2,73
-0,07
0,4
-0,33
0,67
1,8
0,2
-0,2
-1
-0,8
-0,2
-0,8
-5
-14,53
-0,13
-1,2
-14
-0,67
-0,67
0,67
1,5
Ответ: , , , т.е. предприятию следует купить один комплект оборудования I-го вида и три комплекта оборудования II-го вида; увеличение выпуска продукции составит при этом 14 единиц в смену.
[1] Дробная часть действительного числа определяется выражением: , где - наибольшее целое число, не превосходящее .
, 
, 
целые.
, а лишь те, координаты которых являются целыми числами (эти точки выделены на рисунке).
принимает дробное значение, то к системе уравнений необходимо добавить дополнительное ограничение.
,
и 
- преобразованные исходные величины 
и 
, значения которых взяты из последней симплексной таблицы;
и 
- дробные части чисел[1].
,
.
,
.
и преобразуем его в уравнение:
,
.
введём в базис:
.
,
.
,
.
,
,
.
при 
, 
.
умножим на 22.
.
,
, 
, 
, 
.
умножим на 7.
.
, 
,
, 
,
, 
.
, 
, 
, т.е. предприятию следует купить один комплект оборудования I-го вида и три комплекта оборудования II-го вида; увеличение выпуска продукции составит при этом 14 единиц в смену.