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

Пономарев Сергей Евгеньевич

кандидат физико – математических наук, доцент кафедры информационных систем в экономике, Санкт-Петербургский Государственный Инженерно-Экономический

Университет

e-mail: [email protected]

ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА

В статье рассматриваются алгоритмы и программы решения основных оптимизационных задач АСУТП предприятий пищевой, машиностроительной и алюминиево-магниевой промышленности.

Ключевые слова:теория графов, параллельные алгоритмы, рекурсивная процедура.

Оптимизационные задачи автоматизированных систем управления технологией производства (АСУТП) — задачи дискретного программирования, у которых аргументы целевой функции f(x1, x2,……..xn) имеют конечные множества возможных значений.

Конкретная оптимизационная задача АСУТП относится к одному из двух классов.

Для задач первого класса множества возможных значений аргументов xi и xj, (i?j), не пересекаются, и множество допустимых значений аргумента xk зависит от значений аргументов x1, x2,……..xk-1.

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

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

Типичным примером задач второго класса является задача оптимизации стоимости металла товарного вида, входящая в состав АСУТП предприятий алюминиево-магниевой промышленности.

Для решения оптимизационных задач АСУТП нужно запрограммировать процессы построения множества допустимых значений аргументов целевой функции и процессы вычисления и оптимизации значений целевой функции.

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

§1. Алгоритмы и программы расчета и оптимизации себестоимости сложных изделий

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

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

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

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

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

Исходные данные — список деталей, сборочных улов и агрегатов в составе изделия и таблица отношений между деталями, сборочными узлами и агрегатами, где указано, какие детали и в каком количестве входят в состав сборочного узла, какие сборочные узлы и в каком количестве входят в состав агрегата и т.д. Значения элементов таблицы отношений aij, (ji), равно количеству деталей номер i (сборочных узлов номер i) в составе сборочного узла номер j.

Для построения графа комплексного изделия и расчета себестоимости комплексного изделия множество деталей и сборочных узлов в составе изделия нужно упорядочить. Упорядочивание означает разбиение данного множества на классы. К первому классу относятся детали собственного изготовления. Ко второму классу относятся сборочные узлы, изготовленные из деталей первого класса. К третьему классу относятся сборочные узлы, изготовленные из деталей первого класса и сборочных узлов второго класса. К k-тому классу относятся сборочные узлы, изготовленные из деталей первого класса и сборочных узлов k-1-ого класса.

Для решения задачи упорядочивания состава сложного изделия используем таблицу отношений между деталями и сборочными узлами в составе сложного изделия. Обозначим матрицу отношений между деталями и сборочными узлами в составе сложного изделия A. Элементы первого класса — это заголовки нулевых столбцов матрицы A. Затем вычисляем степени матрицы An, (n1), и в матрице An определяем «новые» нулевые столбцы, которые появляются в дополнение к матрице An-1. По номерам этих столбцов определяем их наименования и записываем в качестве элементов n- ого класса. Одновременно вычисляется количество данных столбцов и записывается в качестве элемента массива d(n). Значение элемента массива d(n) равно количеству элементов n – ой группы.

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

Номера элементов первой группы принимают значения от единицы до n(1), где n(1)- количество материалов первой группы. Номера элементов i-ой группы, (1 Применение дискретного программирования для решения оптимизационных задач автоматизированных систем управления технологией производства ,

где n(k)-количество элементов k-ой группы.

Обозначим

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

Номера элементов i-ой группы, (1

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

Построим граф представления структуры сложного изделия: определим множество дуг графа, определим допустимые пути графа и опишем алгоритм построения допустимых путей графа.

Множество вершин графа — множество номеров комплектующих. Все вершины графа распределяются по группам, соответствующим группам комплектующих сложного изделия.

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

Путем, соединяющим вершину k- ой группы Vk с вершиной n- ой группы Vn, (nk), называется последовательность попарно совместимых вершин (Vk, Vk+1, Vk+2….Vn) из групп k, k+1, k+2,…..n.

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

Для реализации параллельного алгоритма построения путей графа последовательные группы материалов объединяются в блоки по n групп. При этом последняя группа k-ого блока совпадает с первой группой k+1-ого блока. Число n определяется производительностью кластера. На каждом кластере независимо от других и параллельно с другими кластерами определяются все пути, соединяющие вершины первой и последней группы блока. Поиск путей на кластере производится в параллельном режиме. На первом элементе кластера определяются пути, выходящие из вершины V1, на втором элементе определяются пути, выходящие из вершины V2, на i-ом элементе определяются пути, выходящие из вершины Vi. После построения путей на каждом блоке на k-ом кластере объединяются пути k-ого и k+1-ого блоков и получаются пути длины 2n. Затем в параллельном режиме объединяются пути двойных блоков и т.д. В результате получаются пути из вершин первой группы в вершины последней.

Пути, соединяющие фиксированную вершину первой группы с номером i с вершинами k- ой группы вычисляем последовательно. Вначале находим пути, соединяющие вершину i с совместимыми с ней вершинами второй группы, и записываем полученные пути в одномерный массив b, элементы которого b(n) являются символьными строками, где перечислены вершины пути, отделяемые друг от друга запятой. Например, для путей второй группы b(n)=i,m, где i- номер вершины из первой группы, m- номер вершины из второй группы. Пути k- ой группы записываются в одномерный массив b, элементы которого

b(n)=n1, n2,…. ni….. nk,

где ni- номер вершины из i — ой группы.

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

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

Для программирования процесса нужно формализовать описанные выше операции. Считаем, что на каждом шаге известны начальный номер элементов k-ой группы — ng количество вершин k-ой группы- n(k), количество путей k-ой группы — p(k) и значения массива путей k-ой группы- b(i), 1ip(k). Нужно пересчитать значения b(i) и определить значение p(k+1), равное числу путей k+1-ой группы.

Вначале текущую версию массива b записываем в массив c и пересчитываем значение начального номера: ng=ng+n(k)+1. Затем по значениям массива c вычисляем новую версию массива b. Для этого выбираем j — ую вершину k+1-ой группы, находим ее номер, равный j+ng, перебираем все пути b(i), находим вершины пути b(i), проверяем по матрице совместимости a совместимость вершин пути b(i) и вершины номер j+n(k)+1. Если все вершины пути b(i) совместимы с вершиной j+n(k)+1, то увеличиваем счетчик на единицу, добавляем к массиву c(i) запятую и номер j+n(k)+1 и получаем новое значение массива b(i). На последнем шаге полученный массив b записываем в файл, имя которого равно номеру вершины первой группы.

Чтобы ускорить процесс расчета и оптимизации себестоимости сложного изделия, по матрице бинарных отношений находим для каждого элемента n k – ой группы количество элементов предыдущей k-1 – ой группы, совместимых с элементом n, и записываем это количество как элемент одномерного массива c(n). Также определяем номера совместимых элементов и записываем их как элементы двухмерного массива nom(n,i), (1?i?c(n)). Полученные данные используем для расчета себестоимости сложного изделия.

Себестоимость блоков сложного изделия вычисляются последовательно. Считаем заданными себестоимости элементов первой группы. Себестоимость элементов k – ой группы вычисляется по значениям себестоимостей S(i) элементов k-1 – ой группы, (k?2). Себестоимость элемента m k – ой группы равна

S(m)=

Где A(m) – множество номеров элементов k – ой группы, совместимых с элементом m, a(i,m) – элемент матрицы бинарных отношений, равный количеству детали i в составе узла m. Для расчета себестоимости S(m) находим i – ое значение массива номеров nom(m,i), (1?i?c(m)), присваиваем его переменной k, определяем элемент матрицы бинарных отношений a(k,m) и добавляем к текущему значению S(m) слагаемое S(k)* a(k,m). Эти операции выполняем для всех 1?i?c(m).

Аналогично определяется расход детали (сборочного узла) Vi.

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

1. Определяются себестоимости деталей собственного изготовления.

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

3. Определяют расхода детали (сборочного узла) Vi по каждому пути графа изделия, проходящему через вершину Vi.

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

§2. Алгоритмы и программы решения задачи оптимизации расхода сырья в процессе производства

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

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

Для постановки и решения задачи нужно описать процессы формирования комплектации производства сырьем и расчета расхода сырья по каждому виду товарной продукции.

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

Считаем, что заданы m видов товарной продукции объемы выпуска Vi, , n групп сырья и для каждой группы с номером k определено значение массива n(k), равное количеству сырья k-ой группы. Кроме того, для каждой группы задана нормативно-справочная таблица, где записаны нормы расхода сырья группы и его цены. Используя эти данные, нужно определить расход определить расход каждого вида сырья в денежном выражении.

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

где n(k)-количество сырья k-ой группы.

Обозначим

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

Тогда номера сырья i-ой группы, (1

В программах для определения совместимости сырья используется двумерный массив a(i,j), элементы которого a(i,j)=1, если материалы i,j- совместимы, и a(i,j)=0, если виды сырья i,j- несовместимы.

В программах сырьевая комплектация представляется символьной строкой, где через запятую перечислены номера совместимых видов сырья разных групп, т.е. сырьевая комплектация- это символьная строка (x1, x2,…. xi … xn), где xi- номер сырья i-ой группы и a(xi, xj)=1, (i?j).

Обозначим расход сырья xi r(xi). Вычислим значение r(xi).

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

где nr(x1,k)- норма расхода сырья x1 на единицу k- ого вида продукции, Vk- объем выпуска k- ого вида продукции.

Для i?2 расход сырья xi r(xi) вычисляется последовательно по формулам

,

где nr(x1, x2,…. xi-1 ,xi)- норма расхода сырья xi, зависящая от x1,x2.. xi-1,

r(xi-1)- расход сырья xi-1.

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

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

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

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

Расчет расхода сырья производится по формулам:

,

где nr(x1, x2,…. xi-1,xi)- норма расхода сырья xi, зависящая от x1,x2.. xi-1,

r(xi-1)- расход сырья xi-1.

Целевая функция задачи оптимального обеспечения производства сырьем f(x1, x2,…. xi … xn)- сумма расходов сырья x1, x2,…. xi … xn в денежном выражении и стоимости дополнительных работ, обусловленных применением сырья x1, x2,…. xi … xn.

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

где r(xi)- расход сырья xi,

c(xi) — наименьшая цена сырья xi, вычисленная с учетом удельных затрат доставки сырья и затрат по доведению качества сырья до уровня, соответствующего техническим условиям производства,

sr(xi) – стоимость дополнительных работ, обусловленных применением сырья xi

Формулы расчета расхода r(xi) приведены выше.

Нужно найти наименьшее значение функции

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

изменяя значения целочисленных переменных xi, (1?i?n), удовлетворяющих неравенствам

и условиям совместимости материалов a(xi, xj)=1, (i?j).

Здесь ng(xi)-нижняя граница номеров материалов i-ой группы, vg(xi)-верхняя граница номеров материалов i-ой группы.

Целевая функция задачи оптимизации расхода сырья в процессе производства f(x1, x2,…. xi … xn) вычисляется рекурсивно, поэтому оптимизационная задача является задачей динамического программирования с конечным множество допустимых значений аргументов целевой функции, распределенных по непересекающимся классам.

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

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

Множество вершин графа — множество номеров сырья. Все вершины графа распределяются по n группам, соответствующим группам сырья.

Дуги графа соединяют вершины, соответствующие совместимым видам сырья разных групп.

Путем, соединяющим вершину k- ой группы Vk с вершиной n- ой группы Vn, (nk), называется последовательность попарно совместимых вершин (Vk, Vk+1, Vk+2….Vn) из групп k, k+1, k+2,…..n. Длина пути определяется как сумма наименьших расходов сырья Vk, Vk+1, Vk+2….Vn, вычисляемых для каждого сырья Vi по расчетной таблице.

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

Производится последовательный пересчет кратчайших путей, соединяющих вершины первой и k-ой группы, в кратчайшие пути, соединяющие вершины первой и k+1-ой группы.

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

Вычисляем длины полученных путей и находим наименьшее значение длин полученных путей. Определяем путь с наименьшей длиной и записываем его вершины. Получаем кратчайший путь, соединяющий вершину первой группы и выбранную вершину k+1- ой группы. В конце выводим значения кратчайших путей, соединяющих вершины первой и последней группы, в ячейках электронной таблицы и определяем среди них оптимальные, обеспечивающие наименьший расход сырья. Программа пересчета кратчайших путей описана в работе [2].

§3. Алгоритмы и программы решения задачи оптимизации стоимости металла товарного вида

Основной задачей АСУТП предприятий алюминиево-магниевой промышленности является задача оптимизации выручки от реализации продукции за счет рациональной выливки металла. Так как распределение металла товарного вида зависит от последовательности выливки (слияния), то и выручка от реализации товарной продукции также зависти от последовательности выливки металла.

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

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

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

Для алюминиевого производства количество электролизеров в цехе кратно 4 и равно 4k. Обычно k=7. Нумеруем электролизеры исходными данных являются массивы концентрации магния и криолита в каждом электролизере, таблица определения сорта металла в зависимости от концентрации магния и криолита и цены тонны металла товарного вида каждого сорта.

Процедура получения оптимальной выливки определяет последовательность номеров электролизеров, задающих оптимальную выливку. Данная последовательность представляет собой массив натуральных чисел, больше либо равных единицы, меньше либо равных 4n, у которого первые четыре элемента – номера электролизеров, сливаемых в первую очередь, вторые четыре элемента- номера электролизеров, сливаемых во вторую очередь и т.д. При этом выручка от реализации металла товарного вида, полученного в результате данной выливки должна получиться наибольшей. Обозначим данный массив b(1:4n). Элементы массива b — это допустимые значения аргументов целевой функции. Значения целевой функции определяются как сумма стоимостей металла товарного вида, полученного выливкой электролизеров с номерами b(4k+1), b(4k+2), b(4k+3), b(4k+4).

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

Предположим, что на k-ом шаге получили четыре значения элементов массива b: b(4k-3)

Значение b(4k+1) должно быть больше b(4k-3). Поэтому сначала присваиваем b(4k+1) значение b(4k-3)+1. Проверяем, совпадает ли b(4k+1) с каким-нибудь предыдущим значением элементов массива b. Если значение b(4k+1) совпадает с каким-нибудь предыдущим значением элементов массива b, то увеличиваем b(4k+1) на единицу (b(4k+1)= b(4k+1)+1) и выполняем проверку на совпадение нового значения b(4k+1) с предыдущими значениями элементов массива b. Продолжаем данные операции, пока не получим первое значение b(4k+1), отличное от предыдущих значений элементов массива b. После этого определяем значение b(4k+2), большее, чем b(4k+1) и b(4k-2), и т.д. Для пересчета значений элементов массива b нужно задать четыре начальных значения: b(1)=1, b(2)=n2, b(3)=n3, b(4)=n4. Пересчет значений элементов массива b производится на базе кластеров и мультипроцессорных вычислительных комплексов. При этом на первом процессоре (компьютере) выполняется пересчет значений для 2?n2?m, на первом процессоре (компьютере) выполняется пересчет значений для m+1?n2?2m и т.д. На VBA процесс пересчета записывается следующим образом:

b(4*k+1) = b(4*k-3)+1 : M:i=2 : while b(i) b(4*k+1) and i

i = i+1 wend : if i

b(4*k+1) = b(4*k+1)+1 : goto M : end if

if I = 4*k+1 then

b(4*k+2) = max(b(4*k+1), b(4*k-2))+1

M:i=2 : while b(i) b(4*k+2) and i

i = i+1 wend : if i

b(4*k+2) = b(4*k+2)+1 : goto M : end if

if I = 4*k+1 then

b(4*k+3) = max(b(4*k+3), b(4*k-1))+1

M:i=2 : while b(i) b(4*k+3) and i

i = i+1 wend : if i

b(4*k+3) = b(4*k+3)+1 : goto M : end if

if I = 4*k+1 then

b(4*k+4) = max(b(4*k+4), b(4*k))+1

M:i=2 : while b(i) b(4*k+4) and i

i = i+1 wend : if i

b(4*k+4) = b(4*k+4)+1 : goto M : end if : end if : end if : end if

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

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

Опишем алгоритм метода. Предположим, что для всех 1?i?k известна процедура построения оптимальной выливки F(i). Найдем F(k+1).

Выбираем номера 4k+1, 4k+2, 4k+3, 4k+4. Применяя известную процедуру F(k), получаем из оставшихся номеров оптимальную последовательность выливки и находим первую версию массива b. Улучшить выливку можно только попарно переставляя номера 4k+1, 4k+2, 4k+3, 4k+4 с оставшимися. Если в результате перестановок выливка не улучшается, то задача решена и первая версия массива b является оптимальной. Иначе выбирается самая эффективная перестановка и получаются две четверки номеров, за счет которых можно улучшить выливку. Таким образом, на каждом шаге получается либо оптимальная выливка, либо восемь номеров, за счет которых можно улучшить выливку. Улучшение выливки производится за счет перестановки данных номеров с остальными. Так как каждое улучшение дает существенный рост выручки, то число операций поиска оптимального плана конечно. Каждый шаг рекурсивной процедуры добавляет ck2 логических операций. Алгоритм является выполнимым за реальное время. Рекурсивные процедуры можно реализовать на языках высокого уровня или в виде макропрограммы, которая автоматически формирует полный текст процедуры, зная правило расширения текста программы.

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

Выливка – это сочетание четырех элементов из n, т.е., выливка — последовательность натуральных чисел 1? b(4k-3)

Множество вершин графа — множество номеров сочетаний. Все вершины графа распределяются по группам, соответствующим группам сочетаний. Дуги графа соединяют вершины, соответствующие совместимым сочетаниям из соседних групп, т.е., дуга соединяет вершины Vk и Vm, (mk), если они совместимы и среди вершин промежуточных групп нет ни одной, совместимой с вершиной Vk. Начало дуги — вершина с меньшим номером, конец дуги — вершина с большим номером.

Путем, соединяющим вершину k- ой группы Vk с вершиной n- ой группы Vn, (nk), называется последовательность попарно совместимых вершин (Vk, Vk+1, Vk+2….Vn) из групп k, k+1, k+2,…..n. Т.е., путь – это последовательность элементов массива b(1:4n) с номерами, большими или равными 4k, , меньшими или равными 4n. Массив b(1:4n) определен на стр. 10. Пути называются эквивалентными, если они состоят из одних и тех же значений массива b(1:4n). Длина пути – сумма стоимостей металла товарного вида, полученного выливками, соответствующими вершинам графа.

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

Литература

1. Ростовцева Т.В., Фомин В.И. Постановка задачи оптимизации затрат материально-технического снабжения строительно-монтажных работ// Современные проблемы прикладной информатики: сб.науч. трудов научно-практической конференции по современным проблемам прикладной информатики. 19-20 мая 2009 года. СПб.: Изд-во Политехнического. Ун-та, 2009 г. с. 90-93

2. Пономарев С.Е., Лукиных О.М. Применение алгоритмов теории графов для оптимизации строительства магистральных нефтепроводов// Современные проблемы прикладной информатики: сб.науч. трудов научно-практической конференции по современным проблемам прикладной информатики. 25-27 мая 2011 года. СПб.: Изд-во Политехнического. Ун-та, 2011 г. с. 117-120

Расчет (построение) сетевого графика


Похожие статьи.

Понравилась статья? Поделиться с друзьями: