Алгоритм формирования материального отчета об использовании материала цехом за месяц

МИНОБРНАУКИ РОССИИ

 

Федеральное государственное бюджетное  образовательное учреждение

высшего профессионального образования

«Чувашский государственный университет  имени И.Н.Ульянова»

 

 

 

 

Факультет дизайна и компьютерных технологий

 

Кафедра компьютерных технологий

 

 

 

 

 

 

КУРСОВАЯ РАБОТА

 

По дисциплине

«Теоретические основы автоматизированного  управления»

 

По теме: «Алгоритм формирования материального отчета об использовании материала цехом за месяц»

 

 

 

 

 

 

 

 

 

Выполнил: студент гр. ЗДиКТ 24-10

 

Никитин А.С.

 

Проверил: ст.преподаватель

       Стаценко Е.Ф.

 

 

 

 

 

 

 

 

 

 

Чебоксары 2012

 

Содержание

Введение………………………………………………………………………..3

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

     определенности…………………………………………………………… 4

2. Методы многокритериальной оптимизации…………………………..6
0. Метод главного критерия………………………………………………6
0. Метод линейной свертки……………………………………………………….7
0. Метод максиминной свертки…………………………………………..8
3. Максиминные стратегии………………………………………………..12
4. Метод линейной свертки и главного критерия. Лексикографическая оптимизация………………………………………………………………20
0. Метод линейной свертки и главного критерия…………...…………20
0. Лексикографическая оптимизация…………………...………………26

Заключение………………………………………………………………...29

Список использованной литературы………………………………….30

 

Введение

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

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

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

 

 

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

Рассматривается следующая  модель задачи ПР:

• X— множество альтернатив;
• Y—  множество исходов;
• : Y R,i = 1,..., m — множество показателей качества (критериев);
• : X Y — детерминистская функция, отображающая множество альтернатив во множество исходов. (Здесь R — множество вещественных чисел.)

Таким образом, мы здесь предполагаем, что каждому решению х X соответствует единственный элемент у Y, где у = (х). "Качество" или "полезность" исхода у, а тем самым и соответствующего решения x оценивается несколькими (т) числами в соответствии с зависимостями . По-прежнему предполагаем, что каждую из функций требуется максимизировать.

С помощью суперпозиции

мы имеем возможность  непосредственно оценивать качество самого решения  x и работать с векторным отображением.

Более того, задание бинарного  отношения предпочтения R'; на множестве исходов Y индуцирует соответствующее бинарное отношение R" на множестве X. Именно:

Соответственно возникает  бинарное отношение R" во множестве оценок :

Где Поэтому в детерминистском случае (в условиях определенности) отношения предпочтения могут задаваться в любом из указанных трех множеств: X,Y,F. Далее в качестве основного отображения будет рассматриваться отображение

и соответственно системы  предпочтений будут задаваться во множествах X,F.

В практических задачах  часто непосредственно задается отображение J и, по сути, Y= F, т. е. в качестве исходов выступают сами оценки .

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

Мы здесь сделали  еще одно уточнение: . То есть мы предполагаем, что все альтернативы или решения параметризованы и каждому из решений соответствует точка , x=( ). И, наконец, вместо обозначений мы снова вернемся к обозначениям . Множество X называется множеством допустимых значений и в разделах, посвященных многокритериальным задачам, будет обозначаться через D.

 

 

 

 

 

 

 

 

 

 

 

2. Методы многокритериальной оптимизации

 

Рассматривается задача многокритериальной оптимизации вида

(2.1)

Таким образом, задано m функций или функционалов , отображающих множество D n-мерных векторов х =( ) во множество вещественных чисел R. Здесь предполагается, что выбор оптимальных значений х производится не во всем n-мерном пространстве , а лишь в пределах некоторого его подмножества D. Например, можно интерпретировать задачу (2.1) как задачу оптимального выбора параметров некоторой системы (например, некоторого программного комплекса или перспективного плана развития фирмы), качество функционирования которой оценивается показателями . В этом случае ограничение отражает наши технологические и иные возможности реализации тех или иных значений x_i. Кроме того, часть ограничений может формироваться на основе имеющейся априорной информации, позволяющей исключить из рассмотрения заведомо неудачные варианты х.

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

 

