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

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

Геометрическая интерпретация и графическое решение задач линейного программирования

Читайте также:
  1. D1. Задача
  2. E) задачи на вычисление боковой поверхности геометрических фигур
  3. E)задачина вычисление боковой поверхности геометрических фигур 1 страница
  4. E)задачина вычисление боковой поверхности геометрических фигур 2 страница
  5. E)задачина вычисление боковой поверхности геометрических фигур 3 страница
  6. E)задачина вычисление боковой поверхности геометрических фигур 4 страница
  7. GІІ.Излагаете проблему группе. Вместе со всеми вырабатываете решение на основе консенсуса. Выполняете любое решение группы.
  8. I Задачи научно-исследовательской деятельности учащихся.
  9. I Цели и задачи изучения дисциплины
  10. I этап. Постановка задачи

 

 

Для случая 2-х переменных (факторов) задача линейного программирования имеет простую геометрическую интерпретацию, но такие задачи не имеют практического значения.

Фактически пусть имеем задачу ЛП

max (min) z =c1 x1+ c2 x2 (1)

 

a11x1+a12x2 ≤b1;

a21x2+a22x2 ≤b2;

… … … (2)

am1x1+am2 x2 ≤bm

 

x1,x2≥0 (3)

 

Система ограничений (2) определяет область допустимых решений задачи линейного программирования (область допустимых планов Ω). Область называется выпуклой, если любые 2 точки этой области могут быть соединены отрезком прямой, все точки которой принадлежат этой области.

 

x2

 

 

 

 


x1

 

 


Вся плоскость является выпуклым множеством.

Полуплоскость также является выпуклым множеством.

 

Известно, что пересечение любого числа выпуклых множеств есть множество выпуклое. След., область допустимых планов задачи линейного программирования является выпуклым множеством (как пересечение полуплоскостей, определяемых каждым ограничением-неравенством.

При этом могут встретится следующие случаи:

 

  а) x2     Ω           x1   в) x2       x1   д) x2       x1   б) x2     Ω   x1   г) x2       x1   е) x2   Ω         x1

z=c1x1+c2x2

z=z0

MN – линия постоянного уровня

 

c1x1+c2x2=Z0

Z(L)=Z(M)=Z(N)=Z0

=(c1c2)= f {c1;c2} – указывает, направление наибольшего возрастания функции Z.

c1x1+c22=0 – определяет линию нулевого уровня (прямая проходит через начало координат)

 

 

 


x2

M

 


L

Zmax

N

 

 


Zmin x1

 

 

Z0

 

 

Т. о., из этой геометрической иллюстрации следует, что целевая функция задачи линейного программирования достигает своих экстремумов на границе области допустимых планов. Обобщая эту задачу на случай n переменных, приходим к n – мерному пространству, где роль прямых играют гиперплоскости. Выпуклый многоугольник – выпуклый многогранник. Прямая уровня – «гиперплоскость». И также, как и в двумерной плоскости, целевая функция достигает своего экстремального значения на границе области допустимых планов.

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

Введем понятие выпуклой, линейной комбинации точек.

 

Пусть рассматривается n векторов, x1, x2,…, xn. Тогда выпуклой линейной комбинацией этих векторов (точек) называется множество x


x =λ1 x1+ λ2 x2+…+ λn xn, 0≤ λi ≤ 1,i=1,n, где

и все , удовлетворяют условию 0 .

x2

 


x2

 


x1

x1 x3

 

Основная теорема линейного программирования:

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


 




Дата добавления: 2015-01-05; просмотров: 30 | Поможем написать вашу работу | Нарушение авторских прав




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