Виды управленческих решений
Управленческие решения классифицируются по видам. Можно выделить четыре вида принятия управленческих решений: стандартное, бинарное, многоальтернативное, инновационное.
Стандартный процесс принятия решений представляет собой самый распространенный тип решений. Цель упорядоченного подхода к принятию решения – повысить объективность и обеспечить учет всех важных данных. Необходимо создание базы данных, которая используется для отсеивания и исключения менее желательных альтернатив. Конечный результат представляет собой однозначный выбор, но он не имеет правильности истинной причины проблемы. Основные шаги в стандартном процессе принятия решений отражены на рис. 6.8.
Постановка цели решения – первый шаг алгоритма стандартного вида принятия управленческого решения. Правильность постановки цели решения предопределяет ответы на три вопроса: «Какой выбор я пытаюсь сделать? Почему это решение необходимо? Каким было последнее принятое решение?» (последний вопрос связан с концепцией конкретного предприятия). Правильность постановки цели решения определяется его связью с предшествующими решениями.
Рис. 6.8. Стандартный вид принятия управленческого решения
Установление критериев решения – второй шаг. Первый вопрос, который задает себе руководитель: «Достигнет ли решение желаемых результатов?», т.е. рассмотренные факторы должны быть учтены в конкретных требованиях. Чтобы принять эффективное решение, необходимо разделить имеющиеся критерии на жесткие ограничения и характеристики, без которых невозможно обойтись, – эго третий шаг в данном алгоритме. Желательные критерии необходимо расположить в порядке приоритетов. Существует несколько методов оценки приоритетов. Простейший из них – балльная система, где максимальное количество баллов равно 10. Каждый балл указывает на относительную ценность и влияние желательного критерия при принятии решения.
В принятии управленческих решений неизбежны компромиссы. Решение должно уравновешивать цели, ценности, критерии, так как каждое решение или выбор, затрагивающий все предприятие, будет иметь негативные последствия для отдельных его частей, если не рассматривать организацию с позиции системного подхода и не учитывать последствия управленческих решений.
Шаг четвертый – сравнение альтернатив. Производится в том случае, когда на первый взгляд все альтернативы имеют вариант один лучше другого. При этом начинать необходимо со сбора информации об альтернативах. Собранная информация помогает измерить степень удовлетворения требований по каждому из критериев. После того как вы четко определили альтернативы, необходимо соотнести варианты решений с критериями. Нельзя сравнивать один вариант решения с другим, так как при этом теряются из вида цель и конечные результаты принятия решения. На данном этапе принятие решение – это процесс нахождения лучшего варианта, основанного на информации.
Риск – это отрицательный побочный эффект, снижающий конечную эффективность действий. Грамотные руководители, прежде чем принять окончательное решение, предпринимают проверку – определение рисков. При оценке риска определяется фактор серьезности. Через этот фактор формируется суждение о степени влияния данного события на ситуацию. При оценке рисков рассматриваются альтернативы и прослеживается вероятность и серьезность данных альтернатив.
Оценка риска – совокупность процедур анализа риска, идентификации источников его возникновения, определения возможных масштабов последствий проявления факторов риска, определение роли каждого источника риска.
Уровень риска – отношение величины ущерба (прибыли) к затратам на подготовку и реализацию риск-решений. К факторам риска относятся внешние и внутренние факторы. Внешние факторы риска – экономические, политические, техногенные, природно-климатические и т.д. Внутренние факторы риска: конкурентоспособность ближайшего окружения – персонала, технологий, организационно-технического уровня и т.д.
Оптимизация риска – процесс перебора множества внешних и внутренних факторов риска, влияющих на его уровень, и выбора наилучшего варианта совокупности факторов.
Управление рисками является компонентом подсистемы разработки и реализации управленческих решений, схема управления рисками представлена на рис. 6.9.
Элементами входа являются параметры возникшей проблемы. Качественный выход возможен только в том случае, когда обеспечен качественный процесс принятия управленческого решения.
Принятие решения – последний шаг. Решение, таким образом, предстает как сумма оценочных решений. Делая выбор, руководитель вносит ряд суждений, которые необходимо сортировать, сравнивать, оценивать риск.
Рис. 6.9. Управление рисками в процессе принятия управленческого решения
Процесс принятия бинарного решения
Большинство бинарных ситуаций возникает в результате отсутствия анализа существующей проблемы. Причины возникновения бинарных ситуаций:
- • переадресовывайте принятия решения вышестоящим руководителям, т.е. подчиненные, поставщики, которые хотят повлиять на решение, представляют его на рассмотрение в бинарной форме, стараясь принудить к выбору, соответствующему их интересам;
- • поверхностный анализ проблемы;
- • нехватка времени для выбора оптимальных решений.
Принятие бинарного решения возможно в том случае, когда предполагается решение «да» или «нет». Выбор бинарного решения отображен на рис. 6.10.
Рис. 6.10. Алгоритм бинарного принятия решений
Основные шаги: постановка цели, выявление потенциальных результатов, установление критериев решения, разделение критериев и сравнение альтернатив «да, нет», выявление и оценка риска.
Наличие ситуации бинарного решения устанавливается посредством формулировки цели решения. Если необходимо изменить тип решения, то следует изменить формулировку. В бинарной ситуации стандартные шаги принятия решений необходимо делать с осторожностью, так как ключевым в данном процессе является выбор критериев, на их основе и принимается решение. Лучше всего рассматривать критерии как позитивные, так и негативные, чтобы получить объективную картину.
Процесс принятия многовариантного решения
При принятии многовариантного решения используется метод оценки альтернатив по желательным характеристикам. Однако при этом необходимо каждую альтернативу индивидуально сопоставлять с некоторым созданным идеальным образцом. Выбор многовариантного решения делается с помощью следующих шагов, которые отображены на рис. 6.11.
Рис. 6.11. Алгоритм принятия многовариантного решения
Процесс принятия инновационного решения
Инновационным называется решение, предусматривающее некоторое нововведение, т.е. формирование и реализацию ранее не известной альтернативы. В данном случае управленцы сталкиваются с такой ситуацией, когда нужно сделать выбор при отсутствии готовых альтернатив. Поэтому в данном случае должно преобладать творческое мышление над рациональным.
Выбор инновационного решения делается с помощью шагов, которые отражены рис. 6.12.
Организация инновационной деятельности начинается с создания инновационного климата в работе (поощрения свободы действий); внедрять следует простые и доступные альтернативы; не стоит начинать с поиска идеального решения; к решению проблемы нужно привлекать других сотрудников.
Сравним рациональный и инновационный процессы принятия решений (табл. 6.1).
Рис. 6.12. Алгоритм принятия инновационного решения
Таблица 6.1
Сравнение рационального и инновационною процессов
Постановка проблемы
Носит конкретный характер
Носит более общий характер
Используется логический подход
Синтез, мозговая атака, другие методы
Результаты
Вырабатывается одна альтернатива
Вырабатывается несколько альтернатив
2. Стандартные, бинарные, многоальтернативные, инновационные решения.
Рассмотрим особенности таких видов решения как: стандартное, бинарное, многоальтернативное и инновационное, которые достаточно часто встречаются в управленческой практике.
Рассмотрение данного типа решений определяется двумя обстоятельствами:
• эти решения представляют собой наиболее распространенный тип решений;
• аналитические шаги, необходимые для его принятия, применимы также и для остальных типов решений.
Конечный результат в стандартных решениях — это однозначный выбор, но он не имеет характер безоговорочной правильности истинной причины проблемы. Основные шаги в этом процессе:
• постановка цели решения;
• установление критериев решения;
• разделение критериев (желательные характеристики);
• оценка риска (опасность/серьезность);
Бинарное решение. В бинарном решении представлены две диаметрально противоположные альтернативы. Обычно это конкурирующие альтернативы, которые вынуждают к выбору типа «да -нет», «или-или» (например, открыть еще один филиал фирмы или нет). Эти решения отличаются высокой степенью связанной с ними неопределенности. Бинарные решения отражают неестественное положение вещей.
Причины возникновения бинарных решений следующие:
• переадресование принятия решений вышестоящим инстанциям;
• поверхностный анализ проблемы;
• нехватка времени на выработку оптимальных решений;
• оправданность бинарных решений в некоторых случаях. Примером может служить ситуация типа «изготовить или купить» в случае единственного источника снабжения.
Для бинарного решения методы стандартного принятия решения следует модифицировать, главным образом для увеличения возможных альтернатив выбора.
Многоальтернативное решение. Многовариантная разновидность решений встречается не так часто.
В этих решениях первые два шага соответствуют стандартному процессу принятия решений. Но, начиная с третьего шага, критерии следует разделять на ограничения и желательные характеристики, а последние — ранжировать по их относительной ценности.
Список критериев необходимо преобразовать в абсолютную шкалу измерения, что позволит каждую альтернативу оценивать саму по себе. Многоальтернативные решения предлагают несколько равноправных способов действия, ведущих к заданному результату. Поэтому приходится формулировать систему технических, экономических, социальных и иных критериев, позволяющих сделать выбор. Однако может случиться, что ни один из существующих вариантов не будет подходящим, и в этом случае можно попытаться сформулировать инновационные решения.
Инновационное решение. В случае принятия инновационного решения требуется сделать выбор при отсутствии очевидных альтернатив. В данном случае идет переключение с рационального мышления на творческое мышление, а затем снова на рациональное. Поиск такого решения происходит на основе искусственного комбинирования подходящих характеристик из тех решений, которые были в целом отклонены. Разумеется, эти характеристики должны быть не только непротиворечивыми и совместимыми, но еще и дополняющими, усиливающими друг друга.
При анализе альтернатив может быть использован метод оптимизации критериев (МОК). Он используется в тех случаях, когда ни одна из известных альтернатив не представляется подходящей.
Идея МОК состоит в предположении, что комбинирование лучших черт известных альтернатив может привести к более эффективному решению. Принимается инновационное решение обычно следующим образом. Сначала составляется перечень его желательных характеристик. Затем эти характеристики проверяются на взаимное соответствие. Из прошедших такую проверку характеристик формируются различные комбинации, из которых выбирается лучшая. Поскольку такой подход носит механический характер, удовлетворительный результат получить довольно сложно, а подчас и невозможно. А если он и достигнут, то не всегда бывает близок к
оптимальному, поэтому может рассматриваться как временный или основа для продолжения работы в данном направлении.
Завершая данный вопрос отметим, что, несмотря на разнообразие как подходов к разработке классификаций управленческих решений, так и существующих вариантов, каждая из них имеет право на существование, использование и дальнейшее развитие. Мы не ставили задачу рассмотреть все возможные классификации управленческих решений (слишком много вариантов), но даже из сравнения приведенных выше, становится ясно, что они не противоречат и хорошо дополняют друг друга.
Видимо поэтому не существует рекомендаций относительно «лучшего» варианта классификации, каждый из них имеет право на существование и использование.
ОСНОВЫ СОЦИАЛЬНОГО УПРАВЛЕНИЯ
Принятие управленческого решения — важнейший этап управленческой деятельности, реализации управленческих отношений и лидерских способностей каждого управленца. Итогом управленческой и организационной работы является управленческое решение.
Решение представляет собой такой акт органов управления или руководителя, в котором не только поставлена цель, но и сформулирован ряд задач, предусмотрены исполнители, выделены ресурсы (трудовые, материальные, финансовые), закреплена ответственность.
Решение принимается в тех случаях, когда выявлена проблемная ситуация. Последняя всесторонне исследована, определены причины и условия ее возникновения, собрана необходимая информация, найден ключ решения, оценены возможные последствия в изменении качества жизни людей и т. п. При подготовке решения выявляются те ограничения, в рамках которых реализуется цель, начинают решаться поставленные задачи. Эти ограничения могут быть внутренними (квалификация людей, наличие ресурсов, качество информации) и внешние (связи с внешним миром, связи с поставщиками, наличие инвесторов и т. п.).
Многообразию проблем соответствует многообразие решений. Специалисты выделяют такие решения: экономические, социальные, политические, идеологические, государственно-правовые, стратегические и тактические, глобальные и специфические, концептуальные и программные, научно обоснованные и эмпирические, интуитивные, рутинные и новаторские.
Совершенно очевидно, что можно выделить разное количество стадий в подготовке управленческого решения (поиск проблемы, определение путей решения, выбор оптимального решения из имеющихся альтернатив, декларация решения и т. п.), но основным является процесс сбора, анализа и переработки информации о внешних и внутренних условиях.
При подготовке и принятии решений используются современные научные и технические средства, методы исследования операций, системный анализ, моделирование, электронно-вычислительная техника. Для коллективных решений особое значение имеет совокупный коллективный интеллект субъекта управления, принимающего решения. Однако следует подчеркнуть творческий характер процесса подготовки и принятия решений, первостепенную роль личности человека, его управленческого интеллекта, профессионализма, воли и других личных и профессиональных качеств.
Любое решение связано с человеком, его творческой индивидуальностью, с мотивацией к деятельности каждого. Без учета этого решение, даже самое обоснованное, не может быть принято, а тем более реализовано. Субъект управления, принимая решение, организуя его исполнение, руководствуется незыблемым принципом — решение должно быть “спроецировано” на человека, коллектив, организацию, затрагивать их коренные интересы, мотивировать их к деятельности. Поэтому важно принять все меры к тому, чтобы решение было принято людьми и они осознали его необходимость. Конечно, может сложиться такая ситуация: решение правильное, даже инновационное, но сознание людей не готово к его восприятию, в нем преобладает приверженность к старым решениям, действуют стереотипы прошлого, эмоции преобладают над здравым смыслом. Но и в таком случае субъект управления проводит работу по инновированию сознания, постепенно добивается внедренческого эффекта средствами разъясняющих и обучающих технологий по изучению и инновированию общественного мнения.
Принятие решения можно определить как процесс неслучайного выбора действий. Осуществить выбор — значит отдать предпочтение (в каком-то отношении) одному по сравнению с другим. Результатом процесса принятия решений является само решение. В сущности, решение — это такое ощущение субъекта, что процесс решения закончен и в результате этого он уже знает, как должен действовать, не только знает, что хочет в данной ситуаций, но и приблизительно представляет, каким образом намерен достигнуть этого. С психологической точки зрения принятие решения — “волевой акт формирования последовательных действий, ведущих к достижению цели на основе преобразования информации в ситуации неопределенности”.
Каждый, даже самый узкий, интервал любой деятельности состоит из ряда решений, принимаемых человеком в процессе выбора вариантов, Целей и способов собственной деятельности. Управленческие решения отличаются от прочих тем, что являются двухступенчатыми. Руководитель в процессе руководства все время принимает решения в отношении того, как он должен руководить, но эти его решения содержат одновременно “вторую ступень” — они являются решением о том, как должны действовать подчиненные.
Нет управленческих решений, которые имели бы только хозяйственные последствия. Решения всегда социальны, всегда воспитывают у подчиненных либо позитивные, либо негативные качества. Поэтому, принимая то или иное решение, руководитель должен иметь в виду двоякий эффект: производственно-экономический и социальный, нравственно-психологический. И оценкой оптимальности принятого им решения являются не только хозяйственные показатели, но и поведение работников при достижении ими производственных целей, мера их активности, инициативы.
В зависимости от того, в какой степени знаком с ситуацией субъект управления, принимающий решение, различают решения:
— уверенности (детерминистские решения, когда известна ситуация и имеющие в ней место причинные зависимости);
— риска (вероятностные решения, когда не известен хотя бы один из моментов, но известна и может быть подсчитана его или их вероятность, если такого рода случаи часто имеют место);
— неуверенности (стратегические решения, когда принимающему решение ни один из указанных моментов не известен).
М. Вудкок и Д. Френсис различают управленческие решения в зависимости от относительной трудности проблем, требующих решения. Они выделяют и рассматривают четыре уровня принятия решений, для каждого из которых требуются определенные управленческие навыки.
Уровень первый — рутинный. Принимая рутинные решения, руководитель ведет себя в соответствии с определенной программой, почти как компьютер, распознающий ситуации и поступающий заранее предсказуемым образом. Его главная функция в том, чтобы “почувствовать” и идентифицировать ситуации, а затем взять на себя ответственность за начало определенных действий.
Уровень второй — селективный. На этом уровне руководитель оценивает достоинства целого круга возможных решений и старается выбрать из некоторого числа хорошо отработанных альтернативных наборов действий те, которые лучше всего подходят к данной проблеме.
Уровень третий — адаптационный. На этом уровне руководитель ищет новое решение известной проблемы. Успех зависит от его личной инициативности и способности прорыва в неизвестное.
Уровень четвертый — инновационный. На этом уровне руководителю необходимо найти способы понимать совершенно неожиданные и непредсказуемые проблемы, решение которых зачастую требует развития в себе способности мыслить по-новому.
В табл. 1 объединяются четыре уровня принятия решений и ключевые навыки, необходимые руководителю. Руководителям, работающим над принятием решений высокого уровня, требуются также и навыки более высокого уровня.
Полезно выделить также решения единоличные (принимаемые руководителем единолично) и коллегиальные (принимаемые руководителем с привлечением подчиненных). Причем в зависимости от “удельного веса” единоначалия и коллегиальности в принятии решений выделяются пять типов принятия решений:
— единоличное принятие решений без предварительных консультаций с сотрудниками и последующего их информирования;
— единоличное принятие решений с последующим информированием подчиненных;
— единоличное принятие решений с предварительными консультациями в коллективе;
— принятие совместных решений с сотрудниками;
— полная передача подчиненным функции принятия решения.
Уровни принятия решений и ключевые навыки, требуемые руководителю
Алгоритм решения задач бинарного квадратичного программирования методом штрафных функций Текст научной статьи по специальности «Математика»
КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ / БИНАРНЫЕ ПЕРЕМЕННЫЕ / ОПТИМАЛЬНОЕ РЕШЕНИЕ / ФОРМУЛА КАРДАНО / ЭВРИСТИЧЕСКИЙ АЛГОРИТМ / QUADRATIC PROGRAMMING / BINARY VARIABLES / OPTIMAL SOLUTION / CARDANO FORMULA / HEURISTIC ALGORITHM
Аннотация научной статьи по математике, автор научной работы — Попов Георгий Александрович
Рассматривается обобщение классической задачи квадратичного программирования , когда наряду с линейными ограничениями допускается наличие квадратичных ограничений. Представлен случай, когда переменные могут принимать только бинарные значения 0 или 1. Подобные задачи важны при выборе оптимальных структур систем, состоящих из большого числа вариантов, и выбор или отказ от выбора отдельных вариантов равносилен значениям 1 или 0 соответствующих бинарных переменных. Описана процедура сведения указанной задачи на основе метода штрафных функций к задаче полиномиального программирования четвертой степени, когда все слагаемые, кроме одного, имеющего четвертую степень, имеют степень не более второй. Решение полученной оптимизационной задачи сведено к решению системы уравнений, содержащих только бинарные переменные . Предложен эвристический рекуррентный алгоритм решения полученной системы уравнений, описаны варианты построения начального варианта решения, а также параметров, используемых в предложенном методе. В процессе сведения использованы классические формулы Кардано для корней кубического уравнения, для практического нахождения которых получены соотношения и описана процедура вычисления. Полученный алгоритм может быть использован также при решении многих задач дискретной математики.
i Надоели баннеры? Вы всегда можете отключить рекламу.
Похожие темы научных работ по математике , автор научной работы — Попов Георгий Александрович
Решение задачи оптимизации закупок с помощью обратных вычислений
Об одном способе построения начального допустимого базиса в задачах оптимизации
Решение задачи равномерного распределения ресурсов методом динамического программирования
Параллельный алгоритм целочисленного квадратичного программирования
Некоторые структурные свойства квадратичных булевых пороговых функций
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.
ALGORITHM OF SOLVING THE PROBLEMS OF THE BINARY SQUARE PROGRAMMING BY THE METHOD OF PENALTY FUNCTIONS
In this paper the author analyses generalization of the classical quadratic programming problem, when along with linear constraints quadratic constraints are allowed. The author consider the case when variables can take only binary values 0 or 1. Such problems are important when choice of the optimal structures of systems covers a large number of variants, and the choice or refusal to select individual variants is equivalent to values 1 or 0 of the corresponding binary variables . There is described the procedure of reducing the indicated problem to the fourth-degree polynomial programming problem on the basis of the penalty method, when all terms are no greater than in the second power, except one having a fourth power. The solution of the obtained optimization problem is reduced to solving a system of equations containing only binary variables . The author proposes a heuristic recursive algorithm for solving the resulting system of equations, and variants of constructing the initial version of the solution. The parameters used in the proposed method are described. In the process of reduction, there are used the classical Cardano formulas for the roots of a cubic equation, for the practical finding of which the relations are obtained and the calculation procedure is described. The algorithm given in this paper can also be used to solve many problems of discrete mathematics.
Текст научной работы на тему «Алгоритм решения задач бинарного квадратичного программирования методом штрафных функций»
DOI: 10.24143/2072-9502-2017-2-48-61 УДК 004.056.5
АЛГОРИТМ РЕШЕНИЯ ЗАДАЧ БИНАРНОГО КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ МЕТОДОМ ШТРАФНЫХ ФУНКЦИЙ
Рассматривается обобщение классической задачи квадратичного программирования, когда наряду с линейными ограничениями допускается наличие квадратичных ограничений. Представлен случай, когда переменные могут принимать только бинарные значения — 0 или 1. Подобные задачи важны при выборе оптимальных структур систем, состоящих из большого числа вариантов, и выбор или отказ от выбора отдельных вариантов равносилен значениям 1 или 0 соответствующих бинарных переменных. Описана процедура сведения указанной задачи на основе метода штрафных функций к задаче полиномиального программирования четвертой степени, когда все слагаемые, кроме одного, имеющего четвертую степень, имеют степень не более второй. Решение полученной оптимизационной задачи сведено к решению системы уравнений, содержащих только бинарные переменные. Предложен эвристический рекуррентный алгоритм решения полученной системы уравнений, описаны варианты построения начального варианта решения, а также параметров, используемых в предложенном методе. В процессе сведения использованы классические формулы Кардано для корней кубического уравнения, для практического нахождения которых получены соотношения и описана процедура вычисления. Полученный алгоритм может быть использован также при решении многих задач дискретной математики.
Ключевые слова: квадратичное программирование, бинарные переменные, оптимальное решение, формула Кардано, эвристический алгоритм.
При решении задач принятия решений часто возникают ситуации, когда результирующее решение выбирается из большого набора вариантов (альтернатив).
Формализованное описание подобных задач часто осуществляется путем введения бинарных переменных по каждой альтернативе, которые могут принимать только два значения, например 0 и 1. Если целевые функции и ограничения в подобной задаче могут быть представлены аналитическими выражениями, то полученные формализованные модели называются задачами математического бинарного (или булевого) программирования.
Наиболее важными задачами бинарного программирования являются задачи линейного и квадратичного бинарного программирования, когда целевые функции и ограничения описывают линейными и квадратичными функциями соответственно, поскольку во многих приложениях задач математического программирования использование более сложных функций не позволяет повысить качество результатов ввиду наличия больших погрешностей в исходных данных, сравнимых с погрешностями самой модели.
Вышеупомянутые задачи являются частным случаем задач целочисленного математического программирования, и поэтому, казалось бы, могут быть решены методами, используемыми при решении задач целочисленного программирования. Однако одна важная особенность делает все известные методы решения задач целочисленного программирования практически неприемлемыми и бесполезными при решении указанных задач: число альтернатив часто бывает настолько большим, что существующие вычислительные средства оказываются неспособными за разумное время найти решение указанных задач. Так, например, в работах [1, 2] приведены формализованные постановки задачи составления учебного расписания, когда в качестве бинарных переменных берутся следующие: xpgad = 1, если занятие по d-й дисциплине у g-й подгруппы проводится в a-й аудитории наp-й паре, и xpgad = 0 в противном случае. Это
означает, что в данной задаче индекс суммирования i представлен набором pgad. Тогда, как показано в [1], в этом случае число всех возможных переменных для типового вуза с общим числом студентов порядка 7 500 достигает 150 миллионов переменных xpgad, что делает практически невозможным автоматизированное решение указанной задачи на основе алгоритмов целочисленного программирования.
Бинарное программирование как самостоятельное научное направление исследований было выделено еще в 60-е гг. ХХ в.; наиболее важные методы решения задач бинарного программирования, применявшиеся в то время, можно найти в [3]. В дальнейшем сколь-нибудь значимых результатов по решению задач бинарного программирования с большим числом переменных, по-видимому, получить не удалось. Состояние исследований в данном направлении в настоящее время отражено в [4, 5]. Отметим также отсутствие значимых результатов по использованию современных эвристических методов оптимизации (генетических алгоритмов, нейронных сетей, методов муравьиных или пчелиных колоний и др.), которые доказали свою эффективность при решении многих других типов задач оптимизации.
Ниже нами предлагаются набор условий для нахождения оптимального решения и построенный на их основе эвристический алгоритм решения.
1. Формализация задачи с использованием метода штрафных функций
В анализируемой ниже задаче квадратичного программирования ограничения заданы в виде равенств, в то время как в классической постановке эти ограничения имеют форму неравенств. Однако способы сведения ограничений в виде неравенств к ограничениям в виде равенств и обратно известны, поэтому предлагаемая постановка охватывает все классические постановки задач квадратичного программирования. Приведем формализованную постановку задачи.
Пусть задан набор переменных x, (i = 1; N ), каждая из которых принимает только значения 0 или 1, т. е. является бинарной переменной; x = (x1, x2, . xN). Тогда задачей квадратичного бинарного программирования является следующая оптимизационная задача:
Z(x) = ZZA,xx + ZBx + C ^ max, (1)
Для нас представляет интерес также несколько другая запись целевой функции (1):
Z(x) = Z ZZAjxx +ZBSx, + C ^max, (3)
s=1 у i=1 j>1 i=1 у
т. е. квадратичное выражение в целевой функции (1) представляется как сумма из S отдельных квадратичных выражений. Именно в таком виде представлена целевая функция в задаче формирования расписания занятий в [1], где S = 19, каждое квадратичное выражение в сумме по S имеет относительно простой вид и соответствует разным ограничениям задачи, число которых составляет порядка 30.
Отметим, что поскольку общее число возможных вариантов решений задачи (1), (2) ограничено (не превосходит 2N), то задача (1), (2) всегда имеет решение. Без ограничения общности можно считать C = 0.
Как было указано выше, для решения задачи (1), (2) предлагается использовать метод штрафных функций — т. е. решение задачи (1), (2) заменяется решением следующей задачи безусловной оптимизации (т. е. задачи без ограничений):
_ _ NN N K f N Л2
Z(x;Lkk = 1;K) = ZZAjxx +ZBx I ZGf^r + E(k) + С 1 ^ max, (4)
i=1 j>1 i=1 k=1 v i=1 у
где tk = —I ZG(k)x, + E^k) l>0 (k = 1;K) — вспомогательные переменные; Lk > 0 трактуется как
величина штрафа за нарушение k-го ограничения: если хотя бы одно из слагаемых в последней сумме не равно нулю (т. е. положительно), то значение целевой функции при больших значени-
ях Lk резко уменьшается. Поэтому оптимальное решение вынуждено стремиться обеспечить выполнение ограничений (2), при которых все слагаемые последней суммы равны нулю. Известно, что при достаточно больших значениях Lk для всех k решения (x*,i = 1;N> задач (4) и (1), (2) совпадают, поэтому вместо решения задачи (1), (2) можно решать задачу (4).
В записи задачи (4) учтены все ограничения задачи (1), (2), кроме самого важного — переменные xi являются бинарными. Для учета данного ограничения предлагается добавить в целевую функцию задачи еще по одному слагаемому на каждую переменную:
_ __NN N K f N Л2 N
Z(x;Lkkk = 1;K;L) = ZZ A.xx — ZL[ZGf^ + E(k) + tk I -(1 -x))2 ^ max, (5)
i=1 J>1 i=1 k=1 V i=1 ) i=1
где L >> max(Lj). Действительно, если для некоторого индекса i выражение xi (1 — xi) отличается
значимо от нуля, в целевой функции Z(x; Lk. k = 1; K; L) появляется большое по модулю отрицательное слагаемое (последняя сумма в правой части), которое сильно уменьшает значение целевой функции по сравнению со случаем xi (1 — xi) = 0.
В результате исходная задача квадратичного программирования переходит в задачу полиномиального программирования четвертой степени. Однако, как будет следовать из приводимых ниже рассуждений, задача (5) по ряду важных свойств аналогична задаче квадратичного программирования.
2. Базовый случай одной переменной
Покажем вначале, что при достаточно больших L решение задачи (5) получается из решения задачи (4) путем целочисленного округления и при этом обеспечивается выполнение требования бинарности переменных xi.
Рассмотрим вначале случай функции одной переменной (т. е. N = 1). Тогда левую часть соотношения (5) после деления обеих частей на L можно записать в виде
или, после обозначений a = a(L) = -1 A + ZLk(G(k))2I, b = b(L) = -1 В — 2^LkG(k)(E(k) + tk)|,
e(L) = «L [ Zl (e (k) + tk ij, получаем f (x, L) = a(L) x2 + b(L) x — e(L) — ( x(1 — x) )2.
Проведем замену переменных 2 = 2 X — 1, т. е. х = ^ . Тогда, полагая
f (—) = f (L) = А (——, L) , с(Ь) = — е(L) +—(4-) +—(Ц-, из последнего соотношения выводим следующее представление задачи (5):
В силу необходимого условия экстремума из (6) следует уравнение
(—, Ь) = — а( Ь) — +—(а(Ь) + Ъ(Ь)) — (—2 — 1) — = 0. а— 2 2
Таким образом, точки максимума функции А—) являются корнями кубического уравнения
г> + | -1 -2а(Ц) 12 -|(а(Ц) + Ь(Ц)) = 0.
Уравнение (7) имеет в комплексной плоскости три корня Zi(L) (/ = 1, 2, 3), которые упорядочим лексикографически, т. е. в порядке возрастания их действительной части; если же действительные части равны, то в порядке возрастания их мнимых частей. Покажем, что корни Zl(L) и z3(Ц) симметричны относительно корня z2(Ц). Для этого воспользуемся формулами Кардано
[6, с. 235]: если дано кубическое уравнение г3 + р 2 + q = 0, то (напомним, кубический корень
в поле комплексных чисел имеет три возможных значения):
причем первый и второй кубические корни в правой части выбираются таким образом, чтобы их произведение равнялось -р/3. В нашем случае р = -1 -2а(Ц), ч = -2(а(Ц) + Ь(Ц)). Кроме того,
оба квадратных корня в правой части должны быть одинаковыми.
Использование формулы (8) для анализа симметричности корней, ввиду указанных ограничений, неудобно. В частности, необходимо перебрать до девяти пар чисел — все комбинации пар трех значений кубического корня первого слагаемого в правой части (8) и трех — второго слагаемого, поэтому преобразуем выражение (8) в более удобную для анализа форму. Умножим второе слагаемое в правой части (8) на сопряженное выражение — по сути, сопряженным является первое слагаемой в (8). Получим
У 2 V 4 27 V 2 V
д-+р3 I—1— = 3 -1 + £+2 +. 2 4 27