Решение задач целочисленного линейного программирования
Многие задачи линейного программирования, если рассмотреть их содержательную постановку (экономическое значение), например, задача о производстве столов, шкафов и кроватей с максимальным доходом при ограниченных ресурсах, являются на самом деле целочисленными задачами линейного программирования (трудно ведь представить, что компания может произвести и продать 1/3 стола или 11/4 шкафа?).
Таким образом, мы берем обычные задачи ЛП (см. примеры на графический метод, симплексный метод, двойственные задачи) и всего лишь добавляем ограничение: все переменные должны принимать целые значения. Но несмотря на такое, казалось бы, небольшое усложнение, само решение задачи становится куда более объемным. Если речь идет о задаче с двумя переменными, проще всего по-прежнему применить графический метод, если же переменных больше, приходится использовать специальные методы для этого класса задач: метод Гомори или метод ветвей и границ.
Ниже вы найдете примеры решений различными способами (графический, Гомори, ветвей и границ) целочисленных задач ЛП - изучайте, ищите похожие, решайте. Если вам нужна помощь в выполнении заданий, перейдите в раздел: Линейное программирование на заказ.
Целочисленные задачи ЛП: примеры онлайн<
Задача 1. Найдите графическим методом и методом Гомори оптимальное целочисленное решение задачи линейного программирования, если она задана следующей математической моделью
Задача 2. Решите задачу методом Гомори
Задача 3. Найти оптимальное решение задачи целочисленного линейного программирования
Задача 4. 1. Найти целочисленное решение задачи линейного программирования.
2.Составить двойственную задачу и решить её без условия целочисленности.
3. По теоремам двойственности проверить связь нецелочисленных решений прямой и двойственной задачи.
Задача 5. Фирма занимается производством корпусной мебели и выпускает два вида книжных полок: А и В.
В первом цехе осуществляется распил ламинированных древесно-стружечных плит (ЛДСП) и сборка каркаса, во втором – остекление полок. Затраты времени в каждом цехе и расход материала на изготовление одной книжной полки, а также прибыль от реализации единицы продукции указаны в таблице.
Показатель Полки типа А Полки типа В
Расход ЛДСП на 1 ед, м2 2 3
Затраты времени в I цехе на 1 ед., ч 2,7 3
Затраты времени во II цехе на 1 ед., ч 1 1,2
Прибыль на 1 ед., у.е. 160 210
Месячный фонд времени, отведенный на изготовление полок, для первого цеха составляет 780 ч., для второго – 324 ч., максимально возможный объем расхода ЛДСП в месяц – 720 м2.
Определите месячный план выпуска продукции, при котором прибыль будет максимальной.