2.1 Метод главного критерия.

 

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

            (2.2)

Формально получили более  простую задачу поиска максимума  функционала f₁ на новом допустимом множестве D'. Добавились ограничения вида показывающие, что мы согласны не добиваться максимальных значений для функционалов сохраняя требование их ограниченности снизу на приемлемых уровнях. Важно понимать, что переход от задачи (2.1) к задаче (2.2) вовсе не есть переход от одной эквивалентной задачи к другой. Произошло существенное изменение исходной постановки задачи, которое в каждой конкретной ситуации требует отдельного обоснования. Мы еще вернемся далее к методу главного критерия и его анализу с позиций оптимальности по Парето. Здесь же отметим, что применение этого метода на интуитивном уровне обычно наталкивается на трудности, связанные с возможным наличием нескольких "главных" критериев, находящихся в противоречии друг с другом. Кроме того, не всегда ясен алгоритм выбора нижних границ Их необоснованное задание может привести, в частности, к пустому множеству D'.

 

2.2 Метод линейной свертки.

 

Это наиболее часто применяемый  метод "скаляризации" (свертки) задачи (2.1), позволяющий заменить векторный критерий оптимальности на скалярный Он основан на линейном объединении всех частных целевых функционалов в один: 

     (2.3)

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

 

2.3 Метод максиминной свертки.

 

Обычно применяется  в форме

Здесь, в отличие от метода линейной свертки, на целевой функционал J(x) оказывает влияние только тот частный критерий оптимальности, которому в данной точке х соответствует наименьшее значение соответствующей функции f (x). И если в случае (2.3), вообще говоря, возможны "плохие" значения некоторых за счет достаточно "хороших" значений остальных целевых функционалов, то в случае максиминного критерия производится расчет "на наихудший случай", и мы по значению J(x) можем определить гарантированную нижнюю оценку для всех функционалов f (x). Этот факт расценивается как преимущество максиминного критерия перед методом линейной свертки.

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

      (2.4)

где весовые коэффициенты удовлетворяют требованиям (2.3).

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

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

    (2.5)

Здесь функции интерпретируются как частные показатели качества функционирования системы; — вектор параметров, подлежащих выбору; — допустимые верхние границы для заданных показателей качества (так называемые контрольные показатели). К форме (2.5) очевидным образом приводятся и обратные неравенства z_k(x) > s_k. Для этого достаточно положить

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

      (2.6)

Имеем, следовательно, многокритериальную задачу максимизации всех запасов:

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

При наличии весовых  коэффициентов имеем задачу

    (2.7)

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

    (2.8)

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

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

         (2.9)

причем выбираем много большим, чем , i = 2, ..., m. Выбор достаточно большого весового коэффициента приводит к тому, что, с одной стороны, при нарушении первого неравенства

      (2.10)

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

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

 

 

 

3. Максиминные стратегии

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

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

       (2.11)

