Уравнений (5) линейно независима, т е. что r = m - rita.netnado.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Уравнений (5) линейно независима, т е. что r = m - страница №1/1

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

Предполагается, что система уравнений (5) линейно независима, т.е. что r = m.

Симплекс-метод доставляет вычислительную схему перехода от вершины к вершине (от одного базисного решения к другому) в нап­равлении наименьшего значения z.

Начинаем с выбора какого-нибудь допустимого базисного решения. Если базисные переменные обозначены через x1, x2,..., xm, то

уравнения (4) и (5), в результате исключения, могут быть записа­ны в следующей форме:

)

x1 + (a1,m+1xm+1 + ... + a1nxn) = b1 2

x2 + (a2,m+1xm+1 + ... + a2nxn) = b2 2

. . . . . . . . . . . . 8 (10)

xm + (am,m+1xm+1 + ... + amnxn) = bm 2

z = (gm+1xm+1 + ... + gnxn) + z0 2

0

Если все bi . 0, то

(

2 bi , i = 1,2,...,m,

xi= * (11)

2 0, i = m+1,m+2,...,n.

9

образуют базисное допустимое решение.

Если в выражении для целевой функции z в (10) все gi . 0, то решение (11) есть оптимальное решение. Это оптимальное решение единственно, если все g > 0.

Рассмотрим теперь случай, когда решение (10) является невырож­денным базисным допустимым решением (т.е. b1, b2,..., bm > 0), которое не оптимально, т.е. среди gi есть отрицательные.

Пусть, для определенности, gk - наибольшее по абсолютной вели­чине из отрицательных gi. Для получения улучшенного базисного допустимого решения в следующий итерационный цикл, в качестве базисной переменной, вводится xk, заменяющее базисную переменную xj, которая в соответствии с уравнениями xi = bi - aikxk (i = 1,2,...m) первой убывает до нуля, когда xk возрастает то нулево­го значения (если среди aik есть отрицательные). Значит, индекс j ассоциируется с наименьшей возможной величиной (обязательно положительной)

bj

x = --- . (12)

ajk

Улучшенное базисное решение дается равенством (12) и

(

2 bi - aikxk . 0, (i = 1,2,...,m; заметим, что xj=0),

xi = * (13)

2 0, (i=m+1, m+2, ... , n; i - k).

9

bj

При этом z = z0 + gkxk = z0 + gk--- < z0. ajk

Теперь введение

bj 1 n

xk = --- - --- (xj + S ajixi). (14)

ajk ajk i=m+1

в систему (10) приводит ее к канонической форме относительно новых базисных переменных.

Замечание: Симплекс-метод не реализуем, если все ajk неположи­тельны, тогда целевая функция z не имеет нижней гра­ницы на множестве решений.

Пример:

1 1

z = -x1 + -x2 (min)

4 3

5x1 + x2 -5 . 0, x1 . 0,

2x1 + 5x2 - 10 . 0, x2 . 0.

Использование искусственных переменных для начала симплекс-процедуры

Введем m искусственных переменных xn+1, xn+2,...,xn+m и решим вспомогательную задачу о минимизации линейной формы

W = xn+1 + xn+2 + ... + xn+m (15)

при условиях

)

a11x1 + a12x2 + ... + a1nxn + xn+1 = b1 . 0, 2

a21x1 + a22x2 + ... + a2nxn + xn+2 = b2 . 0, 2

. . . . . . . . . . . . . . 8 (16)

am1x1 + am2x2 + ... + amnxn + xn+m = bm . 0, 2

xk . 0, (k = 1,2,...,n+m) 2

0 Принимая x1, x2,..., xn за свободные переменные, а xn+1,

xn+2,...,xn+m за базисные:

xi = 0, для 1 , i , n и xn+j = bj для 1 , j , m

находим оптимальное решение вспомогательной задачи.

Если wmin = 0, т.е. все xn+1, xn+2,..., xn+m = 0, то оно опре­деляет допустимое решение исходной задачи. Если же для оптималь­ного решения w > 0, то исходная задача не имеет допустимых реше­ний.

Пример: (Транспортная задача.)

В пунктах P1,..., Pl имеется однородный груз в количествах a1, a2,..., al. Его необходимо перевезти в пункты Q1, Q2,..., Qr в количествах b1, b2,..., br так, чтобы общая стоимость перевозок была минимальна. При этом предполагается, что количество требуе­мого груза равно имеющимся запасам:

S ai = S bj (4)

i j


Обозначим через xij количество груза, перевозимого из пункта Pi в пункт Qj, а через cij - стоимость перевозок единицы этого груза. В задаче имеются следующие ограничения:

1) количество груза, отправляемого из пункта Pi на все пункты назначения, должно быть равно имеющимся запасам ai:

___

S xij= ai, i = 1,l; (5)



j

2) количество груза, прибываемого в Qj со всех пунктов отправ­ления, должно равняться потребности bj:

___

S xij =bj, j = 1,r. (6)



i

Целевая функция определяет полную стоимость перевозки всех грузов:

q = SS cijxij.

ji

Формулировка задачи остается прежней, если количество имеюще­гося груза превышает потребности. При этом вводится фиктивная станция назначения Qr+1, на которую отправляется излишек груза



___

br+1, со стоимостью перевозок ci,r+1 = 0, i=1,l.