Олег ОдинцовОбыкновенные дифференциальные уравнения
Справочник по элементарным функциям
Методы вычисления неопределенных интегралов

Пример отсутствия решения задачи, решаемой симплекс методом

Рассмотрен пример решения задачи симплекс методом, в которой отсутствует решение - целевая функция может принимать сколь угодно большое значение.

Условие задачи

Математическая модель задачи:

F = 4·x1 + 5·x2 + 4·x3 –>max

delim{lbrace}{matrix{4}{1}{{2x_1 + 3x_2{ minus 6}x_3<=240} {4x_1 + 2x_2{ minus 4}x_3<=200} {4x_1 + 6x_2{ minus 8}x_3<=160} {x_1, x_2, x_3>= 0}}}{~}

Решаем симплекс методом.

Вводим дополнительные переменные x4 ≥ 0, x5 ≥ 0, x6 ≥ 0, чтобы неравенства преобразовать в равенства.

delim{lbrace}{matrix{3}{1}{{2x_1 + 3x_2{ minus 6}x_3 + x_4=240} {4x_1 + 2x_2{ minus 4}x_3 + x_5=200} {4x_1 + 6x_2{ minus 8}x_3 + x_6=160} }}{~}

В качестве базиса возьмем x4 = 240; x5 = 200; x6 = 160.

Данные заносим в симплекс таблицу

Симплекс таблица № 1

tabular{1111111}{11111111111}{ {~} C_i {~} {4} {5} {4} {0} {0} {0} {~} C_i {~} b_i x_1 x_2 x_3 x_4 x_5 x_6 Q {0} x_4 {~240~} {~2~} {3} {~{ minus 6}~} {~1~} {~0~} {~0~} {~80~} {0} x_5 {~200~} {~4~} {2} {~{ minus 4}~} {~0~} {~1~} {~0~} {~100~} {0} x_6 {~160~} {~4~} underline{~6~} {~{ minus 8}~} {~0~} {~0~} {~1~} underline{~26.667~} {~} Delta_i {0} {{ minus 4}} underline{{ minus 5}} {{ minus 4}} {0} {0} {0} {~} }

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

F = sum{i=1}3{C_i dot b_i} =0 · 240 + 0 · 200 + 0 · 160 = 0

Вычисляем оценки по формуле:

Delta_j = sum{i=1}3{C_i dot a_ij} minus C_j

Δ1 = 0 · 2 + 0 · 4 + 0 · 4 – 4 = – 4
Δ2 = 0 · 3 + 0 · 2 + 0 · 6 – 5 = – 5
Δ3 = 0 · (–6) + 0 · (–4) + 0 · (–8) – 4 = – 4
Δ4 = 0 · 1 + 0 · 0 + 0 · 0 – 0 = 0
Δ5 = 0 · 0 + 0 · 1 + 0 · 0 – 0 = 0
Δ6 = 0 · 0 + 0 · 0 + 0 · 1 – 0 = 0

Поскольку есть отрицательные оценки, то план не оптимален. Наименьшая оценка:

Δ2 = – 5

Вводим переменную x2 в базис.

Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение Q_i = {b_i}/{a_i2} для столбца x2.

Q_1 = {240}/{3}=80

Q_2 = {200}/{2}=100

Q_3 = {160}/{6}=80/3 = 26.667

Наименьшее неотрицательное: Q3 = 26.667. Выводим переменную x6 из базиса

3-ю строку делим на 6.
Из 1-й строки вычитаем 3-ю строку, умноженную на 3
Из 2-й строки вычитаем 3-ю строку, умноженную на 2

