25 ноя 201378.5K0

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

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

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

Исходные данные задачи на симплекс-метод

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

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

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

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

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

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

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

Цель производственной задачи

Составить такой план производства, при котором прибыль предприятия будет максимальной.

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

(1) Обозначим X1, X2, X3, X4 планируемое количество изделий каждого вида. Тогда искомый план: (X1, X2, X3, X4)

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

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

(3) Тогда целевая прибыль:

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

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

(4) Для решения получившейся задачи на условный экстремум, заменим систему неравенств системой линейных уравнений путем ввода в нее дополнительных неотрицательных переменных (X5, X6, X7).

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

(5) Примем следующий опорный план:

X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80

(6) Занесем данные в симплекс-таблицу:

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

!! В последнюю строку заносим коэффициенты при целевой функции и само ее значение с обратным знаком;

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

Вычислим b = Н / Элементы_выбранного_столбца

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

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

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

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

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

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

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

aij(*) = aij – ( A * B / РЭ )

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

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

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

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

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

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

(10) Так как в последней строке нет отрицательных элементов, это означает, что нами найден оптимальный план производства! А именно: выпускать мы будем те изделия, которые перешли в колонку «Базис» - X1 и X2. Прибыль от производства каждой единицы продукции нам известна (матрица C). Осталось перемножить найденные объемы выпуска изделий 1 и 2 с прибылью на 1 шт., получим итоговую (максимальную!) прибыль при данном плане производства.

ОТВЕТ:

X1 = 32 шт., X2 = 20 шт., X3 = 0 шт., X4 = 0 шт.

P = 48 * 32 + 33 * 20 = 2 196 руб.

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


Орфография

Нашли опечатку? Помогите сделать статью лучше! Выделите орфографическую ошибку мышью и нажмите Ctrl+Enter.

Цитирование

Библиографическая запись для цитирования статьи по ГОСТ Р 7.0.5-2008:
Галяутдинов Р.Р. Решение производственной задачи табличным симплекс-методом // Сайт преподавателя экономики. [2013]. URL: http://galyautdinov.ru/post/proizvodstvennaya-zadacha-simpleks-metod (дата обращения: 28.09.2020).

Еще можно почитать: