Задача 37

Имеется три пункта поставки однородного груза А₁, А₂, А₃ и пять пунктов потребления груза B₁, B₂, B₃, B₄. На пунктах А₁, А₂, А₃ находится груз соответственно в количестве150, 250, 200 тонн. В пункты B₁, B₂, B₃, B₄ требуется доставить соответственно 180, 120, 90, 105 и 105 тонн груза. Затраты на перевозку 1 т. груза между пунктами поставки и пунктами потребления приведены в матрице С (в тыс. руб.):

14	6	4	9	4
17	10	9	11	5
15	11	6	13	8

где С_ij – стоимость перевозки 1 тонны груза от поставщика с номером i (i=1, 2 ,3) к потребителю с номером j (j=1, 2, 3, 4, 5).

Найти такой план закрепеления потребителей за поставщиками, чтобы общие затраты по перевозкам груза были минимальными.

Решение:

Данные задачи запишем в виде матрицы перевозок (таблица 1).

Базы	Потребители	Запасы
B1	B2	B3	B4	B5
А1	14	6	4	9	4	150
А2	17	10	9	11	5	250
А3	15	11	6	13	8	200
Потребности	180	120	90	105	105

В правом верхнем углу каждой клетки проставлены тарифы, взятые из матрицы С.

1. Проверяем сбалансированность данных задачи: сумма всех запасов (150+250+200)=600 равна сумме всех потребностей (180+120+90+105+105)=600

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

Базы	Потребители	Запасы
B1	B2	B3	B4	B5
А1	14	6 +      .	4 90	9	4 -    60	150
А2	17	10  -   120	9	11 85	5 +    45	250
А3	15 180	11	6	13 20	8	200
Потребности	180	120	90	105	105

3. Количество заполненных клеток в таблице 2 равно 7.

Их должно быть m+n-1=3+5-1=7

Значит, план невырожденный.

Из таблицы видно, что:

X₁₃=90; X₁₅=60; X₂₂=120; X₂₄=85; X₂₅=45; X₃₁=180; X₃₄=20.

Стоимость перевозок, соответствующая первому опорному плану, определяется с помощью тарифов:

Z₁=4*90+4*60+10*120+11*85+5*45+15*180+13*20=5920 тыс. руб.

Вычислим потенциалы из условия:

α_i + β_j=C_ij  (для заполненных клеток)

Примем α₁=0, тогда  α₂ =1; α₃=3; β₁=12; β₂=9; β₃=4; β₄ =10 β₅=4

4. Проверим план на оптимальность. Оптимальный план должен удовлетворять условию:

α_i + β_j<C_ij    (для пустых клеток)

Проверка показала, что для клеток (1, 2), (1, 4), (3, 2) и (3, 4) условие оптимальности не выполняется. Загрузим неоптимальную клетку (1, 2) (или любую другую) за счет перераспределения груза в других клетках.

Построим цикл пересчета, который показан на рисунке 2.

Наименьшая из поставок, отмеченных знаком “-“ равна 60. Перемещая ее по циклу, приходим к новому плану, показанному в таблице 3.

Базы	Потребители	Запасы
B1	B2	B3	B4	B5
А1	14	6 +    60	4 -    90	9	4	150
А2	17	10 -    60	9	11 +    85	5     105	250
А3	15 180	11	6 +        .	13 -    20	8	200
Потребности	180	120	90	105	105

Z₂=6*60+4*90+10*60+11*85+5*105+15*180+13*20=5740 тыс. руб.

Вычислим новые потенциалы:

примем α₁=0, тогда  α₂ =4; α₃=6; β₁=9; β₂=6; β₃=4; β₄ =7 β₅=1

Проверим на оптимальность пустые клетки. Проверка показала, что для клеток (3, 2) и (3, 3) условие оптимальности не выполняется. Загрузим неоптимальную клетку (3, 3) за счет перераспределения груза в других клетках.

Построим цикл пересчета, который показан на рисунке 3.

Наименьшая из поставок, отмеченных знаком “-“ равна 20. Перемещая ее по циклу, приходим к новому плану, показанному в таблице 4.

Базы	Потребители	Запасы
B1	B2	B3	B4	B5
А1	14	6     80	4     70	9	4	150
А2	17	10    40	9	11     105	5     105	250
А3	15 180	11	6 20	13	8	200
Потребности	180	120	90	105	105

Z₃=6*80+4*70+10*40+11*105+5*105+15*180+6*20=5660 тыс. руб.

Вычислим новые потенциалы:

примем α₁=0, тогда  α₂ =4; α₃=2; β₁=13; β₂=6; β₃=4; β₄ =7 β₅=1

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

α_i + β_j<C_ij    (для пустых клеток)

Значит, полученный в таблице 4 план оптимален.

Ответ.

Оптимальный план перевозок:

X₁₂=80; X₁₃=70; X₂₂=40; X₂₄=105; X₂₅=105; X₃₁=180; X₃₃=20

Расходы по его осуществлению минимальны и сотавляют

Z_min=5660 тыс. руб.