Реферат: Нелинейное программирование

– Я уже задумывался, – сказал первый Скептик. – И решил действовать так. Сначала пойду куда глаза глядят. Потом спущусь в ближайшую низину и замерю её высоту высотомером. Запомню её расположение и перейду в новую случайную точку. Из нее снова спущусь в низину и снова взгляну на высотомер. Допустим, он покажет на сей раз меньшую высоту. Это значит, что вторая низина ниже первой, и там больше шансов найти воду. Затем...

– Что будет затем, ясно, – прервали его. – Но уверены ли вы, что найдёте воду прежде, чем свалитесь с ног?

– Могу ли я быть в этом уверен? Ведь я же Скептик! Просто это лучше, чем стоять сложа руки.

И первый Скептик скрылся в темноте.

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

– Уж не собираетесь ли вы по следам Кумады? – спросил его Винер, одновременно к чему-то прислушиваясь.

– Вы почти угадали. Но я поступлю несколько иначе. Спустившись в низину, я замерю её высоту, а затем буду бить по мячу ногой в разные стороны. Если мяч будет каждый раз скатываться назад, значит, поблизости нет перевала, за которым новая низина. Если же мяч не скатится ко мне, я отправлюсь по шпагату за ним, приду в низину, в которой он застрял, и замерю её высоту. И так далее...

– Но так можно обнаружить лишь недалёкий перевал.

– Что вы! У меня сильный удар. Меня обычно просят ударить от ворот.

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

– Вы правы... Тогда, пожалуй, я не буду стараться каждый раз ударить посильнее. Я буду чередовать сильные и слабые удары. Или, скажем, буду постепенно усиливать их, начав со слабых.

– Что ж, я желаю вам успеха. Если наградой вам и не послужит вода, то во всяком случае вы повысите свою спортивную форму.

– А я поступлю иначе, – обратился третий Скептик к Винеру. – Я отправлюсь просто бродить по острову, не стараясь найти наилучшее направление, и буду поглядывать на высотомер. Побродив, замечу, где самая низкая точка, и уже там начну поиски воды. Все эти разговоры убедили меня, что если у нас нет карты острова, то никакой разумной стратегии движения быть не может. Так зачем же тогда тратить время на возню с приборами? Но вы, кажется, не слушаете меня?

Где кончается асфальт

Когда приходится определять экстремум функции, у которой их много, задача намного усложняется. В этом случае обычно требуется не только найти экстремум (скажем, минимум), но и определить глобальный (общий) экстремум, или «минимум миниморум». К великому сожалению, большинство реальных математических задач, для которых ищется минимум, многоэкстремальны. Точно так же трудно найти местность, на которой одна вершина господствовала бы безраздельно на очень большом пространстве. Обычно даже вблизи высочайших вершин имеются вершины поменьше, но есть и относительно небольшая область, из которой подъём безусловно приведёт к высочайшей вершине. Эта область называется областью притяжения глобального экстремума. Достаточно выйти за границы этой области или оказаться за ними в начале поиска, как достижение глобального экстремума уже становится трудно гарантировать. Увеличиваются шансы попасть в местный (локальный) экстремум.

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

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

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

Существуют весьма изощрённые способы объединения разных методов. Например, всех трёх скептиков можно было объединить в один коллектив. Вы скажете, между ними мало родства? А много и не требуется. Достаточно того, что они мало верят в свои собственные методы. Можно отправить их на поиск низины общей группой из трёх человек, порешив, что на каждом шаге поиска будет действовать тот из них, на которого падёт жребий. Скажем, все трое будут тянуть из шапки свёрнутые бумажки, на одной из которых стоит крестик. И, представьте себе, в пользу такого образа действий есть свои доводы.

Эпилог

– Простите, что вы сказали? – переспросил Винер.

– Я говорю, вы, кажется, не слышите меня? Разве мой метод не разумен?

– Прошу прощения, быть может, ваш метод и хорош, хотя лично я поостерёгся бы называть его методом. Но меня отвлёк иной звук. Слышите?

– Нет... впрочем, да. Кажется, это журчание. Но почему здесь, а не в низине?

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

– Как видите, в нашем случае решить проблему отыскания воды было весьма просто, – сказал Винер, светя фонарём своему спутнику. – Достаточно было всем замолчать на минуту.