Виды записи симплекс-метода
Основная идея симплексного метода решения ЗЛП состоит в последовательном улучшении опорных решений ЗЛП.Существуют несколько форм записи симплексного метода.
- Базовая форма записи симплекс-метода;
- Симплекс-метод в виде симплексной таблицы;
- Модифицированный симплекс-метод;
- Симплекс-метод в столбцовой форме;
- Симплексный метод в строчечной форме.
Перейти к онлайн решению своей задачи
Определим максимальное значение целевой функции 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.
|
Симплексный метод в строчечной форме
В качестве начальной допустимой базы можно взять 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 называются относительными оценками.
Формы решения методом искусственного базиса
За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.
Формы решения методом искусственного базиса:
- M-метод (симплекс-таблица);
- двухэтапный или двухфазный симплекс-метод (Базовая форма записи, Модифицированный симплекс-метод, Симплекс-метод в столбцовой форме, Симплексный метод в строчечной форме).