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

Метод искусственного базиса

Идея использования искусственных переменных предполагает включение неотрицательных переменных в левую часть каждого из уравнений, в которых не содержится очевидных начальных базисных переменных (когда неравенство имеет знак ≥ или задано в виде равенства). Эти дополнительно вводимые переменные выполняют ту же роль, что и остаточные переменные. Но так как искусственные переменные не имеют отношения к поставленной задаче (отсюда их название - искусственные), то их введение допустимо только в том случае, если симплекс метод будет обеспечивать получение оптимального решения, в котором все искусственные переменные будут равны 0, то есть эти переменные следует использовать только для стартовой точки, причем итерационный метод оптимизации должен "вынуждать" эти переменные принимать нулевые значения в конечном оптимальном решении, обеспечивая допустимость оптимума.
Разработаны два метода получения стартовой точки:
  1. М - метод или метод больших штрафов.
  2. Двухэтапный метод.
Инструкция. Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word и Excel.
Количество переменных
Количество строк (количество ограничений)
При этом ограничения типа xi ≥ 0 не учитывайте. Если в задании для некоторых xi отсутствуют ограничения, то ЗЛП необходимо привести к КЗЛП, или воспользоваться этим сервисом.

Пример. Решить задачу ЛП, найдя начальный опорный план методом искусственного базиса.
Определим максимальное значение целевой функции F(X) =  3x3 - 2x4 - x5 при следующих условиях:
2x1 + x2 + x3 + x4 + 3x5=5
3x1 + 2x3 - x4 + 6x5=7
x1 - x3 + 2x4 + x5=2

Решим прямую задачу линейного программирования двухфазным симплекс-методом.
Введем искусственные переменные x.
2x1 + 1x2 + 1x3 + 1x4 + 3x5 + 1x6+ 0x7 + 0x8 = 5
3x1 + 0x2 + 2x3-1x4 + 6x5 + 0x6+ 1x7 + 0x8 = 7
1x1 + 0x2-1x3 + 2x4 + 1x5 + 0x6+ 0x7 + 1x8 = 2

Для постановки задачи на максимум целевую функцию запишем так:
F(X) =  - Mx6 - Mx7 - Mx8 => max
Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.
Из уравнений выражаем искусственные переменные:
x6 = 5-2x1-x2-x3-x4-3x5
x7 = 7-3x1-2x3+x4-6x5
x8 = 2-x1+x3-2x4-x5
которые подставим в целевую функцию:
F(X) =  - M(5-2x1-x2-x3-x4-3x5) - M(7-3x1-2x3+x4-6x5) - M(2-x1+x3-2x4-x5)=> max
или
F(X) = (6M)x1+(1M)x2+(2M)x3+(2M)x4+(10M)x5+(-14M)=> max
Введем новую переменную x0 = 6x1 + x2 + 2x3 + 2x4+ 10x5.
Выразим базисные переменные <6, 7, 8> через небазисные.
x0 = -14+6x1+x2+2x3+2x4+10x5
x6 = 5-2x1-x2-x3-x4-3x5
x7 = 7-3x1-2x3+x4-6x5
x8 = 2-x1+x3-2x4-x5
Переходим к основному алгоритму симплекс-метода.
Поскольку задача решается на максимум, то переменную для включения в текущий план выбирают по максимальному положительному числу в уравнении для x0.
max(6,1,2,2,10,0,0,0) = 10
x0 = -14+6x1+x2+2x3+2x4+10x5
x6 = 5-2x1-x2-x3-x4-3x5
x7 = 7-3x1-2x3+x4-6x5
x8 = 2-x1+x3-2x4-x5
В качестве новой переменной выбираем x5.
Вычислим значения D5 по всем уравнениям для этой переменной.

bi / ai5

