Смекни!
smekni.com

Линейное программирование, решение задач симплексным методом (стр. 4 из 8)

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

Таким образом, симплексное преобразование выполня­ется по следующему правилу:

1. Выбирается разрешающий столбец, соответствующий наименьшему отрицательному элементу в Z - строке.

2. Выбирается разрешающая строка, которая соответству­ет наименьшему положительному из отношений элементов правой части уравнений на соответствующие элементы раз­решающего столбца. На пересечении разрешающего столбца и разрешающей строки стоит разрешающее число.

3. Элементы разрешающей строки делятся на разрешаю­щее число.

4. Вычисляются элементы всех остальных строк по фор­муле:
Новые эл-ты = Старые эл-ты _

соответствующее число в разрешающей строке

*

соответствующее число в разре­шающем столбце

разрешающее число

Из системы (1.4) находим второе допустимое базисное решение Х2 = Yl = 0; X1 = 25; Y2 = 42; Y3 = 258, которому соответствует новое увеличенное значение функции Z = 250.

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

1. Если в Z - строке найдется хотя бы один отрицатель­ный элемент и

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

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

2. Если все элементы в Z - строке неотрицательны, то достигнуто оптимальное решение.

Это и есть достаточные условия существования оптималь­ного плана решения.

В системе (1.4) коэффициент при Х2 в Z - строке отри­цательный, поэтому второй столбец будет разрешающим. Находим, что вторая строка будет разрешающей. Далее про­изводим симплексное преобразование системы (1.4) соглас­ном указанному правилу:

X1 + 8/42 Y1 – 5/42 Y2 = 20,

X2 – 1/3 Y1 + 1/3 Y2 = 14,

20/7 Y1 – 23/7 Y2 + Y3 = 120,

10/42 Y1 + 20/42 Y2 + Z = 270, (1.5)

Так как в Z - строке все элементы неотрицательны, то данный план является оптимальным. При этом Yl = Y2 = 0; X1 = 20; Х2 = 14 и Zmax = 270.

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

Каждое симплексное преобразование системы сводится к переходу от одной симплексной таблицы к другой.

Соответственно исходной системе уравнений (1.3) состав­ляем первую симплекс-таблицу (табл. 1.1).

X1

X2

Y1

Y2

Y3

контр. столбец

Y1

350

14

5

1

0

0

370

Y2

392

14

8

0

1

0

415

Y3

408

6

12

0

0

1

427

Z

0

-10

-5

0

0

0

-15

Таблица 1.1

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

Из табл. 1.1 имеем первое допустимое решение системы (1.3) Х1 = Х2 = 0, Y1 = 350,

Y2 = 392, Y3 = 408, Z = 0, которое соответствует вершине О (0,0) многоугольника допустимых решений OABCD (рис.1).

Переход ко второй симплекс-таблице (табл. 1.2) выпол­няется согласно указанному в этом пункте правилу для сим­плексных преобразований систем уравнений, при этом раз­решающая переменная Х1 идет в базис вместо разрешающей переменной Y1 Получаем табл. 1.2.

X1

X2

Y1

Y2

Y3

контр. столбец

X1

25

1

5/14

1/14

0

0

370/14

Y2

42

0

3

-1

1

0

45

Y3

258

0

138/14

-6/14

0

1

3758/14

Z

250

0

-20/14

10/14

0

0

3490/14

Таблица 1.2

После заполнения табл. 1.2 следует проверить правиль­ность ее заполнения, для чего суммируем коэффициент по строкам и эта сумма должна быть равна коэффициентам, сто­ящим в соответствующих клетках контрольного столбца. Из табл. 1.2 второе допустимое решение будет Х1 = 25, Х2 = 0, Y1 = 0, Y2 = 42, Y3 = 258 и Z = 250.

Нетрудно видеть, что эта таблица соответствует систе­ме (1.4), а опорное решение

Х1 = 25, Х2 = 0 соответствует вершине D(25,0) многоугольника решений.

Так как в Z - строке имеется отрицательный элемент, то улучшаем решение, для чего составляем симплексную табл. 1.3.

X1

X2

Y1

Y2

Y3

контр. столбец

X1

20

1

0

4/21

-5/42

0

295/14

X2

14

0

1

-1/3

1/3

0

15

Y3

120

0

0

20/7

-23/7

1

844/7

Z

270

0

0

5/21

10/21

0

1895/7

Таблица 1.3

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

Так как в Z - строке нет отрицательных элементов, то данное решение будет оптимальным.

Табл. 1.3 соответствует системе уравнений (1.5) и опти­мальному решению Х1 = 20,

Х2 = 14 и Zmax = 270 и вершине С (20,14) многоугольника допустимых решений OABCD.

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

Симплексный метод на основе укороченных таблиц

Рассмотрим систему уравнений (1.3) и запишем ее в виде таблицы 1.4
СП БП

1

X1

X2

Y1

350

14

5

Y2

392

14

8

Y3

408

6

12

Z

0

-10

-5

Таблица 1.4