опорными (лежат вне многогранника решений). Первое же допустимое решение (опорный план) будет оптимальным.

Пример. Решить следующую задачу методом последовательного уточнения оценок:

L(x) = −2x1 − x2 → min, x1 − 2x2 +3 ≥ 0,

−3x1 −7x2 + 21≥ 0,

−x1 + x2 + 2 ≥ 0,

−5x1 − 4x2 + 20 ≥ 0,

7.5. Методы решения транспортной задачи

Транспортная задача линейного программирования формулируется следующим образом. Необходимо минимизировать транспортные расходы

m n

Q(X )= ∑∑cij xij → min

i=1 j=1

при ограничениях

91

где cij – стоимость перевозки единицы продукции из пункта i в пункт j; xij –

планируемая величина перевозок из пункта i в пункт j (план перевозок X – матрица размерности m ×n );

bj – потребности в продукте в пункте j;

ai – запасы в пункте i.

n m

Предполагается, что модель закрытого типа, то есть ∑bj = ∑ai .

закрытому типу введением фиктивного пункта производства или фиктивного пункта потребления:

Транспортная задача представляет собой задачу линейного программирования и, естественно, ее можно решить с использованием метода последовательного улучшения плана или метода последовательного уточнения оценок. В этом

случае основная трудность бывает связана с числом переменных задачи (m×n) и числом ограничений (m+n). Поэтому специальные алгоритмы оказываются более эффективными. К таким алгоритмам относятся метод потенциалов и венгер-

ский метод.

Алгоритм метода потенциалов, его называют еще модифицированным распределительным алгоритмом, начинает работу с некоторого опорного плана транспортной задачи (допустимого плана перевозок). Для построения опорного плана обычно используется один из двух методов: метод северо-западного угла

или метод минимального элемента.

92

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

Он позволяет найти некоторый допустимый план перевозок. Составим транспортную таблицу некоторой задачи.

В данном случае имеем задачу закрытого типа, т.к.

При построении плана должны учитывать, что сумма перевозок в столбце должна оказаться равной потребностям в данном пункте, а сумма перевозок в строке запасу в пункте, соответствующем данной строке.

Заполнение начинается с верхнего левого угла таблицы. Величина перевозки устанавливается равной минимальной из величин: величины остатка запасов в пункте i или величины еще неудовлетворенного спроса в пункте j.

Если ресурс в данной строке исчерпан, то переходим к перевозке в следующей строке текущего столбца (на одну строку вниз).

Если потребности для данного пункта (столбца) удовлетворены, то переходим к следующей перевозке текущей строки в следующем столбце.

Затраты на перевозку по построенному плану равны

Q = 30×2 + 4×80 + 2×10 + 6×10 + 6×20 + 4×10 +5×30 + 4×60 =1010.

Естественно, что найденный план далек от оптимального.

7.5.2. Метод минимального элемента

В таблице отыскивается min{cij}и в первую очередь заполняется соответствующая клетка: xij = min{ai ,bj}. Затем вычеркивается остаток соответствующей строки, если ai < bj , или столбца, если ai > bj , и корректируем остатки запа-

сов и неудовлетворенного спроса.

В оставшихся клетках таблицы снова отыскивается минимальная стоимость перевозки и заполняется соответствующая клетка и т.д.

93

Затраты на перевозку по построенному плану равны

Q = 30×2 + 4×80 +8×10 + 2×30 +5×40 + 2×20 +1×30 + 4×10 =830.

Этот план лучше, но утверждать, что он оптимален, нельзя.

Определение 1. Набором называется произвольная совокупность перевозок транспортной таблицы.

Определение 2. Цепью называют такие наборы, когда каждая пара соседних клеток в цепи расположены либо в одном столбце, либо в одной строке.

Определение 3. Циклом называется цепь, крайние элементы которой находятся либо в одной строке, либо в одном столбце.

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

