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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

В m пунктах отправления сосредоточен однородный груз в количестве А₁, А₂, А₃, А₄ единиц. Необходимо этот продукт распределить по n потребителям в количестве В₁, В₂, В₃ В₄ единиц, при условии получения минимальных затрат на перевозку (Таблица 1)

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

Заводы и их мощности, тыс. т	Потребители и их спрос, тыс. т
	В1 = 300	В2 = 541	В3 = 900	В4 = 211
А1 = 234	1	2	3	4
А2 = 352	5	6	7	8
А3 = 666	9	1	2	3
А4 = 700	4	5	6	7

Решение

Число пунктов отправления m=4, а число пунктов назначения n=4. Следовательно опорный план задачи определяется числами, стоящими в m+n?1=4+4?1=7 заполненных клетках таблицы 2.

Таблица 2

Пункты отправления	Пункты назначения	Запасы
	B1	B2	B3	B4
A1	1	2	3	4	234
A2	5	6	7	8	352
A3	9	1	2	3	666
A4	4	5	6	7	700
Потребности	300	541	900	211	0

Тарифы перевозок единицы груза из каждого пункта отправления во все пункты назначения задаются матрицей

C=		1	2	3	4
		5	6	7	8
		9	1	2	3
		4	5	6	7

Наличие груза у поставщиков равно:

? Ai=	234	+	352	+	666	+	700	=	1952

Общая потребность в грузе в пунктах назначения равна:

? Bi=	300	+	541	+	900	+	211	=	1952

? A_i=? B_i

Модель транспортной задачи является закрытой. Следовательно, она разрешима.

1. Решение транспортной задачи методом дифференциальных рент

Этап1:

В каждом из столбцов таблицы находим минимальные тарифы и заключаем в рамки. Если в каком-либо столбце окажется несколько одинаковых минимальных тарифов, то выбираем какой-нибудь из них, причем неважно какой. Заполняем клетки, в которых стоят указанные числа. Сначала находим те столбцы (строки) в которых есть только одна клетка для заполнения. Заполнив ее, исключаем из рассмотрения данный столбец (строку) и переходим к заполнению следующей клетки (таблица 3).

Последовательность заполнения клеток следующее: A₁B₁, A₃B₂, A₃B₃, A₃B₄,

Таблица 3

В результате заполнения отмеченных клеток получен условно оптимальный план.

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

Строка A₁ является недостаточной, поскольку запасы пункта отправления A₁ распределены полностью, а потребности пункта назначения B₁ удовлетворены частично. При этом величина недостатка равна 66.

Строка A₃ является недостаточной, поскольку запасы пункта отправления A₃ распределены полностью, а потребности пунктов назначения B₃, B₄, удовлетворены частично. При этом величина недостатка равна 986.

Строка A₂ является избыточной, поскольку запасы пункта отправления A₂ распределены не полностью. При этом величина избытка этой строки равна 352.

Строка A₄ является избыточной, поскольку запасы пункта отправления A₄ распределены не полностью. При этом величина избытка этой строки равна 700.

Таблица 4

Нераспределенный остаток равен 1052.

Суммарный объем поставок равен 900.

После определения избыточных и недостаточных строк, по каждому из столбцов находим разности между минимальными тарифами, записанными в избыточных строках, и тарифами, стоящими в заполненных клетках (Таблица 5).

В столбце 1 минимальный тариф в избыточных строках равно 4 а число стоящее в рамке равно 1. Cледовательно, разность для данного столбца равна 4?1=3.

В столбце 2 минимальный тариф в избыточных строках равно 5 а число стоящее в рамке равно 1. Cледовательно, разность для данного столбца равна 5?1=4.

В столбце 3 минимальный тариф в избыточных строках равно 6 а число стоящее в рамке равно 2. Cледовательно, разность для данного столбца равна 6?2=4.

В столбце 4 минимальный тариф в избыточных строках равно 7 а число стоящее в рамке равно 3. Cледовательно, разность для данного столбца равна 7?3=4.

Таблица 5

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

Этап 2:

В каждом из столбцов таблицы находим минимальные тарифы и заключаем в рамки. Заполняем клетки, в которых стоят указанные числа. Сначала находим те столбцы (строки) в которых есть только одна клетка для заполнения. Заполнив ее, исключаем из рассмотрения данный столбец (строку) и переходим к заполнению следующей клетки.

Последовательность заполнения клеток следующее: A₃B₂, A₃B₃, A₃B₄, A₁B₁, A₄B₁,



В результате заполнения отмеченных клеток получен условно оптимальный план.

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

Строка A₃ является недостаточной, поскольку запасы пункта отправления A₃ распределены полностью, а потребности пунктов назначения B₃, B₄, удовлетворены частично. При этом величина недостатка равна 986.

Строка A₂ является избыточным, поскольку запасы пункта отправления A₂ распределены не полностью. При этом величина избытка этой строки равна 352.

Строка A₄ является избыточным, поскольку запасы пункта отправления A₄ распределены не полностью. При этом величина избытка этой строки равна 634.



Нераспределенный остаток равен 986.

Суммарный объем поставок равен 966.

Определяем положительность или отрицательность нулевой строки A₁. Для этого запасы этой строки увеличиваем на 1 и снова заполняем таблицу. Если суммарный объем поставок не изменится, то строка положительная, в противном случае ? отрицательная.

Последовательность заполнения клеток следующее: A₃B₂, A₃B₃, A₃B₄, A₁B₁, A₄B₁

Суммарный объем поставок не изменился (966).

Следовательно, строка A1 избыточна (положительна).

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

Для столбца 1 разность не определена, так как число, записанное в рамке, в данном столбце, находится в положительной строке.

В столбце 2 минимальный тариф в избыточных строках равно 5 а число стоящее в рамке равно 4. Cледовательно, разность для данного столбца равна 5?4=1.

В столбце 3 минимальный тариф в избыточных строках равно 6 а число стоящее в рамке равно 5. Cледовательно, разность для данного столбца равна 6?5=1.

В столбце 4 минимальный тариф в избыточных строках равно 7 а число стоящее в рамке равно 6. Следовательно, разность для данного столбца равна 7?6=1.



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

В данном случае промежуточная рента равна 1 и находится в столбце B2. Далее переходим к следующей таблице. В этой таблице в строках (являющихся избыточными) переписываем соответствующие тарифы из предыдущей таблицы, а тарифы недостаточных строках получаются в результате прибавления к ним величину промежуточной ренты, т.е. 1.

Этап 3:

В каждом из столбцов таблицы находим минимальные тарифы и заключаем в рамки. Заполняем клетки, в которых стоят указанные числа. Сначала находим те столбцы (строки) в которых есть только одна клетка для заполнения. Заполнив ее, исключаем из рассмотрения данный столбец (строку) и переходим к заполнению следующей клетки.

Последовательность заполнения клеток следующее:

A1B1, A4B1, A1B2, A1B3, A1B4, A3B2, A4B2, A3B3, A4B3, A3B4, A4B4,



В результате заполнения отмеченных клеток получен условно оптимальный план.

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

Строка A1 является недостаточной, поскольку запасы пункта отправления A1 распределены полностью, а потребности пунктов назначения B3, B4, удовлетворены частично. При этом величина недостатка равна 352.

Строка A2 является избыточным, поскольку запасы пункта отправления A2 распределены не полностью. При этом величина избытка этой строки равна 352.



Нераспределенный остаток равен 352.

Суммарный объем поставок равен 1600.

Определяем положительность или отрицательность нулевой строки A3. Для этого запасы этой строки увеличиваем на 1 и снова заполняем таблицу. Если суммарный объем поставок не изменится, то строка положительная, в противном случае ? отрицательная.

Последовательность заполнения клеток следующее:

A1B1, A4B1, A1B2, A1B3, A1B4, A3B2, A4B2, A3B3, A4B3, A3B4, A4B4,



Суммарный объем поставок изменился (1600).

Следовательно, строка A3 недостаточна (отрицательна).

Определяем положительность или отрицательность нулевой строки A4. Для этого запасы этой строки увеличиваем на 1 и снова заполняем таблицу. Если суммарный объем поставок не изменится, то строка положительная, в противном случае ? отрицательная.

Последовательность заполнения клеток следующее: A1B1, A4B1, A1B2, A1B3, A1B4, A3B2, A4B2, A3B3, A4B3, A3B4, A4B4,

Суммарный объем поставок изменился (1600).

Следовательно, строка A4 недостаточна (отрицательна).

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

В столбце 1 минимальный тариф в избыточных строках равно 5 а число стоящее в рамке равно 4. Cледовательно, разность для данного столбца равна 5?4=1.

В столбце 2 минимальный тариф в избыточных строках равно 6 а число стоящее в рамке равно 5. Cледовательно, разность для данного столбца равна 6?5=1.

В столбце 3 минимальный тариф в избыточных строках равно 7 а число стоящее в рамке равно 6. Cледовательно, разность для данного столбца равна 7?6=1.

В столбце 4 минимальный тариф в избыточных строках равно 8 а число стоящее в рамке равно 7. Cледовательно, разность для данного столбца равна 8?7=1.

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

В данном случае промежуточная рента равна 1 и находится в столбце B1. Далее переходим к следующей таблице. В этой таблице в строках (являющихся избыточными) переписываем соответствующие тарифы из предыдущей таблицы, а тарифы недостаточных строках получаются в результате прибавления к ним величину промежуточной ренты, т.е. 1.

