Пример 13
Сталеплавильная компания располагает 3 заводами М1, М2, М3, производящими за некоторый период времени 50, 30, 20 тыс тонн стали. Свою продукцию предприятие поставляет 4 потребителям С1, С2, С3, С4, потребности которых за тот же период времени составляют 12, 15, 25, 36 тыс. тонн стали. Стоимость перевозки 1 тыс. тонн стали с завода М1 потребителям равна 15, 19, 19, 15 ден.ед. соответственно; аналогичные стоимости перевоза с завода М2 равны 19, 18, 18, 10 ден.ед., а с завода М3 – 14, 16, 20, 18 ден. ед. Найти оптимальный план перевозок, при котором общие затраты на перевозку будут минимальны.
Решение.
Пусть запланировано перевести хij тонн стали. Стоимость перевозки будет равна сijxij, тогда целевая функция будет иметь вид:
f(x)=
min
Ранг системы линейных уравнений: m+n -1 =3+5-1 = 7
Таблица 4.14
пункты |
С1 |
С2 |
С3 |
С4 |
С5 |
запасы |
потенциалы аi |
М1 |
15 |
19 7 |
19 25 |
15 6 |
0 12 |
50 |
0 |
М2 |
19 |
18 |
18 |
10 30 |
0 |
30 |
-5 |
М3 |
14 12 |
16 8 |
20 |
18 |
0 |
20 |
-3 |
потребности |
12 |
15 |
25 |
36 |
12 |
100 |
|
потенциалы бj |
17 |
19 |
19 |
15 |
0 |
|
|
Исходный план перевозок имеет суммарную стоимость:
f(x)=19·7+19·25+15·6+0·12+10·30+14·12+16·8=1294 ден. ед.
Находим потенциалы по формуле сij=ai+bj
с15 = а1+б5 с14 = а1+б4 с13 = а1+б3 с12 = а1+б2 с32 = а3+б2 с24 = а2+б4 с31=а3+б1
б5=0-0=0. б4=15-0=15. б3=19-0=19. б2=19-0=19. а3=16-19= -3. а2=10-15= -5. б1=14-(-3)=17.
Для каждой свободной клетки определяем относительные оценки по формуле ∆ij= сij-(ai+bj).
∆11=15-(0+17)=-2 ∆21=19-(-5+17)=7
∆22= 18-(-5+19)=4 ∆23=18-(-5+19)=4
∆25=0-(-5+0)=5 ∆33=20-(-3+19)=4
∆34=18-(-3+15)=6 ∆35=0-(-3+0)=3
Матрица оценок:
Проанализировав матрицу оценок видно, что не выполняется условие ∆ij ≥0. Наименьшая отрицательная оценка по абсолютной величине равняется 2.
Для этой клетки строим цикл.
Q = 7.
Теперь выполним сдвиг по циклу на число Q = 7.
Таблица 4.15.
пункты |
С1 |
С2 |
С3 |
С4 |
С5 |
запасы |
потенциалы аi |
М1 |
15 7 |
19 |
19 25 |
15 6 |
0 12 |
50 |
0 |
М2 |
19 |
18 |
18 |
10 30 |
0 |
30 |
-5 |
М3 |
14 5 |
16 15 |
20 |
18 |
0 |
20 |
-1 |
потребности |
12 |
15 |
25 |
36 |
12 |
100 |
|
потенциалы бj |
15 |
17 |
19 |
15 |
0 |
|
|
Находим потенциалы по формуле сij=ai+bj аналогично первому случаю.
Для каждой свободной клетки определяем относительные оценки по формуле ∆ij= сij-(ai+bj) аналогично первому случаю.
Матрица оценок:
Так как оценки всех свободных клеток строго больше 0, т.е. любой другой план будет менее оптимален. Это говорит о единственности оптимального плана. Поскольку все ∆ij ≥0, то задача решена и оптимальный план перевозок имеет суммарную стоимость:
f(x)=15·7+19·25+15·6+0·12+10·30+14·5+16·15=1280 ден.ед.