Транспортная модель открытого типа

 

Минимальный элемент матрицы тарифов находится в ячейке A1B1 и равен 1, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A1 к потребителю B1 наиболее рентабельный.

Запасы поставщика A1 составляют 120 единиц продукции. Потребность потребителя B1 составляет 225 единиц продукции.

От поставщика A1 к потребителю B1 будем доставлять min = (120 , 225) = 120 единиц продукции.

Разместим в ячейку A1B1 значение равное 120

Мы полностью израсходовали запасы поставщика A1. Вычеркиваем строку 1 таблицы, т.е исключаем ее из дальнейшего рассмотрения.

Минимальный элемент матрицы тарифов находится в ячейке A2B3 и равен 1, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A2 к потребителю B3 наиболее рентабельный.

Запасы поставщика A2 составляют 110 единиц продукции. Потребность потребителя B3 составляет 140 единиц продукции. От поставщика A2 к потребителю B3 будем доставлять min = (110 , 140) = 110 единиц продукции.

Разместим в ячейку A2B3 значение равное 110

Мы полностью израсходовали запасы поставщика A2. Вычеркиваем строку 2 таблицы, т.е исключаем ее из дальнейшего рассмотрения.

Минимальный элемент матрицы тарифов находится в ячейке A4B1 и равен 2, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A4 к потребителю B1 наиболее рентабельный.

Запасы поставщика A4 составляют 70 единиц продукции. Потребность потребителя B1 составляет 105 единиц продукции.

От поставщика A4 к потребителю B1 будем доставлять min = (70 , 105) = 70 единиц продукции.

Разместим в ячейку A4B1 значение равное 70

Мы полностью израсходовали запасы поставщика A4. Вычеркиваем строку 4 таблицы, т.е исключаем ее из дальнейшего рассмотрения.

Минимальный элемент матрицы тарифов находится в ячейке A3B2 и равен 4, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A3 к потребителю B2 наиболее рентабельный.

Запасы поставщика A3 составляют 20 единиц продукции. Потребность потребителя B2 составляет 135 единиц продукции.

От поставщика A3 к потребителю B2 будем доставлять min = (20 , 135) = 20 единиц продукции.

Разместим в ячейку A3B2 значение равное 20

Мы полностью израсходoвали запасы поставщика A3. Вычеркиваем строку 3 таблицы, т.е исключаем ее из дальнейшего рассмотрения.

Минимальный элемент матрицы тарифов находится в ячейке A5B1 и равен 0, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A5 к потребителю B1 наиболее рентабельный.

Запасы поставщика A5 составляют 180 единиц продукции. Потребность потребителя B1 составляет 35 единиц продукции.

От поставщика A5 к потребителю B1 будем доставлять min = (180 , 35) = 35 единиц продукции.

Разместим в ячейку A5B1 значение равное 35

Мы полностью удовлетворили потребность потребителя B1. Вычеркиваем столбец 1 таблицы, т.е исключаем его из дальнейшего рассмотрения.

Минимальный элемент матрицы тарифов находится в ячейке A5B2 и равен 0, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A5 к потребителю B2 наиболее рентабельный.

Запасы поставщика A5 составляют 145 единиц продукции. Потребность потребителя B2 составляет 115 единиц продукции. От поставщика A5 к потребителю B2 будем доставлять min = ( 145 , 115 ) = 115 единиц продукции.

Разместим в ячейку A5B2 значение равное 115

Мы полностью удовлетворили потребность потребителя B2. Вычеркиваем столбец 2 таблицы, т.е исключаем его из дальнейшего рассмотрения.

Минимальный элемент матрицы тарифов находится в ячейке A5B3 и равен 0, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A5 к потребителю B3 наиболее рентабельный.

Запасы поставщика A5 составляют 30 единиц продукции. Потребность потребителя B3 составляет 30 единиц продукции.

От поставщика A5 к потребителю B3 будем доставлять 30 единиц продукции.

Разместим в ячейку A5B3 значение равное 30

Мы полностью израсходoвали запасы поставщика A5. Вычеркиваем строку 5 таблицы, т.е исключаем ее из дальнейшего рассмотрения.

Заполненные нами ячейки будем называть базисными, остальные - свободными.

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

Количество базисных ячеек (задействованных маршрутов) равно 7, что и требовалось.

Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.

S0 = 1 * 120 + 1 * 110 + 4 * 20 + 2 * 70 + 0 * 35 + 0 * 115 + 0 * 30 = 450 ден. ед.

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

3. Построение опорного плана методом Фогеля

Согласно условию задачи построим опорный план методом Фогеля.

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

Поставщик	Потребитель						Δi
	B 1		B 2		B 3
A 1	-		-		-		1
		1		2		9
A 2	-		-		-		2
		3		4		1
