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

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

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

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

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

1. Определение исходных данных

В нашем примере, по условиям задачи предприятие выпускает 4 вида изделий, обрабатывая их на 3 станках.

Исходные данные для производственной задачи запишем в формате матриц:

• Матрица A — нормы времени на обработку изделий;
• Матрица B — фонд времени работы станков;
• Матрица C — продажи производимых изделий.

Таким образом, нормы времени (мин./шт.) на обработку изделий на станках, заданы матрицей A:

Фонд времени работы станков (мин.) задан в матрице B:

Прибыль от продажи каждой единицы изделия (руб./шт.) задана матрицей C:

Кроме того, обозначим через X_i планируемое количество изделий каждого вида. Тогда искомый план: X₁, X₂, X₃, X₄.

2. Запись ограничений плана в виде системы неравенств

Запишем ограничения плана в виде системы неравенств:

Коэффициенты при переменных в левой части системы неравенств берем из матрицы A, значения из правой части — из матрицы B.

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

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

3. Определение целевого показателя

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

Тогда целевая прибыль может быть записана через следующее равенство:

Коэффициенты при переменных берем из матрицы C. То есть мы перемножаем прибыль от производства единицы изделия каждого вида на их планируемое количество, для получения значения суммарной прибыли (которая должна быть максимальной).

4. Приведение системы неравенств к системе линейных уравнений

Для решения получившейся задачи на условный экстремум, заменим систему неравенств системой линейных уравнений путем ввода в нее дополнительных неотрицательных переменных (X₅, X₆, X₇).

Эти переменные являются фиктивными изделиями, на которые мы списываем неиспользованные остатки фондов времени работы станков.

5. Формирование опорного плана

Примем следующий опорный план (предварительный вариант, который в процессе решения задачи будет итерационно улучшаться):

X₁ = 0, X₂ = 0, X₃ = 0, X₄ = 0, X₅ = 252, X₆ = 144, X₇ = 80.

Здесь основным переменным (количеству изделий производимых в рамках плана) сопоставляем нулевые значения, а дополнительным (фиктивным) переменным — соответствующие величины фондов времени работы станков.

6. Составление симплекс-таблицы

Занесем исходные данные в специальную симплекс-таблицу.

В столбец Базис выписываем дополнительные переменные (X₅..X₇). В колонку H вносим величины фонда времени работы станков. В столбцы X₁..X₇ помещаем коэффициенты при этих переменных из составленной ранее системы уравнений (если переменных в уравнении нет, как например, X₆ и X₇ в первом равенстве, то коэффициенты будут равны 0). Кроме того, следует предусмотреть дополнительный столбец (b) для показателя, который мы будем рассчитывать на следующем этапе.

Количество строк в таблице соответствует числу дополнительных переменных (X₅..X₇). В последнюю строку (c) заносим коэффициенты при целевой функции с обратным знаком (коэффициенты при дополнительных переменных X₅..X₇ будут нулевыми).

7. Вычисление показателя b

Выбираем в последней строке наибольшее (по модулю!) отрицательное число.

В нашем примере это -48 (еще раз подчеркнем, что отрицательные числа сравниваем без учета знака).

Далее вычислим для столбца, которому соответствует выбранное число, специальный показатель b_i = Н_i / a_i, где a_i — значение ячейки выбранного столбца и соответствующей строки.

8. Нахождение разрешающего элемента

Среди вычисленных значений b выбираем наименьшее.

Пересечение выбранных столбца и строки даст нам разрешающий элемент (РЭ). Меняем базисную переменную (из первой колонки в выбранной строке) на переменную соответствующую разрешающему элементу (X₅ на X₁).

9. Перерасчет элементов симплекс-таблицы

Теперь необходимо пересчитать все элементы симплекс-таблицы, кроме столбца b (который очищается).

При перерасчете элементов симплекс-таблицы следует придерживаться следующих правил:

• Сам разрешающий элемент (РЭ) обращается в единицу;
• Для элементов разрешающей строки применяется формула: a_ij^* = a_ij / РЭ (то есть каждый элемент делим на значение разрешающего элемента и получаем новые данные);
• Для элементов разрешающего столбца — они просто обнуляются;
• Остальные элементы таблицы пересчитываем по правилу прямоугольника:
  

  Формула здесь следующая: a_ij^* = a_ij — ( A × B / РЭ )

  Как видите, мы берем пересчитываемую ячейку и ячейку с разрешающим элементом. Они образуют противоположные углы прямоугольника. Далее перемножаем значения из ячеек 2-х других углов этого прямоугольника. Это произведение (A × B) делим на разрешающий элемент (РЭ) и вычитаем из текущей пересчитываемой ячейки (a_ij) то, что получилось. В итоге имеем новое значение — a_ij^*.

Полученные в результате перерасчета значения заносим в новую симплекс-таблицу:

10. Проверяем последнюю строку симплекс-таблицы на наличие отрицательных чисел: если их нет — оптимальный план найден (п. 11), если есть — план требует улучшения (п. 7)

Вновь проверяем последнюю строку (c) на наличие отрицательных чисел. Если их нет — оптимальный план найден, переходим к последнему этапу решения задачи (пункт 11). Если есть — план еще не оптимален, и симплекс-таблицу вновь нужно пересчитать.

Так как у нас в последней строке снова имеются отрицательные числа, начинаем новую итерацию (повторение) вычислений с пункта 7.

В нашем примере мы снова ищем в последней строке наибольшее по модулю отрицательное число, вычисляем для соответствующего ему столбца показатель b, определяем разрешающий элемент, меняем базис и пересчитываем элементы симплекс-таблицы.

Пересчитав таблицу мы видим, что на сей раз в последней строке нет отрицательных чисел, следовательно оптимальный план (позволяющий получить максимальную прибыль) найден и можно переходить к завершающему пункту решения.

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

11. Определение производственного плана и вычисление общей прибыли

В соответствии с найденным планом (смотрим какие переменные перешли в колонку «Базис») выпускать мы будем изделия X₁ и X₂ (X₇ не учитываем, т. к. это фиктивное изделие, не производимое на предприятии и введенное для приведения системы неравенств к системе уравнений).

Прибыль от производства каждой единицы продукции нам известна (матрица C). Остается перемножить ее с найденными объемами выпуска изделий X₁ и X₂ (значения X₃ и X₄ нулевые, т. к. эти изделия производить оказалось невыгодно), для получения общей (максимально возможной!) прибыли.

Ответ План производства: X₁ = 32 шт., X₂ = 20 шт., X₃ = 0 шт., X₄ = 0 шт., общая прибыль: P = 48 × 32 + 33 × 20 = 2 196 руб.

Галяутдинов Р.Р.

© Копирование любых материалов статьи допустимо только при указании прямой индексируемой ссылки на источник: Галяутдинов Р.Р.