Геометрическая интерпретация решения ЗЛП. 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Геометрическая интерпретация решения ЗЛП.



Графический метод решения ЗЛП состоит из следующих этапов:

  1. На координатной плоскости Х1ОХ2 строится область допустимых решений (ОДР). Она представляет собой многоугольник, стороны которого лежат на прямых, получаемых из системы ограничений задачи.
  2. Строится вектор нормали q = (С12) целевой функции (он указывает на направление возрастания целевой функции).
  3. Строятся нижние и верхние опорные прямые, т.е. крайние линии уровня целевой функции, имеющие общие точки с ОДР. (Путем параллельного перемещения опорной прямой в направлении вектора нормали q).
  4. Определяются координаты экстремальных точек и вычисляются значения целевой функции в них.

 

Пример 2.3

Решить графическим методом следующую задачу:

 

х1 + 3х2 ≤ 21

1 + 2х2 ≤ 21

1 + х2 ≤ 18

х1; х2 ≥ 0

 

Определить при каких х1 и х2 функция F = 30х1 +60х2 → max

Решение.

 

 

  1. Область допустимых решений построим следующим образом. Постоим прямые с уравнениями
Х1    
Х2    

1) х1 + 3х2 = 21

 

 

Х1    
Х2 10,5  

2) 3х1 + 2х2 = 21

 

Х1    
Х2    

3) 3х1 + х2 = 18

 

 

4) х1 = 0

5) х2 = 0

Прямые пронумерованы, а рядом с соответствующим уравнением приведены координаты двух точек, через которые проходят прямые.

В результате получим выпуклый пятиугольник ОАВСD.

 

2. Строим нормальный вектор q = (30;60)/ 3, уменьшив значение координат в 3 раза. Прямая с уравнением 30 х1 + 60 х2 = 0 представляет собой «нулевую» линию уровня целевой функции. Эта прямая проходит через начало координат и перпендикулярна нормальному вектору q. Передвигаем эту прямую параллельно себе по вектору q и фиксируем ее крайнее положение (т.В).

 

3. Определим координаты точки В, которая принадлежит прямым 1) и 2).

Составляется система уравнений:

х1 + 3х2 = 21 х1 = 3; х2 = 6

1 + 2х2 = 21

 

Тогда F max =30∙3 + 60∙6 = 450

При минимизации F = 30 х1 + 60 х2 линию уровня необходимо смещать параллельно самой себе в направлении противоположном вектору q. Минимум функции достигается в точке О(0;0).

Тогда F min = 0.

 

К достоинствам геометрического метода решения ЗЛП относятся:

- наглядность;

- быстрота и легкость нахождения ответа.

 

К недостаткам геометрического метода относятся:

- возможны «технические» погрешности при приближенном построении графиков;

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

- этот метод легко применим, когда число переменных в стандартной задаче не превышает двух.

Выполнить самостоятельно.

ЗАДАНИЕ №1.

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

 

ТАБЛИЦА №1

  0,1,2 3,4,5,6 7,8,9
  f(x)=3x1-2x2; 2x1+x2≤2; x1+2x2≤2; x1,x2≥0; f(x)=4x1+8x2; x1+x2≤3; x1+2x2≤2; x1,x2≥0; f(x)=-4x1+8x2; 3x1+5x2≤15; x1-x3≤1; x1,x2≥0;
  f(x)=3x1-2x2; -x1+2x2≤2; 2x1-x2≤2; x1,x2≥0; f(x)=-x1+6x2; 4x1+3x2≤12; -x1+x2≤1; x1,x2≥0; f(x)=-x1+6x2; x1+x2≤3; -2x1+x2≤2; x1,x2≥0;
  f(x)=x1+6x2; 3x1+4x2≤12; -x1+x2≤2; x1,x2≥0; f(x)=2x1+6x2; 3x1+4x2≤12; x1+2x2≤2; x1,x2≥0; f(x)=8x1+12x2; 2x1+x2≤4; 2x1+5x2≤10; x1,x2≥0;
  f(x)=8x1+12x2; -3x1+2x2≤0; 4x1+3x2≤12; x1,x2≥0; f(x)=3x1-2x2; 2x1+x2≤2; 2x1+3x2≤6; x1,x2≥0; f(x)=6x1+4x2; x1+2x2≤2; -2x1+x2≤0; x1,x2≥0;
  f(x)=6x1+4x2; 3x1+2x2≤6; 3x1+x2≤3; x1,x2≥0; f(x)=8x1+6x2; -x1+x2≤1; 3x1+2x2≤6; x1,x2≥0; f(x)=8x1+6x2; -x1+x2≤2; 3x1+4x2≤12; x1,x2≥0;

 

2.5 Элементы линейной алгебры.

Любые m переменных системы уравнений с n переменными, где m < n называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля. Тогда остальные n – m переменных называются неосновными (или свободными). Основными могут быть разные группы из n переменных. Максимальное число групп основных переменных равно числу сочетаний (где m-число уравнений, а n-число переменных). Решение системы Х(х1, х2…хn) называется допустимым, если оно содержит лишь неотрицательные компоненты, в противном случае решение называется недопустимым. Базисным решением системы m уравнений с n неизвестными называется решение в котором все (n – m) переменных равны 0. Допустимое базисное решение иначе называется опорным планом.

