Требуется составить план перевозок однородного груза из m пунктов отправления А

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

3.1. Формулировка задачи.

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

Общая формулировка транспортной задачи состоит в следующем:

требуется составить план перевозок однородного груза из m пунктов отправления А₁, А₂, ..., А_m, в каждом из которых имеется а₁, ..., а_m единиц груза в n пунктов назначения В₁, В₂, ..., В_n с заявками b₁, b₂, ..., b_n единиц груза, чтобы удовлетворить всех потребителей и минимизировать суммарную стоимость перевозок. Стоимость C_ij перевозки единицы груза из A_i в B_j известна. При этом предполагается, что общий запас груза в пунктах отправления равен суммарной потребности (сумме всех заявок) пунктов потребления, т.е.

. (3.1.)

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


Пункты отправления Пункты назначения

Рис. 1



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


3.2. Математическая модель

Пусть x_ij - количество груза, отправляемое из пункта отправления А_i в пункт B_j.

Тогда целевая функция

- это суммарная стоимость

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

Очевидно, что система неизвестных переменных x_ij должна удовлетворять условиям:

, i=1, , m, (3.2.)

, j=1, , n, (3.3.)

x_ij³0, для всех i и j.

Таким образом, имеем типичную задачу линейного программирования с mn переменными и m+n ограничениями в виде равенств.

Если выполняется условие (3.1), то такая модель называется сбалансированной транспортной моделью. В сбалансированной модели не все m+n уравнений сформированной задачи являются линейно независимыми. Действительно, суммируя все уравнения (3.2.) и все уравнения (3.3.), в силу условия (3.1.) мы получаем одно и тоже. Таким образом, одно уравнение из m+n оказывается зависимыми, т.е. сбалансированная транспортная модель содержит m+n-1 независимых уравнений. Следовательно, как и в симплекс-методе, базисное допустимое решение должно иметь m+n-1 базисную переменную. Количество небазисных переменных равно m×n-(m+n-1)=(m-1)×(n-1).

Пример составления математической модели транспортной задачи.

На трех базах A_i (i=1,3) сосредоточено а=||15, 25, 5|| единиц груза, которые необходимо доставить на 4 пункта приема В_j (j=1,4) в количестве b=||5, 15, 15, 10||. Стоимость перевозок C_ij одной единицы груза с i-ой базы на j пункт приема заданы матрицей:

.

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

Решение:

Обозначим через x_ij (i=1,3; j=1,4) - количество единиц груза перевозимых с i-го пункта отправления в j пункт назначения.

Тогда необходимо найти такие x_ij, чтобы минимизировать целевую функцию вида

L=10x₁₁+20x₁₃+11x₁₄+12x₂₁+7x₂₂+9x₂₃+20x₂₄+14x₃₂+16x₃₃+18x₃₄,


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

x₁₁+x₁₂+x₁₃+x₁₄=15;

x₂₁+x₂₂+x₂₃+x₂₄=25;

x₃₁+x₃₂+x₃₃+x₃₄= 5;

x₁₁+x₂₁+x₃₁= 5;

x₁₂+x₂₂+x₃₂=15;

x₁₃+x₂₃+x₃₃=15;

x₁₄+x₂₄+x₃₄=10.

x_ij³0 для всех i и j

Как видно, основным отличием транспортной задачи от общей задачи линейного программирования является то, что во всех ограничениях неизвестные x_ij входят с коэффициентом, равным единице, и все ограничения имеют вид равенств.


3.3. Решение транспортной задачи

Решение транспортной задачи осуществляется пошагово с помощью специальной транспортной таблицы (табл. 1).


Таблица 1

ПН ПО	В1	В2	...	Bn	ai
A1	c11	c12	...	c1n	a1
A2	c21	c22	...	c2n	a2
...	...	...	...	...	a...
Am	cm1	cm2	...	cmn	am
bj	b1	b2	...	bn

Шаг 1.

