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

Реферат

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

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

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

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

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

КИЕВ 2001

Оглавление

ОГЛАВЛЕНИЕ 1

Пример № 1. 1

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

Пример № 2. 7

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

Пример № 3. 9

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

Пример № 4. 13

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

Пример № 5. 19

ЛИТЕРАТУРА 25

Пример № 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-й станции назначения.

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