Пример 2.4.

Решить систему уравнений

х1 – х2 – 2х3 + х4 = 0

2 х1 + х2 + 2х3 – х4 = 2

 

Общее число групп основных переменных: - X1X2, X1X3, X1X4, X2X3, X2X4, X3X4.

Выясним, могут ли быть основными переменные X1X2 , т.к. определитель матрицы из коэффициентов

׀ 1 -1 ׀ = 1•1 – 2•(-1) ≠ 0,

׀ 2 1 ׀

то X1X2 – основные переменные

Аналогично основным можно отнести X1X3; X1X4 (у них определители ≠ 0)

Группы X2X3, X2X4, X3X4 не могут быть основными, т.к. их определители = 0

 

Таким образом система уравнений имеет 3 базисных решения:

1) Для основных переменных X1X2 и не основных X3X4

(X3= X4 = 0)


Х12=0 X1 = ⅔

12=2 X2 = ⅔

 

Таким образом, базисное решение: X = (⅔, ⅔, 0, 0) – допустимое решение;

2) Для основных переменных X1X3 и неосновных X2 = X4 = 0

X1 = ⅔ X3 = ⅓

Базисное решение: X2 = (⅔, 0, ⅓, 0). Оно тоже допустимое.

3) Для основных переменных X1 X4 и неосновных X2 = X3 = 0

Базисное решение X3 (⅔, 0, 0, -⅔) – недопустимое.

 

2.6 Симплекс-метод (СМ) решения ЗЛП

 

 

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

В настоящее время СМ используется для компьютерных расчетов, однако не сложные методы можно решать и вручную.

Для реализации СМ необходимо знать 3 основных элемента:

1. способ определения первоначального допустимого базисного решения;

2. правило перехода к лучшему решению;

3. проверка признака оптимальности решении, который состоит в следующем:

 

- если в выражении целевой функции отсутствуют положительные коэффициенты при неосновных переменных, то решение максимально;

- если отсутствуют отрицательные коэффициенты, то решение минимально.

 

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

Достаточно ввести дополнительные неотрицательные переменные с учетом правила определения знака дополнительных переменных:

Знак «+», если неравенство вида ≤;

Знак «-», если неравенство вида ≥.

 

Алгоритм вычислительной реализации этих трех элементов рассмотрим на следующем примере.

Пример 2.5.

Решить задачу симплексным методом:

z=18 y1+16y2+5y3+21y4 →min

при ограничениях:

y1+2y2+3y4≥2

3y1+y2+y3≥3

y1, y2, y3, y4≥0

Шаг 1:

Введем дополнительные переменные y5, y6 со знаком «-», т. к. «≥» получим систему уравнений в канонической форме:

 

y1+2y2+3y4-y5=2

3y1+y2+y3-y6=3

 

Если на первом шаге в качестве основных переменных взять дополнительные переменные y5, y6, тогда:

y1=y2=y3=y4=0, => y5=-2; y6=-3.

У1=(0,0,0,0,-2,-3) – недопустимое базисное решение.

 

Шаг 2:

В данном случае в качестве основных удобно взять переменные y3, y4 в соответствии с правилом выбора основных переменных, сформулированным выше.

0 3 ≠0

1 0

 

y3, y4 - основные переменные.

y1=y2=y6=y5=0 неосновные переменные;

Выразим основные переменные через неосновные:

y3=3-3y1-y2+y6

y4=2/3-y1/3-2/3y2+y5/3

y3=3, y4=2/3;

 

Базисное решение У2=(0,0,3,2/3,0,0) – допустимое решение.

Выражаем линейную функцию через неосновные переменные:

z=18y1+16y2+5(3-3y1+y6-y2)+21(2/3-y1/3-2/3y2+y5/3)= 29-4y1-3y2+7y5+5y6

Критерии оптимальности не выполняются, т.к. имеются отрицательные коэффициенты при y1 и y2, поэтому Z1 =29 – не является минимальным.

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

Шаг 3:

y1, y4 - основные переменные.

y2, y3, y5, y6=0 – неосновные переменные;

После преобразований:

y1=1- 1 y2 - 1 у3+ 1 у6;

3 3 3

y4= 1 - 5 у2+ 1 у3+ 1 у5- 1 у6;

3 9 9 3 9

z=25- 5 y2+ 1 у3+ 1 у5- 1 у6;

3 9 3 9

y3=(1;0;0;1/3;0;0) – допустимое базисное решение.

Z(y3)=25 – не является min, так как имеется отрицательный коэффициент при y2, поэтому переменную y2 переводим в основную.

 

Шаг 4:

y1,y3 – основные переменные.

y3, y4, y5, y6=0 – неосновные переменные.

у1= 4 - 2 у3+ 5 у4- 1 у5+ 2 у6

5 3 3 5 5

y2= 3 + 1 у3- 9 у4+ 3 у5- 1 у6

5 5 5 5 5

y3= (4/5;3/5;0;0;0;0) – допустимое базисное решение

z=24+y3+3y4+6y5+4y6→min

Решение оптимальное, так как в выражении нет отрицательных коэффициентов при неосновных переменных.

Z(y4)=24=min

 



Поделиться:


Последнее изменение этой страницы: 2017-02-17; просмотров: 151; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.224.52.210 (0.189 с.)