Экстремум в задачах линейного программирования множественный


Раздел математики. Предметом которого является изучение и решение экстремальных задач на конечных множествах. Такие задачи записываются в сокращенном виде следующим образом:

M={a1an}

и пусть

f

быть числовой функцией. Определенной на элементах

M

. Задача состоит в том. Чтобы найти элемент

ajM

на котором абсолютный минимум (или абсолютный максимум)

f

на

M

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

f(x)xM extr 

(f(x)xMmin  or  f(x)xMmax).

Дискретное программирование имеет дело только с нетривиальными задачами этого класса задач. Которые удовлетворяют следующим дополнительным условиям.

Таким образом. В задаче

n=|M|

должно быть достаточно большим. Чтобы задача не была разрешима прямыми проверками значений

f(ai)

вручную или с помощью электронного компьютера. Таким образом, в коммивояжера (которая является типичной задачей дискретного программирования) число возможностей пересечь $ m $ точек равно

m

очки есть

(m1)!cm(m1e)m1.

В задачах минимизации булевых функций (ср. Булевы функции. Минимизация; булевы функции. Метрическая теория)

|M|>22n

.

2) Проблема не должна быть регулярной.

Задача называется регулярной . Если: а) для каждой

aiM

существует непустая окрестность

S(ai,M)

и

|S(ai,M)||M|

; б) локальный экстремум

f

, то есть точка

ai

такая . Что

f(ai)=extrf(x)

,

xS(ai,M)

в) локальный экстремум совпадает по крайней мере с одним глобальным экстремумом.

Таким образом. Дискретное программирование имеет дело с проблемами. Включающими. Вообще говоря. Несколько локальных экстремумов. В типичных случаях число локальных экстремумов очень велико. Таким образом. В задачах целочисленного

линейного программирования

x1xk

, число элементов в

M

не превышает

2k

, и число локальных экстремумов может быть равно

 const 2k/k

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

Достаточно универсальные методы. Такие как методы ветвей и границ [1] и их различные модификации-это методы. Основанные на неявном перечислении. Они эффективно используются при решении специализированных задач дискретного программирования. Однако существует широкий класс проблем. Для которых любой неявный метод перечисления лишь немного менее сложен. Чем явные методы перечисления. Другим источником математических трудностей в задачах дискретного программирования является то. Что множество $ M$. На котором ищется экстремум $ f$. Часто задается в неявной форме. Таким образом. В задачах целочисленного линейного программирования множество $ M $

M

на котором экстремум

f

искомое часто дается в неявной форме. Таким образом. В задачах целочисленного линейного программирования множество

M

определяется как совокупность целочисленных решений системы линейных неравенств. Если

M

определяется таким образом или даже более сложным образом. То не только задача полного перечисления

M

, но даже задание одного элемента

M

становится нетривиальной задачей. В результате основные результаты в дискретном программировании были получены при решении и изучении более узких классов задач. К ним относятся транспортные проблемы (ср.

Транспортная задача), задача коммивояжера и задача мультипродавца. Целочисленное линейное программирование. Задачи планирования (см.

k

— ценная логика и т.

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

Обзор методов аппроксимации решения задач дискретным программированием приведен в работе [3].

Статистический подход к задачам дискретного программирования представляет как теоретический. Так и прикладной интерес. Один говорит. Что подмножество

{Z}

быть представимым в виде

{Z}=n=1{Z}n

, где

|{Z}i|>|{Z}j|

если

i>j

и

|{Z}n|

если

n

. Один говорит. Что подмножество

{Z}=n=1{Z}n, {Z}n{Z}n,

содержит почти все проблемы $ Z $ if

Z

если

limn|{Z}n||{Z}|=1.

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

{Z}

почти всех проблем

{Z}

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

F(x1xn)

неразрешима в классе локальных алгоритмов. Если

kl const 2n

, где

k

является индексом локального алгоритма и

l

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

k=2

,

l=1

[5]. Аналогичное значительное сокращение труда. Затрачиваемого почти на все задачи. Может быть получено для экстремальных задач на графах. Построения оптимальных покрытий и т. Д.

Рекомендации

[1] А. А. Корбут. Ю. Ю. Финкельштейн, MR0261958 Zbl 0839.90116 Zbl 0576.90069 Zbl 0218.90034
[2] В. К. Коробков, Пробл. Кибернетики , 14 (1965) с. 297-299)
[3] Ю. Ю. Финкельштейн,
[4] , Дискретная математика и математические проблемы кибернетики

, 1 , Москва (1974) (На русском языке) Zbl 1185.68346

[5] Ю. И. Журавлев, Дискрет. Анал. , 3 (1964) С. 41-77 (На русском языке)

Дискретное программирование. Или теории вероятностей, исследования операцийи информатики. Ниже приводится ряд эталонных ссылок из западной литературы.

Рекомендации

[а1] M. Gondran, M. Minoux, MR0745802 Zbl 0611.90096
[а2] E. L. Lawler, MR0439106 Zbl 0413.90040
[а3] E. L. Lawler (ed.) J. K. Lenstra (ed.) A. H. G. Rinnooy Kan (ed.) D. B. Shmoys (ed.) , The traveling salesman problem: a guided tour of combinatorial optimization

, Wiley (1985) Zbl 0562.00014

[а4] Пападимитриу. К. Штейглиц. Алгоритмы и сложностьMR0663728 Zbl 0503.90060
[a5] A. Schrijver, MR0874114 Zbl 0665.90063

Как процитировать Эту запись:
Дискретное программирование. Энциклопедия математики. URL: http://encyclopediaofmath.org/index.php?title=Discrete_programming&oldid=51599