ВУЗ:
Составители:
Рубрика:
2
==
∑
=
iax
i
n
j
ij
,
1
1,2,…, m.
==
∑
=
jbx
j
m
i
ij
,
1
1,2,…,n.
x
ij
≥ 0, i=1,2,…, m; j=1,2,…,n.
Предполагается, что ,
11
∑∑
==
=
n
j
j
m
i
i
ba т.е. модель закрытая.Если модель не
является закрытой, то вводят ложного поставщика или потребителя с нуле-
выми стоимостями перевозок так, чтобы задача стала закрытой, после чего
ее решают.
Система ограничений задачи содержит mn неизвестных и m+n уравне-
ний. В общем случае система ограничений должна содержать m+n-1 ли-
нейно независимых
уравнений, значит, невырожденный опорный план со-
держит m+n-1 положительных компонент. Клетки таблицы (рисунок 1), в
которых находятся отличные от нуля перевозки, называют занятыми, ос-
тальные – незанятыми. Занятые клетки соответствуют базисным неизвест-
ным, их количество m+n-1.
Опорность плана при записи условий в виде таблицы (рисунок 1) за-
ключается в его ацикличности, т.е
. в таблице нельзя построить замкнутый
цикл, все вершины которого лежат в замкнутых клетках.
Циклом называется набор клеток, в котором две и только две соседние
клетки расположены в одном столбце или одной строке таблицы, причём
последняя клетка находится в той же строке или столбце, что и первая.
Построение циклов начинается в
какой-либо занятой клетке, и перехо-
дят по столбцу или строке к другой занятой клетке, в которой делают пово-
рот под прямым углом и движутся по строке или столбцу к следующей за-
нятой клетке и т.д., пытаясь возвратиться к первоначальной клетке. Если
такой возврат возможен, то получен цикл. Клетки, в
которых происходит
поворот под прямым углом, определяют вершины цикла.
Например:
40
25
20
50
60
5
4 1
20
2
40
40
4
30
2 6 3
10
7 3 5 4
2
n
∑ xij = ai , i = 1,2,…, m.
j =1
m
∑ xij = b j , j = 1,2,…,n.
i =1
xij ≥ 0, i=1,2,…, m; j=1,2,…,n.
m n
Предполагается, что ∑ ai = ∑ b j , т.е. модель закрытая.Если модель не
i =1 j =1
является закрытой, то вводят ложного поставщика или потребителя с нуле-
выми стоимостями перевозок так, чтобы задача стала закрытой, после чего
ее решают.
Система ограничений задачи содержит mn неизвестных и m+n уравне-
ний. В общем случае система ограничений должна содержать m+n-1 ли-
нейно независимых уравнений, значит, невырожденный опорный план со-
держит m+n-1 положительных компонент. Клетки таблицы (рисунок 1), в
которых находятся отличные от нуля перевозки, называют занятыми, ос-
тальные – незанятыми. Занятые клетки соответствуют базисным неизвест-
ным, их количество m+n-1.
Опорность плана при записи условий в виде таблицы (рисунок 1) за-
ключается в его ацикличности, т.е. в таблице нельзя построить замкнутый
цикл, все вершины которого лежат в замкнутых клетках.
Циклом называется набор клеток, в котором две и только две соседние
клетки расположены в одном столбце или одной строке таблицы, причём
последняя клетка находится в той же строке или столбце, что и первая.
Построение циклов начинается в какой-либо занятой клетке, и перехо-
дят по столбцу или строке к другой занятой клетке, в которой делают пово-
рот под прямым углом и движутся по строке или столбцу к следующей за-
нятой клетке и т.д., пытаясь возвратиться к первоначальной клетке. Если
такой возврат возможен, то получен цикл. Клетки, в которых происходит
поворот под прямым углом, определяют вершины цикла.
Например:
40 25 20 50
5 4 1 2
60 20 40
4 2 6 3
40 30 10
7 3 5 4
