3.5. Симплекс - метод решения злп.

(c,x) -?

X = { x : b , x  0} (*)

Симплекс - метод состоит из 2-х этапов:

1. Поиск крайней точки допустимого множества.

2. Перебор крайних точек с целью поиска оптимальной.

1. Поиск крайней точки допустимого множества :

Расширим пространство состояний. Введем дополнительные координаты

X = { x :- y = b , x 0, y  0}, (c,x) -? (**)

Эквивалентность этих задач ((*) и (**)) следует из того , что двойственной к обеим задачам будет : max (b,) при  с,   0.

Запишем - y = b в виде :

1+......+ 0 =+...+-

0 +1+...+0 =+...+-

..................................................................

0 + ....... + 1=+...+-

Переменные ,...,можно рассматривать как базисные переменные, т.к. соответствующие им вектора условий линейно независимы (вектора ...).

Имеем:

- переменных n+m

- уравнений m

Тогда переменные ,...,можно рассматривать, как свободные переменные, которые могут принимать произвольные значения. Как было показано выше, для того чтобы точка увеличенного пространствабыла крайней достаточно x = 0, т.е.. Т.е. полагаем: =...: =: = 0. Если все= - 0 , то мы получили крайнюю точку допустимого множества. Если хотя бы один отрицателен, то меняем систему координат (уточняется далее).

Переход к новому базису.

Обозначим полученную крайнюю точку =(y₁=-b₁,…,y_m=-b_m,x₁=0,…,x_n=0). Ей соответствует разложение по базису:

++...+= B (1)

Разложим по базису каждый , j =:=

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

++...+=(2)

Зададимся величиной >0 (пока не известной).

Умножим на нее обе части равенства (2) и вычтем результат почленно из равенства (1).

Получаем:

++...++=B (3)

Т.о., вектор = (,, ... ,, 0, ... , 0,, 0, ..., 0)

(s -место )

является допустимой крайней точкой, если его компоненты неотрицательны. Т.к. >0, то все компоненты вектора , в которые входят< 0 , положительны. Поэтому надо рассмотреть только компоненты, включающие положительные. Т.е. необходимо определить такое>0,при котором для всех ,> 0 будет

0  0 <  .Т.е. надо   .

Крайняя точка не может содержать m+1 положительную компоненту, поэтому в необходимо обнулить, по крайней мере, одну компоненту.

Положим, что  = ==, т.е. r-я компонента обратится в 0.

Подставим значение в (3):

++...++..++…

+=B

То есть получаем новое разложение:

+...++...++= B ,

которому соответствует новая крайняя точка = (,...,,...,, 0,..., 0,, 0,...,0 ) , где=(i =,i  r ), =.

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

Мы рассмотрели переход от одной крайней точки к другой, но на первом этапе симплекс - метода осуществляется поиск допустимой крайней точки , поэтому возможна ситуация , когда -< 0.Тогда надо вычислять по формуле:

=

* объяснение далее в табличном методе

Мы рассмотрели преобразование одного вектора (условий ()) по новому базису , а надо - для всех векторов. При поиске допустимой крайней точки если хотя бы один из < 0 , то необходимо изменить систему координат, т.е. перейти в другую крайнюю точку.

Пусть с помощью предыдущих рассуждений выбрали столбец s и строку r, т.е. будем вводить в базис , а выводить из базиса

Напомним :

= ++...++...+-

Т.к. вводим в базис , то коэффициент при нем должен быть 1 , а во всех других уравнениях он должен отсутствовать (= 0).

=+ ( изменил знак)

(4) Подставим эту координату во все прочие ограничения , получаем:

=+ +,

где i =,i  r.

и ( i =,i  r) - новые базисные переменные. За конечное число таких исключений мы получим допустимую крайнюю точку.

Табличный метод нахождения крайней точки:

Исходные ограничения:

Надо , чтобы - 0

Как только это произойдет ,( i, j)

Получится допустимая крайняя точка.

Предположим, что одно -< 0. Сделаем одно Жорданово исключение:

Формулы пересчета исходной таблицы:

1). r-я строка преобразуется так:

= ,

=  , j  s

=  - т.е. меняет знак (ниже покажем , что правые части , которые были положительными, так положительными и остались)

(см. первую строку из (4))

2). Столбец с номером s преобразуется так :

=, i  r

3). Остальные элементы пересчитываются так:

=,

i  r, j  s (см. вторую строку из (4))

= , i  r

* в таблице , очевидно, -

Покажем, что правые части ,которые были > 0, такими и останутся.

=

а). Пусть < 0, < 0.

Тогда < -будет так, если выбирать как максимум из

отрицательных.

Тогда == () < 0

б). Пусть < 0, > 0.

= +() << 0

Отсюда вывод : если < 0, то< 0.

Порядок выбора , и :

( разрешающего столбца, строки и элемента)

Пусть хотя бы один -< 0.Рассмотрим строку с номеромi. Либо все элементы этой строки  0, либо хотя бы один >0.

В первом случае: допустимое множество пусто, т.к. = 0.

Во втором случае: пусть > 0. Тогда разрешающий столбец будет иметь номер s.

будем изменять от нуля до тех пор, пока какой-нибудь из не станет = 0.

Рассмотрим отношения . Ограничимся только отрицательными. Выберемr :

=

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

2. Поиск оптимальной точки (перебор крайних точек допустимого множества).

Предположим, что допустимая крайняя точка найдена. Вектор c должен лежать в первом квадранте новой системы координат. Для этого нужно чтобы  0.

Целевая функция f(x) =

Когда мы заменим систему координат {}{}, тогда

f =  (например, для двумерного случая)

Стратегия: надо двигаться от одной крайней точки до другой, чтобы целевая функция уменьшалась. Это гарантирует отсутствие циклов, а, следовательно, конечное число шагов. Если все > 0, то текущая крайняя точка является оптимальной, т.к. если изменим св. переменную (равную 0), то увеличится и значение функции.

* т.к. свободную переменную можно только увеличивать(первый квадрант)

Табличный метод поиска оптимальной точки:

-> 0 i (должны быть положительны)

Задача:

С помощью метода жордановых исключений найти оптимальную точку. В новой системе координат при замене имеем(см. (4))

f

добавка ( < 0)

= ++

f(x) =

=, =

Алгоритм выбора разрешающего элемента при переборе крайних точек:

1. Пусть все  0.

Тогда текущая крайняя точка оптимальна.

2. Пусть существует хотя бы один < 0.

1). Все  0 i ,

тогда min f = - .

2). Пусть < 0 (существует)

выбираем {} , среди таких элементов находим максимальный. Пусть это - это разрешающий элемент.