Тема №4209 Симплекс метод примеры
Поиск задачи:

Рассмотрим тему Симплекс метод примеры из предмета Математика и все вопросы которые связанны с ней. Из представленного текста вы познакомитесь с Симплекс метод примеры, узнаете ключевые особенности и основные понятия.

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

Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве b1 = 240, b2 = 200, b3 = 160 единиц. При этом для продажи 1 группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве a11 = 2 единицы, ресурса второго вида в количестве a21 = 4 единицы, ресурса третьего вида в количестве a31 = 4 единицы. Для продажи 2 и 3 групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве a12 = 3, a13 = 6 единицы, ресурса второго вида в количестве a22 = 2, a23 = 4 единицы, ресурса третьего вида в количестве a32 = 6, a33 = 8 единиц. Прибыль от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно c1 = 4, c2 = 5, c3 = 4 (тыс. руб.). Определить плановый объем и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной.

К прямой задаче планирования товарооборота, решаемой симплекс методом, составитьдвойственную задачу линейного программирования. 
Установить сопряженные пары переменных прямой и двойственной задачи. 
Согласно сопряженным парам переменных из решения прямой задачи получить решение двойственной задачи, в которой производится оценка ресурсов, затраченных на продажу товаров.

Решение задачи симплекс методом

Пусть x1, x2, x3 - количество реализованных товаров, в тыс. руб., 1, 2, 3 - ей групп, соответственно. Тогда математическая модель задачи имеет вид:

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

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

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

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

delim{lbrace}{matrix{3}{1}{{2x_1 + 3x_2 + 6x_3 + x_4=240} {4x_1 + 2x_2 + 4x_3 + x_5=200} {4x_1 + 6x_2 + 8x_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} {~6~} {~1~} {~0~} {~0~} {~80~} {0} x_5 {~200~} {~4~} {2} {~4~} {~0~} {~1~} {~0~} {~100~} {0} x_6 {~160~} {~4~} underline{~6~} {~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~} {~6 minus 3 dot 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~} {~4 minus 2 dot 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~} {~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

6 minus 3 dot 4/3 = 6 minus 4~ = ~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

4 minus 2 dot 4/3 = 4 minus 8/3~ = ~{ 4 dot 3 minus 8 }/{ 3 }~ = ~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~} {~2~} {~1~} {~0~} {~{ minus 1/2}~} {~ minus ~} {0} x_5 {~440/3~} {8/3} {~0~} {~4/3~} {~0~} {~1~} {~{ minus 1/3}~} {~55~} {5} x_2 {~80/3~} underline{~2/3~} {~1~} {~4/3~} {~0~} {~0~} {~1/6~} underline{~40~} {~} Delta_i {400/3} underline{{ minus 2/3}} {0} {8/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 = 8/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

Поскольку есть отрицательная оценка Δ1 = – 2/3, то план не оптимален.

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

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

Q_1 = {160}/{0}= infty

Q_2 = {440/3}/{8/3}=55

Q_3 = {80/3}/{2/3}=40

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

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

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 {~160~} {~0~} {~0~} {~2~} {~1~} {~0~} {~{ minus 1/2}~} {~} {0} x_5 {~440/3 minus 8/3 dot 40~} {~8/3 minus 8/3 dot 1~} {~0 minus 8/3 dot 3/2~} {~4/3 minus 8/3 dot 2~} {~0 minus 8/3 dot 0~} {~1 minus 8/3 dot 0~} {~{ minus 1/3} minus 8/3 dot 1/4~} {~} {4} x_1 {~40~} {~1~} {~3/2~} {~2~} {~0~} {~0~} {~1/4~} {~} }

Вычисляем:

440/3 minus 8/3 dot 40 = 440/3 minus 320/3~ = ~120/3~ = ~40

8/3 minus 8/3 dot 1 = 8/3 minus 8/3~ = ~0

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

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

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

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

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~} {~2~} {~1~} {~0~} {~{ minus 1/2}~} {~} {0} x_5 {~40~} {~0~} {~{ minus 4}~} {~{ minus 4}~} {~0~} {~1~} {~{ minus 1}~} {~} {4} x_1 {~40~} {~1~} {~3/2~} {~2~} {~0~} {~0~} {~1/4~} {~} {~} Delta_i {160} {0} {1} {4} {0} {0} {1} {~} }

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

F = sum{i=1}3{C_i dot b_i} =0 · 160 + 0 · 40 + 4 · 40 = 160

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

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

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

Поскольку отрицательных оценок нет, то план оптимален.

Решение задачи: x1 = 40; x2 = 0; x3 = 0; x4 = 160; x5 = 40; x6 = 0; Fmax = 160

Ответ

x1 = 40; x2 = 0; x3 = 0; x4 = 160; x5 = 40; x6 = 0; Fmax = 160

То есть необходимо реализовать товар первого вида в объеме 40 тыс. руб. Товар 2-го и 3-го видов реализовывать не надо. При этом максимальная прибыль составит Fmax = 160 тыс. руб.

 

Решение двойственной задачи

Двойственная задача имеет вид:

Z = 240·y1 + 200·y2 + 160·y3 –>min

delim{lbrace}{matrix{4}{1}{{2y_1 + 4y_2 + 4y_3>=4} {3y_1 + 2y_2 + 6y_3>=5} {6y_1 + 4y_2 + 8y_3>=4} {y_1, y_2, y_3>= 0}}}{~}

Вводим дополнительные переменные y4 ≥ 0, y5 ≥ 0, y6 ≥ 0, чтобы неравенства преобразовать в равенства.

delim{lbrace}{matrix{3}{1}{{2y_1 + 4y_2 + 4y_3 minus y_4=4} {3y_1 + 2y_2 + 6y_3 minus y_5=5} {6y_1 + 4y_2 + 8y_3 minus y_6=4} }}{~}

Сопряженные пары переменных прямой и двойственной задач имеют вид:

Основные Дополнительные
x1 x2 x3 x4 x5 x6
y4 y5 y6 y1 y2 y3
Дополнительные Основные

Из последней симплекс таблицы № 3 прямой задачи, находим решение двойственной задачи:

Zmin = Fmax = 160;
y1 = Δ4 = 0; y2 = Δ5 = 0; y3 = Δ6 = 1; y4 = Δ1 = 0; y5 = Δ2 = 1; y6 = Δ3 = 4;

Ответ

y1 = 0; y2 = 0; y3 = 1; Zmin = 160;


Категория: Математика | Добавил: Админ (10.11.2015) Просмотров: | Рейтинг: 0.0/0

Другие задачи:
Всего комментариев: 0
avatar