Метод искусственного базиса (Симплекс-метод) — Пример 1

Целевая функция:

1X1+5X2+4X3-3X4→max

Условия:

2X1+7X2+1X3+0X4≤5
1X1+4X2+2X3+8X4=6
-1X1+0X2+2X3+5X4=9

Приведем систему ограничений к каноническому виду, для этого необходимо неравенства преобразовать в равенства, с добавлением дополнительных переменных. Если в преобразуемом неравенстве стоит знак ≥, то при переходе к равенству знаки всех его коэффициентов и свободных членов меняются на противоположные. Тогда система запишется в виде:

2X1+7X2+1X3+0X4+X5=5
1X1+4X2+2X3+8X4+R1=6
-1X1+0X2+2X3+5X4+R2=9
Переходим к формированию исходной симплекс таблицы. В строку F таблицы заносятся коэффициенты целевой функции. Так как нам необходимо найти максимум целевой функции, то в таблицу заносятся коэффициенты с противоположным знаком

Читайте также  Пример применения алгоритма Дейкстры

Так как среди исходного набора условий были равенства, мы ввели искуственные переменные R. Это значит, что в симплекс таблицу нам необходимо добавить дополнительную строку M, элементы которой расчитываются как сумма соответствующих элементов условий-равенств (тех которые после приведения к каноническому виду содержат искусственные переменные R) взятая с противоположным знаком.

Из данных задачи составляем исходную симплекс таблицу.

X1 X2 X3 X4 Своб член
F -1 -5 -4 3
X5 2 7 1 5
R1 1 4 2 8 6
R2 -1 2 5 9
M -4 -4 -13 -15

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение.В строке M имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент — это -13 Ведущей строкой будет та для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R1, а ведущий элемент: 8.

Читайте также  Линейная корреляция. Нормальная корреляция
X1 X2 X3 Своб член
F -1.375 -6.5 -4.75 -2.25
X5 2 7 1 5
X4 0.125 0.5 0.25 0.75
R2 -1.625 -2.5 0.75 5.25
M 1.625 2.5 -0.75 -5.25

В строке M имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент — это -0.75 Ведущей строкой будет та для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X4, а ведущий элемент: 0.25.

X1 X2 X4 Своб член
F 1 3 19 12
X5 1.5 5 -4 2
X3 0.5 2 4 3
R2 -2 -4 -3 3
M 2 4 3 -3

В столбце свободных членов и в строке F нет отрицательных элементов. Выполнение алгоритма на этом завершено, однако не все искусственные переменные (R) были исключены из базиса (условия исходной задачи не совместны).

Выполненные готовые работы

Так же вы можете купить уже выполненные похожие работы. Для удобства покупки работы размещены на независимой бирже. Подробнее об условиях покупки тут.

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...