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

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

93
7.5.1. Метод северо-западного угла
Он позволяет найти некоторый допустимый план перевозок. Составим
транспортную таблицу некоторой задачи.
j
b
30
80
20
30
90
i
a
120
2
30
4
80
2
10
3
8
30
3
5
6
10
6
20
2
40
6
8
7
4
10
5
30
60
3
4
2
1
4
60
В данном случае имеем задачу закрытого типа, т.к.
45
11
250
ij
ij
ab



.
При построении плана должны учитывать, что сумма перевозок в столбце
должна оказаться равной потребностям в данном пункте, а сумма перевозок в
строке запасу в пункте, соответствующем данной строке.
Заполнение начинается с верхнего левого угла таблицы. Величина пере-
возки устанавливается равной минимальной из величин: величины остатка запа-
сов в пункте i или величины еще неудовлетворенного спроса в пункте j.
Если ресурс в данной строке исчерпан, то переходим к перевозке в следу-
ющей строке текущего столбца (на одну строку вниз).
Если потребности для данного пункта (столбца) удовлетворены, то пере-
ходим к следующей перевозке текущей строки в следующем столбце.
Затраты на перевозку по построенному плану равны
30 2 4 80 2 10 6 10 6 20 4 10 5 30 4 60 1010Q
.
Естественно, что найденный план далек от оптимального.
7.5.2. Метод минимального элемента
В таблице отыскивается
min
ij
c
и в первую очередь заполняется соответ-
ствующая клетка:
min ,
ij i j
x a b
. Затем вычеркивается остаток соответствую-
щей строки, если
ij
ab
, или столбца, если
ij
ab
, и корректируем остатки запа-
сов и неудовлетворенного спроса.
В оставшихся клетках таблицы снова отыскивается минимальная стои-
мость перевозки и заполняется соответствующая клетка и т.д.

Страницы