АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Алгоритм решения ЗЛП графическим методом

Читайте также:
  1. B) международным географическим разделением труда
  2. IV. Алгоритм действий командира (начальника) при увольнении военнослужащего в связи с невыполнением им условий контракта
  3. IX. Сложные решения
  4. LZW-модификация алгоритма Лемпеля-Зива
  5. Wiley, 1993), p. 142. Перепечатано с разрешения.
  6. Zip–модификация алгоритма Лемпеля-Зива
  7. А.3.3. Алгоритм медикаментозного лікування
  8. Абсолютизм. Общая характеристика. Особенности стиля. Используемые композиционные решения, конструктивные элементы и строительные материалы. Ключевые здания. Ключевые архитекторы.
  9. АВТОМАТИЗАЦІЯ УСТАНОВКИ ДЛЯ ОТРИМАННЯ РЕЧОВИНИ МЕТОДОМ ЗМІШУВАННЯ
  10. АВТОРСКИЙ ПРОЕКТ ФОРМИРОВАНИЯ КУЛЬТУРЫ ЛЮБВИ У ДЕТЕЙ –СОЦИАЛЬНЫХ СИРОТ МЕТОДОМ КАНИСТЕРАПИИ «ГОРОД СОЛНЦА» (Г. БАРНАУЛ)
  11. Алгоритм
  12. Алгоритм

Решение ЗЛП графическим методом складывается из следующих этапов:

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 – количество изделий вида В, которые необходимо изготовить по плану. Значение функции – прибыль предприятия от реализации произведенной продукции.

(1) (2) (3) (4)

Соблюдая последовательность действий при использовании графического метода решения, строим область допустимых планов W (используя систему ограничений ЗЛП и условия неотрицательности), вектор-градиент целевой функции , линию нулевого уровня 7х1 + 5х2 = 0.

 

 


Рис. 5.

Перемещая линию нулевого уровня вдоль градиентного направления, находим, что



Определим координаты вершины Р4.

Определитель системы

Так как , то система совместна по теореме Крамера и имеет единственное решение

Вычислим вспомогательные определители


По формулам Крамера находим

Таким образом, Р4(5; 3). Зная координаты точки Р4, определим максимальное значение целевой функции

Значит, для получения максимальной прибыли в размере 50 у.е. предприятию при заданных ограничениях на запасы сырья следует производить пять изделий типа А и три изделия типа В.

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |


При использовании материала, поставите ссылку на Студалл.Орг (0.005 сек.)