Поиск оптимального плана перевозки, как и в общей задаче ЛП начинается с нахождения начального базисного решения (начальной вершины выпуклого многогранника области допустимых значений). Для этого используют процедуру, основную на так называемом правиле северо-западного угла. Построение начального решения согласно этому правилу начинается с левого верхнего угла транспортной таблицы. Распределение груза с первого пункта отправления происходит таким образом, что сначала максимально удовлетворяются заявки первого потребителя, затем второго и т.д. до полного распределения груза, имеющегося в А₁. Затем подобным же образом распределится груз из второго пункта отправления, третьего и т.д. При выполнении ограничения на объем груза на пунктах отправки или спроса на пунктах назначения соответствующая строка (столбец) транспортной таблицы исключается из дальнейшего заполнения. Если ограничения, представляемые столбцом или строкой, выполняются одновременно, то можно исключить из дальнейшего заполнения либо столбец либо строку, а в клетке, соответствующей следующему северо-западному углу поставить значение переменной, равной нулю (см. например, табл. 2). Это правило автоматически гарантирует обнаружение нулевых базисных переменных, если таковые встречаются.

Пример нахождения начального базисного решения

Применим описанную процедуру к транспортной таблице 2.

Таблица 2

	В1	В2	...	Bn	ai
A1	4 5	2 5	1	4	10
A2	3	1 5	2 0	4	5
А3	2	5	3 8	4 7	15
bj	5	10	8	7

1. х₁₁=5, столбец 1 исключается из рассмотрения. Тем самым в первом столбце нельзя больше производить никаких операций.

2. В новом северо-западном угле берем х₁₂=5 и строку 1 исключаем из рассмотрения.

3. Новый северо-западный угол х₂₂=5. Столбец и строка 2 одновременно приводят к выполнению соответствующих ограничений. Если исключается из рассмотрения столбец 2, то на следующем шаге в северо-западном угле переменная х₂₃ становится базисной с нулевым значением, поскольку величина предложения груза из второго пункта назначения уже исчерпана. Можно было бы исключить из рассмотрения строку 2, тогда переменная х₃₂ становится нулевой базисной переменной.

4. х₃₃=8, столбец 3 исключается из рассмотрения.

5. х₃₄=7, исключается из рассмотрения или столбец 4 или строка 3.

Процесс нахождения начального базисного решения заканчивается, когда остается не исключенной из рассмотрения в точности одна строка или один столбец. Занятые клетки транспортной таблицы, в том числе и с нулями, называются базисными, а пустые - небазисными. Начальное решение в таблице 2 содержит необходимое количество базисных переменных, равное m+n-1=3+4-1=6, остальные (m-1)(n-1)=2×3=6 небазисных переменных, соответствующие пустым клеткам транспортной таблицы, равны нулю. Использование правила северо-западного угла всегда приводит к нужному числу базисных переменных.

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

Шаг 2.

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

В методе потенциалов строке i и столбцу j транспортной таблице ставятся в соответствие числа u_i и v_j. Для каждой базисной переменной x_ij текущего решения потенциалы u_i и v_j должны удовлетворять уравнению

u_i+v_j=с_ij. (3.4.)

Эти уравнения приводят к системе, состоящей из m+n-1 уравнений (поскольку всего имеется m+n-1 базисных переменных), в которых фигурирует m+n неизвестных. Значения потенциалов легко определить из этой системы, придавая одному из них произвольные значение (обычно u₁ полагается равным нулю) и затем решая систему из m+n-1 уравнений относительно m+n-1 остальных потенциалов. Действительно, поскольку каждое последующее уравнение системы, имеющие только две переменные, содержит одну из переменных, входящую в предыдущее уравнение, а в первом уравнении переменная u₁=0, то все остальные переменные находятся путем подстановки.

Пример нахождения потенциалов

Применительно к транспортной таблице 2 имеем:

u₁+v₁=4;

u₁+v₂=2;

u₂+v₂=1;

u₂+v₃=2’;

u₃+v₃=3;

u₃+v₄=4.

