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


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

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

2x1-x2+7x3+11x4+5x5→min
Условия:

2x1+5x3+x4+8x5=12
-3x1+6x2+2x3-2x4≤5

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

2x1+5x3+x4+8x5+R1=12
-3x1+6x2+2x3-2x4+X6=5

Переходим к формированию исходной симплекс таблицы. В строку F таблицы заносятся коэффициенты целевой функции.

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

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

X1 X2 X3 X4 X5 Своб член
F 2 -1 7 11 5 0
R1 2 0 5 0 8 12
X6 -3 6 2 -2 0 5
M -2 0 -5 0 -8 -12


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

X1 X2 X3 X4 Своб член
F 0.75 -1 3.875 11 -7.5
X5 0.25 0 0.625 0 1.5
X6 -3 6 2 -2 5
M 0 0 0 0 0

В строке M отрицательные элементы отсутствуют. Рассмотрим строку F в которой имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке F максимальный по модулю отрицательный элемент - это -1 Ведущей строкой будет та для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X6, а ведущий элемент: 6.

X1 X6 X3 X4 Своб член
F 0.25 0.167 4.208 10.667 -6.667
X5 0.25 0 0.625 0 1.5
X2 -0.5 0.167 0.333 -0.333 0.833
M 0 0 0 0 0


Так как исходной задачей был поиск минимума, оптимальное решение есть свободный член строки F, взятый с противоположным знаком. Найдено оптимальное решение F=6.667
при значениях переменных равных: X5=1.5, X2=0.833,

Назад



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