Характеристика задач нечеткого математического программирования

В последние годы, наряду с " классическими" задачами математического программирования, появились задачи в так называемой " нечеткой" постановке.

Классическое математическое программирование и его разновидности – в значительной степени нормативная методология эффективного выбора. Нечеткое же программирование выделяет естественную множественность неточно определенных целей, значений и ограничений. При этом оптимальность определяется и в терминах поведения, и как качество, присущее решению (основные сведения об аппарате нечеткой логики приведены в Приложении А).

Главная цель нечеткого математического программирования (НМП) – помочь лицу, принимающему решение, разобраться в выдвинутых им допущениях. Нечеткий подход не подменяет собой простейшего анализа в поисках разумной точности. Он облегчает задачу лица, принимающего решения, позволяя ему не формулировать явно точные ограничения. Вот почему плодотворный обмен идеями между теорией нечетких множеств и классическим программированием может явиться значительным шагом к созданию новых методов.

Стандартная задача нечеткого математического программирования формулируется обычно как задача максимизации (или минимизации) заданной функции на заданном множестве допустимых альтернатив, которое описывается системой равенств или неравенств. Например:

f(x) → max, j_i(x) £ 0, i = 1,..., m, xÎ X,

где X – заданное множество альтернатив, f: X→ R¹ и j: X→ R¹ – заданные функции.

При моделировании в нечеткой форме реальных задач принятия решений в распоряжении исследователя-математика могут оказаться лишь нечеткие описания функции f и j, параметров, от которых зависят эти функции, да и самого множества X. Таким образом, задача стандартного математического программирования превратится в задачу нечеткого математического программирования.

Формы нечеткого описания исходной информации в задачах принятия решений могут быть различными; отсюда и различия в математических формулировках соответствующих задач нечеткого математического программирования.

Перечислим некоторые из таких постановок [8а].

Задача 1. Максимизация заданной обычной функции f: X→ R¹ на заданном нечетком множестве допустимых альтернатив m_: X→ [0, 1].

Задача 2. Нечеткий вариант стандартной задачи математического программирования. Пусть определена следующая задача математического программирования:

f(x) → max,

j(x) £ 0, xÎ X,

 

Нечеткий вариант этой задачи получается, если “смягчить” ограничения, т.е. допустить возможность их нарушения с той или иной степенью. Кроме того, вместо максимизации функции f(x) можно стремиться к достижению некоторого заданного значения этой функции, причем различным отклонениям значения функции от этой величины приписывать различные степени допустимости.

Задача 3. Нечетко описана “максимизируемая” функция, т.е. задано отображение m_j: X´ R¹ → [0, 1], где Х - универсальное множество альтернатив, R¹– числовая ось.

В этом случае функция m_j(x₀, r) при каждом фиксированном x₀ Î X представляет собой нечеткое описание оценки результата выбора альтернативы x₀ (нечеткую оценку альтернативы x₀) или нечетко известную реакцию управляемой системы на управление x₀. Задано также нечеткое множество допустимых альтернатив m_c: X→ [0, 1].

Задача 4. Заданы обычная максимизируемая функция f: X→ R¹ и система ограничений вида j_i(x) £ b_i, i = 1,..., m, причем параметры в описаниях функций j_i(x) заданы в форме нечетких множеств.

Задача 5. Нечетко описаны как параметры функций, определяющих ограничения задачи, так и самой максимизируемой функции.

Рассмотрим, например подробнее задачу линейного программирования с нечёткими коэффициентами. Нечеткость в постановке задачи математического программирования может содержаться как в описании множества альтернатив, так и в описании целевой функции.

 

f(x) → max, g(x) £ 0, xÎ X. (8.1)

 

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

Нечеткую обстановку можно рассматривать как множество Хальтернатив вместе с его нечеткими подмножествами, представляющими собой нечетко сформулированные критерии (цели и ограничения), т.е. как систему (Х, f₀, f₁, ..., f_n). Принять во внимание по возможности все критерии в такой задаче означает построить функцию

D = f₀Ç f₁Ç …Ç f_n, (8.2)

в которую цели и ограничения входят одинаковым образом.

Решение можно определить как нечеткое подмножество универсального множества альтернатив. Оптимум соответствует той области Х, элементы которой максимизируют D. Это и есть случай нечеткого математического программирования.

Очевидно, неразумно в реальных ситуациях проводить резкую границу для множества допустимых альтернатив, поскольку может случится так, что распределения, лежащие за этой границей, дадут эффект, превышающий меньшую желательность для лица принимающего решения.

Например, ясно, что при несовместных распределениях эта область пустая. В этом случае налицо необходимость модификации ограничений. Желательно выяснить, как изменить ограничения задачи, чтобы появились допустимые решения, и задача стала разрешимой.

В таких случаях представляется целесообразным вводить нечеткое множество допустимых элементов и, следовательно, рассматривать проблему как задачу НМП с применением подхода, дающего человеку больше свободы в использовании его субъективных представлений о ситуации.

Формы нечеткого описания исходной информации в задачах принятия решений могут быть различными; отсюда и различия в математических формулировках соответствующих задач НМП.

Нечеткий вариант стандартной задачи математического программирования получается, если " смягчить" ограничения, т.е. допустить возможность их нарушения с той или иной степенью. Кроме того, вместо максимизации целевой функции f(x) можно стремиться к достижению некоторого заданного ее значения, причем различным отклонениям значения f(x) от этой величины приписывать различные степени допустимости (например, чем больше отклонение, тем меньше степень его допустимости).

Пустьа – заданная величина функции цели f(x), достижение которой считается достаточным для выполнения цели принятия решений, и пусть имеется пороговый уровень b такой, что неравенство f(x) < a–b означает сильное нарушение неравенства f(x) ³ a. Тогда функцию принадлежности для нечеткой функции цели можно определить следующим образом:

