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

Решим методом потенциалов закрытую транспортную задачу, заданную в табл. 3.11, в которую уже внесено некоторое допустимое базисное распределение. Суммарные транспортные расходы составляют при этом плане перевозок f(Х)= 3-5+2-25+1-20 +2-25+1-15+4-20 = 230. Потенциалы по формуле (14) находим следующим образом: задавая и₁ = 0, находим по клетке (1;1) v₁ = 3, по клетке (1;2) v₂ = 2, а по клетке (1;4) v₄ = 1; затем по клетке (2;1) находим u₂ = 1 и по клетке (2;3) v₃ = 2; наконец, по клетке (3;3) находим u₃ = -2.

 

 

Таблица 12 - Пример решения транспортной задачи методом потенциалов

 

Мощности поставщиков	Мощности потребителей
30
	3 +	2 -
	- 25		+ 15
		+	- 20		-2

 

Матрица оценок клеток для этого плана рассчитывается по формуле (15):

 

 

Наличие отрицательных оценок свидетельствует о том, что план неоптимален. Построим контур перераспределения, например, для клетки (3;2); в табл. 12 он показан пунктиром и его вершинам присвоены соответствующие знаки.

Наименьшая поставка в вершине контура со знаком «-» равна 20, поэтому проведем перераспределение поставок, уменьшив поставки в клетках со знаком «-» на 20 и увеличив поставки в клетках со знаком «+» также на 20; при этом клетка (3;2) заполняется, а клетка (3;3) освобождается. Новый план представлен в табл. 13; соответствующие значения потенциалов показаны в последних столбце и строке.

 

Таблица 13 - Результаты решения транспортной задачи методом потенциалов

 

Мощности поставщиков	Мощности потребителей
30	25
	25

 

Матрица оценок клеток этого распределения не содержит отрицательных значений:

,

следовательно, данный план перевозок является оптимальным. Стоимость перевозок по этому плану равна:

 

f(X) =3*25 +2*5 + 1*20 +2*5+ 1*35 +2*20 = 180.

 

Наличие нулевой оценки незанятой клетки (3;1) говорит о том, что оптимальный план не является единственным. Можно отметить также, что применяя для начального распределения в этой транспортной задаче модификацию двойного предпочтения метода наименьших стоимостей, мы сразу же получили бы оптимальное распределение, представленное в табл. 13.

 

Решение транспортной задачи с помощью команды «Поиск решения».

При «Поиске решения» задача может быть представлена как в примере.

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

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

 

	A	B	C	D	E	F
	таблица стоимости перевозок
	Пункты назначения	Пункты отправления
	Киев	Львов	Ужгород
	Севастополь
	Симферополь
	Ялта
	Алушта
	таблица потребностей в товаре каждого розничного магазина
	Магазины в городах	Количество требуемого товара	Киев	Львов	Ужгород	Количество, подлежащее доставке
	Севастополь					=СУММ(C11:E11)
	Симферополь
	Ялта
	Алушта
	Всего	=СУММ(B11:B14)
	таблица товарных запасов складов
		Город	Киев	Львов	Ужгород
		Было
		Осталось	=C19-C15
	таблица вычисляемой стоимости перевозок
		Город	Киев	Львов	Ужгород
		стоимость перевозки	=СУММПРОИЗВ (B4:B7;C11:C14)
		Всего	=СУММ(C24:E24)

 

Жирным шрифтом выделены заданные условия задачи. В столбце «Количество, подлежащее доставке» суммируются ячейки по строкам, соответствующим пунктам назначения.

Изменяемые ячейки $C$11:$E$14 должны быть положительными и целыми числами.

Целевая ячейка $C$25 должна стремиться к минимальному значению.

Остатки продукции на складах в ячейках $C$20:$E$20 должны быть положительны. «Количество, подлежащее доставке» в ячейках $F$11:$F$14 должно быть равно содержимому ячеек $B$11:$B$14.

Варианты заданий

Индивидуальная работа предполагает выполнение задачи согласно выбранному варианту. Распределение заданий по вариантам представлено в таблице 20.

Таблица 20 - Варианты заданий

Номер варианта
Номер задания
Задача
Номер варианта
Номер задания
Задача

 

Задание: 1) скорректировать мощности поставщиков в соответствии с выбранным вариантом увеличения мощности; 2) при помощи программы MS Excel (команды «Поиск решения») определить наиболее экономичный вариант прироста мощностей; 3) для выбранного варианта реструктуризации рассчитать оптимальный план перевозок продукции при помощи метода потенциалов.

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

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

Известны следующие величины:

- матрица транспортных расходов действующих предприятий;

- транспортные расходы на доставку продукции от вновь построенного завода к -му потребителю;

- себестоимость единицы изделия на действующих предприятиях;

- себестоимость единицы продукции после расширения производства;

- себестоимость единицы продукции на вновь строящемся предприятии;

- удельные капитальные затраты на расширение производства;

- удельные капитальные затраты на вновь строящемся предприятии.

Пояснения к задаче.

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

 

Вариант 1.

Таблица 22 - Матрица транспортных расходов действующих предприятий ()

 

Постав-щики	Мощность поставщи-ков	Потребители и их спрос

 