Этап 4:

В каждом из столбцов таблицы находим минимальные тарифы и заключаем в рамки. Заполняем клетки, в которых стоят указанные числа. Сначала находим те столбцы (строки) в которых есть только одна клетка для заполнения. Заполнив ее, исключаем из рассмотрения данный столбец (строку) и переходим к заполнению следующей клетки.

Последовательность заполнения клеток следующее: A1B1, A1B2, A1B3, A1B4, A2B1, A4B1, A2B2, A2B3, A2B4, A3B2, A4B2, A3B3, A4B3, A3B4, A4B4,

В результате заполнения отмеченных клеток получен условно оптимальный план.

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

Нераспределенный остаток равен 0.

Суммарный объем поставок равен 1952.

Все имеющие запасы распределены в соответствии с фактическими потребностями пунктов назначения.

Следовательно, получен оптимальный план:

X=		234	0	0	0
		66	286	0	0
		0	255	411	0
		0	0	489	211

При этом плане стоимость перевозок вычисляется так:

S=1*234+2*0+3*0+4*0+5*66+6*286+7*0+8*0+1*255+2*411+3*0+4*0+5*0+6*489+7*211, и составляет 7768 тыс. руб.

2. Решение транспортной задачи методом Северо-Западного угла

транспортный доставка рента запас

Требуется составить план перевозок, при котором общая стоимость доставки продукции будет наименьшей.

Тарифы перевозок представлены матрицей:

C=		1	2	3	4
		5	6	7	8
		9	1	2	3
		4	5	6	7

Данные условия

Пункты отправления	Пункты назначения	Запасы
	B1	B2	B3	B4
A1	1	2	3	4	234
A2	5	6	7	8	352
A3	9	1	2	3	666
A4	4	5	6	7	700
Потребности	300	541	900	211	0

Число пунктов отправления m=4, число пунктов назначения n=4.

транспортный доставка рента запас

m + n - 1 = К_з, где

m - количество потребителей;

n - количество поставщиков;

К_з - количество заполненных клеток.

Следовательно, опорный план задачи определяется числами, стоящими в

К_з = 4 + 4 - 1 = 7 заполненных клетках таблицы. Поэтому если возникнет ситуация, в которой будет необходимо исключить столбец и строку одновременно, мы исключим что-то одно.

Наличие груза у поставщиков равно: ?Ai=234+352+666+700=1952.

Общая потребность в грузе в пунктах назначения равна: ?Bj=300+541+900+211=1952.

?Ai=?Bj.

Модель транспортной задачи является закрытой. Следовательно она разрешима.

Решение:

Начинаем заполнять таблицу от левого верхнего угла и постепенно «двигаемся» к правому нижнему. От северо-запада к юго-востоку.

Поставщик	Потребитель	Запас
	B 1	B 2	B 3	B 4
A 1	1	2	3	4	234
A 2	5	6	7	8	352
A 3	9	1	2	3	666
A 4	4	5	6	7	700
Потребность	300	541	900	211

234 = min {300, 234}

Поставщик	Потребитель	Запас
	B 1	B 2	B 3	B 4
A 1	234 1	2	3	4	234 нет
A 2	5	6	7	8	352
A 3	9	1	2	3	666
A 4	4	5	6	7	700
Потребность	300 66	541	900	211

66 = min {66, 352}

Поставщик	Потребитель	Запас
	B 1	B 2	B 3	B 4
A 1	234 1	2	3	4	234 нет
A 2	66 5	6	7	8	352 286
A 3	9	1	2	3	666
A 4	4	5	6	7	700
Потребность	300 66 нет	541	900	211

286 = min {541, 286}

Поставщик	Потребитель	Запас
	B 1	B 2	B 3	B 4
A 1	234 1	2	3	4	234 нет
A 2	66 5	286 6	7	8	352 286 нет
A 3	9	1	2	3	666
A 4	4	5	6	7	700
Потребность	300 66 нет	541 255	900	211

255 = min {255, 666}

Поставщик	Потребитель	Запас
	B 1	B 2	B 3	B 4
A 1	234 1	2	3	4	234 нет
A 2	66 5	286 6	7	8	352 286 нет
A 3	9	255 1	2	3	666 411
A 4	4	5	6	7	700
Потребность	300 66 нет	541 255 нет	900	211

411 = min {900, 411}

Поставщик	Потребитель	Запас
	B 1	B 2	B 3	B 4
A 1	234 1	2	3	4	234 нет
A 2	66 5	286 6	7	8	352 286 нет
A 3	9	255 1	411 2	3	666 411 нет
A 4	4	5	6	7	700
Потребность	300 66 нет	541 255 нет	900 489	211

