Инструкция
1
Симплекс-метод – один из основных способов решения задач линейного программирования. Он состоит в последовательном построении математической модели, характеризующей рассматриваемый процесс. Решение разбивается на три основных этапа: выбор переменных, построение системы ограничений и поиск целевой функции.
2
Исходя из этого разделения, условие задачи можно перефразировать следующим образом: найти экстремум целевой функции Z(X) = f(x1, x2, … ,xn) → max (min) и соответствующие переменные, если известно, что они удовлетворяют системе ограничений: Φ_i (x1, x2, … ,xn) = 0 при i = 1, 2, …, k;Φ_i (x1, x2, … ,xn) ) 0 при i = k+1, k+2, …, m.
3
Систему ограничений нужно привести к каноническому виду, т.е. к системе линейных уравнений, где число переменных больше числа уравнений (m > k). В этой системе обязательно найдутся переменные, которые можно выразить через другие переменные, а если это не так, то их можно ввести искусственно. В этом случае первые называются базисом или искусственным базисом, а вторые – свободными.
4
Удобнее рассмотреть симплекс-метод на конкретном примере. Пусть дана линейная функция f(x) = 6x1 + 5x2 + 9x3 и система ограничений:5x1 + 2x2 + 3x3 ≤ 25;x1 + 6x2 + 2x3 ≤ 20;4x1 + 3x3 ≤ 18.Требуется найти максимальное значение функции f(x).
5
РешениеНа первом этапе задайте начальное (опорное) решение системы уравнений абсолютно произвольным образом, которое при этом должно удовлетворять данной системе ограничений. В данном случае требуется введение искусственного базиса, т.е. базисных переменных x4, x5 и x6 следующим образом:5x1 + 2x2 + 3x3 + x4 = 25;x1 + 6x2 + 2x3 + x5 = 20;4x1 + 3x3 + x6 = 18.
6
Как видите, неравенства преобразовались в равенства благодаря добавленным переменные x4, x5, x6, которые являются неотрицательными величинами. Таким образом, вы привели систему к каноническому виду. Переменная x4 входит в первое уравнение с коэффициентом 1, а в два других – с коэффициентом 0, то же справедливо для переменных x5, x6 и соответствующих уравнений, что соответствует определению базиса.
7
Вы подготовили систему и нашли начальное опорное решение – X0 = (0, 0, 0, 25, 20, 18). Теперь представьте коэффициенты переменных и свободные члены уравнений (цифры справа от знака «=») в виде таблицы для оптимизации дальнейших вычислений (см. рис).
8
Суть симплекс-метода состоит в том, чтобы привести эту таблицу к такому виду, в котором все цифры в строке L будут неотрицательными величинами. Если же выяснится, что это невозможно, то система вообще не имеет оптимального решения. Для начала выберите самый минимальный элемент этой строки, это -9. Цифра стоит в третьем столбце. Преобразуйте соответствующую переменную x3 в базисную. Для этого разделите строку на 3, чтобы в ячейке [3,3] получилась 1.
9
Теперь нужно, чтобы ячейки [1,3] и [2,3] обратились в 0. Для этого отнимите от элементов первой строки соответствующие цифры третьей строки, умноженные на 3. От элементов второй строки - элементы третьей, умноженные на 2. И, наконец, от элементов строки L - умноженные на (-9). Вы получили второе опорное решение: f(x) = L = 54 при x1 = (0, 0, 6, 7, 8, 0).
10
В строке L осталось только одно отрицательное число -5 во втором столбце. Поэтому будем преобразовывать к базисному виду переменную x2. Для этого элементы столбца должны принять вид (0, 1, 0). Разделите все элементы второй строки на 6.
11
Теперь от элементов первой строки отнимите соответствующие цифры второй строки, умноженные на 2. Затем отнимите от элементов строки L те же цифры, но с коэффициентом (-5).
12
Вы получили третье и окончательное опорное решение, поскольку все элементы строки L стали неотрицательными. Итак, X2 = (0, 4/3, 6, 13/3, 0, 0) и L = 182/3 = -83/18x1 - 5/6x5 -22/9x6. Максимальное значение функции f(x) = L(X2) = 182/3. Поскольку все x_i в решении X2 неотрицательны, как и само значение L, то оптимальное решение найдено.