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