На правах рукописи

Якубовская Наталья Николаевна

АНАЛИЗ И ОПТИМИЗАЦИЯ ТРАНСПОРТНОЙ

ПРОИЗВОДСТВЕННОЙ СИСТЕМЫ

05.13.01 – Системный анализ, управление и обработка информации

(промышленность)

Автореферат диссертации на соискание ученой степени

кандидата технических наук

Санкт-Петербург 2006

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Санкт-Петербургском государственном технологическом институте (техническом университете)».

Научный руководитель:

доктор технических наук, профессор Лисицын Николай Васильевич

Официальные оппоненты:

доктор технических наук, профессор Уткин Лев Владимирович кандидат технических наук Нозик Александр Абрамович Ведущее предприятие:

институт проблем управления РАН, г.Москва.

Защита диссертации состоится «»200_г. в_ час. в ауд. № на заседании диссертационного совета Д212.230.03 при Государственном образовательном учреждении высшего профессионального образования «Санкт-Петербургском государственном технологическом институте (техническом университете)» по адресу: 190013, Санкт-Петербург, Московский пр., д. 26.

С диссертацией можно ознакомиться в библиотеке института.

Отзывы и замечания в одном экземпляре, заверенные печатью, просим направлять по адресу: 190013, Санкт-Петербург, Московский пр., д.26.

Государственное образовательное учреждение высшего профессионального образования «Санкт-Петербургский государственный технологический институт (технический университет)», Ученый совет.

Автореферат разослан «» 200г.

Ученый секретарь диссертационного совета, д.т.н. В. И. Халимон

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Целью диссертации является оптимизация транспортной производственной системы (ТПС) химико-технологического предприятия. Для ее достижения:

– выполнена постановка задачи оптимизации транспортной производственной системы;

– построены математические модели транспортной системы и элементарных транспортных операций;

– выбраны методы и алгоритмы решения задачи оптимизации транспортной системы;

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

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

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

На защиту выносится:

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

программирования для решения транспортной задачи, которые удовлетворяют марковскому свойству;

транспортной производственной системы;

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

Научная новизна заключается в:

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

';

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

Достоверность сформулированных научных положений и выводов подтверждена свидетельством об отраслевой регистрации разработки № от 27.03.06г. отраслевого фонда алгоритмов и программ федерального агентства по образованию: «Новый алгоритм определения минимальной цены транспортировки товара, а также программной реализацией алгоритма в среде Delphi».

Практическая значимость. Разработанная математическая модель оперативного управления ТПС и ее программная реализация позволяют оценить затраты при планировании транспортировок, что дает резерв экономии ресурсов.

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

Апробация и публикации. Результаты диссертации докладывались на международных и всероссийских научных конференциях: научная конференция «ММТТ-19» (2006г., г. Воронеж), XI Международная открытая научная конференция «Современные проблемы автоматизации в прикладных задачах»

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

Структура и объем работы. Диссертация состоит из введения, пяти глав, выводов, списка литературы и приложения. Работа изложена на 130 стр., список литературы включает 81 наименование.

СОДЕРЖАНИЕ РАБОТЫ

сформулированы цели и задачи исследования.

производственной системы. (Глава 1).

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

xij – количество ресурса, транспортируемого из пункта i в пункт j;

zij – номер группы ТС, осуществляющих транспортировку из i в j;

cij – стоимость транспортировки единицы ресурса из i в j.

D = {d кl } к, l = 1,K, N – количество вершин в графе транспортной сети D;

d кl = d кl xij, zij – стоимость транспортировки ресурсов xij группой zij из пункта к в пункт l транспортной сети где g – ресурсоемкость.

Формализованная структура оптимизации ТПС представлена на рис.1.

Для решения нелинейной задачи оптимизации транспортной производственной системы составлен итерационный алгоритм (рис.2).

(ai, bj) Рисунок 1 – Формализованная структура оптимизации ТПС Предлагается линеаризация исходной задачи на основе следующей эвристики: cij зависит только от расстояния и условий транспортировки (2) и одинаковы для любой группы транспортных средств zij. Для решения линейной транспортной задачи разработан безытерационный алгоритм (рис.3), в соответствии, с которым задача оптимизации ТПС декомпозируется на три последовательные задачи. Сначала решается подзадача определения оптимальных путей перемещения ресурсов, затем строится матрица затрат на транспортировку. На матрице затрат решается транспортная задача.

Полученное решение транспортной задачи используется для формирования матрицы цен назначений. Наконец, на матрице цен назначений решается задача о назначениях. Решение задачи о назначениях является решением задачи оптик= Рисунок 2 – Итерационный алгоритм оптимизации мального оперативного управления ТПС. Это решение указывает, какая группа оптимизации отдельных задач и системы в целом.

