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

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

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

Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве b₁ = 240, b₂ = 200, b₃ = 160 единиц. При этом для продажи 1 группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве a₁₁ = 2 единицы, ресурса второго вида в количестве a₂₁ = 4 единицы, ресурса третьего вида в количестве a₃₁ = 4 единицы. Для продажи 2 и 3 групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве a₁₂ = 3, a₁₃ = 6 единицы, ресурса второго вида в количестве a₂₂ = 2, a₂₃ = 4 единицы, ресурса третьего вида в количестве a₃₂ = 6, a₃₃ = 8 единиц. Прибыль от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно c₁ = 4, c₂ = 5, c₃ = 4 (тыс. руб.). Определить плановый объем и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной.

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

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

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

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

В качестве базиса возьмем x₄ = 240; x₅ = 200; x₆ = 160.
Данные заносим в симплекс таблицу

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

Целевая функция:
F = 3∑i = 1C_i·b_i = 0 · 240 + 0 · 200 + 0 · 160 = 0

Вычисляем оценки по формуле:
Δ(x_j) = 3∑i = 1C_i·a_ij – C_j.
Оценки базисных переменных всегда равны нулю. Для свободных переменных, имеем:
Δ(x₁) = 0 · 2 + 0 · 4 + 0 · 4 – 4 =  – 4
Δ(x₂) = 0 · 3 + 0 · 2 + 0 · 6 – 5 =  – 5
Δ(x₃) = 0 · 6 + 0 · 4 + 0 · 8 – 4 =  – 4

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

Наименьшая оценка Δ(x₂) =  – 5. Вводим переменную x₂ в базис.

Определяем переменную, выходящую из базиса из условия, чтобы остальные базисные переменные не приняли отрицательных значений. Для этого находим наименьшее неотрицательное отношение Q_i = b_i/a_i2 для столбца x₂:
Q₁ = 240 / 3 = 80
Q₂ = 200 / 2 = 100
Q₃ = 160 / 6 = 26,67
Наименьшее неотрицательное отношение Q₃ = 26,67 в строке 3. Переменная x₆ выходит из базиса.

Вводим переменную x₂ в базис. Переменную в строке x₆ выводим из базиса. Для этого выполняем эквивалентные преобразования, чтобы столбец x₂ состоял из единицы, в строке x₂, и нулей, в остальных строках.

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

Подробные вычисления
240 – 3·803 = 240 – 2403 = 240 – 80 = 160
2 – 3·23 = 2 – 63 = 2 – 2 = 0
6 – 3·43 = 6 – 123 = 6 – 4 = 2
200 – 2·803 = 200 – 1603 = 200·3–1603 = 4403
4 – 2·23 = 4 – 43 = 4·3–43 = 83
4 – 2·43 = 4 – 83 = 4·3–83 = 43

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

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

Целевая функция:
F = 3∑i = 1C_i·b_i = 0 · 160 + 0 · 4403 + 5 · 803 = 4003 ≈ 133,3

Вычисляем оценки по формуле:
Δ(x_j) = 3∑i = 1C_i·a_ij – C_j.
Оценки базисных переменных всегда равны нулю. Для свободных переменных, имеем:
Δ(x₁) = 0 · 0 + 0 · 83 + 5 · 23 – 4 =  – 23 ≈  – 0,6667
Δ(x₃) = 0 · 2 + 0 · 43 + 5 · 43 – 4 = 83 ≈ 2,667
Δ(x₆) = 0 · ( – 12) + 0 · ( – 13) + 5 · 16 – 0 = 56 ≈ 0,8333

Поскольку есть отрицательная оценка Δ(x₁) =  – 0,6667, то план не оптимален.

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

Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение Q_i = b_i/a_i2 для столбца x₁:
Q₁ = 160 / 0 = ∞
Q₂ = 4403 / 83 = 55
Q₃ = 803 / 23 = 40
Наименьшее неотрицательное отношение Q₃ = 40 в строке 3. Переменная x₂ выходит из базиса.

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

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

Подробные вычисления
4403 – 83·40 = 4403 – 3203 = 440–3203 = 40
83 – 83·1 = 83 – 83 = 8–83 = 0
43 – 83·2 = 43 – 163 = 4–163 =  – 4
 – 13 – 83·14 =  – 13 – 812 =  – 13 – 23 = -1–23 =  – 1

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

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

Целевая функция:
F = 3∑i = 1C_i·b_i = 0 · 160 + 0 · 40 + 4 · 40 = 160

Вычисляем оценки по формуле:
Δ(x_j) = 3∑i = 1C_i·a_ij – C_j.
Оценки базисных переменных всегда равны нулю. Для свободных переменных, имеем:
Δ(x₂) = 0 · 0 + 0 · ( – 4) + 4 · 32 – 5 = 1
Δ(x₃) = 0 · 2 + 0 · ( – 4) + 4 · 2 – 4 = 4
Δ(x₆) = 0 · ( – 12) + 0 · ( – 1) + 4 · 14 – 0 = 1

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

Решение задачи: x₁ = 40; x₂ = 0; x₃ = 0; x₄ = 160; x₅ = 40; x₆ = 0; F_max = 160

Ответ

x₁ = 40; x₂ = 0; x₃ = 0; x₄ = 160; x₅ = 40; x₆ = 0; F_max = 160
То есть необходимо реализовать товар первого вида в объеме 40 тыс. руб. Товар 2-го и 3-го видов реализовывать не надо. При этом максимальная прибыль составит F_max = 160 тыс. руб.

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

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

Из последней симплекс таблицы № 3 прямой задачи, находим решение двойственной задачи:
Z_min = F_max = 160;
y₁ = Δ₄ = 0; y₂ = Δ₅ = 0; y₃ = Δ₆ = 1; y₄ = Δ₁ = 0; y₅ = Δ₂ = 1; y₆ = Δ₃ = 4;

Ответ

y₁ = 0; y₂ = 0; y₃ = 1; Z_min = 160.

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