2.3. Составление математической модели задачи
При разработке математической модели задачи решаются следующие вопросы:
выбор параметров управления;
выбор показателя качества (критерия оптимальности);
формирование ограничений и целевой функции в общем виде и с использованием конкретных числовых данных.
Выбор критерия оптимальности в расстановочной задаче существенно зависит от соотношения провозной способности флота П и объема перевозок Q. В курсовой работе П <Q, т.е. флота недостаточно для выполнения всех перевозок.
Критерий оптимальности - максимум чистой валютной выручки (ЧВВ)
∆ Fij= Fij- Rij ( i=1,m; j=1,n)
Математическая модель задачи в общем виде такова:
(5)
(l
=1,S),
(6)
( i=1,m), (7)
≥0
( i=1,m; j=1,n),
(8)
где
–
число рейсов судов i-го
типа на j-ой
схеме движения, судо- рейсы;
Ti - бюджет времени в эксплуатации судов i-го типа, судо-сутки;
Ti=Ni*T ( i=1,m)
где Ni- число судов i-го типа;
Т- продолжительность планового периода;
Ql - количество груза, предъявленное к перевозке на l-ом участке, тыс.т;
G1 -множество схем движения, содержащих l-й участок;
S- количество груженых участков.
Математическая модель задачи представлена в координатной форме:
Z=∆F11x11+∆F12x12+∆F13x13+∆F14x14+∆F15x15+∆F21x21+∆F22x22+∆F23x23+
+∆F24x24+∆F25x25 max
Ограничения первого типа записывают в координатной форме для груженых участков:
q11x11 + q11x15+ q21x21+ q21x25 ≤Q1
q12x11 + q11x13+ q22x21 + q22x23 ≤Q2
q13x12 + q13x13 +q13x14 + q23x22+ q23x23 + q23x24 ≤Q3
q14x13 + q14x14 + q24x23+ q24x24 ≤Q4
Ограничения второго типа по судам записывают в координатной форме:
t11x11+ t12x12+ t13x13 + t14x14+ t15x15 =T1
t21x21+ t22x22+ t23x23 + t24x24+ t25x25 =T2
Условие неотрицательности:
≥0
(
i=1,
m)
( j=1,n)
Математическая модель задачи в координатной форме с подстановкой числовых значений исходных данных:
Z=380,8x11 + 210x12 + 610,4x13 + 425,6x14 +196х15 + 403,2x21 +231x22 +364x23
+
427х24
+
235,5x25
max
10x11 + 10x15+ 12x21+12х25 ≤ 700
11x11 + 11х13 + 10x21 + 10x23 ≤ 500
10x12 + 10x13 +10x14 + 11x22 +11x23 + 11x24 ≤ 600
11x13 + 11x14 + 10x23+10х24 ≤ 680
115x11+ 72x12+151x13 + 114x14 +78х15 =1825
116x21+ 75x22+ 150x23 + 118x24 +84х15=3285
≥0 ( i=1,3) и ( j=1,4)
Приведём модель к каноническому виду. Для этого введём в ограничения по участкам дополнительные переменные ( s1, s2, s3 ,s4). Введём искусственные переменные (A1,A2) в ограничения по судам, необходимые для построения исходного опорного плана. Математическая модель принимает следующий вид:
10x11+ 10x15+ 12x21+ 12x25+ +S1 =700
11x11+ 11x13+ 10x21+ 10x23+ +S2 =500
10x12+ 10x13+ 10x14+ 11x22+11x23+11x24+ +S3 =600
11x13+ 11x14+ 1023+10x24+ +S4 =680
115x11+72x12+151x13+114x14+78x15+ +A1 =1825
116x21+75x22+150x23+118x24+84x25+ +A2 =3285
Z= 380,8x11+210x12+610,4x13+425,6x14+196х15+403,2x21+231x22+364x23+
+ 427х24+ 235,2x25+ 0· S1 + 0 ·S2+ 0 ·S3 +0· S4–М· A1 –M · A2 max
Исходная симплекс-таблица выглядит следующим образом(таблица №6):
Табл. 6
Исходная симплекс-таблица(1)
№ строки |
Ба зис |
Сб |
В |
380.8 |
210 |
610.4 |
425.6 |
196 |
403.2 |
231 |
364 |
427 |
235.2 |
0 |
0 |
0 |
0 |
-M |
-M |
x11 |
x12 |
x13 |
x14 |
x15 |
х21 |
х22 |
x23 |
x24 |
х25 |
S1
|
S2
|
S3
|
S4
|
A1
|
A2 |
||||
1 |
S1 |
0 |
700 |
10 |
0 |
0 |
0 |
10 |
12 |
0 |
0 |
0 |
12 |
1 |
0 |
0 |
0 |
0 |
0 |
2 |
S2 |
0 |
500 |
11 |
0 |
11 |
0 |
0 |
10 |
0 |
10 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
3 |
S3 |
0 |
600 |
0 |
10 |
10 |
10 |
0 |
0 |
11 |
11 |
11 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
4 |
S4 |
0 |
680 |
0 |
0 |
11 |
11 |
0 |
0 |
0 |
10 |
10 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
5 |
А1 |
-M |
1825 |
115 |
72 |
151 |
114 |
78 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
6 |
А2 |
-M |
3285 |
0 |
0 |
0 |
0 |
0 |
116 |
75 |
150 |
118 |
84 |
0 |
0 |
0 |
0 |
0 |
1 |
m+1 |
Zj-Cj |
0 |
-380.8 |
-210 |
-610.4 |
-425.6 |
-196 |
-403.2 |
-231 |
-364 |
-427 |
-235.2 |
0 |
0 |
0 |
0 |
0 |
0 |
|
m+2 |
-5110 |
-115 |
-72 |
-151 |
-114 |
-78 |
-116 |
-75 |
-150 |
-118 |
-84 |
0 |
0 |
0 |
0 |
0 |
0 |
||
Перепишем симплекс-таблицу в вид, который нам наиболее удобен для дальнейшей работы. Представим это в таблице № 7.
Табл. 7
Исходная симплекс-таблица(2)
x11 |
x12 |
x13 |
x14 |
x15 |
х21 |
х22 |
x23 |
x24 |
x25 |
|
|
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
|
|
380.8 |
210 |
610.4 |
425.6 |
196 |
403.2 |
231 |
364 |
427 |
235.2 |
|
|
10 |
0 |
0 |
0 |
10 |
12 |
0 |
0 |
0 |
12 |
≤ |
700 |
11 |
0 |
11 |
0 |
0 |
10 |
0 |
10 |
0 |
0 |
≤ |
500 |
0 |
10 |
10 |
10 |
0 |
0 |
11 |
11 |
11 |
0 |
≤ |
600 |
0 |
0 |
11 |
11 |
0 |
0 |
0 |
10 |
10 |
0 |
≤ |
680 |
115 |
72 |
151 |
114 |
78 |
0 |
0 |
0 |
0 |
0 |
= |
1825 |
0 |
0 |
0 |
0 |
0 |
116 |
75 |
150 |
118 |
84 |
= |
3285 |
Для решения поставленной перед нами задачи был использован симплекс-метод.