автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Анализ и оптимизация транспортной производственной системы

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

о с

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

АНАЛИЗ И ОПТИМИЗАЦИЯ ТРАНСПОРТНОЙ ПРОИЗВОДСТВЕННОЙ СИСТЕМЫ

05.13.01 — Системный анализ, управление и обработка информации (промышленность)

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

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

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

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

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

доктор технических наук, профессор Уткин Лев Владимирович

кандидат технических наук Нозик Александр Абрамович

Ведущее предприятие:

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

Защита диссертации состоится « 200 ¡^В'^^часх в ауд. №

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

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

Автореферат разослан <</Ь »

Л.

200 г.

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

В. И. Халимон

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

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

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

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

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

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

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

5 выбраны методы и алгоритмы, решения задачи, .оптимизации транспортной системы; ■;... . •-■. - . -

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

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

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

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

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

■ выполняющих заданную транспортировку; '

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

' марковскому свойству; • ' ., •

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

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

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

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

— разработке алгоритма и программы, реализующих метод динамического программирования; для решения транспортной задачи, удовлетворяющей марковскому свойству, поскольку исходная: замкнутая транспортная задача марковским свойством не. обладает, т.к. в ней не удовлетворяется требование равенства количества ресурсов, перемещаемое из данного источника, заданной величине'.., ■• • : •. - .-.■.• - .-....-

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

Практическая значимость. Разработана математическая модель оперативного управления ТПС. Ее программная реализация внедрена в промышленную эксплуатацию в цехе №21 ООО «ПО«Киришинефтеоргсинтез».

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

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

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

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

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

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

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

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

■ т п • .

^ХЛФи'Фи (1)

• • '« I-1 >1 , - '.•■'.'

х--- количество ресурса, транспортируемого из пункта / в пункт _/;

~ номер группы ТС, осуществляющих транспортировку из; в/; Су - стоимость транспортировки единицы ресурса из / в/.

я ' т ___

• =а, =сош1 1 = 1,...,/и; У = 1>->Ъ =ЕЬ, (2)

О = {с1к1} к, I = 1,. - количество вершин в графе транспортной сети £>; йк] = йк1 (ху, г^ - стоимость транспортировки ресурсов ху группой из пункта к в пункт 1 транспортной сети

(3)

= = (о)->(0) = гс^(1)^..,-> ) («,у) = у}; - ,

Тг = -г-ая группа ТС.

(4)

г=4 ■ . :

где § - ресурсоемкость.

тгптл=0 А*г (5)

б

Формализованная структура оптимизации ТПС представлена на рис.]. Для решения нелинейной задачи оптимизации транспортной производственной системы составлен итерационный "алгоритм (рис.2).

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

Предлагается линеаризация исходной задачи на основе следующей эвристики: с,у зависит только от расстояния и условий транспортировки (2) и одинаковы для любой группы транспортных средств гу. Для решения линейной транспортной задачи разработан безытерационный алгоритм (рис.3), в соответствии, с которым задача оптимизации ТПС декомпозируется на три последовательные задачи.. Сначала решается, подзадача определения оптимальных путей перемещения ресурсов, затем строится матрица затрат на транспортировку. . На ; матрице ' 1 затрат решается транспортная задача. Полученное решение транспортной, задачи используется для формирования матрицы цен назначений. Наконец, на матрице цен назначений решается задача о назначениях. Решение задачи о назначениях является решением задачи опта- •

Рисунок 2 - Итерационный алгоритм оптимизации транспортной производственной системой

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

Рисунок 3 — Безытёрацнонный алгоритм решения исходной задачи

Методы решения задачи управления транспортной системой (Глава 2). ' 1. Метод определения оптимальных путей в транспортной сети. - •'■'■'•"

^ : Транспортная - сеть ■ в ' общем - случае представляет ' собой неориентированный граф. Каждому ребру (коммуникации) между вершинами к и / поставлено в соответствие некоторое число с1ц, являющееся некоторой оценкой затрат на транспортировку из пункта £ в / и обратно Требуется определить путь в графе ра- из пункта г в пункт У, проходящий через промежуточные вершины:

