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

--PAGE_BREAK--2. Симплекс-метод 2.1 Идея симплекс-метода


Рассмотрим универсальный метод решения канонической задачи линейного программирования
<img border=«0» width=«157» height=«28» src=«ref-1_845691180-536.coolpic» v:shapes="_x0000_i1041">, <img border=«0» width=«55» height=«20» src=«ref-1_845691716-148.coolpic» v:shapes="_x0000_i1042">, <img border=«0» width=«41» height=«20» src=«ref-1_845691864-229.coolpic» v:shapes="_x0000_i1043">,
с n переменными и m ограничениями-равенствами, известный как симплекс-метод. 

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

С любой угловой точкой связан базисный план задачи, в котором <img border=«0» width=«45» height=«16» src=«ref-1_845692093-123.coolpic» v:shapes="_x0000_i1044"> переменных равны нулю, а оставшимся переменным соответствуют линейно независимые столбцы матрицы условий <img border=«0» width=«17» height=«19» src=«ref-1_845692216-96.coolpic» v:shapes="_x0000_i1045">. Эти линейно независимые столбцы образуют невырожденную базисную матрицу <img border=«0» width=«24» height=«25» src=«ref-1_845692312-112.coolpic» v:shapes="_x0000_i1046">.

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

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

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

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

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

·                   шаг 0. Определение начального базиса <img border=«0» width=«24» height=«25» src=«ref-1_845692312-112.coolpic» v:shapes="_x0000_i1047"> и соответствующей ему начальной угловой точки (базисного плана) <img border=«0» width=«21» height=«24» src=«ref-1_845692536-106.coolpic» v:shapes="_x0000_i1048">.

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

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

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

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

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

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

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

1.                 правые части уравнений <img border=«0» width=«45» height=«25» src=«ref-1_845692642-229.coolpic» v:shapes="_x0000_i1049">, <img border=«0» width=«95» height=«23» src=«ref-1_845692871-302.coolpic» v:shapes="_x0000_i1050">.

2.                 матрица условий <img border=«0» width=«17» height=«19» src=«ref-1_845692216-96.coolpic» v:shapes="_x0000_i1051"> содержит единичную подматрицу размера <img border=«0» width=«48» height=«16» src=«ref-1_845693269-167.coolpic» v:shapes="_x0000_i1052">

<img border=«0» width=«169» height=«113» src=«ref-1_845693436-1031.coolpic» v:shapes="_x0000_i1053">.

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

Пример 2.1.

<img border=«0» width=«265» height=«25» src=«ref-1_845694467-675.coolpic» v:shapes="_x0000_i1054">

<img border=«0» width=«160» height=«113» src=«ref-1_845695142-1296.coolpic» v:shapes="_x0000_i1055">

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

<img border=«0» width=«179» height=«84» src=«ref-1_845696438-1085.coolpic» v:shapes="_x0000_i1056">, <img border=«0» width=«96» height=«84» src=«ref-1_845697523-793.coolpic» v:shapes="_x0000_i1057">,

а целевой вектор с = (1, -3, 0, 4, 2).

Сразу очевидна одна базисная матрица: <img border=«0» width=«123» height=«25» src=«ref-1_845698316-397.coolpic» v:shapes="_x0000_i1058"> с единичными векторами условий. 

Следовательно, выбирая в качестве базисных переменных x1, x3,
x5, и полагая в системе уравнений x2 =
x4 = 0 (небазисные переменные), немедленно находим x1 =10,
x3 = 20,
x5 = 8, так что начальный базисный план x0 = (10, 0, 20, 0, 8).Видим, что значения базисных переменных равны правым частям ограничений. Из этого понятно требование положительности правых частей bi.

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

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

xБ = b.

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


∆j = < сБ, Aj > – cj, j = 1,...,n, (2.1)
где сБ – вектор из коэффициентов целевой функции при базисных переменных xБ, Aj –
j-йстолбец матрицы условий, cj –
j-й коэффициент целевой функции. Разности ∆j называются симплексными разностями или симплексными оценками.

Критерий оптимальности базисного плана. Если для базисного плана с единичной базисной матрицей все симплексные оценки неотрицательны, то этот план оптимален.

Применим данный критерий для проверки на оптимальность базисного плана x0 = (10, 0, 20, 0, 8) из примера 2.1.

Так как в этом плане вектор базисных переменных xБ =(x1, x3,
x5), то сБ = (c1, c3,
c5) = (1, 0, 2).

<img border=«0» width=«429» height=«84» src=«ref-1_845698713-2286.coolpic» v:shapes="_x0000_i1059">.

Следовательно,

∆1 = < сБ, A1 > – c1 = 1∙1 + 0∙0 + 2∙0 – 1= 0,


∆2 = < сБ, A2 > – c2 = 1∙3 + 0∙1 + 2∙2 – (-3) = 10,

∆3 = < сБ, A3 > – c3 = 1∙0 + 0∙1 + 2∙0 – 0= 0,

∆4 = < сБ, A4 > – c4 = 1∙(-1) + 0∙5 + 2∙1 – 4= -3,

∆5 = < сБ, A5 > – c5 = 1∙0 + 0∙0 + 2∙1 – 2= 0.

Так как оценка ∆4 < 0, то базисный план x0 не оптимален. Заметим, что симплексные оценки, соответствующие базисным переменным, всегда равны нулю, так что достаточно проверять только небазисные оценки.
    продолжение
--PAGE_BREAK--2.2 Реализация симплекс-метода на примере


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



f(x)= x1+ 2x2+0x3+ 0x4→max

(2.2)

–x1+ 2x2+ x3= 4,

(2.3)

3x1+2x2+ x4= 12,