Полагая u₁=0, получим значение потенциалов v₁=4, v₂=2, u₂=-1, v₃=3, u₃=0, v₄=4.

Уравнения u_i+v_j=с_ij имеют настолько простую структуру, что их не нужно и записывать в явном виде. Потенциалы определяются непосредственно из транспортной таблицы.

Для включения в базис выбирается та базисная переменная, для которой величина

z_ij=c_ij-(u_i+v_j) (3.5.)

является отрицательной и самой большой по модулю.

Теорема (критерий оптимальности).

Необходимое и достаточное условие оптимальности плана перевозок заключается в неотрицательности всех z_ij=c_ij-(u_i+v_j).

Если опорный план является оптимальным, то вычисления на этом заканчиваются; в противном случае переходит к шагу 3.

Шаг 3.

Из числа переменных текущего базиса выбирается та, которую необходимо вывести из базиса. Затем находится новое базисное решение и производится возврат к шагу 2. Поскольку число вершин области допустимых значений ограничено, то за конечное число шагов получим оптимальное значение транспортной задачи. Шаг 3 эквивалентен использованию условия допустимости в симплекс-методе. Вместе с тем, поскольку все коэффициенты в ограничениях транспортной задачи равны либо нулю, либо единице, отношения, используемые при проверке условия допустимости, всегда будет иметь знаменатель, равный единицы. Поэтому значения базисных переменных сразу же дают соответствующие отношения.

Для определения минимального отношения построим замкнутый цикл, соответствующий вводимой переменной. Цикл состоит только из горизонтальных и вертикальных отрезков, одной из вершин которого является выбранная вводимая небазисная переменная, а остальными вершинами - базисные переменные (занятые клетки). Табл.3 иллюстрирует цикл, соответствующий вводимой переменной х₃₁ для начального базисного решения полученного методом северо-западного угла. Этот цикл можно выразить при помощи переменных следующим образом: х₃₁®х₁₁®х₁₂®х₂₂®х₂₄®₃₁.

Таблица 3

	В1	В2	В3	B4	ai	ui
A1	10 5 (-)	0 10 (+)	20	11	15	0
A2	12	7 5 (-)	9 15	20 5 (+)	25	7
А3	0 (+)	14	16	18 5 (-)	5	5
bj	5	15	15	10	45
vj	10	0	2	13

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

Чтобы план перевозок оказался допустимым, необходимо увеличить перевозки в вершинах цикла, отмеченных знаком (+), и уменьшить в отмеченных знаком (-). Чтобы новый план был базисным, в водимую переменную необходимо загрузить по возможности максимально. Величина груза q, удовлетворяющая этому требованию, определяется минимальным значением перевозок, стоящих в отрицательных вершинах цикла.

В рассматриваемом в табл.3 примере

q=min{5, 5, 5}=5.

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

Новые базисные решения представлено в табл.4.

Таблица 4

	В1	В2	В3	B4	ai	ui
A1	10 0 (-)	0 15 (+)	20	11	15	0
A2	12 (+)	7 (-) 0	9 15	20 10	25	7
А3	0 5	14	16	18	5	-10
bj	5	15	15	10	45
vj	10	0	2	13

Поскольку в рассматриваемом примере три переменные х₁₁, х₂₂ и х₃₂, находящиеся в отрицательных вершинах имеют одно и то же минимальное значение, равное пяти, то в этом случае любую из них можно исключить из базиса. В таблице 4 исключено из базиса переменных х₃₄.

Базисное решение в табл.4 вырожденное, поскольку имеются нулевые базисные переменные х₁₁ и х₂₂. Однако выроженность не требует дополнительных мер предосторожности; с нулевыми базисными переменными оперируют точно так же, как и с переменными, имеющими положительные значения.

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

Оптимальность нового базисного решения (табл.4) проверятся вычислением новых потенциалов.

