Виды записи симплекс-метода
Основная идея симплексного метода решения ЗЛП состоит в последовательном улучшении опорных решений ЗЛП.Существуют несколько форм записи симплексного метода.
- Базовая форма записи симплекс-метода;
- Симплекс-метод в виде симплексной таблицы;
- Модифицированный симплекс-метод;
- Симплекс-метод в столбцовой форме;
- Симплексный метод в строчечной форме, Пример №2.
Перейти к онлайн решению своей задачи
Определим максимальное значение целевой функции F(X) = 3x1+5x2+4x3 при следующих условиях-ограничений.
0.1x1+0.2x2+0.4x3≤1100
0.05x1+0.02x2+0.02x3≤120
3x1+x2+2x3≤8000
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
0.1x1 + 0.2x2 + 0.4x3 + 1x4 + 0x5 + 0x6 = 1100
0.05x1 + 0.02x2 + 0.02x3 + 0x4 + 1x5 + 0x6 = 120
3x1 + 1x2 + 2x3 + 0x4 + 0x5 + 1x6 = 8000
Базовая форма записи симплекс-метода
Решение ведется путем выражения базисных переменных через небазисные:x0 = 3x1+5x2+4x3
x4 = 1100-0.1x1-0.2x2-0.4x3
x5 = 120-0.05x1-0.02x2-0.02x3
x6 = 8000-3x1-x2-2x3
Симплекс-метод в виде симплексной таблицы
Решение ведется в виде симплексной таблицы. Форма разработана для вычислений на ЭВМ. При использовании искусственного базиса используется специальное число М (обычно 10000).| План | Базис | В | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | min |
| 1 | x4 | 1100 | 0.1 | 0.2 | 0.4 | 1 | 0 | 0 | 5500 |
| x5 | 120 | 0.05 | 0.02 | 0.02 | 0 | 1 | 0 | 6000 | |
| x6 | 8000 | 3 | 1 | 2 | 0 | 0 | 1 | 8000 | |
| Индексная строка | F(X1) | 0 | -3 | -5 | -4 | 0 | 0 | 0 | 0 |
| 2 | x2 | 5500 | 0.5 | 1 | 2 | 5 | 0 | 0 | 11000 |
| x5 | 10 | 0.04 | 0 | -0.02 | -0.1 | 1 | 0 | 250 | |
| x6 | 2500 | 2.5 | 0 | 0 | -5 | 0 | 1 | 1000 | |
| Индексная строка | F(X2) | 27500 | -0.5 | 0 | 6 | 25 | 0 | 0 | 0 |
| 3 | x2 | 5375 | 0 | 1 | 2.25 | 6.25 | -12.5 | 0 | 11000 |
| x1 | 250 | 1 | 0 | -0.5 | -2.5 | 25 | 0 | 250 | |
| x6 | 1875 | 0 | 0 | 1.25 | 1.25 | -62.5 | 1 | 1000 | |
| Индексная строка | F(X3) | 27625 | 0 | 0 | 5.75 | 23.75 | 12.5 | 0 | 0 |
Модифицированный симплекс-метод
Матрица коэффициентов A = aij
Матрица b.
Итерация №1.
<X> = (4, 5, 6)
Матрица c.
c = (-3, -5, -4, 0, 0, 0)
cB = (0, 0, 0)
cN = (-3, -5, -4)
Вычисляем:
Матрицу B-1 вычисляем через алгебраические дополнения.
u = cBB-1 = (0, 0, 0)
см. также Матричное описание симплекс-метода
Симплекс-метод в столбцовой форме
Переходим к столбцовой форме симплекс-метода. Выразим каждую переменную через небазисные.x0 = 0-3(-x1)-5(-x2)-4(-x3)+0(-x4)+0(-x5)+0(-x6)
x1 = 0-1(-x1)+0(-x2)+0(-x3)+0(-x4)+0(-x5)+0(-x6)
x2 = 0+0(-x1)-1(-x2)+0(-x3)+0(-x4)+0(-x5)+0(-x6)
x3 = 0+0(-x1)+0(-x2)-1(-x3)+0(-x4)+0(-x5)+0(-x6)
x4 = 1100+0.1(-x1)+0.2(-x2)+0.4(-x3)+1(-x4)+0(-x5)+0(-x6)
x5 = 120+0.05(-x1)+0.02(-x2)+0.02(-x3)+0(-x4)+1(-x5)+0(-x6)
x6 = 8000+3(-x1)+1(-x2)+2(-x3)+0(-x4)+0(-x5)+1(-x6)
Данной системе соответствует таблица T0.
| 0 | -1 | 0 | 0 |
| 0 | 0 | -1 | 0 |
| 0 | 0 | 0 | -1 |
| 1100 | 0.1 | 0.2 | 0.4 |
| 120 | 0.05 | 0.02 | 0.02 |
| 8000 | 3 | 1 | 2 |
| 0 | -3 | -5 | -4 |
Пример решения симплекс-методом в столбцовой форме записи
Решим прямую задачу линейного программирования симплексным методом, с использованием столбцовой формы (через калькулятор).Определим максимальное значение целевой функции F(X) = 3x1+5x2+4x3 при следующих условиях-ограничений.
0.1x1+0.2x2+0.4x3≤1100
0.05x1+0.02x2+0.02x3≤120
3x1+x2+2x3≤8000
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
0.1x1 + 0.2x2 + 0.4x3 + 1x4 + 0x5 + 0x6 = 1100
0.05x1 + 0.02x2 + 0.02x3 + 0x4 + 1x5 + 0x6 = 120
3x1 + 1x2 + 2x3 + 0x4 + 0x5 + 1x6 = 8000
Переходим к столбцовой форме симплекс-метода. Выразим каждую переменную через небазисные.
x0 = 0-3(-x1)-5(-x2)-4(-x3)+0(-x4)+0(-x5)+0(-x6)
x1 = 0-1(-x1)+0(-x2)+0(-x3)+0(-x4)+0(-x5)+0(-x6)
x2 = 0+0(-x1)-1(-x2)+0(-x3)+0(-x4)+0(-x5)+0(-x6)
x3 = 0+0(-x1)+0(-x2)-1(-x3)+0(-x4)+0(-x5)+0(-x6)
x4 = 1100+0.1(-x1)+0.2(-x2)+0.4(-x3)+1(-x4)+0(-x5)+0(-x6)
x5 = 120+0.05(-x1)+0.02(-x2)+0.02(-x3)+0(-x4)+1(-x5)+0(-x6)
x6 = 8000+3(-x1)+1(-x2)+2(-x3)+0(-x4)+0(-x5)+1(-x6)
Данной системе соответствует таблица T0.
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1100 |
0.1 |
0.2 |
0.4 |
1 |
0 |
0 |
120 |
0.05 |
0.02 |
0.02 |
0 |
1 |
0 |
8000 |
3 |
1 |
2 |
0 |
0 |
1 |
0 |
-3 |
-5 |
-4 |
0 |
0 |
0 |
В качестве начальной допустимой базы можно взять B0 = <4, 5, 6>.
Поскольку задача решается на максимум, то ведущий столбец выбирают по минимальному отрицательному числу в последней строке.
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1100 |
0.1 |
0.2 |
0.4 |
1 |
0 |
0 |
120 |
0.05 |
0.02 |
0.02 |
0 |
1 |
0 |
8000 |
3 |
1 |
2 |
0 |
0 |
1 |
0 |
-3 |
-5 |
-4 |
0 |
0 |
0 |
В качестве направляющего выберем столбец, соответствующий переменной x2.
Вычислим значения Di по строкам как частное от деления.
и из них выберем наименьшее:
Чтобы теперь выразить все переменные через небазисные, в выражении для x4 выразим x2 и подставим полученное выражение во все остальные равенства.
x2 = 5500+0.5x1+5x4+2x3+5x4+0x5+0x6
После приведения подобных получим:
x0 = 27500-0.5(-x1)+0(-x2)+6(-x3)+25(-x4)+0(-x5)+0(-x6)
x1 = 0-1(-x1)+0(-x2)+0(-x3)+0(-x4)+0(-x5)+0(-x6)
x2 = 5500+0.5(-x1)+0(-x2)+2(-x3)+5(-x4)+0(-x5)+0(-x6)
x3 = 0+0(-x1)+0(-x2)-1(-x3)+0(-x4)+0(-x5)+0(-x6)
x4 = 0+0(-x1)-1(-x2)+0(-x3)+0(-x4)+0(-x5)+0(-x6)
x5 = 10+0.04(-x1)+0(-x2)-0.02(-x3)-0.1(-x4)+1(-x5)+0(-x6)
x6 = 2500+2.5(-x1)+0(-x2)+0(-x3)-5(-x4)+0(-x5)+1(-x6)
Представим в виде таблицы T1:
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
5500 |
0.5 |
0 |
2 |
5 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
10 |
0.04 |
0 |
-0.02 |
-0.1 |
1 |
0 |
2500 |
2.5 |
0 |
0 |
-5 |
0 |
1 |
27500 |
-0.5 |
0 |
6 |
25 |
0 |
0 |
Таким образом, очередная база равна B1 = <2, 5, 6>. Небазисные переменные следующие: N1 = <1, 3, 4>
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
5500 |
0.5 |
0 |
2 |
5 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
10 |
0.04 |
0 |
-0.02 |
-0.1 |
1 |
0 |
2500 |
2.5 |
0 |
0 |
-5 |
0 |
1 |
27500 |
-0.5 |
0 |
6 |
25 |
0 |
0 |
В качестве направляющего выберем столбец, соответствующий переменной x1.
Вычислим значения Di по строкам как частное от деления.
и из них выберем наименьшее:
Чтобы теперь выразить все переменные через небазисные, в выражении для x5 выразим x1 и подставим полученное выражение во все остальные равенства.
x1 = 250+25x5+0x2+-0.5x3+-2.5x4+25x5+0x6
После приведения подобных получим:
x0 = 27625+0(-x1)+0(-x2)+5.75(-x3)+23.75(-x4)+12.5(-x5)+0(-x6)
x1 = 250+0(-x1)+0(-x2)-0.5(-x3)-2.5(-x4)+25(-x5)+0(-x6)
x2 = 5375+0(-x1)+0(-x2)+2.25(-x3)+6.25(-x4)-12.5(-x5)+0(-x6)
x3 = 0+0(-x1)+0(-x2)-1(-x3)+0(-x4)+0(-x5)+0(-x6)
x4 = 0+0(-x1)-1(-x2)+0(-x3)+0(-x4)+0(-x5)+0(-x6)
x5 = 0-1(-x1)+0(-x2)+0(-x3)+0(-x4)+0(-x5)+0(-x6)
x6 = 1875+0(-x1)+0(-x2)+1.25(-x3)+1.25(-x4)-62.5(-x5)+1(-x6)
Представим в виде таблицы T2:
250 |
0 |
0 |
-0.5 |
-2.5 |
25 |
0 |
5375 |
0 |
0 |
2.25 |
6.25 |
-12.5 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
1875 |
0 |
0 |
1.25 |
1.25 |
-62.5 |
1 |
27625 |
0 |
0 |
5.75 |
23.75 |
12.5 |
0 |
Таким образом, очередная база равна B2 = <2, 1, 6>. Небазисные переменные следующие: N2 = <3, 4, 5>
Последняя строка не содержит отрицательных элементов. Найден оптимальный план.
Окончательный вариант таблицы:
250 |
0 |
0 |
-0.5 |
-2.5 |
25 |
0 |
5375 |
0 |
0 |
2.25 |
6.25 |
-12.5 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
1875 |
0 |
0 |
1.25 |
1.25 |
-62.5 |
1 |
27625 |
0 |
0 |
5.75 |
23.75 |
12.5 |
0 |
Оптимальный план можно записать так:
x2 = 5375
x1 = 250
x6 = 1875
F(X) = 5*5375 + 3*250 + 0*1875 = 27625
Примечание:
1. Для предотвращения зацикливания используется правило Бленда.
2. Столбец s, строка r и элемент trs называются направляющими.
3. Матрица T = t(ij) называется столбцовой симплекс-таблицей, соответствующей перестановке N.
Перейти к онлайн решению своей задачи
Симплексный метод в строчечной форме
В качестве начальной допустимой базы можно взять B0 = <4, 5, 6>. Ей будет соответствовать следующая таблица.| 1100 | 0.1 | 0.2 | 0.4 | 1 | 0 | 0 |
| 120 | 0.05 | 0.02 | 0.02 | 0 | 1 | 0 |
| 8000 | 3 | 1 | 2 | 0 | 0 | 1 |
| 0 | -3 | -5 | -4 | 0 | 0 | 0 |
Матрица Q, составленная из коэффициентов системы, называется симплекс-таблицей, соответствующей базе В. Симплекс-таблица называется допустимой, или прямо допустимой, если qi0 ≥ 0. Элементы qi0 последней строки симплекс-таблицы Q называются относительными оценками.
Симплекс-метод в строчечной форме записи. Пример решения
Рассмотрим пример решения прямой задачи линейного программирования строчечным симплекс-методом через калькулятор.Определим максимальное значение целевой функции F(X) = 3x1+5x2+4x3 при следующих условиях-ограничений.
0.1x1+0.2x2+0.4x3≤1100
0.05x1+0.02x2+0.02x3≤120
3x1+x2+2x3≤8000
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
0.1x1 + 0.2x2 + 0.4x3 + 1x4 + 0x5 + 0x6 = 1100
0.05x1 + 0.02x2 + 0.02x3 + 0x4 + 1x5 + 0x6 = 120
3x1 + 1x2 + 2x3 + 0x4 + 0x5 + 1x6 = 8000
В качестве начальной допустимой базы можно взять B0 = <4, 5, 6>. Ей будет соответствовать следующая таблица.
| 1100 | 0.1 | 0.2 | 0.4 | 1 | 0 | 0 |
| 120 | 0.05 | 0.02 | 0.02 | 0 | 1 | 0 |
| 8000 | 3 | 1 | 2 | 0 | 0 | 1 |
| 0 | -3 | -5 | -4 | 0 | 0 | 0 |
Поскольку задача решается на максимум, то ведущий столбец выбирают по минимальному отрицательному числу в последней строке.
| 1100 | 0.1 | 0.2 | 0.4 | 1 | 0 | 0 |
| 120 | 0.05 | 0.02 | 0.02 | 0 | 1 | 0 |
| 8000 | 3 | 1 | 2 | 0 | 0 | 1 |
| 0 | -3 | -5 | -4 | 0 | 0 | 0 |
Вычислим значения Di по строкам как частное от деления:
и из них выберем наименьшее:
Следовательно, 1-ая строка является ведущей. Вместо переменной x4 в план войдет переменная x2. Разделим 1-ую строку на 0.2 и прибавим к последней строке, а затем вычтем из всех остальных строк.
Представим расчет каждого элемента в виде таблицы:
| B | x1 | x2 | x3 | x4 | x5 | x6 |
| 1100 / 0.2 = 5500 | 0.1 / 0.2 = 0.5 | 0.2 / 0.2 = 1 | 0.4 / 0.2 = 2 | 1 / 0.2 = 5 | 0 / 0.2 = 0 | 0 / 0.2 = 0 |
 |  |  |  |  |  |  |
