Симплекс-метод

Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Метод был разработан советским математиком Канторовичем Л. В. в 1937 году.

Описание

 

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

В модифицированном методе матрица

не пересчитывается, хранится и пересчитывается только матрица  . В остальном алгоритм похож на вышеописанный.

1. Вычисляем двойственные  переменные 

2. Проверка оптимальности. преобразуется в .

Проверка заключается  в вычислении для всех столбцов . Столбец со значением < 0 можно вводить в базис.

Часто выбирают минимальное  значение, но для этого нужно перебрать  все столбцы.

Чаще выбирают значение, меньшее некоторого заданного значения

Если такого столбца не обнаружится, за принимается максимальное найденное абсолютное значение и соответствующий столбец вводится в базис.

3. Определение выводимого.

Пусть - вводимый столбец, соответствующий переменной Базиный план - это решение системы Увеличиваем .

Умножим слева на , т.е. .

Здесь - базисный план, - разложение вводимого столбца по базису.

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

4. Пересчет опорного(базисного) плана.

Вычисляем новый опорный  план по уже приведенной формуле  с найденным значением .

5. Пересчитываем обратную  к базисной  .

Пусть - выводимый столбец.

Матрица B представима в  виде

где - базисная матрица без выводимого столбца.

После замены столбца базисная матрица будет иметь вид 

Нам нужно найти матрицу  , такую что

=> => =>

Откуда 

Замечание.

При пересчете матрицы  накапливаются ошибки округления. Во избежание получения больших ошибок время от времени матрица пересчитывается полностью. Этот процесс называется "повторением".

Как решать модифицированным симплексным  методом

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

7	3	-7	-1	0	0	1	0
-4	-1	8	0	1	0	0	0
2	0	-3	0	0	-1	0	1

 
 Матрица b.  
 
 Итерация №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: uN = (-9, -3, 10, 1, 1)  
 c^*_1,2,3,4,6 = c_N - uN = (9, 3, -10, -1, -1)  
 Откуда номер направляющего столбца s = 1 (индекс максимального значения из положительных элементов).  
 Выбираем из матрицы А столбец под номером 1.  
 
 Умножаем обратную матрицу B_-1 на вектор (a₁₁,...,a_m1)^T 
 a^* = B^-1 (a₁₁,...,a_m1)^T = (7, 0, 0)^T 
 min(6:7 = 0.86;-;2:2 = 1;) = 0.86 
 Откуда номер направляющей строки 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.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.

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

Дана математическая запись модели:  
-x₁ - 5x₂ + 3х₃ = 4;  
2x₁ + 5x₂ - 3х₃ ≥2;  
2х₁ + 4х₂ ≤ -4;  
F(x)= -5x₁ + х₂ - 2х₃ → max.

Шаг №0. Сведем задачу ЛП к нахождению минимума.  
-x₁ - 5x₂ + 3х₃ = 4;  
2x₁ + 5x₂ - 3х₃ ≥2;  
2х₁ + 4х₂ ≤ -4;  
-F(x)= 5x₁ - х₂ + 2х₃ → min.  
Если сразу задана функция минимизации (min), то Шаг №0 пропускаем.

Приводим  из системы неравенств в систему  уравнений, вводя дополнительные переменные:  
-x₁ - 5x₂ + 3х₃ = 4;  
2x₁ + 5x₂ - 3х₃ - х₄ = 2;  
2х₁ + 4х₂ + х₅= -4;  
-F(x)= 5x₁ - х₂ + 2х₃ → min.

В матричной форме:  
Матрица А

-1	-5	3	0	0
2	5	-3	-1	0
2	4	0	0	1

 
Матрица В

4

2

-4

или B^T = (4 ;2; -4);

Тогда задачу ЛП можно записать следующим  образом:

A x X = B  
X ≥ 0  
F(x) = Z = C x X → min

Базисные переменные: x₁, x₂, x₃ 
Небазисные переменные: x₄, x₅ 
Преобразуем матрицу А, выделяя единичную матрицу I

-1/3	-5/3	1	0	0
-1	0	0	1	0
2	4	0	0	1

Шаг №1.  
В начале первого цикла нам известны обратная матрица A^-1 (единичная матрица), базисное решение x_b = A^-1 x b

1	0	0
0	1	0
0	0	1

 
x_b = (4; 2; -4);

Шаг №2. Образуем для каждой небазисной переменной характеристическую разность d_j, используя уравнение:

d_j = c_j - s_j x P_j,

где s - двойственные переменные, которые можно найти следующим  образом:

s_j = c_x x A^-1,

где c_x - вектор коэффициентов целевой функции при базисных переменных.  
c_x = (-5; 1; -2);  
s_j = c_x x A^-1 = (-5; 1; -2);  
d_j = (-5; 1; -2) - (-5; 1; -2) = (0; 0; 0)

Шаг №3. Предполагая, что используется стандартное правило выбора вводимого столбца, находим: s = mind_j.  
s = -5, индекс столбца p = 1

Шаг №4. Если s ≥ 0 - процедура останавливается. Текущее базисное решение является оптимальным.

Шаг №5. Если s ≤ 0, вычисляем преобразованный столбец:

P^-_p = A_-1 x P_p

P^-₁ = (-1/3; -1; 2)  
P^-_p = (a_1s,a_2s,...,a_ms)  
Если все a_is ≤ 0 - процедура останавливается: оптимум неограничен.

Шаг №6. В противном случае находим выводимую из базиса переменную:

x_br / a_rs = min (a_is ≥ 0) = θ

Шаг №7. Строим матрицу и трансформируем ее с ведущим элементом a_rs

Автоматизировать  процесс решения можно с помощью  сервиса "Симплексный метод решения  задач линейного программирования online".

 

Литература

• Акулич И.Л.Глава 1. Задачи линейного программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с. — ISBN 5-06-002663-9
• Томас Х. Кормен и др.Глава 29. Линейное программирование // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 5-8459-0857-4