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

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

Задача. При модернизации оборудования в цехе выделено 64 м² для установки оборудования первого и второго типов. На установку одного комплекта оборудования первого типа требуется 2 м², на установку комплекта оборудования второго типа требуется 3,2 м². Причем, оборудование первого типа приносит ежемесячный доход 2 млн руб., а оборудование второго типа — 4 млн. Определить количество комплектов оборудования первого и второго типов, обеспечивающее максимальную прибыль, при условии, что предприятие может приобрести не более 20 комплектов оборудования первого типа и не более 11 комплектов оборудования второго типа.

Решение. Обозначим — количество устанавливаемого оборудования первого типа; - количество устанавливаемого оборудования второго типа. Тогда математическая модель задачи имеет вид:

Решим задачу двумя способами.

Первый способ — графический. В системе координат х0y построим прямые:

по точкам (0; 20) и (8; 15);

(прямая, проходящая через точку (20; 0) параллельно оси 0y);

(прямая, проходящая через точку (0; 11) параллельно оси 0x).

Определим область допустимых решений, задаваемую системой неравенств (рис. 1).

Рис. 1.

Многоугольник ОАBCD — область допустимых решений. Функция возрастает быстрее всего в направлении вектора. Строим вектор и прямую (линия уровня целевой функции). Перемещаем линию уровня целевой функции по направлению вектору нормали, пока не покинем область в точке B.

Точка B образуется при пересечении прямых:

и. Найдем ее координаты: В (14,4; 11). Максимальное значение в области допустимых решений .

Полученное оптимальное решение нецелочисленное. Для нахождения целочисленного решения заменим область OABCD на область (рис. 1), содержащую все допустимые точки с целочисленными координатами и такую, что координаты каждой из вершин данного многоугольника являются целыми числами. Тогда в области перемещаем линию уровня целевой функции по направлению вектору нормали, пока не покинем область в точке (14; 11). Максимальное значение целевой функции.

Второй способ — метод Гомори.

Задачу (5.1) приведем к каноническому виду.

Приведем задачу в каноническую форму:

Находим первоначальный опорный план и применяем симплекс-метод (табл. 2).

Таблица 2

Поскольку все оценки в последней строке неположительные, то найденный опорный план является оптимальным, причем .

Получили нецелочисленное оптимальное решение. Составляем дополнительное ограничение по переменной, имеющей нецелочисленное решение, используя выражение:

.

Найдем дробные части чисел:

;

;

.

Таким образом, дополнительное условие целочисленности для строки :

.

Введем неотрицательную переменную и составим уравнение.

.

Составим новую симплекс-таблицу (табл. 3) с дополнительным условием.

Таблица 3

Получили недопустимое базисное решение (). Для получения допустимого базисного решения переведем в основные переменные переменную (табл. 4).

Таблица 4

Поскольку все оценки в последней строке неположительные, то найденный опорный план является оптимальным, причем .

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