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

Задача целочисленного линейного программирования (задача ЦЛП) формулируется следующим образом: найти максимум (минимум) линейной целевой функции: Z = ∑cjxj→max(min) на множестве, задаваемом ограничениями:
∑aijxj, i=1,m.
хj≥0, j=1,n, хj – целые числа,

Назначение сервиса. С помощью сервиса можно решить задачу целочисленного программирования геометрическим методом. Для проверки решения создается шаблон в Excel.

Количество ограничений
При этом ограничения типа xi ≥ 0 не учитывайте.
Решение задачи целочисленного программирования графическим методом включает следующие этапы:
  1. Построение множества допустимых решений задачи без учета условия целочисленности и отметить в нем все целочисленные точки.
  2. С помощью линий уровня нахождение оптимальной целочисленной точки, в которой целевая функция достигает своего максимума (минимума).

см. также Задачи ЦЛП. Примеры решений.

Пример. Завод выпускает два вида узлов У1 и У2 для систем управления, используя для этого два вида технологических линеек Л1 и Л2. На производство одного узла вида У1 на линейке Л1 затрачивается 2 часа, на изготовление одного узла У2 затрачивается соответственно 1 час и 2 часа. Завод может использовать Л1 в течение 10 час., а Л2 – 8 час. Прибыль от реализации одного изделия У1 – 5$, а от реализации одного изделия У2 – 4$. Определить количество узлов У1 и У2, которое необходимо выпустить заводу, чтобы получить максимальную прибыль.
Решение:

У1У2Запас времени
Л12110
Л2028
Прибыль54max
Составим экономико-математическую модель задачи.
x1 - количество узлов У1
x2 - количество узлов У2
x1≥ 0,x2 ≥ 0
x1,x2 - целые
Ограничения по запасу времени
2x1 + x2 ≤ 10
2x2 ≤ 8
Целевая функция: F(x) = 5x1 + 4x2 → max
загрузка...