Решение транспортной задачи методом потенциалов

С помощью рассмотренных методов построения первоначального плана можно получить вырожденный или невырожденный опорный план. Построенный опорный план ТЗ как ЗЛП можно было бы довести до оптимального с помощью симплекс-метода. Однако из-за громоздкости симплексных таблиц, содержащих mn переменных, и большого объема вычислительных работ для получения оптимального плана используют более простые методы, самый распространенный из которых метод потенциалов (модифицированный распределительный метод).

Пусть имеется ТЗ с балансовыми условиями

; , причем .

Стоимость перевозки единицы груза из A_i в B_j равна c_ij; таблица стоимостей (c_ij) задана. Требуется найти план перевозок (x_ij), который удовлетворял бы балансовым условиям, и при этом стоимость всех перевозок была минимальна:

L = ® min.

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

Обозначим U_i + V_j = (i=1, ...,m; j=1, ...,n) и будем называть «псевдостоимостью» перевозки единицы груза из A_i в B_j. U_i, и V_j не обязательно должны быть положительными. Обозначим совокупность платежей U₁, ..., U_m, V₁, ..., V_n через (U_i, V_j).

Предположим, что план (x_ij) невырожденный, т.е. число базисных клеток в таблице перевозок равно m + n - 1. Для всех этих клеток x_ij > 0. Определим платежи

(U_i, V_j) так, чтобы во всех базисных клетках псевдостоимости были равны стоимостям:

=U_i + V_j = c_ij при x_ij > 0;

Что касается свободных клеток, то для них соотношение между псевдостоимостями и стоимостями может быть каким угодно:
= c_ij или > c_ij или < c_ij.

Теорема. Если план ТЗ является оптимальным, то можно отыскать систему из m+n чисел и , для которой будут выполняться равенства:

(1) + =c_ij для >0, где с_ij – элементы матрицы транспортных затрат, соответствующие занятым данным решением клеткам;

(2) + £c_ij для =0, где с_ij – элементы матрицы, соответствующие незанятым оптимальным решением клеткам.

Числа и называются потенциалами соответственно поставщиков и потребителей.

Доказательство.

ТЗ минимизации линейной функции L = при ограничениях

можно рассматривать как двойственную некоторой исходной ЗЛП, условия которой получают по общей схеме, рассмотренной выше, если каждому ограничению вида (*) в исходной задаче соответствует переменная U_i (i=1,2,…,m), а каждому ограничению вида (**) – переменная V_j (j=1,2,…,n), а именно максимизировать линейную функцию Z= при ограничениях + £c_ij (i=1,2,…,m, j=1,2,…,n). План Х* - оптимальный план двойственной задачи, поэтому план Y*=( , ) является планом исходной задачи и на основании второй теоремы двойственности L_max=Z_min

или

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

+ =c_ij для x^* _ij>0;

+ £c_ij для x^* _ij=0_.

¨

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

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

а) для каждой занятой клетки сумма потенциалов должна быть равна стоимости единицы перевозки, стоящей в этой клетке:

(1) + =c_ij при x_ij>0;

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

(2) + £c_ij при x_ij=0_.

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

Рассмотрим алгоритм решения ТЗ методом потенциалов и проиллюстрируем его применение на примере:

Пример. Решить ТЗ, исходные данные которой заданы в таблице 1.

Табл. 1

ПН ПО	B1	B2	B3	B4	Запасы ai
A1
A2
A3
Заявки bj					1000¹1100

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

Находим суммарные запасы поставщиков и суммарные запасы потребителей:

Задача с неправильным балансом. Вводим 4-го, фиктивного поставщика с запасами а₄=1100-1000=100 и нулевыми стоимостями перевозок единиц груза (см. табл. 2).

2. Построение первоначального опорного плана (методом минимальной стоимости или другим методом), проверка правильности его построения по количеству занятых клеток (их должно быть m+n-1). Убедиться в линейной зависимости векторов условий (используя метод вычеркивания).

Находим первоначальный опорный план методом минимальной стоимости (см. табл. 2). Полученное решение Х₁ имеет 4+4-1=7 базисных переменных.

Табл. 2

ПН ПО	B1	B2	B3	B4	Запасы ai
A1	-	-	-
A2			-	-
A3	-
Aф	-	-	-
Заявки bj					1100=1100

Вычисляем значение целевой функции на этом опорном плане:

Z(X)=1*200+2*200+3*100+7*100+9*300+12*100+0*100=5300.

3. Построение системы потенциалов. Группа равенств (1) используется как система уравнений для нахождения потенциалов. Данная система уравнений имеет m+n неизвестных U_i, I=1,2,…,m и V_j, j=1,2,…,n. Число уравнений системы и число отличных от нуля компонент невырожденного опорного плана равно m+n-1, т.е. m+n-1 занятых клеток. Уравнений на одно меньше, чем неизвестных, поэтому система является неопределенной и одному неизвестному (обычно U₁) придают нулевое значение. После этого остальные потенциалы определяются однозначно из системы.

В случае вырожденного опорного плана, т.е. когда занятых клеток меньше m+n-1, то остаются неопределенные потенциалы. Для устранения вырожденности дополняют количество занятых клеток до m+n-1, вводя нулевые перевозки. Клетки, в которые введены нулевые перевозки, называются фиктивно занятыми. Причем, т.к. задача решается на минимизацию линейной функции, целесообразно сделать фиктивно занятой ту клетку, в которой стоит наименьшая стоимость.

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

Проверяем правильность построения системы. Для этого просматриваем занятые клетки строк и для каждой из них определяем сумму потенциалов. Если для всех занятых клеток выполняется (1), то система построена правильно, в противном слу-чае ее надо построить заново или изменить так, чтобы условие (1) выполнялось.

