Введение в математическое программирование

Ю.В. Губарь






Введение в математическое программирование












^ИНТУИТ
  / НАЦИОНАЛЬНЫЙ ОТКРЫТЫЙ УНИВЕРСИТЕТ

С.ИНТУ ИТ

    У НАЦИОНАЛЬНЫЙ ОТКРЫТЫЙ УНИВЕРСИТЕТ


Введение в математическое программирование
2-е издание, исправленное
Губарь Ю.В.



Национальный Открытый Университет “ИНТУИТ”
2016


2

Введение в математическое программирование/ Ю.В. Губарь - М.: Национальный Открытый Университет “ИНТУИТ”, 2016
Курс рассматривает задачи математического моделирования, их признаки и свойства, а также целесообразность и область применения.
Вводятся понятия математического программирования, задач математического программирования. Рассматриваются такие разделы математического программирования как линейное и нелинейное программирование, формулируются виды задач линейного и нелинейного программирования, приводятся наиболее распространённые методы решения данных задач. В курсе рассмотрены вопросы, связанные с математическим моделированием, с формой и принципом представления математических моделей, особенностями её построения; в частности, предложены такие подходы, как фундаментальные законы природы, вариационные принципы, применение аналогий, иерархический подход; затронуты вопросы оснащённости и численной реализации математических моделей.
(c) ООО “ИНТУИТ.РУ”, 2007-2016
(c) Губарь Ю.В., 2007-2016

3

                Математическое моделирование. Математическая модель в задачах оптимизации. Элементарные математические модели




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

Невозможно представить себе современную науку без широкого применения математического моделирования. Сущность этой методологии состоит в замене исходного объекта его “образом” — математической моделью — и дальнейшем изучении модели с помощью реализуемых на компьютерах вычислительно-логических алгоритмов. Этот “третий метод” познания, конструирования, проектирования сочетает в себе многие достоинства как теории, так и эксперимента. Работа не с самим объектом (явлением, процессом), а с его моделью дает возможность безболезненно, относительно быстро и без существенных затрат исследовать его свойства и поведение в любых мыслимых ситуациях (преимущества теории). В то же время вычислительные (компьютерные, симуляционные, имитационные) эксперименты с моделями объектов позволяют, опираясь на мощь современных вычислительных методов и технических инструментов информатики, подробно и глубоко изучать объекты в достаточной полноте, недоступной чисто теоретическим подходам (преимущества эксперимента). Неудивительно, что методология математического моделирования бурно развивается, охватывая все новые сферы - от разработки технических систем и управления ими до анализа сложнейших экономических и социальных процессов.

Элементы математического моделирования использовались с самого начала появления точных наук, и не случайно, что некоторые методы вычислений носят имена таких корифеев науки, как Ньютон и Эйлер, а слово “алгоритм” происходит от имени средневекового арабского ученого Аль-Хорезми. Второе “рождение” этой методологии пришлось на конец 40-х—начало 50-х годов XX века и было обусловлено по крайней мере двумя причинами. Первая из них — появление ЭВМ (компьютеров), хотя и скромных по нынешним меркам, но тем не менее избавивших ученых от огромной по объему рутинной вычислительной работы. Вторая - беспрецедентный социальный заказ — выполнение национальных программ СССР и США по созданию ракетноядерного щита, которые не могли быть реализованы традиционными методами.
Математическое моделирование справилось с этой задачей: ядерные взрывы и полеты ракет и спутников были предварительно “осуществлены” в недрах ЭВМ с помощью математических моделей и лишь затем претворены на практике. Этот успех во многом определил дальнейшие достижения методологии, без применения которой в развитых странах ни один крупномасштабный технологический, экологический или экономический проект теперь всерьез не рассматривается (сказанное справедливо и по


4

отношению к некоторым социально-политическим проектам).

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


На первом этапе выбирается (или строится) “эквивалент” объекта, отражающий в математической форме важнейшие его свойства - законы, которым он подчиняется, связи, присущие составляющим его частям, и т.д. Математическая модель (или ее фрагменты) исследуется теоретическими методами, что позволяет получить важные предварительные знания об объекте.


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

На третьем этапе создаются программы, “переводящие” модель и алгоритм на доступный компьютеру язык. К ним также предъявляются требования экономичности


5

и адаптивности. Их можно назвать “электронным” эквивалентом изучаемого объекта, уже пригодным для непосредственного испытания на “экспериментальной установке” — компьютере.

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

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

