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

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

Рассмотрим сначала случай, когда строки матрицы A линейно независимые. Пусть B — некоторая база матрицы A, а B — соответствующая базисная подматрица и пусть
A = (B,N)

c = (c_B, c_N)
где через x_B, c_B обозначены векторы, составленные из базисных компонент векторов x и c соответственно, а через x_N, c_N обозначены векторы, составленные из небазисных компонент векторов x и c соответственно. Тогда ЗЛП примет вид:

Шаг исключения Гаусса на каждой итерации симплекс-метода заключается в умножении слева текущей симплексной таблицы на матрицу

M = E_t· E_t-1 · …· E₁
Матрица M имеет следующее блочное строение:

Справедливы следующие равенства, выражающие элементы симплексной таблицы через коэффициенты ограничений и вектор цен:
q₀₀ = cx = ub, b^* = B^-1b, c^*= c —u A, а^* = B^-1a_s.

Интерпретируя коэффициенты симплекс-таблицы, получим следующую эквивалентную формулировку задачи:

Формула с^* = c - uA показывает, что для того, чтобы вычислить текущие относительные оценки (нулевую строку симплекс-таблицы) необходимо из строки c вычесть все строки матрицы A, домноженные на соответствующие цены u.

Решение х системы Ax = b базисное, если х_N = 0 и, следовательно, x_B = В^-1b. Базисное решение х допустимо, если х ≥ 0 и, так как х _N = 0, то достаточно потребовать х _B ≥ 0. Значение целевой функции cx на базисном решении х есть сх = ub. Базисное решение оптимально, если c ^* = c — uA ≥ 0, или с _N= c_N — uN ≥ 0.

Алгоритм модифицированного симплекс-метода

1. Приведение к канонической форме и начало

   Задача ЛП: минимизировать (c^Tx) при условиях (Ax = b, x ≥ 0).
   Находим начальное допустимое базисное решение. Формируем базисную матрицу B (размер m × m) из столбцов A, соответствующих базисным переменным. Вычисляем B^-1.

2. Вычисление базисной компоненты решения

   Находим значения базисных переменных:
   x_B=B^-1 b
   Небазисные переменные x_N=0

3. Вычисление симплекс-множителей (потенциалов)

   Вектор двойственных переменных:
   u = c_B B^-1
   где c_B — коэффициенты целевой функции при базисных переменных.

4. Оценка оптимальности

   Для всех небазисных столбцов j вычисляем относительные оценки:
   Δ_j = c_N - uN
   Если для всех j выполняется Δ_j≤0 (задача на максимум) — текущее решение оптимально. Конец итераций.
   Иначе выбираем столбец N_j максимального значения из положительных элементов Δ_j для ввода в базис.

5. Определение направления движения

   Вычисляем вектор разложения нового столбца по базису:
   d = B^-1 A_j

6. Проверка неограниченности решения

   Если все компоненты вектора d ≤ 0 (нет положительных направлений), то целевая функция не ограничена снизу. Конец итераций.

7. Определение исключаемой переменной

   Находим максимально возможный шаг θ по правилу минимального симплекс-отношения:
   θ = min{i: d_i > 0} xB_i/d_i
   Индекс i, на котором достигается максимум, указывает на строку, чья базисная переменная покинет базис.

8. Смена базиса и обновление обратной матрицы

   Заменяем столбец в базисе: выводим старый B_i и вводим новый A_j.
   Ключевой шаг: обновляем обратную матрицу без пересчета, используя элементарные преобразования:
   B^-1 = E × B^-1
   где E — матрица, построенная на основе вектора d и индекса i.

9. Переход к следующей итерации

   Возвращаемся к Шагу 2, используя обновленную B^-1 и новый набор базисных индексов.

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

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

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

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

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

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

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

Решение.
x₁ - выпуск диванов, шт.
x₂ - выпуск кресел, шт.
x₃ - выпуск стульев, шт.
x₄ - выпуск столов, шт.

Целевая функция: 1000x₁ + 360x₂ + 120x₃ +200x₄ = max

Ограничения по ресурсам:
5x₁ + 2x₂ + 0.5x₃ +2x₄ ≤ 500
13x₁ +8x₂ + 2x₃ +3x₄ ≤ 1500
8x₁ + 3x₂ + 2x₃ +3x₄ ≤ 900

Ограничение по количеству
x₂ ≤ 2x₁
x₃ = 4x₄
x₄ ≥ x₁
x₁ ≥ 10

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

Целевая функция: 1000x₁ + 360x₂ + 120x₃ +200x₄ = max

