21265

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

Лекция

Экономическая теория и математическое моделирование

Транспортная задача Т3возникает при планировании рациональных перевозок грузов загрузки оборудования и других организационноэкономических процессов. Требуется составить такой план перевозок откуда куда и сколько единиц груза везти чтобы все заявки были выполнены а общая стоимость всех перевозок минимальна. Матрицу X будем называть матрицей перевозок или планом грузоперевозок. Суммарное количество груза доставляемого в каждый ПН из всех ПО должно быть равно заявке поданной данным пунктом: 3...

Русский

2015-01-17

474.5 KB

46 чел.

Тема  «Транспортная задача»

1. Общая постановка транспортной задачи.

2. Математическая модель транспортной задачи.

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

3.1. Методы нахождения начального (опорного) решения ТЗ.

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

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

3.2. Методы нахождения оптимального решения ТЗ.

3.2.1. Распределительный метод.

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

1. Общая постановка транспортной задачи

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

Классическая транспортная задача (Т3) формулируется следующим образом:

«Имеются m пунктов отправления (ПО) А1, А2...Аm, в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно a1, a2,…, am единиц.

Имеются n пунктов назначения (ПН) B1, B2 ,...., Bn, подавших заявки соответственно на bi, b2, ..., bn единиц груза.

Известны стоимости (или расстояния) cij перевозки единицы груза из каждого пункта отправления Аi, i = 1,2,..., m, до каждого пункта назначения Bj, j = 1,2, …, n .

Все числа Сij можно представить в виде матрицы стоимостей (или расстояний):

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

Определение 1. Транспортная задача, в которой суммарные запасы  и суммарные потребности  совпадают, называется закрытой моделью, в противном случае – открытой. Открытая модель решается приведением к закрытой.

2. Математическая модель транспортной задачи

Определение 2. Обозначим Xij –  количество единиц груза, отправляемого из i-го ПО  Аi в j-й ПН Bj.

Тогда все Xij можно представить в виде матрицы X:

.

Определение 3. Матрицу X будем называть матрицей перевозок или планом грузоперевозок. Заметим, что все xij  0, i = 1,.. .,m, j = 1,.., n.

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

1. Сумма всех заявок равна сумме всех запасов:

.                                          (1)

2. Суммарное количество груза, направляемого из каждого ПО во все ПН, должно быть равно запасу груза в данном пункте:

                                (2)

3. Суммарное количество груза, доставляемого в каждый ПН из всех ПО, должно быть равно заявке, поданной данным пунктом:

                                   (3)

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

.                                    (4)

Заметим, что уравнения (1 – 3), а также функция L представляют собой уравнение первой степени относительно каждой из переменных; они полностью определяют задачу линейного программирования с целевой функцией L и ограничениями (2) и (3). Требуется найти (m · n) переменных xij, удовлетворяющих указанным условиям и минимизирующих целевую функцию L. Из условия (1) вытекает важное следствие. Из (m + n) уравнений в системе ограничений транспортной задачи одно (любое) уравнение можно отбросить, так как оно вытекает из остальных (m + n – 1) уравнений.

Действительно, если определено, например, наличие груза у всех отправителей и потребности всех получателей, кроме одного, то спрос последнего легко устанавливается как разность между общим запасом и общей потребностью других получателей. Поскольку модель транспортной задачи содержит (m + n – l) независимых уравнений, любой ее невырожденный допустимый план включает (m + n – 1) переменную с положительным значением. Поэтому из (m · n) возможных маршрутов перевозок в оптимальном плане транспортной задачи загружается не более (m + n – 1) маршрутов.

Определение 4. Если план задачи включает меньше чем (m + n – 1) положительных переменных, то он называется вырожденным планом, а если число ненулевых перевозок равно (m + n – 1), то невырожденным.

Определение 5. Базисными клетками транспортной таблицы являются клетки, соответствующие базисным переменным, а остальные клетки – свободные.

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

1. Все коэффициенты при переменных xij в условиях (2) и (3) равны 1 и xij  0; i = 1,2,..., m;  j = 1,2, ..., n.

