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

Доказательство. Пусть   = 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,

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

 

2.3 Критерий оптимальности базисного решения транспортной задачи. Методы отыскания оптимального решения

 

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

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

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

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

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

Распределительный метод. При  этом методе для каждой пустой клетки строят цикл и для каждого цикла  непосредственно вычисляют алгебраическую сумму тарифов.

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

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

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

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

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

1. Сумма запасов в пунктах  отправления превышает сумму  поданных заявок (транспортная задача  с избытком запасов):

å аi > å bj ( где i=1,...,m ; j=1,...,n );

2. Сумма поданных заявок  превышает наличные запасы (транспортная  задача с избытком заявок):

å аi < å bj ( где i=1,...,m ; j=1,...,n );

Рассмотрим последовательно  эти два случая:

Транспортная задача с  избытком запасов.

Сведем её к ранее рассмотренной  транспортной задаче с правильным балансом. Для этого, сверх имеющихся n пунктов  назначения В1, B2, ... , Bn, введём ещё один, фиктивный, пункт назначения Bn+1, которому припишем фиктивную заявку, равную избытку запасов над заявками

bn+1 = å аi - å bj ( где i=1,...,m ; j=1,...,n ) ,

а стоимость перевозок  из всех пунктов отправления в  фиктивный пункт назначения bn+1 будем  считать равной нулю. Введением фиктивного пункта назначения B n+1 с его заявкой b n+1 мы сравняли баланс транспортной задачи, и теперь ее можно решать, как  обычную транспортную задачу с правильным балансом.

Транспортная задача с избытком заявок.

Эту задачу можно свести к обычной транспортной задаче с  правильным балансом, если ввести фиктивный  пункт отправления Am+1 с запасом am+1 равным недостающему запасу, и стоимость  перевозок из фиктивного пункта отправления  во все пункты назначения принять  равной нулю.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Глава 3. Решение закрытой транспортной задачи

 

3.1 Постановка задачи

 

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

И так, с трех складов A₁, A₂, A₃ необходимо доставить автолампы и аксессуары в пять торговых точек B₁, B₂, B₃, B₄, B₅. Требуется закрепить склады так, чтобы общая сумма затрат на перевозку была минимальной.

Числовые данные задачи представлены в следующей таблице:

Склады	Торговые точки					Объем вывоза, кг.
	В1	В2	В3	В4	В5
	Стоимость перевозки 1кг. груза, руб.
А1	3	3	2	4	2	40
А2	6	2	3	1	7	150
А3	4	5	2	8	4	100
Объем вывоза, кг.	20	80	90	60	40	290

 

Математическая модель задачи

Пусть x_ij – количество единиц груза, которое необходимо доставить от i-го поставщика к j-му потребителю.

Тогда суммарные затраты  на перевозку Z составят:

 

 

3.2 Алгоритм решения

 

1. Определяем характер транспортной задачи. Модель транспортной задачи называют закрытой, если . В противном случае модель транспортной задачи называю открытой. Если , то открытая транспортная задача сводиться к закрытой путем введения фиктивного потребителя с объемом потребностей и стоимостями перевозок равными 0. Если , то открытая транспортная задача сводиться к закрытой путем введения фиктивного потребителя с объемом потребностей и стоимостями перевозок равными 0.
2. Составим первый опорный план методом «минимальной стоимости».
3. Проверим полученный опорный план на невырожденность. План называется невырожденным, если выполняется условие k=m+n-1 , где k – это число заполненных ячеек, m – число поставщиков, n – число потребителей. Если опорный план вырожденный (условие не выполняется), необходимо перейти от него к невырожденному опорному плану. Для этого незаполненную ячейку с минимальной стоимостью перевозок заполняем нулем, но без образования замкнутого цикла с опорными вершинами в заполненных ячейках.
4. Определим потенциалы поставщиков u_i и потребителей v_j из уравнений . При этом предполагается, что .
5. Проверим опорный план на оптимальность, вычислив оценки свободных ячеек: . Если , то найденный план оптимальный. При этом если какая-либо оценка , то оптимальный план неединственный. В случае если все оценки , то оптимальный план единственный.
6. Если какая-либо из оценок , то план неоптимальный и необходимо произвести перераспределение поставок (произвести загрузку свободной ячейки с отрицательной оценкой).
7. Шаги алгоритма 4-6 повторяем до тех пор, пока не будет получен оптимальный опорный план.

 

 

 

 

 

 

Решение

 

Задача является закрытой, т.к. .

Первый опорный план:

 

20		80		90		60		40
440	3		3		240		4		2
1150	6		280		3		160		710
1100	420		5		250		8		430

 

Т.к. (т.е. опорный план невырожденный). Определим потенциалы поставщиков u_i и потребителей v_j.

 

20		80		90		60		40
440	3		3		240		4		2			0
1150	6		280		3		160		710			3
1100	420		5		250		8		430			0
4		-1		2		-2		4

 

Оценки свободных ячеек:

S₁₁=-1;

S₁₂=4;

S₁₄=6;

S₁₅=-2;

S₂₁=-1

S₂₃=-2;

S₃₂=6

S₃₄=10

Полученный опорный план неоптимальный, т.к. среди оценок свободных  ячеек есть отрицательные, возьмем  самую минимальную из них, это  S₁₅=-2;и

S₂₃=-2; мы используем S₁₅=-2.

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

 

 

20		80		90		60		40
40	3		3		2 40		4		2			0
150	6		280		3		160		7 10			3
100	420		5		2 50		8		430			0
4		-1		2		-2		4