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

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

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

Институт

e-mail: tayshea@mail.ru

ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ Автоматических СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА

В статье рассматриваются методы и программки решения главных оптимизационных задач АСУТП компаний пищевой, машиностроительной и алюминиево-магниевой индустрии ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА.

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

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

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

Для задач первого класса огромного количества вероятных ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА значений аргументов xi и xj, (i≠j), не пересекаются, и огромное количество допустимых значений аргумента xk находится в зависимости от значений аргументов x1, x2,……..xk-1.

Для задач второго класса огромного количества вероятных значений у всех аргументов одно и тоже. Огромное количество допустимых значений аргументов мотивированной функции представляет собой объединение конечных ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА непересекающихся множеств с схожим количеством частей, равным k. Для задач второго класса огромное количество допустимых значений аргументов мотивированной функции определяется рекурсивно. Представим, что найдены m*k допустимых значений аргументов мотивированной функции. Последующая группа k допустимых значений аргументов мотивированной функции определяется так, что ее элементы не равны ранее ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА отысканным и обеспечивают среднее значение мотивированной функции.

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

Обычным примером задач второго класса является задачка оптимизации цены металла товарного ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА вида, входящая в состав АСУТП компаний алюминиево-магниевой индустрии.

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

Для решения задач первого класса используются параллельные методы и программки, подобные методам и программка теории графов. Для ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА решения задач второго класса используются рекурсивные методы и программки, подобные программкам формирования комбинаторных структур (сочетаний, перестановок, размещений).

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

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

Всеохватывающее изделие имеет иерархическую структуру. Состоит из агрегатов, которые состоят из ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА сборочных узлов, сборочные узлы состоят из других узлов и деталей и т.д.

Высчитать себестоимость сложного изделия можно только по его структуре. Структуру всеохватывающего изделия представляют в виде нацеленного графа и по графу вычисляют количество деталей в составе сборочных узлов и их себестоимость, количество сборочных узлов в составе изделия ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА и их себестоимость и т.д.

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

Для автоматизации расчета себестоимости всеохватывающих изделий необходимо создать методы ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА и программки построения графа структуры изделия и вычислить по графу структуры изделия количество деталей в составе сборочных узлов и их себестоимость, количество сборочных узлов в составе изделия и их себестоимость и т.д.

Начальные данные - перечень деталей, сборочных улов и агрегатов в составе изделия и таблица отношений меж деталями, сборочными ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА узлами и агрегатами, где обозначено, какие детали и в каком количестве входят в состав сборочного узла, какие сборочные узлы и в каком количестве входят в состав агрегата и т.д. Значения частей таблицы отношений aij, (j>i), равно количеству деталей номер i (сборочных узлов номер i) в составе ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА сборочного узла номер j.

Для построения графа всеохватывающего изделия и расчета себестоимости всеохватывающего изделия огромное количество деталей и сборочных узлов в составе изделия необходимо упорядочить. Упорядочивание значит разбиение данного огромного количества на классы. К первому классу относятся детали собственного производства. Ко второму классу относятся сборочные узлы, сделанные из деталей первого класса. К ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА третьему классу относятся сборочные узлы, сделанные из деталей первого класса и сборочных узлов второго класса. К k-тому классу относятся сборочные узлы, сделанные из деталей первого класса и сборочных узлов k-1-ого класса.

