Оптимизация производственной программы промышленного предприятия. 2

Контрольная задача 1. Оптимизация производственной программы промышленного предприятия.

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

Ресурсы оборудования, сырья, труда  ограничены.

Выпуск продукции А, Б и В  не может быть меньше заключенных  на эту продукцию договоров.

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

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

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

Решение.

Составим экономико-математическую модель задачи. Обозначим  - количество единиц продукции вида А, произведенной соответственно 1 и 2 технологическими способами; - количество единиц продукции вида Б, произведенной соответственно 1 и 2 технологическими способами; - количество единиц продукции вида В, произведенной соответственно 1, 2 и 3 технологическими способами. Т.е. - количество единиц продукции каждого вида (А, Б, В), произведенной различными технологическими способами или план производства. Естественно потребовать, чтобы . Тогда прибыль, полученная при таком плане производства, составит .

Учтем затраты  ресурсов при таком плане производства.

Новое оборудование: , но данный вид ресурсов ограничен, т.е. возникает ограничение .

Аналогичным образом накладываются ограничения и на другие виды ресурсов и получаем систему ограничений: .

Т.к. есть еще  условия на объемы поставок по договорам, то получаем дополнительные ограничения. По виду продукции А: , и аналогично по другим видам продукции: .

Таким образом, приходим к экономико-математической модели задачи.

Требуется среди  неотрицательных решений системы  неравенств ,

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

Получаем решение  .

Оптимальный ассортимент. Следует  производить продукции А первым технологическим способом 1200 и вторым технологическим способом 4000; продукции  Б вторым технологическим способом 2150; продукции В первым технологическим способом 4960 и третьим технологическим способом 224.

При этом прибыль будет максимальной и составит 7727400 тыс.руб.

Анализ невыгодной продукции.

Предприятию невыгодно производить  продукцию Б первым технологическим  способом, при выпуске 1 единицы прибыль  уменьшится на 55 тыс.руб. и продукцию В вторым технологическим способом, при выпуске 1 единицы прибыль уменьшится на 84,57 тыс.руб.

Анализ ограничений  по ресурсам.

Время работы на новом оборудовании используется полностью, его выгодно увеличивать, при увеличении на 1 станко-час. Прибыль увеличивается на 1,14 тыс.руб.

Время работы на старом оборудовании недоиспользуется на 290090 станко-час.

Высококачественное сырье недоиспользуется на 18800 т.

Стандартное сырье недоиспользуется на 20034 т.

Труд высоквалифицированных рабочих  и рабочих средней квалификации используются полностью, его выгодно  увеличивать,  при увеличении на 1 чел.-час. Прибыль увеличивается  на 17,14 и 26 тыс.руб. соответственно.

Анализ ограничений  по договорам.

Продукцию А и Б производить  невыгодно, она вошла в ассортимент  только потому, что на нее заданы минимальные ограничения по выполнению договоров. Каждая единица продукции  вида А и Б снижает прибыль  на 20 и 132 тыс.руб. соответственно.

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

Контрольная задача 2. Транспортная задача.

Четыре оптовых склада обслуживают  четыре магазина одним товаром.

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

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

Решение.

С помощью надстройки поиск решения  получаем следующее решение:

Х₁₄ = 35, т.е. 35 единиц груза перевезти от первого поставщика четвертому покупателю;

Х₂₁ = 75, т.е. 75 единиц груза перевезти от второго поставщика первому покупателю;

Х₂₂ = 20, т.е. 20 единиц груза перевезти от второго поставщика второму покупателю;

Х₂₄ = 5, т.е. 5 единиц груза перевезти от второго поставщика четвертому покупателю;

Х₃₁ = 30, т.е. 30 единиц груза перевезти от третьего поставщика первому покупателю;

Х₄₃ = 60, т.е. 60 единиц груза перевезти от четвертого поставщика третьему покупателю;

Х₄₄ = 25, т.е. 25 единиц груза перевезти от четвертого поставщика четвертому покупателю.

Общая стоимость перевозок составит 1105 тыс.руб.

Теоретический вопрос. Постановка и структурная модель транспортной задачи.

Транспортная  задача линейного программирования  получила  в  настоящее время широкое распространение  в  теоретических  обработках  и  практическом применении на транспорте и в промышленности. Особенно  важное  значение  она имеет в  деле  рационализации  постановок  важнейших  видов  промышленной  и сельскохозяйственной   продукции,   а   также   оптимального    планирования грузопотоков и работы различных видов транспорта [2, С.47].

Кроме того, к задачам  транспортного  типа  сводятся  многие  другие  задачи линейного  программирования - задачи  о  назначениях,  сетевые,  календарного планирования.

Транспортная задача является частным  типом задачи линейного программирования и формулируется следующим образом. Имеется m пунктов отправления (или  пунктов производства) А_i …, А_m, в которых сосредоточены запасы однородных продуктов в количестве a₁, ..., а_m единиц. Имеется n пунктов назначения (или пунктов потребления) В₁, ..., В_m, потребность которых в указанных продуктах составляет b₁, ..., b_n единиц. Известны также транспортные расходы С_ij, связанные с перевозкой единицы продукта из пункта A_i в пункт В_j, i 1, …, m; j 1, ..., n. Предположим, что

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