и из них выберем наименьшее:
min (5 : 3 , 7 : 6 , 2 : 1 ) = 11/6
Вместо переменной x7 в план войдет переменная x5.
Выразим переменную x5 через x7
x5 = 11/6-1/2x1-1/3x3+1/6x4-1/6x7
и подставим во все выражения.
x0 = -14+6x1+x2+2x3+2x4+10(11/6-1/2x1-1/3x3+1/6x4-1/6x7)
x6 = 5-2x1-x2-x3-x4-3(11/6-1/2x1-1/3x3+1/6x4-1/6x7)
x8 = 2-x1+x3-2x4-(11/6-1/2x1-1/3x3+1/6x4-1/6x7)
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = -21/3+x1+x2-11/3x3+32/3x4-12/3x7
x6 = 11/2-1/2x1-x2-11/2x4+1/2x7
x5 = 11/6-1/2x1-1/3x3+1/6x4-1/6x7
x8 = 5/6-1/2x1+11/3x3-21/6x4+1/6x7
Полагая небазисные переменные x = (6, 5, 8) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (-1, -1, 11/3, -32/3, 0, 0, 12/3,0), x0 = -21/3
max(1,1,-11/3,32/3,0,0,-12/3,0)= 32/3
x0 = -21/3+x1+x2-11/3x3+32/3x4-12/3x7
x6 = 11/2-1/2x1-x2-11/2x4+1/2x7
x5 = 11/6-1/2x1-1/3x3+1/6x4-1/6x7
x8 = 5/6-1/2x1+11/3x3-21/6x4+1/6x7
В качестве новой переменной выбираем x4. <з> Вычислим значения D4 по всем уравнениям для этой переменной.
bi / ai4

и из них выберем наименьшее:
min (11/2 : 11/2 , - , 5/6 : 21/6) = 5/13
Вместо переменной x8 в план войдет переменная x4.
Выразим переменную x4 через x8
x4 = 5/13-3/13x1+8/13x3+1/13x7-6/13x8
и подставим во все выражения.
x0=-21/3+x1+x2-11/3x3+32/3(5/13-3/13x1+8/13x3+1/13x7-6/13x8)-12/3x7
x6=11/2-1/2x1-x2-11/2(5/13-3/13x1+8/13x3+1/13x7-6/13x8)+1/2x7
x5=11/6-1/2x1-1/3x3+1/6(5/13-3/13x1+8/13x3+1/13x7-6/13x8)-1/6x7
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = -12/13+2/13x1+x2+12/13x3-15/13x7-19/13x8
x6 = 12/13-2/13x1-x2-12/13x3+5/13x7+9/13x8
x5 = 13/13-7/13x1-3/13x3-2/13x7-1/13x8
x4 = 5/13-3/13x1+8/13x3+1/13x7-6/13x8
Полагая небазисные переменные x = (6, 5, 4) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (-2/13, -1, -12/13, 0, 0, 0, 15/13, 19/13),x0 = -12/13
max(2/13,1,12/13,0,0,0,-15/13,-19/13)= 1
x0 = -12/13+2/13x1+x2+12/13x3-15/13x7-19/13x8
x6 = 12/13-2/13x1-x2-12/13x3+5/13x7+9/13x8
x5 = 13/13-7/13x1-3/13x3-2/13x7-1/13x8
x4 = 5/13-3/13x1+8/13x3+1/13x7-6/13x8
В качестве новой переменной выбираем x2.
Вычислим значения D2 по всем уравнениям для этой переменной.
bi / ai2

и из них выберем наименьшее:
min (12/13 : 1 , - , - ) = 12/13
Вместо переменной x6 в план войдет переменная x2.
Выразим переменную x2 через x6
x2 = 12/13-2/13x1-12/13x3-x6+5/13x7+9/13x8
и подставим во все выражения.
x0=-12/13+2/13x1+(12/13-2/13x1-12/13x3-x6+5/13x7+9/13x8)+12/13x3-15/13x7-19/13x8
x5 = 13/13-7/13x1-3/13x3-2/13x7-1/13x8
x4 = 5/13-3/13x1+8/13x3+1/13x7-6/13x8
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = 0-x6-x7-x8
x2 = 12/13-2/13x1-12/13x3-x6+5/13x7+9/13x8
x5 = 13/13-7/13x1-3/13x3-2/13x7-1/13x8
x4 = 5/13-3/13x1+8/13x3+1/13x7-6/13x8
Полагая небазисные переменные x = (2, 5, 4) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (0, 0, 0, 0, 0, 1, 1, 1), x0 = 0
Выражение для x0 не содержит положительных элементов. Найден оптимальный план.
x0 = 0-x6-x7-x8
x2 = 12/13-2/13x1-12/13x3-x6+5/13x7+9/13x8
x5 = 13/13-7/13x1-3/13x3-2/13x7-1/13x8
x4 = 5/13-3/13x1+8/13x3+1/13x7-6/13x8

На этом первый этап (первая фаза) симплекс-метода завершен. Переходим ко второму этапу. Удаляем переменные с искусственными переменными.
x2 = 12/13-2/13x1-12/13x3
x5 = 13/13-7/13x1-3/13x3
x4 = 5/13-3/13x1+8/13x3

