Реферат: Линейное программирование, решение задач симплексным методом
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.