I. Метод наименьшей стоимости.

РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ

Решение открытой задачи сводится к решению закрытой

Лекция 12

 

Транспортная задача

Транспортные задачи – специальный класс задач линейного программирования. Эти задачи описывают перемещение (перевозку) какого-либо товара из пункта направления (например, места производства) в пункт назначения (склад или магазин). Назначение транспортной задачи – определение объемов перевозок из пунктов отправления в пункты назначения с минимальной суммарной стоимостью перевозок.

m

n

– количество поставщиков продукции;

– количество потребителей продукции;

– индекс для поставщиков;

– индекс для потребителей;

, – наличие продукции у каждого поставщика;

, – потребность в продукции каждого потребителя;

– стоимость доставки продукции единицы продукции от - поставщика к -потребителю.

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

 

– задача называется закрытой

– задача называется открытой(с нарушенным балансом).

 

 

 

С этой целью при a < b добавляем фиктивного поставщика с запасом b-a. Если же a > b , то добавляем фиктивного потребителя с заказом груза a-b. В обоих случаях соответствующие фиктивным объектам тарифы перевозок c_ij полагаем равными нулю. В результате суммарная стоимость перевозок не изменяется.

 

Математическая модель

 

– решение задачи

 

Целевая функция

– целевая функция

 

Ограничения

, , ,

 

 

Этапы:

I. Построение начального базисного решения : метод северо-западного угла, метод наименьшей стоимости (минимального элемента), метод Фогеля.

II. Итеративный процесс поиска оптимального решения (метод потенциалов).

 

Общая транспортная задача с m пунктами отправления и n пунктами назначения имеет m+n ограничений в виде равенств, по одному на каждый пункт отправления и назначения. Т. к. транспортная задача д.б. сбалансированной, то одно из этих равенств избыточно. Т.о. транспортная задача имеет m+n+1 независимых ограничений, отсюда вытекает, что начальное базисное решение состоит из m+n+1 базисных переменных.

 

Пусть поставщиков продукции,

потребителей продукции

Запасы ,

Потребность

Затраты на перевозку продукции

 

 

					Запасы
Потребность

 

 

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

 

1)Выбор ячейки с наименьшим значением

Потребители Поставщики					Запасы
Потребность

2)

Выбор ячейки с наименьшим значением

Потребители Поставщики					Запасы
		2| 15
Потребность

 

3)

Выбор ячейки с наименьшим значением

Потребители Поставщики					Запасы
		2| 15
	4|5
Потребность

4)

Выбор ячейки с наименьшим значением

Потребители Поставщики					Запасы
		2| 15
			9 | 15
	4 |5
Потребность

5)

 

Выбор ячейки с наименьшим значением

Потребители Поставщики					Запасы
		2| 15
			9 | 15
	4 |5			18 | 5
Потребность

 

6)

Должно быть базовых переменных

Есть только 5, поэтому выбираем любую

 

Потребители Поставщики					Запасы
		2| 15		11 | 0
			9 | 15	20 | 10
	4 |5			18 | 5
Потребность

 

 

Первое допустимое решение

, , , , ,

 

Значение функции цели

 

30 135 200 20 90