Постановка и решение задачи оптимизации грузопотоков

Задача оптимизации грузопотоков в общем виде формулируется следующим образом: имеется множество поставщиков (пункты погрузки) и множество потребителей однородных грузов (пункты разгрузки). Известно количество грузов, имеющихся у поставщиков и объемы поставок потребителям. Определены кратчайшие расстояния между пунктами транспортной сети.

Рисунок 1 – Схема железнодорожного направления

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

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

(1.1)

m – количество поставщиков продукции;

n – количество потребителей продукции;

хij – объем перевозок от i-поставщика к j-потребителю;

lij – расстояние перевозки от i-поставщика к j-потребителю.

При этом действуют следующие ограничения:

; .

аi – объем вывоза груза от поставщика, т;

bj – объем завоза груза потребителю, т.

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

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

Существую различные методы получения базисного плана. Один из них – метод северо-западного угла. В соответствии с этим методом заполнение таблицы начинается с левого верхнего угла, затем по каждой строке распределительной таблицы находится минимальное значение расстояния перевозки, и то же самое выполняется по каждому столбцу.

Опорный план должен отвечать следующим условиям:

1) он должен содержать m + n – 1 клеток, где

m – количество строк;

n – количество столбцов.

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

3) должно соблюдаться условие проверки плана на оптимальность методом потенциалов.

Доказано, что, если план является оптимальным, то ему соответствует система из m + n чисел, удовлетворяющих следующим условиям:

1) при хij > 0

2) при xij = 0.

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

Таблица 1.1 – Распределительная таблица оптимального закрепления потребителей за поставщиками каменного угля

Грузоотправители	Грузополучатели
	Г	В	Е	З	И	Вывоз
А	50 390	200	30 290	445	110 540	190
Б	270	60 80	10 170	130 325	420	200
Д	75	115	140 120	275	430	140
Ввоз	50	60	180	130	110	530

Популярные материалы:

Изучение структуры парка автомобилей
Таблица 6: Структура парка автомобилей Годы 2006 2007 2008 2009 2010 Всего 7500 7900 8025 9000 9825 Иномарки 2375 2400 2550 2975 3000 Отечественные 4100 4625 5650 ...

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

Расчет сменной программы по видам ТО и диагностики
Для расчета сменной программы по видам ТО необходимо принять количество рабочих дней в году и количество смен работы для каждой зоны ТО по Приложению 8 Методических указаний. Сменная программа рассчитывается по общей для всех видов ТО фо ...