Метод потенциалов решения ТЗ

Транспортная задача линейного программирования

Основные определения и понятия.

 

• Постановка транспортной задачи (ТЗ)

Однородный груз находится у т поставщиков в объемах а₁, а₂. ..., а_m. Груз

необходимо доставить n потребителям в объемах b₁ , b₂ , ..., bn. Общий объ-

ем поставок равен общему объему заявок. Заданы стоимости с_ij, i = 1,2,…, m,

j =1,2,…, п доставки единицы груза от каждого поставщика i каждому

потребителю j. Требуется рассчитать такой план перевозок, при котором

запасы всех поставщиков вывозятся полностью, заявки всех потребителей

полностью удовлетворяются и суммарные транспортные издержки мини­-

мальны.

• Математическая модельТЗ

(3.1)     (3.2)     (3.3)     (3.4)   (3.5)

Переменными (неизвестными) ТЗ являются х_ij- объемы перевозок от каж-

дого i-го поставщи­ка каждому j-му потребителю. Целевая функция (3.1)

выражает требование минимизации транспортных издержек на перевозку

всех грузов. Ограничения (3.2) отражают тот факт, что запасы всех m постав-

щиков вывозятся полностью. Ограничения (3.3) выражает требование пол-

ностью удовлетворить заявки всех п потребителей. Ограничения (3.4) назы-

вается уравнением баланса и отражает равенство общего объема поставок

общему объему заявок.

• Математическая формулировка ТЗ: найти такой план перевозок х_ij, удов-

летворяющий ограничениям (3.2)–(3.5) и обеспечивающий минимум целевой

функции (3.1).

• ТЗ всегда имеет решение, т.к. целевая функция (3.1) ограничена снизу

нулем ввиду неотрицательности её слагаемых.

• Исходные данные ТЗ записываются в таблице (называемой транспортной

таблицей) вида

 

bj   ai	b1	b2	…	bn
a1	c11	c12	…	c1n
a2	c21	c22	…	c2n
…	…	…	…	…
am	cm1	cm2	…	cmn

 

В дальнейшем все действия по нахождению решения ТЗ будут сво­диться к

преобразованию транспортной таблицы

• Доказано, что система ограничений (3.2)-(3.5) ТЗ имеет ранг N=m + n – 1,

поэтому решение ТЗ не может иметь отличных от нуля координат больше,

чем N. Значит, в каждом решении, включая оптимальное, будут отличны от

нуля не более, чем (n + т — 1) пере­возок х_ij . Ячейки (клетки) таблицы, в ко-

торых записываются эти отличные от нуля перевозки, называются базисны-

ми, а остальные (пустые) - свободными.

• Решение ТЗ называется невырожденным, если число ненулевых координат

вектора решения X равно N=m + n – 1.

• Уравнение баланса (3.4) является обязательным условием решения ТЗ. Когда

уравнение баланса нарушено, то в ТЗ необходимо искусственно восстано-

вить баланс следующим способом:

- в ТЗ с избытком заявок вводится фиктивный поставщик с запасом а_ф,

равным недостающему объему поставок;

- в ТЗ с избытком запасов вводится фиктивный потребитель с заявкой b_ф,

равной превышающему объему поставок.

Транспортная таблица дополняется в первом случае фиктивной строкой а_ф ,

во втором – фиктивным столбцом b_ф. В клетках таблицы, связывающих

фиктив­ные пункты с реальными, стоимости перевозки с_ij = 0.

• Метод «северо-западного угла» построения опорного решения ТЗ: заполне-

ние транспортной таблицы начинается с левой верхней клетки («северо-за-

падного угла») и состоит из однотипных операций. Запасы первого постав-

щика используются для обеспечения сначала первого потребителя, затем

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

используются запасы следующего поставщика и т.д. до полного распределе-

ния запасов между потребителями.

• После построения начального опорного решения необходимо проверить,

чтобы число занятых клеток равнялось N=m + n – 1, т.е. решение было

невырожденным.

Метод потенциалов решения ТЗ

• Векторы U=( u₁, u₂. ..., u_m ) и V=( v₁, v₂. ..., v_n ) называются потенциалами

