Векторная оптимизация

ВЕКТОРНАЯ ОПТИМИЗАЦИЯ

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

Эффективность функционирования экономической системы оценивается, как правило, несколькими критериями. Математической формой критерия эффективности  в оптимизационных экономико-математических задачах является целевая функция.

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

 Если точки максимума  , определенные при решении задач по каждому критерию   не совпадают, то решение задачи может быть только компромиссным.

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

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

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

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

 При разработке методов решения многокритериальных задач приходится решать ряд специфических проблем. 
1. Проблема нормализации возникает наиболее часто. Отдельные критерии как правило имеют различные единицы и масштабы измерения, что делает невозможным их непосредственное сравнение. К единому и безразмерному виду критерии приводятся посредством операции нормирования. Наиболее распространенными способами нормирования является замена абсолютных значений критериев их относительными величинами 
, 
или относительными значениями отклонений от оптимальных значений критериев 
. 
2. Проблема учета приоритета критериев встает, если критерии имеют различную значимость. В этом случае необходимо найти математическое определение приоритета и степень его влияния на решение задачи. 
3.  Проблема определения области компромисса возникает при решении многомерных нелинейных задач, поэтому для их решения необходимо применять методы, гарантирующие эффективное решение. 
         Методы решения задач многокритериальной оптимизации можно подразделить на четыре группы: 

методы, основанные на свертывании  критериев;

методы, использующие ограничения  на критерии;

методы целевого программирования; 

методы, основанные на отыскании  компромиссного решения.

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

  Пример. Решить задачу методом последовательных уступок, если уступка по первому критерию составляет 10% от его оптимального значения. 
 
 
Решение. 
Решим задачу по критерию  . Получим  . В соответствии с условием задачи величина уступки  . Дополнительное ограничение будет иметь вид  , то есть  .  
получим  ,  ,   

Задача.

Предприятие может выпускать  пять видов продукции И1, И2, ИЗ, И4, И5. Для этого используется три вида ресурсов, расход которых на производство единицы продукции и их запасы приведены в таблице:

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

 
 
Оптовая цена и себестоимость единицы  продукции соответствующего типа приведены  в таблице:

 
 
Объем каждого вида продукции должен быть не менее 100 и не более 500 единиц. Мерой эффективности производственной программы являются следующие показатели: 
 
1. Прибыль предприятия – f₁; 
 
2. Валовый объем выпуска продукции в стоимостном выражении – f₂; 
 
3. Себестоимость продукции – f₃; 
 
4. Уровень загрузки оборудования – f₄. 
 
Решить задачу методом последовательных уступок, если уступку по каждому критерию полагать равной 10% от его оптимального значения. 
 
Решение 
 
1. Обозначим через   – количество продукции И1,   – количество продукции И2,   – количество продукции И3,   – количество продукции И4,   – количество продукции И5.  
 
Целевые функции будут иметь вид:  
 
Прибыль:  . 
 
Валовый объем ( в стоимостном выражении): 
 
. 
 
Себестоимость:  . 
 
Уровень загрузки оборудования:   
 
Ограничениями задачи будут: 
 
1. По расходу ресурсов: 
 
 – В₁ 
 
 – В₂ 
 
 – В₃ 
 
2. По фонду времени работы оборудования: 
 
 – (токарное)  
 
 – (фрезерное)  
 
 – (сверлильное)  
 
 – (шлифовальное) 
 
3. По объему выпускаемой продукции:  . 
 
4. Условие целочисленности переменных:  . 
 
Предположим, что критерии пронумерованы в порядке убывания важности. Решаем задачу для  .  
 2500 (ден.ед.). 
Определяем величину уступки по первому критерию:  . Вводим дополнительное ограничение:  . Решаем задачу для  .  12992(ден.ед.). 
Определяем величину уступки по второму критерию:  . Вводим дополнительное ограничение:  . Решаем задачу для  ,  9198(ден.ед.). 
Определяем величину уступки по третьему критерию:  .Вводим дополнительное ограничение:  . Решаем задачу для     10075 (ст./час). 
 
 
Варианты производственной программы 
 
 
 
При решении задачи векторной оптимизации по методу последовательных уступок значение прибыли составит 2343 (ден.ед.), значение валового объема – 11696 (ден.ед.), себестоимость – 9353 (ден.ед.),загрузка оборудования – 10075 (ден.ед.). 
 
Предприятие должно выпускать продукции И1 – 225 ед, И2 – 100 ед, ИЗ – 100 ед, И4– 439 ед, И5– 100 ед.