Симплекс-метод
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 7x1+5x2 при следующих условиях-ограничений.
2x1+3x2+2x3=19
2x1+x2+x4=13
3x2+x5=15
Расширенная матрица системы ограничений-равенств данной задачи:
| 2 | 3 | 2 | 0 | 0 | 19 | | 2 | 1 | 0 | 1 | 0 | 13 | | 0 | 3 | 0 | 0 | 1 | 15 |
|
|
|
Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x3.
Получаем новую матрицу:
| 1 | 1.5 | 1 | 0 | 0 | 9.5 |
| 2 | 1 | 0 | 1 | 0 | 13 |
| 0 | 3 | 0 | 0 | 1 | 15 |
2. В качестве базовой переменной можно выбрать x4.
3. В качестве базовой переменной можно выбрать x5.
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (3,4,5).
Выразим базисные переменные через остальные:
x3 = -x1-1.5x2+9.5
x4 = -2x1-x2+13
x5 = -3x2+15
Подставим их в целевую функцию:
F(X) = 7x1+5x2
x1+1.5x2+x3=9.5
2x1+x2+x4=13
3x2+x5=15
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
| A = | | 1 | 3/2 | 1 | 0 | 0 | | 2 | 1 | 0 | 1 | 0 | | 0 | 3 | 0 | 0 | 1 |
|
|
|
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Экономический смысл дополнительных переменных: дополнительные переменные задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.
Решим систему уравнений относительно базисных переменных: x3, x4, x5
Полагая, что свободные переменные равны 0, получим первый опорный план: X0 = (0,0,9.5,13,15)
Базисное решение называется допустимым, если оно неотрицательно.
| Базис | B | x1 | x2 | x3 | x4 | x5 |
| x3 | 9.5 | 1 | 1.5 | 1 | 0 | 0 |
| x4 | 13 | 2 | 1 | 0 | 1 | 0 |
| x5 | 15 | 0 | 3 | 0 | 0 | 1 |
| F(X0) | 0 | -7 | -5 | 0 | 0 | 0 |
Переходим к основному алгоритму симплекс-метода.
Итерация №0
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (9.5 : 1 , 13 : 2 , - ) = 6.5
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.
| Базис | B | x1 | x2 | x3 | x4 | x5 | min |
| x3 | 9.5 | 1 | 1.5 | 1 | 0 | 0 | 9.5 |
| x4 | 13 | 2 | 1 | 0 | 1 | 0 | 6.5 |
| x5 | 15 | 0 | 3 | 0 | 0 | 1 | - |
| F(X1) | 0 | -7 | -5 | 0 | 0 | 0 | 0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x4 в план 1 войдет переменная x1.
Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент РЭ=2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x1 и столбец x1. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (2), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
| B | x1 | x2 | x3 | x4 | x5 |
| 9.5-(13*1):2 | 1-(2*1):2 | 1.5-(1*1):2 | 1-(0*1):2 | 0-(1*1):2 | 0-(0*1):2 |
| 13 : 2 | 2 : 2 | 1 : 2 | 0 : 2 | 1 : 2 | 0 : 2 |
| 15-(13*0):2 | 0-(2*0):2 | 3-(1*0):2 | 0-(0*0):2 | 0-(1*0):2 | 1-(0*0):2 |
| 0-(13*-7):2 | -7-(2*-7):2 | -5-(1*-7):2 | 0-(0*-7):2 | 0-(1*-7):2 | 0-(0*-7):2 |
Получаем новую симплекс-таблицу:
| Базис | B | x1 | x2 | x3 | x4 | x5 |
| x3 | 3 | 0 | 1 | 1 | -0.5 | 0 |
| x1 | 6.5 | 1 | 0.5 | 0 | 0.5 | 0 |
| x5 | 15 | 0 | 3 | 0 | 0 | 1 |
| F(X1) | 45.5 | 0 | -1.5 | 0 | 3.5 | 0 |
Итерация №1
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
min (3 : 1 , 6.5 : 0.5 , 15 : 3 ) = 3
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
| Базис | B | x1 | x2 | x3 | x4 | x5 | min |
| x3 | 3 | 0 | 1 | 1 | -0.5 | 0 | 3 |
| x1 | 6.5 | 1 | 0.5 | 0 | 0.5 | 0 | 13 |
| x5 | 15 | 0 | 3 | 0 | 0 | 1 | 5 |
| F(X2) | 45.5 | 0 | -1.5 | 0 | 3.5 | 0 | 0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x3 в план 2 войдет переменная x2.
Строка, соответствующая переменной x2 в плане 2, получена в результате деления всех элементов строки x3 плана 1 на разрешающий элемент РЭ=1. На месте разрешающего элемента получаем 1. В остальных клетках столбца x2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x2 и столбец x2. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
| B | x1 | x2 | x3 | x4 | x5 |
| 3 : 1 | 0 : 1 | 1 : 1 | 1 : 1 | -0.5 : 1 | 0 : 1 |
| 6.5-(3*0.5):1 | 1-(0*0.5):1 | 0.5-(1*0.5):1 | 0-(1*0.5):1 | 0.5-(-0.5*0.5):1 | 0-(0*0.5):1 |
| 15-(3*3):1 | 0-(0*3):1 | 3-(1*3):1 | 0-(1*3):1 | 0-(-0.5*3):1 | 1-(0*3):1 |
| 45.5-(3*-1.5):1 | 0-(0*-1.5):1 | -1.5-(1*-1.5):1 | 0-(1*-1.5):1 | 3.5-(-0.5*-1.5):1 | 0-(0*-1.5):1 |
Получаем новую симплекс-таблицу:
| Базис | B | x1 | x2 | x3 | x4 | x5 |
| x2 | 3 | 0 | 1 | 1 | -0.5 | 0 |
| x1 | 5 | 1 | 0 | -0.5 | 0.75 | 0 |
| x5 | 6 | 0 | 0 | -3 | 1.5 | 1 |
| F(X2) | 50 | 0 | 0 | 1.5 | 2.75 | 0 |
1. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи. Окончательный вариант симплекс-таблицы:
| Базис | B | x1 | x2 | x3 | x4 | x5 |
| x2 | 3 | 0 | 1 | 1 | -0.5 | 0 |
| x1 | 5 | 1 | 0 | -0.5 | 0.75 | 0 |
| x5 | 6 | 0 | 0 | -3 | 1.5 | 1 |
| F(X3) | 50 | 0 | 0 | 1.5 | 2.75 | 0 |
Оптимальный план можно записать так: x1 = 5, x2 = 3, x3 = 0, x4 = 0, x5 = 6.
F(X) = 7*5 + 5*3 = 50.
Примечание:
1. По какому методу пересчитываются симплекс-таблицы?
Используется правило прямоугольника (метод жордановских преобразований).
2. Обязательно ли каждый раз выбирать максимальное значение из индексной строки? Можно не выбирать, но это может привести к зацикливанию алгоритма.
3. В индексной строке в n-ом столбце нулевое значение. Что это означает?
Нулевые значения должны соответствовать переменным, вошедшим в базис. Если в индексной строке симплексной таблицы оптимального плана находится нуль, принадлежащий свободной переменной, не вошедшей в базис, а в столбце, содержащем этот нуль, имеется хотя бы один положительный элемент, то задача имеет множество оптимальных планов. Свободную переменную, соответствующую указанному столбцу, можно внести в базис, выполнив соответствующие этапы алгоритма. В результате будет получен второй оптимальный план с другим набором базисных переменных.
171
183 396 