2. Ограничения (2) и (3) выражаются точными равенствами.

3. Каждая неизвестная величина входит лишь в два уравнения.

4. Условия (2) и (3) не являются линейно независимыми, так как их правые части связаны предположением (4.1).

5. Число линейнонезависимых уравнений в ограничениях (2), (3) равно (m + n – 1).

6. Общее число переменных xij равно m · n.

7. Число базисных переменных (или независимых переменных) равно (m + n – 1).


8. Число свободных переменных равно

.

В случае, когда суммарные запасы превышают суммарные потребности, т.е. , то вводится фиктивный (n + 1)-й потребитель, потребности которого определяются по формуле .

В случае, когда суммарные потребности превышают суммарные запасы, т.е. , то вводится фиктивный (m + 1)-й поставщик, запасы которого определяются по формуле

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

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

Рассмотрим пример, на основе которого покажем, как строится математическая модель транспортной задачи.

Пример 1. В городе имеются четыре домостроительных комбината (ДСК): А1, A2, А3, А4, и строятся четыре микрорайона: B1, B2, B3, B4.

Известны ресурсы каждого ДСК, которые составляют соответственно 14, 20, 26, 41 условных единиц продукции. Известна также потребность в комплектах унифицированных изделий каждого микрорайона, что составляет 20, 22, 15, 34 условных единиц соответственно. Известны затраты, связанные с доставкой одного комплекта унифицированных изделий из каждого ДСК в каждый микрорайон, которые заданы матрицей С:

.

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

Покажем, что данная задача является транспортной задачей, удовлетворяющей граничным условиям (1) и (4). Имеется четыре ПО: А1, A2, А3, А4 – это ДСК (m = 4) и четыре ПН: B1, B2, B3, B4 –  это микрорайоны.

Проверим выполнение условия (4.1), если a1 = 14; a2 = 20; а3 = 26; а4 = 41и b1 = 30; b2 = 22; b3 = 15; b4 = 34:

                            (5)

Запишем ограничения (2) и (3) в виде системы уравнений:

                        (6)

                      (7)

Целевая функция может быть записана в виде

.            (8)

Из уравнений (5) – (8) видно, что данная задача является классической транспортной задачей, а следовательно, обладает всеми восемью свойствами, присущими данному классу задач линейного программирования.

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

После того, как построена математическая модель транспортной задачи, переходим к ее решению, которое можно разбить на несколько этапов:

1) построение транспортной таблицы;

2) определение исходного опорного решения;

3) построение последовательных итераций-приближений к оптимальному решению.

Введем следующие определения.

Определение 6. Будем называть любой план перевозок X = (xij) допустимым, если он удовлетворяет условиям (2), (3), что означает: все заявки удовлетворены, все запасы исчерпаны.

Определение 7. Допустимый план перевозок будем называть опорным, если в нем отличны от нуля не более (m + n – l) перевозок, а остальные равны нулю.

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

  1.  сумма перевозок в каждой строке равна запасу ai в данной строке;
  2.  сумма перевозок в каждом столбце равна спросу bj в данном столбце.

Определение 8. План Х* = (x*ij) будем называть оптимальным, если он среди всех допустимых планов X = (xij) приводит к минимальной стоимости перевозок (L* min).

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

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

Все операции по определению оптимального плана сводятся к манипуляциям непосредственно с таблицей, где в определенном порядке записаны условия транспортной задачи, перечень пунктов отправления, пунктов назначения, заявки bj, j = 1,2,..., h; запасы ai, i = 1,2..., m; стоимость грузоперевозок Cij, i = 1,2,... m; j = 1,2,..., n. Такая таблица называется  транспортной таблицей. Транспортная таблица состоит из m отрок n столбцов. В правом верхнем углу каждой клетки проставляется стоимость Cij перевозки единицы груза из Ai в Bj. Центр клетки остается свободным. Туда впоследствии будет занесена перевозка xij. Ниже представлен общий вид транспортной табл. 1.

Таблица 1

ПН

ПО

B1

B2

Bn

Запас ai

A1

c11

c12

c1n

a1

A2

c21

c22

c2m

a2

