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

Условие задачи, решаемой симплекс М методом.

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

Содержание

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

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

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

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

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

F = 10·x₁ + 8·x₂ + 12·x₃ –>max

Решаем симплекс методом.
Вводим дополнительные переменные x₄ ≥ 0, x₅ ≥ 0, x₆ ≥ 0, x₇ ≥ 0, чтобы неравенства преобразовать в равенства.

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

F = 10·x₁ + 8·x₂ + 12·x₃ + 0·x₄ + 0·x₅ + 0·x₆ + 0·x₇– M·x₈– M·x₉ –>max

В качестве базиса возьмем x₄ = 2000; x₅ = 1000; x₈ = 100; x₉ = 50.
Данные заносим в симплекс таблицу

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

$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline&C_i & & 10 & 8 & 12 & 0 & 0 & 0 & 0 & -\kern-0.2em M & -\kern-0.2em M\\ \hline C_i&b_i & &x_1&x_2&x_3&x_4&x_5&x_6&x_7&x_8&x_9&Q\\ \hline 0 & x_4 & 2000&5 & 2 & 4 & 1 & 0 & 0 & 0 & 0 & 0&400 \\ \hline0 & x_5 & 1000&4 & 5 & 4 & 0 & 1 & 0 & 0 & 0 & 0&250 \\ \hline-\kern-0.2em M & x_8 & 100&\underline{1} & 0 & 0 & 0 & 0 & { \kern-0.2em-\kern-0.2em 1} & 0 & 1 & 0&\underline{100} \\ \hline-\kern-0.2em M & x_9 & 50&0 & 1 & 0 & 0 & 0 & 0 & { \kern-0.2em-\kern-0.2em 1} & 0 & 1&- \\ \hline & \Delta_i &{ \kern-0.2em-\kern-0.2em 150}M&\underline{-\kern-0.2em M{ \kern-0.2em-\kern-0.2em 10}}&-\kern-0.2em M{ \kern-0.2em-\kern-0.2em 8}&{ \kern-0.2em-\kern-0.2em 12}&0&0&M&M&0&0&\\ \hline\end{array}$

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

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

Поскольку есть отрицательные оценки, то план не оптимален. Наименьшая оценка:
Δ₁ = – M – 10

Вводим переменную x₁ в базис.
Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x₁:

