Планирование перевозок грузов горных предприятий

ВВЕДЕНИЕ

Применение методов математического программирования в планировании связано с повышением требований к количественному и качественному анализу экономических процессов, вносит изменения в содержание плана отрасли и порядок его разработки. Поэтому совершенствование методов планирования народного хозяйства при широком использовании вычислительной техники остается необходимым условием дальнейшего повышения эффективности экономики.
Одной из ключевых проблем развития народного хозяйства является дальнейшее повышение научной обоснованности решений, принимаемых во всех областях практической деятельности. По мере развития народного хозяйства, усложнения внутриотраслевых и межотраслевых связей и роста общественных потребностей повышаются требования к планированию и управлению. Особенно большое значение придается комплексности и научной обоснованности планов развития народного хозяйства. Решение таких задач невозможно без применения эффективных экономико-математических методов и ЭВМ, степень использования которых во многом определяет научную обоснованность планирования и управления экономикой.
Под математическим моделированием понимается метод исследования процессов или явлений на основе изучения их математических моделей.
Линейные модели применяются для решения большого количества плановых задач. Причем форма задач во многих случаях повторяется, задачи одного класса возникают в различных отраслях горной промышленности, сферах деятельности горного предприятия.

1. ПЛАНИРОВАНИЕ ПЕРЕВОЗОК ГРУЗОВ ГОРНЫХ ПРЕДПРИЯТИЙ

Грузы предприятий горной промышленности составляют значительный удельный вес (до 40%) в грузообороте страны. Поэтому рациональное планирование их перевозок является важной задачей. Они называются транспортными и относятся к линейным.

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

Приведем модель транспортной задачи в общем виде.

Имеется несколько n производителей (поставщиков) однородного продукта (i = 1, 2, 3, …, n) и несколько m потребителей (j = 1, 2, 3,…, m). Объем груза, который необходимо вывезти от i-го поставщика Аi, а потребность j-го потребителя — Вj. Затраты на перевозку единицы груза от i-го поставщика j-му потребителю составляют cij.

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

За управляемые переменные примем хij –  объем груза, перевозимого от i-го поставщика j-му потребителю.

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

                                            (1.1)

Ограничениями задачи (помимо требований положительности переменных, которые здесь и в дальнейшем не указываются) являются:

обязательность вывоза грузов от каждого поставщика

                                        (1.2)

полное удовлетворение запросов потребителей

                                      (1.3)

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

                                                  (1.4)

Подобная модель называется закрытой. Если , то модель называется открытой, для ее решения она приводится к закрытой введением фиктивного поставщика или потребителя.

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

Транспортные задачи – это также и задачи планирования грузоперевозок внутри предприятия, например, планирование карьерных грузопотоков. Приведем модель этой задачи.

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

Обозначим через i – забои карьера (участки горного предприятия)  отвалы (приемные пункты),  объем работ
i-му участку; Qj – максимальную приемную способность j-го отвала; Сij – затраты на перевозку единицы объема с i-го забоя на j-й отвал.

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

За управляемые переменные примем xij – объем грузоперевозок с i-го участка на j-й отвал, тогда целевая функция примет вид

                                           (1.5)

при ограничениях:

по объему работ по участкам

                                           (1.6)

т.е. с каждого участка нужно увезти породу полностью;

по приемной способности отвалов

                                          (1.7)

т.е. объем пород, вывозимый на отвал, не может превышать его приемной способности;

по положительности переменных

                                                  (1.8)

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

                                           (1.9)

Решение транспортной задачи линейного программирования включает два основных этапа: построение опорного решения (начального плана перевозок) и построение оптимального решения.

Пример 1.

На карьере три вскрышных участка, порода с которых вывозится на два отвала. Средние расстояния транспортирования породы с участков на отвалы (в км) приведены в таблице 1.

Таблица 1

Участок

Отвалы

1

2

1

3,5

4,2

2

5,7

5,1

3

4,5

4,8

Годовой объем вскрышных работ по участкам соответственно составляет (в млн. м3) – 2,6; 3,7; 2,9, а максимальные приемные способности отвалов соответственно 4,7 и 5,3.