Am

cm1

cm2

cmn

am

Заявки

bj

b1

b2

bn

Рассмотрим транспортную табл. 2 (пример 1).

Таблица 2

ПН

ПО

B1

B2

B3

B4

Запас ai

A1

70

38

24

92

14

A2

58

18

56

72

20

A3

19

10

100

30

26

A4

3

36

12

8

41

Заявки

bj

30

22

15

34

101

3.1. Методы нахождения начального (опорного) решения ТЗ

Решение транспортной задачи сводится к преобразованиям транспортной таблицы.

Определение исходного опорного решения X0 транспортной задачи состоит в заполнении транспортной таблицы тем или другим способом. Рассмотрим два метода определения исходного опорного решения: метод «северо-западного угла» и метод минимального элемента.

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

Заполнение транспортной таблицы начинаем с левого верхнего угла. В клетку (1,1) заносим наименьшее из чисел a1 и b1, т.е.

.

Если a1 > b1, то х11 = b1. Это означает, что потребности первого потребителя удовлетворены полностью, и, следовательно, первый столбец таблицы заполнен. Двигаемся далее по первой строке, записывая в соседнюю клетку (1,2) меньшее из чисел (а1b1) и b2, т.е.

.

Если a1 < b1, то х11 = а1. Это означает, что запасы первого ПО исчерпаны, и, следовательно, первая  строка заполнена. Двигаемся далее по первому столбцу, записывая в клетку (2,1) наименьшее из чисел (b1a1) и a2, т.е.

.

В случае a1 < b1 можно исключить и поставщика, и потребителя, однако при этом план получается вырожденным, поэтому считается, что выбывает только поставщик, а спрос потребителя остается неудовлетворенным и равным нулю.

Продолжаем этот процесс, пока все заявки не будут выполнены, запасы израсходованы.

Найдем методом «северо-западного угла» опорное решение транспортной задачи из табл. 2. Заполнение таблицы  начнем с левого верхнего угла или клетки (1,1).

Результаты приведены в табл. 3.

Таблица 3

ПН

ПО

B1

B2

B3

B4

Запас ai

A1

70

14

38

24

92

14

A2

58

16

18

4

56

72

20

A3

19

10

18

100

8

30

26

A4

3

36

12

7

8

34

41

Заявки

bj

30

22

15

34

101

Таким образом, опорное решение – план перевозок X0 вида

,

которому отвечает значение целевой функции

.

Т.е. при таком плане перевозок затраты на доставку груза от поставщиков к потребителям составят 3 316 условных единиц.

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

В правиле «северо-западного угла» учитываются величины аi, i = 1, ..., m и bj, j = l, ...n, и не рассматриваются величины затрат Cij, i = 1, ..., m, j = l, ...n. Поэтому исходное опорное решение часто может быть далеко от оптимальным.

Приведем теперь для построения опорного решения (плана) метод минимального элемента, в котором существенно учитывается матрица С = Сij, i = 1, ..., m; j = l, ...n – матрица транспортных издержек. Для этого посмотрим транспортную таблицу, дополненную одной строкой, которую назовем строкой остатков, и столбцом – столбцом остатков (табл. 4).

Таблица 4

ПН

ПО

B1

B2

Bn

Запас ai

Столбец остатков

A1

c11

c12

c1n

a1

A2

c21

c22

c2m

a2

Am

cm1

cm2

cmn

am

Заявки

bj

b1

b2

bn

Строка остатков

Построение исходного опорного решения начинают с клетки, имеющей наименьшую стоимость Cij. В эту клетку (i, j) заносим

.

Остатки по строке и столбцу записываем в соответствующие клетки строки и столбца остатков. Если bj < ai, то остаток соответствующий столбцу j, равен 0 и столбец bj закрыт. Если ai < bj, то остаток в соответствующей строке равен 0 и строка аi закрыта. Далее заполняем последовательно клетки с минимальной по всей таблице стоимостью Cij без учета закрытых уже столбца или строки, а величина соответствующей перевозки xij определяется точно так же, как в методе  «северо-западного угла», т.е. xij равняется минимуму из остатка груза в i-м пункте отправления и недостающего груза в j-м пункте назначения.

