Меню
Главная
Авторизация/Регистрация
 
Главная arrow Экономика arrow Исследование операций в экономике

Открытая модель транспортной задачи

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

7.9. Найти оптимальное распределение поставок для транспортной задачи (табл. 7.17).

Решение. В данном случае суммарный спрос потребителей больше, чем суммарная мощность поставщиков (45 + + 35 + 55 + 65 = 200 > 40 + 60 + 90 = 190). Введем "фиктивного поставщика" и в таблицу поставок добавим дополнительную строку (табл. 7.18) так, чтобы задача стала закрытой. Для этого мощность фиктивного поставщика следует принять равной 10 = 200 – 190. Коэффициенты затрат этой добавленной строки определяются издержками ввиду недогрузки мощностей потребителей. Если информация об этих издержках отсутствует, то их принимают равными одному и тому же числу (например, нулю, как в табл. 7.18). Согласно теореме 7.3, конкретное значение этого числа нс влияет на оптимальное распределение поставок.

Таблица 7.17

45

35

55

65

40

4

1

2

5

60

3

2

3

7

90

4

4

5

2

10

0

0

0

0

Таблица 7.18

45

35

55

65

40

4

1

2

5

60

3

2

3

7

90

4

4

5

2

Первоначальное распределение поставок для сформулированной закрытой транспортной задачи найдем, например, по методу наименьших затрат. Для удобства укажем последовательность заполнения таблицы поставок: xi4 =10, х12 = 35, х34 = 55, х13 = 5, х23 = 50, х91 =10, х31 = 35. В результате приходим к следующему базисному распределению поставок (табл. 7.19).

Таблица 7.19

4

5

-2

2

7

-3

4

5

-4

0

0

0

-2

0

1

0

2

(7.19)

Установим, оптимально ли это распределение, для этого найдем для него матрицу оценок (7.19). Так как среди

Рис. 7.7

оценок свободных клеток есть отрицательные, то найденное распределение нс оптимально. Переведем поставку в одну из клеток с наименьшей отрицательной оценкой, например в клетку (4,3). Цикл для этой клетки изображен на рис. 7.7. Поставка, передаваемая по циклу, равна х43 = min {50,35,10} = 10. Передвигая по циклу поставку, равную 10 единицам, приходим к следующему распределению поставок (табл. 7.20). Найдем оценки свободных клеток данного распределения (см. матрицу оценок (7.20)). Так как оценки всех свободных клеток неотрицательны, то распределение поставок табл. 7.20 оптимально. ►

Таблица 7.20

4

5

2

7

4

5

0

0

0

(7.20)

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

Венгерский метод решения транспортной задачи

Основные идеи обсуждаемого метода впервые были высказаны венгерским математиком К. Эгервари в 1931 г. Г. Кун (1953) развил подход Эгервари и назвал созданный им метод венгерским.

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

