ИДЗ №2_ТРАНСПОРТНАЯ ЗАДАЧА В КЛАССИЧЕСКОЙ ПОСТАНОВКЕ (1). Метод потенциалов решения транспортной задачи в классической постановке

• Название: Метод потенциалов решения транспортной задачи в классической постановке
• Дата: 15.04.2021
• Размер: 115.96 Kb.
• Имя файла: ИДЗ №2_ТРАНСПОРТНАЯ ЗАДАЧА В КЛАССИЧЕСКОЙ ПОСТАНОВКЕ (1).docx
• Тип: Документы; #195016
• страница: 2 из 6

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

Решение.

1. 
   Проверим задачу на замкнутость по следующей формуле:
   

(1)

В условии данной задачи Определим суммарный объем произведенного товара и суммарный объем спроса на товар, сравним полученные результаты.





Задача является замкнутой, т.к.

2. 
   Найдем начальное допустимое базисное решение (далее – НДБР) методом северо-западного угла.
   

	7			5			20			9
11
		7			4
			1			2			3			4
13
					1			12
			0			4			2			3
17
								8			9
			3			6			2			1

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

Для определения базисности найденного решения проверим количество перевозок, которых должно быть равно и построим граф перевозок, который должен быть деревом (рисунок 1).


Рисунок 1 – Граф перевозок начального решения
Граф перевозок является деревом, количество введенных перевозок в НДБР равно 6, что означает, что найденное начальное решение не только допустимое, но и базисное.

3. 
   Решим задачу методом потенциалов
   

Для начала определим стоимость перевозки товара начального допустимого базисного решения:



Далее для проверки решения на оптимальность введем потенциалы производителей ( и потенциалы потребителей однородного товара ( ), полагая, что (таблица 2).

В соответствии с критерием оптимальности: , определим оптимальность найденного решения. Рассчитаем оценку каждой коммуникации по формуле: . Найденные оценки расположим в левом верхнем углу каждой клетки, соответствующей конкретной коммуникации (таблица 2).

Таблица 2 - Итерация №1

	7			5			20			9
11	0			0			3			5
		7			4
			1			2			3			4
13	-3			0			0			2
					1			12
			0			4			2			3
17	0			2			0			0
								8			9
			3			6			2			1