Пусть х_ij - количество единиц продукта, поставляемого из пункта А_i в пункт В_j. Подлежащие минимизации суммарные затраты на перевозку продуктов из всех пунктов производства во все пункты потребления выражаются формулой:

  (1)

Суммарное количество продукта, направляемого  из каждого пункта отправления во все пункты назначения, должно быть равно запасу продукта в данном пункте. Формально это означает, что

, i 1, …, m  (2)

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

, j 1, …, n  (3)

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

x_ij 0, i 1, ..., m; j 1, ..., n (4)

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

Определение 1.

Всякое неотрицательное решение  системы линейных уравнений , j 1, …, n и  , i 1, …, m, определяемое матрицей X=(x_ij)(i 1, …, m; j 1, ..., n), называется планом транспортной задачи.

Определение 2.

План X*=(x*_ij)(i 1, …, m; j 1, ..., n), при котором функция    принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные записываются в виде таблицы 1.

Таблица 1.

Очевидно, общее наличие груза у поставщиков равно , а общая потребность в грузе в пунктах назначения равна единице. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т.е.

,  (5)

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

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

, i 1, ..., m.

Введение этого условия приводит к открытой транспортной модели.

Теорема 1.

Любая транспортная задача, у которой  суммарный объем запасов совпадает  с суммарным объемом потребностей, имеет решение.

Модели  транспортной задачи

Закрытая модель транспортной задачи

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

Доказательство. Пусть   = M > 0 . 

Тогда   величины  x_ij = a_ib_j /M (i = 1,2,3, ... m; j = 1,2,3, ..., n)                                являются планом, так как они удовлетворяют системе ограничений

 ( 2 ) и ( 3 ) .

 Действительно, подставляя значения  в  (2) и (3) , находим 

     = a_i ,

    = b_j .

Выберем из значений  C_ij  наибольшее  C¢ = max C_ij и заменим в линейной функции ( 1 ) все коэффициенты  на C¢  тогда, учитывая ( 2 ) , получим 

   ,

Выберем из значений C_ij  наименьшее C¢¢=min C_ij и заменим в линейной функции все коэффициенты на C¢¢ ; тогда, учитывая ( 2 ) имеем

Объединяя два последних неравенства в одно двойное, окончательно получаем

C¢¢M ≤ Z ≤  C¢ M, т. е.  линейная функция ограничена на множестве планов транспортной задачи.

Открытая модель транспортной задачи

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

1. суммарные запасы превышают суммарные потребности ;
2. суммарные потребности превышают суммарные запасы .

Линейная функция одинакова в обоих случаях, изменяется только вид системы ограничений.

 Найти минимальное значение  линейной функции

 при ограничениях

,    i = 1, 2, ..., m,                           (случай  а)

,    j = 1, 2, ..., n;

,    i = 1, 2, ..., m,                           (случай б)

,   j = 1, 2, ..., n,

x_ij ³ 0   (i = 1, 2, ..., m;    j = 1, 2, ..., n).

Открытая модель решается приведением к закрытой модели.

 В случае (а), когда суммарные запасы превышают  суммарные потребности, вводится  фиктивный потребитель B_n+1, потребности которого  b_n+1 = . В случае (б), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик  A_m+1, запасы которого a_m+1 = .

Стоимость перевозки  единицы груза как фиктивного потребителя, так и стоимость  перевозки единицы груза от фиктивного поставщика полагают равными нулю, так как груз в обоих случаях  не перевозится.

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

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

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

Число переменных X_ij в транспортной задаче с m пунктами отправления и n пунктами назначения равно nm, а число уравнений в системах (2) и (3) равно n+m. Так как мы предполагаем, что выполняется условие (5), то число линейно независимых уравнений равно n+m-1  отличных от нуля неизвестных.

Если в опорном  плане число отличных от нуля компонентов  равно в точности n+m-1, то план является не выраженным, а если меньше - то выраженным.

Для определения  опорного плана существует несколько методов. Три из них - метод северно-западного угла, метод минимального элемента и метод аппроксимации Фогеля - рассмотрены ниже.

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

Как и для всякой задачи линейного программирования, оптимальный план транспортной задачи является и опорным планом.

Для определения оптимального плана транспортной задачи можно использовать изложенные выше методы. Однако ввиду исключительной практической важности этой задачи и специфики ее ограничений [каждое неизвестное входит лишь в два уравнения системы (2) и (3) и коэффициенты при неизвестных равны единице] для определения оптимального плана транспортной задачи разработаны специальные методы, в частности метод потенциалов и Венгерский метод.

  
Список литературы

1. Экономико-математические методы. Математические методы и модели в экономике. Раздаточный материал/ сост. Аксенова Р.Н.- Владивосток, ДВГАЭУ, 2001.

2. Линейное  программирование:  Учебно-метод.  пособие  к   контрольной работе для студ. эконом. факультета /И.В. Большакова, М.В. Кураленко. − Мн.: БНТУ, 2004. − 148 с.