tabular{111111}{11111111111}{ {~} C_i {~} {4} {5} {4} {0} {0} {0} {~} C_i {~} b_i x_1 x_2 x_3 x_4 x_5 x_6 Q {0} x_4 {~240 minus 3 dot 80/3~} {~2 minus 3 dot 2/3~} {~3 minus 3 dot 1~} {~{ minus 6} minus 3 dot ( minus 4)/3~} {~1 minus 3 dot 0~} {~0 minus 3 dot 0~} {~0 minus 3 dot 1/6~} {~} {0} x_5 {~200 minus 2 dot 80/3~} {~4 minus 2 dot 2/3~} {~2 minus 2 dot 1~} {~{ minus 4} minus 2 dot ( minus 4)/3~} {~0 minus 2 dot 0~} {~1 minus 2 dot 0~} {~0 minus 2 dot 1/6~} {~} {5} x_2 {~80/3~} {~2/3~} {~1~} {~{ minus 4/3}~} {~0~} {~0~} {~1/6~} {~} }

Вычисляем:

240 minus 3 dot 80/3 = 240 minus 80~ = ~160

2 minus 3 dot 2/3 = 2 minus 2~ = ~0

{ minus 6} minus 3 dot ( minus 4)/3 = { minus 6} + 4~ = ~{ minus 2}

200 minus 2 dot 80/3 = 200 minus 160/3~ = ~{ 200 dot 3 minus 160 }/{ 3 }~ = ~440/3

4 minus 2 dot 2/3 = 4 minus 4/3~ = ~{ 4 dot 3 minus 4 }/{ 3 }~ = ~8/3

{ minus 4} minus 2 dot ( minus 4)/3 = { minus 4} + 8/3~ = ~{ ( minus 4) dot 3 + 8 }/{ 3 }~ = ~{ minus 4/3}

Получаем новую таблицу:

Симплекс таблица № 2

tabular{1111111}{11111111111}{ {~} C_i {~} {4} {5} {4} {0} {0} {0} {~} C_i {~} b_i x_1 x_2 x_3 x_4 x_5 x_6 Q {0} x_4 {~160~} {~0~} {~0~} {{ minus 2}} {~1~} {~0~} {~{ minus 1/2}~} {~ minus ~} {0} x_5 {~440/3~} {~8/3~} {~0~} {{ minus 4/3}} {~0~} {~1~} {~{ minus 1/3}~} {~ minus ~} {5} x_2 {~80/3~} {~2/3~} {~1~} {{ minus 4/3}} {~0~} {~0~} {~1/6~} {~ minus ~} {~} Delta_i {400/3} {{ minus 2/3}} {0} underline{{ minus 32/3}} {0} {0} {5/6} {~} }

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

F = sum{i=1}3{C_i dot b_i} =0 · 160 + 0 · 440/3 + 5 · 80/3 = 400/3

Вычисляем оценки по формуле:

Delta_j = sum{i=1}3{C_i dot a_ij} minus C_j

Δ1 = 0 · 0 + 0 · 8/3 + 5 · 2/3 – 4 = – 2/3
Δ2 = 0 · 0 + 0 · 0 + 5 · 1 – 5 = 0
Δ3 = 0 · (–2) + 0 · (–4)/3 + 5 · (–4)/3 – 4 = – 32/3
Δ4 = 0 · 1 + 0 · 0 + 5 · 0 – 0 = 0
Δ5 = 0 · 0 + 0 · 1 + 5 · 0 – 0 = 0
Δ6 = 0 · (–1)/2 + 0 · (–1)/3 + 5 · 1/6 – 0 = 5/6

Поскольку есть отрицательные оценки, то план не оптимален. Наименьшая оценка:

Δ3 = – 32/3

Вводим переменную x3 в базис.

Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение Q_i = {b_i}/{a_i3} для столбца x3.

Q_1 = {160}/{{ minus 2}}={ minus 80} < 0

Q_2 = {440/3}/{{ minus 4/3}}={ minus 110} < 0

Q_3 = {80/3}/{{ minus 4/3}}={ minus 20} < 0

Поскольку среди оценок нет неотрицательных, то решения не существует. Целевая функция может быть сделана сколь угодно большой.

Ответ: Решения задачи не существует. Целевая функция может быть сколь угодно большой.

Опубликовано:


Яндекс.Метрика
Rambler's Top100
Олег Одинцов © 1cov-edu.ru