Численные методы оптимизации. Рейзлин В.И. - 100 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

100
j
v
1
v
2
v
3
v
4
v
5
v
i
u
1
u
2
30
4
80
2
10
3
8
2
u
3
5
6
6
2
30
3
u
6
8
7
4
0
5
40
4
u
3
4
2
10
1
30
4
20
Затраты на перевозку по построенному плану равны:
30 2 4 80 2 10 2 10 1 30 2 30 5 40 4 20 790Q
.
2. Строим систему потенциалов
11
2vu
,
21
4vu
,
31
2vu
,
34
2vu
,
52
2vu
,
44
1vu
,
53
5vu
,
54
4vu
.
Полагаем
1
0u
и находим значения остальных потенциалов:
2
2u
,
3
1u 
,
4
0u
,
1
2v
,
2
4v
,
3
2v
,
4
1v
,
5
4v
.
3. Проверяем систему на потенциальность:
12
03vu
,
13
36vu
,
14
23vu
,
22
25vu
,
23
58vu
,
24
44vu
,
33
37vu
,
32
06vu
,
41
13vu
,
44
11vu
,
51
48vu
,
42
16vu  
,
Система потенциальна, следовательно, план оптимален и окончательные
затраты
min
Q
790.
Определение 4. Допустимый опорный план транспортной задачи называет-
ся невырожденным, если число заполненных клеток транспортной таблицы, т.е.
число положительных перевозок
0
ij
x
, равно
1mn
, где
m
– число пунктов
отправления,
n
– число пунктов назначения.
Определение 5. Если допустимый опорный план содержит менее
1mn
элементов
0
ij
x
, то он называется вырожденным, а транспортная задача назы-
вается вырожденной транспортной задачей.
Следующая теорема позволяет определить вырожденность задачи до ее
решения.
Теорема. Для невырожденной транспортной задачи необходимо и доста-
точно отсутствие такой неполной группы пунктов производства, суммарный

Страницы