Целевое программирование
Целевое программирование — это ветвь многокритериальной оптимизации , которая, в свою очередь, является ветвью многокритериального анализа решений (MCDA). Его можно рассматривать как расширение или обобщение линейного программирования для обработки множества, обычно противоречивых объективных показателей. Каждой из этих мер присваивается цель или целевое значение, которое необходимо достичь. Отклонения измеряются от этих целей как выше, так и ниже цели. Нежелательные отклонения от этого набора целевых значений затем минимизируются с помощью функции достижения. Это может быть вектор или взвешенная сумма в зависимости от используемого варианта целевого программирования. Поскольку считается, что удовлетворение цели удовлетворяет лица, принимающего решения, удовлетворения предполагается, что в основе лежит философия . Целевое программирование используется для выполнения трех типов анализа:
- Определите необходимые ресурсы для достижения желаемого набора целей.
- Определить степень достижения цели имеющимися ресурсами.
- Предоставление наилучшего решения при различном объеме ресурсов и приоритетах целей.
История
[ редактировать ]Программирование целей было впервые использовано Чарнсом, Купером и Фергюсоном в 1955 году. [1] хотя настоящее имя впервые появилось в тексте Чарнса и Купера 1961 года. [2] Основополагающие работы Ли, [3] зажечь, [4] Игницио и Кавальер, [5] и Ромеро [6] последовал. Шнидерьянс приводит библиографию большого количества статей, написанных до 1995 года, касающихся целевого программирования. [7] а Джонс и Тамиз дают аннотированную библиографию за период 1990-2000 гг. [8] Недавний учебник Джонса и Тамиза. [9] дает всесторонний обзор современного состояния целевого программирования.
Первым инженерным применением целевого программирования, предложенным Игницио в 1962 году, была разработка и размещение антенн, используемых на второй ступени корабля « Сатурн-5» . Его использовали для запуска космической капсулы «Аполлон», которая высадила первых людей на Луну.
Варианты
[ редактировать ]В первоначальных формулировках целевого программирования нежелательные отклонения распределялись по ряду уровней приоритета, при этом минимизация отклонения на более высоком уровне приоритета была бесконечно более важной, чем любые отклонения на более низких уровнях приоритета. Это известно как лексикографическое или упреждающее целевое программирование. Игницио [4] дает алгоритм, показывающий, как лексикографическая целевая программа может быть решена как серия линейных программ. Лексикографическое целевое программирование используется, когда существует четкая приоритетность целей, которые необходимо достичь.
Если лицо, принимающее решения, больше заинтересовано в прямом сравнении целей, тогда следует использовать взвешенное или неупреждающее целевое программирование. В этом случае все нежелательные отклонения умножаются на веса, отражающие их относительную важность, и складываются в одну сумму, образуя функцию достижения. Отклонения, измеренные в разных единицах, не могут быть суммированы непосредственно из-за явления несоизмеримости .
Следовательно, каждое нежелательное отклонение умножается на константу нормализации, чтобы обеспечить прямое сравнение. Популярным выбором констант нормализации является целевое значение соответствующей цели (следовательно, переводя все отклонения в проценты) или диапазон соответствующей цели (между лучшими и наихудшими возможными значениями, следовательно, отображая все отклонения в диапазоне от нуля до единицы). . [6] Для лиц, принимающих решения, более заинтересованных в достижении баланса между конкурирующими целями, Чебышева используется целевое программирование . Представлен Флавеллом в 1976 году. [10] этот вариант направлен на минимизацию максимального нежелательного отклонения, а не суммы отклонений. При этом используется метрика расстояния Чебышева .
Сильные и слабые стороны
[ редактировать ]Основным преимуществом целевого программирования является его простота и удобство использования. Это объясняет большое количество приложений целевого программирования во многих и разнообразных областях. Линейные целевые программы могут быть решены с использованием программного обеспечения линейного программирования либо как одна линейная программа, либо, в случае лексикографического варианта, как серия связанных линейных программ.
Таким образом, целевое программирование может обрабатывать относительно большое количество переменных, ограничений и целей. Спорным недостатком является способность целевого программирования производить решения, которые не являются эффективными по Парето . Это нарушает фундаментальную концепцию теории принятия решений , согласно которой ни один рациональный человек, принимающий решения, не будет сознательно выбирать решение, которое не является эффективным по Парето. Однако существуют методы [6] [11] [12] чтобы обнаружить, когда это происходит, и соответствующим образом спроецировать решение на эффективное по Парето решение.
Установка соответствующих весов в модели целевого программирования — еще одна область, вызвавшая споры с некоторыми авторами. [13] предлагая использовать процесс анализа иерархий или интерактивные методы [14] для этой цели. Также веса целевых функций можно рассчитать на основе их предпочтения, используя подход порядкового приоритета . [15]
См. также
[ редактировать ]Внешние ссылки
[ редактировать ]- LiPS — Бесплатная, простая в использовании программа с графическим интерфейсом, предназначенная для решения задач линейного, целочисленного и целевого программирования.
- LINSOLVE — бесплатное линейное программирование и линейное целевое программирование в окне командной строки Windows]
Ссылки
[ редактировать ]- ^ А. Чарнс, В. В. Купер , Р. Фергюсон (1955) Оптимальная оценка вознаграждения руководителей с помощью линейного программирования, Management Science, 1, 138-151.
- ^ А. Чарнс, WW Купер (1961) Модели управления и промышленные применения линейного программирования, Уайли, Нью-Йорк
- ^ С.М. Ли (1972) Целевое программирование для анализа решений, Ауэрбак, Филадельфия
- ^ Перейти обратно: а б Дж. П. Игницио (1976) Целевое программирование и расширение, Lexington Books, Лексингтон, Массачусетс.
- ^ JP Ignizio, TM Cavalier (1994) Линейное программирование, Прентис Холл.
- ^ Перейти обратно: а б с C Ромеро (1991) Справочник по критическим вопросам целевого программирования, Pergamon Press, Оксфорд.
- ^ MJ Scniederjans (1995) Методика и приложения целевого программирования, издательство Kluwer, Бостон.
- ^ Д. Ф. Джонс, М. Тамиз (2002) Целевое программирование в период 1990–2000 годов, в «Оптимизация по множественным критериям: современные аннотированные библиографические обзоры», М. Эрготт и X. Гандибле (ред.), 129–170. Клювер
- ^ Джонс Д.Ф., Тамиз М. (2010) Программирование практических целей, Springer Books.
- ^ Р.Б. Флавелл (1976) Новая формулировка целевого программирования, Омега, 4, 731-732.
- ^ Э. Л. Ханнан (1980) Недоминирование в программировании целей, INFOR, 18, 300-309
- ^ М. Тамиз, С.К. Мирразави, Д.Ф. Джонс (1999)Расширение анализа эффективности Парето на целочисленное целевое программирование, Омега, 27, 179-188.
- ^ С. И. Гасс (1987) Процесс определения приоритетов и весов для крупномасштабных программ с линейными целями, Журнал Общества операционных исследований, 37, 779-785.
- ^ Б.Дж. Уайт (1996) Разработка продуктов и их риторики на основе единой иерархической модели, 1996 г., Материалы ежегодной конференции Общества технических коммуникаций, 43, 223-224.
- ^ Тафаккори, Кейван; Тавакколи-Могаддам, Реза; Сиадат, Али (2022). «Устойчивое вложение и планирование на основе переговоров в системах аддитивного производства: тематическое исследование и многоцелевые метаэвристические алгоритмы» . Инженерные применения искусственного интеллекта . 112 : 104836. дои : 10.1016/j.engappai.2022.104836 . ISSN 0952-1976 .