2015-08-21
347Целевая функция:
2X1+9X2+1X3-1X4+5X5→max
Условия:
9X1-2X2-3X3+2X4-5X5=5
6X1-1X2-2X3+1X4-5X5=1
-8X1+4X2+3X3-1X4+9X5=3
Приведем систему ограничений к каноническому виду, для этого необходимо неравенства преобразовать в равенства, с добавлением дополнительных переменных. Если в преобразуемом неравенстве стоит знак ≥, то при переходе к равенству знаки всех его коэффициентов и свободных членов меняются на противоположные. Тогда система запишется в виде:
9X1-2X2-3X3+2X4-5X5+R1=5
6X1-1X2-2X3+1X4-5X5+R2=1
-8X1+4X2+3X3-1X4+9X5+R3=3
Переходим к формированию исходной симплекс таблицы. В строку F таблицы заносятся коэффициенты целевой функции. Так как нам необходимо найти максимум целевой функции, то в таблицу заносятся коэффициенты с противоположным знаком
Так как среди исходного набора условий были равенства, мы ввели искуственные переменные R. Это значит, что в симплекс таблицу нам необходимо добавить дополнительную строку M, элементы которой расчитываются как сумма соответствующих элементов условий-равенств (тех которые после приведения к каноническому виду содержат искусственные переменные R) взятая с противоположным знаком.
|
|
|
Из данных задачи составляем исходную симплекс таблицу.
| X1 | X2 | X3 | X4 | X5 | Своб член | |
| F | -2 | -9 | -1 | -5 | ||
| R1 | -2 | -3 | -5 | |||
| R2 | -1 | -2 | -5 | |||
| R3 | -8 | -1 | ||||
| M | -7 | -1 | -2 | -9 |
Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение.В строке M имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -7 Ведущей строкой будет та для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R2, а ведущий элемент: 6.
| X2 | X3 | X4 | X5 | Своб член | |
| F | -9 | -2 | -7 | ||
| R1 | -1 | ||||
| X1 | -0 | -0 | -1 | ||
| R3 | |||||
| M | -2 | -0 | -1 | -5 | -8 |
В строке M имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -5 Ведущей строкой будет та для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R1, а ведущий элемент: 3.
| X2 | X3 | X4 | Своб член | |
| F | -11 | -2 | ||
| X5 | -0 | |||
| X1 | -0 | -0 | ||
| R3 | -0 | |||
| M | -3 | -0 | -1 |
В строке M имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -3 Ведущей строкой будет та для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R3, а ведущий элемент: 3.
|
|
|
| X3 | X4 | Своб член | |
| F | -1 | ||
| X5 | |||
| X1 | -0 | ||
| X2 | -0 | ||
| M | -0 | -0 | -0 |
В строке M имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -0 Ведущей строкой будет та для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X2, а ведущий элемент: 0.
| X2 | X4 | Своб член | |
| F | |||
| X5 | -0 | ||
| X1 | |||
| X3 | -0 | ||
| M | -0 | -0 |
В строке M имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -0 Ведущей строкой будет та для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X5, а ведущий элемент: 0.
| X2 | X5 | Своб член | |
| F | -10 | ||
| X4 | -1 | ||
| X1 | -1 | ||
| X3 | |||
| M | -0 |
В строке M отрицательные элементы отсутствуют. Рассмотрим строку F в которой имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке F максимальный по модулю отрицательный элемент - это -10 Ведущей строкой будет та для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X4, а ведущий элемент: 5.
| X2 | X4 | Своб член | |
| F | |||
| X5 | -0 | ||
| X1 | |||
| X3 | -0 | ||
| M | -0 | -0 |
Так как в строке F нет отрицательных элементов, то найдено оптимальное решение F=15
при значениях переменных равных: X5=1, X1=2, X3=3,