Наименьшее неотрицательное: Q₃ = 100. Выводим переменную x₈ из базиса. Для этого над строками таблицы выполняем линейные преобразования .
Из 1-й строки вычитаем 3-ю строку, умноженную на 5
Из 2-й строки вычитаем 3-ю строку, умноженную на 4
$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline&C_i & & 10 & 8 & 12 & 0 & 0 & 0 & 0 & -\kern-0.2em M & -\kern-0.2em M\\ \hline C_i&b_i & &x_1&x_2&x_3&x_4&x_5&x_6&x_7&x_8&x_9&Q\\ \hline 0 & x_4 & \kern-0.3em 2000\kern-0.3em-\kern-0.3em 5\kern-0.2em\cdot\kern-0.2em 100\kern-0.3em & \kern-0.3em 5\kern-0.3em-\kern-0.3em 5\kern-0.2em\cdot\kern-0.2em 1\kern-0.3em & \kern-0.3em 2\kern-0.3em-\kern-0.3em 5\kern-0.2em\cdot\kern-0.2em 0\kern-0.3em & \kern-0.3em 4\kern-0.3em-\kern-0.3em 5\kern-0.2em\cdot\kern-0.2em 0\kern-0.3em & \kern-0.3em 1\kern-0.3em-\kern-0.3em 5\kern-0.2em\cdot\kern-0.2em 0\kern-0.3em & \kern-0.3em 0\kern-0.3em-\kern-0.3em 5\kern-0.2em\cdot\kern-0.2em 0\kern-0.3em & \kern-0.3em 0\kern-0.3em-\kern-0.3em 5\kern-0.2em\cdot\kern-0.2em \left(-1\right)\kern-0.3em & \kern-0.3em 0\kern-0.3em-\kern-0.3em 5\kern-0.2em\cdot\kern-0.2em 0\kern-0.3em & \kern-0.3em 0\kern-0.3em-\kern-0.3em 5\kern-0.2em\cdot\kern-0.2em 1\kern-0.3em & \kern-0.3em 0\kern-0.3em-\kern-0.3em 5\kern-0.2em\cdot\kern-0.2em 0\kern-0.3em & \\ \hline0 & x_5 & \kern-0.3em 1000\kern-0.3em-\kern-0.3em 4\kern-0.2em\cdot\kern-0.2em 100\kern-0.3em & \kern-0.3em 4\kern-0.3em-\kern-0.3em 4\kern-0.2em\cdot\kern-0.2em 1\kern-0.3em & \kern-0.3em 5\kern-0.3em-\kern-0.3em 4\kern-0.2em\cdot\kern-0.2em 0\kern-0.3em & \kern-0.3em 4\kern-0.3em-\kern-0.3em 4\kern-0.2em\cdot\kern-0.2em 0\kern-0.3em & \kern-0.3em 0\kern-0.3em-\kern-0.3em 4\kern-0.2em\cdot\kern-0.2em 0\kern-0.3em & \kern-0.3em 1\kern-0.3em-\kern-0.3em 4\kern-0.2em\cdot\kern-0.2em 0\kern-0.3em & \kern-0.3em 0\kern-0.3em-\kern-0.3em 4\kern-0.2em\cdot\kern-0.2em \left(-1\right)\kern-0.3em & \kern-0.3em 0\kern-0.3em-\kern-0.3em 4\kern-0.2em\cdot\kern-0.2em 0\kern-0.3em & \kern-0.3em 0\kern-0.3em-\kern-0.3em 4\kern-0.2em\cdot\kern-0.2em 1\kern-0.3em & \kern-0.3em 0\kern-0.3em-\kern-0.3em 4\kern-0.2em\cdot\kern-0.2em 0\kern-0.3em & \\ \hline10 & x_1 & 100 & 1 & 0 & 0 & 0 & 0 & { \kern-0.2em-\kern-0.2em 1} & 0 & 1 & 0& \\ \hline-\kern-0.2em M & x_9 & 50 & 0 & 1 & 0 & 0 & 0 & 0 & { \kern-0.2em-\kern-0.2em 1} & 0 & 1& \\ \hline\end{array}$
Получаем новую таблицу.

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

$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline&C_i & & 10 & 8 & 12 & 0 & 0 & 0 & 0 & -\kern-0.2em M & -\kern-0.2em M\\ \hline C_i&b_i & &x_1&x_2&x_3&x_4&x_5&x_6&x_7&x_8&x_9&Q\\ \hline 0 & x_4 & 1500 & 0&2 & 4 & 1 & 0 & 5 & 0 & { \kern-0.2em-\kern-0.2em 5} & 0&750 \\ \hline0 & x_5 & 600 & 0&5 & 4 & 0 & 1 & 4 & 0 & { \kern-0.2em-\kern-0.2em 4} & 0&120 \\ \hline10 & x_1 & 100 & 1&0 & 0 & 0 & 0 & { \kern-0.2em-\kern-0.2em 1} & 0 & 1 & 0&- \\ \hline-\kern-0.2em M & x_9 & 50 & 0&\underline{1} & 0 & 0 & 0 & 0 & { \kern-0.2em-\kern-0.2em 1} & 0 & 1&\underline{50} \\ \hline & \Delta_i &{ \kern-0.2em-\kern-0.2em 50}M\kern-0.3em+\kern-0.3em 1000&0&\underline{-\kern-0.2em M{ \kern-0.2em-\kern-0.2em 8}}&{ \kern-0.2em-\kern-0.2em 12}&0&0&{ \kern-0.2em-\kern-0.2em 10}&M&M\kern-0.3em+\kern-0.3em 10&0&\\ \hline\end{array}$

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

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

Поскольку есть отрицательные оценки, то план не оптимален. Наименьшая оценка:
Δ₂ = – M – 8

Вводим переменную x₂ в базис.
Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x₂:

