Конспект лекций по курсу «Математическое программирование»

 

Для определения потенциалов решим следующую систему:

Положим α₁=0. Тогда β₁=2; α₂=3; β₂=1; β₃=5; α₃=1; β₄=11. Найденные потенциалы вносим в таблицу 5.9.

Вычисляем псевдостоимости  для свободных клеток и проставляем  их в левые верхние углы клеток. Выбираем свободную клетку, в которой  ;  например, выберем клетку (1,4). Строим цикл пересчета, проходящий через эту клетку, и произведем по нему максимально допустимый сдвиг h = 10 (в отрицательных клетках наименьшей перевозкой является х₂₃=10). После сдвига клетка (2,3) становится свободной, а клетка (1,4) - базисной. Получаем новый опорный план, записанный в таблице 5.10.

Таблица 5.10

Пн По	В1	В2	В3	В4	Запасы	αi
А1	2 5	1                   4	0                   7	6 10	15	0
А2	5 17	4 18	3                   8	9                     9	35	3
А3	8                  7	7                 11	6 17	12 3	20	6
Потребности	22	18	17	13	70=70
βj	2	1	0	6

Вновь строим систему  потенциалов, рассчитываем псевдостоимости,  строим цикл пересчета, проходящий через клетку (3,1), делаем по нему максимально допустимый сдвиг величины h=3.

Таблица 5.11

Пн По	В1	В2	В3	В4	Запасы	αi
А1	2 2	1                   4	-4                 7	6 13	15	0
А2	5 17	4 18	-1                 8	9                     9	35	3
А3	4 3	2                 11	6 17	8                   12	20	2
Потребности	22	18	17	13	70=70
βj	2	1	-4	6

 

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

Итак, оптимальный план имеет  следующий вид: х₁₁=2; х₁₄=13; х₂₁=17; х₂₂=18; х₃₁=3; х₃₃=17.

При этом f_mln = 2•2 + 13•6 + 17•5 + 18•4 + 3•4 + 17•6 =353

 

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

 

При  рассмотрении  транспортной  задачи  (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	20
А2	1	5	4	30
Потребности	15	25	18	58 #50

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

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

Таблица 5.13

Пн По	В1	В2	В3	Запасы
А1	2	4	3	20
А2	1	5	4	30
А3	0	0	4	8
Потребности	15	25	18	58=58

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

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

Пн По	В1	В2	В3	Запасы	αi		Пн По	В1	В2	В3	Запасы	αi
А1	2 15	4 5	3       3	20	0		А1	2       2	4 20	5       3	20	1
А2	3      1	5 20	4 10	30	1		А2	1 15	5 5	4 10	30	0
А3	-1     0	1       0	0 8	8	-3		А3	-3     0	1       0	0 8	8	-4
Потре бности	15	25	18	58=58			Потре бности	15	25	18	58=58
βj	2	4	3				βj	1	5	4

 

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

Пн По	В1	В2	В3	Запасы	αi		Пн По	В1	В2	В3	Запасы	αi
А1	0       2	4 10	3 10	20	0		А1	0       2	4 2	3 18	20	0
А2	1 15	5 15	4	30	1		А2	1 15	5 15	4         4	30	1
А3	-3     0	1       0	0 8	8	-3		А3	-4     0	0 8	0	8	-4
Потре бности	15	25	18	58=58			Потре бности	15	25	18	58=58
βj	0	4	3				βj	0	4	3

 

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