Решение транспортной задачи

Имеется 3 поставщика и 3 потребителя. Ресурсы 1-го поставщика составляют 10 ед., 2-го – 8, 3-го – 13. Потребности потребителя А составляют 6 ед., Б – 14 ед., В – 11 ед. Транспортная задача закрытая.

Издержки на транспортировку единицы груза с учетом расстояния между поставщиками и потребителями приведены в таблице 10.

Таблица 10 - Издержки на транспортировку единицы груза

от поставщиков к потребителю

Поставщики	Потребители
А	Б	В

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

Сформируем задачу линейного программирования:

Х₁₁ – объем перевозки грузов от 1-го поставщика в потребителю А,

…

Х_ij – объем перевозки груза от i- го поставщика к потребителю j,

…

Х₃₃ – объем перевозки от 3-го поставщика к потребителю В.

Ограничения по объемам поставки:

1-го поставщика: Х₁₁ + Х₁₂ + Х₁₃ = 10

2-го поставщика: Х ₂₁ + Х₂₂ + Х₂₃ = 8

3-го поставщика: Х₃₁ + Х₃₂ + Х₃₃ = 13

Ограничения по потребностям:

Потребителя А: Х₁₁ + Х₂₁ + Х₃₁ = 6

Потребителя Б: Х₁₂ + Х₂₂ + Х₃₂ = 8

Потребителя В: Х₁₃ + Х₂₃ + Х₃₃ = 13

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

С (min) = 4 Х₁₁ + 5Х₁₂ + 4Х₁₃ + 2Х₂₁ + 3Х₂₂ + 6Х₂₃ + Х₃₁ + 2Х₃₂ + 4Х₃₃

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

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

Алгоритм метода северо-западного угла 1.Выбирается левая верхняя клетка таблицы. 2.В эту клетку записывается базисная переменная: a)Сравниваем ресурсы (а₁) и потребности (b₁). Если а₁>b₁, то Х₁₁ = b₁ и клетка объявляется базисной. В клетку записывается Х₁₁. Подсчитывается новый ресурс: =а₁–b₁ из таблицы исключается первый столбец. Делается переход к п. 1 для новой таблицы (без исключенного столбца). b)Если а₁<b₁, то Х₁₁ = а₁. Подсчитывается новая потребность =b₁ – а₁. Из таблицы исключается первая строка. Переход к п. 1 для новой таблицы (без исключенной строки). c)Если а₁ = b₁, то Х₁₁ = а₁ = b₁. Подсчитывается = 0 (или =0). Из таблицы исключается столбец или строка (условно можно принять исключение строки). Переход к п. 1 новой таблицы (без строки).

Использование метода северо-западного угла позволило получить первоначальный план перевозки грузов (табл. 11).

Таблица 11 - Первоначальный план перевозки грузов

по методу северо-западного угла

Поставщики	Потребители	ui
А	Б	В
6 х	14 10 2 х	11х
	10 4 х	4)	5)
	8 х		3)		-2
	13 11 х		2)	4)	-3
vj

Клетки 1–А, 1-Б, 2-Б, 3-Б, 3-В занятые, остальные – свободные.

С₁ = 46 + 54 + 38 + 22 +411=116

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

Таблица 12 – Первоначальное решение транспортной задачи,

построенное методом минимального элемента

в таблице

Поставщики	Потребители	ui
А	Б	В
6х	147 х	111 х
	10 х			4)
	8 1 х		3) + 7	6) - 1
	137 х	1)	2) - 7	4 +
vj

Клетка 1-В, 2-Б, 2-В, 3-А, 3-Б – занятые (базисные), остальные – свободные (небазисные).

С₁= 410+37+61+16+27=87

Значение целевой функции в этом варианте на 29 руб. меньше, чем в случае использования метода северо-западного угла.

Необходимо проверить, является ли данный план оптимальным? Если план не оптимален, то его следует улучшить.

Оптимальность плана устанавливают при помощи метода потенциалов. Этот метод позволяет также улучшить план.

Алгоритм метода потенциалов 0)Записывается исходное опорное решение. 1)Определяются потенциалы строчек (u_i) и столбцов (v_j). Обычно u₁=0. Остальные рассчитываются по формуле: c_ij = u_i + v_j, где c_ij – издержки на перевозку единицы груза в занятых клетках. 2)Вычисляются характеристики свободных клеток: _ij = c_ij – (v_j + u_i) 3)Если все характеристики неотрицательны, то при решении задачи на минимум получено оптимальное решение. Если же имеется хотя бы одна отрицательная оценка, то это обозначает, что составленный план не оптимален и его можно улучшить. 4)Выбирается наименьшая характеристика. По контуру свободной клетки с этой характеристикой производится преобразование однократного замещения (ПОЗ). Осуществляется переход к п. 1.

Характеристики указывают на величину экономии (по сравнению с составленным планом), которую можно получить при улучшении плана, связанного с введением в клетку (i,j) единицы перевозки груза.

Клетку 3-В следует ввести в базис. Для нее необходимо провести ПОЗ.

Построим для нее замкнутый прямоугольный контур.

Правила построения контура 1. Одна вершина контура должна лежать в свободной клетке, а остальные – в занятых клетках. 2. Звенья контура должны располагаться только по строкам и столбцам таблицы. Для каждой свободной клетки можно построить единственный контур. Число вершин всегда четное. 3. Вершины контура размечают чередующимися знаками «+» и «-», начиная с той вершины, которая лежит в свободной клетке. Этой вершине присваивают знак «+».

Далее производится улучшение плана.

Алгоритм улучшения плана (ПОЗ): 1. Из всех вершин прямоугольного контура, помеченных знаком «-», выбирают ту, в которой записан минимальный объем грузоперевозок. 2. Этот объем грузоперевозок последовательно вычитают из всех объемов, расположенных в отрицательные вершинах контура, и прибавляют ко всем объемам грузов в положительных вершинах контура.

В результате выполнения указанного алгоритма клетка с минимальным объемом груза становится свободной, т. е. выводится из базиса, а выбранная клетка – заполненной, т. е. вводится в базис (табл. 13).

Таблица 13 - Вторая таблица транспортной задачи

Поставщики	Потребители	ui
А	Б	В
				4)
		+	3) - 8
		1) - 6	2) + 6	4)
vj

С₂ = 4×10 + 3×8 + 1×6+2×6 + 4× 1 = 86

₁₁=4 – (1+0)=3 ₂₁ = 2 – (1 + 1) = 0

₁₂ = 5 – (0 + 2) = 3 ₂₃ = 6 – (1 + 4) = 1

Решение оптимально, поскольку все оценки неотрицательны. Поскольку имеется нулевая оценка (₂₁=0), то имеется еще одно альтернативное оптимальное решение. Для его нахождения в базис вводят клетку с нулевой оценкой (табл. 14).

Таблица 14 – Таблица транспортной задачи с альтернативным

оптимальным решением

Поставщики	Потребители	ui
А	Б	В
				4)
		2)	3)
			2)	4)
vj

С₄ = 4×10 + 2×6 + 3×2 + 2×12 + 4×1 = 86

₁₁ = 4 – (1 + 0) = 3 ₁₂ = 5 – (2 + 0) = 3

₃₁ = 1 – (1 + 0) = 0 ₂₃ = 6 – (4 + 1) = 1

От этого оптимального решение можно снова вернуться к предыдущему.

Дата добавления: 2014-01-05