(/ = ку(0)->1у(0) = к,(1)(1 )'=к?(2)->...->ку(п0)-> 1у= у) = Ри ; (6)

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

X

•* с,; — пип V (1, ••■ ' .* ' '■ • ■' (7)

у Ра к'ЛтУ>Лт) 4 '

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

Л+1 (*. Л=т=1 ,{/к{ и Д /к{,I, т)+¿ту} к = 0,1,2,...,и-1 • г, 7 = 1 ,...,п (8)

/о ('"»./) = <*/ ЛО' 0 = °

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

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

: Дополнительные трудности возникают, когда стоимость г /-ой транспортировки зависит от Ху нелинейным образом: <?,/%). Источником нелинейности может быть, например, зависимость расхода топлива от скорости и грузоподъемности, приведенная на рис.4. В этом случае общий критерий оптимизации также нелинейный: • - .

• ' (9)

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

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

Функция Беялмана в данном случае может представлять собой минимальные расходы по транспортировке го двух пунктов в п'пунктов, когда в исходных пунктах количество ресурсов а\ и а^: а2), ] = 1,..., п. Благодаря

ограничениям функциональные уравнения (8) сводятся к функциям одной переменной а\\

¿Ы^пЫ + ^^-сО (Ю)

= + -ьМ/Лъ ; = 2>->" (11)

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

Сначала методом северо-западного угла определяется начальное приближение для решения транспортной задачи. Затем фиксируются все хц к — 3, ..., п, 1 = 1..... т. Для к = 1,2, для первых двух исходных пунктов,

решается транспортная задача с помощью функциональных уравнений (10) и (11). Затем решение для к = 1, 2 фиксируется, для к — 5, ...,т решения остаются фиксированными, а для Аг = 3,4 снова решается задача (10) и (11) и так далее. Таким образом, реализуется следующая процедура:

А О-) = Я у (а>) + [Ь] ~ ) (12)

} = 2,...,п; г = 1,... ,/и — 1 ' "; .

Процесс последовательных приближений по определению' сходится, так

как от /-го шага к /+1-ому происходит уменьшение стоимости транспортировки.

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

задано п работ и т исполнителей; задана матрица С={с,у} стоимостей

назначения /-го исполнителя для выполнения /-ой работы. Требуется так

произвести назначения, чтобы суммарная стоимость назначений У0 была бы

минимальна, - , * ; * . , - V ' •-■■.... :

.Математическое моделирование- производственных: операций

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

I.-Модель перемещения транспортных , средств между .пунктами, к и I,

транспортной сети. Стоимость транспортировки между пунктами

транспортной сети очевидно должна зависеть от скорости перемещения и от

расстояния между пунктами. Функция от скорости носит параболический

характер, (см. рис. 4), что в итоге выражено в следующей зависимости: ■ '1'

= (£0 + • V + V V2) % • сг /10 0, (14)

где к0,ки к2 — коэффициенты, V - скорость, 5и - расстояние между пунктами к и

/, ст~ стоимость топлива. ' ' ....... -

Путь из г в ] состоит из щ участков к -> 1 и на каждом т-ом участке скорость транспортировки ут определяется транспортными условиями и нормами. Суммарная стоимость транспортировки из7 в/ Су равняется

ё "у ■

Значения коэффициентов к0, к\, кг были получены в результате обработки экспериментальных данных транспортного управлении ООО «ПО Киришинефтеоргсинтез». За реперную точку был принят нормативный расход бензина при средней скорости движения 60 км/ч и усредненной по грузоподъемности. Обработка данных для 250 грузовых автомобилей, участвующих в перевозке нефтепродуктов, окончательно привели к следующей зависимости удельного расхода бензина Тот скорости движения:

Т = 6.2 - 0.051 -V 4- 0.00083-V2 (16)

Хотя это приближенная модель с относительной ошибкой 20-25%, она

отражает реальность и может быть использована для оценки энергетических

затрат на транспортировку.

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

. .. . . (17)

? = (/-1 )-т + ]\ г = 1, 2; ] = 1,2,3,4, где сч — стоимость д-ой транспортировки, хч — объемы транспортировок, —