Выразим базисные переменные:
x5 = 13/13-7/13x1-3/13x3
x4 = 5/13-3/13x1+8/13x3
которые подставим в целевую функцию:
F(X) =  + 3x3-2(5/13-3/13x1+8/13x3)-(13/13-7/13x1-3/13x3)
или
F(X) = -2+x1+2x3
Получаем новую систему переменных.
x0 = -2+x1+2x3
x2 = 12/13-2/13x1-12/13x3
x5 = 13/13-7/13x1-3/13x3
x4 = 5/13-3/13x1+8/13x3
max(1,0,2,0,0) = 2
x0 = -2+x1+2x3
x2 = 12/13-2/13x1-12/13x3
x5 = 13/13-7/13x1-3/13x3
x4 = 5/13-3/13x1+8/13x3
В качестве новой переменной выбираем x3.
Вычислим значения D3 по всем уравнениям для этой переменной.

bi / ai3

и из них выберем наименьшее:
min (12/13 : 12/13 , 13/13 : 3/13, - ) = 1
Вместо переменной x2 в план войдет переменная x3.
Выразим переменную x3 через x2
x3 = 1-1/6x1-11/12x2
и подставим во все выражения.
x0 = -2+x1+2(1-1/6x1-11/12x2)
x5 = 13/13-7/13x1-3/13(1-1/6x1-11/12x2)
x4 = 5/13-3/13x1+8/13(1-1/6x1-11/12x2)
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = 0+2/3x1-21/6x2
x3 = 1-1/6x1-11/12x2
x5 = 1-1/2x1+1/4x2
x4 = 1-1/3x1-2/3x2
Полагая небазисные переменные x = (3, 5, 4) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (-2/3, 21/6, 0, 0, 0), x0 = 0
max(2/3,-21/6,0,0,0) = 2/3
x0 = 0+2/3x1-21/6x2
x3 = 1-1/6x1-11/12x2
x5 = 1-1/2x1+1/4x2
x4 = 1-1/3x1-2/3x2
В качестве новой переменной выбираем x1.
Вычислим значения D1 по всем уравнениям для этой переменной.
bi / ai1

и из них выберем наименьшее:
min (1 : 1/6 , 1 : 1/2 , 1 : 1/3 ) = 2
Вместо переменной x5 в план войдет переменная x1.
Выразим переменную x1 через x5
x1 = 2+1/2x2-2x5
и подставим во все выражения.
x0 = 0+2/3(2+1/2x2-2x5)-21/6x2
x3 = 1-1/6(2+1/2x2-2x5)-11/12x2
x4 = 1-1/3(2+1/2x2-2x5)-2/3x2
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = 11/3-15/6x2-11/3x5
x3 = 2/3-11/6x2+1/3x5
x1 = 2+1/2x2-2x5
x4 = 1/3-5/6x2+2/3x5
Полагая небазисные переменные x = (3, 1, 4) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (0, 15/6, 0, 0, 11/3), x0 = 11/3
Выражение для x0 не содержит положительных элементов. Найден оптимальный план.
Окончательный вариант системы уравнений:
x0 = 11/3-15/6x2-11/3x5
x3 = 2/3-11/6x2+1/3x5
x1 = 2+1/2x2-2x5
x4 = 1/3-5/6x2+2/3x5

Оптимальный план можно записать так:
x1 = 2
x3 = 2/3
x4 = 1/3
F(X) = 3•2/3 + 0•2 = 11/3

Примечание:

  1. Число операций в симплекс-методе не превосходит n!/((n-m)!*m!)
  2. Решение х системы уравнений, в котором все небазисные переменные равны 0, называется базисным решение.
  3. Если все компоненты базисного решения неотрицательны, то оно называется допустимым базисным решение или опорным планом.

M-задача

Болит горло
Как быстро вылечить ангину, гланды, тонзиллит
Природные средства, проверенные временем и врачами
Подробнее
ЕГЭ по математике
Yandex.Просвещение представляет бесплатные видеокурсы по ЕГЭ с возможностью прохождения тестов
Подробнее
Транспортная задача
Используя метод минимального тарифа, представить первоначальный план для решения транспортной задачи. Проверить на оптимальность, используя метод потенциалов. Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
1234b
112436
243858
3276310
a4688 
Решить онлайн