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

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

Рисунок 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

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

Охрана труда при производстве и ремонте
В ходе модернизации крытого вагона модели 13-9553 вводятся новый конструкционный материал – стеклопластик. Его описание и механические свойства приведены в разделе 1. В данной части проекта мы рассмотрим лишь его пожароустойчивость. Такж ...

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

Выбор сегмента рынка услуг
По заданию проекта услуга по приёму отработанных эксплуатационных материалов может быть сегментирована на виды работ приведённые в таблице 8. Таблица 8: Перечень услуг У-код услуги Перечень услуг У1 Приём отработанных масе ...