расстояние, а( - коэффициент амортизации. Задача назначения решена с помощью разработанной программы, реализующей венгерский алгоритм. Программное обеспечение для оптимизации ТПС (Глава 4). 1. Программа нахождения возможного количества транспортных средств. (определение непересекающихся сочетаний из сочетаний транспортных средств). Для расчета количества транспортных средств сначала определяются все сочетания из п транспортных средств по от = 1,..., п — 0+1 транспортных средств, где Q - количество заданий на транспортировку, полученное в результате решения транспортной задачи. Максимальное число сочетаний из сочетаний п - £) + 1 определяется исходя из требования, чтобы в задаче о назначениях матрица цен назначений была бы квадратной: исполнителей транспортировок было бы столько же, сколько заданий на транспортировки.

Таким образом, количество возможных исполнителей ир будет равно сумме числа сочетаний из и по т — 1,..., п — £) + 1: ■ ■

' ; ■ . ■ ■ л-СМ , -

"р= ' (18)

Это'число рассчитывается с помощью рекуррентной формулы

с: -сГ^^,.. от=1,...,л-е+1; (19) 1

т ' ■ ■ .

Разработанная программа формирует Ир сочетаний, которые запоминаются в массиве 5"(1:ир, 1:6). Затем из этого массива сочетаний формируются сочетания по Каждое сочетание из сочетаний проверяется на непротиворечивость: не ■ повторяются ли номера транспортных средств в: составляющих сочетаниях данного сочетания сочетаний. Если повторяются, то данное сочетание сочетаний не фиксируется, если не повторяются,. то оно запоминается.- ' ' .■■

2. Программа определения оптимальных путей в транспортной сети. В этой программе последовательно строятся функцииБеллмана к = 2, ..., п—\, 1= 1,... , п, представляющие собой минимальные пути из заданного начального исходного пункта г'„ в заданный конечный пункт ]к через к промежуточных пунктов. Для каждого участка оптимального пути кроме /к запоминается номер рК1 промежуточного пункта на к-ом шаге. При к = и - 1 выводится цена /п-\ОУ оптимального пути и определяется в обратном порядке оптимальный путь изв /„ по рекуррентной формуле: * ..........'

_ ^ = (/>+1.)) к = п-2,...,1 (2о)

' =р(п-1,Л).....

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

¡н, /2.....(,-1»7«г- Входными данными программы являются "значения цен рёбер

транспортного графа с/,у и номера начального и конечного пункта;

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

и)=«и» Ы*-«)+вЛь - *;)+/м С/ - *,)}

г = 1.....п

(23) (22)

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

я

(23)

Возможны два варианта реализации компьютерной программы по алгоритму (21-23). Первый вариант, когда вычисляются все функции двух переменных Дг, /) для / = 1,] — 1,-..., а\ согласно уравнениям (19-21), а затем в обратном порядке для г = п,..., 1 восстанавливаются оптимальные к,.. Во втором варианте программы используются только две функции // и С помощью /¡-1 вычисляется согласно (21) и она записывается на место Но на каждом ¿-ом шаге запоминаются оптимальные решения к{1, у): сколько ресурса выделяется /-ому потребителю, если в первом источнике осталось количество ресурса равноеРешалась следующая задача:

У \ 1 2 3 4 5 6 а,

1 5 6 1 3 6 3 40

2 3 5 4 2. 1 2 65

ь, 15 20 25 И 13 21 105

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

г б

2 1 2 3 4 5 6

' Км ■ 0 0 25 0 0 0 2^ = 25 <^ = 40

и 15 20 0 11 13 21

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

/ 1 2 • 3 4 "5 "6 в 2 «

Км' 0 15 25 0 0 0 1-1 XI ^, =262 (»1 1=1

кг 1 15 5 0 11 13 21

Объяснение различий в том, что замкнутая , задача не обладает марковским свойством независимости оптимального решения на г'-ом шаге от

предистории, решений на предыдущих шагах от 1 — 1 до 1. Действительно, чтобы удовлетворить ограничениям типа равенства

п

5>а=в, / = 1.....т (24)

необходимо на ¡-ом шаге, когда количество ресурса в /-ом источнике равно определять к(1, ]) как разность между / и уже израсходованным ресурсом на оптимальной траектории к(/,у) для / = /-1,..., 1:

' - = . - (25).

¿•1-1

где оптимальное : находится по рекуррентной формуле -