Метод позволяет находить оптимальный план перевозок транспортной таблицы. В основе лежит следующая теорема.

Теорема. Для того, чтобы некоторый план X =[xij ]m×n транспортной зада-

чи был оптимальным, необходимо и достаточно, чтобы ему соответствовала такая система m+n чисел u1,u2,...,um; v1,v2 ,...,vn , для которой выполняются условия

отправления и пунктов назначения. Условия (7.8-7.9) называются условиями потенциальности.

План X будем называть потенциальным, если для него существует система ui и vj , удовлетворяющая (7.8–7.9). Тогда теорема коротко формулируется

следующим образом.

Теорема. Для оптимальности транспортной задачи необходимо и достаточно, чтобы потенциальный план был оптимален.

94

т.е. стоимость перевозок по любому плану X ' не меньше стоимости перевозок по потенциальному плану X .

Следовательно, план X оптимален.

Необходимость. Будем рассматривать транспортную задачу, как задачу линейного программирования с минимизацией линейной формы

m n

Q(X )= ∑∑cij xij → min

i=1 j=1

при соответствующих ограничениях. Заполним симплексную таблицу и рассмотрим двойственную к ней задачу, что легко получить из таблицы. Прямую таблицу будем заполнять, повернув.

Получаем, что двойственная задача имеет вид:

95

при ограничениях

yij = ui −vj + cij ≥ 0 , i =1,m, j =1,n ,

т.е. vj −ui ≤ cij , i =1,m, j =1,n .

Пусть X =[xij ]m×n – оптимальное решение транспортной задачи. Тогда на

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

u1*, ...,um* ; v1*, ...,vn* .

Убедимся, что эти числа являются потенциалами соответствующих пунктов транспортной задачи. Действительно, все ui*,v*j как опорное решение двой-

ственной задачи удовлетворяют неравенствам (7,8).

Если xij > 0, то по второй теореме двойственности соответствующее ограничение

yij* = ui* −v*j + cij ≥ 0

двойственной задачи обращается в строгое равенство

v*j −ui* = cij .

Алгоритм метода потенциалов

Алгоритм метода потенциалов состоит из предварительного этапа и повторяющегося основного этапа.

Предварительный этап.

Каким-либо способом ищется допустимый план X (методом северозападного угла или минимального элемента).

есть план X исследуется на оптимальность). Для этого проверяется vj −ui ≤ cij ,

xij = 0.

