ГЛАВА 4
МЕТОД ВЕКТОРНОЙ ОПТИМИЗАЦИИ
4.1. ВВЕДЕНИЕ В ПРОБЛЕМУ
Плодотворное развитие методов оптимизации началось с середины 50-х годов. Появились новые математические методы расчетов автоматических систем управления [63—66]. Современное состояние этой области науки хорошо было проанализировано в работе [67]. Следует заметить, что почти во всех публикациях до 1970 г. проблема оптимизации освещалась с точки зрения лишь одного, заранее фиксированного скалярного показателя качества системы, что для многих практических задач было явно недостаточно. Дальнейшее совершенствование и развитие методов оптимизации существенно связано с проблемой оптимизации векторных показателей качества системы.
Недостаток функционирования системы, определенного из условия оптимизации скалярного показателя качества, заключается в следующем: выбранный и оптимизируемый критерий отвечает лишь на одни требования, предъявленные к качеству системы, тогда как другие требования, порой не менее важные, чем первые, игнорируются. Сочетание всех требований может быть учтено некоторой совокупностью критериев, образующей векторный функционал качества, т. е. векторный критерий качества.
Исходя из сказанного, становится очевидным естественное возникновение математической проблемы одновременной оптимизации совокупности критериев, каждый из которых оценивает определенное качество системы. Данная проблема получила название проблемы векторной оптимизации.
Первая формулировка проблемы оптимизации векторного критерия качества в научной литературе встречается в 1896 г. [68]. Она возникла в связи с решением задач из сферы планирования и организации производства и позднее быстро распространилась на разнообразные области управления. В 1963 г. американский ученый Л. Заде [69] поставил вопрос о проектировании систем, наилучших по нескольким показателям качества. Эту работу следует считать началом нового, более глубокого понимания проблем оптимизации. Автор обращает внимание специалистов на тот факт, что в большинстве случаев при проектировании систем управления проектировщики, естественно, желают получить систему, обладающую многими оптимальными характеристиками. Система лишь с одним показателем эффективности давно не устраивает их; машинам и сооружениям почти всегда желательно придать многокритериальные оптимальные свойства.
Научная ценность публикации Л. Заде заключается в утверждении того, что в большинстве практических случаев точная оптимизация векторного функционала недостижима. Это означает, что если выбором управления удается оптимизировать один скалярный функционал, то почти всегда не остается возможности для оптимизации на том же решении второго скалярного функционала. Настоящее заключение, по существу, сводится к косвенному утверждению того, что проблема точной оптимизации векторного критерия, т. е. проблема точной оптимизации всех скалярных функционалов на одном и том же решении, не существует и дать ее точную математическую формулировку нельзя. Именно в этом и заключается противоречивость естественного желания многокритериальной оптимизации и невозможности достижения его точными методами.
Становится очевидным, что подход к проблеме векторной оптимизации должен базироваться на идее приближения к решению, определяющему систему с идеальными характеристиками.
Проблема многокритериальной оптимизации с 1970 г.
Предварительным заданием вектора весовых коэффициентов λ (λ1, λ2, λn) автоматически вводится предпочтение критериев, что не всегда возможно сделать. Для широкого класса функций I1(X), I2(X), ..., Ik(X) доказано, что при каждом выборе вектора минимизации линейной формы (4.1) получается решение, которое является одной из Парето-точек. Различные формы свертки векторных критериев рассмотрены в [71].
Во многих практических задачах применение вышеперечисленных методов малоэффективно. В основном это происходит потому, что введение предпочтения критериев, т. е. установление их иерархической последовательности предпочтения, или же предварительное задание весовых коэффициентов с целью минимизации свертки (4.1) не всегда возможно и порою ничем не оправдано.
В работе [72] дан анализ всех существующих методов решения задач векторной оптимизации и сформулированы преимущества и недостатки каждого из них. Здесь же предлагается приближенный метод решения задачи векторной оптимизации, применение которого во многих практических ситуациях полностью оправдывает себя и дает хорошие результаты. Этот новый метод решения задач многокритериальной оптимизации основан на идее определения идеальной точки в пространстве критериев качества и введения нормы в этом пространстве. Полученное при этом компромиссное решение является Парето-оптимальным решением и обеспечивает максимальную близость показателей качества системы к своим наилучшим (идеальным) значениям.
Характерным для данного подхода является то, что он освобожден как от установления порядка предпочтения критериев, так и от предварительного выбора весовых коэффициентов формы (4.1).
Следует отметить, что от выбора меры приближения к идеальной точке в пространстве критериев качества, т. е. от определения метрики в этом пространстве, в некоторой степени зависит окончательный вид решения задачи векторной оптимизации. Следовательно, вопрос выбора такой меры должен быть тщательно изучен при рассмотрении каждой конкретной задачи. Однако в ряде практических случаев выбор квадратичной метрики и осуществление приближения к идеальной точке в евклидовом пространстве дает эффективные результаты.
4.2. ОБЩАЯ МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ ВЕКТОРНОЙ ОПТИМИЗАЦИИ
Сформулируем новую постановку задачи оптимизации векторных показателей качества. Идея такой постановке впервые была высказана в [73].
4.2.
Следовательно, задачу оптимизации системы S по векторному показателю качества можно сформулировать следующим образом: определены S[Ζ], I(Ζ), R (Z), требуется найти z*∑Z. Прежде чем изложить постановку задачи векторной оптимизации в математическом программировании, рассмотрим задачи линейного и нелинейного программирования.
ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Одним из важных разделов проблемы оптимизации является линейное программирование, которое успешно применяется для решения ряда важных задач управления народным хозяйством, проектирования сложных систем автоматизации производственных процессов, планирования, экономики и др. Методы линейного программирования начали широко развиваться после выхода в свет работы Л. В. Канторовича [74]. В настоящее время они математически хорошо разработаны и достаточно эффективны при оптимизации скалярной функции цели.
4.2.
для которого форма (4.3) принимает наибольшее (или наименьшее) значение. Решение Χ0Ω принято называть оптимальным планом задачи.
Задача линейного программирования служит математической моделью многих важных задач управления, встречающихся в практике. Она точно или приближенно решается симплекс-методом Данцига. В отечественной литературе этот метод часто называют методом последовательного улучшения плана.
Однако во многих практических задачах оптимизация лишь по одному показателю качества системы недостаточна, а необходимо одновременно учитывать два или более показателя, что приводит к задачам оптимизации с векторными критериями качества. В транспортной задаче, например, можно выделить два показателя качества: общую стоимость перевозок и время, необходимое для доставки всего груза по назначению. Если в первом случае оптимальный план строится с целью максимального сокращения расходов, то во втором оптимальным планом перевозок считается тот, по которому все грузы могут быть доставлены в пункты назначения в кратчайшее время. Оба показателя качества операции перевозок вступают в противоречие друг с другом. Тем не менее необходимо стремиться получить решение задачи перевозок при «хорошем» времени выполнения плана и достаточно низких расходах. Совокупность всех этих требований может быть учтена некоторым выбором целевых функций, которые и образуют векторный критерий качества — векторную функцию цели.
ОБЩАЯ ЗАДАЧА ПРОГРАММИРОВАНИЯ
Если g(X), fa(X) — линейные функции, аналогичные (4.3) — (4.5), то данная задача превращается в задачу линейного программирования; если же g(X), fa(X) — произвольные (выпуклые) функции, то данная задача называется задачей нелинейного (выпуклого) программирования.
БОЛЕЕ ОБЩАЯ ЗАДАЧА