1 = 1,...,2. > . • . :..: (26) ■ То есть,'как следует из (25-26), решение на /-ом шаге должно зависеть от, решений на предыдущих шагах от г -1 , до 1. Это и означает отсутствие марковского свойства. Чтобы с' помощью метода - динамического программирования можно было решать замкнутую ■ транспортную задачу, необходимо дополнить алгоритм решения частью, учитывающей равенства (24) с помощью формул (25-26). На блок-схеме рис. 5 эта часть обведена прямоугольником. Так как только второй вариант алгоритма предусматривает запоминание всех к(1, /), то только оп может быть использован для

оптимального управления ТПС. - ...........

Сведение задачи синтеза ХТС к транспортной задаче (Глава 5). Пусть производится т полуфабрикатов, а из них/ путем компаундирования требуется получить п конечных (товарных) продуктов, причем процесс осуществляется непрерывно в потоке, т.е. весь поток 2-ого полупродукта должен быть использован и нет емкости для его накопления й хранения. Формально это может быть выражено в виде уравнения аналогичного зависимости (2): '. , " } , " - - Г . '

. . . „ п - ■ - .........'.....

• 5>у=а<- 1 = 1,...,/и, '(27)

;•■ . V . ■ , V ; ... ;/=*... ; ... ........

где Ху - поток ¡'-ого полупродукта, входящий в состав /-ого продукта, т/ч, ¡^ -

ввод п, (1(1,;)

/= 1,2; г- 1.....я

яь Ь],..., Ь„

/к = <1ик +с12,-(Ь, - к) У

Рисунок 5 - Алгоритм решения задачи методом динамического программирования

заданный общий поток г-ого полупродукта. Задание по выпуску/-ых продуктов, также аналогичное (2), может быть представлено так: .. . - .

, 7 = 1,,..,я, . V..... (28)

1=1 .

где 6, - заданный поток /-ого продукта. Приготовление продуктов рассмотрим на примере схемы выработки - двух сортов ДГ ООО «ПО «Киришинефтеоргсинтез». Известно, что все полупродукты содержат вредную примесь серы с массовой долей л,. Данные о потоках сведены в таблицу: .

i Наименованйе •Расхода,, т/ч Доля серы я,-, %

1 ДТ гидроочищенное 230 ~ 0.035

2 Денормализат .- 110 0.006

3 Бензин отгон 7 0.02

4 Керосиновая фракция 41 0.12

5 ДТ прямогонное 0.836

Пусть из этих полупродуктов необходимо приготовить два сорта экологически чистого ДТ в количестве 288 т/ч с долей серы пе более 0.05% и 120 т/ч с долей серы не более 0.2%. . :

В качестве критерия оптимизации для данной задачи в соответствии с зависимостью (1) выбирается сумма отклонений от заданных долей серы:

5

2 £

7=1

«=1 %

(29)

где Sj — заданное процентное содержание серы в г-ом и 7-ом продуктах.

■ Задача минимизации (29) при условии (27-28) решена как"транспортная. Ее результаты сведены в таблице: ; ,

• ] 1 ^ " 2 а,

1 . 236 . 7 243 0.052

2 37 .73 110 0.006

3 3 4 7 0.02

4 12 10 22 0.12

5 0 26 26 0.832

ь, 288 120 408

.0.05 . 0.2 :

0.0498 0.1995

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

Выводы.

1. На основании анализа транспортной производственной системы определены пути повышения ее эффективности за счет оптимизации структуры и параметров.

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

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

4. Разработан комплекс алгоритмов и программ для решения задачи оптимизации ТПС, внедренный в промышленную эксплуатацию в цехе №21 ООО «ПО«Киришинефтеоргсинтез».

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Якубовская H.H., Викторов В.К., Лисицын Н.В., Кузичкин Н.В. Синтез системы оперативного управления транспортировкой материальных ресурсов. В сборнике Современные проблемы информатизации в прикладных задачах, №4, Воронеж: Научная книга, 2005. — с.144-147.

2. Якубовская H.H. Логическая концепция организации работы транспортного хозяйства нефтеперерабатывающего предприятия. В сборнике Интеллектуализация предприятий нефтехимического комплекса: экономика, менеджмент, технология, инновации, образование. — СПб: СПб ГИЭУ, 2006. — с.390-392.

3. Якубовская H.H., Викторов В.К., Лисицын Н.В. Задача оперативного управления транспортной производственной системой //Проблемы управления. 2006. №1.-с. 44-46.

4. Якубовская H.H., Викторов В.К., Лисицын Н.В. Оценка затрат на перемещение ресурсов в транспортной сети (тезисы). ММТТ-19. Воронеж. Воронежская государственная технологическая академия. 2006. - с.141-142.

5. Якубовская H.H., Викторов В.К., Лисицын Н.В., Кузичкин Н.В. Алгоритм для решения транспортной задачи методом динамического программирования //Системы управления и информационные технологии, №1, 2006. - с.24-26.

6. Викторов В.К,, Ананченко И.В., Якубовская H.H. Новый алгоритм определенияминимальной цены транспортировки товара. Программная реализация разработанного алгоритма в среде Delphi. Свидетельство об отраслевой регистрации разработки №5886 от. 27.03.06 г. Отраслевой фонд алгоритмов и программ-Федеральное агентство по образованию.

7. Якубовская H.H. Динамическое программирование для транспортной задачи с двумя пунктами потребления // Химическая промышленность, т.83 №5, 2006. — с.245-250.

14.11.06 г. Зак. 189-75 РТП ИК «Синтез» Московский пр., 26

Введение.

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

2 Методы решения задач управления транспортной системой.

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

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

2.3 Венгерский метод.

2.4 Итерационные методы для нелинейных транспортных задач.

3 Математическое моделирование производственных операций транспортной системы.

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

3.2 Модель назначения группы транспортных средств для выполнения транспортировки.

4 Программное обеспечение для оптимизации транспортной производственной системы.

4.1 Программа нахождения возможного количества транспортных средств.

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

4.3 Программа решения транспортной задачи.

4.4 Программа решения задачи о назначениях.

5 Сведение задачи синтеза химико-технологической системы к транспортной задаче.

Выводы.

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

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

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

Источниками конкурентных преимуществ являются: оптимизация внутрипроизводственных связей, оптимизация деятельности предприятия во времени, интеграция распределительных сетей и др. Математическую основу моделей составляют аппарат теории вероятностей, математическая статистика, методы исследования операций и методы принятия решений. Необходимо отметить, что эти модели являются абстрактными, имеют большую размерность, носят главным образом качественный характер, что затрудняет получение аналитических решений [28].

Отсюда следует, что основная идея настоящей научной работы заключается в исследовании взаимосвязей качественных оценок стратегического управления и формализованных количественных математических подходов на примере решения сложной производственной задачи оптимизации транспортной производственной системы (ТПС) с использованием методов системного анализа [14-17].

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

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

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

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

Основные научные результаты диссертации:

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

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

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

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

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

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

Диссертационная работа состоит из пяти глав.

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

Вторая глава посвящена методам определения оптимальных путей в транспортной сети. Показано, что для определения оптимальных путей в транспортной сети, представленной в виде неориентированного графа, следует использовать метод Дейкстры или метод динамического программирования. Трудоемкость обоих методов примерно одинаковая и заложена одна и та же вычислительная идея: прямой путь из / в у может оказаться «дороже», чем обходной путь через промежуточные вершины. В качестве унифицированного был выбран один метод динамического программирования.

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

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

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

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

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

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

В качестве основных производственных операций транспортных систем рассматриваются две основные операции: перемещение из пункта к в пункт / в составе пути из /-го пункта транспортной сети в у-ый пункт перемещения и назначение р-ой группы транспортных средств для выполнения ^-ой транспортировки. Для их оценки разработаны соответствующие математические модели.

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Якубовская H.H., Викторов В.К., Лисицын Н.В., Кузичкин Н.В. Синтез системы оперативного управления транспортировкой материальных ресурсов. В сборнике Современные проблемы информатизации в прикладных задачах, №4, Воронеж: Научная книга, 2005. - с. 144-147.

2. Якубовская H.H. Логическая концепция организации работы транспортного хозяйства нефтеперерабатывающего предприятия. В сборнике Интеллектуализация предприятий нефтехимического комплекса: экономика, менеджмент, технология, инновации, образование. - СПб: СПб ГИЭУ, 2006. -с.390-392.