Будем считать, что в процессе перевозки груза помимо уже привычных для нас поставщиков и потребителей могут участвовать перевалочные пункты. Пусть i3 = {} – множество поставщиков, потребителей и перевалочных пунктов; L = |/у|, где ljj=(Pj'Pj) – множество упорядоченных пар, определяющих, между какими пунктами множества Р возможна перевозка груза. Тогда пара (Р, L) называется транспортной сетью. Элементы р{ множества Р называются пунктами, а элементы /~ e Lзвеньями транспортной сети. При графическом изображении звену А. соответствует стрелка, идущая от пункта /т к пункту/^. Заметим, что транспортная сеть является частным случаем графа, для которого Р есть множество вершин, L – множество звеньев.

Каждому звену А- сопоставим число d•• > 0, называемое пропускной способностью звена. Величина пропускной способности есть максимально допустимый объем поставки, который может проходить по соответствующему звену за рассматриваемый промежуток времени. Величину поставки, передаваемой по звену L будем называть потоком по соответствующему звену и ооозначать, как и раньше, х{•. Очевидно, что

(7.21)

для всех i и j.

Задача, двойственная транспортной задаче (7.4)-(7.7), состоит в нахождении максимума функции

(7.22)

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

(7.23)

где

Отметим, что переменные ир Vj имеют непосредственное отношение к потенциалам рассмотренного выше распределительного метода. Действительно, потенциалы из параграфа 7.4 можно считать неположительными. Тогда они будут отличаться только знаком от соответствующих переменных иР v.

Введем в рассмотрение матрицу

(7.24) где

(7.25)

(7.26)

Очевидно, что элементыматрицы Т неотрицательны и тем самым выполнены усло́вия (7.23).

Рассмотрим вспомогательную сеть, множество Р пунктов которой совпадает с множеством пунктов задачи (7.4)– (7.7), а множество звеньев состоит из тех звеньев этой задачи, для которых равны нулю. Поскольку звенья сети соответствуют клеткам матрицы поставок при матричной форме записи, то при переходе к сети для нас остаются "активными" только клетки

Используя вторую теооему двойственности, можно доказать, что если в сети удастся найти максимальный поток, удовлетворяющий условиям (7.4), (7.5), (7.7) ("насыщающий" максимальный поток), то он также является решением исходной задачи (7.4)-(7.7).

Рассмотрим алгоритм этого поиска, используя матричную форму записи задачи (соответственно термины "поток в сети" и "распределение поставок" равнозначны).

Предположим, найден некоторый поток в сети (Р, L), удовлетворяющий условиям

гдеПусть г – строка матрицы, для которой

(поставщик с номером i не полностью отправил свой груз). Сопоставим этой строке метку вида, где

Аналогичным образом поступаем со всеми поставщиками (строками матрицы), которые не полностью отправили свой груз.

Пусть г – номер какой-либо из отмеченных строк и j – номер такого произвольного неотмеченного столбца, что(клетка (i, j) активная). Сопоставим ему метку , где

и произвольной неотмеченной r-й строке, для которой ставим в соответствие метку, где

Продолжаем отмечать строки и столбцы до тех пор, пока не будет отмечен какой-либо "ненасыщенный" столбец, т.е. такой столбец с некоторым номером, для которого

Вычисляем значение

(7.27)

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

Поочередно прибавляем и вычитаем значение Δ из значенийв цепочке

гдеи

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

(7.28)

где tij – множества отмеченных строк и столбцов (соответственно).

Величину δ вычитаем из отмеченных строк и прибавляем к отмеченным столбцам матрицы Т.

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

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

Таблица 7.21

50

30

10

10

40

6

4

4

5

20

6

9

5

8

40

8

2

10

6

Решение. Матрица, определяемая формулой (7.24), имеет вид

На первом шаге решения активными остаются те клетки таблицы поставок, для которых соответствующие элементы матрицыравны нулю (табл. 7.22: неактивные клетки выделены).

Рассмотрим какое-либо распределение поставок по активным клеткам. Оно может быть получено, например, с помощью любого из методов, обсуждавшихся в параграфе 7.2 (см. табл. 7.22).

Отмечаем строки, оказавшиеся ненасыщенными:

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

Таблица 7.22

1/20

1/20

1/20

50

30

10

10

40

6

4

4 10

5 10

0/20

20

6 20

9

5

8

40

8

2 30

10

6

0/10

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

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

Отмечаем строки и столбцы матрицы поставок (табл. 7.23).

Таблица 7.23

!!!

1/20'

1/20

1/20

1/20

50

30

10

10

40

о

4

4 10

5 10

0/20

20

6 20

9

5

8

40

8

9

' 30

10

6

0/10

В результате оказался отмеченным первый – ненасыщенный – столбец. Путь перераспределения потока состоит в данном случае из единственной клетки (1,1). Находим величину Δ изменения потока в сети по формуле (7.27):

Величину поставки клетки (1, 1) увеличиваем на Δ = 20, и вновь отмечаем строки и столбцы (табл. 7.24).

Таблица 7.24

3/10

50

30

10

10

40

6 20

4

4 10

5 10

20

6 20

9

5

8

40

8

2 30

10

6

0/10

Вновь первый – ненасыщенный – столбец оказался неотмеченным. Поэтому находим величину δ по формуле (7.28):

Перестраиваем сеть, вычитая значение δ из элементов третьей строки матрицы Т = Τχιi прибавляя к элементам второго столбца этой матрицы. Получаем матрицу

определяющую активные клетки таблицы поставок предстоящего шага.

Отмечая строки и столбцы таблицы поставок, приходим к табл. 7.25.

Таблица 7.25

1/10*

3/10

1/10

3/10

50

30

10

10

40

6 20

4

4 10

5 10

4/10

20

6 20

9

5

8

40

8

  • 2
  • 30

10

6

0/10

В результате оказался отмеченным ненасыщенный первый столбец. Путь перераспределения потока образуют клетки (1, 1), (1, 4), (3, 4). Величину Δ изменения потока в сети находим по формуле (7.27):

Поочередно прибавляя и вычитая Δ из поставок клеток пути перераспределения потока, приходим к табл. 7.26.

Таблица 7.26

50

30

10

10

40

6 30

4

4 10

5 0

20

6 20

9

5

8

40

8

2

10

6 10

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

Рассмотрим применение венгерского метода для решения задачи о назначениях (параграф 7.2.), являющейся частным случаем транспортной задачи в предположении единичности мощностей всех поставщиков и потребителей. Можно доказать, что в общем случае решение этой задачи будет целочисленным. Как следствие, задача о назначениях допускает также комбинаторную формулировку: в каждой строке и столбце данной квадратной матрицы выбрать по одному элементу так, чтобы сумма этих элементов была наименьшей.

7.11. Трудозатраты отдельных сотрудников предприятия по видам работ представлены в табл. 7.27.

Таблица 7.27

!!!

Виды работ

1

2

3

4

Исполнители

1

1

3

5

3

работ –

2

2

2

3

2

сотрудники

3

5

2

6

3

предприятия

4

1

4

3

2

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

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

Таблица 7.28

1

1

1

1

1

1

3

5

3

1

2

2

3

2

1

5

2

6

3

1

1

4

3

2

(В дальнейшем строку и столбец таблицы, в которые вписаны единичные мощности "поставщиков" и "потребителей", будем опускать.)

Применяя венгерский метод, находим матрицу, определяемую формулой (7.24):

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

Рассмотрим какое-либо распределение поставок но активным клеткам (табл. 7.29; неактивные клетки выделены).

Единственная ненасыщенная строка в данном случае первая. Отмечаем эту строку: . Единственная активная клетка первой строки лежит в первом столбце – отмечаем этот столбец:. Клетка первого столбца, имеющая ненулевую "поставку", расположена в четвертой строке, поэтому. Находим также, что . В результате приходим к табл. 7.29.

Таблица 7.29

1/1

1

3

5

3

0/1

2

2

3

2 1

5

2 1

6

3

1 1

4

3

2

1/1

Поскольку третий – единственный ненасыщенный – столбец оказался неотмеченным (см. табл. 7.29.), необходима перестройка сети. Для этого находим величину δ по формуле (7.28):

где – элементы матрицы . Вычитаем значение δ из элементов отмеченных (первой и четвертой) строк матрицы Т = 7'0 и прибавляем к элементам неотмеченного (единственного в данном случае) первого столбца этой матрицы. В результате приходим к матрице

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

Продолжая решение задачи, приходим к табл. 7.30.

Таблица 7.30

!!!

1/1

Vi*

1

3

5

3

0/1

2

2

3

2 1

5

2 1

6

3

1 1

4

3

2

1/1

В результате оказался отмеченным ненасыщенный третий столбец. Путь перераспределения потока в данном случае образуют клетки (4, 3), (4, 1),(1, 1). Находим величину Δ изменения потока в сети по формуле (7.27): Δ = 1.

Величины поставок клеток (4,3) и (1,1) увеличиваем на Δ = 1, а поставку клетки (1,1) уменьшаем на эту же величину. В результате приходим к табл. 7.31.

Таблица 7.31

1 1

3

5

3

2

2

3

2 1

5

2 1

6

3

1

4

3 1

2

Максимальный поток оказывается насыщающим для всех строк и столбцов данной таблицы, поэтому полученное распределение "поставок" (исполнителей по видам работ) является оптимальным. ►

 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы