Решение транспортной задачи методом потенциалов

 

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

Таблица 13

	B 1	B 2	B 3	B 4	B 5	Запасы (аj)
А 1	-	40		-	-		0
А 2		-			-		-2
А 3	-		-	-			-4
Потребности (bj)
	7	22	9	6	12

Составим систему потенциалов для заполненных клеток табл.13.

Имеем: , получим:

Потенциалы для строк записываем в дополнительном столбце справа, а потенциал столбцов _j в нижней дополнительной строке (табл. 13).

Найдем косвенные тарифы для пустых клеток.

Достаточное условие оптимальности не выполнено для клетки A ₂ B ₂.

Составим для нее цикл пересчета. В таблице 13 он отмечен штриховыми линиями.

 

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

D = min (40; 20) = 20 – величина сдвига по циклу.

После пересчета по циклу получим:

 

Получаем новый план перевозок (табл.14).

Таблица 14

	B 1	B 2	B 3	B 4	B 5	Запасы (аj)
А 1	-			-	-		0
А 2			-		-		-9
А 3	-		-	-			-4
Потребности (bj)
	14	22	9	13	12

 

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

руб.

Составим систему потенциалов для заполненных клеток табл.14.

Имеем: ,

Полагая ₁= 0, находим потенциалы.

Получим:

Подсчитаем косвенные тарифы для пустых клеток.

Для всех свободных клеток табл. 14 истинные тарифы меньше их косвенных тарифов: . Полученный план перевозок оптимальный и единственный.

Наименьшая стоимость перевозок составила 1950 руб.

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

 

5.5 Особенности решения транспортной задачи
с невыполненным балансом

 

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

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

. (18)

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

1. Пусть дисбаланс между запасами и потребностями равен ,

. (19)

Тогда вводим в рассмотрение (n+ 1)-го потребителя с потребностью . В этом случае баланс выполняется:

. (20)

Дополняем матрицу тарифов перевозок для (n+ 1)-го потребителя нулевыми числами

, . (21)

Условие (21) означает, что неизвестный груз остается на базе А_i (нулевая цена перевозки).

2. Далее решаем задачу закрытого вида.

Случай невыполнения баланса из-за превышения потребностей над запасами решается путем привлечения новых баз.

Литература

а) основная литература

1. Акулич И.Л. Математическое программирование в решениях и задачах: Учебное пособие для студентов экономических специальностей ВУЗов - М.: Высшая школа,1986

2.

б) дополнительная литература

3. Карпелевич Ф.М., Садовский Л.Е. Элементы линейной алгебры и линейного программирования. - М.: Наука, 1967.

4. Карасев А.И., Аксютина З.М., Савельева Т.И. Курс высшей математики для экономических вузов. Ч.2. - М.: Высш. шк., 1982.

5. Калихман И.Л. Сборник задач по математическому программированию. - М.: Высшая школа,1975

6. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. Учебное пособие для ВУЗов. - М.:Высшая школа, 1976

7. Першин А.И. Элементы линейной алгебры и линейного программирования. Приволжское книжное из-во, Саратов,1967

8. Муртаф Б. Современное линейное программирование: Пер.с англ. - М.:Мир,1984

9. Баландин В.С.,Першин А.И. Методические указания по линейному программированию. - Саратов, 1984

10. Баландин В.С., Першин А.И. Методы оптимизации в экономических задачах. Учебное пособие. - Саратов, СГУ, 1988

11. Эддоус М., Стэнсфил Р.Методы принятия решений/ Пер. с англ.- М.:Аудит, ЮНИТИ, 1997.

 

 

 

Учебное издание

 

Балаш Ольга Сергеевна

Высочанская Елена Юрьевна

Попова Анна Александровна

 

 

МАТЕМАТИКА

Методические указания

 

Подписано в печать _____________

Формат 60´84 1/16 Усл. печ. л. 2,5.

Тираж 300 экз.

 

 

Саратовский институт (филиал)

Российского государственного торгово-экономического университета

410052, Саратов, ул. Международная, 24

 

Отпечатано в РИО Саратовского института (филиала)

Российского государственного торгово-экономического университета

410052, Саратов, ул. Международная, 24