Ограничения:
5x₁ + 2x₂ + 0.5x₃ +2x₄ ≤ 500
13x₁ +8x₂ + 2x₃ +3x₄ ≤ 1500
8x₁ + 3x₂ + 2x₃ +3x₄ ≤ 900
2x₁ - x₂ ≤ 0
x₃ - 4x₄= 0
x₁ - x₄  ≥ 0
x₁ ≥ 10
x₁ ≥ 0, x₂  ≥ 0, x₃  ≥ 0, x₄ ≥ 0

Пример №4. Задача линейного программирования модифицированным симплексным методом
Дана математическая модели задачи:
7x₁ + 3x₂ – 7x₃ ≥ 6
4x₁ + x₂ – 8x₃ ≥ -1
2x₁– 3x₃ ≥ 2
F(x) = 2x₁ + 5x₂ – 3x₃ → min

Решим прямую задачу линейного программирования модифицированным симплексным методом через онлайн сервис Симплексный метод.
Поскольку в правой части присутствуют отрицательные значения, умножим соответствующие строки на (-1).
Определим минимальное значение целевой функции F(X) = 2x₁ + 5x₂ - 3x₃ при следующих условиях-ограничений.
7x₁ + 3x₂ - 7x₃≥6
- 4x₁ - x₂ + 8x₃≤1
2x₁ - 3x₃≥2
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
7x₁ + 3x₂-7x₃-1x₄ + 0x₅ + 0x₆= 6
-4x₁-1x₂ + 8x₃ + 0x₄ + 1x₅ + 0x₆ = 1
2x₁ + 0x₂-3x₃ + 0x₄ + 0x₅-1x₆ = 2
Решение состоит из двух этапов. Первый этап - введение искусственного базиса (единичной матрицы) и поиск первого опорного плана (без учета целевой функции). Второй этап - поиск оптимального решения на основе целевой функции.

Первый этап. Для нахождения начальной допустимой базы воспользуемся методом искусственного базиса.
Имеем:
Матрица коэффициентов A = a_ij

Итерация №1.
Базисные переменные: <X> = (7, 5, 8)
Выбираем столбцы под номерами(7, 5, 8) из матрицы А и формируем матрицу В.

Матрица c.
В этой матрице под номерами (7,8 - номера искусственных переменных) ставим (-1).
c = (0, 0, 0, 0, 0, 0, -1, -1)
Формируем из матрицы С две матрицы: c_B - составленная из базисных компонентов вектора С и c_N - составленная из небазисных компонентов вектора С.
c_B(7,5,8) = (-1, 0, -1)
c_N(1,2,3,4,6) = (0, 0, 0, 0, 0)
Матрица N формируется из матрицы А из соответствующих столбцов с номерами N.

Матрицу B^-1 вычисляем через алгебраические дополнения.

Умножаем вектор c_B на обратную матрицу B^-1. Получаем вектор цен u.
u = c_BB^-1 = (-1, 0, -1)
Умножаем обратную матрицу B^-1 на вектор b.

Умножаем вектор u на матрицу N: (-9, -3, 10, 1, 1)
Тогда вектор нулевой строки c^* будет равен разности двух векторов c_N и uN:
c^*_1,2,3,4,6 = c_N - uN = (9, 3, -10, -1, -1)
Откуда номер направляющего столбца s = 1 (индекс максимального значения из положительных элементов).
Выбираем из матрицы А столбец под номером 1.

Умножаем обратную матрицу B^-1 на вектор (a₁₁,...,a_m1)
a^* = B_-1 (a₁₁,...,a_m1)^T = (7, 0, 0)^T
min(6:7 = ⁶/₇;-;2:2 = 1;) = ⁶/₇
Откуда номер направляющей строки r = 1 (индекс минимального значения).

Итерация №2.
Базисные переменные: <X> = (1, 5, 8)
Выбираем столбцы под номерами(1, 5, 8) из матрицы А и формируем матрицу В.

Матрица c.
c = (9, 3, -10, -1, 0, -1, 0, 0)
Формируем из матрицы С две матрицы: c_B - составленная из базисных компонентов вектора С и c_N - составленная из небазисных компонентов вектора С.
c_B(1,5,8) = (9, 0, 0)
c_N(2,3,4,6,7) = (3, -10, -1, -1, 0)
Матрица N формируется из матрицы А из соответствующих столбцов с номерами N.


Умножаем вектор c_B на обратную матрицу B^-1. Получаем вектор цен u.
u = c_BB^-1 = (1²/₇, 0, 0)
Умножаем обратную матрицу B^-1 на вектор b.

Умножаем вектор u на матрицу N: (3⁶/₇, -9, -1²/₇, 0, 1²/₇)
Тогда вектор нулевой строки c^* будет равен разности двух векторов - c_N и uN:
c^*_2,3,4,6,7 = c_N - uN = (^-6/₇, -1, ²/₇, -1, -1²/₇)
Откуда номер направляющего столбца s = 3 (индекс максимального значения из положительных элементов).
Выбираем из матрицы А столбец под номером 3.

