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

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

Задача линейного программирования модифицированным симплексным методом
Дана математическая модели задачи:
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: (-9, -3, 10, 1, 1)
Тогда вектор нулевой строки c* будет равен разности двух векторов cN и uN:
c*1,2,3,4,6 = cN - uN = (9, 3, -10, -1, -1)
Откуда номер направляющего столбца s = 1 (индекс максимального значения из положительных элементов).
Выбираем из матрицы А столбец под номером 1.

Умножаем обратную матрицу B-1 на вектор (a11,...,am1)
a* = B-1 (a11,...,am1)T = (7, 0, 0)T
min(6:7 = 6/7;-;2:2 = 1;) = 6/7
Откуда номер направляющей строки 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 = (12/7, 0, 0)
Умножаем обратную матрицу B-1 на вектор b.

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

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

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

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

Вычисляем:

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

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

Второй этап. Удаляем столбцы с искусственными переменными. Заменим вектор оценок С на целевую функцию.
Выразим базисные переменные:
x1 = 1-11/2x3-1/2x6
которые подставим в целевую функцию:
F(X) = 2(1-11/2x3-1/2x6) + 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: (0, 0, 0, 0, 0)
Тогда вектор нулевой строки c* будет равен разности двух векторов cN и uN:
c*2,3,6 = cN - uN = (-5, 0, 0, 0, 0)
Вектор С не содержит положительных элементов больше нуля. Найдено оптимальное решение X.
Вектор результатов X = (1, 0, 0)T
Значение целевой функции F(X) = bc = 2

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

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

загрузка...