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

причем выбираем много большим, чем , 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 соответствуют значения