5018
.pdfТаблица 8 – Данные задания 7 «Транспортная задача»
№ |
с11 |
|
с12 |
|
|
с13 |
|
с21 |
с22 |
с23 |
с31 |
|
с32 |
|
с33 |
|
с41 |
с42 |
с43 |
||||
1 |
4 |
|
|
3 |
6 |
|
4 |
|
|
1 |
6 |
|
2 |
8 |
|
2 |
|
8 |
3 |
|
7 |
||
2 |
4 |
|
|
3 |
6 |
|
4 |
|
|
1 |
6 |
|
7 |
8 |
|
2 |
|
4 |
5 |
|
3 |
||
3 |
4 |
|
|
3 |
5 |
|
4 |
|
|
1 |
6 |
|
7 |
8 |
|
2 |
|
8 |
5 |
|
7 |
||
4 |
4 |
|
|
3 |
6 |
|
4 |
|
|
1 |
6 |
|
7 |
8 |
|
2 |
|
9 |
5 |
|
7 |
||
5 |
2 |
|
|
7 |
3 |
|
6 |
|
|
4 |
3 |
|
7 |
4 |
|
5 |
|
4 |
6 |
|
2 |
||
6 |
4 |
|
|
7 |
6 |
|
6 |
|
|
4 |
3 |
|
1 |
4 |
|
3 |
|
4 |
6 |
|
2 |
||
7 |
2 |
|
|
5 |
6 |
|
6 |
|
|
4 |
3 |
|
1 |
4 |
|
3 |
|
4 |
6 |
|
2 |
||
8 |
8 |
|
|
3 |
5 |
|
2 |
|
|
4 |
6 |
|
6 |
7 |
|
1 |
|
9 |
4 |
|
3 |
||
9 |
8 |
|
|
6 |
5 |
|
2 |
|
|
4 |
1 |
|
6 |
7 |
|
5 |
|
9 |
4 |
|
3 |
||
10 |
8 |
|
|
6 |
5 |
|
2 |
|
|
2 |
1 |
|
6 |
7 |
|
1 |
|
9 |
4 |
|
3 |
||
11 |
8 |
|
|
6 |
5 |
|
2 |
|
|
3 |
1 |
|
6 |
7 |
|
1 |
|
9 |
4 |
|
3 |
||
12 |
4 |
|
|
5 |
7 |
|
7 |
|
|
8 |
2 |
|
4 |
1 |
|
6 |
|
4 |
3 |
|
6 |
||
13 |
8 |
|
|
5 |
7 |
|
7 |
|
|
8 |
2 |
|
4 |
1 |
|
6 |
|
4 |
3 |
|
3 |
||
14 |
7 |
|
|
5 |
8 |
|
2 |
|
|
8 |
7 |
|
6 |
1 |
|
4 |
|
2 |
3 |
|
4 |
||
15 |
3 |
|
|
5 |
4 |
|
2 |
|
|
8 |
7 |
|
6 |
3 |
|
4 |
|
5 |
3 |
|
7 |
||
16 |
2 |
|
|
5 |
4 |
|
2 |
|
|
8 |
7 |
|
6 |
3 |
|
4 |
|
6 |
3 |
|
5 |
||
17 |
2 |
|
|
5 |
4 |
|
2 |
|
|
4 |
7 |
|
6 |
3 |
|
2 |
|
6 |
3 |
|
5 |
||
18 |
2 |
|
|
5 |
4 |
|
2 |
|
|
4 |
7 |
|
6 |
3 |
|
2 |
|
4 |
3 |
|
6 |
||
19 |
2 |
|
|
5 |
4 |
|
2 |
|
|
4 |
6 |
|
5 |
3 |
|
2 |
|
4 |
3 |
|
6 |
||
20 |
5 |
|
|
4 |
6 |
|
2 |
|
|
4 |
6 |
|
5 |
3 |
|
2 |
|
4 |
3 |
|
6 |
||
Таблица 9 – Данные задания 7 «Транспортная задача» |
|
|
|
|
|
|
|||||||||||||||||
№ |
|
|
|
а1 |
|
|
а2 |
|
|
а3 |
|
|
а4 |
|
b1 |
|
|
b2 |
|
|
b3 |
||
1 |
|
|
30 |
|
|
40 |
|
|
|
50 |
|
10 |
|
|
40 |
|
|
70 |
|
20 |
|
||
2 |
|
|
25 |
|
|
45 |
|
|
|
50 |
|
10 |
|
|
35 |
|
|
65 |
|
20 |
|
||
3 |
|
|
20 |
|
|
40 |
|
|
|
45 |
|
10 |
|
|
35 |
|
|
65 |
|
20 |
|
||
4 |
|
|
20 |
|
|
40 |
|
|
|
55 |
|
10 |
|
|
35 |
|
|
70 |
|
20 |
|
||
5 |
|
|
22 |
|
|
44 |
|
|
|
54 |
|
20 |
|
|
35 |
|
|
70 |
|
60 |
|
||
6 |
|
|
25 |
|
|
45 |
|
|
|
30 |
|
20 |
|
|
35 |
|
|
70 |
|
60 |
|
||
7 |
|
|
25 |
|
|
45 |
|
|
|
30 |
|
20 |
|
|
20 |
|
|
70 |
|
60 |
|
||
8 |
|
|
20 |
|
|
40 |
|
|
|
30 |
|
20 |
|
|
20 |
|
|
70 |
|
60 |
|
||
9 |
|
|
15 |
|
|
40 |
|
|
|
30 |
|
20 |
|
|
20 |
|
|
30 |
|
55 |
|
||
10 |
|
|
15 |
|
|
40 |
|
|
|
30 |
|
15 |
|
|
20 |
|
|
30 |
|
55 |
|
||
11 |
|
|
15 |
|
|
26 |
|
|
|
30 |
|
15 |
|
|
20 |
|
|
32 |
|
55 |
|
||
12 |
|
|
10 |
|
|
25 |
|
|
|
30 |
|
15 |
|
|
40 |
|
|
15 |
|
15 |
|
||
13 |
|
|
10 |
|
|
25 |
|
|
|
30 |
|
35 |
|
|
40 |
|
|
15 |
|
15 |
|
||
14 |
|
|
10 |
|
|
25 |
|
|
|
30 |
|
35 |
|
|
30 |
|
|
30 |
|
40 |
|
||
15 |
|
|
28 |
|
|
25 |
|
|
|
10 |
|
15 |
|
|
34 |
|
|
25 |
|
25 |
|
||
16 |
|
|
20 |
|
|
15 |
|
|
|
10 |
|
15 |
|
|
30 |
|
|
10 |
|
20 |
|
||
17 |
|
|
15 |
|
|
15 |
|
|
|
10 |
|
20 |
|
|
30 |
|
|
10 |
|
20 |
|
||
18 |
|
|
35 |
|
|
15 |
|
|
|
10 |
|
20 |
|
|
30 |
|
|
10 |
|
20 |
|
||
19 |
|
|
23 |
|
|
15 |
|
|
|
10 |
|
20 |
|
|
30 |
|
|
10 |
|
25 |
|
||
20 |
|
|
16 |
|
|
15 |
|
|
|
10 |
|
20 |
|
|
30 |
|
|
10 |
|
29 |
|
31
Пример 7. Решить транспортную задачу, используя следующие данные:
|
|
|
|
5 |
3 |
6 |
|
ai |
30,45,50,25 ; |
C |
c |
5 |
1 |
6 |
. |
b j |
40,70,30 ; |
|
ij |
2 |
7 |
2 |
|
|
|
|
|||||
|
|
|
|
8 |
3 |
7 |
|
|
|
|
|
|
|
4 |
3 |
|
|
|
Решение: |
Транспортная задача называется закрытой если |
ai |
bj . |
|
||||||
|
|
|
|
|
|
i |
1 |
j 1 |
|
|
Проверим модель на сбалансированность: |
|
|
|
|
|
|||||
4 |
|
|
|
3 |
|
|
|
|
|
|
ai a1 |
a2 |
a3 |
a4 |
30 45 50 25 150, |
b j b1 |
b2 b3 40 |
70 |
30 |
140. |
|
i 1 |
|
|
|
j 1 |
|
|
|
|
|
|
|
|
4 |
3 |
|
|
|
|
|
|
|
Так как |
ai |
b j , условие баланса не выполняется, |
данная модель |
|||||||
|
|
i |
1 |
j 1 |
|
|
|
|
|
|
является |
открытой. |
Приведём задачу к закрытому виду; |
введём |
фиктивного |
||||||
|
|
|
|
|
4 |
|
3 |
|
|
|
потребителя |
B4 , |
потребность которого равна |
b4 |
ai |
b j |
150 |
140 |
10 ед. |
||
|
|
|
|
|
i 1 |
j |
1 |
|
|
|
груза. Стоимости перевозки единицы груза (тарифы) для фиктивного потребителя (поставщика) принимаются равными 0.
Составим исходный план перевозок методом «наименьшего элемента» (минимальной стоимости). Поставки в клетки с нулевыми тарифами осуществляются в последнюю очередь.
1) Выбираем клетку (2,2) с наименьшим «реальным» тарифом равным 1. Записываем в эту клетку максимально возможную поставку 45 ед. груза, т.е. наименьшее из чисел a2 45 и b2 70 . Исключаем при этом из дальнейшего рассмотрения поставщика A2 (его возможности полностью исчерпаны). Запомним, что потребитель B2 еще нуждается в 70−45=25 ед. груза.
2) Минимальный тариф равный 2 соответствует двум клеткам (3,1) и (3,3) выбираем любую, например клетку (3,1), помещаем в эту клетку 40 ед. груза ( a3 50 , b1 40) и исключаем из рассмотрения потребителя B1 (его потребности полностью удовлетворены). У поставщика A3 ещё имеется в 50−40=10 ед. груза.
3) Заполним клетку (3,3), которой соответствует минимальный тариф равный 2,
поставка в этой клетке равна 10 ( a3 |
10 , b3 |
30 ), исключаем из рассмотрения |
||||||
A3 . У потребителя B3 еще имеется потребность в 30−10=20 ед. груза. |
|
|
||||||
4) В оставшейся части таблицы наименьший |
тариф |
3 соответствует клеткам |
||||||
(1,2) |
и (4,2), выберем клетку |
(4,2) и поместим |
поставку 25 |
ед. |
груза |
|||
( a4 |
25,b2 25 ). |
Исключаем |
из |
рассмотрения |
два пункта |
A4 |
и B2 |
32
одновременно, поэтому в клетку (4,3), стоящую рядом |
с клеткой (4,2) запишем |
|||||||||||||||||||
0. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5) В клетку (1,3) помещаем 20 ед. груза ( a1 |
30,b3 |
|
20 ), исключаем потребителя |
|||||||||||||||||
B3 . При этом у поставщика A1 |
еще имеется в 30−20=10 ед. груза. |
|
|
|
||||||||||||||||
6) Заполним |
последнюю оставшуюся клетку (1,4) поставкой 10 единиц груза. |
|||||||||||||||||||
Все запасы распределены, а потребности удовлетворены. |
|
|
|
|
|
|||||||||||||||
В опорном плане число занятых поставками клеток должно быть равно |
||||||||||||||||||||
числу m |
n |
1 |
4 |
4 |
1 |
7 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
План- |
|
|
B1 |
|
B2 |
|
B3 |
|
|
B4 |
|
U i |
|
|
|
||
|
|
|
1 |
|
|
40 |
|
70 |
|
30 |
|
10 |
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
30 |
|
|
5 |
|
3 |
|
6 |
|
|
0 |
|
U1 |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
20 |
|
10 |
|
|
|
|
|
|
|
|
|
|
A1 |
|
|
-1 |
+ |
1 |
|
− |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
45 |
|
|
5 |
|
1 |
|
6 |
|
|
0 |
|
U 2 |
3 |
|
|
|
|
|
|
|
|
|
|
|
45 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A2 |
|
|
0 |
|
|
|
1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
50 |
|
|
2 |
|
7 |
|
2 |
|
|
0 |
|
U 3 |
0 |
|
|
|
|
|
|
|
|
|
40 − |
|
|
+ |
10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
A3 |
|
|
|
|
9 |
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
25 |
|
|
8 |
|
3 |
|
7 |
|
|
0 |
|
U 4 |
5 |
|
|
|
|
|
|
|
|
|
|
|
25 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
A4 |
|
|
1 |
|
|
|
|
|
-1 |
|
|
|
|
|
|
|
|
|
|
|
V j |
|
V1 |
2 |
V2 |
2 |
V3 |
2 |
V4 |
4 |
Z1 |
340 |
|
|
|
|||
Z1 |
6 |
20 |
0 10 |
1 45 |
2 |
40 |
2 10 |
3 25 |
7 |
0 |
120 |
45 |
80 |
20 |
75 |
340. |
Проверим полученный план на оптимальность |
методом потенциалов: |
|
|||||
а) Потенциалами |
строк |
–U i |
и |
столбцов |
– V j |
называются |
числа, |
удовлетворяющие |
условию |
Ui |
Vj |
cij для базисных |
переменных |
(для |
заполненных клеток).
Так как система для определения потенциалов содержит на одно уравнение меньше, чем число потенциалов, то, чтобы найти решение системы потенциалов, один потенциал задаём произвольно, например, U3 0 .
Остальные потенциалы найдём, решая систему уравнений:
33
U1 |
V3 |
6, |
V1 |
2 U3 |
2 0 |
2, |
|
U1 |
V4 |
0, |
V3 |
2 |
U3 |
2 0 2, |
|
U2 |
V2 |
1, |
U4 |
7 V3 |
7 2 5, |
||
U3 |
V1 |
2, |
V2 |
3 |
U4 |
3 5 |
2, |
U3 |
V3 |
2, |
U2 |
1 |
V2 |
1 |
2 3, |
U4 |
V2 |
3, |
U1 |
6 |
V3 |
6 2 |
4, |
U4 |
V3 |
7, |
V4 |
U1 |
4. |
|
б) |
Определяем |
характеристики |
|
для |
свободных |
клеток |
по формуле |
||||||||
Eij cij |
Ui |
V j |
и запишем их в левом нижнем углу свободных клеток. План |
||||||||||||
является оптимальным если все Eij |
0 . |
|
|
|
|
|
|
|
|
||||||
|
E11 |
5 |
(4 |
2) |
1; |
E23 |
6 |
3 |
2 |
1; |
E34 |
0 |
0 |
4 |
4; |
|
E12 |
3 |
4 |
2 |
1; |
E24 |
0 |
3 |
4 |
1; |
E41 |
8 |
5 |
2 |
1; |
|
E21 |
5 |
3 |
2 |
0; |
E32 |
7 |
0 |
2 |
9; |
E44 |
0 |
(5 |
4) |
1. |
План 1 не оптимален, так как E11 0 и E44 0 .
Улучшим план. Выберем клетку с наименьшей отрицательной характеристикой, например, клетку (1,1) пометим знаком «+» и построим для неё контур:
(1,1) |
(1,3) (3,3) (3,1). |
Контур удовлетворяет |
следующим условиям: это замкнутая ломаная, |
состоящая из вертикальных и горизонтальных отрезков; отрезки контура могут пересекаться; все вершины контура находятся в заполненных клетках, за исключением той клетки, для которой он строится; число вершин ─ чётное.
Клетки, в которых находятся вершины контура, поочередно помечаем знаками «+» и «─». Из клеток, помеченных знаком «─», выбираем наименьшую
поставку |
min 20,40 20 . Число |
перераспределяется по контуру, в |
клетках со знаком «+» добавляется |
, в клетках со знаком «─» отнимается . |
После перераспределения груза, только одна вершина контура становится свободной.
Строим новый план перевозок.
34
План- |
|
B1 |
|
B2 |
|
B3 |
|
B4 |
U i |
|
2 |
40 |
|
70 |
|
30 |
|
10 |
|
||
|
|
|
|
|
|
|||||
30 |
|
5 |
|
3 |
|
6 |
|
0 |
U1 |
3 |
|
20 |
|
|
|
|
|
10 |
|
|
|
A1 |
+ |
|
2 |
|
1 |
|
− |
|
|
|
45 |
|
5 |
|
1 |
|
6 |
|
0 |
U 2 |
2 |
|
|
|
45 |
|
|
|
|
|
|
|
A2 |
1 |
|
|
|
2 |
|
1 |
|
|
|
50 |
─ 2 |
|
7 |
+ |
2 |
|
0 |
U 3 |
0 |
|
|
20 |
|
|
30 |
|
|
|
|
||
A3 |
|
|
9 |
|
|
|
3 |
|
|
|
25 |
|
8 |
|
3 |
─ 7 |
+ |
0 |
U4 |
5 |
|
|
|
|
25 |
|
|
0 |
|
|
|
|
A4 |
1 |
|
|
|
|
|
-2 |
|
|
|
V j |
V1 |
2 |
V2 |
2 |
V3 |
2 |
V4 |
3 |
Z2 |
320 |
Затраты на реализацию плана 2 составляют:
Z1 5 20 0 10 145 2 20 2 30 325 7 0 100 45 40 60 75 320.
Найдем потенциалы строк и столбцов, для чего составим систему уравнений.
Потенциал |
U3 примем равным 0. |
|
|||||
U1 |
V3 |
5, |
V1 |
2 U3 |
2 0 2, |
||
U1 |
V4 |
0, |
V3 |
2 U3 |
2 |
0 2, |
|
U2 |
V2 |
1, |
U4 |
7 V3 |
7 2 5, |
||
U3 |
V1 |
2, |
V2 |
3 U4 |
3 |
5 |
2, |
U3 |
V3 |
2, |
U2 |
1 V2 |
1 |
2 |
3, |
U4 |
V2 |
3, |
U1 |
5 V3 |
5 2 3, |
||
U4 |
V3 |
7, |
V4 |
0 U1 |
|
3. |
|
Определим характеристики для свободных клеток.
E12 |
3 |
3 |
2 |
2; |
E23 |
6 |
2 |
2 |
2; |
E34 |
0 |
0 |
3 |
3; |
E13 |
6 |
(3 |
2) |
1 |
E24 |
0 |
2 |
3 |
1; |
E41 |
8 |
5 |
2 |
1; |
E21 |
5 |
2 |
2 |
1; |
E32 |
7 |
0 |
2 |
9; |
E44 |
0 |
(5 |
3) |
2. |
План 2 |
не является оптимальным, т.к. E44 |
2 |
|
|
|
|||||||||
После применения, |
рассмотренного выше алгоритма, получили план 3. |
35
План- |
|
B1 |
|
B2 |
|
B3 |
|
B4 |
U i |
|
3 |
40 |
|
70 |
|
30 |
|
10 |
|
||
|
|
|
|
|
|
|||||
30 |
5 |
|
3 |
|
6 |
|
0 |
U1 |
3 |
|
|
20 |
|
|
|
|
|
10 |
|
|
|
A1 |
|
|
0 |
|
1 |
|
|
|
|
|
45 |
|
5 |
|
1 |
|
6 |
|
0 |
U2 |
1 |
|
|
|
45 |
|
|
|
|
|
|
|
A2 |
2 |
|
|
|
3 |
|
2 |
|
|
|
50 |
|
2 |
|
7 |
|
2 |
|
0 |
U 3 |
0 |
|
20 |
|
|
|
30 |
|
|
|
|
|
A3 |
|
|
7 |
|
|
|
3 |
|
|
|
25 |
|
8 |
|
3 |
|
7 |
|
0 |
U4 |
3 |
|
|
|
25 |
|
|
|
0 |
|
|
|
A4 |
3 |
|
|
|
2 |
|
|
|
|
|
V j |
V1 |
2 |
V2 |
0 |
V3 |
2 |
V4 |
3 |
Z2 |
320 |
План 3 является оптимальным, т, к. все |
Eij |
0 . Затраты на реализацию |
||||||||
оптимального плана составляют Z3 |
320. |
|
|
|
|
|
36