Графический метод решения задач целочисленного программирования
Задача целочисленного линейного программирования (задача ЦЛП) формулируется следующим образом: найти максимум (минимум) линейной целевой функции:Z = ∑cjxj→max(min) на множестве, задаваемом ограничениями:
∑aijxj, i=1,m.
хj≥0, j=1,n, хj – целые числа,
Назначение сервиса. С помощью сервиса можно решить задачу целочисленного программирования геометрическим методом. Для проверки решения создается шаблон в Excel.
Решение задачи целочисленного программирования графическим методом включает следующие этапы:
- Построение множества допустимых решений задачи без учета условия целочисленности и отметить в нем все целочисленные точки.
- С помощью линий уровня нахождение оптимальной целочисленной точки, в которой целевая функция достигает своего максимума (минимума).
Пример. Завод выпускает два вида узлов У1 и У2 для систем управления, используя для этого два вида технологических линеек Л1 и Л2. На производство одного узла вида У1 на линейке Л1 затрачивается 2 часа, на изготовление одного узла У2 затрачивается соответственно 1 час и 2 часа. Завод может использовать Л1 в течение 10 час., а Л2 – 8 час. Прибыль от реализации одного изделия У1 – 5$, а от реализации одного изделия У2 – 4$. Определить количество узлов У1 и У2, которое необходимо выпустить заводу, чтобы получить максимальную прибыль.
Решение:
| У1 | У2 | Запас времени | |
| Л1 | 2 | 1 | 10 |
| Л2 | 0 | 2 | 8 |
| Прибыль | 5 | 4 | max |
x1 - количество узлов У1
x2 - количество узлов У2
x1≥ 0,x2 ≥ 0
x1,x2 - целые
Ограничения по запасу времени
2x1 + x2 ≤ 10
2x2 ≤ 8
Целевая функция: F(x) = 5x1 + 4x2 → max
