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

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

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

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

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

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

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

Пример. Мебельная фабрика выпускает диваны, кресла, стулья и столы. Информация о производстве представлена в таблице.
При принятии решения об объемах производства продукции необходимо учесть следующие условия:
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

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

Пример №2. Задача линейного программирования модифицированным симплексным методом
Дана математическая модели задачи:
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

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

Пример. Дана математическая запись модели:
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

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

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

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