В настоящее время транспортная задача линейного программирования широко применяется как в теоретических разработках, так и в практике планирования различных экономических процессов. Особо важное значение она имеет при решении вопросов рационализации поставок важнейших видов промышленной и сельскохозяйственной продукции, а также оптимального планирования грузопотоков и работы различных видов транспорта.
Постановка задачи и ее математическая модель. Некоторый однородный продукт, сосредоточенный
y m поставщиков Αi в количестве ai (i=1, 2, …, m) единиц
соответственно, необходимо доставить n потребителям Βj в количестве bj (ј=1, 2, …, n)
единиц. Известна стоимость Cij перевозки единицы груза от i-го поставщика к ј-му потребителю.
Необходимо составить план
перевозок, позволяющий вывезти все грузы, полностью
удовлетворить потребности и имеющий минимальную стоимость.
Обозначим через xij
количество единиц груза, запланированных к перевозке
от i-го поставщика к ј-му потребителю; тогда условие задачи можно
записать в виде таблицы (табл. 3.1), которую в
дальнейшем будем называть матрицей планирования.
Составим математическую
модель задачи . Так как от i-го поставщика к
ј-му потребителю запланировано к перевозке xij
единиц груза,
Таблица 3.1
|
Поставщики |
Потребители |
Запасы |
|||
|
В1 |
В2 |
… |
Вn |
||
|
А1 |
С11 х11 |
С12 х12 |
… |
С1n х1n |
α1 |
|
А2 |
С21 х21 |
С22 х22 |
… |
С2n х2n |
α2 |
|
: . |
… |
… |
. . |
… |
: . |
|
Аm |
Сm1 хm1 |
Сm2 хm2 |
… |
Сmn хmn |
αm |
|
Потреб-ности |
B1 |
b2 |
|
bn |
Σαi = Σbj |
то стоимость перевозки
составит Сijxij. Стоимость всего плана выразится двойной суммой:
.
Систему ограничений получаем
из следующих условий задачи:
а) все грузы должны быть
вывезены, т.е.
= αi , (i = 1
, 2 , …, m)
(эти уравнения получаются из
строк табл.3.1);
б) все потребности должны
быть удовлетворены, т.е.
= bj, (ј =1, 2,…, n)
(уравнения получаются из столбцов табл.3.1).
Таким
образом, математическая модель транспортной задачи имеет
следующий вид.
Найти наименьшее значение линейной функции
(3.1.1)
при ограничениях
![]()
= αi , (i = 1
, 2 , …, m), (3.1.2)
= bj, (ј =1, 2,…, n),
(3.1.3)
xij
0 (i = 1 , 2 , …, m; ј
= 1 , 2, …, n).
В рассмотренной модели
предполагается, что суммарные запасы равны суммарным потребностям, т.е.
=
. (3.1.4)
Такая модель называется закрытой.
Теорема 3.1. Любая
транспортная задача, у которой суммарный обьем
запасов совпадает с суммарным обьемом потребностей , имеет решение.
Для доказательства теоремы
необходимо показать, что при заданных условиях существует хотя бы один план
задачи и линейная функция на множестве планов ограничена.
Доказательство. Пусть
=
= M >
0. Тогда величины xij = αi
bj/M (i = 1,
2, …, m; j = 1,
2, …, n) является планом, так как они
удовлетворяют системе ограничений (3.1.2), (3.1.3).
Действительно, подставляя значения хij в (3.1.2), и (3.1.3) имеем
=
= ![]()
=
M =
,
=
= ![]()
=
M =
.
Выберем из значений Сij наибольшее С′ = maх Сij и заменим в линейной функций (3.1.1) все коэффициенты на С′ ; тогда, учитывая (3.1.2), получаем
С′
= С′
= С′М.
Выберем из значений Сij наименьшее С" = min Сij и заменим в
линейной функции все коэффициенты на С"; тогда, учитывая (3.1.2), имеем
С"
= С"
= С"М.
Обьединяя
два последних неравенства в одно двойное, окончательно получаем
С"М
Z
С′ М,
т.е. линейная функция ограничена на множестве
планов транспортной задачи.
Сформулируем частную
транспортную задачу для двух пунктов отправления и трех пунктов назначения.
Задача 1. На двух базах отправления А1
и А2 сосредоточено соответственно а1 и а2 единиц
некоторого однородного груза. Этот груз следует доставить в три пункта назначения
В1, В2 , В3, причем в каждый из них
должно быть завезено соответственно b1, b2, b3 единиц этого
груза. Стоимость перевозки единицы груза из пункта Аi в пункт Bj (равную сij) считаем заданной (табл.3.2)
Таблица 3.2
|
Поставщики |
Потребители |
Запасы |
||
|
В1 |
В2 |
В3 |
||
|
А1 |
С11 Х11 |
С12 Х12 |
С13 Х13 |
a1 |
|
А2 |
C21 X21 |
C22 X22 |
С23 Х23 |
a2 |
|
Потребность в грузе |
b1 |
b2 |
b3 |
∑ai= ∑bj |
Считаем, что общий запас грузов на станциях отправления равен сум-марной
потребности в этом грузе всех пунктов назначения: a1 + a2 = b1 + b2 + b3. Требуется
составить такой план перевозок, при котором их общая стоимость была бы
наименьшей.
Через xij обозначим
количество единиц груза, предназначенного к отправке из пункта Аi в пункт Вj. Тогда количество груза, который планируется к доставке в пункт В1 из пунктов А1 и А2, составит х11 + х21. Но так как потребность в грузе в
пункте В1 равна b1, то должно выполняться
равенство
х11 + х21 = b1. Аналогичные рассуждения приводят
к равенствам: х12 + х22 = b2; х13 + х23 = b3.
С другой стороны, общее количество груза, отправленного со станции А1, а1 = х11 + х12 + х13, а со станции А2, в пункты
назначения В1, В2, В3, а2 = х21 + х22 + +х23.
Общая стоимость всех перевозок
f = c11x11 + c12x12 + c13x13 + c21x21 + c22x22 + c23x23 =
=
.
Итак, математически задача
для двух пунктов отправления и трех пунктов назначения формулируется таким
образом.
Дана система
x11 + x21 = b1,
x12 + x22 = b2,
x13 + x23 = b3,
х11 + х12 + х13 = a1,
x21 + x22 + x23 = a2,
пяти линейных алгебраических
уравнений с шестью неизвестными и линейная форма
f =
.
Требуется среди всех неотрицательных решений xij системы
выбрать такое, при котором линейная форма f принимает минимальное значение.
Построение
первоначального опорного плана. Как и для других
задач линейного программирования, итерационный. процесс по отысканию
оптимального плана транспортной задачи начинают с нахождения опорного плана .
Рассмотрим
систему ограничений (3.1.2) и (3.1.3) транспортной задачи. Она
содержит mn неизвестных и m+n уравнений, связанных
соотношением (3.1.4). Если сложить почленно уравнения отдельно
подсистемы (3.1.2) и отдельно подсистемы (3.1.3), то получим
два одинаковых уравнения. В табл. 3.1 такое сложение равнозначно
соответственно почленному сложению столбцов и почленному сложению строк.
Наличие в системе
ограничений двух одинаковых уравнений говорит об ее линейной зависимости. Если
одно из этих уравнений отбросить, то в общем случае система ограничений должна содержать m+n-1
линейно независимых уравнений, следовательно, невырожденный опорный план
транспортной задачи содержит m+n-1 положительных компонент или перевозок.
Таким образом, если
каким-либо способом получен невырожденный опорный план транспортной задачи, то в матрице (xij)
(i =1, 2,…, m; ј=1, 2,…, n) значений его компонент
(табл. 3.1.) положительными являются только m+n-1, а
остальные равны нулю.
Если условия транспортной задачи и ее опорный
план записаны в виде таблицы (табл.3.1), то клетки, в которых
находятся отличные от нуля перевозки, называются занятыми, остальные –незанятыми.
Занятые клетки соответствуют базисным неизвестным, и для невырожденного
опорного плана их количество равно m+n-1. Если ограничения транспортной задачи
записаны в виде (3.1.2) и (3.1.3), то, как известно,
базисным неизвестным, включенным в опорный план, соответствует система линейно
независимых векторов. Опорность плана при записи условий транспортной задачи в
виде таблицы (табл. 3.1) заключается в его ацикличности, т.е. в таблице
нельзя построить замкнутый цикл, все вершины которого лежат в занятых клетках.
Циклом называется набор клеток вида (i1ј1) (i1 ј2)
× (ј2i2 )…(ј1im ), в котором две и только две соседние клетки расположены в одном
столбце или одной строке таблицы, причем последняя клетка находится в той же
строке или столбце, что и первая. Построение циклов начинают с какой-либо
занятой клетки и переходят по столбцу (строке) к другой занятой клетке, в
которой делают поворот под прямым углом и движутся по строке (столбцу) к
следующей занятой клетке и т.д., пытаясь возвратиться к первоначальной клетке.
Если такой возврат возможен, то получен цикл и план не является опорным. Клетки,
в которых происходит поворот под прямым углом, определяют вершины цикла. В
противном случае план является опорным.
Всякий план транспортной
задачи, содержащий более m+n-1 занятых клеток, не является опорным, так как ему
соответствует линейно зависимая система векторов. При таком плане в таблице
всегда можно построить замкнутый цикл, с помощью которого уменьшают и число
занятых клеток до m+n-1.
Если к занятым клеткам,
определяющим опорный невырожденный план, следовательно, и ацикличный,
присоединить какую-либо незанятую клетку, то план становится неопорным,
появляется единственный цикл, все вершины которого, за исключением одной, лежат
в занятых клетках.
Первоначальный опорный план
транспортной задачи как задачи линейного программирования можно построить ранее
рассмотренными методами, однако это сопряжено с большими вычислениями.
Существуют несколько простых схем построения первоначального опорного плана
транспортной задачи, которые рассмотрим на примерах .
Метод северо-западного угла. Пусть условия
транспортной задачи заданы табл.3.3.
Не
учитывая стоимости перевозки единицы груза, начинаем удовлетворение
потребностей первого потребителя В1 за счет запаса поставщика А1. .Для этого
сравниваем α1 =100 с b1=200, α1 <
b1, меньший из обьемов, т.е. = 100
ед. записываем в левый нижний угол клетки А1В1. Запасы первого поставщика
полностью израсходованы, по этому остальные клетки
первой строки прочеркиваем. Потребности В остались
неудовлетворенными на 200-100=100 ед. Сравниваем этот
остаток с запасами поставщика А2: так как 100<250, то
100 ед. записываем в клетку А2В1,
чем полностью удовлетворяем потребности потребителя В1, а
оставшиеся клетки в первом столбце прочеркиваем.
У поставщика А2 осталось
150 ед. груза. Удовлетворяем
потребителя В2 за счет оставшегося у поставщика
А2 груза. Для
этого сравниваем этот остаток с потребностями потребителя В2 :
150<200, записываем 150 ед. в клетку А2В2 и,
так как запасы А2 полностью израсходованы, прочеркиваем
остальные клетки второй строки. Потребности В2 остались
неудовлетворенными на 50 ед.
Таблица 3.3
|
Постав- Щики. |
Потребители |
Запасы |
||||
|
В1 |
В2 |
В3 |
В4 |
В 5 |
||
|
А1 |
10 100 |
7 _ |
4 _ |
1 _ |
4 _ |
100 |
|
А2 |
2 100 |
7 150 |
10 _ |
6 _ |
11 _ |
250 |
|
А3 |
8 _ |
5 50 |
3 100 |
2 50 |
2 _ |
200 |
|
А4 |
11 _ |
8 _ |
12 _ |
16 50 |
13 250 |
300 |
|
Потреб-ности |
200 |
200 |
100 |
100 |
250 |
850 |
Удовлетворяем их за счет
поставщика А3 и переходим к удовлетворению
В3 за счет остатка, имеющегося
у поставщика А3 , и т. д. Процесс
продолжаем до тех пор, пока не удовлетворим всех потребителей за счет запасов
поставщиков. На этом построение первоначального опорного плана заканчивается.
Таким
образом, в табл. 3.3 в правых верхних углах клеток стоят числа,
определяющие стоимость перевозки единицы грузов, а в левых нижних углах –числа,
определяющие план перевозок, так как их сумма по строкам равна запасам
соответствующего поставщика, а сумма по столбцам –потребности соответствующего
потребителя.
Проверим,
является ли план, построенный в табл.3.3, опорным. Видим, что,
начиная движение от занятой клетки А1В1, вернуться не только в
нее, но и в любую другую занятую клетку, двигаясь только по занятым клеткам,
невозможно. Следовательно, план является опорным. В то же время план
невырожденный, так как содержит точно m+n-1=4+5-1=8 занятых клеток .
При
составлении первоначального опорного плана методом северо- западного угла
стоимость перевозки единицы груза не учитывалась, по этому построенный план далек от оптимального, получение
которого связано с большим обьемом вычислительных работ. Поэтому рассмотренный
метод используется при вычислениях с помощью ЭВМ.
Найдем общую стоимость составленного
плана как сумму произведений обьемов перевозок, стоящих в левом углу занятых
клеток, на соответствующие стоимости в этих же клетках:
Z = 100*10 + 100*2 + 150*7 +
50*5 + 100*3 + 50*2 + 50*16 + 250*13 = 6950(ед. стоимости).
Если при составлении
опорного плана учитывать стоимость перевозки единицы груза, то, очевидно, план
будет значительно ближе к оптимальному .
Метод минимальной стоимости. Суть
метода заключается в
том, что из
всей таблицы стоимостей
выбирают наименьшую и
в клетку, которая ей соответствует, помещают меньшее из чисел αi
или bj. Затем из рассмотрения исключают либо строку, соответствующую
поставщику, запасы которого полностью израсходованы, либо
столбец, соответствующий
потребителю, потребности
которого полностью удовлетворены, либо
и строку и
столбец, если израсходованы
запасы поставщика и
удовлетворены потребности потребителя.
Из оставшейся части
таблицы стоимостей снова
выбирают наименьшую стоимость,
и процесс распределения запасов
продолжают, пока все
запасы не будут
распределены, а потребности
удовлетворены.
Составим с
помощью этого метода
опорный план уже
рассмотренной задачи. Запишем
её условие в
таблицу (табл. 3.4). Выбираем
в таблице наименьшую
стоимость (это стоимость, помещенная в
клетке А1В4), так
как α1=b4, 100 ед. груза помещаем
в этой клетке
и исключаем из
рассмотрения первую строку
и четвёртый столбец.
В оставшейся таблице стоимостей
наименьшей является стоимость,
расположенная в клетке
А2В1 и в клетке
А3В5. Заполняем
любую из них,
например А2В1. Имеем 200<250,
следовательно, записываем в неё
200 исключаем из рассмотрения
столбец В1. В
клетку А3В5 записываем 200 ед. и исключаем
из рассмотрения строку
А3. В оставшейся
таблице стоимостей
снова выбираем наименьшую стоимость
и продолжаем процесс
до тех пор, пока
все запасы не будут
распределены, а потребности удовлетворены. В результате получен
план
X= (х14=100; х21=200; х22=50; х35=200; х42=150; х43=100 х45 =50),
остальные значения
переменных равны нулю.
Таблица 3.4
|
Постав- Щики. |
Потребители |
Запасы |
||||
|
В1 |
В2 |
В3 |
В4 |
В 5 |
||
|
А1 |
10 _ |
7 _ |
4 _ |
1 100 |
4 _ |
100 |
|
А2 |
2 200 |
7 50 |
10 _ |
6 _ |
11 _ |
250 |
|
А3 |
8 _ |
5 _ |
3 _ |
2 _ |
2 200 |
200 |
|
А4 |
11 _ |
8 150 |
12 100 |
16 _ |
13 50 |
300 |
|
Потреб-ности |
200 |
200 |
100 |
100 |
250 |
850 |
План не содержит циклов и
состоит из семи положительных перевозок, следовательно, является вырожденным
опорным планом. Определим его стоимость:
Z = 100*1 + 200*2 + 50*7 + 200*2 + 150*8 +
100*12 + 50*13 = 4300 (ед).
Метод
двойного предпочтения. Если таблица стоимостей велика,
то перебор всех элементов затруднителен. В этом случае используют метод
двойного предпочтения, суть которого заключается в следующем.
В каждом столбце отмечают
знаком V клетку
с наименьшей стоимостью. Затем то же проделывают в каждой строке. В результате
некоторые клетки имеют отметку VV. В них находится минимальная стоимость как по
столбцу, так и по строке. В эти клетки помещают максимально возможные объемы
перевозок, каждый раз исключая из рассмотрения соответствующие столбцы или
строки. Затем распределяют перевозки по клеткам, отмеченным
знаком V. В оставшейся
части таблицы перевозки распределяют по наименьшей стоимости.
Применим метод двойного
препочтения к задаче, условия которой записаны в табл. 3.5.
Таблица 3.5
|
Постав- Щики. |
Потребители |
Запасы |
||||
|
В1 |
В2 |
В3 |
В4 |
В 5 |
||
|
А1 |
10 _ |
7 _ |
4 _ |
VV 1 100 |
4 _ |
100 |
|
А2 |
VV 2 200 |
7 _ |
10 50 |
6 _ |
11 _ |
250 |
|
А3 |
8 _ |
V 5 _ |
V 3 _ |
V 2 _ |
VV 2 200 |
200 |
|
А4 |
11 _ |
8 200 |
12 50 |
16 _ |
13 50 |
300 |
|
Потреб-ности |
200 |
200 |
100 |
100 |
250 |
850 |
Сначала заполняем клетки A2В1, A1В4, A3В5, а затем клетку A4В2. В оставшейся части таблицы последовательно заполняем клетки по минимальной стоимости A2В3, A4В3, A4В5. План, полученный в табл.3.5, является вырожденным опорным планом. Найдем его стоимость:
Z = 100*1 + 200*2
+ 50*10
+ 200*2 + 200*8 + 50*12 + 50*13 = 4250 (ед).
Таким образом, наименьшую
стоимость имеет опорный план, полученный методом двойного предпочтения,
следовательно, он наиболее близок к оптимальному плану.
С помощью рассмотренных
методов построения первоначального плана можно получить вырожденный или
невырожденный опорный план. Построенный опорный план транспортной задачи как
задачи линейного программирования можно было бы довести до оптимального с
помощью симплексного метода. Однако из-за громоздкости
симплексных таблиц, содержащих mn неизвестных, и большего обьема
вычислительных работ для получения оптимального плана используют более простые
методы, самый распространенный из которых метод потенциалов (модифицированный
распределительный метод).
Метод потенциалов.
Теорема 3.2. Если план Х* = (x*ij) транспортной задачи является
оптимальным, то ему соответствует
система из m +n чисел U*i и
V*j, удовлетворяющих
условиям
U*i + V*j = Сij
для x*ij > 0
и
U*i + V*j
Сij для x*ij
= 0
(
i= 1, 2, …, m; j = 1, 2, …, n).
Числа U*i и
V*j называются потенциалами
соответственно поставщиков и потребителей.
На основании теоремы 2.6.2 получаем, что ограничения исходной задачи,
соответствующие положительным компонентам оптимального плана двойственной
задачи, удовлетворяются как строгие равенства, а соответствующие компонентам,
равным нулю, - как неравенства, т.е.
U*i + V*j = Cij
для x*ij
0,
U*i + V*j
Cij для x*ij = 0.
На основании доказанной теоремы для того чтобы
первоначальный опорный план был оптимальным, необходимо выполнение следующих
условий:
а
) для каждой занятой клетки сумма потенциалов должна быть равна стоимости
единицы перевозки, стоящей в этой клетке :
Ui
+ Vj = Сij ;
(3.1.5)
б
) для каждой незанятой клетки сумма потенциалов должна быть меньше или равна
стоимости единицы перевозки, стоящей в этой клетке:
Ui
+ Vj
Сij .
(3.1.6)
Таблица 3.6
Матрица
Планирования. |
Потребители |
Запасы |
|||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
|||
|
Щики |
υј uί |
V
υ1=3 |
V υ2=8 |
V Υ3 =12 |
V υ4=13 |
V Υ5=13 |
|
|
А1 |
V U1=-12 |
10 |
7 |
4 |
1 100 |
4 |
100 |
|
А2 |
V u2 =–1 |
2 200
|
-7 50 |
10
1 |
+6 6 |
11 1 |
250 |
|
А3 |
V u3=–11 |
8 |
5 |
3 |
-2 0 |
+2 200 |
200 |
|
А4 |
V
u4=0 |
11 |
8 + 150 |
12 100 |
16 |
–
13 50 |
300 |
|
Потребности |
200 |
200 |
100 |
100 |
250 |
850 |
|
Если хотя бы одна
незанятая клетка не удовлетворяет условию (3.1.6), то опорный план является
неоптимальным и его можно улучшить, вводя в базис вектор, соответствующий
клетке, для которой нарушается условие оптимальности (т.е. в клетку надо
переместить некоторое количество единиц груза ).
Таким образом, для проверки плана на
оптимальность необходимо сначала построить систему потенциалов. Рассмотрим
алгоритм метода потенциалов и одновременно проиллюстрируем
его применение на опорном плане, полученном
в табл.3.4. Для этого к таблице добавим строку и столбец, в которых записывают
значения потенциалов (в результате получим табл.3.6).
1. Построение
системы потенциалов. Для построения системы потенциалов используем
условие
Ui
+ Vj = Сij,
где Сij
–стоимость перевозки единицы груза занятой клетки в i-строке и ј-м столбце.
Систему потенциалов
можно построить только для невырожденного опорного плана. Такой план содержит
m+n-1 занятых клеток, поэтому для него можно составить систему из m+n-1 линейно независимых уравнеий вида (3.5)
с n+m неизвестными. Уравнений на одно меньше, чем неизвестных, поэтому система
является неопределенной и одному неизвестному (обычно U1) придают
нулевое значение. После этого остальные потенциалы определяются однозначно.
Пусть
известен потенциал Ui; тогда из равенства (3.5) следует Vj=
Сij– Ui.
Если известен потенциал
Vj, то из того же равенства имеем: Ui = Сij –
Vj.Таким образом, для
определения неизвестного потенциала от
величины Сij занятой клетки следует вычесть известный потенциал.
В табл.3.6 опорный план
вырожденный, так как не хватает одной занятой клетки. Поэтому выбираем строку,
которая содержит наибольшее количество занятых клеток (строка А4 ),
и полагаем U4 =0. В строке А4 три занятых клетки (А4
В2, А4В3
и А4В5),
которые связывают соответственно потенциал U4 с потенциалами V2,
V3, V5. Определим
эти потенциалы : V2 =С42 – U4 = 8 – 0 =8,
V3 = С43 – U4 =12 – 0 =12, V5 =
С45 – U4=13 – 0 = 13. С помощью потенциала U4 определить
еще какой-нибудь неизвестный потенциал невозможно, поэтому отмечаем его знаком
V. Теперь поочередно просматриваем столбцы В2, В3 и В5,
для которых потенциалы уже определены. В столбце В2 имеются две занятые клетки
(А2 В2 и А4 В2 ), которые
связывают потенциал V2 с потенциалами U2 и U4;
потенциал U4 уже определен. Переходим к клетке А2В2 и
с помощью С22 определим неизвестный потенциал : U2 = С22
– V2= 7-8=
-1. Отмечаем потенциал V2 знаком
V и переходим к столбцу В3. В этом столбце нет занятых
клеток, которые бы связывали V3 с неизвестными потенциалами строк.
Отмечаем потенциал V3 знаком
V и переходим к столбцу В5. В нем одна занятая клетка (А3В5),
которая связывает V5 с неизвестным потенциалом U3 .
Определим его: U3 = С32 - V5 =2 -13= - 11.
Отмечаем потенциал V3 знаком V и, так как неизвестные потенциалы
столбцов использованы, переходим к известным потенциалам строк, которые еще не
отмечены знаком V, затем, просматриваем соответствующие им строки.
Потенциал U2 занятой
клеткой А2В1 связан с неизвестным потенциалом V1. Находим этот потенциал : V1 =2
– (–1)=3 и отмечаем потенциал U2 знаком V.
В строке A3 нет занятых клеток, которые
связывали бы потенциал U3 с неизвестным потенциалом столбца; потенциал U3 отмечаем V.
Переходим к известным
потенциалам столбцов, которые не отмечены знаком V (это потенциал V1 ).
Но в столбце В1 нет занятых клеток, которые связывали бы V1
с неизвестным потенциалом строки, поэтому потенциал V1 отмечаем
знаком V. Построение cистемы потенциалов прервалось, потенциалы U1 и
V4 остались неопределенными. Это произошло потому, что опорный план
выражденный (отсутствует одна занятая клетка). Для устранения вырожденности дополняют количество занятых клеток до m+n–1, вводя нулевые
перевозки. Клетки, в которые введены нулевые перевозки, называются фиктивно
занятыми.
Чтобы определить потенциалы
U1 и V4, необходимо сделать фиктивно занятой
одну из незанятых клеток либо строки А1, либо столбца В4,
для которых один из потенциалов определен. Задача решается на минимизацию
линейной функции, поэтому целесообразно сделать фиктивно занятой клетку, в
которой стоит наименьшая стоимость.
Просматривая стоимости,
стоящие в незанятых клетках строки А1 и столбца В4,
выбираем наименьшую (mίnСij = 2), которая соответствует клетке А3В4, в нее записываем
нуль и считаем занятой. Теперь клетка А3В4 связывает
потенциал V4 с потенциалом U3; V4 = С34 -
U3 =2 - (- 11) = 13. Затем находим
U1 = С14 - V4 =1-
13= - 12.
Система потенциалов
построена, знаки V, которыми отмечались потенциалы, следует стереть. Проверяем
правильность построения системы. Для этого просматриваем занятые клетки строк и
для каждой из них определяем сумму потенциалов. Если для всех занятых клеток
выполняется равенство (3.5), то система построена правильно, в противном случае
ее надо построить заново или изменить так, чтобы условие (3.5) выполнялось.
2. Проверка выполнения условия оптимальности для незанятых клеток. Просматриваем
строки и для каждой незанятой клетки проверяем выполнеия условия (3.6), т.е.
суммируем потенциалы, на пересечениях которых стоит незанятая клетка, сумму
сравниваем со стоимостью, стоящей в ней. Если для всех незанятых клеток Ui
+ Vј
Сij, то
(см. теорему 3.2) план оптимальный. Если для некоторых клеток Ui + Vј
> Сij, то план является неоптимальным.Тогда для каждой клетки, в которой не выполняется условие
оптимальности, находим величину разности (Ui + Vј )– Сij > 0 и записываем ее значение в левый нижний угол этой же клетки.
В табл. 3.6 для
незанятых клеток последовательно получаем: для строки А1 : -9 <
10, -4 < 7, 0 < 4, -8 < 4; для
строки А2: для клетки А2В3 имеем 11 >10 или
11 - 10 = 1; условие оптимальности нарушено, разность равную единице,
записываем в эту клетку; для клетки А2В4 имеем
12 > 6, 12 – 6 = 6, условие также нарушено, разность равную шести,
записываем в эту клетку; для клетки А2В5 имеем 12 >11,
12 -11=1, разность, равную единице,
записываем в клетку;
для
строки А3 : -8 < 8, -3 < 5, 1 < 3;
для строки А4 : 3 < 11, 13 < 16.
Таким образом, имеются
три клетки, в которых нарушено условие оптимальности; разности соответственно
равны 1, 6 и 1.
3. Выбор
клетки, в которую необходимо послать перевозку.
Транспортная задача
линейного программирования решается на минимум линейной функции, поэтому
алгоритм ее решения также следует общим принципам алгоритма симплексного метода
решения задач на минимум.
Если отождествлять занятые клетки с
векторами, составляющими базис, а незанятые – с остальными векторами системы
ограничений, то в общей задаче линейного программирования в базис включается
тот вектор, которому соответствует max
0(Zј -Сј ). В транспортной задаче значение Zј
заменено суммой потенциалов (Ui + Vј ), поэтому загрузке подлежит в
первую очередь клетка, которой соответствует max[(Ui + Vј )–
Сij].
Таким образом, в
рассматриваемом примере max(1; 6; 1) = 6, клетку А2В4 необходимо сделать занятой. Для этого сначала необходимо
определить, сколько единиц груза должно быть перераспределено в нее.
4. Построение цикла и определение величины перераспределения груза. Для определения количества единиц груза, подлежащих перераспределению,
отмечаем знаком «+» незанятую клетку, которую надо загрузить. Это означает, что
клетка присоединяется к занятым клеткам. В таблице занятых клеток стало m+n,
поэтому появляется цикл, все вершины которого, за исключением клетки,
отмеченной знаком «+», находятся в занятых клетках, причем этот цикл
единственный. Отыскиваем цикл и, начиная движение от клетки, отмеченной знаком
«+», поочередно проставляем знаки «–», и
«+». Затем находим
0=mίn
xij, где xij – перевозки, стоящие в вершинах цикла,
отмеченных знаком «–».
Величина
0 определяет,
сколько единиц груза можно перераспределить по найденному циклу. Значение
0 записываем
в незанятую клетку, отмеченную знаком «+», двигаясь по циклу, вычитаем
0 из обьемов перевозок, расположенных в клетках,
которые отмечены знаком «–», и прибавляем к обьемам перевозок, находящихся в
клетках, отмеченных знаком «+». Если
0 соответствуют несколько минимальных перевозок,
то при вычитании оставляем в соответствующих клетках нулевые перевозки в таком
количестве, чтобы во вновь полученном опорном плане занятых клеток было m+n-1.
В рассматриваемом
примере клетку А2В4 отмечаем знаком «+» и находим цикл,
приведенный в табл. 3.6. Имеем
0 = mίn (50; 50; 0) = 0, т.е. нулевую
перевозку необходимо переместить в клетку А2В4, остальные
числа при вычитании и прибавлении нуля , очевидно, не
изменяется.
5. В результате перераспределения
0 получен
новый опорный невырожденный план (табл.3.7), который снова подлежит проверке на
оптимальность. Для проверки на оптимальность нового опорного плана можно
вновь построить систему потенциалов и проверить выполнение условия
оптимальности для каждой незанятой клетки.
Если полученный план
снова окажется неоптимальным, то следует выполнить вычисления, приведенные в
п.4. Процесс повторяют до тех пор, пока все незанятые клетки не будут
удовлетворять условию (3.6). Все вычисления оптимального плана рекомендуется
выполнять в одной таблице, поэтому значения xij, Ui, Vј, а также знаки V, «+» «–», следует
записывать карандашом и затем стирать.
Построение новой системы
потенциалов и проверка всех незанятых клеток на оптимальность требуют
значительных затрат времени, поэтому рассмотрим порядок изменения системы
потенциалов, позволяющий значительно сократить обьем вычислительных работ.
6.Изменение системы потенциалов. В
новом опорном плане, записанном в табл.3.7, пока указаны старые потенциалы.
Клетка А2В4 прежде свободная, теперь стала занятой. Для
занятой клетки должно выполняться условие Ui +Vј = = Сij.
В действительности же U2 + V4 = -1 + 13 = 12 ≠ 6.
Следовательно, необходимо либо U2 , либо V4 уменьшить на шесть. Очевидно, что
уменьшать следует тот потенциал, уменьшение которого приводит к наименьшему
изменению остальных потенциалов.Так если изменить V4, а потенциал U2
оставить без изменения, то изменению подлежит только потенциал U1;
в противном случае изменяются все остальные потенциалы.
Отмечаем потенциал U2 знаком «!», потенциал V4 – знаком
«–». Изменение потенциала V4, так как клетка A1В4 занята,
потребует изменения потенциала U1 (отмечаем его знаком «+»); на этом цепочке изменений обрывается.
Таким образом, значения
потенциалов, отмеченных знаком «–», уменьшаются, а знаком «+» - увеличиваются
(в данном случае на 6ед.). В результате для всех занятых клеток выполняется
соотношение (3.5). Значение
потенциала V4 уменьшилось
на 6ед., поэтому свободные клетки в столбце В4, не удовлетворяющие
условию оптимальности, появиться не могут. Если же такие клетки были, то они
могут исчезнуть, так как разность, равная шести,
Таблица 3.7
|
Потребители |
Запасы |
|||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
|||
|
щики |
Vј Ui |
3 |
8 |
12 |
- 13 7 |
13 |
|
|
А1 |
+ 12 -6 |
10 |
7 |
4 2 |
-
1 100 |
+ 4 3 |
100 |
|
А2 |
-
1! |
2 200 |
-
7 50 |
10 1 |
+
6 0 |
11 1 |
250 |
|
А3 |
–11 |
8 |
5 |
3 |
2 |
2 200 |
200 |
|
А4 |
0 |
11 |
+
8 150 |
12 100 |
16 |
13 50 - |
300 |
|
Потребности |
200 |
200 |
100 |
100 |
250 |
850 |
|
максимальна для всех
клеток, в которых нарушено это условие. Свободные клетки, не удовлетворяющие
условию оптимальности, могут появиться только в строке (столбце), потенциал
которой увеличился. Потенциал U1 увеличился на 6 ед. поэтому
незанятые клетки строки A1 следует проверить на оптимальность :-3
< 10; 2 < 7; 6 >4; 7 > 4. Клетки A1В3 и A1В5
не удовлетворяют этому условию; находим для них величины разностей ui + vј – cij
и записываем их в левый нижний угол соответствующих клеток.
Определяем max (2; 3; 1;
1) =3. Клетка A1В5 подлежит загрузке, отмечаем ее знаком
«+» и устанавливаем цикл перераспределения, показанный в табл. 3.7 пунктирной
линией. Отмечаем вершины цикла попеременно знаками «–» и «+» и находим
0 = mίn (50; 50; 100) = 50. По циклу
перераспределяем 50 ед. груза в клетку A1В5 и получаем опорный план, приведенный в
табл. 3.8.
Так как значение
0 = 50
достигается для двух клеток цикла, отмеченных знаком «–», то в полученном
опорном плане в клетке A2В2 оставлена нулевая перевозка.
Заметим, что план в результате
последней итерации улучшился на 150 ед. стоимости. Это улучшение находится как
произведение количества единиц груза, перемещенного в свободную клетку, на
величину разности в этой клетке. Величина разности (Ui + Vj)
– Сij > 0 в незанятой клетке показывает, на сколько
уменьшится стоимость плана перевозок, если единицу груза перераспределить в эту
клетку.
В полученном опорном
плане изменяем систему потенциалов и проверяем его на оптимальность. Условию
оптимальности не удовлетворяют две клетки с разностями, равными двум и единице,
следовательно, груз надо перераспределить в клетку A1В3 . Отмечаем, ее
знаком «+» и строим цикл перераспределения, который показан в табл.3.8
пунктирной линией. Циклы могут иметь различную конфигурацию, быть даже
самопересекающимися (табл. 3.8).
Таблица 3.8
|
Потребители |
Запасы |
|||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
|||
|
щики |
Vј Ui |
3 |
8 |
12 |
7 |
- 13 10 |
|
|
А1 |
- 6! |
10 |
7 |
+
4 2 |
-
1 50 |
4 50 |
100 |
|
А2 |
- 1 |
2 200 |
-
7 0 |
10 1 |
6 50 + |
11 |
250 |
|
А3 |
+ –11 -8 |
8 |
5 |
3 |
2 |
2 200 |
200 |
|
А4 |
0 |
11 |
+ 8 200 |
12 100 - |
16 |
13 |
300 |
|
Потребности |
200 |
200 |
100 |
100 |
250 |
850 |
|
Отмечаем вершины цикла
знаками «–» или «+» и находим величину перераспределения:
0 = mίn(50; 0;100) = 0. Нулевую перевозку
перемещаем в клетку A1В3 , получаем новый опорный план и вносим изменения в систему
потенциалов. Построенная система потенциалов позволяет сделать вывод, что план,
приведенный в табл.3.9, является оптимальным. Его стоимость равна 4150 ед.
стоимости.
Таблица 3.9
Матрица
Планирования. |
Потребители |
Запасы |
|||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
|||
|
щики |
Vј Ui |
3 |
6
8 |
-
10 12 |
7 |
10 |
|
|
А1 |
- 6! |
10 |
7 |
4 |
1 50 |
4 50 |
100 |
|
А2 |
-1
|
2 200 |
7 |
10 |
6 50 |
11 |
250 |
|
А3 |
–8 |
8 |
5 |
3 |
2 |
2 200 |
200 |
|
А4 |
+ 2 0 |
11 |
8 200 |
12 100 |
16 |
13 |
800 |
|
Потребности |
200 |
200 |
100 |
100 |
250 |
850 |
|
3.4. Открытая модель транспортной задачи.
Транспортная задача, в
которой суммарные запасы и потребности совпадают, т.е. выполняется условие
=
, называется закрытой моделью; в
противном случае – открытой. Для открытой
модели
может быть два случая:
а) суммарные запасы превышают суммарные
потребности
>
;
б ) суммарные потребности превышают
суммарные запасы
<
.
Линейная
функция одинакова в обоих случаях, изменяется только вид
системы ограничений.
Найти минимальное
значение линейной функции ![]()
при ограничениях
αi , (i = 1
, 2 , …, m), (случай а )
= bj, (ј =1, 2,…, n);
= αi , (i = 1
, 2 , …, m), (случай
б )
bj, (ј =1, 2,…, n),
xij
0 (i = 1
, 2 , …, m; ј = 1 ,
2, …, n).
Открытая модель решается
приведением к закрытой модели .
В случае (а), когда
суммарные запасы превышают суммарные потребности, вводится фиктивный
потребитель Вn+1, потребности которого
bn+1 =
-
.
В случае (б), когда
суммарные потребности превышают суммарные запасы, вводится фиктивный
поставщик Аm+1, запасы
которого
αm+1 =
-
.
Стоимость перевозки
единицы груза как до фиктивного потребителя, так и стоимость перевозки единицы
груза от фиктивного поставщика полагают
равными нулю, так как груз в обоих случаях не перевозится.
После преобразований
задача принимает вид закрытой модели и решается обычным способом. При равных
стоимостях перевозки единицы груза от поставщиков к фиктивному потребителю
затраты на перевозку груза реальным потребителям минимальны, а фиктивному
потребителю будет направлен груз от наименее выгодных поставщиков. То же самое
получаем и в отношении фиктивного поставщика .
Прежде чем решать
какую-нибудь транспортную задачу, необходимо сначала проверить, к какой модели
она принадлежит, и только после этого составить таблицу для ее решения.
Пример 1.
Составить план перевозок грузов с наименьшей общей стоимостью от четырех
поставщиков Ai (i =1, 2,
3, 4) соответственно в количествах 100, 400, 100 и 100ед. к пяти потребителям Bj (j=1,2, 3, 4, 5) соответственно в количествах 50, 100, 150,
200 и 250ед.; стоимости перевозок единицы груза приведены в табл. 3.10.
|
Bj Ai |
B1 |
B2 |
B3 |
B4 |
B5 |
|
A1 A2 A3 A4 |
1 16 4 3 |
6 10 1 2 |
8 8 9 7 |
12 6 11 7 |
16 15 13 15 |
Решение. Вычислим
суммарные запасы и потребности:
= 700;
=750. Потребности превышают запасы на 50 ед. Необходимо
ввести фиктивного поставщика Am+1, объем запасов которого αm+1 = 50 ед. В табл. 3.10 получен оптимальный план. При
составлении первоначального опорного плана методом минимальной стоимости или
двойного предпочтения необходимо наименьшую стоимость выбрать только среди
стоимостей реальных поставщиков и потребителей, а запасы фиктивного поставщика
(потребности фиктивного потребителя) распределять в последнюю очередь. Это
позволит получить план, более близкий к оптимальному. Отмеченное выше используют также при введении фиктивно
занятых клеток.
Таблица
3.11
Матрица
планирования. |
Потребители |
Запасы |
|||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
|||
|
щики |
Vј Ui |
3 |
5 |
10 |
8 |
17 |
|
|
А1 |
-2 |
1 50 |
6 |
8 50 |
12 |
16 |
100 |
|
А2 |
-2 |
16 |
10 |
+ 8 |
6 200 |
- 15 200 |
400 |
|
А3 |
–4 |
4 |
-
1 100 |
9 |
11 |
13
0 + |
100 |
|
А4 |
-3 |
3 |
+ 2 0 |
7 100 - |
7 |
15 |
100 |
|
Аm+1 |
-17 |
0 |
0 |
0 |
0 |
0 50 |
50 |
|
Потребности |
50 |
100 |
150 |
200 |
250 |
750 |
|
Анализируя оптимальный план задачи, можно сделать следующие
выводы. Потребитель B5 получает 50 ед. груза от фиктивного
поставщика, следовательно, его потребности будут не удовлетворены на это же
количество единиц. Оптимальный план не является единственным, так как для
клетки A2B3 сумма
потенциалов равна стоимости перевозки U2 + V3 = C23 и
в нее по циклу, показанному в
табл. 3.11, можно переместить 100 ед. груза.
В результате перераспределения получен новый опорный план,
который также является оптимальным, так как система потенциалов останется без изменения
и общая стоимость плана перевозок
не уменьшается, поскольку (U2 + V3 ) - C23 = 0.
Любая выпуклая линейная комбинация двух оптимальных планов
также является оптимальным планом, поэтому это свойство можно использовать для
улучшения планирования, при этом можно учесть особенности, которые не были
учтены в математической модели задачи (ранее взятые договорные обязательства,
сложившиеся традиции в отношениях и т.д.).