Для решения задачки упорядочивания состава сложного изделия используем таблицу отношений меж деталями и ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА сборочными узлами в составе сложного изделия. Обозначим матрицу отношений меж деталями и сборочными узлами в составе сложного изделия A. Элементы первого класса - это заглавия нулевых столбцов матрицы A. Потом вычисляем степени матрицы An, (n>1), и в матрице 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, (n>k), именуется последовательность попарно совместимых вершин (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 с совместимыми с ней верхушками 2-ой группы, и записываем приобретенные пути в одномерный массив b, элементы которого b(n) являются ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА символьными строчками, где перечислены верхушки пути, отделяемые друг от друга запятой. К примеру, для путей 2-ой группы b(n)=i,m, где i- номер верхушки из первой группы, m- номер верхушки из 2-ой группы. Пути 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. Методы и программки решения задачки оптимизации ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА расхода сырья в процессе производства

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

Основную сложность дилемме присваивает ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА тот факт, что в процессе производства норма расхода определенного сырья из определенной группы находится в зависимости от выбора сырья других групп.

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

По технологии производства определяются группы сырья и перечень сырья каждой ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА группы. Группы упорядочивают. К первой группе относятся виды сырья, нормы расхода которых зависят только от выпускаемой продукции, и для каждого вида продукции определяются как расход сырья на единицу объема выпуска продукции. Ко 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-ой группы определяется после того как вычислены расходы сырья первой, 2-ой, …, i-1-ой групп. Для ускорения поочередных вычислений используются конвейерные системы. В отличие от параллельных систем, в ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА конвейерных системах любая программка по окончанию операции передает результаты вычислений последующей программке для выполнения последующей операции и воспринимает результаты работы предшествующей программки, для которых производится текущая операция.

В конвейерных системах, используемых для расчета расхода сырья, 1-ая программка определяет расход сырья первой группы, сразу 2-ая программка вычисляет расход сырья 2-ой группы ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА по результатам, которые ей передала до того 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, x ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА2,…. 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, (n>k), именуется последовательность попарно совместимых вершин (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 электролизеров в одну емкость ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА и после затвердевания получают алюминий товарного вида. Сорт алюминия товарного вида находится в зависимости от концентрации магния и криолита. Концентрация магния для алюминия товарного вида находится как средне-арифметическое концентраций этих веществ в сливаемых электролизерах.

Рассредотачивание алюминия товарного вида по сортам находится в зависимости от плана выливки, т ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА.е. от того, какие электролизеры сливали сначала, во вторую, в третью и т.д.

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

Для дюралевого производства количество электролизеров в цехе кратно 4 и равно 4k. Обычно k=7. Нумеруем электролизеры начальными данных являются массивы концентрации ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА магния и криолита в каждом электролизере, таблица определения сорта металла зависимо от концентрации магния и криолита и цены тонны металла товарного вида каждого сорта.

Процедура получения хорошей выливки определяет последовательность номеров электролизеров, задающих лучшую выливку. Данная последовательность представляет собой массив натуральных чисел, больше или равных единицы, меньше или равных 4n ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА, у которого 1-ые четыре элемента – номера электролизеров, сливаемых сначала, 2-ые четыре элемента- номера электролизеров, сливаемых во вторую очередь и т.д. При всем этом выручка от реализации металла товарного вида, приобретенного в итоге данной выливки должна получиться большей. Обозначим данный массив 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. Продолжаем данные операции, пока не ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА получим 1-ое значение 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<= 4*k

i = i+1 wend : if i<= 4*k then

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<= 4*k

i = i+1 wend : if i<= 4*k then

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<= 4*k

i = i+1 wend : if i<= 4*k then

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<= 4*k

i = i+1 wend : if i<= 4*k then

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 с оставшимися. Если в итоге перестановок выливка не улучшается, то задачка решена и 1-ая версия массива b является хорошей. По другому выбирается самая действенная перестановка и получаются две четверки номеров, за счет которых можно сделать лучше выливку. Таким макаром, на каждом ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА шаге выходит или лучшая выливка, или восемь номеров, за счет которых можно сделать лучше выливку. Улучшение выливки делается за счет перестановки данных номеров с остальными. Потому что каждое улучшение дает значимый рост выручки, то число операций поиска рационального плана естественно. Каждый шаг рекурсивной процедуры добавляет ck2 логических операций. Метод является ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА выполнимым за реальное время. Рекурсивные процедуры можно воплотить на языках высочайшего уровня либо в виде макропрограммы, которая автоматом сформировывает полный текст процедуры, зная правило расширения текста программки.

Задачку оптимизации цены металла товарного вида можно решить графовым способом. Построим граф задачки, определим огромное количество дуг графа, определим допустимые пути графа ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА, введем понятие длины пути и опишем метод построения допустимых путей графа.

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

Огромное количество вершин графа - огромное количество номеров сочетаний. Все верхушки ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА графа распределяются по группам, подходящим группам сочетаний. Дуги графа соединяют верхушки, надлежащие совместимым сочетаниям из примыкающих групп, т.е., дуга соединяет верхушки Vk и Vm, (m>k), если они совместимы и посреди вершин промежных групп нет ни одной, совместимой с верхушкой Vk. Начало дуги - верхушка с ПРИМЕНЕНИЕ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЕЙ ПРОИЗВОДСТВА наименьшим номером, конец дуги - верхушка с огромным номером.

Методом, соединяющим верхушку k- ой группы Vk с верхушкой n- ой группы Vn, (n>k), именуется последовательность попарно совместимых вершин (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


primenenie-vertera-gel-v-kosmetologii-piling-i-ochishenie.html
primenenie-video-i-zvukozapisi-pri-kriminalisticheskoj-deyatelnosti.html
primenenie-vspomogatelnih-reproduktivnih-tehnologij.html