МатБюро Примеры решений задач Линейное программирование Целочисленные задачи линейного программирования

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

Многие задачи линейного программирования, если рассмотреть их содержательную постановку (экономическое значение), например, задача о производстве столов, шкафов и кроватей с максимальным доходом при ограниченных ресурсах, являются на самом деле целочисленными задачами линейного программирования (трудно ведь представить, что компания может произвести и продать 1/3 стола или 11/4 шкафа?).

Таким образом, мы берем обычные задачи линейного программирования (см. примеры на графический метод, симплексный метод, двойственные задачи) и всего лишь добавляем ограничение: все переменные должны принимать целые значения. Но несмотря на такое, казалось бы, небольшое усложнение, само решение задачи становится куда более объемным. Если речь идет о задаче с двумя переменными, проще всего по-прежнему применить графический метод, если же переменных больше, приходится использовать специальные методы для этого класса задач: метод Гомори или метод ветвей и границ.

Ниже вы найдете примеры решений различными способами (графический, Гомори, ветвей и границ) целочисленных задач ЛП - изучайте, ищите похожие, решайте. Если вам нужна помощь в выполнении заданий, перейдите в раздел: Решение контрольных по линейному программированию.

Целочисленные задачи ЛП: примеры онлайн

Задача 1. Найдите графическим методом и методом Гомори оптимальное целочисленное решение задачи линейного программирования, если она задана следующей математической моделью

Решение методом Гомори задачи целочисленного ЛП (pdf, 131 Кб)

Задача 2. Решите задачу методом Гомори

Решение задачи методом Гомори (pdf, 53 Кб)

Задача 3. Найти оптимальное решение задачи целочисленного линейного программирования

Решение методом ветвей и границ задачи целочисленного ЛП (pdf, 61 Кб)

Задача 4. 1. Найти целочисленное решение задачи линейного программирования.
2.Составить двойственную задачу и решить её без условия целочисленности.
3. По теоремам двойственности проверить связь нецелочисленных решений прямой и двойственной задачи.

Решение задачи методом Гомори, двойственные задачи (pdf, 135 Кб)


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