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

Решение задач линейного программирования модифицированным симплексным методом
Дана математическая запись модели:
7x1 + 3x2 – 7x3 ≥ 6
4x1 + x2 – 8x3 ≥ -1
2x1– 3x3 ≥ 2
F(x) = 2x1 + 5x2 – 3x3 → min
Решить задачу оптимизации модели модифицированным симплексным методом.

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

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


 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)
Формируем из матрицы С две матрицы: cB - составленная из базисных компонентов вектора С и cN - составленная из небазисных компонентов вектора С.
cB(7,5,8) = (-1, 0, -1)
cN(1,2,3,4,6) = (0, 0, 0, 0, 0)
Матрица N формируется из матрицы А из соответствующих столбцов с номерами N.

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

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

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

Умножаем обратную матрицу B-1 на вектор (a11,...,am1)T
a* = B-1 (a11,...,am1)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)
Формируем из матрицы С две матрицы: cB - составленная из базисных компонентов вектора С и cN- составленная из небазисных компонентов вектора С.
cB(1,5,8) = (9, 0, 0)
cN(2,3,4,6,7) = (3, -10, -1, -1, 0)
Матрица N формируется из матрицы А из соответствующих столбцов с номерами N.

Вычисляем:

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

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

Умножаем обратную матрицу B-1 на вектор (a13,...,am3)T
a* = B-1 (a13,...,am3)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)
Формируем из матрицы С две матрицы: cB - составленная из базисных компонентов вектора С и cN - составленная из небазисных компонентов вектора С.
cB(1,5,4) = (0, 0, 0.2857)
cN(2,3,6,7,8) = (-0.8571, -1, -1, -1.2857, 0)
Матрица N формируется из матрицы А из соответствующих столбцов с номерами N.

Вычисляем:

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

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

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

Матрица b.

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

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

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

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

Умножаем вектор u на матрицу N: uN =  (0, 0, 0, 0, 0)
c*2,3,6 = cN - 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.

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

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

загрузка...