поставщиков и потребителей соответственно, если их координаты удов-

летворяют соотношениям

u_i + v_j = c_ij, для х_ij > 0 , i = 1,2,…, m, j =1,2,…, п.

• Теорема.

Если для всех базисных клеток решения (x_ij > 0)

u_i + v_j = c_ij,

а для всех свободных клеток (x_ij =0)

u_i + v_j £ c_ij,,

то решение x_ij является оптимальным и никакими способами улучшено быть

не может.

• Если среди свободных клеток найдется хотя бы одна, в которой величина

D_ij = u_i + v_j - c_ij > 0 при x_ij =0,

то решение может быть улучшено. Про­цесс улучшения решения состоит в

определении вводимой и выво­димой клеток транспортной таблицы. В таб-

лицу вводится клетка, для которой D_ij максимальна. Выводимая клетка

определяется с помощью цикла.

• Правило построения цикла:

В соответствии со свой­ствами ТЗ для невырожденного базисного решения в

таблице можно образовать замкнутую цепоч­ку, состоящую только их верти-

кальных и горизонтальных звень­ев, одной из вершин которой является вы-

бранная свободная клетка, а остальные — занятые клетки. Логика построе-

ния цикла проста: «выйдя» из свободной, вводимой в базис, клетки в гори-

зонтальном направлении, мы дол­жны «остановиться» в той занятой клетке

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

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

занятой клетке, чтобы, повернув в ней в горизонтальном направлении, мы

смогли перейти к следующей занятой клетке и далее аналогично выстраива-

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

замкнутый цикл.

• Переход от одного опорного решения ТЗ к другомупроизводится с по-

мощью цикла. В построенном цикле, начиная с вводимой клетки (кото­рая

считается первой), помечаются вершины: нечетные — знаком «+», а четные

знаком «—». Среди множества клеток, помеченных знаком «—», выбирает-

ся клетка с наименьшим значением x_ij (обозначим его Q). Затем производит-

­ ся пересчет плана по цепочке: к объемам перевозок в клетках, помеченных

знаком «+», добавляется объем Q, а из клеток, помеченных знаком «—»,

этот объем вычитается. В ре­зультате в базис решения вводится исходная

клетка цикла с объемом Q и выводится клетка цикла, объем которой был

равен Q. Если новое базисное решение не оптимально, то описанная про-

цедура продолжается до получения оптимального решения.

• Алгоритм решения ТЗ методом потенциалов.

1.Проверить уравнение баланса (3.4). При необходимости выровнять баланс

введением фиктивного поставщика или фиктивного потребителя.

2. Построить начальное опорное решение, например, методом («северо-за-

падного угла» и проверить правильность его составления по количеству

базисных клеток (их должно быть N=m + n – 1, остальные клетки — сво-

бодные).

3. Определить потенциалы U=( u₁, u₂. ..., u_m ) и V=( v₁, v₂. ..., v_n ) по базисным

клеткам. Для этого решают систему уравнений

u_i + v_j = c_ij ,для х_ij > 0 , i = 1,2,…, m, j =1,2,…, п,

которая имеет бесконечное множество решений. Для нахождения частного

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

пример, полагают u₁=0.

4. Проверить выполнение условия оптимальности для всех свободных кле-

ток. Для этого вычисляют

D_ij = u_i + v_j - c_ij > 0 при x_ij =0.

Если все D_ij £ 0, то план оптимален, вычисляют значение целевой функции

и решение задачи заканчивается.

5. Если хотя бы в одной свободной клетке D_ij > 0, приступают к улучшению

решения путем пе­реброски перевозок по циклу.

6. После этого заново подсчитываются потенциалы и D_ij, и, если план все

еще не оптимален, процедура улучшения продол­жается до тех пор, пока

не будет найдено оптимальное решение.

• Если в ТЗ получаетсявырожденное решение,когда число ненулевых

клеток меньше чем (т + п-1), то вырожденность устраняется следующим

методом: вырожденное решение дополняется необходимым коли­чеством

нулевых клеток (базисных нулей) таким образом, чтобы они позволяли

построить цикл и рассчитать полную систему по­тенциалов, и далее

действуют в соответствии с правилами опи­санного выше алгоритма.