Математические методы в коммерческой деятельности. Буравлева О.Ю. - 28 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

Итак, мы приходим к следующему алгоритму решения транспортной задачи методом потенциалов:
− взять любой опорный план перевозок, в котором отмечены m + n – 1 базисных клеток (остальные
клетки свободные);
− определить для этого плана платежи (α
i
и β
j
) исходя из условия, чтобы в любой базисной клетке
псевдостоимости были равны стоимостям. Один из платежей можно назначить произвольно, например,
положить равным нулю;
− подсчитать псевдостоимости С
i,j
= α
i
+ β
j
для всех свободных клеток. Если окажется, что все они
не превышают стоимостей, то план оптимален. Если хотя бы в одной свободной клетке псевдостои-
мость превышает стоимость, следует приступить к улучшению плана путем переброски перевозок по
циклу, соответствующему любой свободной клетке с отрицательной ценой (для которой псевдостои-
мость больше стоимости);
− после этого заново подсчитываются платежи и псевдостоимости, и, если план еще не оптимален,
процедура улучшения продолжается до тех пор, пока не будет найден оптимальный план.
Так в нашем примере после двух циклов расчетов получим оптимальный план вида:
X
2
=
060014
000270
260004
064200
x
,
где 0
x
– базисный нуль.
При этом стоимость всей перевозки изменялась следующим образом
Z(X
0
) = 703,
Z(X) = 709,
Z(X
2
) = Z
min
= 703.
Следует также отметить, что оптимальный план может иметь и другой вид, но его стоимость оста-
нется такой же Z
min
= 703.
Однако на практике чаще встречаются задачи с неправильным балансом.
1 Пусть суммарные запасы поставщиков превосходят суммарные запасы потребителей, т.е.
∑
=
m
i
i
a
1
>
∑
=
n
j
j
b
1
.
Очевидно, что в этом случае при составлении оптимального плана перевозок часть запасов постав-
щиков, равная
b
n+1
=
∑
=
m
i
i
a
1
–
∑
=
n
j
j
b
1
останется не вывезенной. Поэтому в системе ограничений транспортной задачи первую группу уравне-
ний (i ∈ 1, m ) следует заменить неравенствами вида «≤».
Вторая группа уравнений остается без имени, так как запросы всех потребителей удовлетворяются
полностью. Для приведения к канонической форме в полученные неравенства вводят дополнительные
переменные x
1(n+1)
, x
2(n+1)
, …, x
m(n+1)
. В результате первые m ограничений задачи принимают вид
∑
=
n
j
ij
x
1
+ x
i(n+1)
= a
i
, i = 1, 2, …, m.
В целевую функцию дополнительные переменные не входят (входят с нулевыми коэффициен-
тами). Математическая модель задачи принимает вид
Z(X) =
∑∑∑
===
+
m
i
m
i
n
j
ijij
xc
111
0 x
i(n+1)
→ min, (5.4)
∑
=
n
j
ij
x
1
+ x
i(n+1)
= a
i
, i = 1, 2, …, m, (5.5)

Страницы