Eng | Rus | Ukr
Исследование операций
26.01.2005

<< prev | ^up^ | next >>

2.3. НАХОЖДЕНИЕ ДОПУСТИМЫХ БАЗИСНЫХ РЕШЕНИЙ

Определение начального допустимого базисного решения (ДБР) в общем случае представляет значительные трудности. Поэтому для поиска ДБР разработаны специальные методы.

Метод искусственных переменных. Пусть ограничения задачи ЛП имеют вид Ax£A0.

Если все bi ³ 0, i = 1, 2,..., m, то свободные векторы, образующие единичную подматрицу, составляют базис, а соответствующие им переменные - начальное базисное решение.

В общем случае, когда некоторые ограничения имеют знак ³, например

ai1x1 + ai2x2 +.+ainxn³bi , i=1,2,...., m,

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

a11x1 + a12x2 +.+ a1nxn -1xn+1 + 0xn+2 +.+0xn+m = b1;

   a21x1 + a22x2 +.+ a2nxn +0xn+1-1xn+2 +.+0xn+m = b2;      (2.3.1)

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

am1x1 + am2x2 +.+ amnxn + 0xn+1 + 0xn+2 +.-1xn+m = bm.

Свободные переменные {xn+1,.,xn+m}в этом случае уже невозможно использовать в качестве начального базиса, так как xn+1<0,.,xn+m<0. Поэтому в уравнения (2.3.1) дополнительно вводят искусственные переменные xn+m+1,.,xn+m+k. Эти переменные не имеют ничего общего с реальной задачей, и потому их надо вывести из базиса как можно быстрее. Для этого перед началом итераций искусственным переменным в целевой функции приписывают для задач максимизации очень большие по модулю отрицательные коэффициенты (-М), где M>>ci ,

(i = 1, 2, ..,m).

В случае решения задач минимизаци искусственные переменные вводят в целевую функцию с большими положительными коэффициентами (+М).

Знаки искусственных переменных xn+m+1,.,xn+m+k должны совпадать со знаками соответствующих свободных членов. Искусственные переменные образуют начальное базисное решение. Применив симплекс-метод, необходимо вывести из базиса все искусственные переменные. Если удается доказать (или показать), что искусственные переменные полностью вывести из базиса невозможно, то это означает, что задача не имеет решения, то есть ее ограничения противоречивы.

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

Пример 2.5.

Минимизировать f(x)=15x1+33x2

при ограничениях

3x1 + 2x2 ³ 6;

3x1 + x2 ³ 6;

x2 ³ 1;

x1 , x2 ³ 0.

Введя свободные переменные x3, x4, x5 приходим к расширенной форме задачи

3x1 + 2x2 -x3 = 6;

6x1 + x2 -x4 = 6;

x2 -x5 = 1.

Как видим, переменные x3, x4, x5 образуют недопустимое базисное решение

x3 = -6<0; x4 = -6<0; x5 = -1<0.

Поэтому вводим в ограничения и в целевую функцию искусственные переменные x6, x7, x  и приходим к такой задаче:

                       минимизировать {15x1 + 33x2 + Mx6 + Mx7 + Mx8}

при ограничениях

3x1 + 2x2 -x3 + x6 = 6;

6x1 + x2 -x4 + x7 = 6;

x2 -x5 + x8 = 1.

Очевидно, начальное базисное решение x6*=6; x7*=6; x8*=1. Так как A6, A7, A8 образуют единичный базис, а все ai0>0, то применим для решения метод симплекс таблиц (табл.2.7).

Таблица 2.7

cj

   

15

33

0

0

0

M

M

M

 

Bx

A0

A1

A2

A3

A4

A5

A6

A7

A8

M

x6

6

3

2

-1

0

0

1

0

0

M

x7

6

6

1

0

-1

0

0

1

0

M

x8

1

0

1

0

0

-1

0

0

1

   

13M

9M-15

4M-33

-M

-M

-M

0

0

0

Первая итерация. Элементы индексной строки вычисляем следующим образом:                  a06 = a07 = a08 =0;

Поскольку это задача минимизации, то направляющий столбец определяем по наибольшему положительному элементу индексной строки:

Направляющий столбец - A1, направляющая строка - вторая.

Выполним одну итерацию симплекс-метода. Поделим направляющую строку на направляющий элемент a21=6. Далее умножим преобразованную направляющую строку на (9М-15) и вычтем ее из индексной. В результате получим табл. 2.8.

Таблица 2.8.

cj

   

15

33

0

0

0

M

M

 

Bx

A0

A1

A2

A3

A4

A5

A6

A8

M

x6

3

0

1

-1

0

1

0

15

x1

1

1

0

-

0

0

0

M

x8

1

0

1

0

0

-1

0

1

   

4M+15

0

M-30

-M

M-

-M

0

0

Вторая итерация. Так как a02=5/2M-30 >a0j (j¹2), то направляющий столбец второй итерации A2. Направляющая строка - третья, направляющий элемент a82=1. Выполним одну итерацию симплекс-метода. Для этого умножим направляющую строку на 3/2 и вычтем из первой строки.

Затем умножим ее на 1/6, и вычтем из второй, в наконец умножим направляющую строку на (5/2M-30 ) и вычтем из индексной строки. В результате получим табл. 2.9.

Таблица 2.9.

cj

   

15

33

0

0

0

M

 

Bx

A0

A1

A2

A3

A4

A5

A6

M

x6

1

0

0

-1

1

1

15

x 1

1

0

0

-

0

33

x 2

1

0

1

0

0

-1

0

   

M+

0

0

-M

M-

M-30

0

Третья итерация. Так как a05 = 3/2M - 30 > a0j, j¹5 то направляющий столбец A5.. Направляющая строка - первая, а направляющий элемент a65=1 . После выполнения очередной итерации симплекс-метода выведем из базиса последнюю искусственную переменную x6 и введем x5. В результате приходим к табл. 2.10.

Таблица 2.10.

cj

   

15

33

0

0

0

 

Bx

A0

A1

A2

A3

A4

A5

0

x 5

1

0

0

-

1

15

x 1

1

0

0

33

x 2

2

0

1

-

0

   

76

0

0

-20

0

Четвертая итерация. Как видим, в табл. 2.10 все искусственные переменные выведены из базиса, итак, имеем начальный ДБР. Однако он не оптимальный, так как в индексной строке есть положительные оценки. Поэтому выполним еще одну итерацию симплекс-метода с направляющим элементом a54 = 1/3, и получим табл. 2.11.

Таблица 2.11

cj

   

15

33

0

0

0

 

Bx

A0

A1

A2

A3

A4

A5

0

x4

3

0

0

-2

1

3

15

x1

1

0

-

0

33

x2

1

0

1

0

0

-1

   

53

0

0

-5

0

-23

Поскольку в индексной строке табл. 2.11 все оценки для небазисных векторов a0j<0, то найдено оптимальное решение:

x1опт= ; x2опт= 1; x4опт= 3.

Соответствующее значение целевой функции

min(15x1 + 33x2) = 15 x1опт + 33 x2опт =53.

<< prev | ^up^ | next >>

 
     
  Copyright © 2002-2004