Реш ение линейной транспортной задачи arg m in c ij x ij = C непересекаю щ и хся сочетаний тран спортны х средств, В ы числение стоимости назначений e pq с учетом условий (4) при Рисунок 3 – Безытерационный алгоритм решения исходной задачи Методы решения задачи управления транспортной системой (Глава 2).

1. Метод определения оптимальных путей в транспортной сети.

неориентированный граф. Каждому ребру (коммуникации) между вершинами k и l поставлено в соответствие некоторое число dkl, являющееся некоторой оценкой затрат на транспортировку из пункта k в l и обратно dlk. Требуется определить путь в графе pij из пункта i в пункт j, проходящий через промежуточные вершины:

Его суммарная «длина» сij должна быть минимальна:

Известно, что метод динамического программирования основан на принципе оптимальности: любой подпуть минимального пути является минимальным путем между соответствующими вершинами. Через fk(i, j) обозначается минимальный путь из i в j длиной не более k ребер (или дуг).

Согласно принципу оптимальности может быть составлено рекуррентное уравнение Беллмана, которое для данной задачи имеет вид:

Оптимальный путь составляется из m вершин на каждом шаге k.

программирования. План (ее решение) может быть получен с помощью приближенных методов – северо-западного угла и (или) наименьшего элемента.

Суть обоих методов состоит в том, что базисный план составляется последовательно в m+n-1 шагов. Метод потенциалов позволяет улучшить приближенное решение и довести его до оптимального.

транспортировки зависит от xij нелинейным образом: qij(xij). Источником нелинейности может быть, например, зависимость расхода топлива от скорости и грузоподъемности, приведенная на рис.4. В этом случае общий критерий оптимизации также нелинейный:

Методы решения транспортной задачи.

Один из способов решения нелинейной задачи – ее сведение к некоторой последовательности линейных задач, для которых существует метод решения, например, тот же метод потенциалов. Другой подход – последовательные рассматривается транспортная задача с двумя исходными m = 2 и n конечными пунктами.

Рисунок 4 – Нелинейная зависимость расхода топлива от скорости и грузоподъемности Функция Беллмана в данном случае может представлять собой минимальные расходы по транспортировке из двух пунктов в n пунктов, когда в исходных пунктах количество ресурсов а1 и а2: fj(а1, а2), j = 1,…, n. Благодаря ограничениям функциональные уравнения (8) сводятся к функциям одной переменной а1:

Таким образом, для n = 2 нелинейная транспортная задача сравнительно легко может быть решена методом динамического программирования, Трудности, связанные с памятью компьютеров и их быстродействием, начинаются при n > 2. В этом случае целесообразно использовать метод последовательных приближений.

приближение для решения транспортной задачи. Затем фиксируются все xkl k = 3, …, n, l = 1,…, m. Для k = 1,2, для первых двух исходных пунктов, решается транспортная задача с помощью функциональных уравнений (10) и (11). Затем решение для k = 1, 2 фиксируется, для k = 5, …, m решения остаются фиксированными, а для k = 3,4 снова решается задача (10) и (11) и так далее.

Таким образом, реализуется следующая процедура:

Процесс последовательных приближений по определению сходится, так как от i-го шага к i+1-ому происходит уменьшение стоимости транспортировки.

задано n работ и m исполнителей; задана матрица С={cij} стоимостей назначения i-го исполнителя для выполнения j-ой работы. Требуется так произвести назначения, чтобы суммарная стоимость назначений Y0 была бы минимальна.

транспортной системы (Глава 3).

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

где k0, k1, k2 – коэффициенты, v – скорость, skl – расстояние между пунктами k и l, сТ – стоимость топлива.

Путь из i в j состоит из nij участков k l и на каждом m-ом участке скорость транспортировки vm определяется транспортными условиями и нормами. Суммарная стоимость транспортировки из i в j cij равняется Значения коэффициентов k0, k1, k2 были получены в результате обработки Киришинефтеоргсинтез». За реперную точку был принят нормативный расход бензина при средней скорости движения 60 км/ч и усредненной по грузоподъемности. Обработка данных для 250 грузовых автомобилей, участвующих в перевозке нефтепродуктов, окончательно привели к следующей зависимости удельного расхода бензина Т от скорости движения:

Хотя это приближенная модель с относительной ошибкой 20-25%, она отражает реальность и может быть использована для оценки энергетических затрат на транспортировку.

транспортировки. Стоимости epq выполнения q-ой транспортировки р-ой группой транспортных средств рассчитывались по формуле:

где сq – стоимость q-ой транспортировки, хq – объемы транспортировок, sq – расстояние, al – коэффициент амортизации. Задача назначения решена с помощью разработанной программы, реализующей венгерский алгоритм.

Программное обеспечение для оптимизации ТПС (Глава 4).

1. Программа нахождения возможного количества транспортных средств (определение непересекающихся сочетаний из сочетаний транспортных средств). Для расчета количества транспортных средств сначала определяются все сочетания из n транспортных средств по m = 1,…, n – Q + 1 транспортных средств, где Q – количество заданий на транспортировку, полученное в результате решения транспортной задачи. Максимальное число сочетаний из сочетаний n – Q + 1 определяется исходя из требования, чтобы в задаче о назначениях матрица цен назначений была бы квадратной: исполнителей транспортировок было бы столько же, сколько заданий на транспортировки.

Таким образом, количество возможных исполнителей nР будет равно сумме числа сочетаний из n по m = 1,…, n – Q + 1:

Это число рассчитывается с помощью рекуррентной формулы запоминаются в массиве S(1:nР, 1:Q). Затем из этого массива сочетаний формируются сочетания по Q. Каждое сочетание из сочетаний проверяется на непротиворечивость: не повторяются ли номера транспортных средств в составляющих сочетаниях данного сочетания сочетаний. Если повторяются, то данное сочетание сочетаний не фиксируется, если не повторяются, то оно запоминается.

2. Программа определения оптимальных путей в транспортной сети. В этой программе последовательно строятся функции Беллмана fк(l) к = 2, …, n – 1, l = 1, …, n, представляющие собой минимальные пути из заданного начального исходного пункта iн в заданный конечный пункт jк через к промежуточных пунктов. Для каждого участка оптимального пути кроме fк запоминается номер pкl промежуточного пункта на к-ом шаге. При к = n – 1 выводится цена fn-1(jк) оптимального пути и определяется в обратном порядке оптимальный путь из jк в iн по рекуррентной формуле:

Результат расчетов (минимальный путь) выводится в прямом порядке:

iн, l2,K, ln-1, jk. Входными данными программы являются значения цен ребер транспортного графа dij и номера начального и конечного пункта.

3. Программа решения транспортной задачи. В качестве примера рассматривается алгоритм динамического программирования для двух источников m=2.

Функциональное уравнение и начальное условие имеет вид:

Условие замкнутости записывается так:

Возможны два варианта реализации компьютерной программы по алгоритму (21-23). Первый вариант, когда вычисляются все функции двух переменных f(i, j) для i = 1,…, n, j = 1,…, a1 согласно уравнениям (19-21), а затем в обратном порядке для i = n,…, 1 восстанавливаются оптимальные кi.. Во втором варианте программы используются только две функции fi и fi–1. С помощью fi–1 вычисляется fi согласно (21) и она записывается на место fi–1. Но ресурса выделяется i-ому потребителю, если в первом источнике осталось количество ресурса равное j. Решалась следующая задача:

Решение, полученное по первому варианту программы, имеет вид:

С помощью второго варианта получается другое решение:

Объяснение различий в том, что замкнутая задача не обладает марковским свойством независимости оптимального решения на i-ом шаге от предистории, решений на предыдущих шагах от i – 1 до 1. Действительно, чтобы удовлетворить ограничениям типа равенства необходимо на i-ом шаге, когда количество ресурса в l-ом источнике равно j, определять к(i, j) как разность между j и уже израсходованным ресурсом на оптимальной траектории к(l, j) для l = i – 1, …, 1:

То есть, как следует из (25-26), решение на i-ом шаге должно зависеть от решений на предыдущих шагах от i – 1 до 1. Это и означает отсутствие программирования можно было решать замкнутую транспортную задачу, необходимо дополнить алгоритм решения частью, учитывающей равенства (24) с помощью формул (25-26). На блок-схеме рис. 5 эта часть обведена прямоугольником. Так как только второй вариант алгоритма предусматривает запоминание всех к(i, j), то только он может быть использован для оптимального управления ТПС.

Сведение задачи синтеза ХТС к транспортной задаче (Глава 5).

компаундирования требуется получить n конечных (товарных) продуктов, причем процесс осуществляется непрерывно в потоке, т.е. весь поток i-ого полупродукта должен быть использован и нет емкости для его накопления и хранения. Формально это может быть выражено в виде уравнения аналогичного зависимости (2):

где xij – поток i-ого полупродукта, входящий в состав j-ого продукта, т/ч, ai – l=l-