(2.4)

xj≥0, j = 1,2,3,4.

(2.5)



Матрица условий A = (A1, A2, A3, A4), где
<img border=«0» width=«77» height=«57» src=«ref-1_845700999-454.coolpic» v:shapes="_x0000_i1060"> <img border=«0» width=«69» height=«57» src=«ref-1_845701453-466.coolpic» v:shapes="_x0000_i1061"> <img border=«0» width=«68» height=«57» src=«ref-1_845701919-461.coolpic» v:shapes="_x0000_i1062"> <img border=«0» width=«69» height=«57» src=«ref-1_845702380-464.coolpic» v:shapes="_x0000_i1063">
Целевой вектор c =(c1,
c2,
c3,
c4) = (1, 2, 0, 0); вектор правых частей b=(b1,
b2) = (4, 12).

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

Задача имеет предпочтительный вид, так как правые части уравнений положительны, а столбцы матрицы условий A3,
A4 образуют единичную подматрицу. Значит начальная базисная матрица <img border=«0» width=«24» height=«28» src=«ref-1_845702844-124.coolpic» v:shapes="_x0000_i1064">= (A3,A4); x3и
x4– базисные переменные,
x1и
x2— небазисные переменные, cБ= (c3,
c4) = = (0, 0).

Начальный базисный план имеет вид x0= (0, 0, x3, x4) = (0, 0, 4, 12); f(
xo)= 0.

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

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


1= <
cБ,
A1> –
c1= 0 ·(–1)+ 0 ·3 – 1 = –1.

2= <
cБ,
A2> –
c2= 0 ·2 + 0 · 2 – 2 = –2.
Так как оценки отрицательны, то план x – не оптимален. Будем искать новый базисный план (смежную угловую точку) с большим значением целевой функции.

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

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

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

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


x' = (0, x2,x3, x4).
Этот план не является базисным, так как он содержит только одну нулевую координату, значит надо сделать нулевой (исключить из базиса) одну из переменных x3илиx4. Подставим координаты плана x' = (0, x2,x3,x4) в ограничения задачи. Получим


2x2+
x3= 4,

2x2 + x4 = 12.
Выразим отсюда базисные переменные x3иx4через переменную x2, вводимую в базис.



x3 = 4 – 2x2,

(2.6)

x4 = 12 – 2x2.

(2.7)



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



4 – 2x2≥,

(2.8)

12 – 2x2 ≥.

(2.9)



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

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

2x2 ≤ 4,

2x2 ≤ 12,

откуда максимальное значение x2 = min { 4/2, 12/2 } = 2. Подставляя это значение в выражения (2.6), (2.7) для x3иx4, получаем x3 = 0.Следовательно x3 выводится из базиса. 

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

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

x' = (0, x2, 0, x4)

Базис этой точки состоит из столбцов A2 и A4, так что <img border=«0» width=«24» height=«28» src=«ref-1_845702968-120.coolpic» v:shapes="_x0000_i1065">= (A2,A4). Этот базис не является единичным, так как вектор A2 = (2,2), и следовательно задача (2.2)–(2.5) не имеет предпочтительного вида относительно нового базиса. Преобразуем условия задачи (2.3), (2.4) таким образом, чтобы она приняла предпочтительный вид относительно новых базисных переменных x2,x4, то есть чтобы переменная x2входила в первое уравнение с коэффициентом, равным единице, и не присутствовала во втором уравнении. Перепишем уравнения задачи
– x1+ 2 x2+ x3 = 4, (p1)

3x1 +2 x2 + x4 = 12. (p2)
Поделим первое уравнение на коэффициент при x2.Получим новое уравнение <img border=«0» width=«20» height=«28» src=«ref-1_845703088-110.coolpic» v:shapes="_x0000_i1066">= p1 / 2, эквивалентное исходному 
– 1/2 x1+ x2+ 1/2 x3 = 2. (<img border=«0» width=«20» height=«28» src=«ref-1_845703088-110.coolpic» v:shapes="_x0000_i1067">)
Используем это уравнение, которое назовем разрешающим, для исключения переменной x2из второго уравнения. Для этого надо уравнение <img border=«0» width=«20» height=«28» src=«ref-1_845703088-110.coolpic» v:shapes="_x0000_i1068"> умножить на 2 и вычесть из p2. Получим <img border=«0» width=«23» height=«28» src=«ref-1_845703418-115.coolpic» v:shapes="_x0000_i1069"> = p2– 2<img border=«0» width=«20» height=«28» src=«ref-1_845703088-110.coolpic» v:shapes="_x0000_i1070"> = p2– p1:
4 x1 – x3 + x4 = 8. (<img border=«0» width=«23» height=«28» src=«ref-1_845703418-115.coolpic» v:shapes="_x0000_i1071">)
В итоге получили новое «предпочтительное» представление исходной задачи относительно новых базисных переменных x2, x4:


f(x) = x1 + 2 x2 + 0 x3 + 0 x4max

– 1/2 x1+ x2+ 1/2 x3 = 2 (<img border=«0» width=«20» height=«28» src=«ref-1_845703088-110.coolpic» v:shapes="_x0000_i1072">)

4 x1– x3 +x4= 8(<img border=«0» width=«23» height=«28» src=«ref-1_845703418-115.coolpic» v:shapes="_x0000_i1073">)

xj0,j= 1,2,3,4


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


x' = (0, 2, 0, 8); f(x1)=4.
На этом завершается первая итерация простого симплекс-метода. Далее процесс решения задачи продолжается с шага 1, состоящем в проверке найденного плана на оптимальность. Решение заканчивается тогда, когда все симплексные оценки текущего базисного плана окажутся неотрицательными.

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