Открытые транспортные задачи

При рассмотрении транспортной задачи (5.1 - 5.4) предполагалась справедливость равенства . Такие транспортные задачи называются закрытыми.

На практике часто возникают так называемые открытые транспортные задачи, для которых .

Если , то задача состоит в отыскании наиболее дешевого плана перевозок, при котором полностью удовлетворяются потребности пунктов назначения В_j (); при этом не все запасы пунктов отправления исчерпываются.

Если же , то потребности пунктов назначения не полностью удовлетворяются, а запасы пунктов отправления исчерпываются.

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

Пусть . Введём фиктивный пункт назначения В_n+1 с потребностью .

Будем считать, что c_in+1=0 при всех . После решения полученной закрытой транспортной задачи опустим перевозки в пункт В_n+1; получим оптимальный план перевозок для открытой транспортной задачи.

Аналогично, в случае справедливости неравенства вводится фиктивный пункт отправления А_m+1, и дело сводится к решению закрытой транспортной задачи.

Пример. Пусть исходные данные приведены в таблице 5.12

Таблица 5.12

Пн По	В1	В2	В3	Запасы
А1	^2	^4	^3
А2	^1	^5	^4
Потребности				58 #50

Это открытая транспортная задача, в которой .

Введем фиктивный пункт отправления А₃ с запасом 8 (табл. 5.13)

Таблица 5.13

Пн По	В1	В2	В3	Запасы
А1	^2	^4	^3
А2	^1	^5	^4
А3	^0	^0	^4
Потребности				58=58

Получилось закрытая транспортная задача. Решим ее методом
потенциалов (табл. 5.14, 5.15, 5.16, 5.17).

Таблица 5.14 Таблица 5.15

Пн По

В1

В2

В3

Запасы

αi

Пн По

В1

В2

В3

Запасы

αi

А1

^2

^4

^3 3

А1

^2^2

^4

^5^3

А2

^3 1

^5

^4

А2

^1

^5

^4

А3

^-1 0

^1 0

^0

-3

А3

^-^3^0

^1 0

^0

-4

Потре бности

58=58

Потре бности

58=58

βj

βj

Таблица 5.16 Таблица 5.17

Пн По

В1

В2

В3

Запасы

αi

Пн По

В1

В2

В3

Запасы

αi

А1

^0^2

^4

^3

А1

^0^2

^4

^318

А2

^1

^5

^4

А2

^1

^5

^4^4

А3

^-^3^0

^1 0

^0

-3

А3

^-^4^0

^0

^0

-4

Потре бности

58=58

Потре бности

58=58

βj

βj

В таблице 5.17 - оптимальный план перевозок для закрытой транспортной задачи. Опускаем перевозки из фиктивного пункта А₃,
получим оптимальный план для открытой транспортной задачи (табл.5.18).

f_min = 2•4 + 18•3 + 15•1 + 15•5 = 152

Потребность пункта В₂ удовлетворена не полностью.

Таблица 5.18

Пн По	В1	В2	В3	Запасы
А1	^2	^4	^318
А2	^1	^5	^4
Потре бности

Дата добавления: 2014-01-07