Если система непотенциальна, то переходят к основному этапу (т.к. план

что v'j −u'j = cij , xij > 0.

3. Исследуем систему ui' , v'j на потенциальность. Если система непотенциальна, то переходим на п.1. Иначе найден оптимальный план.

96

Число неизвестных больше числа уравнений, поэтому можем взять, например, u1 = 0 и найти значения остальных потенциалов, u2 = −4 , u3 = −2 ,

u4 = −1, v1 = 2, v2 = 4 , v3 = 2 , v4 = 2, v5 = 3.

3. Проверяем систему на потенциальность:

Система непотенциальна.

Переходим к общему этапу.

1. Выбираем клетку, для которой неравенство вида vj −ui ≤ cij нарушается в наибольшей степени, то есть, находится число

αi0 j0 = maxi, j {αij = vj −ui −cij > 0}

среди тех клеток, для которых условие (1) не выполняется: αi0 j0 = α25 = 5.

Начиная с клетки i0 j0 в направлении против часовой стрелки строится цепь из заполненных клеток таблицы (цикл). Совершая обход по цепи, помечаем

97

клетки, начиная с i0 j0 , попеременно знаками + и –. Клетки со знаками + образу-

ют положительную полуцепь, а со знаками – отрицательную полуцепь. В клетках отрицательной полуцепи ищем минимальную перевозку

θ = min{xij−}.

Теперь улучшаем план следующим образом: перевозки отрицательной полуцепи уменьшаем на величину θ, а перевозки положительной полуцепи увеличиваем на θ. Новые

xij− −θ, xij' = xij+ + θ,

xij .

В нашем примере θ = min{xij−}=20.

1.Новому плану соответствует таблица.

vj

Затраты на перевозку по построенному плану равны:

Q= 30×2 + 4×80 + 2×10 + 6×10 + 4×30 + 2×20 +5×10 + 4×60 = 910.

2.Строим систему потенциалов

Полагаем u1 = 0 и находим значения остальных потенциалов:

u2 = −4 , u3 = −7 , u4 = −6 , v1 = 2, v2 = 4 , v3 = 2 , v4 = −3, v5 = −2.

3. Проверяем систему на потенциальность:

Q= 30×2 + 4×80 + 2×10 + 2×10 + 4×30 + 2×30 +5×10 + 4×50 =850 .

2.Строим систему потенциалов

99

v j

Затраты на перевозку по построенному плану равны:

Q= 30×2 + 4×80 + 2×10 + 2×10 +1×30 + 2×30 +5×40 + 4×20 = 790 .

2.Строим систему потенциалов

Полагаем u1 = 0 и находим значения остальных потенциалов:

u2 = 2 , u3 = −1, u4 = 0 , v1 = 2, v2 = 4 , v3 = 2 , v4 =1, v5 = 4 .

3. Проверяем систему на потенциальность:

Система потенциальна, следовательно, план оптимален и окончательные затраты Qmin =790.

Определение 4. Допустимый опорный план транспортной задачи называется невырожденным, если число заполненных клеток транспортной таблицы, т.е. число положительных перевозок xij > 0, равно m + n +1, где m – число пунктов

отправления, n – число пунктов назначения.

Определение 5. Если допустимый опорный план содержит менее m + n +1 элементов xij > 0, то он называется вырожденным, а транспортная задача назы-

вается вырожденной транспортной задачей.

Следующая теорема позволяет определить вырожденность задачи до ее решения.

Теорема. Для невырожденной транспортной задачи необходимо и достаточно отсутствие такой неполной группы пунктов производства, суммарный

100

объем производства которой точно совпадает с суммарными потребностями некоторой группы пунктов потребления.

Другими словами, это условие означает, что для любых двух систем индексов i1,i2 ,...,it , j1, j2 ,..., jS , где t + S < n + m , имеет место неравенство

Для решения транспортной задачи методом потенциалов строится система потенциалов vj −ui = cij , xij > 0. Если опорное решение невырожденно, то чис-

ло неизвестных на 1 больше числа уравнений. При вырожденном опорном решении число этих уравнений еще меньше. По аналогии симплекс-методом, в невырожденном решении xij > 0 представляют собой базисные переменные, а

xij = 0 – небазисные. Если опорное решение вырожденно, то часть базисных пе-

ременных принимает нулевые значения.

Пусть первое опорное решение, найденное методом северо-западного угла или методом минимального элемента, является вырожденным. Тогда, чтобы решать задачу методом потенциалов необходимо выбрать в качестве базисных переменных некоторые перевозки xij = 0 и для них также составить уравнения

vj −ui = cij по условию (2) теоремы. Какие перевозки вида xij = 0 включать в базисные? Выбираются такие клетки таблицы с xij = 0, чтобы из базисных пере-

менных нельзя было организовать ни одного цикла!

При переходе к новому улучшенному плану задачи в небазисные переменные переводится перевозка в отрицательной полуцепи, которая находится сле-

дующим образом θ = min{xij−}. В вырожденной задаче это значение может достигаться на нескольких перевозках xij отрицательной полуцепи. В этом случае

на каждом шаге в небазисные переменные переводится та минимальная перевозка отрицательной полуцепи, которая связана с пунктом производства, имеющим меньший номер. Это правило уменьшает вероятность возникновения зацикливания, что само по себе достаточно редкое явление в практических задачах.

101