Наименьшее неотрицательное: Q₄ = 50. Выводим переменную x₉ из базиса и удаляем искусственные переменные. Выполняем линейные преобразования .
Из 1-й строки вычитаем 4-ю строку, умноженную на 2
Из 2-й строки вычитаем 4-ю строку, умноженную на 5
$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|}\hline&C_i & & 10 & 8 & 12 & 0 & 0 & 0 & 0\\ \hline C_i&b_i & &x_1&x_2&x_3&x_4&x_5&x_6&x_7&Q\\ \hline 0 & x_4 & \kern-0.3em 1500\kern-0.3em-\kern-0.3em 2\kern-0.2em\cdot\kern-0.2em 50\kern-0.3em & \kern-0.3em 0\kern-0.3em-\kern-0.3em 2\kern-0.2em\cdot\kern-0.2em 0\kern-0.3em & \kern-0.3em 2\kern-0.3em-\kern-0.3em 2\kern-0.2em\cdot\kern-0.2em 1\kern-0.3em & \kern-0.3em 4\kern-0.3em-\kern-0.3em 2\kern-0.2em\cdot\kern-0.2em 0\kern-0.3em & \kern-0.3em 1\kern-0.3em-\kern-0.3em 2\kern-0.2em\cdot\kern-0.2em 0\kern-0.3em & \kern-0.3em 0\kern-0.3em-\kern-0.3em 2\kern-0.2em\cdot\kern-0.2em 0\kern-0.3em & \kern-0.3em 5\kern-0.3em-\kern-0.3em 2\kern-0.2em\cdot\kern-0.2em 0\kern-0.3em & \kern-0.3em 0\kern-0.3em-\kern-0.3em 2\kern-0.2em\cdot\kern-0.2em \left(-1\right)\kern-0.3em & \\ \hline0 & x_5 & \kern-0.3em 600\kern-0.3em-\kern-0.3em 5\kern-0.2em\cdot\kern-0.2em 50\kern-0.3em & \kern-0.3em 0\kern-0.3em-\kern-0.3em 5\kern-0.2em\cdot\kern-0.2em 0\kern-0.3em & \kern-0.3em 5\kern-0.3em-\kern-0.3em 5\kern-0.2em\cdot\kern-0.2em 1\kern-0.3em & \kern-0.3em 4\kern-0.3em-\kern-0.3em 5\kern-0.2em\cdot\kern-0.2em 0\kern-0.3em & \kern-0.3em 0\kern-0.3em-\kern-0.3em 5\kern-0.2em\cdot\kern-0.2em 0\kern-0.3em & \kern-0.3em 1\kern-0.3em-\kern-0.3em 5\kern-0.2em\cdot\kern-0.2em 0\kern-0.3em & \kern-0.3em 4\kern-0.3em-\kern-0.3em 5\kern-0.2em\cdot\kern-0.2em 0\kern-0.3em & \kern-0.3em 0\kern-0.3em-\kern-0.3em 5\kern-0.2em\cdot\kern-0.2em \left(-1\right)\kern-0.3em & \\ \hline10 & x_1 & 100 & 1 & 0 & 0 & 0 & 0 & { \kern-0.2em-\kern-0.2em 1} & 0& \\ \hline8 & x_2 & 50 & 0 & 1 & 0 & 0 & 0 & 0 & { \kern-0.2em-\kern-0.2em 1}& \\ \hline\end{array}$
Получаем новую таблицу.

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

$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|}\hline&C_i & & 10 & 8 & 12 & 0 & 0 & 0 & 0\\ \hline C_i&b_i & &x_1&x_2&x_3&x_4&x_5&x_6&x_7&Q\\ \hline 0 & x_4 & 1400 & 0 & 0&4 & 1 & 0 & 5 & 2&350 \\ \hline0 & x_5 & 350 & 0 & 0&\underline{4} & 0 & 1 & 4 & 5&\underline{87.5} \\ \hline10 & x_1 & 100 & 1 & 0&0 & 0 & 0 & { \kern-0.2em-\kern-0.2em 1} & 0&- \\ \hline8 & x_2 & 50 & 0 & 1&0 & 0 & 0 & 0 & { \kern-0.2em-\kern-0.2em 1}&- \\ \hline & \Delta_i &1400&0&0&\underline{{ \kern-0.2em-\kern-0.2em 12}}&0&0&{ \kern-0.2em-\kern-0.2em 10}&{ \kern-0.2em-\kern-0.2em 8}&\\ \hline\end{array}$

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

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

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

