25.11.2013   38 403   0  

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


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

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

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

Предприятие выпускает 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 (дата обращения: 17.10.2017).

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

 
 
   
Формулы ФОРМУЛЫ
Термины ТЕРМИНЫ
Бухучет БУХУЧЕТ
Налоги НАЛОГИ
Статистика СТАТИСТИКА
Биографии БИОГРАФИИ
Задачи ЗАДАЧИ
ENGLISH
  Галяутдинов Руслан Рамилевич

ГАЛЯУТДИНОВ
Руслан Рамилевич

старший преподаватель экономических дисциплин (маркетинг, логистика, рынок ценных бумаг)... подробнее

Почта
 
 
 
Курсы валют ЦБ РФ
СейчасБудет
Курс доллара0.000.00
Курс евро0.000.00
Товарные рынки
BIDASK
Золото0.000.00
Серебро0.000.00
Платина0.000.00
Нефть Brent0.000.00
  Обзорные лекции к ГОСам по специальности 'Экономика и управление на предприятии' Решение задачи коммивояжера онлайн