Симплекс-метод

Размещено на http://www.allbest.ru/

Симплекс-метод

1. Идея симплекс-метода

Рассмотрим универсальный метод решения канонической задачи ЛП.

, , ,

известный как симплекс-метод.

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

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

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

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

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

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

Общая схема симплекс-метода состоит из следующих основных шагов.

· 0 шаг. Определение начального базиса  и соответствующей ему начальной угловой точки (базисного плана) .

· 1 шаг. Проверка текущего базисного плана на оптимальность. Если критерий оптимальности выполнен, то план оптимален и решение закончено. Иначе переход на шаг 2.

· 2 шаг. Нахождение переменной, вводимой в состав базисных. (Из условия увеличения целевой функции).

· 3 шаг. Нахождение переменной, исключаемой из состава базисных переменных (Из условия сохранения ограничений задачи).

· 4 шаг. Нахождение координат нового базисного плана (смежной угловой точки). Переход на шаг 1.

Повторяющиеся шаги 1-4 образуют одну итерацию симплекс-метода.

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

Определение. Будем говорить, что каноническая задача ЛП имеет «предпочтительный вид», если

1. правые части уравнений , .

2. матрица условий содержит единичную подматрицу размера 

.

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

Пример.

Матрица условий  и вектор правых частей ограничений имеют вид

, .

Сразу очевидна одна базисная матрица: с единичными векторами

.

Следовательно , , - базисные переменные, а x_2, x₄ - небазисные. Полагая в системе уравнений x₂=x₄ =0, немедленно находим x₁ =10, x₃ =20, x₅ =8. Видим, что значения базисных переменных равны правым частям ограничений. Из этого понятно требование положительности правых частей b_i.

В дальнейшем, базисные переменные будем объединять в вектор x_Б.

Таким образом, в канонической задаче предпочтительного вида в качестве начальной базисной матрицы берется единичная подматрица A_Б =E, а соответствующие ей базисные переменные равны правым частям ограничений: x_Б =b.

2. Простейшая реализация симплекс-метода

Простейшая реализация симплекс-метода («простой С-метод») применяется к канонической задаче ЛП, имеющей «предпочтительный вид». Не умаляя общности, будем считать, что единичная подматрица содержится в первых m столбцах. Тогда каноническая задача запишется следующим образом

f(x) = c1x1 + c2x2 +… + cmxm + cm+1xm+1 +… + cnxn ??max	(3.1)
x1 + a1m+1 xm+1 + … + a1n xn = b1	(3.2)
x2 + a2m+1 xm+1 + … + a2n xn = b2
………………………………………………………….
xm + amm+1 xm+1 + … + amn xn = bm
xj і--0, j=1,2,…, n.	(3.3)

Матрица условий

содержит единичную подматрицу размера m x m в первых m столбцах, следовательно A_Б ={A₁, A_2,…, A_m}=E.

Основные шаги симплекс-метода (теория)

Поскольку единичная базисная матрица находится в первых m столбцах матрицы условий, то первые m координат начального базисного плана являются базисными, а последние n - m координат являются небазисными, то есть равны нулю:

x^o = (x₁, x₂,…, x_m, 0,…, 0).

Подставляя координаты точки x^o в ограничения (3.2) и учитывая, что

x_m+1 =… = x_n = 0, получаем: x₁ = b₁, x₂ = b₂,…, x_m = b_m, то есть x^o_Б = b.

Значит начальный базисный план имеет вид:

x^o = (b₁,…, b_m, 0,…, 0),

где с_Б = (с₁,…, с_m) - вектор, составленный из коэффициентов целевой функции при базисных переменных.

1 шаг. Проверка базисного плана на оптимальность.

Из системы ограничений (3.2) выразим базисные переменные через небазисные:

x1= b1 - a1m+1xm+1 - … - a1nxn, x2 = b2 - a2m+1xm+1 - … - a2nxn, ………………………………………… xm = bm - amm+1xm+1 - … - amnxn,	(3.4)

Подставим эти выражения в целевую функцию (3.1).

f (x) = c₁ (b₁ - a_1m+1x_m+1 - … - a_1nx_n) + c₂ (b₂ - a_2m+1x_m+1 - … - a_2nx_n) +

………………………………………………..

+ c_m (b_m - a_mm+1x_m+1 - … - a_mnx_n) + c_m+1x_m+1 +… + c_nx_n.

