И. Методы решения задач векторной оптимизации

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

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

Решение векторных задач с равнозначными критериями

с равнозначными критериями

Алгоритм 1. Решение ВЗМП с равнозначными критериями

(В.В. Хоменюк, Ю.К. Машунин [58])

Алгоритм решения ВЗМП (9.1.1)-(9.1.4) с равнозначными критериями выполнен в соответствии с принципом оптимальности 1 и представлен в виде ряда шагов.

Алгоритм 1.

Шаг 1. Решается задача (9.1.1)-(9.1.4) по каждому критерию отдельно, то есть для Vk G К₍ ищется максимум, а для Vk G К₂ - минимум. В результате решения получим:

Шаг 2. Определяем наихудшую неизменяемую часть критерия f_k°, к = 1,К. Для этого решается задача (9.1.1)-(9.1.4) для каждого критерия к = 1,К] на минимум: f® = min f_k(X), G(X) < В, X > О, k = kK,.

Решается задача (9.1.2)-(9.1.4) для каждого критерия на максимум: fJ = max f_k(X), G(X) < В, X > 0, k = 1J<₂.

Шаг 3. От каждого критерия отнимается его наихудшая неизменяемая часть. f_k(X) - f®, k = 1, К, X е S.

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

o<(f_k(X)-f»)<(f;-f»),k=iX>

o>(f_k(x)-f«)>(f;-f«),k = lX-

Шаг 4. Выполняется стандартная нормализация критериев:

(Х) = (f_k(X) - f»)/(f- - f°), k = iX X e s.

В задаче максимизации Vke разность между любым текущим значением f_k(X), VXeS и наихудших значением - f J всегда больше нуля:

(f_k(x)-f°)>o, (f;-f°)>o,

поэтому относительная оценка больше нуля Х_к(Х) > 0;

в задаче минимизации VkeK₂ разность между любым текущим значением f_k(X), VXgS и наихудших значением - f J всегда меньше нуля (f_k(X) - f°) < 0, но меньше нуля и (f * - f°) < 0, поэтому относительная оценка всегда больше нуля Х_к(Х) > 0, Vke К₂. __

В целом по задаче Vk G К относительная оценка Х_к(Х), к = 1,К лежит в пределах 0 < Х_к(Х) < 1, Vk е К.

Шаг 5. Построение Х-задачи.

VX е S определим X = minX_k(X), которую максимизируем по X G S, в результате получим максиминную задачу с нормализованными критериями.

Х° = max min X (X), G(X) < В, X > 0. (11.1.1)

х к ^к

Используя взаимосвязь (10.1.8) и (10.1.9), преобразуем задачу

(11.1.1) в Х-задачу.

Х° = max X, %-(f_k(x)-f°)/(f;-f°)

Шаг 6. Решение Х-задачи.

Шаг 7. Конец.

В результате решения Х-задачи получаем точку оптимума Х° и максимальную относительную оценку X, такую, что Х° < X (Х°), к = 1,К, Х°е S, то есть является максимальным нижним уровнем для всех относительных оценок Х_к(Х°), гарантированным результатом в относительных единицах, а в соответствии с теоремой 3 точка {X⁰} оптимальна по Парето.

Определим величину каждого критерия в оптимальной точке из соотношения:

Х(Х«) = (f_k(X“) - - f«), k =

отсюда

f_k(x«) = f” + (x»)(f; - f “), k = 1Л. (111-3)

то есть величина любого критерия в оптимальной точке складывается из наихудшей неизменяемой части fj, к = 1,К, увеличенной на изменяемую часть критерия на допустимом множестве точек S. Причем для всех критериев увеличение осуществляется на величину не хуже максимального нижнего уровня в относительных единицах от изменяемой части критерия.

Заметим, что для критериев к = 1,К, идет увеличение от f", к = 1,К, на X (X°)(f* - f°), так как (f* - f°) > 0, а для к = 1,К - идет ' i к к к^л к к^х

уменьшение от f° к = 1,К„ на X,(X°)(f* - f°), так как (f* - f°) < О,

К -'х. |х к к к к^х

k= VK?-

Алгоритм решения ВЗМП (9.1.1)-(9.1.4) с неоднородными критериями покажем на тестовом примере векторной задачи линейного программирования.

Решение линейной ВЗМП

Пример 1 (векторная задача линейного программирования)

optF(X)= {maxf,(X)= 199х, + 143.8х₂ + 133.8х₃, (11.1.4)

max f₂(x) = 346х, + 360х₉ + 482.8х₃, max f₃(x) = 121.2Х[ + 122.9х₂ + 124.2х₃, max f₄(x) = 199х’ + 131.4х₂ + 119.4х₃, min f₅(x) = 5Xj + 5х₂ + х₃,

min f (х) = 19.9х. + 13.14х_ + 11.94x3.

6^{х 7} 1 2 З⁷

• 5Xj + 5х₂ +
• 19.9Xj + 13.14х₂ + 1.12х₂ + 199х, + 143.8х₂ + 346Xj + 360х₂ +
• 5х₃ 11794х₃
• 1.28 х₃ 133.8х₃ 487.8х₃ х_р х₂, х₃

< 2047,

< 9400,

< 502,

> 40000,

> 90000.

>0.

(11.1.5)

Результаты решения по каждому критерию:

= 0.4181, Х° = {_Х1 = 195.6, х₂ = 0, х₃ = 137.6}, f/X⁰) = 57340, f₃(X°) = 134850, f₅(X°) = 40800, f₂(X°) = 55360, f₄(X°) = 1666, f₆(X°) = 5536, (X°) = 0.4181, (X°) = 0.4181, X₃(X°) = 5656, (X°) = 0.4295, X₅(X°) = 0.4181, (X°) = 0,5704. X°<(X°),k = 1^6.

Полученный результат в виде точки X и максимального уровня является оптимальным решением векторной задачи (11.1.4)-(11.1.5). Он соответствует принципу оптимальности (см. определение 7):

X°k(X°),k= 1,6.

В соответствии с теоремой 1 критерии первый, второй и пятый являются наиболее противоречивыми.