4.5. Основные понятия ЛП. Свойства задач ЛП (стр. 2 )

Рассмотрим возможные варианты построения начального решения.

1. Исходная модель представлена неравенствами “£”:

.

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

Если положить xj=0, j=1,2,…,n, то дополнительные переменные xn+i=bi³0 (i=1,2,…,m) удовлетворяют всем требованиям допустимого базисного решения: выполняются все условия задачи и число базисных переменных равно m. Очевидно, что этому базисному решения соответствует единичный базис {Ai}(0)={An+1, An+2,…,An+m}. В этом случае не надо вычислять коэффициенты разложения небазисных векторов по базису. Действительно, в системе уранений

каждый коэффициент входит только в одно уравнение с множителем +1. Поэтому ее решением будет

an+i, j= aij,

то есть коэффициенты разложения равны соответствующим компонентам раскладываемого вектора условий.

2. Исходная модель представлена неравенствами “³”:

.

Тогда соответствующая каноническая модель

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

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

В первом из них в каждое равенство канонической модели вводится искусственная переменная :

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

Этот прием очень простой, но приводит к значительному увеличению числа переменных. Второй вариант устраняет этот недостаток.

Найдем в канонической модели уравнение с наибольшей правой частью. Пусть таким будет последнее уравнение, то есть.

.

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

где

