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

Элементы теории. Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными

Читайте также:
  1. D – элементы
  2. I. МЕХАНИКА И ЭЛЕМЕНТЫ СПЕЦИАЛЬНОЙ ТЕОРИИ ОТНОСИТЕЛЬНОСТИ
  3. III. Несущие элементы покрытия.
  4. S-элементы I и II групп периодической системы Д.И.Менделеева.
  5. V. ЭЛЕМЕНТЫ ФИЗИКИ АТОМА
  6. XII. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ
  7. А. Понятие и элементы договора возмездного оказания услуг
  8. А. Понятие и элементы комиссии
  9. А. Понятие и элементы простого товарищества
  10. Актеры и элементы Use Case
  11. Архитектурная композиция и ее элементы
  12. Архитектурно-конструктивные элементы стен

Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и целевой функции (ЦФ) задачи.

Каждое из неравенств задачи линейного программирования определяет на координатной плоскости некоторую полуплоскость, а система неравенств в целом – пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклуюфигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи ОДР является пустым множеством.

Все вышесказанное относится и к случаю, когда система ограничений включает равенства. ЦФ при фиксированном значении представляет на плоскости прямую линию. Изменяя значения целевой функции L, получим семейство параллельных прямых, называемых линиями уровня.

Это связано с тем, что изменение значения L повлечет изменение лишь длины отрезка, отсекаемого линией уровня на осях координат, а угловой коэффициент прямой останется постоянным. Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L.

Вектор с координатами из коэффициентов ЦФ перпендикулярен к каждой из линий уровня. Направление вектора совпадает с направлениемвозрастания ЦФ, что является важным моментом для решения задач. Направлениеубывания ЦФ противоположно направлению вектора.

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

При поиске оптимального решения задач линейного программирования возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений – единственная точка; задача не имеет решений.



 

В рассматриваемом примере содержатся только две переменные x1 и x2, поэтому задачу можно решить графически.

1) На плоскости x1, x2 строим область допустимых значений переменных, определяемую ограничениями задачи:

 

x1 + 2x2 3 (А)

3x1 + 1x2 3 (Б)

x1 , x2 0 .

 

Последнее ограничение определяет первый квадрант плоскости. Чтобы построить множество точек удовлетворяющих неравенству (А), нанесем на плоскость график прямой, определяющий границу этого множества: x1 + 2x2 = 3 (Б).

Приведем это уравнение к виду: . А это уравнение прямой «в отрезках» и для построения этой прямой используются две точки (a , 0) и (0 , b). (рис. 1.1)

 

Рис. 1.1

Запишем уравнение границы допустимой области из неравенства (А):

.

 

Аналогично, из неравенства (Б) получим уравнение второй границы:

 

Построим обе прямые на плоскости. Множества точек, удовлетворяющие неравенствам (А) и (Б) будут полуплоскости, лежащие под соответствующими прямыми, а множество допустимых значений переменных будет пересечением (общей частью) этих полуплоскостей, лежащее в первом квадранте: четырехугольник ABCD (рис. 1.2).

Рис. 1.2.

 

2) На множестве допустимых решений (ABCD) найдем точку, в которой целевая функция Z = 2x1 + x2 имеет максимальное значение. Для этого посмотрим линии уровня целевой функции. Линией уровня называется множество точек, на которых функция принимает постоянное значение:

 

Z = 2x1 + x2 = К,

 

где К - задаваемая постоянная.

При К = 1 уравнение линии уровня будет:

 

2x1 + x2 = 1.

или (в отрезках) : .

При К = 2, аналогично:

 

2x1 + x2 = 2 ,

 

или .

 

Нанеся линии уровня на область допустимых решений (рис. 1.3), получим, что при увеличении значения Z соответствующая линия уровня перемещается параллельно предыдущей вправо и вверх. Таким образом, точкой из многоугольника ABCD, в которой целевая функция Z имеет максимальное значение, будет вершина С. Эта точка и определяет решение задачи.

‡агрузка...

Рис. 1.3.

 

3) Вычисление координат оптимальной точки (С).

 

Точка C лежит на пересечении прямых (А) и (Б), поэтому, чтобы определить ее координаты надо решить систему уравнений:

 

x1 + 2x2 = 3 (А)

3x1 + x2 = 3 (Б)

Решение:

x1* = 0,6 ; x2* = 1,2 ;

 

максимальное значение Z:

 

Z* = 2·0,6 + 1,2 = 2,4.

Задание 2. Решение задачи ЛП в симплекс-таблицах.


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


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