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

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

На коммуникации (2;1) условие оптимальности решения не выполняется. Это означает, что найденное решение не оптимально. Невязка равна -3.

Введем на этой коммуникации перевозку. Граф перевозок сразу станет цикличным (рисунок 2). Отметим цикл и перераспределим минимально возможный объем товара по клеткам цикла (таблица 3).



Рисунок 2 – Граф перевозок итерации №1 с циклом

Будем именовать клетки цикла всегда начиная с номера производителя. Цикл в итерации №1 будет следующим: (2;1) – (1;1) – (1;2) – (2;2).

Таблица 3 – Цикл графа перевозок в итерации №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

Перераспределим по клеткам цикла 1 ед. товара для получения нового допустимого решения. Определим для нового решения потенциалы производителей и потребителей (таблица 4).

Таблица 4 – Допустимое базисное решение итерации №2

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