Задача квадратичного программирования


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

gi(x) = ∑ cijx1αij1x2αij2…xnαijn (1.39)

где xi > 0, cij > 0, αijk, k = 1,2,…, n — произвольные действительные числа.

Математическая формулировка задачи геометрического программирования заключается в минимизации позинома g0 (х) при условии, что некоторые другие позиномы gi (х) не превосходят единицы:

min g0 (х) = min {∑c0j ∏xkα0jk}

при условии, что

gi (х) = {∑cij ∏xkαijk ≤ 1, i = 1,2,…, n.

В частном случае от задачи геометрического программирования (с невыпуклыми ограничениями и критерием оптимальности) вида:

min {c0∏xkα0k} (1.41)

при условии, что

ci ∏xkαik ≤ 1, i = 1,2,…, m; xk > 0, k=1,2,…, n,

путем преобразования переменных нетрудно перейти к задаче линейного программирования. Прологарифмируем функции критерия оптимальности и ограничений и введем новые переменные zk = ln xk, k = 1, 2, …, n. Тогда исходной задаче будет эквивалентна следующая задача линейного программирования:

min {ln c0 + ∑α0kzk} (1.42)

при условии, что

∑αikzk ≤ — ln ci, i = 1,2,…, m. (1.43)

Определение оптимального решения z* задачи линейного программирования (1.42) и переход к переменным исходной задачи с помощью преобразования хk* = ехр (zk*), k = 1, 2,…, n, позволяет найти глобальный-минимум задачи геометрического программирования (1.41).

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

В задачах оптимального проектирования часто возникает необходимость получить наилучшие (минимальные или максимальные) значения для нескольких характеристик проектируемого устройства, т. е. требуется найти такое оптимальное решение х* ∈ D, которое обеспечивает минимум одновременно по всем введенным частным критериям оптимальности Qi (х), i = 1, 2, …, s. Обычно эти критерии противоречивы (уменьшение одних приводит к увеличению других). В связи с этим для совместного учета всей совокупности частных критериев необходимо рассматривать векторный критерий оптимальности

Q (х) = (Q1 (х), Q2 (х),…, Qs (х)), (1.44)

приводящий к модели принятия оптимального решения, которая называется задачей векторной (многокритериальной) оптимизации:

min Q(x), (1.45)
где
D= {x|gi(x) ≥ 0, i = 1, 2, …, m}. (1.46)

Выражение (1.45) является сокращенной записью следующей модели принятия оптимального решения:

Найти значения управляемых параметров х, которые обеспечивают одновременно минимальное значение по каждому из частных критериев оптимальности:

min Q1(x); min Q2(x);… min Qs(x) (1.47)

при выполнении условий работоспособности проектируемого устройства

gi(x1, x2, …, n) ≥ 0, i = 1, 2, …, m; (1.48)
xj ≤ xj ≤ xj+, j= 1, 2, …, n. (1.49)

Оптимальное решение х* задачи векторной оптимизации (1.47)— (1.49) в общем случае, не являясь оптимальным ни для одного из частных критериев Q, (х) (в смысле постановки задачи параметрической оптимизации (1.25)—(1.27)), должно быть компромиссным (в определенном смысле) для векторного критерия Q (х) в целом.

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


Комментарии запрещены.




Статистика