Распределить объемы вскрышных пород с участков по отвалам, обеспечив минимальную работу транспорта.

Словесная формулировка задачи: составить план грузоперевозок, обеспечивающих вывозку и плановые объемы вскрышных пород с минимальными транспортными затратами, учитывая приемные способности отвалов.

Математическая формулировка задачи: обозначим через х11 – объем породы, транспортируемый с первого участка на первый отвал; х12 – то же, с первого участка на второй отвал; х21 – то же, со второго участка на первый отвал; х22 – то же, со второго участка на второй отвал; х31 – то же, с третьего участка на первый отвал; х32 – то же, с третьего участка на второй отвал.

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

Минимизировать  (годовой грузооборот) при ограничениях:

(условия обязательности выполнения плановых объемов работ по участкам);

(предельная приемная способность отвалов);

(условие неотрицательности переменных).

2. ПОСТРОЕНИЕ ОПОРНОГО РЕШЕНИЯ

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

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

Метод северо-западного угла используется, как правило, при расчетах на ЭВМ. При его применении данные о стоимостях не нужны. Рассматривается клетка 11 (северо-западный угол) и в нее на основании сравнения величин а1 и b1 проставляется максимальный объем перевозок (минимальная из величин а1 и b1). Если а1 > b1, то первый столбец из рассмотрения исключается, так как потребности первого потребителя удовлетворены (x11 = b1), и определяется разность  (остаток запасов у первого поставщика). Далее рассматривается клетка 12 (новый северо-западный угол) и сравниваются величины b2 и ().В клетку 12 проставляется минимальная из этих величин. Если  b2, то далее рассматривается клетка 22 (новый северо-западный угол) и сравниваются величины а2 и [] (оставшаяся потребность у второго потребителя). Подобная процедура повторяется вплоть до заполнения всей матрицы.

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

При построении опорного решения транспортной задачи методом двойного предпочтения поочередно просматриваются все строки и столбцы матрицы. Клетки, содержащие минимальные удельные затраты на перевозку в каждой строке и столбце, помечаются каким-нибудь знаком. Первоначально объемы перевозок проставляются в клетках, отмеченных дважды, т.е. предпочтительных как в строке, так и в столбце (отсюда и название метода). После того, как клетки помеченные дважды, заполнены полностью, объемы проставляются в клетки, отмеченные один раз. Затем с учетом ограничений по аi и bj заполняются остальные клетки.

3. УСЛОВИЯ И МЕТОД ПОСТРОЕНИЯ ОПТИМАЛЬНОГО РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ

 

Один из наиболее простых и распространенных методов оптимизации транспортной задачи – метод потенциалов. Условия оптимальности плана транспортной задачи вытекают из теорем двойственности и заключаются в следующем.

Для того чтобы допустимый план транспортной задачи был оптимальным, необходимо и достаточно, чтобы ему соответствовала система чисел U1,U2,…,Un,V1,V2,…,Vm, удовлетворяющая условиям:

I.                                       если                               (3.1)

II.                   если                             (3.2)

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

Условия потенциальности показывают, что разность потенциалов потребителя и поставщика равна стоимости перевозки между ними, если перевозка осуществляется (условие 3.2), и не больше стоимости перевозки при ее отсутствии (условие 3.1).

Алгоритм решения транспортной задачи методом потенциалов стоит из двух этапов: предварительного и общего.

Первый (предварительный) этап включает:

I — 1 – построение опорного решения;

I — 2 – присвоение и расчет системы потенциалов;

I — З – проверка первоначального плана на оптимальность.

Если опорное решение не является оптимальным, то переходят ко второму (общему) этапу, который включает:

II — 1 – улучшение плана перевозок;

II — 2 – исправление системы потенциалов;

II — З – проверка улучшенного плана на оптимальность.

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

Рассмотрим подробнее составные части метода потенциалов.

Построение опорного решения (I-1) осуществляется методами северо-западного угла, наименьших стоимостей или двойного предпочтения.

