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

Пример решения задачи симплекс М-методом

Рассмотрен пример решения задачи, в которой начальный базис находится симплекс М методом.

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

Найти оптимальные величины производства продукции видов А, Б и В. Затраты сырья на единицу продукции: А – 5, Б – 2, В – 4. Объем сырья – 2000 единиц. Затраты оборудования на единицу продукции: А – 4, Б – 5, В – 4. Объем оборудования – 1000 единиц. Прибыль от реализации единицы продукции: А – 10, Б – 8, В – 12. Критерий – максимум прибыли предприятия. Производство продукции А должно быть не менее 100 ед. Производство продукции Б должно быть не менее 50 ед.

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

1) Определение оптимального плана производства

Пусть x1, x2, x3 - количество произведенной продукции вида А, Б, В, соответственно. Тогда математическая модель задачи имеет вид:

F = 10·x1 + 8·x2 + 12·x3 –>max

delim{lbrace}{matrix{5}{1}{{5x_1 + 2x_2 + 4x_3<=2000} {4x_1 + 5x_2 + 4x_3<=1000} {x_1>=100} {x_2>=50} {x_1, x_2, x_3>= 0}}}{~}

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

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

delim{lbrace}{matrix{4}{1}{{5x_1 + 2x_2 + 4x_3 + x_4=2000} {4x_1 + 5x_2 + 4x_3 + x_5=1000} {x_1 minus x_6=100} {x_2 minus x_7=50} }}{~}

Чтобы выбрать начальный базис, вводим искусственные переменные x8 ≥ 0, x9 ≥ 0 и очень большое число M (M –> ∞). Решаем М методом.

F = 10·x1 + 8·x2 + 12·x3 + 0·x4 + 0·x5 + 0·x6 + 0·x7– M·x8– M·x9 –>max

delim{lbrace}{matrix{5}{1}{{5x_1 + 2x_2 + 4x_3 + x_4=2000} {4x_1 + 5x_2 + 4x_3 + x_5=1000} {x_1 minus x_6 + x_8=100} {x_2 minus x_7 + x_9=50} {x_1, x_2, x_3, x_4, x_5, x_6, x_7, x_8, x_9>= 0}}}{~}

В качестве базиса возьмем x4 = 2000; x5 = 1000; x8 = 100; x9 = 50.

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

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

tabular{11111111}{11111111111111}{ {~} C_i {~} {10} {8} {12} {0} {0} {0} {0} {minus M} {minus M} {~} C_i {~} b_i x_1 x_2 x_3 x_4 x_5 x_6 x_7 x_8 x_9 Q {0} x_4 {~2000~} {5} {~2~} {~4~} {~1~} {~0~} {~0~} {~0~} {~0~} {~0~} {~400~} {0} x_5 {~1000~} {4} {~5~} {~4~} {~0~} {~1~} {~0~} {~0~} {~0~} {~0~} {~250~} {minus M} x_8 {~100~} underline{~1~} {~0~} {~0~} {~0~} {~0~} {~{ minus 1}~} {~0~} {~1~} {~0~} underline{~100~} {minus M} x_9 {~50~} {0} {~1~} {~0~} {~0~} {~0~} {~0~} {~{ minus 1}~} {~0~} {~1~} {~ minus ~} {~} Delta_i {{ minus 150}M} underline{minus M{ minus 10}} {minus M{ minus 8}} {{ minus 12}} {0} {0} {M} {M} {0} {0} {~} }

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

F = sum{i=1}4{C_i dot b_i} =0 · 2000 + 0 · 1000 + (– M) · 100 + (– M) · 50 = – 150M

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

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

Δ1 = 0 · 5 + 0 · 4 + (– M) · 1 + (– M) · 0 – 10 = – M – 10
Δ2 = 0 · 2 + 0 · 5 + (– M) · 0 + (– M) · 1 – 8 = – M – 8
Δ3 = 0 · 4 + 0 · 4 + (– M) · 0 + (– M) · 0 – 12 = – 12
Δ4 = 0 · 1 + 0 · 0 + (– M) · 0 + (– M) · 0 – 0 = 0
Δ5 = 0 · 0 + 0 · 1 + (– M) · 0 + (– M) · 0 – 0 = 0
Δ6 = 0 · 0 + 0 · 0 + (– M) · (–1) + (– M) · 0 – 0 = M
Δ7 = 0 · 0 + 0 · 0 + (– M) · 0 + (– M) · (–1) – 0 = M
Δ8 = 0 · 0 + 0 · 0 + (– M) · 1 + (– M) · 0 – (– M) = 0
Δ9 = 0 · 0 + 0 · 0 + (– M) · 0 + (– M) · 1 – (– M) = 0

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

Δ1 = – M – 10

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

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

Q_1 = {2000}/{5}=400

Q_2 = {1000}/{4}=250

Q_3 = {100}/{1}=100

Q_4 = {50}/{0}= infty

