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

  (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.

Пункты отправления	Пункты назначения					Запасы
	В1	…	Bj	…	Bn	А1
A1	C11 X11	…	C1j X1j	…	C1n X1n	a1
…	…	…	…	…	…	…
Ai	Ci1 Xi1	…	Cij Xij	…	Cin Xin	ai
…	…	…	…	…	…	…
Am	Cm1 Xm1	…	Cmj Xmj	…	Cmn Xmn	am
Потребности	b1	…	bj	…	bn

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

,  (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 с.