Вводим переменную x₃ в базис.
Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x₃:

= 87.5

Наименьшее неотрицательное: Q₂ = 87.5. Выводим переменную x₅ из базиса.
2-ю строку делим на 4.
Из 1-й строки вычитаем 2-ю строку, умноженную на 4
$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|}\hline&C_i & & 10 & 8 & 12 & 0 & 0 & 0 & 0\\ \hline C_i&b_i & &x_1&x_2&x_3&x_4&x_5&x_6&x_7&Q\\ \hline 0 & x_4 & \kern-0.3em 1400\kern-0.3em-\kern-0.3em 4\kern-0.2em\cdot\kern-0.2em \frac{175}{2}\kern-0.3em & \kern-0.3em 0\kern-0.3em-\kern-0.3em 4\kern-0.2em\cdot\kern-0.2em 0\kern-0.3em & \kern-0.3em 0\kern-0.3em-\kern-0.3em 4\kern-0.2em\cdot\kern-0.2em 0\kern-0.3em & \kern-0.3em 4\kern-0.3em-\kern-0.3em 4\kern-0.2em\cdot\kern-0.2em 1\kern-0.3em & \kern-0.3em 1\kern-0.3em-\kern-0.3em 4\kern-0.2em\cdot\kern-0.2em 0\kern-0.3em & \kern-0.3em 0\kern-0.3em-\kern-0.3em 4\kern-0.2em\cdot\kern-0.2em \frac{1}{4}\kern-0.3em & \kern-0.3em 5\kern-0.3em-\kern-0.3em 4\kern-0.2em\cdot\kern-0.2em 1\kern-0.3em & \kern-0.3em 2\kern-0.3em-\kern-0.3em 4\kern-0.2em\cdot\kern-0.2em \frac{5}{4}\kern-0.3em & \\ \hline12 & x_3 & \frac{175}{2} & 0 & 0 & 1 & 0 & \frac{1}{4} & 1 & \frac{5}{4}& \\ \hline10 & x_1 & 100 & 1 & 0 & 0 & 0 & 0 & { \kern-0.2em-\kern-0.2em 1} & 0& \\ \hline8 & x_2 & 50 & 0 & 1 & 0 & 0 & 0 & 0 & { \kern-0.2em-\kern-0.2em 1}& \\ \hline\end{array}$

Вычисляем:

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

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

$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|}\hline&C_i & & 10 & 8 & 12 & 0 & 0 & 0 & 0\\ \hline C_i&b_i & &x_1&x_2&x_3&x_4&x_5&x_6&x_7&Q\\ \hline 0 & x_4 & 1050 & 0 & 0 & 0 & 1 & { \kern-0.2em-\kern-0.2em 1} & 1 & { \kern-0.2em-\kern-0.2em 3}& \\ \hline12 & x_3 & \frac{175}{2} & 0 & 0 & 1 & 0 & \frac{1}{4} & 1 & \frac{5}{4}& \\ \hline10 & x_1 & 100 & 1 & 0 & 0 & 0 & 0 & { \kern-0.2em-\kern-0.2em 1} & 0& \\ \hline8 & x_2 & 50 & 0 & 1 & 0 & 0 & 0 & 0 & { \kern-0.2em-\kern-0.2em 1}& \\ \hline & \Delta_i &2450&0&0&0&0&3&2&7&\\ \hline\end{array}$

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

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

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

Решение задачи: x₁ = 100; x₂ = 50; x₃ = 175/2 = 87.5; x₄ = 1050; x₅ = 0; x₆ = 0; x₇ = 0; F_max = 2450

Ответ

x₁ = 100; x₂ = 50; x₃ = 175/2 = 87.5; x₄ = 1050; x₅ = 0; x₆ = 0; x₇ = 0; F_max = 2450

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

Автор: Олег Одинцов. Опубликовано: 08-12-2011