WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 ||

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

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

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

dkl = k0 + k1 v + k2 v2 skl cT /100, (14) ( ) где k0, k1, k2 – коэффициенты, v – скорость, skl – расстояние между пунктами k и l, сТ – стоимость топлива.

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

(16) T = 6.2 - 0.051 v + 0.00083 vХотя это приближенная модель с относительной ошибкой 20-25%, она отражает реальность и может быть использована для оценки энергетических затрат на транспортировку.

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

epq = cp xq + al sq ( ) lGp (17) q = i -1 m + j; i 1, 2;= j 1, 2,=, 4, ( ) где сq – стоимость q-ой транспортировки, хq – объемы транспортировок, sq – расстояние, al – коэффициент амортизации. Задача назначения решена с помощью разработанной программы, реализующей венгерский алгоритм.

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

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

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

n-Q+m np = cn (18) m=Это число рассчитывается с помощью рекуррентной формулы n - m +m m-cn = cn0 (19) =, m 1,K,n - Q +1; cn =m Разработанная программа формирует nР сочетаний, которые запоминаются в массиве 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н по рекуррентной формуле:

lk = p k, p k +1,l= k n - 2,K,( ( ) ) k +(20) ln-1 = p n -1, jk ( ) Результат расчетов (минимальный путь) выводится в прямом порядке:

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

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

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

fi j = minj g1i ki + g2i bi -ki + fi-1 j - ki ( ) { ( ) ( ) ( ) } 0ki (21) i =1,K,n 0 j af0 j = g11 j + g12 b1 - j ( ) ( ) ( ) (22) Условие замкнутости записывается так:

n a1 + a2 = (23) bi i=Возможны два варианта реализации компьютерной программы по алгоритму (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-ом шаге запоминаются оптимальные решения к(i, j): сколько ресурса выделяется i-ому потребителю, если в первом источнике осталось количество ресурса равное j. Решалась следующая задача:

i 1 2 3 4 5 6 ai j 1 5 6 1 3 6 3 2 3 5 4 2 1 2 bj 15 20 25 11 13 21 Решение, полученное по первому варианту программы, имеет вид:

i 1 2 3 4 5 6 2 к1i 0 0 25 0 0 == k = 25 < a1 40 g 1ili i=1 l=1 i=15 20 0 11 13 2i С помощью второго варианта получается другое решение:

i 1 2 3 4 5 6 2 к1i 0 15 25 0 0 k = 40 gli = 1i i=1 l =1 i=к2i 15 5 0 11 13 Объяснение различий в том, что замкнутая задача не обладает марковским свойством независимости оптимального решения на i-ом шаге от предистории, решений на предыдущих шагах от i – 1 до 1. Действительно, чтобы удовлетворить ограничениям типа равенства n (24) k = al l =1,K,m li i=необходимо на i-ом шаге, когда количество ресурса в l-ом источнике равно j, определять к(i, j) как разность между j и уже израсходованным ресурсом на оптимальной траектории к(l, j) для l = i – 1, …, 1:

k i, j = j - k l, jl, ( ) (25) ( ) l=i-где оптимальное jl находится по рекуррентной формуле jl-1 = jl -k l, jl l = i,K,2.

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

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

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

n (27) x = ai i =1,K,m, ij j=где xij – поток i-ого полупродукта, входящий в состав j-ого продукта, т/ч, ai – ввод n, d(l, i) fк = d1i·к +d2i·(bi – к)+ l = 1, 2; i = 1,…, n + f (j-к) a1, b1,…, bn fк > fm i = Да Да fm = fк i = n f1(j) = fк к(i, j) = к Да j = к = к + 1 к < кк кк = j Да i = n j > bi Да Да j = j + 1 j < aкк = bi j = fm = f(j) = f1(j) к = Да j < aj = j + ji-1 = ji - к(i, ji) s = к Да i = n-l = i-1 i = i - 1 i > Да i = i - s = s + к(l, j-s) вывод f1(a1) Да вывод к(i, ji) l > l = l - fn = к(n, a1) i = 1,…,n s < j стоп i = n Да к = j - s Рисунок 5 – Алгоритм решения задачи методом динамического программирования заданный общий поток i-ого полупродукта. Задание по выпуску j-ых продуктов, также аналогичное (2), может быть представлено так:

m j =1,K,n, (28) x = bj ij i=где bj – заданный поток j-ого продукта. Приготовление продуктов рассмотрим на примере схемы выработки двух сортов ДТ ООО «ПО «Киришинефтеоргсинтез». Известно, что все полупродукты содержат вредную примесь серы с массовой долей si. Данные о потоках сведены в таблицу:

i Наименование Расход ai, т/ч Доля серы si, % 1 ДТ гидроочищенное 230 0.2 Денормализат 110 0.3 Бензин отгон 7 0.4 Керосиновая фракция 41 0.5 ДТ прямогонное – 0.Пусть из этих полупродуктов необходимо приготовить два сорта экологически чистого ДТ в количестве 288 т/ч с долей серы не более 0.05% и 120 т/ч с долей серы не более 0.2%.

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

2 si (29) b xij - sj, j=1 i=1j где si, sj – заданное процентное содержание серы в i-ом и j-ом продуктах.

Задача минимизации (29) при условии (27-28) решена как транспортная.

Ее результаты сведены в таблице:

i 1 2 ai si j 1 236 7 243 0.2 37 73 110 0.3 3 4 7 0.4 12 10 22 0.5 0 26 26 0.bj 288 120 s3 0.05 0.j sp 0.0498 0.j Таким образом, на примере приготовления дизельных топлив показано как химико-технологическая задача может быть сведена к транспортной и решена методом, разработанным для решения транспортной задачи.

Выводы.

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

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

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ 1. Якубовская Н.Н., Викторов В.К., Лисицын Н.В., Кузичкин Н.В. Синтез системы оперативного управления транспортировкой материальных ресурсов.

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

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

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

2006. №1. – с. 44-46.

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

Воронежская государственная технологическая академия. 2006. – с.141-142.

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

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

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

– с.245-250.

Pages:     | 1 ||






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»