489 = min {489, 700}

Поставщик	Потребитель	Запас
	B 1	B 2	B 3	B 4
A 1	234 1	2	3	4	234 нет
A 2	66 5	286 6	7	8	352 286 нет
A 3	9	255 1	411 2	3	666 411 нет
A 4	4	5	489 6	7	700 211
Потребность	300 66 нет	541 255 нет	900 489 нет	211

211 = min {211, 211}

Поставщик	Потребитель	Запас
	B 1	B 2	B 3	B 4
A 1	234 1	2	3	4	234 нет
A 2	66 5	286 6	7	8	352 286 нет
A 3	9	255 1	411 2	3	666 411 нет
A 4	4	5	489 6	211 7	700 211 нет
Потребность	300 66 нет	541 255 нет	900 489 нет	211 нет

Стоимость доставки продукции, для начального решения, не сложно посчитать.

234*1 + 66*5 + 286*6 + 255*1 + 411*2 + 489*6 + 211*7 = 7768 тыс. руб.

Проверим.

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

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

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

Значение одного потенциала необходимо задать.

Пусть u₂ = 0.

Последовательно найдем значения потенциалов.



A2B1: v1 + u2 = 5 v1 = 5 - 0 = 5 A2B2: v2 + u2 = 6 v2 = 6 - 0 = 6 A3B2: v2 + u3 = 1 u3 = 1 - 6 = -5 A3B3: v3 + u3 = 2 v3 = 2 - (-5) = 7 A4B3: v3 + u4 = 6 u4 = 6 - 7 = -1 A4B4: v4 + u4 = 7 v4 = 7 - (-1) = 8 A1B1: v1 + u1 = 1 u1 = 1 - 5 = -4 Найдем оценки незадействованных маршрутов. A1B2: Д12 = c12 - (u1 + v2) = 2 - (-4 + 6) = 0 A1B3: Д13 = c13 - (u1 + v3) = 3 - (-4 + 7) = 0 A1B4: Д14 = c14 - (u1 + v4) = 4 - (-4 + 8) = 0 A2B3: Д23 = c23 - (u2 + v3) = 7 - (0 + 7) = 0 A2B4: Д24 = c24 - (u2 + v4) = 8 - (0 + 8) = 0 A3B1: Д31 = c31 - (u3 + v1) = 9 - (-5 + 5) = 9 A3B4: Д34 = c34 - (u3 + v4) = 3 - (-5 + 8) = 0 A4B1: Д41 = c41 - (u4 + v1) = 4 - (-1 + 5) = 0 A4B2: Д42 = c42 - (u4 + v2) = 5 - (-1 + 6) = 0	Поставщик Потребитель U B 1 B 2 B 3 B 4 A 1 234 1 2 3 4 u1 = -4 A 2 66 5 286 6 7 8 u2 = 0 A 3 9 255 1 411 2 3 u3 = -5 A 4 4 5 489 6 211 7 u4 = -1 V v1 = 5 v2 = 6 v3 = 7 v4 = 8

Нет отрицательных оценок, следовательно, уменьшить общую стоимость доставки продукции невозможно.

Ответ:

X опт =		234	0	0	0
		66	286	0	0
		0	255	411	0
		0	0	489	211

S_min = 234*1 + 66*5 + 286*6 + 255*1 + 411*2 + 489*6 + 211*7 = 7768 тыс. руб.

3. Линейный метод решения транспортной задачи в среде MS Excel

Для решения транспортной задачи создадим таблицу-матрицу, в которой укажем исходные данные (Таблица 12)

Таблица 12

	потребитель ->	1 пункт	2 пункт	3 пункт	4 пункт
поставщик
Склад №1	4	1	1	1	1
Склад №2	4	1	1	1	1
Склад №3	4	1	1	1	1
Склад №4	4	1	1	1	1
	факт ->	4	4	4	4
	запросы ->	300	541	900	211
Склад №1	234	1	2	3	4
Склад №2	352	5	6	7	8
Склад №3	666	9	1	2	3
Склад №4	700	4	5	6	7
ВСЕГО	73	19	14	18	22

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

Таблица 13

	потребитель ->	1 пункт	2 пункт	3 пункт	4 пункт
поставщик
Склад №1	234	0	0	23	211
Склад №2	352	0	0	352	0
Склад №3	666	0	141	525	0
Склад №4	700	300	400	0	0
	факт ->	300	541	900	211
	запросы ->	300	541	900	211
Склад №1	234	1	2	3	4
Склад №2	352	5	6	7	8
Склад №3	666	9	1	2	3
Склад №4	700	4	5	6	7
ВСЕГО	7768	1200	2141	3583	844

Образец построения таблицы и расчета в EXCEL (Рисунок 1):

Размещено на Allbest.ru