Реферат: Линейное программирование, решение задач симплексным методом

X2 – 6/14 Y1 + У3

= 258,

-20/14

X2 + 10/14 Y1

+ Z = 250.


(1.4)

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

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

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.

К-во Просмотров: 743
Бесплатно скачать Реферат: Линейное программирование, решение задач симплексным методом