Рассматривая вопрос шире, напомним, что моделирование присутствует почти во всех видах творческой активности людей различных “специальностей” — исследователей и предпринимателей, политиков и военачальников. Привнесение в эти сферы точного знания помогает ограничить интуитивное умозрительное “моделирование”, расширяет поле приложений рациональных методов. Конечно же, математическое моделирование плодотворно лишь при выполнении хорошо известных профессиональных требований: четкая формулировка основных понятий и предположений, апостериорный анализ адекватности используемых моделей, гарантированная точность вычислительных алгоритмов и т.д. Если же говорить о моделировании систем с участием “человеческого фактора”, т.е. трудноформализуемых объектов, то к этим требованиям необходимо добавить аккуратное разграничение математических и житейских терминов (звучащих одинаково, но имеющих разный смысл), осторожное применение уже готового математического аппарата к изучению явлений и процессов (предпочтителен путь “от задачи к методу”, а не наоборот) и ряд других.

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

Элементарные математические модели

Рассмотрим некоторые подходы к построению простейших математических моделей,


6

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

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

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


Рис. 1.2.

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

Эти трансформации описываются цепочкой равенств

mu²           V²
    — (7И |- т) — — (if -I- m)gl(l — cosat).

Здесь mv²/2 — кинетическая энергия пули массы m, имеющей скорость v, M — масса груза, V — скорость системы “пуля—груз” сразу после столкновения, g — ускорение свободного падения, I — длина стержня, — угол наибольшего отклонения. Искомая скорость определяется формулой


(1)

7

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


Сходные рассуждения может применить и инженер для оценки времени tₖ сверления слоя металла толщины L лазером с мощностью W, излучение которого перпендикулярно поверхности материала (рис. 1.3).


Рис. 1.3. Начальная, промежуточная и конечная стадии сверления металла лазером

Если энергия лазера полностью идет на испарение столбика металла массы /. > • ( S — облучаемая площадь, ls — объем столбика, — плотность вещества), то закон сохранения энергии выражается равенством

      Г,;.:       (2)


где h — энергия, требуемая для испарения единицы массы. Величина h имеет составную структуру: h=(T™-T)h1+h₂+h₃, поскольку материал необходимо последовательно нагреть до температуры плавления Тпл, а затем расплавить и превратить в пар ( T — исходная температура, h₁ - удельная теплоемкость, h2 и h3, — соответственно удельная теплота плавления и парообразования).Изменение глубины выемки l(t) со временем определяется из детального баланса энергии в промежутке времени от t до t+dt. На испаренную за это время массу

[Z(t + dt) -l(t)\Sp = dlSp

тратится энергия ■ . -.■>.••, равная энергии i; . , сообщаемой веществу лазером:


8

dl hSp — W dt

откуда получается дифференциальное уравнение

dl _ И'
dt hSp

Его интегрирование (с учетом того, что начальная глубина выемки равна нулю) дает

(3)         ^(3)
      /•5;.      ⁽ )


где E(t) — вся энергия, выделенная лазером к моменту времени t. Следовательно, глубина выемки пропорциональна затраченной энергии (причем величина tₖ, когда l(tₖ)=L, совпадает с вычисленной по формуле (2)).


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

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


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


Рис. 1.4.

Под словом “небольшой” подразумевается упрощающее обстоятельство, а именно то, что все продукты распада, не испытывая столкновений с атомами вещества, беспрепятственно покидают область I. Другими словами, длина свободного пробега продуктов распада в первом веществе значительно больше характерных размеров


9

самого материала LI, Т.е.     .■. Слова “толстый слой” означают, что в согласии с
целями хранения продукты деления полностью поглощаются в области II. Это гарантируется при выполнении противоположного условия .,.    /..., где — длина
пробега продуктов распада во втором веществе, LII — его характерный размер.

Итак, все, что вылетает из области I, поглощается в области II, и суммарная масса обоих веществ со временем не меняется. Это и есть закон сохранения материи, примененный к данной ситуации. Если в начальный момент времени t=0 массы веществ были равны MI(0) и MII(0), то в любой момент времени справедлив баланс

         •/.•.,>1, (4;.:.     (4)

Одного уравнения(4), очевидно, недостаточно для определения текущих значений двух масс - MI(t) и MII(t). Для замыкания математической формулировки необходимо привлечь дополнительное соображение о характере распада. Оно гласит, что скорость распада (число атомов, распадающихся в единицу времени) пропорционально общему числу атомов радиоактивного вещества. За небольшое время dt между моментами t и t + dt всего распадется

Afr(t + dt) — Nj(t) = —ar7V/(i +   a > 0, 0 < £ < 1,

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




dt               ⁷

Учитывая, что ■ ■ .■ ■  ■ .■ ■, где — атомный вес вещества I, получаем


----—                 (5) dt


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

Уравнения (4), (5) вместе с условиями              , а также величинами ,
MI(0), MII(0) и составляют математическую модель рассматриваемого объекта.

Интегрируя (5), получаем, что масса делящегося материала убывает по экспоненциальному закону


     = ЛЛ(0)£-^


10