В результате применения метода минимального элемента получим план перевозок X = (Xij), состоящий не более чем из (m + n – l) перевозок.

Пример 2. В двух пунктах отправления А1, А2 находится соответственно 150 и 90 тонн горючего. В пункты В1, В2, В3 требуется доставить соответственно 60, 70, 110 тонн горючего. Стоимости перевозки 1т горючего определены в условных денежных единицах и заданы матрицей

.

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

Найдем опорное решение методом минимального элемента. Построение исходного опорного решения начинают с клетки, отвечающей наименьшей стоимости Cij. B данной задаче это клетка (2,2), где С22 = 2.

В эту клетку заносим .

Остатки по строке и по столбцу записываем в соответствующие клетки строки и столбца остатков. Столбец b2 имеет остаток 0 (столбец закрыт), строка a2 имеет остаток 20.0.

Таблица 5

B1

B2

B3

Запас ai

Столбец остатков

A1

6

60

10

7

90

150

60.0

A2

12

2

70

8

20

90

20.0

Заявки

bj

60

70

20

240

Строка остатков

0

0

20.0

Теперь переходим к клетке (1,3), имеющей наименьшую Cij , не считая С22, равную C13 = 3. В клетку (1,3) заносим

.

Затем переходим к клетке (1,1):

.

Наконец переходим к клетке (2,3), в которую заносим

.

Результаты занесены в табл. 4.5.

Таким образом, получаем  опорное решение, которое в матричном представлении имеет вид

.

Вычислим значение целевой функции

на опорном решении X.

Получим

.

Заметим, что это опорное решение дает затраты ближе к оптимальным затратам, чем опорное решение, полученное методом «северо-западного угла» (табл. 6).

Таблица 6


ПН

ПО

B1

B2

B3

Запас ai

A1

6

60

10

70

7

20

150

A2

12

2

8

90

90

Заявки

bj

60

70

20

240

3.2. Методы нахождения оптимального решения ТЗ

3.2.1. Распределительный метод

Любая транспортная задача, т.е. задача, удовлетворяющая условиям (1) – (4), может быть решена симплексным методом или любым универсальный методом линейного программирования. Однако по сравнению с общей задачей линейного программирования транспортная модель имеет некоторые отличительные особенности. В ее системе ограничений применяется одинаковая единица измерения для всех величин, а коэффициенты при всех переменных равны единице. Это позволило разработать для нее специальные методы решения, упрощающие процесс вычислений по сравнению с универсальными методами. В качестве метода построения последовательных итераций, улучшающих найденное опорное решение транспортной задачи, рассмотрим так называемый распределительный метод.

Основные  идеи и принципы работы этого метода покажем на примере 3.

Пример 3. Пусть в пределах одного города перевозится одинаковый груз из трех пунктов отправления к трем пунктам назначения. Всего отправляется ежедневно 30 т, в том числе из первого пункта – 12 т, из 2-го – 8 т, из третьего – 10 т. Эти 30 т груза должны поступать в ПН в следующих количествах: в первый пункт – 6 т, во второй – 9 т, в третий – 15 т. Известны расстояния между пунктами отправления и пунктами назначения. Требуется составить план перевозок, обеспечивающий наименьший общий пробег грузов в тонно-километрах.

Решение. По условию задачи имеются три пункта отправления: А1, A2, А3 (m = 3) и три пункта назначения B1, B2, В3 (n = 3). Обозначим через xij, i = 1, 2, 3; j = 1, 2, 3 неизвестные величины, определяющие объем перевозок в тоннах от i-го ПО к j-му ПН. Представим все исходные данные и неизвестные величины в виде транспортной табл. 7.

Таблица 7


ПН

ПО

B1

B2

B3

Запас ai

A1

1

x11

3

x12

4

x13

12

A2

2

x21

5

x22

3

x23

8

A3

6

x31

7

x32

4

x33

10

Заявки

bj

6

9

15

30

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

,

.