Наименьшее неотрицательное: Q3 = 100. Выводим переменную x8 из базиса. Для этого над строками таблицы выполняем линейные преобразования.

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

tabular{1111111}{11111111111111}{ {~} C_i {~} {10} {8} {12} {0} {0} {0} {0} {minus M} {minus M} {~} C_i {~} b_i x_1 x_2 x_3 x_4 x_5 x_6 x_7 x_8 x_9 Q {0} x_4 {~2000 minus 5 dot 100~} {~5 minus 5 dot 1~} {~2 minus 5 dot 0~} {~4 minus 5 dot 0~} {~1 minus 5 dot 0~} {~0 minus 5 dot 0~} {~0 minus 5 dot ( minus 1)~} {~0 minus 5 dot 0~} {~0 minus 5 dot 1~} {~0 minus 5 dot 0~} {~} {0} x_5 {~1000 minus 4 dot 100~} {~4 minus 4 dot 1~} {~5 minus 4 dot 0~} {~4 minus 4 dot 0~} {~0 minus 4 dot 0~} {~1 minus 4 dot 0~} {~0 minus 4 dot ( minus 1)~} {~0 minus 4 dot 0~} {~0 minus 4 dot 1~} {~0 minus 4 dot 0~} {~} {10} x_1 {~100~} {~1~} {~0~} {~0~} {~0~} {~0~} {~{ minus 1}~} {~0~} {~1~} {~0~} {~} {minus M} x_9 {~50~} {~0~} {~1~} {~0~} {~0~} {~0~} {~0~} {~{ minus 1}~} {~0~} {~1~} {~} }

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

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

tabular{11111111}{11111111111111}{ {~} C_i {~} {10} {8} {12} {0} {0} {0} {0} {minus M} {minus M} {~} C_i {~} b_i x_1 x_2 x_3 x_4 x_5 x_6 x_7 x_8 x_9 Q {0} x_4 {~1500~} {~0~} {2} {~4~} {~1~} {~0~} {~5~} {~0~} {~{ minus 5}~} {~0~} {~750~} {0} x_5 {~600~} {~0~} {5} {~4~} {~0~} {~1~} {~4~} {~0~} {~{ minus 4}~} {~0~} {~120~} {10} x_1 {~100~} {~1~} {0} {~0~} {~0~} {~0~} {~{ minus 1}~} {~0~} {~1~} {~0~} {~ minus ~} {minus M} x_9 {~50~} {~0~} underline{~1~} {~0~} {~0~} {~0~} {~0~} {~{ minus 1}~} {~0~} {~1~} underline{~50~} {~} Delta_i {{ minus 50}M + 1000} {0} underline{minus M{ minus 8}} {{ minus 12}} {0} {0} {{ minus 10}} {M} {M + 10} {0} {~} }

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

F = sum{i=1}4{C_i dot b_i} =0 · 1500 + 0 · 600 + 10 · 100 + (– M) · 50 = – 50M + 1000

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

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

Δ1 = 0 · 0 + 0 · 0 + 10 · 1 + (– M) · 0 – 10 = 0
Δ2 = 0 · 2 + 0 · 5 + 10 · 0 + (– M) · 1 – 8 = – M – 8
Δ3 = 0 · 4 + 0 · 4 + 10 · 0 + (– M) · 0 – 12 = – 12
Δ4 = 0 · 1 + 0 · 0 + 10 · 0 + (– M) · 0 – 0 = 0
Δ5 = 0 · 0 + 0 · 1 + 10 · 0 + (– M) · 0 – 0 = 0
Δ6 = 0 · 5 + 0 · 4 + 10 · (–1) + (– M) · 0 – 0 = – 10
Δ7 = 0 · 0 + 0 · 0 + 10 · 0 + (– M) · (–1) – 0 = M
Δ8 = 0 · (–5) + 0 · (–4) + 10 · 1 + (– M) · 0 – (– M) = M + 10
Δ9 = 0 · 0 + 0 · 0 + 10 · 0 + (– M) · 1 – (– M) = 0

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

Δ2 = – M – 8

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

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

Q_1 = {1500}/{2}=750

Q_2 = {600}/{5}=120

Q_3 = {100}/{0}= infty

Q_4 = {50}/{1}=50

Наименьшее неотрицательное: Q4 = 50. Выводим переменную x9 из базиса и удаляем искусственные переменные. Выполняем линейные преобразования.

Из 1-й строки вычитаем 4-ю строку, умноженную на 2
Из 2-й строки вычитаем 4-ю строку, умноженную на 5

