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

Рассмотрено решение задач линейного программирования симплекс методом. Рассмотрена двойственная задача и ее решение симплекс методом. Дан экономический смысл исходной задачи и переменных двойственной задачи. Рассмотрено решение задачи симплексным М – методом.

Введение

Наиболее распространенный вид задач линейного программирования, решаемых симплекс методом, имеет следующий вид:

F = c₁·x₁ + c₂·x₂ + c₃·x₃ -> max
a₁₁·x₁ + a₁₂·x₂ + a₁₃·x₃ ≤ b₁
a₂₁·x₁ + a₂₂·x₂ + a₂₃·x₃ ≤ b₂
a₃₁·x₁ + a₃₂·x₂ + a₃₃·x₃ ≤ b₃
x₁ ≥ 0; x₂ ≥ 0; x₃ ≥ 0;

Чтобы преобразовать неравенства в равенства, вводят неотрицательные переменные x₄  ≥  0; x₅  ≥  0; x₆  ≥  0. Тогда получаем систему уравнений:

a₁₁·x₁ + a₁₂·x₂ + a₁₃·x₃ + x₄ = b₁
a₂₁·x₁ + a₂₂·x₂ + a₂₃·x₃ + x₅ = b₂
a₃₁·x₁ + a₃₂·x₂ + a₃₃·x₃ + x₆ = b₃
x₁ ≥ 0; x₂ ≥ 0; x₃ ≥ 0; x₄ ≥ 0; x₅ ≥ 0; x₆ ≥ 0.

Они определяют пересечение трех плоскостей в 6-ти мерном пространстве. Поскольку линейные функции не имеют локальных экстремумов, то экстремум целевой функции может быть только на границе, определяемой неравенствами x₁ ≥ 0; x₂ ≥ 0; x₃ ≥ 0; x₄ ≥ 0; x₅ ≥ 0; x₆ ≥ 0. На этой границе три из 6-ти переменных равны нулю. Значения остальных, которые называются базисом, получаются из решения системы уравнений. Решение симплекс методом выполняется в два этапа.

1. Выбирается начальный базис. В данном случае это x₄ = b₁, x₅ = b₂, x₆ = b₃ (при этом x₁ = 0; x₂ = 0; x₃ = 0).
2. Выполняется поиск решения в симплекс таблице. Если базис не дает оптимального решения, выбирается новый базис, составляется новая симплекс таблица до получения оптимального решения.

Экономический смысл задач, решаемых симплекс методом

Здесь, как правило, x₁, x₂, x₃ – количество произведенной продукции 1, 2, 3-го вида, соответственно; c₁, c₂, c₃ – прибыль на единицу продукции; F – общая прибыль; a_ij – количество затрат i-го сырья на единицу j-го вида продукции; b₁, b₂, b₃ – количество запасов сырья.

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

Двойственная задача получается из прямой задачи транспонированием матрицы a, меняя b и c местами, а также изменяя знаки неравенств и вида экстремума целевой функции:

Z = b₁·y₁ + b₂·y₂ + b₃·y₃ -> min
a₁₁·y₁ + a₂₁·y₂ + a₃₁·y₃ ≥ c₁
a₁₂·y₁ + a₂₂·y₂ + a₃₂·y₃ ≥ c₂
a₁₃·y₁ + a₂₃·y₂ + a₃₃·y₃ ≥ c₃
y₁ ≥ 0; y₂ ≥ 0; y₃ ≥ 0;

Ее решение получается из решения прямой задачи, полученным симплекс метолом. При этом

Z_min = F_max. Значения y₁, y₂, y₃ равны оценкам вспомогательных переменных x₄, x₅, x₆, взятых из последней симплекс таблицы прямой задачи:

y₁ = Δ₄, y₂ = Δ₅, y₃ = Δ₆.

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

Переменные y₁ = Δ₄, y₂ = Δ₅, y₃ = Δ₆ определяют, насколько увеличится максимальная прибыль, при увеличении запасов сырья b₁, b₂, b₃ на единицу. То есть при изменении запасов сырья на Δb₁, Δb₂, Δb₃ происходит изменение максимальной прибыли на величину

ΔF_max = y₁·Δb₁ + y₂·Δb₂ + y₃·Δb₃.

Величины Δb₁, Δb₂, Δb₃ часто записывают как Δx₄, Δx₅, Δx₆, поскольку Δx₄ = Δb₁, Δx₅ = Δb₂, Δx₆ = Δb₃.

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

Задача N 36. Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве 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 (тыс. руб.). Определить плановый объем и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной.

Задача N 53. К прямой задаче планирования товарооборота, решаемой симплекс методом, составить двойственную задачу линейного программирования.

Установить сопряженные пары переменных прямой и двойственной задачи.

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

Решение этой задачи симплекс методом и решение двойственной задачи >>>

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

В некоторых случаях выбрать начальный базис не просто. Например, если имеется дополнительное ограничение x₃ ≥ 10, то для преобразования неравенства в равенство, необходимо ввести переменную x₇ ≥ 0. Тогда неравенство примет вид:

x₃ – x₇ = 10.

Поскольку x₇ ≥ 0, то нельзя в качестве базиса выбрать x₇ = -10. В этом случае, для построения начального базиса, вводят фиктивную переменную x₈ ≥ 0 и вводят ее в предыдущее равенство:

x₃ – x₇ + x₈ = 10.

Тогда, в начальном базисе полагают x₈ = 10, а в целевую функцию вводят член -M· x₈:

F = c₁·x₁ + c₂·x₂ + c₃·x₃ – M·x₈ -> max

где M –> ∞ - очень большое положительное число. Если задача имеет решение, то после первых итераций симплекс методом переменная x₈ выходит из базиса.

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

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

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

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