Сгруппируем слагаемые при одинаковых небазисных переменных:

f (x) = - (c1 a1m+1 + c2 a2m+1 + … + cm amm+1 - cm+1). xm+1 - …- - (c1 a1n + c2 a2n + … + cm amn - cn). xn.	(3.5)

Заметим, что выражения в круглых скобках можно записать в виде

c₁ a_1m+1 + c₂ a_2m+1 + … + c_m a_mm+1 - c_m+1 = < c_Б, A_m+1 > - c_m+1 =--D_m+1,

_{…………………………………………………………………………………………………………………………}

c₁ a_1n + c₂ a_2n + … + c_m a_mn - c_{n =} < c_Б, A_n > - c_n =--D_n,

где с_Б = (с₁,…, с_m) - вектор, составленный из коэффициентов целевой функции при базисных переменных, A_m+1,…, A_n - столбцы матрицы условий А при небазисных переменных x_m+1,…, x_n.

Выражения

D--j = < сБ, Aj > - cj, j = m+1,…, n,	(3.6)

называются симплексными разностями или симплексными оценками базисного плана.

С учетом (3.6), формулу (3.5) для целевой функции можно переписать в виде

.

Эта формула позволяет получить признак оптимальности базисного плана. Если все симплексные оценки с небазисными номерами D--_j і--0, то текущий базисный план - оптимален.

Действительно, если хотя бы одна оценка, например, ?_k строго отрицательна, то придавая соответствующей небазисной переменной x_k положительное значение, а остальные небазисные переменные плана x полагая равными нулю, получим

f (x) = f (xo) - Dk xk = f (xo) + | D--k | xk > f (xo),	(3.7)

то есть в этом случае план x^o может быть улучшен.

Легко проверить, что симплексные оценки, соответствующие единичным базисным столбцам всегда равны 0.

2 шаг. Нахождение переменной вводимой в состав базисных переменных.

Как следует из формулы (3.7), целевую функцию можно увеличить, если ввести в состав базисных переменных (сделать положительной) небазисную переменную x_j, которой соответствует отрицательная оценка ?_j < 0. Если таких оценок несколько, то обычно в состав базисных вводят небазисную переменную х_к с наибольшей по модулю отрицательной оценкой, то есть такую, для которой

,

где D--_j = < C_Б, A_j > - c_j, j = m+1,…, n (номера небазисных переменных).

Таким образом мы получим новый план

x¹ = (x₁,…, x_m,0,…, x_k,…, 0,…, 0).

Но х¹ - небазисный план, так как число положительных координат равно m+1, число нулевых координат равно n - m -1.

Чтобы получить новую угловую точку, занулим одну из базисных переменных, то есть выведем одну переменную из состава базисных.

3 шаг. Определение переменной выводимой из базиса.

Подставим координаты точки х¹ в условия (3.4) и учтем, что переменные x_j должны быть неотрицательны

x1 = b1 - a1kxk і--0 x2 = b2 - a2kxk і--0 …………………………. xm = bm - amkxk і--0	(3.8)

Из формулы (3.7) видно, что чем больше величина х_к > 0, тем больше возрастает целевая функция. Постараемся найти максимальное значение х_к, не нарушая ограничений задачи и выполняя условия неотрицательности (3.8).

Неравенства (3.8) можно переписать в виде

A1kxk Ј b1 a2kxk Ј b2 ……………… amkxk Ј bm	(3.9)

При решении системы неравенств (3.9) возможны два случая:

a) среди коэффициентов при х_к нет положительных: a_ik Ј--0, i=1,2,…, m. Так как b_i >--0, то неравенства (3.9) выполняются при любом сколь угодно большом значении х_к. Это говорит о том, что целевая функция не ограничена на множестве планов (max f(x) ®--Ґ) и следовательно, решения задачи ЛП не существует.

b) среди коэффициентов при х_к есть положительные a_ik > 0. Решая систему неравенств (3.9) получим:

хк Ј--bi /aik, для всех i, для которых aik > 0.	(3.10)

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

х_к = min {b_i /a_ik} по всем i: a_ik > 0.

Пусть минимум достигается при i = r, то есть х_к ? b_r /a_rk. Это означает, что базисная переменная х_r в условиях (3.8) обращается в нуль.

х_r = b_r - a_rk x_k = b_r - a_rk (b_r /a_rk) = 0, 1 ??r ??m.

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

4 шаг. Определение координат нового базисного плана.

Новый базисный план будет иметь вид

x¹ = (x₁, x₂,…, 0,…, x_m, 0,…, х_k,0,…, 0),

где на месте х_r стоит ноль, а х_к > 0. тому базисному плану соответствует новая базисная матрица:

Для нахождения координат новой угловой точки х¹ каноническая задача ЛП приводится к новому предпочтительному виду, то есть к такой форме, чтобы матрица стала единичной (= E). Для этого столбец А_k нужно преобразовать к единичному представлению,

- r-я строка,

в котором коэффициент = 1, а все остальные элементы =0, i ??r. Этого можно добиться с помощью элементарных операций над уравнениями системы. Решение заканчивается тогда, когда для некоторой точки все оценки D_j і--0.

3. Реализация симплекс-метода на примере

Продемонстрируем применение симплекс-метода на примере из главы 2.

Рассмотрим каноническую задачу ЛП

f(x) = x1+ 2x2 +0 x3 + 0 x4 max	(3.11)
-x1+ 2x2+ x3 = 4,	(3.12)
3 x1 +2x2 + x4 = 12,	(3.13)
xj ? 0, j = 1,2,3,4.	(3.14)

Матрица условий A = (A₁, A₂, A₃, A₄), где

, , , .

Целевой вектор c =(c₁, c₂, c₃, c₄)=(1, 2, 0, 0); вектор правых частей b=(b₁, b₂) = (4, 12).

0 шаг. Нахождение начальной угловой точки (базисного плана).