3. Якубовская H.H., Викторов В.К., Лисицын Н.В. Задача оперативного управления транспортной производственной системой //Проблемы управления. 2006. №1,-с. 44-46.

4. Якубовская H.H., Викторов В.К., Лисицын Н.В. Оценка затрат на перемещение ресурсов в транспортной сети (тезисы). ММТТ-19. Воронеж. Воронежская государственная технологическая академия. 2006. - с. 141-142.

5. Якубовская H.H., Викторов В.К., Лисицын Н.В., Кузичкин Н.В. Алгоритм для решения транспортной задачи методом динамического программирования //Системы управления и информационные технологии, №1, 2006. - с.24-26.

6. Викторов В.К., Ананченко И.В., Якубовская H.H. Новый алгоритм определения минимальной цены транспортировки товара. Программная реализация разработанного алгоритма в среде Delphi. Свидетельство об отраслевой регистрации разработки №5886 от 27.03.06 г. Отраслевой фонд алгоритмов и программ. Федеральное агентство по образованию.

7. Якубовская H.H. Динамическое программирование для транспортной задачи с двумя пунктами потребления // Химическая промышленность, т.83, №5, 2006. - с.245-250.

Выводы

1. На основании анализа транспортной производственной системы определены пути повышения ее эффективности за счет оптимизации структуры и параметров.

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

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

4. Разработан комплекс алгоритмов и программ для решения задачи оптимизации ТПС, внедренный в промышленную эксплуатацию в цехе №21 ООО «ПО«Киришинефтеоргсинтез».

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

6. На примере построения оптимальной химико-технологической системы производства дизельных топлив показано, как задача синтеза этой ХТС сводится к транспортной задаче, что подтверждает универсальность разработанных алгоритмов и программ.

Заключение

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

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

1. Сомов В.Е. Стратегическое управление нефтеперерабатывающими предприятиями. - СПб: Химиздат, 1999. - 264с.

2. Ансофф И. Стратегическое управление. М.: Экономика, 1989. - 519с.

3. Ефимов B.C. Стратегия бизнеса. М.: - Финпресс, 1998. - 192с.

4. Ефремов B.C. Классические модели стратегического анализа и планирования: модель Шелл/DPM. Менеджмент в России и за рубежом, сентябрь-октябрь, 1997.-с.62-68.

5. Маркова В.Д., Кузнецова С.А. Стратегический менеджмент. М.: ИНФРА-М, 1999.-90с.

6. Захаров Г.Н. Формирование экономического механизма устойчивогоразвития нефтехимического предприятия: Дис.канд. экон. наук. С

7. Петербургский государственный инженерно-экономический университет, 2002. -183 с.

8. Лисицын Н.В. Оптимизация нефтеперерабатывающего производства. -СПб: ХИМИЗДАТ, 2003. 184 с.

9. Локтаев C.B., Лисицын Н.В. Управление организационными системами. СПб, Химиздат, 2005, -586 с.

10. Моисеев H.H. Математические задачи системного анализа. М.: Наука, 1981.-488 с.

11. Перцовский М.И., Белышев П. А. Комплексная автоматизация промышленного предприятия на примере системы учета и контроля ресурсов нефтедобывающего и нефтепереррабатывающего предприятий, //Мир компьютерной автоматизации, № 6, 2002. с.44-49.

12. Волкова В.Н., Денисов A.A. Основы теории систем и системного анализа. СПб: СПбГТУ, 2003.-520 с.

13. Юдицкий С.А. Технология целевого моделирования бизнес-систем //Приборы и системы управления, №10, 2000. с.76-81.

14. Юдицкий С.А. Сценарно-целевой подход к системному анализу //Автоматика и телемеханика, №4, 2001. с. 163-175.

15. Якубовская H.H., Викторов В.К., Лисицын Н.В. Задача оперативного управления транспортной производственной системой //Проблемы управления. 2006. №1. с. 44-46.

16. Якубовская H.H., Викторов В.К., Лисицын Н.В. Оценка затрат на перемещение ресурсов в транспортной сети (тезисы). ММТТ-19. Воронеж. Воронежская государственная технологическая академия. 2006. с. 141-142.

17. Корягин М.Е. Конкуренция транспортных потоков //Автоматика и телемеханика, №3, 2006. с. 143-151.

18. Кутыркин С.Б., Волчков С.А., Балахонова Н.В. Повышение качества предприятия с помощью информационных систем класса ERP //Методы менеджмента качества, №4, 2000. 8с.

19. Кнопов А.П., Пепеляев В.А. О некоторых непрерывных моделях управления запасами//Кибернетика и системный анализ, №3, 2005.-с. 175178.

20. Галушко В.Г. Об одной модели учета потерь при транспортировке скоропортящихся грузов //Проблемы управления и информатики, №3, 2005. сЛ 23-127.

21. Юдин Д.Б., Гольштейн Е.Г. Задача и методы линейного программирования. М.: Советское радио, 1964. - 736с.

22. Кофман А. Введение в прикладную комбинаторику. М.: Наука, 1975. -479с.

23. Голыитейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. М.: Советское радио, 1969. с.53-56.

24. Кузнецов A.B., Сакович В.А., Холод Н.И. Высшая математика. Минск: Высшая школа, 2004. - 436с.

25. Туревский И.С. Экономика и управление автотранспортным предприятием. М.: Высшая школа, 2005. - 211с.

26. Александров Н.И. Методы и модели стратегического интегрированногоуправления социально-экономическими системами: Дис. докт. экон.наук. СПб государственный университет, 1997. 350с.

27. Лукинский B.C. и др. Логистика автомобильного транспорта. М.: Финстат, 2004.-368с.

28. Химмельблау Д. Прикладное нелинейное программирование. М.: Мир, 1975.-536 с.

29. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.: Мир, 1985509 с.

30. Реклейтис Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике: в 2-х книгах. Кн. 1. М.: Мир, 1986. -352 с.

31. Реклейтис Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике: в 2-х кн. Кн. 2. М.: Мир, 1986.-320 с.

32. Розенброк X., Стори С. Вычислительные методы для инженеров-химиков. М.: Мир, 1968.-444 с.

33. Карманов В.Г. Математическое программирование. М.: ФИЗМАТЛИТ, 2001.-264 с.

34. Козлов В.Н., Колесников Д.Н., Сиднев А.Г. Решение задач математического программирования. СПб: СПбГТУ, 1992. -112 с.

35. Калиткин H.H. Численные методы. М.: Наука, 1978. -512 с.

36. Рейгольд Э., Нивергельд Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. - 476с.

37. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 536с.

38. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. М.: Наука, 1965. - 458с.

39. Романовский И.В. Алгоритм решения экстремальных задач. М.: Наука, 1977.-352с.

40. Хедли Дж. Нелинейное и динамическое программирование. М.: Мир, 1967.-506с.

41. Триус Е.Б. Задача математического программирования транспортного типа. М.: Сов. радио, 1967. с.81-82.

42. Миронов A.A., Цурков В.И. Замкнутые транспортные модели с минимаксным критерием // АиТ, №3, 2002. с.50-61.

43. Хачатурян Н.К. О решениях типа бегущей волны в одной транспортной модели // АиТ, №3,2003. с.137-149.

44. Авен О.И., Ловецкий С.Е., Моисеенко Г.Е. Оптимизация транспортных потоков. М.: Наука, 1985. с.110.

45. Хеллман О. Введение в теорию оптимального поиска. М.: Наука, 1985. с.9-22.

46. Рубенштейн М.И., Сергеев С.И. Математические модели и методы решения задач минимизации транспортных затрат в производственных системах // Итоги науки и техники. Сер. Организация управления транспортом. Т. 12. -М.: ВИНИТИ, 1992. с.3-90.

47. Кравцов М.К., Лукшин Е.В. О целочисленных вершинах многогранника трехиндексной аксиальной транспортной задачи // АиТ, №3. 2004. с.71-79.

48. Афраймович Л.Г., Прилуцкий М.Х. Многоиндексные задачи распределния ресурсов в иерархических системах//АиТ, №6, 2006. с. 194205.

49. Борисов В.И., Гор А.И., Дехтяр Б.А. и др. Автомобиль «Волга» ГАЗ-24. -М.: Машиностроение, 1975. 252с.

50. Якубовская H.H., Викторов В.К., Лисицын Н.В., Кузичкин Н.В. Алгоритм для решения транспортной задачи методом динамического программирования //Системы управления и информационные технологии, №1, 2006. с.24-26.

51. Лисицын Н.В. Оптимизация процессов разделения-смешения //ТОХТ. 2003. Т. 37. №3.-с. 319-323.

52. Сомов В.Е., Садчиков И.А., Шершун В.Г. и др. Стратегические приоритеты российских нефтеперерабатывающих предприятий. М.: ЦНИИТЭнефтехим, 2002. -292 с.

53. Залищевский Г.Д., Поздяев В.В., Лисицын Н.В., Кузичкин Н.В. Оптимальное компаундирование дизельных топлив //Нефтепереработка и нефтехимия. М.: ЦНИИТЭнефтехим, 2002. № 4. -с. 10-14.

54. Лисицын Н.В., Поздяев В.В., Кузичкин Н.В. Оптимальное смешение дизельных топлив //Тезисы докладов конференции «Математические методы в технике и технологиях» ММТТ-15. Тамбов, 2002. Т. 6. -с. 63-65.

55. Кособокова Э.М., Березинец П. А. К разработке стратегии энергосбережения на предприятиях нефтепереработки. //Химия и технология топлив и масел, № 1, 2001.-е. 6-8.

56. Лисицын Н.В., Кузичкин Н.В. Комплекс для получения топливных смесей //Свидетельство на полезную модель № 26350. Офиц. бюл. российского агенства по патентам и товарным знакам «Изобретения. Полезные модели». Москва, № 33, 2002. -с.413.

57. Логинов С.А., Капустин В.М., Луговской А.И. и др. Промышленное производство высококачественных дизельных топлив с содержанием серы 0,035 и 0,05 //Нефтепереработка и нефтехимия. М.: ЦНИИТЭнефтехим, № 11, 2001.-е. 57-61.

58. Вентцель Е.С. Элементы динамического программирования. -М.: Наука, 1964.-176с.

59. Ховард P.A. Динамическое программирование и марковские процессы. -М.: Мир.-192с.

60. Голубков Е.П. Технология принятия управленческих решений. -М.: «Дело и сервис», 2005. -544с.

61. Хемди А.Т. Введение в исследование операций. -М.: Изд. «Вильяме»,2005.-912с.

62. Кнут Д.Э. Искусство программирования, т.1. Основные алгоритмы. -М.: Изд. «Вильяме», 2000. -720с.

63. Кнут Д.Э. Искусство программирования, т.2. Получисленные алгоритмы. -М.: Изд. «Вильяме», 2000. -832с.

64. Кнут Д.Э. Искусство программирования, т.З. Сортировка и поиск. -М.: Изд. «Вильяме», 2000. -720с.

65. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. -М.: МЦНМО. 2000. -960с.

66. Шень А. Программирование: Теоремы и задачи. -М.: МЦНМО, 2004. -296с.

67. Альфред В.А., Хопкрофт Д., Ульман Д.Д. Структуры данных и алгоритмы. М.: Изд. «Вильяме», 2000. - 384с.

68. Андреева Т.А. Программирование на языке Paskal. -M.: Интернет-университет ИТ, Бином, 2006. -240с.

69. Безменов H.A. Turbo Paskal 7.0. Руководство программиста. -М.: Эксмо,2006.-160с.

70. Доменский М.С. Алгоритмизация и программирование на Turbo Paskal. -СПб: Питер, 2004.-237с.

71. Коффман Э.Б. Turbo Paskal. -M.: Изд. «Вильяме», 2002. -896с.

72. Warren R. Learn Object Paskal with Delphi. Wordware Publisting inc. -400p.75. http: www.petroleumrefining.com.

73. Якубовская Н.Н. Динамическое программирование для транспортной задачи с двумя пунктами потребления, т.83. Химическая промышленность, №5, 2006. -с.245-250.

74. Adams С., Peter J.F., at al. Inrestigation of Soybean Oil as a Dissel Fuel Extender: Endurance Tests. //JA OCS, 1983,1574-1579 pp.