Пример — Табличный симплекс метод

Необходимо решить задачу линейного программирования.

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

2x 1+5x2+3x3+8x4 →min

Ограничивающие условия:

3x1+6x2-4x3+x4≤12
4x1-13x2+10x3+5x4≥6
3x1+7x2+x3≥1

Приведем систему ограничений к каноническому виду, для этого необходимо перейти от неравенств к равенствам, с добавлением дополнительных переменных.

Так как наша задача — задача минимизации, то нам необходимо преобразовать ее к задаче на поиск максимума. Для этого изменим знаки коэффициентов целевой функции на противоположные. Элементы первого неравенства записываем без изменений, добавив в него дополнительную переменную x5 и изменив знак «≤» на «=». Т. к. второе и третье неравенства имеют знаки «≥» необходимо поменять знаки их коэффициентов на противоположные и внести в них дополнительные переменные x6 и x7 соответственно. В результате получем эквивалентную задачу:

3x1+6x2-4x3+x4+x5=12
-4x1+13x2-10x3-5x4+x6=-6
-3x1-7x2-x3+x7=-1

Читайте также  Линейная корреляция. Нормальная корреляция

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

x1
x2
x3
x4
Своб член
F
2
5
3
8
X5
3
6
-4
1
12
X6
-4
13
-10
-5
-6
X7
-3
-7
-1
-1

В составленой нами таблице имеются отрицательные элементы в столбце свободных членов, находим среди них максимальный по модулю — это элемент: -6, он задает ведущую строку — X6. В этой строке так же находим максимальный по модулю отрицательный элемент: -10 он находится в столбце X3 который будет ведущим столбцом. Переменная в ведущей строке исключается из базиса, а переменная соответсвующая ведущему столцу включается в базис. Пересчитаем симплекс-таблицу:

X1 X2 X6 X4 Своб член
F 0.8 8.9 0.3 6.5 -1.8
X5 4.6 0.8 -0.4 3 14.4
X3 0.4 -1.3 -0.1 0.5 0.6
X7 -2.6 -8.3 -0.1 0.5 -0.4
Читайте также  Линейное программирование

В составленой нами таблице имеются отрицательные элементы в столбце свободных членов, находим среди них максимальный по модулю — это элемент: -0.4, он задает ведущую строку — X7. В этой строке так же находим максимальный по модулю отрицательный элемент: -8.3 он находится в столбце X2 который будет ведущим столбцом. Переменная в ведущей строке исключается из базиса, а переменная соответсвующая ведущему столцу включается в базис. Пересчитаем симплекс-таблицу:

X1 X7 X6 X4 Своб член
F -1.988 1.072 0.193 7.036 -2.229
X5 4.349 0.096 -0.41 3.048 14.361
X3 0.807 -0.157 -0.084 0.422 0.663
X2 0.313 -0.12 0.012 -0.06 0.048

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

Читайте также  Главная медиана графа
X2 X7 X6 X4 Своб член
F 6.351 0.31 0.269 6.655 -1.924
X5 -13.895 1.763 -0.577 3.882 13.694
X3 -2.578 0.152 -0.115 0.577 0.539
X1 3.195 -0.383 0.038 -0.192 0.153

Так как в строке F нет отрицательных элементов, то
найдено оптимальное решение. Так как исходной задачей был поиск минимума, то оптимальным решением будет свободный член строки F, взятый с противоположным знаком. F=1.924
при значениях переменных равных: x3=0.539, x1=0.153. Переменные x2 и x4 не входят в базис, поэтому x2=0 x4=0.

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