Оптимизация по обобщенному критерию

Обозначим множество всех путей на графе через .

Введем понятие j-й длины пути (j=1,q) по k-му критерию оптимизации (k=1,m) L_jk – это сумма значений k-го критерия по всем вершинам j-го пути.

Найдем множество L_jk из графа

Представим имеющиеся данные в относительном виде. Для этого по каждому k-му критерию оптимизации (т.е. столбцу) определим минимальное и максимальное значение L: L_{min k} и L_{max k}. Далее по каждому k-му критерию (внутри столбца) определим длины путей в относительном виде по формуле

Такая относительная форма представления результатов является единственно правильной, потому что:

- безразмерный вид позволяет сравнивать критерии, имеющие разные размерности и проводить далее операции по свертке критериев

- диапазон изменения критериев в абсолютном виде совершенно может быть разным, а в относительном виде при применении формул свертки – должен быть одинаков. Об этом указывают также Р.Л. Кини и Х. Райфа []. При использовании формулы (1) диапазон изменения всех критериев в относительном виде от 0 до 1.

Формула для вычисления длины пути по обобщенному критерию по каждому j -му пути:

- для рассматриваемого примера

и для общего случая:

(2)

При этом должно выполняться условие

; (2.2)

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

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

,

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

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

Т_шт

А

В D

С

Рис. 2.2. Взаимосвязь себестоимости обработки С и штучного времени Т_шт

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

,

где - весовой коэффициент при С, - весовой коэффициент при Т_шт.