Если теперь положить xj=0 (j=1,2,...,m) и xn+m=0, то дополнительные переменные xn+i=b`i³0 (i=1,2,…,m-1) могут быть приняты в качестве базисных. Однако при этом нехватает одной базисной переменной и последнее уравнение не выполняется. Введем в него искусственную переменную xm+n+1

которая и будет недостающей базисной переменной (xm+n+1=bm). Таким образом, получено искусственное базисное решение, содержащее независимо от числа ограничений только одну искусственную переменную. Соответствующий ему базис, как и ранее, является единичным:

.

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

, для первого варианта,

для второго варианта,

где М - большое положительное число, такое, что M>>max|Cj| (в задаче на минимум знак минус заменяется на плюс).

Если при выполнении признака оптимальости хотя бы одна исксственная перемнная останется положительной, то это будет означать, что задача неразрешима из-за противоречивости условий: не выполняться будут те условия, в которые входят ненулевые искуссвенные переменные.

3.В исходной модели условия заданы в виде равенств

Для построения базисного решения введем в каждое равенство искусственную переменную:

Тогда базисное решение будет состоять из искусственных переменных базис – из единичных векторов при этих переменных, а исходный критерий модифицируется:

Число искусственных переменных может быть меньше, если в исходной системе есть переменные, входящие со знаком плюс только в одно уравнение. Такие переменные принимаются за базисные, а искусственные переменные в соответствующие условия не вводятся..

4.Исходная модель содержит все виды ограничений (общий случай).

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

4.9.5. Связь между параметрами последовательных итераций

Процедура перехода от вершины к вершине связана с пересчетом большого числа параметров. К ним относятся коэффициенты разложения aij, относительные оценки Δj, базисные переменные и критерий. В симплекс-методе для их вычисления применяются обобщенные преобразования Жордана – Гаусса.

Пусть {Ai}(0), iÎI0={1,2,…,k,…,m}- исходный базис. Смежный базис отличается от него только одной компонентой:

{Ai}(1), iÎI1={1,2,…,r,…,m}.

Если из множества I0 исключить индекс k, а из I1 удалить r, то эти множества будут тождественно равны.

Возьмем вектор Aj такой, что jÏ I0 & jÏ I1. Он может быть представлен как через исходный, так и смежный базисы:

(4.17)

(4.18)

Зная коэффициенты разложения по исходному базису aij, найдем коэффициенты разложения по смежному базису Для этого в (4.17) заменим вектор Ak на вектор Ar. Из представления Ar через исходный базис

(4.19)

получаем

(4.20)

В (4.17) выделим слагаемое с вектором Ak

и заменим в нем Ak выражением (4.20):

После преобразования получаем:

(4.21)

В формулах (4.18) и (4.21) вектор Aj представлен через одну и ту же систему векторов. Приравнивая коэффициенты при одноименных векторах, находим искомые зависимости:

(4.22)

где - число переменных в канонической модели.

В базисном решении выполняется равенство

в котором xi - базисные переменные. Переобозначим вектор ограничений В на А0:

.

Отсюда очевидно, что xi - это коэффициенты разложения вектора ограничений по текущему базису, то есть с учетом принятой индексации

и

Значит, для базисных переменных справедливы соотношения (4.22). Этого и следовало ожидать, так как полученные ранее формулы (4.11) и (4.12) для пересчета базисных переменных являются частным случаем (4.22). Действительно, достаточно заменить в них xi на ai0 , чтобы прийти к (4.22).

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

Введем расширенные векторы следующим образом:

.

Так как размерность векторов увеличилась на единицу, базис должен включать m+1 векторов. В качестве недостающего базисного вектора возьмем единичный вектор

в котором единица стоит на позиции m+1. Такой вектор линейно независим от расширенных векторов условий. Как и раньше, рассмотрим два смежных расширенных базиса, образованных векторами с индексами и .

Представим небазисный вектор через расширенный базис:

(4.23)

Так как первые m компонент вектора равны нулю, первые m уравнений в (4.23) тождественны (4.17) и, следовательно, Новыми здесь являются только коэффициенты Чтобы выяснить их смысл, запишем последнее уравнение системы (4.23):

Отсюда имеем

,

то есть оценки и критерий тоже являются коэффициентами разложения.

Таким образом, все параметры симплекс-метода математически представляют собой коэффициенты разложения, а рекуррентные формулы (4.22) справедливы для

4.9.6. Алгоритм симплекс-метода

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

Полная симплекс-таблица имеет следующую структуру.

Таблица l	C0	C1	C2	…	Cr	…	C	q
i	Csi	базис Asi	B=A0	A1	A2	…	Ar	…	A
1	Cs1	As1	a10=xS1	a11	a12	…	a1r	…	a1
2	Cs2	As2	a20=xS2	a21	a22	…	a2r	…	a2
…	…	…	…	…	…	…	…	…	…	…
k	Csk	Ask	ak0=xSk	ak1	ak2	…	akr	…	ak	q0
…	…	…	…	…	…	…	…	…	…	…
m	Csm	Asm	am0=xSm	am1	am2	…	amr	…	am
m+1	-am+1,j	L	Δ1	Δ2	…	Δr	…	Δ
m+2	zj	z0	z1	z2	…	zr	…	z

Здесь Cj – коэффициенты линейной формы L, Csi – коэффициенты в L при базисных переменных (подмножество Cj), Asi – базисные векторы, si – индекс базисного компонента на позиции i. Жирной линией выделена главная часть таблицы, все ее элементы подчиняются соотношениям (4.22). Первая и последняя строки и второй столбец таблицы являются вспомогательными, они обязательны только в начальной таблице.

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

Алгоритм состоит из предварительного и основного этапов.

На предварительном этапе сначала определяется начальное базисное решение одним из методов, рассмотренных выше. Исходя из него заполняется начальная симплекс-таблица. В третий столбец заносятся m базисных векторов, а во второй – соответствующие коэффициеты из L (или из верхней строки) в порядке следования условий в модели (на первую позицию ставится вектор при базисной переменной из первого условия и т. д.).

Так как начальный базис единичный, элементы главной части таблицы кроме последней строки не вычисляются, а берутся прямо из модели (в столбец A0 заносятся правые части условий, в Aj – коэффициеты при ).

Для получения относительных оценок используются формулы (4.11) и (4.12). Значения zj находятся как скалярное произведение векторов Cb=[Csi] и Aj (суммируются произведения одноименных компонент). Вычитая из нижней строки верхнюю, получаем L и оценки Δj.

Основной этап является итерационным.

Очередная итерация заканчивается заполнением симплекс-таблицы за исключением столбца q. Пусть завершилась l-я итерация. Цикл начинается с анализа оценок Δj в таблице l. Если нет отрицательных оценок, значит, выполнился признак оптимальности. В этом случае возможны два вывода: