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

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

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

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

F = c1·x1 + c2·x2 + c3·x3 -> max
a11·x1 + a12·x2 + a13·x3 ≤ b1
a21·x1 + a22·x2 + a23·x3 ≤ b2
a31·x1 + a32·x2 + a33·x3 ≤ b3
x1 ≥ 0; x2 ≥ 0; x3 ≥ 0;

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

a11·x1 + a12·x2 + a13·x3 + x4 = b1
a21·x1 + a22·x2 + a23·x3 + x5 = b2
a31·x1 + a32·x2 + a33·x3 + x6 = b3
x1 ≥ 0; x2 ≥ 0; x3 ≥ 0; x4 ≥ 0; x5 ≥ 0; x6 ≥ 0.

Они определяют пересечение трех плоскостей в 6-ти мерном пространстве. Поскольку линейные функции не имеют локальных экстремумов, то экстремум целевой функции может быть только на границе, определяемой неравенствами x1 ≥ 0; x2 ≥ 0; x3 ≥ 0; x4 ≥ 0; x5 ≥ 0; x6 ≥ 0. На этой границе три из 6-ти переменных равны нулю. Значения остальных, которые называются базисом, получаются из решения системы уравнений. Решение симплекс методом выполняется в два этапа.

  1. Выбирается начальный базис. В данном случае это x4 = b1, x5 = b2, x6 = b3 (при этом x1 = 0; x2 = 0; x3 = 0).
  2. Выполняется поиск решения в симплекс таблице. Если базис не дает оптимального решения, выбирается новый базис, составляется новая симплекс таблица до получения оптимального решения.

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

Здесь, как правило, x1, x2, x3 – количество произведенной продукции 1, 2, 3-го вида, соответственно; c1, c2, c3 – прибыль на единицу продукции; F – общая прибыль; aij – количество затрат i-го сырья на единицу j-го вида продукции; b1, b2, b3 – количество запасов сырья.

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

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

Z = b1·y1 + b2·y2 + b3·y3 -> min
a11·y1 + a21·y2 + a31·y3 ≥ c1
a12·y1 + a22·y2 + a32·y3 ≥ c2
a13·y1 + a23·y2 + a33·y3 ≥ c3
y1 ≥ 0; y2 ≥ 0; y3 ≥ 0;

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

Zmin = Fmax. Значения y1, y2, y3 равны оценкам вспомогательных переменных x4, x5, x6, взятых из последней симплекс таблицы прямой задачи:

y1 = Δ4, y2 = Δ5, y3 = Δ6.

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

Переменные y1 = Δ4, y2 = Δ5, y3 = Δ6 определяют, насколько увеличится максимальная прибыль, при увеличении запасов сырья b1, b2, b3 на единицу. То есть при изменении запасов сырья на Δb1, Δb2, Δb3 происходит изменение максимальной прибыли на величину

ΔFmax = y1·Δb1 + y2·Δb2 + y3·Δb3.

Величины Δb1, Δb2, Δb3 часто записывают как Δx4, Δx5, Δx6, поскольку Δx4 = Δb1, Δx5 = Δb2, Δx6 = Δb3.

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

Задача N 36. Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве b1 = 240, b2 = 200, b3 = 160 единиц. При этом для продажи 1 группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве a11 = 2 единицы, ресурса второго вида в количестве a21 = 4 единицы, ресурса третьего вида в количестве a31 = 4 единицы. Для продажи 2 и 3 групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве a12 = 3, a13 = 6 единицы, ресурса второго вида в количестве a22 = 2, a23 = 4 единицы, ресурса третьего вида в количестве a32 = 6, a33 = 8 единиц. Прибыль от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно c1 = 4, c2 = 5, c3 = 4 (тыс. руб.). Определить плановый объем и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной.

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

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

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

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

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

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

x3 – x7 = 10.

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

x3 – x7 + x8 = 10.

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

F = c1·x1 + c2·x2 + c3·x3 – M·x8 -> max

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

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

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

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


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


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