Студопедия  
Главная страница | Контакты | Случайная страница

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

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

Читайте также:
  1. A. гностическим методам
  2. C. Ветвящихся алгоритмов
  3. CТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ
  4. I. ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
  5. II. Для решения следующих задач используйте формулы для сочетаний
  6. II. Обоснование целесообразности решения проблемы программно-целевым методом
  7. III. Алгоритмическая конструкция ветвление и ее использование в языке Visual Basic
  8. III. Порядок производства и решения дел
  9. IV. Алгоритмическая конструкция цикл и ее использование в языке Visual Basic
  10. IV[17]. КАК ИЗУЧАТЬ? АЛГОРИТМ ДЕЯТЕЛЬНОСТИ

1. По ограничениям задачи строится область допустимых решений (ОДР). Каждому неравенству на плоскости соответствует полуплоскость, каждому уравнению соответствует прямая, ОДР будет пересечением построенных полуплоскостей. Возможны несколько вариантов ОДР (замкнутая область, неограниченная область, пустое множество). Если ОДР – пустое множество, то задача не имеет решения. Если ОДР не пусто, то переходим к шагу 2.

 

2. Строим вектор градиента с координатами начала (0,0) и конца (с1,с2),
где с1, с2 - коэффициенты целевой функции.

 

3. Строим линию уровня целевой функции. Линия уровня целевой функции в данной ЗЛП – прямая, перпендикулярная вектору градиента.

 

4. Определяем те точки ОДР, которые визуально наиболее соответствуют оптимальному решению. При этом, если задача на максимум, то линию уровня целевой функции перемещаем параллельно самой себе в направлении градиента до самой “дальней” точки (точек) ОДР. Если же задача на минимум, то линию уровня перемещаем в противоположном градиенту направлении.

 

5. Если очевидно, что некоторая угловая точка с координатами (x1,x2) является единственной кандидатурой на оптимальное решение, то находим эти координаты и подставляем их в целевую функцию. Если же таких точек несколько, то требуется сравнение значений целевой функции в этих точках. Для каждой точки составляем систему двух линейных уравнений. которые соответствуют прямым, задающим данные точки. Полученные решения подставляются в целевую функцию. В качестве оптимальной выбирается та точка, для которой значение целевой функции лучше.
Решение ЗЛП записываем в виде: x1, x2 и F(x1,x2)=c1*x1+c2*x2.

 

Замечание. Возможны несколько вариантов решений: оптимальное решение единственное (см. рис.), решений множество, целевая функция неограниченна.

 

Х2


C(х1,х2)

Пример ОДР,

которую фор- B

мируют 6

ограничений, D

включая 2

тривиальных:

x1³0, x2³0.

ОДР имеет 6

угловых точек: A

A,B,C,D,E,F (c1,c2) Х1

F E



Дата добавления: 2015-01-12; просмотров: 9 | Нарушение авторских прав

<== предыдущая лекция | следующая лекция ==>
Статья 2.| Часть первая

lektsii.net - Лекции.Нет - 2014-2021 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав