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

Якубовская Наталья Николаевна АНАЛИЗ И ОПТИМИЗАЦИЯ ТРАНСПОРТНОЙ ПРОИЗВОДСТВЕННОЙ СИСТЕМЫ 05.13.01 - Системный анализ, управление и обработка информации (промышленность)

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

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

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

Научный консультант:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Во введении обоснована актуальность темы диссертации, сформулированы цели и задачи исследования.

Аналитический обзор методов оптимального управления транспортной системой промышленного химико-технологического предприятия. Постановка задачи оптимизации транспортной производственной системы. (Глава 1).

Математическая формулировка задачи оптимизации транспортной производственной системой может быть представлена следующим образом:

m n m,izn ( ) (1) c xij, zij xij ij xij ij i=1 j=xij - количество ресурса, транспортируемого из пункта i в пункт j;

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

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

nm K,m;

(2) x = ai const i 1,==== ij x bj j 1,K,n; a b ij i j j=1 i=1j i D = dкl к, l =1,K, N - количество вершин в графе транспортной сети D;

{ } dкl = dкl xij, zij - стоимость транспортировки ресурсов xij группой zij из пункта ( ) к в пункт l транспортной сети nij cij xij, zij = min (3) ( ) d ( ) ( ) Pij kij p lij p p=Pij = кij =0 о lij 0 = 1 оK о кij nij о lij nij = j кij ( ) ( ) ( ) ( ) ( ) {i };

Tz = t1z,K,tn z} - z-ая группа ТС.

{ z nz xij, (4) ( ) g tk zij k =где g - ресурсоемкость.

TZ I TA = 0 A Z (5) Формализованная структура оптимизации ТПС представлена на рис.1.

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

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

Полученное решение транспортной задачи используется для формирования матрицы цен назначений. Наконец, на матрице цен назначений решается задача о назначениях. Решение задачи о назначениях является решением задачи оптик = xij= xijк нет условия (2) изменение xijк выполнены zij=zijк нет условия (4,5) изменение zijк выполнены Вычисление сij(xijк, zijк) (3) Решение линейной транспортной задачи к arg min cij xij = xij +нет к к xij +1 - xij < e xijк= xijк+стоп Рисунок 2 - Итерационный алгоритм оптимизации транспортной производственной системой мального оперативного управления ТПС. Это решение указывает, какая группа ТС должна осуществить заданную транспортировку. Таким образом, постановка задачи оптимизации ТПС сводится к ее декомпозиции, оптимизации отдельных задач и системы в целом.

Вычисление cij (3) на графе D Решение линейной транспортной задачи arg min cij xij = C Количество транспортировок Q=m+n-Формирование задачи о назначениях. Выбор P=Q непересекающихся сочетаний транспортных средств, удовлетворяющих условиям (5) Вычисление стоимости назначений epq с учетом условий (4) при xij CРешение задачи о назначениях arg min y e = Y pq pq ypq p q y = y = pq pq pq Рисунок 3 - Безытерационный алгоритм решения исходной задачи Методы решения задачи управления транспортной системой (Глава 2).

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

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

i = kij 0 о lij = kij 1 о lij = kij 2 о K о kij nij о lij =ij = j pij 0 1 n ( ) ( ) ( ) ( ) ( ) (6) ( ) ( ) ( ) Его суммарная длина сij должна быть минимальна:

nij cij = min (7) d ( ) ( ) pij m=1 kij m lij m Известно, что метод динамического программирования основан на принципе оптимальности: любой подпуть минимального пути является минимальным путем между соответствующими вершинами. Через fk(i, j) обозначается минимальный путь из i в j длиной не более k ребер (или дуг).

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

fk+1 i, j = minm j fk i, j, fk i, m + dmj ( ) ( ) ( ) { } m=1,K,n (8) k = 0, 1, 2,K,n -1 i, j =1,K,n f0 i, j = dij fk i, i = ( ) ( ) Оптимальный путь составляется из m вершин на каждом шаге k.

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

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

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

m n F = ( ) (9) q xij ij i=1 j=Методы решения транспортной задачи.

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

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

f1 a1 = q11 a1 + q21 b1 - a( ) ( ) ( ) (10) f a1 = mina 1 j x1 j + q2 j bj - x1 j + f a1 - x1 j j = 2,K,n(11) ( ) ( ) ( ) ( ) {q jj-1 };

0x1 j Таким образом, для 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) и так далее.

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

f1 ai = qij ai + qi+1, j b - ai ( ) ( ) (12) ( ) j fi ai = mina qij xij + qi+1, j b - xij + f ai - xij ( ) ( ) ( ) ( ) { } j j-0 xij l (13) j = 2,K, n;= i 1,K, m - Процесс последовательных приближений по определению сходится, так как от i-го шага к i+1-ому происходит уменьшение стоимости транспортировки.

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