В нашем примере записываем систему уравнений для нахождения потенциалов и решаем ее:

U₁+V₄=1,

U₂+V₁=2,

U₂+V₂=3,

U₃+V₂=7,

U₃+V₃=9,

U₃+V₄=12,

U₄+V₄=0.

Пусть U₃=0, тогда V₂=7- U₃=7,

V₃=9- U₃=9, V₄=12- U₃=12,

U₁=1-V₄=-11, U₄=0-V₄=-12,

U₂=3-V₂=-4, V₁=2- U₂=6.

Табл. 3

	V1=6	V2=7	V3=9	V4=12
U1=-11
U2­=-4		- 3	5	+ 6 2
U3=0	0	+ 7 100		- 12
U4=-12

4. Проверка выполнения условия оптимальности для свободных клеток с помощью группы неравенств (2) + £c_ij при x_ij=0_. Для чего просматриваем строки и для каждой незанятой клетки проверяем выполнение условия (2), т.е. суммируем потенциалы, на пересечениях которых стоит незанятая клетка, сумму сравниваем со стоимостью, стоящей в ней.

Условие оптимальности: если для всех незанятых клеток U_i+V_j£c_ij, то план оптимальный, если для некоторых клеток U_i+V_j>c_ij, то план неоптимальный, необходимо перейти к новому опорному плану, на котором значение целевой функции будет меньше.

Для каждой свободной клетки, в которой не выполняется условие оптимальности, находим величину разности D_ij=(U_i+V_j)-С_ij>0 и записываем ее значение в левый нижний угол этой же клетки. Числа D_ij называются оценками для свободных клеток таблицы (векторов условий) ТЗ.

Тогда условие оптимальности можно перефразировать: опорный план является оптимальным, если для всех клеток таблицы (векторов условий) оценки неположительные D_ij£0.

Для нашего примера найдены положительные оценки D₂₃=0, D₂₄=2, D₃₁=0. Начальной опорное решение не является оптимальным, т.к. имеется положительная оценка D₂₄=2. См. табл. 3.

5. Выбор клетки, в которую необходимо послать перевозку.

ТЗ решается на минимум линейной функции, поэтому алгоритм ее решения также следует общим принципам алгоритма симплекс-метода решения задач на минимум.

Если отождествлять занятые клетки с векторами, составляющими базис, а свободные – с остальными векторами системы ограничений, то в ОЗЛП в базис включается тот вектор, которому соответствует максимальная оценка целевой функции. В ТЗ загрузке подлежит в первую очередь клетка, например (l,k), которой соответствует наибольшая положительная оценка D_lk= {D_ij}= [(U_i+V_j)-С_ij].

Выбираем клетку, в которую пошлем перевозку {D₂₄=2}=D₂₄.

6. Построение цикла и определение величины перераспределения груза.

Для определения количества единиц груза, подлежащих перераспределению, отмечаем знаком «+» свободную клетку, которую надо загрузить. Это означает, что клетка присоединяется к занятым клеткам. В таблице занятых клеток стало m+n, поэтому появляется цикл, все вершины которого, за исключением клетки, отмеченной знаком «+», находятся в занятых клеток, причем этот цикл единственный. Стрелками будем показывать направление обхода цикла. Отыскиваем цикл и, начиная движение от клетки, помеченной знаком «+», поочередно проставляем знаки «-» и «+».

Затем находим q₀= {x_ij} , где x_ij – перевозки, стоящие в вершинах цикла, отмеченных знаком «-». Величина q₀ определяет, сколько единиц груза можно перераспределить по найденному циклу. Значение q₀ записываем в свободную клетку со знаком «+». Двигаясь по циклу, вычитаем q₀ из объемов перевозок в клетках со знаком «-», и прибавляем к объемам перевозок в клетках со знаком «+». Если q₀ соответствуют несколько минимальных перевозок, то при вычитании оставляем в соответствующих клетках нулевые перевозки в таком количестве, чтобы во вновь полученном опорном плане занятых клеток было m+n-1.

Отмечаем «+» клетку (2,4) и для нее строим цикл, присоединяя ее к занятым клеткам. Применяя метод вычеркивания, находим цикл (2,4), (3,4), (3,2), (2,2).

Начиная с клетки (2,4) с «+», поочередно в вершинах расставляем знаки. Определим величину q₀ , перераспределяемую по циклу, она равна значению наименьшей из перевозок в клетках со знаком «-»:q₀=100.

6. В результате перераспределения q₀ получен новый опорный невырожденный план, который снова подлежит проверке на оптимальность. Для проверки на оптимальность нового плана вновь строим систему потенциалов и проверяем выполнение условия оптимальности для каждой незанятой клетки.

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

В нашем примере полученный план оказался неоптимальным, следует выполнить вычисления, приведенные в п. 5.

Приложения транспортной задачи к решению некоторых экономических задач

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

1. Увеличение производительности автомобильного транспорта за счет минимизации порожнего пробега.

2. Оптимальное закрепление за станками операций по обработке деталей.

3. Оптимальные назначения или проблема выбора.

4.Задачи размещения с учетом транспортных и производственных затрат.

Контрольные вопросы

1. Транспортная задача: постановка и ее математическая модель.

2. Открытые и закрытые модели транспортных задач.

3. Необходимое и достаточное условие разрешимости транспортных задач.

4. Построение первоначального опорного плана транспортных задач методом северо-западного угла.

5. Построение первоначального опорного плана транспортных задач методом минимальной стоимости.

6. Решение транспортных задач методом потенциалов. Критерий оптимальности решения транспортных задач.

Понятие цикла.

Рекомендованная литература: [ 3, 5, 6, 7, 8, 11]