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

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

1

1

-1

1

1

0

0

1

-2

1

0

0

-1

1


Матрица b.

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

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

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

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

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

3. Определение новой свободной переменной.
Умножаем обратную матрицу B-1 на вектор (a11,...,am1)
a* = B-1 (a11,...,am1)T = (1, 0)T
min(1:1 = 1;4:1 = 4;) = 1
Откуда номер направляющей строки r = 1 (индекс минимального значения).
Итерация №2.
Базисные переменные: <X> = (1, 7)
Выбираем столбцы под номерами (1, 7) из матрицы А и формируем матрицу В.

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

Вычисляем:

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

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

3. Определение новой свободной переменной.
Умножаем обратную матрицу B-1 на вектор (a12,...,am2)
a* = B-1 (a12,...,am2)T = (-1, 0)T
min(-;3:2 = 1.5;) = 1.5
Откуда номер направляющей строки r = 2 (индекс минимального значения).
Итерация №3.
Базисные переменные: <X> = (1, 3)
Выбираем столбцы под номерами (1, 3) из матрицы А и формируем матрицу В.

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

Вычисляем:

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

Умножаем вектор u на матрицу N: uxN = (-3, -1, -1, -1, 1)
Тогда вектор нулевой строки c* будет равен разности двух векторов cN и uN:
c*2,4,5,6,7 = cN - uN = (0, 0, 0, 0, -1)
Вектор С не содержит положительных элементов больше нуля. Первый этап симплекс-метода завершен.
Второй этап. Удаляем столбцы с искусственными переменными. Заменим вектор оценок С на целевую функцию.
Выразим базисные переменные:
x1 = 2.5-0.5x2+0.5x4+0.5x5-0.5x6
x3 = 1.5-1.5x2-0.5x4-0.5x5-0.5x6
которые подставим в целевую функцию:
F(X) = -(2.5-0.5x2+0.5x4+0.5x5-0.5x6)-2x2 + 6(1.5-1.5x2-0.5x4-0.5x5-0.5x6)-x4
или
F(X) = 6.5+6.5x2+2.5x4+3.5x5+2.5x6
Имеем:
Матрица коэффициентов A = aij

Матрица b.

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

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

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

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

Умножаем вектор u на матрицу N: uxN = (0, 0, 0, 0, 0)
Тогда вектор нулевой строки c* будет равен разности двух векторов cN и uN:
c*2,4,5,6 = cN - uN = (-6.5, -2.5, -3.5, -2.5, 0)
Вектор С не содержит положительных элементов больше нуля. Найдено оптимальное решение X.
Вектор результатов X = (2.5, 0, 1.5, 0)T
Значение целевой функции F(X) = b·c = 6.5
загрузка...