Расчет системы потенциалов (I-2) производится на основании второго условия оптимальности.

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

Используя занятые клетки для расчета потенциалов, можно составить систему из () уравнений с (т + п) переменными. Такая система имеет неограниченное множество решений. Поэтому для построения системы потенциалов надо задаться потенциалом одного поставщика или потребителя (строки или столбца). Обычно полагают U1 = 0 либо присваивают нулевой потенциал строке, имеющей занятую перевозкой клетку с наибольшей стоимостью. Далее потенциалы всех остальных столбцов и строк вычисляют через занятые клетки, используя второе условие оптимальности.

Проверка плана на оптимальность (шаги I — З и II — 3 ) проводится для клеток, не занятых перевозками. Очевидно, что для клеток с перевозками второе условие оптимальности выполняется, так как оно было использовано для присвоения системы потенциалов. Для всех незанятых клеток проверяется выполнение первого условия оптимальности. Для этого вычисляют невязку . Если  для всех клеток, то план является оптимальным, так как первое условие оптимальности соблюдено. Если имеются положительные превышения, то первое условие оптимальности не соблюдено и план может быть улучшен. Величина  показывает, какая экономия на перевозку единицы груза может быть достигнута при изменении плана перевозок.

Улучшение плана перевозок заключается в выборе (II-1) клетки с максимальным превышением и составлении замкнутого контура (цикла), вершинами которого являются клетка с нарушением и клетка с перевозками. Контур может иметь различную конфигурацию, но на нем всегда четное количество вершин. Начиная с клетки, имеющей нарушение, вершины контура нумеруются (по часовой стрелке или против). Нечетные вершины составляют положительную полуцепь, а четные — отрицательную. При улучшении плана в вершинах положительной полуцепь (нечетных) объемы перевозок увеличатся, а в вершинах отрицательной полуцепи (четных) уменьшатся. Далее просматривают объемы перевозок в четных клетках и находят минимальный из них . После этого перераспределяют объемы перевозок внутри контура, для чего к объемам перевозок в нечетных вершинах прибавляют объем , а из объемов перевозок в четных вершинах вычитают эту величину. В результате этой процедуры получают улучшенный план, в котором общие затраты на перевозку меньше, чем в предыдущем плане, на величину . Новый план является допустимым, так как в каждой строке и столбце замкнутого контура в одной клетке объем увеличился, а в другой уменьшился на одну и ту же величину.

Проверке улучшенного плана на оптимальность (шаг II-З) предшествует исправление системы потенциалов (шаг II-2). Для этого не обязательно строить новую систему потенциалов, можно исправить прежнюю.

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

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

ВЫВОДЫ

Отдельные типы задач линейного программирования (транспортные) в силу специфичности своей структуры могут решаться простыми методами. К транспортным относится большое количество задач планирования перевозок грузов. Кроме того, ряд других задач может быть сведен к транспортным.
Транспортная задача имеет следующие особенности:
— Все ограничения имеют вид неравенств;
— Каждая переменная входит всего в два ограничения;
— Коэффициенты при переменных в ограничениях равны 1.
Для решения транспортной задачи составляют специальные матрицы. Решение транспортной задачи состоит в последовательном переборе всех допустимых базисных решений, до тех пор, пока не будет выполнен критерий оптимальности. В отличие от задач линейного программирования транспортная задача всегда имеет оптимальное решение.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Вітлінський В.В. Моделювання економiки: Навч. посiбник. — К.:
КНЕУ, 2003.
2. Малыхин В. И. Математическое моделирование экономики: Учеб. практ. пособие. —М.: УРАО, 1998.
3. Курносов А.М. Кудин И.Б. Совершенствование методов математического программирования в горном деле / Отв. ред. Д.М.Бронников. – М.: Наука, 1984. – 232с.
4. Резниченко С.С., Ашихмин А.А. Математические методы и моделирование в горной промышленности: Учеб. пособ. для студ. горн. спец. вузов. – 2-е изд., стер. – М.: Изд-во МГУ, 2001. – 404с.

Скачать работу

Полная версия работы содержит все необходимые формулы.