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

Министерство образования и науки Российской Федерации

(МИНОБРНАУКИ РОССИИ)

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ УПРАВЛЕНИЯ»

Институт информационных систем управления

Кафедра математических методов в управлении

по дисциплине: «Методы оптимальных решений»

ДОМАШНЯЯ РАБОТА №2

Вариант 20

на тему: «Транспортная задача»

Москва 2014 год

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

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

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

Таблица 1. Исходные данные

В правом столбце записаны компоненты вектора a. Каждая i – я компонента его равна максимальному количеству единиц продукта (максимальному предложению), которое может отправить i -й поставщик.

В верхней строке находятся компоненты вектора b. Каждая j – я компонента его равна минимальному количеству единиц продукта (максимальному спросу), которое должен получить j -й потребитель.

В остальных местах таблицы 1 находятся элементы матрицы С удельных затрат на транспортировку продукта размера .

В матричном виде:

Общий объем производства больше, чем требуется всем потребителям , т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 116 -104 = 12 единиц, причем тарифы на перевозку в этот пункт условимся считать равными нулю, помня, что переменные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами.

Первое базисное допустимое решение, построенное по правилу «северо-западного угла», которое состоит в том, чтобы на каждом этапе мы максимально загружали «северо-западную клеточку».

Таблица 2. Первое базисное допустимое решение

			18		+	2
			+ 10	16	12	-2
	7	7	3	4	2

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

Имеем:

Затем по формуле вычисляем оценки всех свободных клеток:

Находим наибольшую положительную оценку:

Для найденной свободной клетки (2, 5) строим цикл пересчета – замкнутую ломаную линию. Это будет цикл с вершинами в клетках (2, 5), (2, 3), (3, 3), (3, 5). Ниже, на схеме выделены только вершинные клетки цикла пересчета.

Таблица 3. Второе базисное допустимое решение

		3	+
		+18	6			2
						-2
	7	7	3	4	- 2

Имеем:

Затем по формуле вычисляем оценки всех свободных клеток:

Находим наибольшую положительную оценку:

Для найденной свободной клетки (1, 3) строим цикл пересчета. Это будет цикл с вершинами в клетках (1, 3), (1, 2), (2, 2), (2, 3).

	6

Таблица 4. Третье базисное допустимое решение

	39		+ 3
	+		3			3
						-1
	7	6	2	3	- 3

Следующим шагом является нахождение потенциалов:

Оценки для свободных клеток:

Наибольшая положительная оценка:

Для найденной свободной клетки (2, 1) строим цикл пересчета. Это будет цикл с вершинами в клетках (2, 1), (2, 3), (1, 3), (1, 1).

	3

Таблица 5. Четвертое базисное допустимое решение

	36	+
	+ 3	21				1
						-1
	7	8	2	3	- 1

Находим потенциалы:

Далее находим оценки свободных клеток.

Наибольшая положительная оценка:

Для найденной свободной клетки (1, 2) строим цикл пересчета. Это будет цикл с вершинами в клетках (1, 2), (1, 1), (2, 1), (2, 2).

Таблица 6. Пятое базисное допустимое решение

		21
						1
						-1
	7	7	2	3	- 1

Имеем:

Оценки свободных клеток:

Опорный план является оптимальным, так как все оценки свободных клеток

Итак, оптимальное базисное допустимое решение

2. Решение задачи с помощью инструмента «Поиск решения» программного продукта Microsoft Excel.