Ограничения в данной задаче связаны с тем, что из каждого пункта отправляется и в каждый пункт доставляется строго определенное количество груза. Например, из пункта А1 можно отправить груз к трем получателям, но общее количество отправляемого груза должно составлять 12 т. Математически это условие выражается уравнением: x11 + x12 + x13 = 12.

Для пунктов А2 и А3 имеем соответственно уравнения:

x21 + x22 + x23 = 8;   x31 + x32 + x33 = 10.

С другой стороны, в первый пункт назначения B1 может поступать груз из трех различных пунктов отправления, но в определенном общем количестве 6 т. Следовательно, должно выполнять условие: x11 + x21 + x31 = 6.

Соответственно для второго и третьего ПН имеем уравнения:

x12 + x22 + x32 = 9,   x13 + x23 + x33 = 15.

Шесть приведенных уравнений и выражают ограничивающие условия данной транспортной задачи, воспользуемся методом «северо-западного угла». Для этого построим транспортную таблицу и начнем ее заполнение с левой верхней клетки. При этом количество заполненных клеток составит: (m + n – 1) = 3 + 3 – 1 = 5.

Занесем полученные значения xij в транспортную табл. 8.

Таблица 8


ПН

ПО

B1

B2

B3

Запас ai

A1

1

x11

3

x12

4

x13

12

A2

2

x21

5

x22

3

x23

8

A3

6

x31

7

x32

4

x33

10

Заявки

bj

6

9

15

30

Проверим правильность заполнения таблицы. Для этого определим количество заполненных клеток и проверим равенство суммы всех запасов, имеющихся в ПО, сумме всех заявок, поступивших в ПН:

  1.  количество заполненных клеток равно 5;
  2.  количество свободных клеток равно 4;
  3.  6 + (6 + 3) + (5 + 10) = (6 + 6) + (3 + 5) + 10. Равенство верное.

Следовательно, таблица заполнена верно.

Таким образом, получено опорное решение, определяющее матрицу перевозок X0 вида.

.

Полученное решение в общем случае не является оптимальным, но оно удовлетворяет всем ограничениям задачи.

Общий пробег грузов при опорном решении составляет

.

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

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

Многоугольник строится так, что одна из его свободных вершин находится в свободной клетке, а остальные – в заполненных (загруженных) клетках, при этом все углы многоугольника должны быть прямыми. При правильном заполнении первоначального варианта каждой свободной клетке будет соответствовать один такой многоугольник.

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

Рис. 1

Определим алгебраическую сумму величин, стоящих в вершинах:

4 – 3 + 5 – 3 = + 3.

Для свободной клетки (2,1) многоугольник имеет вид рис. 2.

Рис. 2

Алгебраическая сумма величин, стоящих в вершинах многоугольника, равна

+ 2 – 1 + 3 – 5 = – 1.

Свободной клетке (3,1) соответствует многоугольник с вершинами (3,1), (1,1), (1,2), (2,2), (2,3), (3,3) (рис. 4.3).

Рис. 4.3

Вычислим алгебраическую сумму величин у вершин данного многоугольника:

6 – 1 + 3 – 5 + 3 – 5 = 1.

Для четвертой свободной клетки (3,2) многоугольник с вершинами (3,2), (2,2), (2,3), (3,3) имеет вид рис. 4.

Рис. 4

Алгебраическая сумма равна 7 – 5 + 3 – 5 = 0.

Рассмотрим экономическое значение алгебраических сумм для соответствующих многоугольников (+ 3, – 1, + 1, 0), полученных для свободных клеток.

Начнем с клетки (1,3). Алгебраическая сумма: 4 – 3 + 5 – 3 = + 3. Если эту клетку с расстоянием перевозки в 4 км включить в план перевозок и предусмотреть перевозку в этом направлении хотя бы 1 т груза, то для сохранения общего равновесия плана перевозок [выполнение условии (1) – (3)] придется уменьшить на 1т перевозки в клетках (1,2) и (2,3) с расстоянием транспортировки в 5 км. Эта операция явно невыгодна, так как мы уменьшаем загрузку двух клеток с малыми расстояниями перевозок за счет увеличения загрузки других клеток с более дальними расстояниями.