Умножаем обратную матрицу B^-1 на вектор (a₁₃,...,a_m3)
a^* = B_-1 (a₁₃,...,a_m3)^T = (^-1/₇,0, 0)^T
min(-;-;²/₇:²/₇ = 1;) = 1
Откуда номер направляющей строки r = 3 (индекс минимального значения).

Итерация №3.
Базисные переменные: <X> = (1, 5, 4)
Выбираем столбцы под номерами(1, 5, 4) из матрицы А и формируем матрицу В.

Матрица c.
c = (0, ^-6/₇, -1, ²/₇, 0, -1, -1²/₇, 0)
Формируем из матрицы С две матрицы: c_B - составленная из базисных компонентов вектора С и c_N - составленная из небазисных компонентов вектора С.
c_B(1,5,4) = (0, 0, ²/₇)
c_N(2,3,6,7,8) = (^-6/₇, -1, -1, -1²/₇, 0)
Матрица N формируется из матрицы А из соответствующих столбцов с номерами N.


Умножаем вектор c_B на обратную матрицу B^-1. Получаем вектор цен u.
u = c_BB^-1 = (^-2/₇, 0, 1)
Умножаем обратную матрицу B^-1 на вектор b.

Умножаем вектор u на матрицу N: (^-6/₇, -1, -1, ^-2/₇, 1)
Тогда вектор нулевой строки c^* будет равен разности двух векторов c_N и uN:
c^*_2,3,6,7,8 = c_N - uN = (0, 0, 0, -1, -1)
Вектор С не содержит положительных элементов больше нуля. Первый этап симплекс-метода завершен.

Второй этап. Удаляем столбцы с искусственными переменными. Заменим вектор оценок С на целевую функцию.
Выразим базисные переменные: x₁ = 1-1¹/₂x₃^-1/₂x₆
которые подставим в целевую функцию:
F(X) = 2(1-1¹/₂x₃^-1/₂x₆) + 5x₂-3x₃
или
F(X) = 2+5x₂+x₆
Имеем:
Матрица коэффициентов A = a_ij

Матрица b.

Итерация №1.
Базисные переменные: <X> = (1, 5, 4)
Выбираем столбцы под номерами(1, 5, 4) из матрицы А и формируем матрицу В.

Матрица c.
c = (0, -5, 0, 0, 0, 0)
Формируем из матрицы С две матрицы: c_B - составленная из базисных компонентов вектора С и c_N - составленная из небазисных компонентов вектора С.
c_B(1,5,4) = (0, 0, 0)
c_N(2,3,6) = (-5, 0, 0, 0, 0)
Матрица N формируется из матрицы А из соответствующих столбцов с номерами N.

Вычисляем обратную матрицу B^-1 вычисляем через алгебраические дополнения.

Умножаем вектор c_B на обратную матрицу B^-1. Получаем вектор цен u.
u = c_BB^-1 = (0, 0, 0)
Умножаем обратную матрицу B^-1 на вектор b.

Умножаем вектор u на матрицу N: (0, 0, 0, 0, 0)
Тогда вектор нулевой строки c^* будет равен разности двух векторов c_N и uN:
c^*_2,3,6 = c_N - uN = (-5, 0, 0, 0, 0)
Вектор С не содержит положительных элементов больше нуля. Найдено оптимальное решение X.
Вектор результатов X = (1, 0, 0)^T
Значение целевой функции F(X) = bc = 2

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

Пример №5. Дана математическая запись модели:
7x₁ + 3x₂ – 7x₃ ≥ 6
4x₁ + x₂ – 8x₃ ≥ -1
2x₁– 3x₃ ≥ 2
F(x) = 2x₁ + 5x₂ – 3x₃ → min
Решить задачу оптимизации модели модифицированным симплексным методом.
Поскольку в правой части присутствуют отрицательные значения, умножим соответствующие строки на (-1).
Определим минимальное значение целевой функции F(X) = 2x₁+5x₂-3x₃ при следующих условиях-ограничений.
7x₁+3x₂-7x₃≥6
-4x₁-x₂+8x₃≤1
2x₁-3x₃≥2
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
7x₁ + 3x₂-7x₃-1x₄ + 0x₅ + 0x₆= 6
-4x₁-1x₂ + 8x₃ + 0x₄ + 1x₅ + 0x₆ = 1
2x₁ + 0x₂-3x₃ + 0x₄ + 0x₅-1x₆= 2
Решение состоит из двух этапов. Первый этап - введение искусственного базиса (единичной матрицы) и поиск первого опорного плана (без учета целевой функции). Второй этап - поиск оптимального решения на основе целевой функции.

