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

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

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

 

Пример 2.3

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

 

х₁ + 3х₂ ≤ 21

3х₁ + 2х₂ ≤ 21

3х₁ + х₂ ≤ 18

х₁; х₂ ≥ 0

 

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

Решение.

 

 

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

Х1
Х2

1) х₁ + 3х₂ = 21

 

 

Х1
Х2	10,5

2) 3х₁ + 2х₂ = 21

 

Х1
Х2

3) 3х₁ + х₂ = 18

 

 

4) х₁ = 0

5) х₂ = 0

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

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

 

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

 

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

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

х₁ + 3х₂ = 21 х₁ = 3; х₂ = 6

3х₁ + 2х₂ = 21

 

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

При минимизации F = 30 х₁ + 60 х₂ линию уровня необходимо смещать параллельно самой себе в направлении противоположном вектору 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-число переменных). Решение системы Х(х₁, х₂…х_n) называется допустимым, если оно содержит лишь неотрицательные компоненты, в противном случае решение называется недопустимым. Базисным решением системы m уравнений с n неизвестными называется решение в котором все (n – m) переменных равны 0. Допустимое базисное решение иначе называется опорным планом.

Пример 2.4.

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

х₁ – х₂ – 2х₃ + х₄ = 0

2 х₁ + х₂ + 2х₃ – х₄ = 2

 

Общее число групп основных переменных: - X₁X₂, X₁X₃, X₁X₄, X₂X₃, X₂X₄, X₃X₄.

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

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

׀ 2 1 ׀

то X₁X₂ – основные переменные

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

Группы X₂X₃, X₂X₄, X₃X₄ не могут быть основными, т.к. их определители = 0

 

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

1) Для основных переменных X₁X₂ и не основных X₃X₄

(X₃= X₄ = 0)

Х₁-Х₂=0 X₁ = ⅔

2Х₁+Х₂=2 X₂ = ⅔

 

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

2) Для основных переменных X₁X₃ и неосновных X₂ = X₄ = 0

X₁ = ⅔ X₃ = ⅓

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

3) Для основных переменных X₁ X₄ и неосновных X₂ = X₃ = 0

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

 

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

 

 

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

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

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

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

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

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

 

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

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

 

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

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

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

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

 

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

Пример 2.5.

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

z=18 y₁+16y₂+5y₃+21y₄ →min

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

y₁+2y₂+3y₄≥2

3y₁+y₂+y₃≥3

y₁, y₂, y₃, y₄≥0

Шаг 1:

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

 

y₁+2y₂+3y₄-y₅=2

3y₁+y₂+y₃-y₆=3

 

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

y₁=y₂=y₃=y₄=0, => y₅=-2; y₆=-3.

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

 

Шаг 2:

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

0 3 ≠0

1 0

 

y₃, y₄ - основные переменные.

y₁=y₂=y₆=y₅=0 неосновные переменные;

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

y₃=3-3y₁-y₂+y₆

y₄=2/3-y₁/3-2/3y₂+y₅/3

y₃=3, y₄=2/3;

 

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

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

z=18y₁+16y₂+5(3-3y₁+y₆-y₂)+21(2/3-y₁/3-2/3y₂+y₅/3)= 29-4y₁-3y₂+7y₅+5y₆

Критерии оптимальности не выполняются, т.к. имеются отрицательные коэффициенты при y₁ и y₂, поэтому Z₁ =29 – не является минимальным.

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

Шаг 3:

y₁, y₄ - основные переменные.

y₂, y₃, y₅, y₆=0 – неосновные переменные;

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

y₁=1- 1 y₂ - 1 у₃+ 1 у₆;

3 3 3

y₄= 1 - 5 у₂+ 1 у₃+ 1 у₅- 1 у₆;

3 9 9 3 9

z=25- 5 y₂+ 1 у₃+ 1 у₅- 1 у₆;

3 9 3 9

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

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

 

Шаг 4:

y₁,y₃ – основные переменные.

y₃, y₄, y₅, y₆=0 – неосновные переменные.

у₁= 4 - 2 у₃+ 5 у₄- 1 у₅+ 2 у₆

5 3 3 5 5

y₂= 3 + 1 у₃- 9 у₄+ 3 у₅- 1 у₆

5 5 5 5 5

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

z=24+y₃+3y₄+6y₅+4y₆→min

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

Z(y₄)=24=min