Алгебраическая сумма 4 – 3 + 5 – 3 = + 3 показывает, что при ввозе в данную свободную клетку каждой тонны груза мы увеличиваем общую величину пробега груза на 3∙т.км. Соответственно результат +1, полученный для клетки (3,1), говорит о том, что включение этой клетки в план перевозок приведет к увеличению общего пробега по сравнению с исходным планом перевозок на 1т∙км в расчете на каждую дополнительную тонну груза.

Использование клетки (3,2) не дает ни увеличения, ни уменьшения пробега, и только клетка (2,1) с алгебраической суммой – 1 может быть включена в новый план перевозок, так как это приведет к уменьшению общего пробега на 1т.км для каждой включаемой в этот маршрут тонны груза.

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

Шаг 2. Построение нового плана перевозок X1. Рассмотрим свободную клетку (2,1) и соответствующий ей многоугольник с вершинами в клетках (1,1), (1,2), (2,3), (2,1). В пределах этих клеток нужно произвести перемещение с целью улучшения исходного плана перевозок. Для этого перенесем в свободную клетку (2,1) меньшее из чисел, стоящих в клетках с отрицательными знаками: min {6,3}=3. Поместив это число в свободную клетку, прибавим его одновременно к числу, стоящему в другой клетке с положительным знаком, и вычтем его из обеих клеток с отрицательными знаками (рис. 5, 6).

Рис..5

Рис. 6

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

,

которому соответствует транспортная задача (табл. 9).

Таблица 9


ПН

ПО

B1

B2

B3

Запас ai

A1

1

3

3

9

4

0

12

A2

2

3

5

0

3

5

8

A3

6

0

7

0

4

10

10

Заявки

bj

6

9

15

30

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

т∙км.

Полученная величина на 3 т.км меньше, чем в исходном плане перевозок X0:

т∙км.

Шаг 3. Проверим, может ли быть улучшен план перевозок X1. Для этого необходимо снова построить многоугольники для каждой свободной клетки и подсчитать сумму расстояний перевозок, взятых с чередующимися знаками. Заметим, что для клетки (3,2) с расстоянием перевозки 7 км многоугольник имеет вид рис. 7.

Рис 7

Для остальных свободных клеток линии замкнутся в форме квадрата или прямоугольника. Вычисляя для каждой незанятой клетки алгебраическую сумму, получим только положительные числа. Это означает, что план перевозок X1 улучшен быть не может и оптимальное значение L* = 101 достигает при оптимальном плане перевозок X* = X1.

Замечание. Оптимальный план перевозок X* = X1 получен всего лишь в результате одной итерации от опорного решения Х0, при этом уменьшение общего пробега оказалось незначительным (всего около 3 %). В большей степени это объясняется тем, что Х0 уже достаточно близок к оптимальному.

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

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

Алгебраическая сумма показателей дает характеристику потенциальных возможностей данной клетки: при положительном итоге ее заполнение нерационально, при отрицательном – гарантирует (для невырожденных случаев) улучшение плана.

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

В результате ранее свободная клетка становится загруженной, а клетка с наименьшей отрицательной характеристикой превращается в свободную. Общее число занятых клеток остается равным (m + n – 1).

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

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

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

Указанный недостаток распределительного метода легко реализуется в методе потенциалов. Как и в предыдущем разделе, алгоритм решения транспортной задачи рассмотрим сначала на примере 4.

Пример 4. Пусть условия транспортной задачи заданы табл. 10.

Таблица 10


ПН

ПО

B1

B2

B3

Запас ai

A1

3

8

2

35

A2

7

4

8

30

Заявки

bj

15

20

30

65

Найдем опорное решение методом «северо-западного угла» табл. 11.

Таблица 11


ПН

ПО

B1

B2

B3

Запас ai

A1

3

15

8

20

2

35

A2

7

4

0

8

30

30

Заявки

bj

15

20

30

65

Таким образом,

.

Опорному плану перевозок отвечает значение целевой функции

.

Алгоритм метода потенциалов разобьем на несколько шагов.

