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

План.

17.1. Математическая модель задачи.

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

17.3. Метод Гомори и его применение в экономических задачах.

Математическая модель задачи

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

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

.

Знаки некоторых или всех неравенств могут быть ≤, ≥.

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

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

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

В системе координат X₁0X₂ находят область допустимых решений, строят вектор–градиент Ñ L (` x) и линию уровня. Перемещая линию уровня по направлению вектора-градиента для задач на максимум, определяют наиболее удаленную точку и ее координаты.

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

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

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

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

Зная, что для установки одного комплекта оборудования 1-го вида требуется 2 м² площади, а для оборудования 2-го вида – 1 м² площади, определить такой набор дополнительного оборудования, который дает возможность максимально увеличить выпуск продукции.

Решение. Составим математическую модель задачи.

Предположим, что фирма приобретает х ₁ комплектов дополнительного оборудования 1-го вида и х ₂ комплектов дополнительного оборудования 2-го вида.

Математическая модель задачи будет иметь вид

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

.

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

Рис. 17.1.

0АВС – область допустимых решений (ОДР). Оптимальное решение задача имеет в точке В(9/5; 41/15), при этом максимальное значение целевой функции составляет 218/15 ед. Полученное оптимальное решение не целочисленное.

Условию целочисленности переменных удовлетворяют координаты 12 точек, принадлежащих ОДР. Чтобы найти точку, координаты которой определяют решение исходной задачи, заменим многоугольник 0АВС многоугольником 0KEMNF, содержащим все допустимые точки с целочисленными координатами.

Строим вектор-градиент Ñ L (` x) (2, 4). Линию уровня перемещаем по направлению вектора-градиента Ñ L (` x), получим в точке Е(1, 3) максимальное значение целевой функции

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