Методы решения физико-математических задач

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

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

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

Найти оптимальные величины производства продукции видов А, Б и В. Затраты сырья на единицу продукции: А – 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

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

Чтобы выбрать начальный базис, вводим искусственные переменные 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

В качестве базиса возьмем x4 = 2000; x5 = 1000; x8 = 100; x9 = 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}

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

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









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

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




Наименьшее неотрицательное: Q3 = 100. Выводим переменную x8 из базиса. Для этого над строками таблицы выполняем линейные преобразования .
Из 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}

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

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









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

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




Наименьшее неотрицательное: Q4 = 50. Выводим переменную x9 из базиса и удаляем искусственные переменные. Выполняем линейные преобразования .
Из 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}

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

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







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

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

= 87.5


Наименьшее неотрицательное: Q2 = 87.5. Выводим переменную x5 из базиса.
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}

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

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







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

Решение задачи: 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 единиц.

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

Меню