Наибольшая по модулю отрицательная величина z_ij соответствует небазисная переменная х₂₁. Замкнутый цикл для х₂₁ показывает, что переменной, исключаемой из базиса может быть как х11 так и х22. Выберем в качестве такой переменной х11. В табл.5 представлено новое базисное решение. Значение потенциалов вновь вычисляются заново.

Таблица 5

	В1	В2	В3	B4	ai	ui
A1	10	0 15 (-)	20	11 (+)	15	0
A2	12 0	7 0 (+)	9 15	20 10 (-)	25	7
А3	0 5	14	16	18	5	-5
bj	5	15	15	10	45
vj	5	0	2	13

В таблице 5 переменной, вводимой в базис, и исключаемой переменной, являются х₁₄ и х₂₄, соответственно. Новое решение представлено в таблице 6.

Таблица 6

	В1	В2	В3	B4	ai	ui
A1	10	0 5	20	11 10	15	0
A2	12 0	7 10	9 15	20	25	7
А3	0 5	14	16	18	5	-5
bj	5	15	15	10	45
vj	5	0	2	11

Поскольку все z_ij в таблице 6 неотрицательны, то полученное решение оптимально. Максимальные суммарные транспортные расходы составляют

min L=5×0+10×11+10×7+15×9+5×0=315.


3.4. Метод наименьшей стоимости

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

Проиллюстрируем метод на примере транспортной задачи из табл 3.

В таблице 7 начальное решение получено методом наименьшей стоимости

Таблица 7

	В1	В2	В3	B4	ai	ui
A1	10 0	0 5	20	11	15	0
A2	12	7 0	9 15	20 10	25	7
А3	0 5	14	16	18	5	-10
bj	5	15	15	10	45
vj	10	0	2	13

Данная таблица равна таблице 4, полученной при использовании метода северо-западного угла только на втором шаге,. Далее решение продолжается по рассмотренному выше алгоритму. Очевидно, что при методе наименьшей стоимости оптимальное решение будет найдено за меньшее число шагов.


3.5. Другие разновидности транспортных моделей

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


ТЕСТЫ

(верно (В) или неверно (Н)?)

1. В методе решения транспортной задачи, по существу, используя шаги симплекс-метода.
   
2. Если ко всем коэффициентом c_ij прибавить дно и тоже число, то оптимальные значения x_ij изменятся.
   
3. Сбалансированная транспортная задача может не иметь допустимых решений.
   
4. Транспортную задачу всегда можно сбалансировать.
   
5. Для сбалансирования одной и той же транспортной задачи могут понадобитьcя как фиктивные пункты отправления, так и фиктивные пункты назначения.
   
6. Если в симплекс-методе и методе решения транспортной задачи используется одно и тоже начальное базисное решение, то итерации в обоих случаях, по существу, совпадают.
   
7. Для каждой свободной клетки транспортной таблицы может существовать несколько циклов, одна вершина которого лежит в данной свободной клетке, а остальные - в базисных клетках.
   
8. Коэффициенты при неизвестных в уравнениях транспортной задачи равны единице.
   
9. Метод северо-западного угла и метод наименьшей стоимости используются только на первом шаге решения транспортной задачи.
   
10. Метод наименьшей стоимости в общем случае позволяет решить транспортную задачу за меньшее число шагов, чем метод северо-западного угла.
    
11. Метод потенциалов позволяет облегчить процедуру нахождения вводимой в базис переменной.
    
12. Количество базисных переменных в транспортной задаче равно (m-1)(n-1).
    
13. Количество небазисных переменных в транспортной задачи равно m+n-1.
    
14. Проверка количества базисных переменных в начальном решении особенно важно при использовании метода наименьшей стоимости.
    
15. Стоимости перевозок из фиктивных пунктов отправления или в фиктивные пункты назначения принимаются равными единице.
    

Ответы

1-В;

2-Н;

3-Н;

4-В;

5-Н;

6-В;

7-Н;

8-В;

9-В;

10-В;

11-В;

12-Н;

13-Н;

14-В;

15-Н

ЗАДАЧИ

Решить транспортную задачу