Выбирая теперь произвольную пару чисел, например хх = 0, х2 = 3, означающих точку на прямой АВ, и вычислим значение целевой функции в этой точке. Оно оказывается равным у=3. Выберем теперь точку хх = 2, х2 = 3, лежащую на прямой СД и вычислим значение целевой функции в этой точке. Оно оказывается равным у=1.
Поскольку целевая функция у(хг,х2) непрерывно зависит от
своих аргументов, на основе полученного результата можно утверждать, что с передвижением прямой АВ вправо значение целевой функции возрастает, что показано на рисунке с помощью жирной стрелки. Продолжая эти рассуждения, приходим к выводу, что максимального значения целевая функция достигает в точке 0(4,2), поскольку далейшее движение прямой вправо выводит ее за пределы области допустимых значений. Таким образом, решением исходной задачи является пара чисел хх = 4, х2 = 2 , для которой максимальное значение функции равно 10.
Отметим, кстати, что если бы целевая функция имела вид у= х1 + 2х2, то есть изображающая ее прямая была бы параллельна
отрезку ОН, ограничивающему область допустимых значений, то решением задачи было бы все множество точек, принадлежащих этому отрезку.
Необходимо особо подчеркнуть, что в тех случаях, когда решаются достаточно часто встречающиеся в практике многокритериальные задачи, то вводятся несколько функций полезности. Одним из наиболее распространенных подходов к их решению является при этом ее сведение тем или иным способом к одному критерию, чаще всего путем свертки.
Как и многие другие практические задачи, задачи математического программирования довольно часто приходится решать с учетом возможного риска, а также в условиях значительной информационной и иной неопределенности. Наличие неопределенности в таких задачах может быть обусловлено как нечеткостью описания множества альтернатив, так недостаточно четким представлением ЛПР или экспертов о характере самой функции полезности.
В дальнейшем будем рассматривать класс задач, в которых нечетко описано множество альтернатив и четко описана функция полезности. Пример такой задачи можно получить, если представить, что границы области допустимых значений на рис. 49 размыты, то есть определены недостаточно четко.
Еще одним примером может служить выбор рационального варианта пути студента в университет при условии отсутствия четкости и регулярности в работе используемых им видов городского транспорта. В качестве целевой функции при этом могут рассматриваться либо время пребывания в пути, либо стоимость проезда, обе из которых необходимо минимизировать (при условии, конечно, что студент честно пытается оплатить свой проезд). Подобные задачи обычно и называются задачами нечеткого математического программирования.
Цель настоящего учебного пособия ограничивается преимущественно только рассмотрением основных идей существующих подходов к решению различных видов задач нечеткого математического программирования, без детального анализа характерных особенностей применяемых методов.
Archive for февраля, 2010
Графическое решение задачи линейного математического программирования
Четверг, февраля 25, 2010Основные подходы к решению задач математического программирования
Четверг, февраля 18, 2010При постановке, анализе и решении задач нечеткого математического программирования будем опираться на основные идеи следующих двух наиболее распространенных подходов к нахождению их решения. Оба этих подхода представляются логически вполне обоснованными и рациональными с точки зрения сущности обеспечиваемых ими результатов.
Сущность первого подхода заключается в том, что исходная задача нечеткого математического программирования формулируется в виде задачи достижения некоторой нечетко определенной цели. Эта цель 0(х) должна достигаться на некотором множестве альтернатив х е X. При этом решением задачи является нахождение пересечения этого нечеткого множества целей С(х) и нечеткого множества имеющихся при этом ограничений С(х\ как это показано на рис. 50 для двумерного случая.
При этом в качестве ограничений здесь обычно выступают допустимые альтернативы х, под которыми могут пониматься, например, различные виды располагаемых ресурсов, необходимых для достижения желаемой цели, или определенное их соотношение.
В процессе решения задачи на основе этого подхода в принципе не исключен случай, когда эти множества оказываются непересекающимися, то есть О (х) П С(х) = 0. Иными словами, задача при выбранных целях и существующих ограничениях не имеет решения (рис. 51). Это может быть следствием как завышенных целей, недостижимых при данных условиях, так и достаточно жестких ограничений.
Для преодоления такой ситуации необходимо взаимно "подтянуть" друг к другу области целей и ограничений. Это можно сделать как путем определенного снижения желаемых целей, так и путем некоторого смягчения имеющихся ограничений. Правда, если эти ограничения имеют ресурсный характер, и их смягчить не удается, следует пересматривать цели. Такой процесс постепенного "сближения" множеств необходимо продолжать до тех пор, пока не образуется некоторая область из пересечения.
Второй подход к решению задач нечеткого математического программирования
Среда, февраля 10, 2010Второй подход к решению задач нечеткого математического программирования основан на идее, использующей представление этих задач таким образом, что их решения выбираются подобно тому, как это обычно делается в задачах многокритериальной оптимизации. При этом считается, что в решении исходной задачи должны присутствовать только те альтернативы (не сравнимые между собой в рамках данной задачи), которые не доминируются строго никакими другими альтернативами.
Под строгим доминированием здесь понимается такое отношение предпочтения между альтернативами из рассматриваемого их множества, при котором одна какая-то альтернатива (или несколько альтернатив) являются существенно лучшими по отношению к некоторому подмножеству других, которые в силу этого заведомо не могут с ней (или с подмножеством таких альтернатив) конкурировать.
При таком понимании решения задачи нечеткого математического программирования лицо, принимающее решение (ЛПР), получает в свое распоряжение возможность в большей мере использовать свои субъективные суждения или представления о некоторой реальной ситуации, которые не могли быть формализованы в традиционной математической постановке исходной задачи математического программирования. Следовательно, в процессе решения задач подобного рода ЛПР, оперируя методами теории нечетких множеств, может с их помощью вполне руководствоваться своими субъективными суждениями наравне с другой располагаемой информацией об исследуемом объекте или системе.
Особый класс задач, встречающихся в теории автоматизированного управления и принятия решений, образуют так называемые игровые задачи, в которых исход выбора и реализации конкретного варианта управления или, соответственно, результат принятия решения, определяются не только выбором самого лица, принимающего решение, но и выбором его партнеров. Конечно, слово "партнер" здесь употреблено условно и в достаточно общем смысле, поскольку в подавляющем большинстве случаев оно относится скорее к оппоненту, а то и к противнику ЛПР.
Типичным примером такой задачи в управлении являются действия летчика во время воздушного боя. Не менее типичным примером задачи игрового характера в процессе принятия управленческого решения может служить ситуация подготовки условий ответственного контракта, когда вы, как продавец, преследуя цель наиболее выгодной продажи, должны также предугадывать возможные действия покупателя вашей продукции, стремящегося к максимальному обеспечению своих собственных интересов.
Математическая постановка задач такого класса определяется заложенными в них принципами принятия решений.
Задача достижения нечетко определенной цели (подход Беллмана-Заде)
Среда, февраля 3, 2010Рассмотрим случай решения задачи с нечетко определенной целью. При этом будем полагать, что цель, которую преследует лицо, принимающее решение, и множество альтернатив, имеющихся в его распоряжении, представляют собой некоторые равноправные по своей значимости нечеткие подмножества некоторого универсального множества альтернатив. Описываемый подход получил свое название по имени известных математиков Р. Беллмана, который разрабатывал методы решения задач математического программирования, и Л. Заде, который распространил их на случай нечеткого описания цели.
Пусть X представляет собой это универсальное множество альтернатив х е X. Нечеткой целью в множестве X пусть является некоторое нечеткое подмножество этого множества С с: X. Как обычно, нечеткое подмножество описывается функцией принадлежности /лс : X —> [ОД], означающей степень принадлежности каждой
конкретной альтернативе этому подмножеству, в данном случае подмножеству цели С(х).
Пусть, например, X представляет собой некоторую числовую ось. Тогда нечеткой целью принятия решения могут выступать такие нечеткие множества, как "величина х должна быть примерно равна пяти" или "величина х должна ненамного отличаться от шести". Будем полагать, что при этом используемые нечеткие понятия вполне четко описаны функциями принадлежности, соответствующими данным нечетким множествам. Это означает, в частности, что чем больше степень принадлежности /ис какой-либо альтернативы х нечеткому множеству цели С(х), то есть чем большим будет значение /ис (х), тем более высокой будет являться степень достижения этой
цели при выборе данной альтернативы л: в качестве решения задачи.
В этом смысле нечеткое описание цели в рамках подхода Беллмана-Заде можно одновременно считать и функцией полезности в обычной задаче нечеткого математического программирования, если нормировать к единице значения этой функции.
Нечеткие ограничения, представляющие собой, по сути, множество допустимых альтернатив, также описываются некоторыми нечеткими подмножествами С из того же универсального множества X.
Пусть универсальное множество Х-^> К1, то есть представляет собой числовую ось. В этом случае нечеткие ограничения могут иметь следующий вид: "х не должен быть слишком большим" или "х должен быть намного больше нуля". Предполагается, что эти смысловые понятия достаточно четко описаны функциями принадлежности соответствующих нечетких множеств, которые будем обозначать /ис.
Более общей следует считать такую постановку задачи, при которой нечеткие цели и нечеткие ограничения представляют собой подмножества различных универсальных множеств Хх и Х2.
Пусть X представляет собой некоторое универсальное множество альтернатив и пусть задано однозначное его отображение <р : X —> У в другое универсальное множество У. В этом случае элементы множества У можно интерпретировать как отклики или реакции системы на входные воздействия (управления) X в задаче автоматизированного управления, или как некоторые оценки или некоторый эффект (результат) выбора соответствующих альтернатив из множества^в задаче принятия решений.
Нечетко описанная цель при этом задается в виде некоторого нечеткого подмножества С универсального множества реакций и оценок У, иными словами, С, то есть в виде функции принадлежности /ис : У —> [0,1]. С учетом того, что можно ввести в рассмотрение
преобразование у=ф(х), получим /л0(у) = /л0((р(х)). Таким образом, исходная задача может рассматриваться как задача достижения нечетко определенной цели /л0 при заданных нечетких ограничениях //с(х).
Классификация задач нечеткого математического программирования
Вторник, февраля 2, 2010При решении задач нечеткого математического программирования важно предварительно определить, к какому из типичных классов задач она относится, поскольку от этого существенно зависит выбор рационального метода решения. В связи с этим рассмотрим основные виды задач нечеткого математического программирования. Будем рассматривать стандартную задачу математического программирования в следующем виде:
/(х)-> тах,
^Дх)>0,/ = 1~^.(1)
При этом сразу же подчеркнем, что в процессе моделирования в такой форме реальных задач автоматизированного управления или принятия решений часто в распоряжении исследователя-математика могут оказаться только нечеткие описания функций /(х) и р1 (х). В практике нередки случаи, когда нечетко могут быть описаны параметры, от которых зависят эти функции. Например, задаются только определенные интервалы, в которых могут находиться значения указанных параметров.
Нечетко может быть описано и само множество X. Вообще, нечеткое описание системы автоматизированного управления или системы принятия решений может, например, отражать недостаточность информации об этих системах или выступать некоторой формой приближенного описания системы, достаточного для решения поставленной задачи.
В некоторых случаях даже точно описанные множество ограничений или множество допустимых альтернатив могут выступать только некоторым приближенным отражением реальности. Этот тезис следует понимать в том смысле, что в реальной действительности встречаются ситуации, когда некоторые альтернативы, находящиеся вне рассматриваемого множества, то есть должны считаться недопустимыми. Однако именно они в той или иной мере могут быть более желательными или даже предпочтительными для ЛПР, чем отдельные (или даже все) альтернативы, которые находятся в составе исходного множества.
В качестве примера можно привести следующую задачу, пусть множеством допустимых альтернатив является некоторая совокупность способов различного распределения ресурсов. При этом наличие четкой границы множества может привести к тому, что ресурсы, лежащие за ее пределами и способные дать перевешивающий общий эффект, выпадут из рассмотрения. В этом случае результат выбора любого варианта из рассматриваемого множества альтернатив окажется менее желательным для ЛПР, и наилучшее решение не будет найдено.