Задача имеет предпочтительный вид, так как правые части уравнений положительны, а столбцы матрицы условий A_3, A₄ образуют единичную подматрицу. Значит начальная базисная матрица = (A₃, A₄); x₃ и x₄ - базисные переменные, x₁ и x₂ - небазисные переменные, c_Б = (c_3, c₄₎ = (0, 0).

Начальный базисный план имеет вид

x⁰ = (0, 0, x₃, x₄₎ = (0, 0, 4, 12); f(x^o) = 0.

1 шаг. Проверка базисного плана на оптимальность.

Подсчитаем симплексные оценки для небазисных переменных по формуле (3.6)

D₁ = < c_Б, A₁ > - c₁ = 0 ·(-1) + 0 ·3 - 1 = -1.

D₂ = < c_Б, A₂ > - c₂ = 0 ·2 + 0 · 2 - 2 = -2.

Так как оценки отрицательны, то план x^o - не оптимален. Будем искать новый базисный план (смежную угловую точку) с большим значением целевой функции.

2 шаг. Нахождение переменной вводимой в базис.

Целевую функцию можно увеличить, если ввести в состав базисных переменных (сделать положительной) одну из небазисных переменных x₁ или x₂, поскольку обе оценки D_j < 0. Обычно в состав базисных вводят небазисную переменную с наибольшей по модулю отрицательной оценкой, поэтому будем вводить в базис переменную x_2.

3 шаг. Определение переменной выводимой из базиса.

После ввода в базис переменной x₂ новый план будет иметь вид

x¹ = (0, x_2, x₃, x₄).

Этот план не является базисным, так как он содержит только одну нулевую координату, значит надо сделать нулевой (исключить из базиса) одну из переменных x₃ или x₄.

Подставим координаты плана x¹ = (0, x_2, x₃, x₄) в ограничения задачи. Получим

2x₂+ x₃ = 4,

2x₂ + x₄ = 12.

Выразим отсюда базисные переменные x₃ и x₄ через переменную x₂, вводимую в базис.

x3 = 4 - 2x2,	(3.15)
x4 = 12 - 2x2.	(3.16)

Так переменные x₃ и x₄ должны быть неотрицательны, получим систему неравенств

4 - 2x2 і--_,	(3.17)
12 - 2x2 --і--_.	(3.18)

Чем больше значение x₂, тем больше возрастает целевая функция. Найдем максимальное значение новой базисной переменной, не нарушающее ограничения задачи, то есть удовлетворяющее условиям (3.17), (3.18).

Перепишем неравенства в виде

2x₂ Ј--4,

2x₂ Ј12,

откуда максимальное значение x₂ = min {4/2, 12/2} = 2. Подставляя это значение в выражения (3.15), (3.16) для x₃ и x₄, получаем x₃ = 0. Следовательно x₃ выводится из базиса.

4 шаг. Определение координат нового базисного плана.

Новый базисный план (смежная угловая точка) имеет вид

x¹ = (0, x_2, 0, x₄₎.

Базис этой точки состоит из столбцов A₂ и A₄, так что = (A_2, A₄). Заметим, что этот базис не является единичным, так как вектор A₂ = (2, 2), и следовательно задача (3.11) - (3.14) не имеет предпочтительного вида относительно нового базиса. Преобразуем условия задачи (3.12), (3.13) таким образом, чтобы она приняла предпочтительный вид относительно новых базисных переменных x_2, x_4, то есть чтобы переменная x₂ входила в первое уравнение с коэффициентом, равным единице, и не присутствовала во втором уравнении. Перепишем уравнения задачи

- x₁+ 2x₂+ x₃ = 4, (p₁₎

3x₁ +2x₂ + x₄ = 12. (p₂₎

Поделим первое уравнение на коэффициент при x₂. Получим новое уравнение = p₁ / 2, эквивалентное исходному

- 1/2 x₁+ x₂+ 1/2 x₃ = 2. ()

Используем это уравнение, которое назовем разрешающим, для исключения переменной x₂ из второго уравнения. Для этого надо уравнение умножить на 2 и вычесть из p₂. Получим уравнение = p₂ - 2 = p₂ - p₁.

4 x₁ - x₃ + x₄ = 8. (₎

В итоге получили новое «предпочтительное» представление исходной задачи (3.11) - (3.14) относительно новых базисных переменных x₂, x₄:

f(x) = x₁+ 2x₂ + 0 x₃ + 0 x₄® max

- 1/2 x₁+ x₂+ 1/2 x₃ = 2. ()

4 x₁ - x₃ + x₄ = 8. (₎

x_j і 0, j = 1,2,3,4.

Подставляя сюда представление нового базисного плана x¹ = (0, x_2,0, x₄), сразу найдем его координаты, так как значения базисных переменных равны правым частям уравнений

x¹ = (0,2,0,8); f(x¹)=4.

На этом завершается первая итерация простого симплекс-метода. Далее процесс решения задачи продолжается с шага 1, состоящем в проверке найденного плана на оптимальность. Решение заканчивается тогда, когда все симплексные оценки текущего базисного плана окажутся неотрицательными.

Мы не будем проводить вторую итерацию по схеме первой, поскольку все вычисления симплекс-метода удобнее проводить в табличном виде.

симплекс переменная канонический программирование

Литература

1. Эконометрика: Учебник / Под ред. И.И. Елисеевой. - М.: Финансы и статистика, 2002. - 344 с.: ил.

2. Практикум по эконометрике: Учеб. пособие / И.И. Елисеева, С.В. Курышева, Н.М. Гордеенко и др.; Под ред. И.И. Елисеевой. - М.: Финансы и статистика, 2002. - 192 с.: ил.

3. Кремер Н.Ш., Путко Б.А. Эконометрика: Учебник для вузов. - М.: ЮНИТИ-ДАНА, 2002. - 311 с.

4. Магнус Я.Р., Катышев П.К., Пересецкий А.А. Эконометрика. Начальный курс: учебник. - М.: Дело, 2001. - 400 с.

5. Катышев П.К., Магнус Я.Р., Пересецкий А.А. Сборник задач к начальному курсу эконометрики. - 3-е изд., испр. - М.: Дело, 2003. - 208 с.

6. Доугерти К. Введение в эконометрику. - М.: Финансы и статистика, 1999.

7. Джонстон Дж. Эконометрические методы. - М.: Статистика, 1980.

8. Кейн Э. Экономическая статистика и эконометрия. Введение в количественный экономический анализ. Вып. 1. - М.: Статистика, 1977.

9. Ланге О. Введение в эконометрику / Пер. с польск. - М.: Прогресс, 1964.

10. Лизер С. Эконометрические методы и задачи. - М.: Статистика, 1971.

11. Маленво Э. Статистические методы эконометрии. - М.: Статистика, 1976.

12. Тинтнер Г. Введение в эконометрию. - М.: Финансы и статистика, 1965.

13. Айвазян С.А., Мхитарян В.С. Прикладная статистика и основы эконометрики: учебник для вузов. - М.: ЮНИТИ, 1998.

14. Вентцель Е.С. Теория вероятностей: Учебник для вузов. - 6-е изд. - М.: Высш. шк., 1999.

Размещено на Allbest.ru