Первый этап. Для нахождения начальной допустимой базы воспользуемся методом искусственного базиса.
Имеем:
Матрица коэффициентов A = a_ij

Итерация №2.
Базисные переменные: <X> = (1, 5, 8)
Выбираем столбцы под номерами (1, 5, 8) из матрицы А и формируем матрицу В.

Матрица c.
c = (9, 3, -10, -1, 0, -1, 0, 0)
Формируем из матрицы С две матрицы: c_B - составленная из базисных компонентов вектора С и c_N- составленная из небазисных компонентов вектора С.
c_B(1,5,8) = (9, 0, 0)
c_N(2,3,4,6,7) = (3, -10, -1, -1, 0)
Матрица N формируется из матрицы А из соответствующих столбцов с номерами N.

Вычисляем:

Умножаем вектор c_B на обратную матрицу B^-1. Получаем вектор цен u.
u = c_BB^-1 = (1.2857, 0, 0)
Умножаем обратную матрицу B^-1 на вектор b.

Умножаем вектор u на матрицу N: (3.8571, -9, -1.2857, 0, 1.29)
c^*_2,3,4,6,7 = c_N - uN = (-0.8571, -1, 0.2857, -1, -1.29)
Откуда номер направляющего столбца s = 3 (индекс максимального значения из положительных элементов).
Выбираем из матрицы А столбец под номером 3.

Умножаем обратную матрицу B^-1 на вектор (a₁₃,...,a_m3)^T
a^* = B_-1 (a₁₃,...,a_m3)^T = (-0.1429, 0, 0)^T
min(-;-;0.29:0.29 = 1;) = 1
Откуда номер направляющей строки r = 3 (индекс минимального значения).

Итерация №3.
Базисные переменные: <X> = (1, 5, 4)
Выбираем столбцы под номерами (1, 5, 4) из матрицы А и формируем матрицу В.

Матрица c.
c = (0, -0.8571, -1, 0.2857, 0, -1, -1.2857, 0)
Формируем из матрицы С две матрицы: c_B - составленная из базисных компонентов вектора С и c_N - составленная из небазисных компонентов вектора С.
c_B(1,5,4) = (0, 0, 0.2857)
c_N(2,3,6,7,8) = (-0.8571, -1, -1, -1.2857, 0)
Матрица N формируется из матрицы А из соответствующих столбцов с номерами N.

Вычисляем:

Умножаем вектор c_B на обратную матрицу B^-1. Получаем вектор цен u.
u = c_BB^-1 = (-0.2857, 0, 1)
Умножаем обратную матрицу B^-1 на вектор b.

Умножаем вектор u на матрицу N: (-0.8571, -1, -1, -0.2857, 1)
c^*_2,3,6,7,8 = c_N - uN = (-0, -0, -0, -1, -1)
Вектор С не содержит положительных элементов больше нуля. Первый этап симплекс-метода завершен.

Второй этап. Удаляем столбцы с искусственными переменными. Заменим вектор оценок С на целевую функцию.
Выразим базисные переменные: x₁ = 1-1.5x₃-0.5x₆
которые подставим в целевую функцию:
F(X) = 2(1-1.5x₃-0.5x₆) + 5x₂-3x₃
или
F(X) = 2+5x₂+x₆
Имеем:
Матрица коэффициентов A = a_ij

Матрица b.

Итерация №1.
Базисные переменные: <X> = (1, 5, 4)
Выбираем столбцы под номерами (1, 5, 4) из матрицы А и формируем матрицу В.

Матрица c.
c = (0, -5, 0, 0, 0, 0)
Формируем из матрицы С две матрицы: c_B - составленная из базисных компонентов вектора С и c_N - составленная из небазисных компонентов вектора С.
c_B(1,5,4) = (0, 0, 0)
c_N(2,3,6) = (-5, 0, 0, 0, 0)
Матрица N формируется из матрицы А из соответствующих столбцов с номерами N.

Вычисляем:
Матрицу B^-1 вычисляем через алгебраические дополнения.

Умножаем вектор c_B на обратную матрицу B^-1. Получаем вектор цен u.
u = c_BB^-1 = (0, 0, 0)
Умножаем обратную матрицу B^-1 на вектор b.

Умножаем вектор u на матрицу N: uN = (0, 0, 0, 0, 0)
c^*_2,3,6 = c_N - uN = (-5, 0, 0, 0, 0)
Вектор С не содержит положительных элементов больше нуля. Найдено оптимальное решение X.
Вектор результатов X = (1, 0, 0)^T
Значение целевой функции F(X) = bc = 2

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