Совет 1: Как решать симплексным методом

Если в задаче имеется N неизвестных, то область допустимых решений в системе ограничивающих условий будет являться выпуклым многогранником в N-мерном пространстве. Графическое решение такой задачи невозможно, и в этом случае применяется симплексный метод линейного программирования.
Инструкция
1
Запишите систему ограничений как систему линейных уравнений, число неизвестных в которой будет больше количества уравнений. Выберите R неизвестных при ранге системы R. Используя метод Гаусса, приведите систему к такому виду:

x1= b1+a1r+1x r+1+…+ a1nx n;
x2= b2+a2r+1x r+1+…+ a2nx n;

xr= br+ar,r+1x r+1+…+ amx n.
2
Придайте свободным переменным конкретные значения и после этого рассчитайте базисные величины. Их значения должны быть неотрицательными. Так, если за базисные величины приняты значения от X1 до Xr, то решение данной системы от b1 до 0 будет являться опорным, при условии, что значения от b1 до br ≥ 0.
3
При предельной допустимости базисного решения системы проверьте его на оптимальность. Если оно не будет соответствовать оптимуму, перейдите к следующему. Таким образом, от решения к решению заданная линейная система будет приближаться к оптимуму.
4
Сформируйте симплекс-таблицу. Перенесите в ее левую часть члены с переменными во всех равенствах, а свободные от переменных – в правую. Таким образом, в столбцах будут указаны базовые переменные, свободные члены, Х1…Xr, Xr+1…Xn, в строках отобразятся Х1…Xr, Z.
5
Просмотрите последнюю строку и выберите среди приведенных коэффициентов или максимальное положительное при поиске на min, или минимальное отрицательное число при поиске на max. Если таких значений нет, базисное решение считается оптимальным. Просмотрите столбец таблицы, тождественный выбранному отрицательному или положительному значению в последней строке. Найдите в нем положительные величины. Если их нет, то такая задача не имеет решения.
6
Выберите из оставшихся коэффициентов столбца таблицы именно тот, для которого разница в отношении к свободному члену минимальна. Это значение будет являться разрешающим коэффициентом, а строка, в которой он записан - ключевой. Переведите свободную переменную из строки, где находится разрешающий элемент, в разряд базисных, а базисную, указанную в столбце – в свободную. Составьте еще одну таблицу с измененными наименованиями и значениями переменных.
7
Распределите все элементы ключевой строки, кроме столбца, где находятся свободные члены, на разрешающие элементы и новые полученные значения. Впишите их в строку со скорректированной базисной переменной во второй таблице. Те элементы ключевого столбца, которые равны нулю, всегда тождественны единице. В новой таблице также будут сохранены и столбец с нулем в ключевой строке и строка с нулем в ключевом столбце. Запишите результаты преобразования переменных из первой таблицы.

Совет 2: Как решать симплекс метод

Линейное программирование – математическая область исследования линейных зависимостей между переменными и решения на их основе задач на поиск оптимальных значений того или иного показателя. В связи с этим методы линейного программирования, в том числе симплекс-метод, широко применяются в экономической теории.
Инструкция
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, то оптимальное решение найдено.
Видео по теме
Видео по теме
Поиск
Совет полезен?
Добавить комментарий к статье
Осталось символов: 500