1 Цель и задачи Цель: Освоить методику решения задач целочисленного линейного программирования.
Задачи: 1 Уяснить формулировку задач, относящихся к классу задач целочисленного линейного программирования.
2 Освоить алгоритм Р.Гомори решения задач целочисленного линейного программирования.
Решить задачу целочисленного линейного программирования методом Р.Гомори.
Сформулировать краткие выводы по результатам решения задачи.
Программное обеспечение: пакет экономических расчетов PER.
2 Методика решения задачи целочисленного линейного программирования методом р.Гомори
2.1 Числовая задача
Для приобретения оборудования по сортировке зерна выделено 34 млн руб. Оборудование должно быть размещено на площади, не превышающей 60м2. Заказывается оборудование двух типов: А и В, характеристика которых дана в таблице 1.
Таблица 1 – Характеристика оборудования
Показатели |
Тип оборудования |
|
А |
В |
|
Занимаемая площадь, м2 |
3 |
5 |
Стоимость 1 машины, млн руб. |
3 |
4 |
Производительность в смену, т |
2 |
3 |
Составить оптимальный план приобретения оборудования, обеспечивающий максимум обшей производительности. Оборудования типа В приобретается не более 8 штук.
Последовательность решения задачи
2.2.1 Построение экономико-математической модели задачи
Переменные
Х1 - количество приобретаемых машин типа А, шт.
Х2 - количество приобретаемых машин типа В, шт.
Ограничения
По площади размещения машин, м2
3Х1 + 5Х2 < 60
По затратам денежных средств, млн руб.
(1)
3Х1 + 4Х2 < 34
По приобретению оборудования типа В, шт.
Х1 > 0, Х2 > 0, Х1, Х2 – целые числа.
Целевая функция
Критерий оптимальности – Максимум производительности оборудования, т.
Z = 2Х1 + 3Х2 => max
Математическая формулировка задачи.
Найти такие целочисленные значения переменных Х1 и Х2 , что выполняются ограничения задачи (1) и достигается максимальное значение целевой функции Z.
Экономическая формулировка задачи.
Определить, сколько необходимо приобрести оборудования типа А и сколько приобрести оборудования типа В, чтобы уложиться в выделенные ресурсы, выполнить план приобретения оборудования В и обеспечить максимальную производительность оборудования.
.
2.2.2 Подготовка задачи к решению симплексным методом
Запишем задачу (1) в каноническом виде:
3Х1 + 5Х2 + Х3 = 60
3Х1 + 4Х2 + Х4 = 34 (2)
Х2 + Х5 = 8
Хj > 0, j = 1, 5 ; Х1, Х2 – целые числа
Z = 2Х1 + 3Х2 + 0Х3 + 0Х4 + 0Х5 = > max