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

Этап решения модели

Читайте также:
  1. Can-Am-2015: новые модели квадроциклов Outlander L и возвращение Outlander 800R Xmr
  2. II Съезд Советов, его основные решения. Первые шаги новой государственной власти в России (октябрь 1917 - первая половина 1918 гг.)
  3. MathCad: способы решения системы уравнений.
  4. SALVATOR создает Знания-Образы, когнитивные имитационные модели сознания, расширяющие человеческие возможности и защитные функции.
  5. V. Идеология и практика модели «общенародного государства»
  6. V2: ДЕ 53 - Способы решения обыкновенных дифференциальных уравнений первого порядка
  7. YIII.5.2.Аналогия и моделирование
  8. Авторегрессионные модели временных рядов
  9. Алгоритм моделирования по принципу Dt.
  10. Алгоритм моделирования по принципу особых состояний.
  11. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧ НА ЗАКОН СОХРАНЕНИЯ ИМПУЛЬСА
  12. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧ НА ЗАКОН СОХРАНЕНИЯ ЭНЕРГИИ

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

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

Замечание. Графический̆ метод применим в случае двух переменных. Практических приложений у этого метода немного, но он важен для наглядности и понимания происходящего.

Сначала необходимо построить пространство решений, то есть получить область, точки которой удовлетворяют всем ограничениям. Каждое ограничение задает полуплоскость ограниченную некоторой̆ прямой, пересечение этих полуплоскостей̆ есть пространство решений.

Далее, необходимо максимизировать z = 5x1+4x2. Рассмотрим семейство соответствующих прямых.

Если z=0, то 0 = 5х1 + 4х2 (0; 0) и (2; -2,5). Если z=10, то 10 = 5х1 + 4х2 (0; 2,5) и (2; 0). Бесконечно много допустимых решений. Если z=15, то 15 = 5х1 + 4х2 (0; 3,7) и (3; 0). Бесконечно много допустимых решений.

Направление возрастания функции z = 5х1+4х2 есть перпендикуляр к прямым соответствующего семейства. В следствии чего, мы можем увеличивать значение целевой функции, пока соответствующая ей прямая имеет хотя бы одну общую точку с пространством решений.

..\Book1.xls

В нашем случае оптимальное решение соответствует точке пересечения прямых x1 + 2х2 ≤ 6 и x1 + 2х2 ≤ 6, то есть в точке С(3; 1,5), а значение целевой функции 21.

Значит лучшим решением будет выпускать 3т и 1,5т, получая при этом прибыль в 21 тис. ден. ед.

Замечание (Об угловой точке) Очевидно, что если область задана произвольным многоугольником, а максимизируемая функция имеет общий̆ вид z = ax + by, то решение (оптимум) все равно будет достигаться в угловой̆ точке.

Если мы изменим угол наклона, то есть коэффициенты целевой функции, то увидим, что решение достигается в любом случае в одной из угловых точек (или в нескольких).

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

1. На плоскости X10X2 строят прямые.

2. Определяются полуплоскости.

3. Определяют многоугольник решений;

4. Строят вектор N(c1; c2), который указывает направление целевой функции;

5. Передвигают прямую целевую функцию c1x2 + c2x2 = z в направлении вектора N до крайней точки многоугольника решений.

6. Вычисляют координаты точки и значение целевой функции в этой точке.

Приведем основные свойства задачи ЛП.

  1. Допустимое множество решений задачи ЛП либо пусто, либо является выпуклым многогранником в Rn (как пересечение полупространств, описываемых ограничениями-неравенствами). Оно может быть, как ограниченным, так и неограниченным; в любом случае это замкнутый многогранник.
  2. Если допустимое множество не пусто, а целевая функция ограничена сверху (для задачи максимизации, а для задачи минимизации - ограничена снизу) на этом множестве, то задача ЛП имеет оптимальное решение.
  3. Оптимальные решения задачи ЛП (если они существуют) всегда находятся на границе допустимого множества. Точнее, если существует единственное оптимальное решение, то им является какая-либо вершина многогранника допустимых решений; если две или несколько вершин являются оптимальными решениями, то любая также является оптимальным решением (т.е. существует бесконечно много точек максимума или минимума).

 


1 | 2 | 3 | 4 |

Поиск по сайту:



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