tabular{1111111}{111111111111}{ {~} C_i {~} {10} {8} {12} {0} {0} {0} {0} {~} C_i {~} b_i x_1 x_2 x_3 x_4 x_5 x_6 x_7 Q {0} x_4 {~1500 minus 2 dot 50~} {~0 minus 2 dot 0~} {~2 minus 2 dot 1~} {~4 minus 2 dot 0~} {~1 minus 2 dot 0~} {~0 minus 2 dot 0~} {~5 minus 2 dot 0~} {~0 minus 2 dot ( minus 1)~} {~} {0} x_5 {~600 minus 5 dot 50~} {~0 minus 5 dot 0~} {~5 minus 5 dot 1~} {~4 minus 5 dot 0~} {~0 minus 5 dot 0~} {~1 minus 5 dot 0~} {~4 minus 5 dot 0~} {~0 minus 5 dot ( minus 1)~} {~} {10} x_1 {~100~} {~1~} {~0~} {~0~} {~0~} {~0~} {~{ minus 1}~} {~0~} {~} {8} x_2 {~50~} {~0~} {~1~} {~0~} {~0~} {~0~} {~0~} {~{ minus 1}~} {~} }

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

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

tabular{11111111}{111111111111}{ {~} C_i {~} {10} {8} {12} {0} {0} {0} {0} {~} C_i {~} b_i x_1 x_2 x_3 x_4 x_5 x_6 x_7 Q {0} x_4 {~1400~} {~0~} {~0~} {4} {~1~} {~0~} {~5~} {~2~} {~350~} {0} x_5 {~350~} {~0~} {~0~} underline{~4~} {~0~} {~1~} {~4~} {~5~} underline{~87.5~} {10} x_1 {~100~} {~1~} {~0~} {0} {~0~} {~0~} {~{ minus 1}~} {~0~} {~ minus ~} {8} x_2 {~50~} {~0~} {~1~} {0} {~0~} {~0~} {~0~} {~{ minus 1}~} {~ minus ~} {~} Delta_i {1400} {0} {0} underline{{ minus 12}} {0} {0} {{ minus 10}} {{ minus 8}} {~} }

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

F = sum{i=1}4{C_i dot b_i} =0 · 1400 + 0 · 350 + 10 · 100 + 8 · 50 = 1400

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

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

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

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

Δ3 = – 12

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

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

Q_1 = {1400}/{4}=350

Q_2 = {350}/{4}=175/2 = 87.5

Q_3 = {100}/{0}= infty

Q_4 = {50}/{0}= infty

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

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

tabular{1111111}{111111111111}{ {~} C_i {~} {10} {8} {12} {0} {0} {0} {0} {~} C_i {~} b_i x_1 x_2 x_3 x_4 x_5 x_6 x_7 Q {0} x_4 {~1400 minus 4 dot 175/2~} {~0 minus 4 dot 0~} {~0 minus 4 dot 0~} {~4 minus 4 dot 1~} {~1 minus 4 dot 0~} {~0 minus 4 dot 1/4~} {~5 minus 4 dot 1~} {~2 minus 4 dot 5/4~} {~} {12} x_3 {~175/2~} {~0~} {~0~} {~1~} {~0~} {~1/4~} {~1~} {~5/4~} {~} {10} x_1 {~100~} {~1~} {~0~} {~0~} {~0~} {~0~} {~{ minus 1}~} {~0~} {~} {8} x_2 {~50~} {~0~} {~1~} {~0~} {~0~} {~0~} {~0~} {~{ minus 1}~} {~} }

Вычисляем:

1400 minus 4 dot 175/2 = 1400 minus 350~ = ~1050

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

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

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

tabular{11111111}{111111111111}{ {~} C_i {~} {10} {8} {12} {0} {0} {0} {0} {~} C_i {~} b_i x_1 x_2 x_3 x_4 x_5 x_6 x_7 Q {0} x_4 {~1050~} {~0~} {~0~} {~0~} {~1~} {~{ minus 1}~} {~1~} {~{ minus 3}~} {~} {12} x_3 {~175/2~} {~0~} {~0~} {~1~} {~0~} {~1/4~} {~1~} {~5/4~} {~} {10} x_1 {~100~} {~1~} {~0~} {~0~} {~0~} {~0~} {~{ minus 1}~} {~0~} {~} {8} x_2 {~50~} {~0~} {~1~} {~0~} {~0~} {~0~} {~0~} {~{ minus 1}~} {~} {~} Delta_i {2450} {0} {0} {0} {0} {3} {2} {7} {~} }

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

F = sum{i=1}4{C_i dot b_i} =0 · 1050 + 12 · 175/2 + 10 · 100 + 8 · 50 = 2450

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

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

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

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

Решение задачи: x1 = 100; x2 = 50; x3 = 175/2 = 87.5; x4 = 1050; x5 = 0; x6 = 0; x7 = 0; Fmax = 2450

Ответ: x1 = 100; x2 = 50; x3 = 175/2 = 87.5; x4 = 1050; x5 = 0; x6 = 0; x7 = 0; Fmax = 2450

То есть необходимо произвести x1 = 100 единиц продукции вида А, x2 = 50 единиц продукции вида Б и x3 = 87,5 единиц продукции вида В. Максимальная прибыль при этом составит Fmax = 2450 единиц.

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


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