Динамическое программирование
Задачи динамического программирования: задача распределения инвестиций, задача замены оборудования, задача Джонсона
xf1(x)f2(x)f3(x)
16.345
25.267
34.34.67.8
4563
5*76.38.2
Решить онлайн
Примеры решений Метод Гомори Графический метод Теория игр Симплекс-метод M-задача Теоремы двойственности Одноканальные СМО Задача коммивояжера Транспортная задача

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

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

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

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

Решим прямую задачу линейного программирования модифицированным симплексным методом при помощи онлайн сервиса Симплекс-метод.
Поскольку в правой части присутствуют отрицательные значения, умножим соответствующие строки на (-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

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

Определим максимальное значение целевой функции F(X) = 3x1+5x2+4x3 при следующих условиях-ограничений с помощью онлайн сервиса.
0.1x1+0.2x2+0.4x3≤1100
0.05x1+0.02x2+0.02x3≤120
3x1+x2+2x3≤8000
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
0.1x1 + 0.2x2 + 0.4x3 + 1x4 + 0x5 + 0x6 = 1100
0.05x1 + 0.02x2 + 0.02x3 + 0x4 + 1x5 + 0x6 = 120
3x1 + 1x2 + 2x3 + 0x4 + 0x5 + 1x6 = 8000
Решение состоит из двух этапов. Первый этап - введение искусственного базиса (единичной матрицы) и поиск первого опорного плана (без учета целевой функции). Второй этап - поиск оптимального решения на основе целевой функции.
Поскольку сразу имеем единичную матрицу, нет необходимости вводить дополнительный искусственный базис.
Второй этап. Заменим вектор оценок С на целевую функцию.
Имеем:
Матрица коэффициентов A = aij
модифицированный симплекс-метод
Матрица b.
модифицированный симплексный метод
Итерация №1.
<X> = (4, 5, 6)

Матрица c.
c = (-3, -5, -4, 0, 0, 0)
cB = (0, 0, 0)
cN = (-3, -5, -4)

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

u = cBB-1 = (0, 0, 0)

c* = cN - uN = (-3, -5, -4)
Откуда s = 2


Откуда r = 1
Итерация №2.
<X> = (2, 5, 6)

Матрица c.
c = (-3, -5, -4, 0, 0, 0)
cB = (-5, 0, 0)
cN = (-3, -4, 0)

Вычисляем:

u = cBB-1 = (-25, 0, 0)

c* = cN - uN = (-0.5, 6, 25)
Откуда s = 1


Откуда r = 2
Итерация №3.
<X> = (2, 1, 6)

Матрица c.
c = (-0.5, 0, 6, 25, 0, 0)
cB = (0, -0.5, 0)
cN = (6, 25, 0)

Вычисляем:

u = cBB-1 = (1.25, -12.5, 0)

c* = cN - uN = (5.75, 23.75, 12.5)
Нулевая строка симплексной таблицы неотрицательна. Найдено оптимальное решение X.
Вектор результатов X = (250, 5375, 0)T
Значение целевой функции F(X) = bc = 27625

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

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

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

Пример. Мебельная фабрика выпускает диваны, кресла, стулья и столы. Информация о производстве представлена в таблице.
При принятии решения об объемах производства продукции необходимо учесть следующие условия:
1) объем производства кресел должен быть не более чем в два раза больше, чем диванов, 2) объем производства стульев должен быть в четыре раза больше, чем столов, 3) объем производства столов должен быть не меньше, чем диванов, 4) объем производства диванов должен быть не менее 10 шт. Требуется определить наилучшую структуру производства, которая обеспечит максимальную массу прибыли. Решить задачу модифицированным симплексным методом.

Решение.
x1 - выпуск диванов, шт.
x2 - выпуск кресел, шт.
x3 - выпуск стульев, шт.
x4 - выпуск столов, шт.

Целевая функция: 1000x1 + 360x2 + 120x3 +200x4 = max

Ограничения по ресурсам:
5x1 + 2x2 + 0.5x3 +2x4 ≤ 500
13x1 +8x2 + 2x3 +3x4 ≤ 1500
8x1 + 3x2 + 2x3 +3x4 ≤ 900

Ограничение по количеству
x2 ≤ 2x1
x3 = 4x4
x4 ≥ x1
x1 ≥ 10

Таким образом, система ограничений имеет вид:

Целевая функция: 1000x1 + 360x2 + 120x3 +200x4 = max

Ограничения:
5x1 + 2x2 + 0.5x3 +2x4 ≤ 500
13x1 +8x2 + 2x3 +3x4 ≤ 1500
8x1 + 3x2 + 2x3 +3x4 ≤ 900
2x1 - x2 ≤ 0
x3 - 4x4= 0
x1 - x4  ≥ 0
x1 ≥ 10
x1 ≥ 0, x2  ≥ 0, x3  ≥ 0, x4 ≥ 0

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

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

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

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

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

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

Транспортная задача
Используя метод минимального тарифа, представить первоначальный план для решения транспортной задачи. Проверить на оптимальность, используя метод потенциалов. Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
1234b
112436
243858
3276310
a4688 
Решить онлайн
Динамическое программирование
Задачи динамического программирования: задача распределения инвестиций, задача замены оборудования, задача Джонсона
xf1(x)f2(x)f3(x)
16.345
25.267
34.34.67.8
4563
5*76.38.2
Решить онлайн
Нелинейное программирование
Метод Лагранжа
Метод множителей Лагранжа
Решить онлайн
Курсовые на заказ