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

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

Читайте также:
  1. II Съезд Советов, его основные решения. Первые шаги новой государственной власти в России (октябрь 1917 - первая половина 1918 гг.)
  2. MathCad: способы решения системы уравнений.
  3. V2: ДЕ 53 - Способы решения обыкновенных дифференциальных уравнений первого порядка
  4. XII. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ
  5. Алгоритм
  6. Алгоритм
  7. Алгоритм
  8. Алгоритм
  9. Алгоритм 65 «Кровотечение в послеродовом периоде»
  10. Алгоритм 72 «Ожоги и травмы глаза, века, конъюнктивы»
  11. Алгоритм MD4
  12. Алгоритм RC6

1. Находим область допустимых решений системы ограни­чений задачи.

2. Строим вектор-градиент .

3. Проводим линию уровня L0, которая перпендикулярна вектору .

4. Линию уровня перемещаем по направлению вектора параллельно себе пока она не станет опорной к многоугольнику планов. Точка входа в область – точка минимума функции, точка выхода из области – точка максимума.

Если только одна общая точка с областью допусти­мых решений, то эта точка будет точкой экстремума и решение ЗЛП единственное.

Если окажется, что линия уровня проходит через одну из сторон ОДР, то в таком случае экстремум достигается во всех точках соответствующей стороны, а ЗЛП будет иметь бесчисленное множество решений. Говорят, что такая ЗЛП имеет альтернативный оптимум, и ее решение находят в виде выпуклой линейной комбинации решений :

 

где .

ЗЛП может быть неразрешима, когда определяющие ее ограничения окажутся противоречивыми (т. е. область допустимых решений окажется пустым множеством).

5. Находим координаты точки экстремума и значение це­левой функции в этой точке.

Пример 38.1.Найти максимум функции , если

Решение.

Определим вначале многоугольник решений – ОДР.

Для этого построим прямые, которые ограничивают этот многоугольник:

I: ; II: ;

III: ; IV: .

Каждая прямая отсекает отрезки на осях координат: I – (10;10); II – (-2;3); III – (-10;3); IV – (20;12).

Проверим справедливость каждого неравенства по одной точке (начало координат).

Рассмотрим первое неравенство: . Начало координат (0;0) не удовлетворяет этому неравенству, поэтому область решения лежит по другую сторону от прямой I; это показано на рис. 38.4 стрелками.

Для второго неравенства начало координат (0;0) удовлетворяет этому неравенству, поэтому область решения лежит по ту же сторону от прямой II, что и начало координат.

Рассмотрим неравенство . Начало координат (0;0) не удовлетворяет этому неравенству, поэтому область решения лежит по другую сторону от прямой ІII.

Рассмотрим неравенство . Начало координат (0;0) удовлетворяет этому неравенству, поэтому область решения лежит по ту же сторону от прямой IV, что и начало координат.

 



Замечание: Если ограни- чивающая прямая проходит через начало координат, то вместо точки (0;0) можно взять любую другую точку.

 

Рис. 38.4. Многоугольник решений

Образовалась область решения всех неравенств – это многоугольник АВСД – многоугольник планов.

Теперь строим градиент целевой функции. Это вектор: = .

Далее строим линию уровня, соответствующую ; она проходит через начало координат и перпендикулярна . Перемещая ее в направлении вектора , видим, что наиболее отдаленной вершиной многоугольника является вершина С.

Вычислим координаты этой вершины. Точка С лежит на пересечении прямых IIIи ІV. Решим систему уравнений этих прямых:

 

Откуда

Следовательно,

Пример 38.2. Найти минимум функции , если

Решение.

Для построения многоугольника решений можно использовать пример 38.1. Далее строим градиент целевой функции (рис. 38.5).

Это вектор: = .

Строим линию уровня , она проходит через начало координат и перпендикулярна . Пе­ремещая ее в направлении вектора = , видим, что вектор является нормальным вектором прямой III, значит линия уровня и прямая III параллельны, то есть при входе в область линия уровня совпадает с прямой .

 

 

38.5. Многоугольник решений

 

Вычислим координаты точек D и С, а также значение функции цели. Точка D лежит на пересечении прямых І и III. Решим систему уравнений:

 

Откуда

Тогда

 

Точка С лежит на пересечении прямых III и IV. Решим систему уравнений:

 

Откуда ,

Следовательно, минимум будет в любой точке отрезка :

 

где .

 

.

 




Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.014 сек.)