(8.3)

где m_a – функция принадлежности, описывающая степени выполнения соответствующего неравенства с точки зрения лица, принимающего решения.

Аналогично определяется функция принадлежности m_c(x) для нечетких ограничений. В результате исходная задача оказывается сформулированной в форме задачи выполнения нечетко определенной цели, к которой применим подход Беллмана-Заде (8.2) [8б].

При моделировании ситуации в форме задачи линейного программирования

min {cx½ Ax£ b, x ³ 0} (8.4)

 

о коэффициентахa_ij, b_i и c_i известно лишь то, что они находятся в некотором множестве, отражающем все реальные возможности.

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

Рассмотрим задачу нахождения минимума на заданной области. Пусть задана область вида:

P = { x ½ a_i1x₁ + a_i2x₂ + … + a_inx_n Í b_i, }, (8.5)

где a_ij, b_i – нечеткие подмножества множества R, а бинарная операция " +" обозначает сложение нечетких множеств.

Требуется найти на заданной области.

Коэффициент при каждой переменной в ограничениях можно считать функцией полезности, определенной на числовой оси. Можно считать, что эти коэффициенты дают субъективную оценку различных возможностей, включая, таким образом, другие, не определенные ограничения.

Сведём решение исходной задачи к решению ряда задач линейного программирования. Для этого введём дискретные a-уровни [8в, 8г]. В результате нечёткие ограничения принимают следующий интервальный вид:

 

(8.6)

 

Таким образом, мы перешли от нечётких множеств к чётко определённым и теперь, зная, что σ –обычный интервал, можем записать нашу задачу в следующем виде (случай 2´ 2):

 

(a₁₁, a₁₂) x₁ + (c₁₁, c₁₂) x₂ Í (b₁₁, b₁₂)

(a₂₁, a₂₂) x₁ + (c₂₁, c₂₂) x₂ Í (b₂₁, b₂₂). (8.7)

 

Теперь, чтобы привести задачу к виду обычной задаче линейного программирования, нам достаточно записать неравенства отдельно по левому и правому краям интервалов, с учётом знаков неравенства. Т.е., мы приведём систему к следующему виду:

a₁₁x₁ + c₁₁x₂ ³ b₁₁

a₁₂ x₁ + c₁₂x₂ £ b₁₂

a₂₁x₁ + c₂₁x₂ ³ b₂₁

a₂₂ x₁ + c₂₂x₂ £ b₂₂. (8.8)

 

С помощью несложных преобразований мы перешли от задачи с нечёткими коэффициентами к задаче линейного программирования с чёткими коэффициентами, при этом количество ограничений увеличилось в два раза и полученную задачу мы можем решить симплексным методом.

Таким образом, из рассмотренного примера явно просматривается алгоритм решения задачи с нечеткими коэффициентами. Следуя ходу рассуждений в данном примере, составим алгоритм решения задачи. Он имеет вид:

 

Исходная задача

Вводим дискретные a-уровни

Ограничения принимают интервальный вид

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

Получаем задачу ЛП с четкими коэффициентами

Решаем полученную задачу симплекс-методом

 

Как видим, исходная задача НМП представляется в виде совокупности обычных задач линейного программирования на всевозможных множествах уровня множества допустимых альтернатив. Если альтернатива х₀ есть решение задачи на множестве уровня a, то можно считать что число a есть степень принадлежности альтернативы х₀ нечеткому множеству решений исходной задачи. Перебрав, таким образом, всевозможные значения a, получаем функцию принадлежности нечеткого решения.

Если же и компоненты целевой функции с_i являются нечеткими, то необходимо выбирать для каждого уровня a соответствующие границы множеств σ _a(c_J), в соответствии с правилами интервальной арифметики, минимизируя предварительно таким образом .

Из данного примера видно, что за гибкость приходится платить ценой увеличения размерности задачи. Фактически исходная задача с ограничениями по включению преобразуется в задачу с ограничениями в виде неравенств, с которыми легко обращаться; при этом такая цена не слишком высока, поскольку сохраняется возможность использования хорошо разработанных классических методов.

 

Проверочные вопросы

1. Задача линейного программирования.

2. Базисные и опорные решения системы линейных уравнений.

3. Основные свойства выпуклых множеств.

4. основные свойства задач линейного программирования.

5. Геометрический метод решения задач линейного программирования, его достоинства и недостатки.

6. Дайте геометрическую интерпретацию симплексного метода.

7. Докажите теорему об оптимальности плана и сформулируйте основные следствия из нее.

8. Основные этапы симплексного метода.

9. Дайте экономическую интерпретацию исходной и двойственной задач.

10. Сформулируйте и докажите первую теорему двойственности. Какой экономический смысл она имеет.

11. Вторая теорема двойственности. Связь между решениями исходной и двойственной задач.

12. Объективно обусловленные оценки ресурсов.

13. Приведите постановку транспортной задачи.

14. Как построить первоначальный опорный план транспортной задачи.

15. Метод потенциалов при решении транспортной задачи.

16. Задача целочисленного программирования.

17. Метод отсечения при решении задачи целочисленного программирования.

18. Метод ветвей и границ при решении задачи целочисленного программирования.

19. Сформулируйте задачу линейного программирования с нечеткими коэффициентами.

20. Алгоритм решения задачи линейного программирования с нечеткими коэффициентами.

 

 

* Также вместо термина «опорные решения» в литературе часто встречается термин «допустимые решения».

* Browder F. Mathematical Developments Arising from Hilbert Problems. American Math Society, 1976, Providense, RI.

* В данной работе сформулирована не сама вторая теорема двойственности в традиционной постановке, а ее следствие.

⇐ Предыдущая12345678

Поделиться: