 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Алгоритм решения ЗЛП графическим методом
Решение ЗЛП графическим методом складывается из следующих этапов:
1) В плоскости х 1 ох 2 строим область допустимых планов данной ЗЛП – область W;
Рис. 4
2) Находим вектор-градиент;
3) Строим линию нулевого уровня 
;
4) Линию нулевого уровня перемещаем вдоль градиентного направления (см. рис. 4) и определяем ту вершину выпуклого многогранника W, которая впервые соприкасается с линией уровня. Эта вершина и будет отвечать оптимуму целевой функции типа минимум 
.
Затем линию уровня перемещаем вглубь ОДЗ (см. рис. 4) и отыскиваем ту вершину многогранника W, после которой линия уровня будет покидать указанную область. Эта вершина и будет отвечать оптимуму целевой функции типа максимум 
.
5) Для получения численного решения задачи находим координаты соответствующих вершин многогранника и вычисляем значения целевой функции в этих точках.
Пример. Некоторое предприятие освоило производство продукции двух видов А и В, используя при этом сырье четырех типов S1, S2, S3, S4. Запасы сырья и норма их расхода на производство единицы продукции указаны в таблице. Известно, что прибыль предприятия от реализации единицы продукции вида А составляет 7 у.е., а от реализации единицы товара типа В – 5 у.е. Определить такой план выпуска продукции, который бы позволил предприятию получить максимальную прибыль.
| Вид продук- Вид ции сырья | А | В | Запасы сырья |
| S1 | |||
| S2 | |||
| S3 | |||
| S4 | |||
| Прибыль |
Сформулируем задачу математически. Через х 1 обозначим количество изделий вида А, а через х 2 – количество изделий вида В, которые необходимо изготовить по плану. Значение функции 
– прибыль предприятия от реализации произведенной продукции.
|
Соблюдая последовательность действий при использовании графического метода решения, строим область допустимых планов W (используя систему ограничений ЗЛП и условия неотрицательности), вектор-градиент целевой функции 
, линию нулевого уровня 7 х 1 + 5 х 2 = 0.
Рис. 5.
Перемещая линию нулевого уровня вдоль градиентного направления, находим, что
Определим координаты вершины Р 4.
Определитель системы
Так как 
, то система совместна по теореме Крамера и имеет единственное решение
Вычислим вспомогательные определители
По формулам Крамера находим
Таким образом, Р 4(5; 3). Зная координаты точки Р 4, определим максимальное значение целевой функции
Значит, для получения максимальной прибыли в размере 50 у.е. предприятию при заданных ограничениях на запасы сырья следует производить пять изделий типа А и три изделия типа В.
Поиск по сайту: