Главная|Решения онлайн |Теория | Основные формулы и обозначения |Обратная связь |


Метод искусственного базиса (Симплекс-метод) - Пример 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 0
X5 2 7 1 0 5
R1 1 4 2 8 6
R2 -1 0 2 5 9
M 0 -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) были исключены из базиса (условия исходной задачи не совместны).

 

Назад



R336709263964 - WebMoney 41001419134483 - Яндекс Деньги
WebMoneyПонравился сайт? Окажите помощь в развитиияндекс