2. Построим область допустимых решений.
ОДР - неограниченная выпуклая многоугольная область.
3. Найдем оптимальное решение злп
В точке с координатами (2; 3) целевая функция принимает минимальное значение = 22.
Ответ: 1) самый дешевый набор для профилактического приема состоит из 2 грамм комплекса «Здоровье» и 3 грамм комплекса «Долголетие» и его стоимость равна 22 ден.ед.
2) Если использовать этот набор для профилактического приема, то нормы витаминов V1=9 и V2=8 будут точно выполнены, а витамин V3 = 20.
Алгоритм графического решения злп
1. Составить математическую модель задачи, т.е. систему ограничений и целевую функцию.
2. Построить область допустимых решений.
2.1. Построить на плоскости Ох1,х2 прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.
2.2. Найти полуплоскости, определяемые каждым из ограничений (неравенств).
2.3. Пересечение этих полуплоскостей – даст Область допустимых решений3 (ОДР). При этом возможен один из трех случаев:
ОДР – пустая область (система ограничений несовместна и, следовательно, ЗЛП не имеет решений);
ОДР – выпуклый многоугольник (задача имеет оптимальное решение);
ОДР – неограниченная выпуклая многоугольная область (в зависимости от коэффициентов целевой функции задача может иметь или не иметь решения, т.к. целевая функция неограниченно возрастает (zmax +) или неограниченно убывает (zmax - ) в области допустимых решений. .
3. Найти оптимальное решение
построить линию уровня целевой функции F(x), то есть прямую c1x1 + c2x2 = h, где h - любое положительное число;
построить вектор-градиент целевой функции
перемещать линию уровня в направлении вектора-градиента (при поиске мах, и в противоположном направлении при поиске мин). Получим семейство параллельных прямых. На области допустимых решений надо найти точку, через которую пройдет последняя линия уровня. Определить координаты найденной точки максимума (минимума) функции и вычислить значение функции в этой точке.
Тема 2. Лекция 2, практика 2.
Вопросы:
Графическое решение злп
Двойственность в задачах линейного программирования
Решение задачи линейного программирования средствами ms Excel
Анализ задач линейного программирования в ms Excel
1. Графическое решение злп
Задача 1. Об оптимальном использовании ресурсов.
Предприятие выпускает два вида продукции: П1 и П2. На изготовление единицы П1 требуется затратить а11 кг сырья первого типа, а21 кг сырья второго типа. На изготовление единицы П2 требуется затратить a12 кг сырья первого типа, a22 кг сырья второго типа. Производство обеспечено сырьем каждого типа в количестве b1 кг и b2 кг соответственно. Рыночная цена единицы П1 составляет c1 тыс. ден. ед., а единицы П2 - c2 тыс. ден. ед.
а11=2 |
а12=1 |
b1=400 |
а21= 3 |
а22= 4 |
b2= 900 |
с1=60 |
с2=40 |
|
Требуется:
1) построить математическую модель задач;
2) решить графически ЗЛП, т.е. найти план производства продукции, обеспечивающий максимальную выручку от их реализации.