Научная электронная библиотека
Монографии, изданные в издательстве Российской Академии Естествознания

2.3.3. Пошаговое описание симплекс-алгоритма

Пусть исходная задача линейного программирования представлена в канонической форме

f = c1x1 + c2x2 + … + cnxn > min;

a11x1 + a12x2 + … + a1nxn + xn+1 = b1;

a21x1 + a22x2 + … + a2nxn + xn+2 = b2;

……………………………………………;

am1x1 + am2x2 + … + amnxn + xn+m = bm;

∀xj ≥ 0 и ∀bi > 0.

Шаг 1. Построим начальную симплекс-таблицу (табл. 2.1).

Таблица 2.1

 

x1 ...

x2 ...

x3

xn

...

xn+m

–f

 

xn+1

a11

a1s

a1n

1

     

b1

xn+r

ar1

ars

arn

 

...

   

bm

xn+m

am1

ams

amn

   

1

 

br

–f

c1

cs

cn

     

1

0

 

Шаг 2. Если все сj ≥ 0, то конец – оптимальным решением является базисное решение (2.6); если некоторое значение сj  < 0, то выбрать переменную xs, которая будет введена в базисное множество на следующей итерации вместо r-й базисной переменной, так чтобы

cs = min cj  < 0.

Шаг 3.

а) Если все ais ≤ 0, то конец, множество решений есть:

– xs ≥ 0 произвольно, базисные переменные равны

xj = bi – aisxs;

– небазисные переменные xj = 0 (j ≠ s) удовлетворяют исходной системе и обладает свойством

f = f0 + csxs → –∞ при xs → +∞.

б) Если какое-то ais > 0, то выбираем r-ю базисную переменную, чтобы вывести ее в следующей итерации, следующим образом

shukaev051.wmf при ais > 0.

Шаг 4. Чтобы получить из предшествующей таблицы начальные данные таблицы, описывающей следующую итерацию, умножим каждый элемент выбранной строки r на число, обратное ведущему элементу ars и поместим эти произведения в r-ю строку таблицы для следующей итерации (табл. 2.2). Вводим переменную xs на место переменной xn+r в предыдущей итерации. Чтобы получить элемент, стоящий в i-й строке и j-м столбце в новой таблице, вычтем из соответствующего элемента предыдущей таблицы произведение числа, стоящего в i-й строке и s-м столбце предыдущей таблицы на число, стоящее в r-й строке и j-м столбце новой таблицы.

Таблица 2.2

 

x1 ...

xn+1

x2 ...

....

x3

xn+m

xn

xn+m

–f

bi

xn+1

shukaev052.wmf

 

shukaev053.wmf

1

     

shukaev054.wmf

xn+r

shukaev055.wmf

1

shukaev056.wmf

 

...

   

shukaev057.wmf

xn+m

shukaev058.wmf

 

shukaev059.wmf

   

1

 

shukaev060.wmf

 

1

             
   

...

           
     

1

         

–f

c1

cs

cn

     

1

shukaev061.wmf

 

где в соответствии с правилами шага 4:

shukaev062.wmf shukaev063.wmf shukaev064.wmf

shukaev065.wmf shukaev066.wmf shukaev067.wmf

Пример 2.1.

f = –9x1 – 10x2 – 16x3 > min;

18x1 + 15x2 + 12x3 + x4 = 360;

6x1 + 4x2 + 8x3 + x5 = 192;

5x1 + 3x2 + 3x3 + x6 = 180;

∀xj ≥ 0.

Шаг 1. Начальная симплекс-таблица имеет вид (табл. 2.3)

Таблица 2.3

 

x1

x2

x3

x4

x5

x6

–f

bi

x4

18

15

12

1

     

360

x5

6

4

8

 

1

   

192

x6

5

3

3

   

1

 

180

–f

–9

–10

–16

     

1

0

 

Шаг 2. cs = min {–9; –10; –16} = –16. Следовательно, s = 3.

Шаг 3.

shukaev068.wmf

Следовательно r = 2 и ведущий элемент ars = a23 = 8.

Шаг 4. Переход к следующей симплекс-таблице (табл. 2.4)

Таблица 2.4

 

x1

x2

x3

x4

x5

x6

–f

shukaev069.wmf

x4

9

9

 

1

shukaev070.wmf

   

72

x3

shukaev071.wmf

shukaev072.wmf

1

 

shukaev073.wmf

   

24

x6

–1

shukaev074.wmf

   

shukaev075.wmf

1

 

108

–f

3

–2

   

2

 

1

384

 

Так как условие теоремы 2.3 не выполнено снова переходим к шагу 2.

Шаг 2. cs = –2.Следовательно s = 2.

Шаг 3.

shukaev076.wmf

Следовательно r = 1 и ведущий элемент ars = a12 = 9.

Шаг 4. Переход к следующей симплекс-таблице (табл. 2.5)

Таблица 2.5

 

x1

x2

x3

x4

x5

x6

–f

bi

x2

9

1

 

shukaev077.wmf

shukaev078.wmf

   

8

x3

shukaev079.wmf

 

1

shukaev080.wmf

shukaev081.wmf

   

20

x6

shukaev082.wmf

   

shukaev083.wmf

shukaev084.wmf

1

 

96

–f

6

   

shukaev085.wmf

shukaev086.wmf

 

f

400

 

Все относительные оценки в последней симплекс-таблице не отрицательны, следовательно, в соответствии с теоремой 2.3 имеем оптимальное решение:

x1 = 0; x2 = 8; x3 = 20; x4 = 0; x5 = 0; x6 = 96; f = –400.


Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074