Себестоимость единицы изделия на действующих предприятиях: =3, =4, =2, =5.

Варианты прироста мощностей:

1) строительство нового предприятия:

= 4; =1; =2; =3; =5; =2; =8.

2) реконструкция предприятия :

= 2; =6.

 

 

Вариант 2.

 

Таблица 23 - Матрица транспортных расходов действующих предприятий ()

 

Постав-щики	Мощность поставщи-ков	Потребители и их спрос

 

Себестоимость единицы изделия на действующих предприятиях: =5, =6, =4, =3.

Варианты прироста мощностей:

1) строительство нового предприятия:

= 3; =4; =2; =2; =5; =4; =6.

2) реконструкция предприятия :

= 3; =5.

 

Вариант 3.

 

Таблица 24 - Матрица транспортных расходов действующих предприятий ()

 

Постав-щики	Мощность поставщи-ков	Потребители и их спрос

 

Себестоимость единицы изделия на действующих предприятиях: =5, =6, =7, =6.

Варианты прироста мощностей:

1) строительство нового предприятия:

= 3; =5; =4; =6; =2; =3; =8.

2) реконструкция предприятия :

= 4; =6.

 

Вариант 4.

Таблица 25 - Матрица транспортных расходов действующих предприятий ()

 

Постав-щики	Мощность поставщи-ков	Потребители и их спрос

 

Себестоимость единицы изделия на действующих предприятиях: =3, =5, =4, =3.

Варианты прироста мощностей:

1) строительство нового предприятия:

= 6; =9; =8; =10; =7; =4; =12.

2) реконструкция предприятия :

= 3; =10.

 

Вариант 5.

 

Таблица 26 - Матрица транспортных расходов действующих предприятий ()

 

Постав-щики	Мощность поставщи-ков	Потребители и их спрос

 

Себестоимость единицы изделия на действующих предприятиях: =5, =6, =7, =6.

Варианты прироста мощностей:

1) строительство нового предприятия:

= 13; =15; =14; =16; =2; =13; =8.

2) реконструкция предприятия :

= 4; =6.

 

Вариант 6.

 

Таблица 27 - Матрица транспортных расходов действующих предприятий ()

 

Постав-щики	Мощность поставщи-ков	Потребители и их спрос
		8,4	6,8	7,6		9,3
		4,1	4,9	5,4	6,2	7,8
		7,3	5,2	9,1	9,4	10,1
		11,1				9,4

 

Себестоимость единицы изделия на действующих предприятиях: =4,3; =6,5; =7,4; =5,3.

Варианты прироста мощностей:

1) строительство нового предприятия:

= 6,6; =8,9; =7,8; =10; =9,7; =9,4; =12.

2) реконструкция предприятия :

= 3; =10.

 

Вариант 7.

Таблица 28 - Матрица транспортных расходов действующих предприятий ()

Постав-щики	Мощность поставщи-ков	Потребители и их спрос

 

Себестоимость единицы изделия на действующих предприятиях: =8; =8; =6; =5.

Варианты прироста мощностей:

1) строительство нового предприятия:

= 7; =10; =4; =3; =5; =4; =13.

2) реконструкция предприятия :

= 6; =8.

СОДЕРЖАНИЕ ОТЧЕТА

1) Цель работы;

2) постановка задачи;

3) результаты расчетов, проведенных в Excel методом потенциалов и командой «Поиск решения»;

4) выводы по выполнению работы.

 

КОНТРОЛЬНЫЕ ВОПРОСЫ

1)Что такое математическая модель транспортной задачи?

2)Сформулируйте особенности транспортной задачи линейного программирования?

3)Как установить оптимальность допустимого базисного решения?

4)Опишите методы нахождения первоначального базисного распределения поставок?

5)В чем заключается суть метода потенциалов?

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

 

1) Вагнер Г. Основы исследования операций./ Г. Вагнер. - М.: Мир, 1972. – 562 с.

2) Вентцель Е.С. Исследование операций. Задачи, приниципы, методология./ Е.С. Вентцель.-М.: Высшая школа, 2001.-208с.

3) Ковалёв В.Г. Математическое программирование (линейные задачи)./ В.Г. Ковалёв, А.Р. Наринян, В.А. Поздеев. – К.: Изд-во Европ. ун-та, 2003. – 170 с.

4) Кремер Н.Ш. Исследование операций в экономике./ Н.Ш.Кремер, Б.А. Путко, И.М. Тришин. – М.: ЮНИТИ, 2006.-407 с.

5) Розен В.В. Математические модели принятия решений в экономике./ В.В. Розен. – М.: Книжный дом «Университет», Высшая школа, 2002. – 288 с.

6) Трояновский В.М. Математическое моделирование в менеджменте./ В.М. Трояновский.- М.: Русская деловая литература, 1999.-240с.

7) Федосеев В.В., Гармаш А.Н. Экономико-математические методы и прикладные модели./ В.В.Федосеев, А.Н. Гармаш.– М.: ЮНИТИ, 1999.-391с.

8) Чейз Р. Б. Производственный и операционный менеджмент / Р.Б. Чейз. Н. Дж. Эквилайн, Р.Ф. Якобс. - М.: Вильяме, 2004. — 704 с.