Шаг 1. Для построения нового плана перевозок X1 строится система (m + n) чисел u1, u2, …, um, v1, v2, …, vn, таких, чтобы выполнялось условие  для всех базисных (загруженных) клеток. Для данного примера система чисел v1, v2, v3, u1, u2 должна удовлетворять уравнениям

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

.

Тогда числа будут равны

Найденные значения занесем в табл. 12.


Таблица 12


v
j

ui

3

8

12

Запас ai

0

3

15

8

20

2

35

4

7

4

0

8

30

30

Заявки

bj

15

20

30

65

Шаг 2. Вторым шагом метода потенциалов является исследование системы чисел ui, i = 1,2; vj, j = 1, 2, 3 на потенциальность, то есть каждый элемент cij, отвечающий свободной клетке, сравниваем с соответствующей разностью vjui. Если для всех таких элементов выполняются неравенства:

,                                               (9)

то система потенциальна и построенный план оптимален. Если для некоторого cij

,

то система (ui vj) не является потенциальной, план X оптимальным не является, и  надо перейти к следующему шагу. Итак, проверим систему на потенциальность:

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

В случае непотенциальности системы переходим к общему шагу – улучшению (в смысле приближения к оптимальному решению) плана.

Шаг 3. Для клетки (1,3) условие (4.9) не выполняется, следовательно, строим для нее многоугольник и производим перераспределение как в распределительном методе (рис. 8, 9).

Рис. 8

Рис. 9

Таким образом, получим новый план перевозок:

.

Посчитаем значение целевой функции L1, отвечающее плану X1:

.

Шаг 4. Поскольку мы перераспределили перевозки, то условие потенциальности не выполняется и нужно построить другую систему чисел. Обычно новую систему чисел (ui vj) i = 1, 2; j = 1, 2, 3 строят путем исправления старой. Для того чтобы для клетки (1,3) выполнялось условие потенциальности, уменьшим v3 на величину

,                                         (10)

т.е. v3 на величину L13. Тогда для всех клеток j-го столбца, вошедших в новый набор, кроме клетки (i, j), условие потенциальности не будет выполняться. Для того чтобы для этих клеток восстановить потенциальность, уменьшим соответствующие числа на Lij. Однако при этом нарушается потенциальность для клеток набора, расположенных в строках, следовательно, их также необходимо уменьшить на Lij.

Итак, для клетки (1, 3) Lij = 12 – 0 – 2 = 10. Поскольку в третьем столбце есть еще заполненная клетка (2,3), то необходимо уменьшить u2 на Lij = 10. В этом случае нарушается потенциальность клетки (2,2), т.к. она тоже находится во второй строке, следовательно, из  v2 вычитаем Lij = 10. В результате у нас получилась следующая транспортная табл. 13.

Таблица 13


v
j

ui

3

8 – 10 = – 2

12 – 10 = 2

Запас ai

0

3

15

8

2

20

35

4 – 10 = – 6

7

4

20

8

10

30

Заявки

bj

15

20

30

65

Шаг 5. Переходим к следующей итерации, возвращаемся к шагу 2.

Вторая итерация.

Шаг 2. Проверяем на потенциальность свободные клетки транспортной таблицы:

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

Шаг 3. Для клетки (2,1) строим многоугольник и перераспределяем перевозки (рис. 10, 11).

Рис. 10

Рис. 11

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

.

Стоимость перевозок по плану равна

.

Шаг 4. Для клетки (2,1) в соответствии с формулой (4.10) Lij = 3 – (– 6) – 7 = 2.


Таблица 14


v
j

ui

2 – 2 = 0

– 2

2 – 2 = 0

Запас ai

0 – 2 = – 2

3

5

8

2

30

35

– 6

7

10

4

20

8

0

30

Заявки

bj

15

20

30

65

Шаг 5. Переходим к следующей итерации, возвращаемся к шагу 2.

Третья итерация.

Шаг 2. Проверяем на потенциальность свободные клетки транспортной таблицы:

Таким образом, полученная система потенциальна. Оптимальным планом перевозок является

.

При этом оптимальная суммарная стоимость перевозок составит

.

22

PAGE  22