где хотя бы одно из неравенств (2.11) — строгое. И аналогично под  слабо эффективным решением мы понимаем решение, которое не может быть улучшено одновременно по всем показателям. На рис. 2.1 слабо эффективным решениям соответствуют "северная, северо-восточная и восточная части границы" множества достижимости f(D) (f(D) — это образ множества D для векторного отображения

Иначе говоря, в данном примере множество слабо эффективных  оценок S(f) совпадает с множеством Множество P(f) эффективных оценок равно и совпадает с "северо-восточной границей" множества f(D).

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

Справедлива следующая  теорема.

Теорема 2.1. Пусть заданы произвольные числа Тогда решение задачи

    (2.12)

при любых фиксированных  есть слабо эффективный вектор. Наоборот, любой слабо эффективный вектор может быть получен как решение задачи (2.12) при некоторых и i = 1,..., т.

Доказательство. Прямое утверждение теоремы докажем от противного. Пусть х° есть решение задачи (2.12) и существует вектор х' D, для которого

что эквивалентно предположению  о том, что вектор х° не является слабо эффективным. Тогда для любых наборов будем иметь

и, следовательно,

а это противоречит предположению  о том, что х° есть решение задачи (2.12). Прямое утверждение теоремы доказано.

Докажем обратное утверждение. Пусть х°— слабо эффективный вектор:

 Это означает, что не существует  другого вектора х', для которого

      (2.13)

( —для всех номеров i= 1,..., m).

По условию теоремы  заданы такие { }, что . Введем числа

и покажем, что

    (2.14)

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

Из (2.13) следует, что для любого вектора х', отличного от х°, будет существовать такой номер для которого

       (2.15)

(это прямое следствие  слабой эффективности векторах  ). Из (2.15) получаем:

(напоминаем, что неравенства  можно умножать на положительные  числа ). Но тогда и

Таким образом, доказано, что для любого отличного от ,

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

Замечание 2.1

Если слабо эффективное  решение получено как решение задачи (2.12) при каком-то наборе коэффициентов то, очевидно, это же решение будет достигаться при любом наборе где — произвольное положительное число. Поэтому можно считать, что всегда выполнено условие нормировки:

    (2.16)

В противном случае вместо коэффициентов а, мы будем рассматривать  другие коэффициенты:

В силу приведенного замечания  будем далее предполагать, что  условие (2.16) всегда выполнено.

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

выполнено условие f_i> t_i при t_i- 0. Поэтому далее вместо задачи (2.12) будем рассматривать задачу

Обозначим множество  решений задачи (2.17) при фиксированном  наборе коэффициентов а через 

Согласно доказанной теореме, множество

совпадает с множеством слабо эффективных решений:

Дадим геометрическую иллюстрацию  доказанному утверждению для  случая двух целевых функционалов . Имеем

Если рассматривать  указанную зависимость в пространстве критериев, то получим функцию

Построим линии уровня (линии постоянного значения) функции  Ф на плоскости ( )- Для этого рассмотрим прямую L, заданную уравнением

при некотором фиксированном  наборе . График прямой показан на рис. 2.2.

 

Рис. 2.2. Линии уровня функции минимума

 

В любой точке этой прямой, например, в точке будем иметь При смещении из точки а вправо параллельно оси получим Аналогичная ситуация наблюдается и при перемещении вверх из точки а параллельно оси ординат: будем иметь Поэтому, согласно определению функции Ф, ее линия уровня, соответствующая значению будет совпадать с "уголком" (а'а а") с вершиной в точке a, показанным на рис. 2.2 (естественно, данную линию уровня целесообразно рассматривать только в пределах множества достижимостиf(D)). Следовательно, во всех точках отрезков [а', а] и [а, а'] функция Ф будет иметь одно и то же значение, совпадающее с ее значением в вершине "уголка", равным по построению

Легко видеть, что любой "уголок" подобного типа с вершиной, расположенной на прямой L, также будет линией уровня, соответствующей своему значению функции Ф. Причем при удалении вдоль прямой L от начала координат на "северо-восток" мы будем получать линии уровня, отвечающие большим значениям Ф. Например, на рис. 2.2 показана линия уровня (b'bb"), где Ф(b) > Ф(а).

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

Ясно, что решению основной задачи (2.17) будет соответствовать наиболее удаленное от начала координат положение "уголка" (в пределах множества достижимости f(D)), которому соответствует максимальное возможное значение функции Ф, а значит, и F. На рис. 2.3 показано множество слабо эффективных оценок (отрезок [с, d]), полученных в результате решения задачи (2.17). На этом же рисунке показано решение [с', d'], полученное при другом наборе весовых коэффициентов, соответствующих прямой L'.

Рис. 2.3. Решения для разных наборов весов

Продолжая такие построения, легко убедиться, что, перебирая  всевозможные можно получить "северную", "северо-восточную" и "восточную" части границы множества достижимости  (D):

Это и отвечает основному содержанию сформулированной теоремы.

Здесь важно отметить, что задачи оптимизации типа (2.17) могут иметь не единственное решение. Так, для значения а, отвечающего  прямой L, мы в качестве решения получим целое множество [с, d]слабо эффективных оценок и соответствующих им слабо эффективных решений исходной многокритериальной задачи. Каждое из этих решений, вообще говоря, должно быть найдено.

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

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

 

 

 

 

 

 

 

 

 

 

 

 

4. Метод линейной свертки и  главного критерия. Лексикографическая  оптимизация

4.1 Метод линейной свертки  и главного критерия.

Теорема 2.2. Пусть Тогда решение задачи

          (2.18)

есть эффективный вектор.

Доказательство. Пусть есть решение задачи (2.18) и существует такой что а для i = i₀  имеем Тогда

и, следовательно, не максимизирует функционал F1. Полученное противоречие доказывает, что точки х' со сформулированными выше свойствами не существуют и поэтому х° — эффективный вектор. Теорема доказана.

Замечание 2.2

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

Таким образом, согласно доказанной теореме

Здесь

Обратимся снова к  геометрическим иллюстрациям для m = 2. В этом случае

где функция Ф₁ считается определенной в пространстве критериев (/1,/₂). Построим линии уровня функции Ф₁:

       (2.19)

Набор коэффициентов  считается фиксированным (неизменным в процессе всего рассмотрения). Графики прямых (2.19) для различных констант в правой части и различных весовых коэффициентов показаны на рис. 2.4.

ь

Рис. 2.4. Линии уровня функции Ф1

 

Угловой коэффициент  наклона прямой L определяется числами и равен . При увеличении константы в правой части уравнения (2.19) прямая перемещается вверх параллельно L (занимая положение L). Таким образом, мы имеем целое семейство линий уровня, и максимум функции Ф_1, а вместе с ней и F_1, достигается в точках плоскости соответствующих точкам касания (но не пересечения) самой "верхней" линии уровня и множества достижимости f(D). На рис. 2.4 точка b с координатами реализует найденную рассмотренным методом эффективную оценку. Легко видеть, что ни одна из точек интервалов [a, b], [с, d], соответствующих слабо эффективным, но не эффективным решениям, не может являться точкой касания f(D) и какой-либо линии уровня функции Ф_} (угловой коэффициент не может равняться нулю или бесконечности, т. к. все > 0 и их величина ограничена сверху единицей).

На рис. 2.4 показана точка q, являющаяся решением задачи (2.18) при другом наборе весовых коэффициентов. Перебирая различные а, можно (как и в случае максиминной свертки) получить достаточно точную аппроксимацию множеств P(f) и P(D).

Ситуация, связанная с  существованием эффективных решений, не являющихся решениями задачи (2.18) ни при каких , проиллюстрирована на рис. 2.5.

Все точки дуги а, b являются эффективными оценками, но ни одна из них (кроме самих точек а и b) не может являться точкой касания линий уровня функции Ф1 к множеству f(D) ни при каком наборе коэффициентов а. Таким образом, ясно, что отсутствие выпуклости множества f(D) приводит к принципиальным затруднениям при применении метода линейной свертки. Аналогично, наличие строго прямолинейных участков "северовосточной" границы множества f(D) может приводить к похожим трудностям из-за приближенного характера вычислений (точки внутри таких прямолинейных участков оказываются "неустойчивыми" решениями задачи (2.18)).

Рис. 2.5. Случай невыпуклой границы множества достижимости

 

Замечание 2.3

Весьма часто при  эвристическом выборе весовых коэффициентов в методе линейной свертки пытаются сразу определить желаемую эффективную точку, исходя из заданных оценок критериев по "важности". Так, например, полагая, что критерий существенно "важнее" чем критерий , мы бы желали в качестве единственного решения многокритериальной задачи получить эффективную точку а на рис. 2.6. Однако мы не знаем при этом, на сколько коэффициент а₂ должен превышать значение , чтобы была получена именно искомая точка. На рис. 2.6 показана ситуация, когда и в то же время найденной точке b соответствуют значения