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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

Ответ: min Z(X) = 590 при X =
03020
20100
2000
.
Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены.
Пусть имеется транспортная задача с балансовыми условиями
∑
ji
x
,
= a
i
(i = 1…m; j = 1...n);
∑
ji
x
,
= b
j
(j = 1…n; 1...m).
Причем
∑
i
a =
∑
i
b .
Стоимость перевозки единицы груза из А
i
в В
j
равна C
i,j
; таблица стоимостей задана. Требуется най-
ти план перевозок (x
i,j
), который удовлетворял бы балансовым условиям и при этом стоимость всех пе-
ревозок была минимальна.
Идея метода потенциалов для решения транспортной задачи сводится к следующему. Представим
себе, что каждый из пунктов оправления A
i
вносит за перевозку единицы груза (все равно куда) какую-
то сумму α
i
; в свою очередь каждый из пунктов назначения В
j
также вносит за перевозку груза (куда
угодно) сумму β
j
. Эти платежи передаются некоторому третьему лицу («перевозчику»). Обозначим α
i
+
β
j
= c
i,j
(i = 1...m; j = 1...n) и будем называть величину с
i,j
«псевдостоимостью» перевозки единицы груза
из А
i
в В
j
. Заметим, что платежи α
i
и β
j
не обязательно должны быть положительными; не исключено,
что «перевозчик» сам платит тому или другому пункту какую-то премию за перевозку. Также надо от-
метить, что суммарная псевдостоимость любого допустимого плана перевозок при заданных платежах
(α
i
и β
j
) одна и та же и от плана к плану не меняется.
До сих пор мы никак не связывали платежи (α
i
и β
j
) и псевдостоимости с
i,j
с истинными стоимостя-
ми перевозок С
i,j
. Теперь мы установим между ними связь. Предположим, что план (x
i,j,
) невырожден-
ный (число базисных клеток в таблице перевозок равно (m + n – 1). Для всех этих клеток x
i,j
> 0. Опреде-
лим платежи (α
i
и β
j
) так, чтобы во всех базисных клетках псевдостоимости были равны стоимостям
α
i
+ β
j
= C
i,j
= c
i,j
,
а для всех свободных клеток (X
i,j
= 0)
α
i
+ β
j
≤ C
i,j
,
то план является оптимальным и никакими способами улучшен быть не может. Нетрудно показать,
что это теорема справедлива также для выраженного плана, и некоторые из базисных переменных ров-
ны нулю. План обладающий свойством для клеток:
– базисных C
i,j
= c
i,j
; (5.1)
– свободных C
i,j
, c
i,j
;
(5.2)
называется потенциальным планом, а соответствующие ему платежи (α
i
и β
j
) – потенциалами пунктов А
i
в
В
j
(i = 1, …, m; j = 1, …, n). Пользуясь этой терминологией вышеупомянутую теорему можно сформули-
ровать так: Всякий потенциальный план является оптимальным. Итак, для решения транспортной
задачи нам нужно одно – построить потенциальный план. Оказывается его можно построить методом
последовательных приближений, задаваясь сначала какой-то произвольной системой платежей, удовле-
творяющей условию (5.1). При этом в каждой базисной клетке получится сумма платежей, равная стои-
мости перевозок в данной клетке; затем, улучшая план следует одновременно менять систему платежей
так, что они приближаются к потенциалам. При улучшении плана нам помогает следующее свойство
платежей и псевдостоимостей: Какова бы ни была система платежей (α
i
в β
j
) удовлетворяющая условию
(5.1), для каждой свободной клетки цена цикла перерасчета равна разности между стоимостью и псев-
достоимостью в данной клетке: γ
i,j
= c
i,j
– C
i,j
.
Таким образом при использовании методом потенциалов для решения транспортной задачи
отпадает наиболее трудоемкий элемент распределительного метода: поиски циклов с отрица-
тельной ценой.
Процедура построения потенциального (оптимального) плана состоит в следующем.

Страницы