3. Решение задачи производится методом потенциалов
Наличие каждого типа флота, принимаемого в расчет, определяется по формулам:
Ф1= 1,1(А1/П11 +А2/П12)=1,1(120/11,4+230/14,2)= 30ед.
Ф2= 1,1(А3/П23 +А4/П24)=1,1(32/10,2+15/9,1)=5ед.
Ф3= 1,1(А5/П35 +А6/П36)=1,1(16/14,1+20/10,7)=4 ед.
где Аj - грузооборот на j-ом участке работы, млн.ткм;
Пij – провозная способность одного судна или состава i-го типа на j-ом участке
работы, млн.ткм;
Исходная матрица Таблица 4
Тип флота |
Наличие флота Фi, ед. |
Участок работы |
|||||||||||
1 |
2 |
3 |
4 |
5 |
6 |
||||||||
Грузооборот Аj, млн. ткм. |
|||||||||||||
120 |
230 |
32 |
15 |
16 |
20 |
||||||||
3 |
30 |
X11 П11=11,4 Э11=8,4 |
X12 14,2 8,9 |
X13 13,0 11,4 |
X14 12,8 12,1 |
X15 10,9 12,4 |
X16 11,9 10,3 |
||||||
5 |
5 |
X21 6,9 10,4 |
X22 10,0 11,2 |
X23 10,2 11,0 |
X24 9,1 10,8 |
X25 7,8 11,2 |
X26 8,4 10,4 |
||||||
9 |
4 |
X31 8,8 8,9 |
X32 14,0 9,4 |
X33 12,3 9,3 |
X34 10,6 9,8 |
X35 14,1 10,2 |
X36 10,7 9,1 |
||||||
Начальный допустимый план составляется способом северо-западного угла. Матрица
заполняется с правой верхней клетки (1-1) исходя из условия:
Xij = min {Фi; Аi/Пij}.
Начальный допустимый план Таблица 5
Тип флота |
Наличие флота ф |
Участок работы |
Резерв |
||||||
1 |
2 |
3 |
4 |
5 |
6 |
|
|||
Грузооборот Аj, млн. ткм. |
|
||||||||
120,00 |
230,00 |
32,00 |
15,00 |
16,00 |
20,00 |
|
|||
3 |
30 |
10,53 |
16,20 |
2,46 |
0,81 |
|
|
|
|
11,40 |
14,20 |
13,00 |
12,80 |
10,90 |
11,90 |
|
|||
8,40 |
8,90 |
11,40 |
12,10 |
12,40 |
10,30 |
|
|||
|
|
|
|
|
|
|
|||
5 |
5 |
|
|
|
0,51 |
2,05 |
2,38 |
0,06 |
|
6,90 |
10,00 |
10,20 |
9,10 |
7,80 |
8,40 |
|
|||
10,40 |
11,20 |
11,00 |
10,80 |
11,20 |
10,40 |
|
|||
|
|
|
|
|
|
|
|||
9 |
4 |
|
|
|
|
|
|
3,94 |
|
8,80 |
14,00 |
12,30 |
10,60 |
14,10 |
10,70 |
|
|||
8,90 |
9,40 |
9,30 |
9,8 |
10,2 |
9,1 |
|
|||
|
|
|
|
|
|
|
|||
X11 = min {Ф1; А1/П11} = min {30; 120/11,4} = min{30;10,53 } = 10,53 ед.
X12 = min {(Ф1 - X11); А2/П12} = min {(30-10,6); 230/14,2} = min{19,5;16,2} = 16,2 ед.
X13 = min {(Ф1 - X11- X12); А3/П13} = min {(30-10,6-16,2); 32/13,0} = min{3,2; 2,46} = 2,46 ед.
X14 = min {(Ф1-Х11-Х12-Х13); А4 П14} = min {30-10,6-16,2-2,5; 15/12,8} = min{0,81; 1,17}= 0,81 ед.
X24 = min {Ф2;( А4-Х14*П14)/ П24} = min {5; (15-0,81*12,8)/9,1} = min{5;0,51}=0,51 ед.
X25 = min {(Ф2–X24); А5/П25} = min {(5-0,51); 16/7,8} = min{4,49; 2,05}=2,05 ед.
X26 = min {(Ф2 -х24-х25); А6/П35} = min {(5-0,51-2,05); 20/8,4} = min{2,44; 2,38}=2,38 ед.
X27 = min {(Ф2–X24- х25-х26); А7/П27} = min {(5-0,51-2,05-2,38); 1} = min{0,06; 1}=0,06 ед.
X3р= 4-0,06=3,94 ед.
Значение целевой функции
F = 10,53*8,4+16,2*8,9+2,46*11,4+0,81*12,1+0,51*10,8+2,05*11,2+2,38*10,4= 342,52
(мл.руб).
Метод потенциалов
Необходимое количество базисных (загруженных) клеток рассчитывается по формуле:
Lнеоб = m+n-1
Где m – количество строк в матрице;
n – количество столбцов в матрице.
Lнеоб = 3+7-1=9
План является невырожденным.
Для расчета потенциалов составляем уравнения для базисных клеток из следующего условия:
αi +βj × Пij = Эij
где αi - потенциал i-ой строки;
βj - потенциал j-го столбца.
α1 =0.
Клетка (1-1) α1 +β1 × П11 = Э11
β1 = (Э11 −α1)/ П11 = (8,4-0)/11,4= 0,73
Клетка (1-2) α1 +β2 × П12 = Э12
β2 = (Э12 −α1) / П12 = (8,9-0)/14,2= 0,63
Клетка (1-3) α1 +β3 × П13 = Э13
β3 = (Э13 −α1)/П13 = (11,4-0)/13= 0,88
Клетка (1-4) α1 +β4 × П14 = Э14
β4 = (Э14 −α1)/П14 = (12,1-0)/12,8= 0,94
Клетка (2-4) α2 +β4 × П24 = Э24
α2 = Э24 –(β4 × П24) =10,8-(0,94*9,1)=2,25
Клетка (2-5) α2 +β5 × П25 = Э25
β5 = (Э25 –α2)/П25 = (11,2-2,25)/7,8= 1,15
Клетка (2-6) α2 +β6 × П26 = Э26
β6 = (Э26 –α2)/П26 = (10,4-,2,25)/8,4= 0,97
Клетка (2-7) α2 +β7 × П27 = Э27
Β7 = (Э27 –α2)/П27 = (0-2,25)/1= -2,25
Клетка (3-7) α3 +β7 × П37= Э37
α3 = Э37 –(β7 × П37) =1-(0-2,25)=3,25
Начальный допустимый план Таблица 6
Тип флота |
Наличие флота ф |
Участок работы |
Резерв |
|
||||||||||||
1 |
2 |
3 |
4 |
5 |
6 |
|
α |
|||||||||
Грузооборот Аj, млн. ткм. |
||||||||||||||||
120,00 |
230,00 |
32,00 |
15,00 |
16,00 |
20,00 |
|
0 |
|||||||||
3 |
30 |
10,53 |
16,20 |
2,46 |
0,81 |
|
|
|
||||||||
11,40 |
14,20 |
13,00 |
12,80 |
10,90 |
11,90 |
|
||||||||||
8,40 |
8,90 |
11,40 |
12,10 |
12,40 |
10,30 |
|
||||||||||
|
|
|
|
|
|
|
||||||||||
5 |
5 |
|
|
|
0,51 |
2,05 |
2,38 |
0,06 |
2,25 |
|||||||
6,90 |
10,00 |
10,20 |
9,10 |
7,80 |
8,40 |
|
||||||||||
10,40 |
11,20 |
11,00 |
10,80 |
11,20 |
10,40 |
|
||||||||||
|
|
|
|
|
|
|
||||||||||
9 |
4 |
|
|
|
|
|
|
3,94 |
3,25 |
|||||||
8,80 |
14,00 |
12,30 |
10,60 |
14,10 |
10,70 |
|
||||||||||
8,90 |
9,40 |
9,30 |
9,8 |
10,2 |
9,1 |
|
||||||||||
|
|
|
|
|
|
|
||||||||||
|
0,73 |
0,36 |
0,88 |
,94 |
1,15 |
0,97 |
-2,25 |
|||||||||
План является оптимальным, если для свободных клеток выполняется условие
Э15=
1+
15-Э15
=
0+1,15
10,9-12,4
= 0,14
Э16=
1+
16-Э16
=
0+0,97
11,9-10,3
= 1,24
Э21=
+
21-Э21
=
2,25+0,73
,4-10,4
= -3,07
Э22=
+
2
22
-
Э22
=
2,25+0,63
10,0-11,2
= -2,65
Э23= + 3 23 - Э23 = 2,25+0,88 10,2-11 = 0,23
Э31=
+
31-Э31
=
3,25+0,73
8,8-8,9
= 0,77
Э32=
+
32-Э32
=
3,25+0,63
14,0-9,4
= 2,67
Э33=
+
33-Э33
=
3,25+0,88
12,3-9,3
= 4,77
Э34=
+
34-Э34
=
3,25+0,94
10,6-9,8
= 3,41
Э35= + 35-Э35 = 3,25+1,15 14,1-10,2 = 9,27
Э36= + 36-Э36= 3,25+0,97 10,7-9,1 = 4,52
План не является оптимальным, т.к. содержит положительные характеристики.
План необходимо улучшить за счет перераспределения флота.
Для всех сторон цепи перераспределения составляются уравнения, исходя из предположения, что клетку с наибольшим отклонением от оптимальности необходимо загрузить на величину Δ > 0 . При любом перераспределении флота в таблице должен сохраняться баланс по строкам и столбцам.
Составляем уравнения:
По второй строке Δ25 + Δ27 = 0
По третьей строке Δ35 + Δ37 = 0
По пятому столбцу Δ25 × П25 + Δ35 × П35 =0
Для резервного столбца уравнение не составляется.
Для решения системы уравнений принимаем с наибольшим отклонением от оптимальности Δ35=1
Δ37 = (0- Δ35) = -1
Δ27
=
-1
Δ25
=
Δ27=0-(-1)= 1
Для всех клеток, в которых Δij < 0 рассчитывается абсолютная величина γij по формуле:
где x ij - количество единиц i-го типа флота на j-ом участке работы.
γ27
0,06
γ37
=
Для нового допустимого плана значения неизвестных определяются по формуле:
xij′ = xij + Δ′ij
где Δ′ij - величина приращения
x ij - значение неизвестных в начальном плане.
Δ′25 = Δ25 × γmin = 1x 0.06= 0,06
Δ′27= Δ27 × γmin = -1x 0,06= -0,06
Δ′35= Δ35 × γmin = 1x 0.06= 0,06
Δ′37 = Δ37 × γmin = -1x 0,06= -0,06
x′25= x 25 + Δ′25 = 0,51 +0,06= 0,57
x′27= x 27+ Δ′27 = 0,06-0,06 = 0
x′35 = x 35+ Δ′35 = 0+0,06 = 0,06
x′37 = x 37 + Δ′37 = 3,94-0,06 = 3,88
Базисные клетки не участвующие в цепи перераспределения переносятся в новую таблицу без изменения.
Таблица 7