Транспортная задача по критерию времени

найденном оптимальном  решении X опт полагают все перевозки из

фиктивного  пункта или в него равными нулю, то есть отбрасывают их, и

вычисляют итоговое значение целевой функции используя  первоначальные

матрицы C и T .

Количество  единиц товара, перевозимого из пункта производства Ai в

пункт потребления B j , не может быть отрицательным, поэтому необходимо

ввести следующее  условие:

xij≥0, i=11m , j=11 n.

После того, как  будет найдено X опт для целевой функции

T=max

xij0

tij ,i=11m , j=11n , попытаемся дооптимизировать полученное

решение по критерию стоимости, предварительно заблокировав в матрице C

те элементы, которым соответствуют элементы матрицы T такие, что

tijmax

xij0

tij , xij∈ X опт . То есть при дооптимизации по критерию стоимости

необходимо  избежать увеличения продолжительности  самой длительной

перевозки. При  этом целевой функцией будет функция L=Σ

i =1

m

Σj

=1

n

cij⋅xijmin .

3. Краткие сведения  о методе решения  задачи

3.1. Метод северо-западного угла

Данный метод используется для построения начального опорного плана

транспортной  задачи.

Описание алгоритма.

1. Определяют  верхний левый элемент матрицы  X:

x11=min a1 , b1

Возможны три  случая:

а) если a1b1 , то x11=a1 и вся первая строка, начиная со второго

элемента, заполняют  нулями;

5

б) если a1b1 , то x11=b1 , а все оставшиеся элементы первого столбца

заполняют нулями;

в) если a1=b1 , то x11=a1=b1 и все оставшиеся элементы первых столбца

и строки заполняют  нулями.

На этом один шаг метода заканчивается.

2. Пусть уже проделано k шагов, (k + 1)-й шаг состоит в следующем.

Определяют  верхний левый элемент незаполненной  части матрицы X.

Пусть это элемент

x λ μ

 λμ=k2  ,

причем

x λμ=min a λ

k  , bμ

 k  ,

где

a λ

 k =a λ−Σ

j=1

μ−1

x λj

bμ

 k =bμ−Σ

i =1

λ−1

xiμ

Если a λ

 k bμ

 k  то заполняем нулями λ -ю строку, начиная с ( μ1 )-го

элемента. В  противном случае заполняем нулями оставшуюся часть μ -ro

столбца.

3.2. Метод потенциалов

Метод потенциалов  позволяет, исходя из некоторого опорного плана,

построить за конечное число итераций решение Т-задачи.

Общая схема метода. В данном начальном опорном плане перевозок

каждому пункту ставят в соответствие некоторое  число, называемое его

предварительным потенциалом. Предварительные потенциалы выбирают так,

чтобы их разность для любой пары пунктов Ai и B j , связанных основной

коммуникацией, была равна cij . Если окажется, что разность

предварительных потенциалов для всех других коммуникаций не превосходит

cij , то данный план перевозок – оптимальное решение задачи. В противном

случае указывают  способ улучшения текущего плана  Т-задачи.

Описание  алгоритма метода потенциалов. Алгоритм складывается из

предварительного  этапа и конечного числа однотипных итераций.

На предварительном  этапе строят начальный опорный план и

составляют  матрицу C1=∣∣cij−v j

0 −ui

 0∣∣, i=11m, j=11n ,

где v j

0 ,ui

0 — предварительные потенциалы пунктов

Ai i=11m и B j  j=11n .