»ли метод последовательного улучшени¤ плана. ћетод предназначен дл¤ решени¤ общей задачи линейного программировани¤.

ѕусть имеем следующую задачу:

,††††††††††††††††††††††† ††(1)

с системой ограничений следующего вида:

.††††††††††††††††††††††††††††† (2)

–азрешим эту систему относительно переменных :

.††††††††††††††††††††††††††††††† (3)

¬екторы условий, соответствующие , образуют базис. ѕеремен≠ные† †назовем базисными переменными. ќстальные переменные задачи Ц небазисные.

÷елевую функцию можно выразить через небазисные переменные: .

≈сли приравн¤ть небазисные переменные нулю† ,

то соответствующие базисные переменные примут значени¤ .

¬ектор †с такими компонентами представл¤ет собой угловую точку многогранника решений (допустимую) при условии, что †(опорный план).

“еперь необходимо перейти к другой угловой точке с меньшим значением целевой функции. ƒл¤ этого следует выбрать некоторую небазисную переменную и некоторую базисную так, чтобы после того, как мы Упомен¤ем их местамиФ, значение целевой функции уменьшилось. “акой направленный перебор в конце концов приведет нас к решению задачи.

ѕостроение опорного плана. ѕусть необходимо решить задачу:

.

¬ведем дополнительные переменные, чтобы преобразовать ограничени¤-неравенства к равенствам. ¬ ограничени¤х-равенствах дополнительные переменные должны быть нулевыми. “огда система ограничений принимает вид:

,

где ††.

¬ качестве базисных переменных будем брать систему дополнительно введенных переменных. “огда симплексна¤ таблица дл¤ преобразованной задачи будет иметь следующий вид:

 

ѕравила выбора разрешающего элемента при поиске опорного плана.

1.     ѕри условии отсутстви¤ У0-строкФ (ограничений-равенств) и Усво≠бодныхФ перемен≠ных (т.е. переменных, на которые не наложено требование неотри≠цатель≠ности).

Ј        ≈сли в столбце свободных членов симплексной таблицы нет отрицательных элементов, то опорный план найден.

Ј        ≈сть отрицательные элементы в столбце свободных членов, например . ¬ такой строке ищем отрицательный коэф≠фициент , и этим самым определ¤ем разрешающий столбец . ≈сли не найдем отри≠цательный , то система ограничений несовместна (противо≠речива).

Ј        ¬ качестве разрешающей выбираем строку, которой соответствует минимальное отношение: , где †- номер разрешающей строки. “аким образом, †- разрешающий элемент.

Ј        ѕосле того, как разрешающий элемент найден, делаем шаг модифицированного жорданова исключени¤ с направл¤ющим элементом †и переходим к следующей симплексной таблице.

 

2. ¬ случае присутстви¤ ограничений-равенств и УсвободныхФ переменных поступают следующим образом.

Ј        ¬ыбирают разрешающий элемент в У0-строкеФ и делают шаг модифицированного жорданова исключени¤, после чего вычеркивают этот разрешающий столбец. ƒанную последовательность действий продолжают до тех пор, пока в симплексной таблице остаетс¤ хот¤ бы одна У0-строкаФ (при этом таблица сокращаетс¤).

≈сли же присутствуют и свободные переменные, то необходимо данные переменные сделать базисными. » после того, как свободна¤ переменна¤ станет базисной, в процессе определени¤ разрешающего элемента при поиске опорного и оптимального планов данна¤ строка не учитываетс¤ (но преобразуетс¤).

ѕостроение оптимального плана. ƒл¤ того чтобы опорный план был оптимален, при минимизации целевой функции необходимо, чтобы коэффициенты в строке целевой функции были неположительными (в случае максимизации Ц неотрицательными). “.е. при поиске минимума мы должны освободитьс¤ от положительных коэффициентов в строке .

¬ыбор разрешающего элемента. ≈сли при поиске минимума в строке целевой функции есть коэффициенты больше нул¤, то выбираем столбец с положительным коэффициентом в строке целевой функции в качестве разрешающего. ѕусть это столбец с номером .

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

Ц разрешающий (направл¤ющий) элемент, строка †Ц разрешающа¤.

ƒл¤ перехода к следующей симплексной таблице (следующему опорному плану с меньшим значением целевой функции) делаетс¤ шаг модифици≠ро≠ван≠ного жорданова исключени¤ с разрешающим элементом .

≈сли в разрешающем столбце нет положительных коэффициентов, то целева¤ функци¤ неограничена снизу (при максимизации Ц неограничена сверху).

 

Ўаг модифицированного жорданова исключени¤ над симплексной таблицей.

1.     Ќа месте разрешающего элемента ставитс¤ 1 и делитс¤ на разрешающий элемент.

2.     ќстальные элементы разрешающего столбца мен¤ют знак на противоположный и дел¤тс¤ на разрешающий элемент.

3.     ќстальные элементы разрешающей строки дел¤тс¤ на разрешающий элемент.

4.     ¬се остальные элементы симплексной таблицы вычисл¤ютс¤ по следующей формуле: †.