|  |
|  |
|  |
|
 |  |  |  |  |  | |
| 5500 | 0.5 | 1 | 2 | 5 | 0 | 0 |
| 10 | 0.04 | 0 | -0.02 | -0.1 | 1 | 0 |
| 2500 | 2.5 | 0 | 0 | -5 | 0 | 1 |
| 27500 | -0.5 | 0 | 6 | 25 | 0 | 0 |
Вычислим значения Diпо строкам как частное от деления:
и из них выберем наименьшее:
Следовательно, 2-ая строка является ведущей. Вместо переменной x5в план войдет переменная x1. Разделим 2-ую строку на 0.04 и прибавим к последней строке, а затем вычтем из всех остальных строк.
Представим расчет каждого элемента в виде таблицы:
| B | x1 | x2 | x3 | x4 | x5 | x6 |
|  |
|  |
|  |
|
| 10 / 0.04 = 250 | 0.04 / 0.04 = 1 | 0 / 0.04 = 0 | -0.02 / 0.04 = -0.5 | -0.1 / 0.04 = -2.5 | 1 / 0.04 = 25 | 0 / 0.04 = 0 |
|  |
|  |
|  |
|
 |  |  |  |  |  | |
Последняя строка не содержит отрицательных элементов. Найден оптимальный план.
Окончательный вариант таблицы:
| 5375 | 0 | 1 | 2.25 | 6.25 | -12.5 | 0 |
| 250 | 1 | 0 | -0.5 | -2.5 | 25 | 0 |
| 1875 | 0 | 0 | 1.25 | 1.25 | -62.5 | 1 |
| 27625 | 0 | 0 | 5.75 | 23.75 | 12.5 | 0 |
Примечание:
1. Число операций в симплекс-методе не превосходит n!/((n-m)!*m!)
2. Решение х системы уравнений, в котором все небазисные переменные равны 0, называется базисным решение.
3. Если все компоненты базисного решения неотрицательны, то оно называется допустимым базисным решение или опорным планом.
Пример. Собственник располагает четырьмя видами ресурсов. Это, например, денежные средства, производственные помещения, оборудование, сырье. Ресурсы необходимо распределить между шестью видами предприятий. Предприятия различаются по экономическим условиям деятельности: месту расположения, системе налогообложения, стоимости электроэнергии, оплате труда и т. д., в связи , с чем имеют разные издержки производства. Относительные уровни издержек заданы в таблице.
Распределение ресурсов по предприятиям сопряжено с необходимостью ряда ограничений, которые могут быть описаны системой четырех уравнений с шестью неизвестными.
Смысл первого уравнений в нашем примере в том, что ресурс вида 1, общий ресурс которого составляет 16 единиц, может размещаться в количестве четырех единиц на предприятии первого типа и одной единицы – на предприятии четвертого типа. Аналогично раскрывается смысл второго и последующих уравнений. Последнее условие говорит о том, что число предприятий не может быть отрицательным.
Необходимо определить, какое количество предприятий каждого типа следует иметь, чтобы общие издержки были минимальными.
Перейти к онлайн решению своей задачи
Формы решения методом искусственного базиса
За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.
Формы решения методом искусственного базиса:
- M-метод (симплекс-таблица);
- двухэтапный или двухфазный симплекс-метод (Базовая форма записи, Модифицированный симплекс-метод, Симплекс-метод в столбцовой форме, Симплексный метод в строчечной форме).