Решение транспортных задач методами линейного программирования

Национальный Технический Университет Украины «КПИ»

 

 

 

 

 

 

 

 

Реферат

Тема:    РЕШЕНИЕ ТРАНСПОРТНЫХ ЗАДАЧ МЕТОДАМИ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ.

 

Часть II (примеры)

 

 

 

 

 

Выполнил:  Дрюк Я.А. 

 

 

Проверил: Яганов П.О.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

КИЕВ 2001

ОГЛАВЛЕНИЕ

 

Пример  № 1.

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

 На 4 станциях  имеется избыток пустых вагонов  в размере соответственно 100, 120, 150 и 50 вагонов. Необходимо распределить  данные вагоны по 7 станциям с  недостатком порожняка (соответственно 70, 50, 60, 30, 50, 70 и 90 вагонов). Расстояние между каждой станцией отправления (избытка вагонов) и каждой станцией назначения (недостатка порожняка) представлено в виде матрицы (табл.1). Необходимо составить план распределения вагонов между указанными станциями с минимальным суммарным пробегом пустых вагонов.

Таблица 1

Исходные данные транспортной задачи

Станция отправления	Избыток пустых вагонов	Станция назначения
		5	6	7	8	9	10	11
		Недостаток  пустых вагонов
		70	50	60	30	50	70	90
1	100	15	23	28	13	12	16	21
		X1,5	X1,6	X1,7	X1,8	X1,9	X1,10	X1,11
2	120	24	17	24	11	11	12	18
		X2,5	X2,6	X2,7	X2,8	X2,9	X2,10	X2,11
3	150	8	19	16	18	9	17	15
		X3,5	X3,6	X3,7	X3,8	X3,9	X3,10	X3,11
4	50	12	28	18	16	21	20	25
		X4,5	X4,6	X4,7	X4,8	X4,9	X4,10	X4,11

Разработка  плана перевозок означает, что  необходимо указать, сколько пустых вагонов каждая станция отправления  должна отправить в адрес каждой станции назначения. В верхних  левых углах каждой клетки вышеприведенной  таблицы указано расстояние перевозки  вагонов (или другой показатель критерия оптимизации) c_ij, в нижних правых углах – количество вагонов x_ij.

Это задача закрытого  типа, так как суммарное количество избыточных пустых вагонов равно  суммарному количеству требующихся  вагонов (420 = 420).

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

Целевая функция (суммарный пробег пустых вагонов) определяется по формуле:

 

 

 

 

 

 

 

Система ограничений

где a_i – ресурсы i-й станции отправления; b_j – потребность j-й станции назначения.

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

Методы построения исходного опорного плана перевозок

Исходный опорный  план перевозок может быть построен различными методами. Здесь приводятся наиболее распространенные из них.

Метод северо-западного  угла (диагональный). Построение начального опорного плана начинается с левой  верхней клетки (называемой северо-западным углом) матрицы и продолжается, двигаясь далее вправо по строке и вниз по столбцу (табл. 2).

Таблица 2

Исходный опорный  план, построенный методом северо-западного  угла

Станция отправления	Избыток пустых вагонов	Станция назначения
		5	6	7	8	9	10	11
		Недостаток  пустых вагонов
		70	50	60	30	50	70	90
1	100	15 70	23 30	28	13	12	16	21
2	120	24	17 20	24 60	11 30	11 10	12	18
3	150	8	19	16	18	9 40	17 70	15 40
4	50	12	28	18	16	21	20	25 50

Значение целевой  функции составит

L = 15·70 + 23 · 30 + 17· 20 + 24 · 60 + 11 · 30 + 11 · 10 + 9 · 40 + 17 · 70 + 15 · 40 +  25· 50 = = 7360 ваг-км

Метод минимального элемента. Построение начального опорного плана начинается с клетки, имеющей  минимальное расстояние перевозки  в таблице. Эта клетка исключается  из дальнейшего рассмотрения матрицы, потом заполняется клетка с очередным  минимальным элементом и т.д. (табл. 3).

Таблица 3

Исходный опорный  план, построенный методом “минимального  элемента”

Станция отправления	Избыток пустых вагонов	Станция назначения
		5	6	7	8	9	10	11
		Недостаток  пустых вагонов
		70	50	60	30	50	70	90
1	100	15	23 30	28 10	13	12	16	21 60
2	120	24	17 20	24	11 30	11	12 70	18
3	150	8 70	19	16	18	9 50	17	15 30
4	50	12	28	18 50	16	21	20	25

Значение целевой  функции составит

L = 23 · 30 + 28· 10 + 21· 60 + 17· 20 + 11· 30 + 12· 70 + 8 · 70 + 9· 50 + 15· 30 +  18· 50 = 6100 ваг-км.

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

Таблица 4

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

Станция отправления	Избыток пустых вагонов	Станция назначения
		5	6	7	8	9	10	11
		Недостаток  пустых вагонов
		70	50	60	30	50	70	90
1	100	15	23	28	13	12	16 60	21 40
2	120	24	17 50	24	11 30	11 30	12 10	18
3	150	8 70	19	16 60	18	9 20	17	15
4	50	12	28	18	16	21	20	25 50

 
Значение целевой функции составит

L = 16· 60 + 21· 40 + 17· 50 + 11· 30 + 11· 30 + 12· 10 + 8· 70 + 16·  60 + 9· 20 +  25· 50 = 6380 ваг-км.

Метод наименьшего критерия в строке. Построение начального опорного плана начинается с клетки с минимальным расстоянием перевозки в строке и далее по строке (табл. 5).

Таблица 5

Исходный опорный план, построенный методом наименьшего  критерия в строке

Станция отправления	Избыток пустых вагонов	Станция назначения
		5	6	7	8	9	10	11
		Недостаток  пустых вагонов
		70	50	60	30	50	70	90
1	100	15 20	23	28	13 30	12 50	16	21
2	120	24	17 50	24	11	11	12 70	18
3	150	8 50	19	16 10	18	9	17	15 90
4	50	12	28	18 50	16	21	20	25

Значение целевой  функции составит

L = 15· 20 + 13· 30 + 12· 50 + 17· 50 + 12· 70 + 8· 50 + 16· 10 +15· 90 + 18· 50 =  5790 ваг-км.

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

Таблица 6

Исходный опорный план, построенный методом двойного предпочтения

Станция отправления	Избыток пустых вагонов	Станция назначения
		5	6	7	8	9	10	11
		Недостаток  пустых вагонов
		70	50	60	30	50	70	90
1	100	15	23 30	28 10	13	12 *	16	21 60
2	120	24	17 + 20	24	11 *+ 30	11 *	12 + 70	18
3	150	8 * + 70	19	16 +	18	9 + 50	17	15 + 30
4	50	12 *	28	18 50	16	21	20	25

Значение целевой  функции составит

L = 23· 30 + 28· 10 + 21· 60 + 17· 20 + 11· 30 + 12· 70 + 8· 70 + 9·  50 + 15· 30 + 18· 50 = 6100 ваг-км.

Более подробно эти методы рассмотрены в.