Модифицированный симплекс-метод

см. также Матричное описание симплекс-метода

Решим прямую задачу линейного программирования модифицированным симплекс-методом.

Пример решения модифицированным симплекс-методом

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

c* = cN - uN = (-3, -5, -4)
Откуда s = 2


Откуда r = 1
Итерация №2.
<X> = (2, 5, 6)

Матрица c.
c = (-3, -5, -4, 0, 0, 0)
cB = (-5, 0, 0)
cN = (-3, -4, 0)

Вычисляем:

u = cBB-1 = (-25, 0, 0)

c* = cN - uN = (-0.5, 6, 25)
Откуда s = 1


Откуда r = 2
Итерация №3.
<X> = (2, 1, 6)

Матрица c.
c = (-0.5, 0, 6, 25, 0, 0)
cB = (0, -0.5, 0)
cN = (6, 25, 0)

Вычисляем:

u = cBB-1 = (1.25, -12.5, 0)

c* = cN - uN = (5.75, 23.75, 12.5)
Нулевая строка симплексной таблицы неотрицательна. Найдено оптимальное решение X.
Вектор результатов X = (250, 5375, 0)T
Значение целевой функции F(X) = bc = 27625

Замечания по модифицированному симплексному методу.

  1. Данный метод используется при m намного меньше n (например, количество строк m = 2, а количество переменных n = 8).
  2. При расчетах метод затрачивает намного меньше времени и памяти ЭВМ.
  3. Для вычислений всех оценок достаточно знать начальный вектор b и вектор цен u.
  4. Для предотвращения зацикливания в модифицированном методе удобно применять правило Бленда.
  5. Недостаток модифицированного симплекс-метода: накопление ошибок в связи с вычислением обратной матрицы B-1.
  6. Существуют методы, позволяющие избежать вычисления обратной матрицы B-1.

Дополнительно .
В методе используются операции нахождения обратной матрицы, умножение матриц. Для ознакомления с этими операциями следуйте на главную страницу сайта в раздел Линейная алгебра.

Пример. Мебельная фабрика выпускает диваны, кресла, стулья и столы. Информация о производстве представлена в таблице.
При принятии решения об объемах производства продукции необходимо учесть следующие условия:
1) объем производства кресел должен быть не более чем в два раза больше, чем диванов, 2) объем производства стульев должен быть в четыре раза больше, чем столов, 3) объем производства столов должен быть не меньше, чем диванов, 4) объем производства диванов должен быть не менее 10 шт. Требуется определить наилучшую структуру производства, которая обеспечит максимальную массу прибыли. Решить задачу модифицированным симплексным методом.

Решение.
x1 - выпуск диванов, шт.
x2 - выпуск кресел, шт.
x3 - выпуск стульев, шт.
x4 - выпуск столов, шт.

Целевая функция: 1000x1 + 360x2 + 120x3 +200x4 = max

Ограничения по ресурсам:
5x1 + 2x2 + 0.5x3 +2x4 ≤ 500
13x1 +8x2 + 2x3 +3x4 ≤ 1500
8x1 + 3x2 + 2x3 +3x4 ≤ 900

Ограничение по количеству
x2 ≤ 2x1
x3 = 4x4
x4 ≥ x1
x1 ≥ 10

Таким образом, система ограничений имеет вид:

Целевая функция: 1000x1 + 360x2 + 120x3 +200x4 = max

Ограничения:
5x1 + 2x2 + 0.5x3 +2x4 ≤ 500
13x1 +8x2 + 2x3 +3x4 ≤ 1500
8x1 + 3x2 + 2x3 +3x4 ≤ 900
2x1 - x2 ≤ 0
x3 - 4x4= 0
x1 - x4  ≥ 0
x1 ≥ 10
x1 ≥ 0, x2  ≥ 0, x3  ≥ 0, x4 ≥ 0

загрузка...