Задача.
Имеется предприятие по производству колбасы. Мы можем выпускать 2 вида колбасы:
- вареную;
- ветчинно-рубленную.
Цена вареной колбасы 120 руб.
Цена ветчинно-рубленной – 200 руб.
Для производства этих колбас используется 3 вида рекурсов:
- говядина,
- свинина,
- горох.
На складе имеются следующие запасы этих ресурсов:
- говядина – 100 кг.,
- свинина – 60 кг.,
- горох – 200 кг.
Известны нормативы затрат каждого вида ресурса на производство единицы продукции:
Ставится задача: Лицо, принимающее решения, должно составить план выпуска продукции, так чтобы уложиться в ограничение и обеспечить максимум стоимости выпускаемой продукции.
Введем переменные:
x – количество выпускаемой продукции,
j – номер выпускаемой продукции, j=1,2,
Тогда хj – количество продукции j-го типа, которое мы должны определить.
b – количество ресурса, которым располагает ЛПР.
i – номер ресурса, i=1,3,
Цj – цена за 1 ед. j-го типа продукции,
bi - количество ресурсов i-го типа, которыми распоряжается ЛПР,
а – норматив затрат ресурса,
аij – показывает сколько единиц i-го ресурса требуется для производства 1 шт. j-той продукции.
Задачи, в которых переменные и критерии и в ограничениях находятся в первой степени, называются задачами линейного программирования.
Задача в общем виде:
- количество говядины, которая потребуется, чтобы реализовать нашу продукцию,
- количество свинины, которая потребуется, чтобы реализовать нашу продукцию,
- количество гороха, который потребуется, чтобы реализовать нашу продукцию.
Общий вид задачи:
120х1 + 200х2 → max
0,7х1 + 0,3х2 ≤ 100
0,2х1 + 0,6х2 ≤ 60
0,1х1 + 0,1х2 ≤ 200.
Решим задачу методом геометрической интерпретации:
ОДС1 – если смотреть на задачу через призму только 1-го ограничения (говядины),
ОДС2 – если смотреть на задачу через призму только 2-го ограничения (свинины).
Построим прямую Ф=0. Точка, максимально удаленная от прямой Ф=0 – точка оптимума.
Оптимальное решение находится на пересечении условий (пересечение условий говядины и свинины).
0,7х1 + 0,3х2 = 100
0,2х1 + 0,6х2 = 60,
Точка оптимума имеет координаты
х1 = 116,56
х2 = 61,143
Резерв по ресурсу – это разность между запасами с сколько надо потратить.
у1 = 0
у2 = 0 резервные ресурсы.
У3 ≠ 0 – недефицитны ресурс.