A 3	-		-		-		2
		6		4		8
A 4	-		-		-		1
		2		3		3
A 5	-		-		-		-
		0		0		0

 

 

Поставщик	Потребитель
	B 1		B 2		B 3
A 1	-		-		-
		1		2		9
A 2	-		-		-
		3		4		1
A 3	-		-		-
		6		4		8
A 4	-		-		-
		2		3		3
A 5	-		-		-
		0		0		0
j	1		1		2

 

Из полученных разностей выберем наибольшую.

Наибольшей разностью обладает столбец 3. В данном столбце выберем ячейку A2B3, как обладающую наименьшим тарифом.

Стоимость доставки единицы продукции от поставщика A2 к потребителю B3, как минимум, на 2 ден.ед. меньше чем от остальных поставщиков к потребителю B3.

Запасы поставщика A2 составляют 110 единиц продукции. Потребность потребителя B3 составляет 140 единиц продукции. От поставщика A2 к потребителю B3 будем доставлять min = (110 , 140) = 110 единиц продукции.

Разместим в ячейку A2B3 значение равное 110

Мы полностью израсходoвали запасы поставщика A2. Вычеркиваем строку 2 таблицы, т.е исключаем ее из дальнейшего рассмотрения.

Наибольшей разностью обладает столбец 3. В данном столбце выберем ячейку A4B3, как обладающую наименьшим тарифом.

Стоимость доставки единицы продукции от поставщика A4 к потребителю B3, как минимум, на 5 ден.ед. меньше чем от остальных поставщиков к потребителю B3 (см. правую таблицу).

Запасы поставщика A4 составляют 70 единиц продукции. Потребность потребителя B3 составляет 30 единиц продукции.

От поставщика A4 к потребителю B3 будем доставлять min = (70 , 30) = 30 единиц продукции.

Разместим в ячейку A4B3 значение равное 30

Мы полностью удовлетворили потребность потребителя B3. Вычеркиваем столбец 3 таблицы, т.е исключаем его из дальнейшего рассмотрения.

Наибольшей разностью обладает строка 3. В данной строке выберем ячейку A3B2, как обладающую наименьшим тарифом.

Стоимость доставки единицы продукции от поставщика A3 к потребителю B2, как минимум, на 2 ден.ед. меньше чем к другим потребителям.

Запасы поставщика A3 составляют 20 единиц продукции. Потребность потребителя B2 составляет 135 единиц продукции.

От поставщика A3 к потребителю B2 будем доставлять min = (20 , 135) = 20 единиц продукции.

Разместим в ячейку A3B2 значение равное 20

Мы полностью израсходовали запасы поставщика A3. Вычеркиваем строку 3 таблицы, т.е исключаем ее из дальнейшего рассмотрения.

Запасы поставщика A5 составляют 115 единиц продукции. Потребность потребителя B2 составляет 115 единиц продукции. От поставщика A5 к потребителю B2 будем доставлять 115 единиц продукции.

Разместим в ячейку A5B2 значение равное 115

Мы полностью израсходовали запасы поставщика A5. Вычеркиваем строку 5 таблицы, т.е исключаем ее из дальнейшего рассмотрения.

Поставщик	Потребитель						Запас
	B 1		B 2		B 3
A 1	120		-		-		120
		1		2		9
A 2	-		-		110		110
		3		4		1
A 3	-		20		-		20
		6		4		8
A 4	40		-		30		70
		2		3		3
A 5	65		115		-		180
		0		0		0
Потребность	225		135		140

 

Заполненные нами ячейки будем называть базисными, остальные - свободными.

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

Количество базисных ячеек (задействованных маршрутов) равно 7, что и требовалось.

Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.

S0 = 1 * 120 + 1 * 110 + 4 * 20 + 2 * 40 + 3 * 30 + 0 * 65 + 0 * 115 = 480 ден. ед.

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

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

Перейдем к перепланировке перевозок методом потенциалов.

3. Оптимизация транспортной модели закрытого типа
1. Метод потенциалов на основе опорного плана, построенного методом северо-западного угла

Дальнейшие наши действия будут состоять из шагов, каждый из которых состоит в следующем:

•  Находим потенциалы поставщиков и потребителей для имеющегося решения.

•  Находим оценки свободных ячеек. Если все оценки окажутся неотрицательными - задача решена.

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

•  Находим новое решение, как минимум, не хуже предыдущего.

•  Вычисляем общую стоимость доставки всей продукции для нового решения.

Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика.

Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.

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

(ui + vj = cij, где cij - тариф клетки AiBj)

Поскольку, число базисных клеток - 7, а общее количество потенциалов равно 8, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.

Примем v2 = 0.

v2 + u2 = c22

v2 + u2 = 4

u2 = 4 - 0 = 4