Виды записи симплекс-метода

Основная идея симплексного метода решения ЗЛП состоит в последовательном улучшении опорных решений ЗЛП.

Существуют несколько форм записи симплексного метода.

  1. Базовая форма записи симплекс-метода;
  2. Симплекс-метод в виде симплексной таблицы;
  3. Модифицированный симплекс-метод;
  4. Симплекс-метод в столбцовой форме;
  5. Симплексный метод в строчечной форме.

Перейти к онлайн решению своей задачи

Определим максимальное значение целевой функции 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

Симплексный метод в строчечной форме

В качестве начальной допустимой базы можно взять 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 называются относительными оценками.

Формы решения методом искусственного базиса

За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.
Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.

Формы решения методом искусственного базиса:

  1. M-метод (симплекс-таблица);
  2. двухэтапный или двухфазный симплекс-метод (Базовая форма записи, Модифицированный симплекс-метод, Симплекс-метод в столбцовой форме, Симплексный метод в строчечной форме).
загрузка...