Задача 37
Имеется три пункта поставки однородного груза А1, А2, А3 и пять пунктов потребления груза B1, B2, B3, B4. На пунктах А1, А2, А3 находится груз соответственно в количестве150, 250, 200 тонн. В пункты B1, B2, B3, B4 требуется доставить соответственно 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
Значит, план невырожденный.
Из таблицы видно, что:
X13=90; X15=60; X22=120; X24=85; X25=45; X31=180; X34=20.
Стоимость перевозок, соответствующая первому опорному плану, определяется с помощью тарифов:
Z1=4*90+4*60+10*120+11*85+5*45+15*180+13*20=5920 тыс. руб.
Вычислим потенциалы из условия:
бi + вj=Cij (для заполненных клеток)
Примем б1=0, тогда б2 =1; б3=3; в1=12; в2=9; в3=4; в4 =10 в5=4
4. Проверим план на оптимальность. Оптимальный план должен удовлетворять условию:
бi + вj<Cij (для пустых клеток)
Проверка показала, что для клеток (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
Z2=6*60+4*90+10*60+11*85+5*105+15*180+13*20=5740 тыс. руб.
Вычислим новые потенциалы:
примем б1=0, тогда б2 =4; б3=6; в1=9; в2=6; в3=4; в4 =7 в5=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
Z3=6*80+4*70+10*40+11*105+5*105+15*180+6*20=5660 тыс. руб.
Вычислим новые потенциалы:
примем б1=0, тогда б2 =4; б3=2; в1=13; в2=6; в3=4; в4 =7 в5=1
Проверим на оптимальность пустые клетки. Проверка показала, что все клетки удовлетворяют условию:
бi + вj<Cij (для пустых клеток)
Значит, полученный в таблице 4 план оптимален.
Ответ.
Оптимальный план перевозок:
X12=80; X13=70; X22=40; X24=105; X25=105; X31=180; X33=20
Расходы по его осуществлению минимальны и сотавляют
Zmin=5660 тыс. руб.