Пуассоновский поток и его свойства. Простейший (пуассоновский) поток и его свойства. Получение экспоненциально распределенной случайной величины из равномерно распределенной. Уравнения в частных производных. Разностные аппроксимации гиперболических уравнений первого порядка. Параболическое уравнение в частных производных. Условно и безусловно устойчивые схемы. Метод прогонки для нахождения решения по неявной схеме. Линейная и нелинейная регрессия. Метод наименьших квадратов. Оптимизационные модели. Условная оптимизация. Метод наикратчайшего градиентного спуска для безусловной оптимизации. Метод наикратчайшего градиентного спуска. Линейная оптимизация. Симплекс-метод. Принцип оптимальности Беллмана для решения задач дискретной оптимизации.

Лекционные заметки по курсу «моделирование». §1. Общее понятие о моделировании. Моделирование как способ познания. Абстрактная логика учит, что познание есть идеальное (смысловое) отображение реальности в сознании людей. Способы познания бывают, вообще говоря, различны: в частности, как достаточно убедительно показал К. Кастанеда, особенным способом познания обладают индейцы яки. Традиционная европейская теория познания подразделяет его на эмпиризм и логику (атеисты и агностики), а верующие веру в особый способ познания, причём можно говорить о том, что моделирование включает в себя и эмпиризм и логику, и при этом используются устройства, способные выполнять с высокой производительностью формальные логические операции и вычисления (ЭВМ). Само же моделирование есть такой способ познания, когда модель отображает определённым образом существенные свойства и поведение моделируемого объекта, в частности путём изучения закономерностей его поведения, и в определённых случаях его имитации (имитационное моделирование). §2. Виды моделей Модель может иметь внешнее сходство с объектом, либо не иметь его. Пример последнего ---рассмотрение системы из двух сцепленных маятников, конфигурационным пространством которой является тор, не имеющий никакого внешнего сходства с данным объектом. Идеальными моделями и являются идеальные жидкость или газ, не смотря на то, что они обнаруживают внешнее сходство с объектами, однако являются идеальными потому что, являются лишь идеальными конструкциями разума, не наблюдающимися в природе, хотя достаточно часто использующиеся в технике, как приближение (PV-диаграммы для тепловых машин, расчёт подъёмной силы крыла по формуле Жуковского и т.п.). В данном курсе мы будем рассматривать математические модели, которые будут подразделяться на аналитические и имитационные, причем те, в свою очередь будут подразделяться на, абстрактные и конкретные, стохастические (вероятностные), оптимизационные. §3. Принципы построения аналитических моделей. Имитационные модели. Как правило, аналитические модели строятся по следующему принципу: 1) Вывод основных уравнений 2) Выбор метода решения 3) Выбор вычислительного алгоритма и программирование 4) Получение результата и формулировка выводов Имитационные модели обычно строятся тогда, когда получение аналитических моделей является либо очень трудоёмким, либо невозможным. Среди данных моделей значительное место занимают модели теории массового обслуживания, причём, когда необходим подсчёт агрегатных (интегральных, суммарных) характеристик. z§4. Моделирование динамики популяций в биологии Ярким примером аналитической модели является модель Lotka-Volterra динамики численности популяций хищников и их жертв в замкнутой экосистеме (например, щук и карасей в большом озере). Статья, в которой упоминались обе фамилии, вышла на французском, поэтому иногда по-русски обе фамилии не склоняются, тем не менее, Лотка являлся поляком, а Вольтерра --- итальянцем, поэтому обе фамилии должны склоняться по первому склонению. Несмотря на достаточную приближенность и простоту модель и до сих пор вызывает споры касательно идеи коэволюции: дело в том, что из неё следует, что биосистема находится в равновесии, в случае если присутствуют все звенья трофической цепи. В книге Якова Перельмана «Живая математика» приводятся примеры быстрого размножения видов при отсутствии естественных биологических врагов: виды начинают размножаться по экспоненциальному закону, быстро уничтожая пропитание, что может в конечном итоге привести даже к и уничтожению самой популяции. Т.е., грубо говоря, не будет щук, караси сожрут все водоросли, не будет карасей --- озеро заболотится. У болгарского писателя фантаста Павела Вежинова был рассказ о том, как на одной планете всего лишь одному виду гусениц и бабочек удалось уничтожить все остальные конкурирующие виды, потому что у них развилась способность использовать электрические разряды; причём такая форма жизни не противоречит классическому дарвинизму, когда более совершенные формы сменяют менее совершенные, однако вступает в противоречие с идеей коэволюции. §5. Модель Лотки — Вольтерры. Перейдём теперь к самой модели. Пусть — количество карасей и в отсутствии хищных рыб они размножаются по экспоненте с коэффициентом , т.е. . Пусть — количество щук, и в отсутствии еды их естественная убыль пропорциональна с коэффициентом , т.е. . Далее, модель предполагает, что размножение щук, ровно как и убыль карасей пропорциональна произведению их количеств (фактически вероятности встречи) с коэффициентами и . Итого имеем систему 2-x дифференциальных уравнений первого порядка: А теперь выполним с системой трюк, который называется переходом к фазовому пространству. Вынося за скобки в первом уравнении и — во втором и, поделив уравнения друг на друга, получим уравнение уже первого порядка на пространстве . Данное уравнение оказывается уравнением с разделяющимися переменными, и мы находим его решение согласно стандартной процедуре Выходит, что фазовые кривые данной системы являются замкнутыми, что приводит к устойчивым периодическим колебаниям численности системы вокруг точки равновесия : Вблизи положения равновесия , если пренебречь членами более высоких порядков система сведётся к виду: Дифференцирование первого уравнения и подстановка в него второго даёт: что приводит к гармоническим колебаниям с периодом . §6. Моделирование движения в физике Другой пример моделей даёт движение в физике. В случае потенциального движения, оно описывается вторым законом Ньютона в форме: , где не зависит ни от , ни от . В таком случае, мы можем понизить порядок уравнения движения, помножив его на . , где . Т.е. получаем уравнение первого порядка: , в котором нетрудно усмотреть закон сохранения полной энергии для потенциальной системы: первый член являет собой кинетическую энергию, второй --- потенциальную, а правая часть --- полную энергию системы, которая остаётся постоянной. §6. Примеры Пример 1. Движение в постоянном поле тяготения (свободное падение, определение максимальной высоты и дальности броска) Уравнение движения в постоянном поле тяготения (если пренебречь сопротивлением воздуха) имеет вид: , где означает вертикальную координату, а --- ускорение свободного падения Проделаем вышеописанную процедуру с данным уравнением. Имеем аналогичным образом получаем закон сохранения энергии , где первый член означает потенциальную энергию, ---- потенциальную, а правая часть являет собой полную энергию (разумеется, с точностью до массы (которая сокращается). Уравнения для скорости и уравнения движения имеют вид: Задача. Тело брошено вверх с начальной скоростью . Какой максимальной высоты оно достигнет? Решение. В точке максимума вся кинетическая энергия переходит в потенциальную, поэтому в ней . Т.е. Ответ. Брошенное вверх с начальной скоростью тело достигнет максимальной высоты при . Пример 2. Движение при постоянном гравитационном поле в вертикальной плоскости. (Бросок на дальность). В данном случае уравнения движения принимают вид: Задача. Какова максимальная дальность броска при данной начальной скорости , и для какого угла она достигается? Решение. Поскольку уравнения для координат и y независимы, то и их решения также независимы , при этом (Считаем, что бросание происходит из начала координат), и являются компонентами начальной скорости соответственно, . В точке максимальной дальности броска . Тогда имеем Т.к. где обозначает угол по отношению к горизонтальному направлению, под которым производится бросок, имеем Максимальное значение равно 1, и достигается при , следовательно Ответ. Максимальная дальность броска равна и достигается для броска под углом . Пример 3. Движение в ньютоновском поле тяготения. Вторая космическая скорость. В гравитационном поле, подчиняющемуся закону обратных квадратов, уравнение для радиус-вектора движущегося тела, удаляющегося от гравитирующего тела строго по прямой, имеет вид: где обозначает радиус-вектор движущегося тела, а --- массу гравитирующего тела (напр. Земли). Будучи первообразной для силы, потенциал определён с точностью до константы. Поэтому можно положить потенциал на бесконечности равным 0. Тогда закон сохранения энергии примет вид На бесконечности и потенциальная и кинетическая энергия равны 0 по определению, тогда на поверхности Земли уравнение примет вид , где обозначает радиус Земли, — её массу и — ускорение свободного падения соответственно. Тогда скорость, необходимая для преодоления тяготения Земли будет равна , что примерно составляет 11 км/с. Пример 4. Гармонический осциллятор. Уравнение колебаний гармонического осциллятора имеет вид , Как и раньше, домножим его на и получим закон сохранения энергии. Или С целью упрощения вычислений рассмотрим случай . Имеем, В общем случае Пример 5. Затухающие колебания гармонического осциллятора. Уравнения для затухающих колебаний имеет вид . В данном случае домножение на не сработает в силу наличия члена, зависящего от . Однако, уравнение является линейным и его решение может быть найдено в виде . Запишем характеристическое уравнение: Рассмотрим случай . Тогда пусть . Решение уравнения движения принимает вид Колебания затухают по экспоненте с частотой . (С большим периодом колебаний , соответственно). Пример 6. Вынужденные колебания. Резонанс. Рассмотрим гармонический осциллятор, на который действует внешняя сила, с частотой колебаний, равной частоте осциллятора. В этом случае уравнение движения принимает вид Будем искать частное решение в виде Имеем Вынужденные колебания происходят с той же угловой частотой , но при этом амплитуда колебаний линейно возрастает несмотря на ограниченность силы . Добавление 1. Особые точки линейных систем на плоскости. §7. Ведение в численные методы. Возникающие в математических моделях уравнения решить аналитически удаётся далеко не всегда. Поэтому возникает необходимость использования численных методов. Для начала вспомним численные методы нахождения интегралов. Самыми простейшими методами численного нахождения интегралов являются методы прямоугольников и трапеций. Однако выбор значений на концах интервалов для формулы прямоугольников отнюдь не является оптимальным: в этом случае его точность оказывается существенно меньшей, чем для формулы трапеций. Однако, если на каждом шаге интегрирования выбирать значение функции по средине интервала, точной окажется сравнимой, а иногда даже большей, чем при использовании формулы трапеций. Объяснить это можно так: если через среднюю точку провести касательную, то значение функции умноженное на длину интервала даст площадь трапеции ограниченной касательной к функции в средней точке и вертикальными линиями, проходящими через границу интервала. Поскольку по теореме о линейном приближении касательная является наилучшим приближение для функции в окрестности точки касания, то приводит к тому, что погрешность данного метода оказывается достаточно невысокой — где является шагом интегрирования. §7.1 Метод Симпсона. Точность, большую чем метод средних прямоугольников или метод трапеций даёт метод Симпсона, основанный на приближении функций параболами на каждом шаге интегрирования. В общем положении через три точки можно провести только одну параболу для нахождения коэффициентов формулы Симпсона необходимо, чтобы квадратурная формула была точной для многочленов от степени 0 для степени 2 включительно. Для упрощения вычислений достаточно рассмотреть отрезок . Из условия точности для имеем: Приходим к системе Решая которую, находим, что Т.е., квадратурная формула принимает вид §7.2 Метод Монте-Карло Рассмотрим геометрическую интерпретацию интеграла как площади под кривой. Тогда вероятность попадания случайной точки равномерно распределённой в объемлющем прямоугольнике в область под кривой равна отношению площади данной области к площади объемлющего прямоугольника. Метод Монте-Карло состоит в оценке данной вероятности частотой попаданий случайно распределённой величины в область под кривой, которая сходится к вероятности при стремлении частоты испытаний к бесконечности в силу центральной предельной теоремы Муавра — Лапласа. Рассмотрим дискретную случайную величину Посчитаем её математическое ожидание и дисперсию Число попаданий в область под кривой равно Вероятность того, что число попаданий равно распределена биномиально Частота попаданий стремится к вероятности p и в силу центральной предельной теоремы Муавра — Лапласа где означает среднеквадратическое отклонение величины . Введём обозначения и Несмотря на то, что интеграл в правой части не берётся в элементарных функциях, он легко может быть вычислен путём почленного интегрирования ряда Тейлора для подынтегрального выражения. Пусть теперь . Тогда вероятность попадания частоты f в интервал будет равна Зададимся величиной интеграла находилось с точностью до с вероятностью . Тогда Или Т.е. при заданном имеем относительно низкую скорость сходимости пропорциональную корню из числа испытаний. Это значительно ниже, чем для точных методов однако метод Монте — Карло может быть использован либо в случае плохих функций (пример ), либо в случае кратных интегралов с очень сложными условиями, когда точные методы трудноприменимы. §8. Метод Рунге—Кутта 2-го порядка для решения дифференциальных уравнений. Для решения обыкновенных дифференциальных уравнений наиболее часто применяются методы Рунге—Кутта разных порядков (обычно, 3-го и 4-го порядков). Здесь мы рассмотрим получение метода Рунге—Кутта 2-го порядка. Возьмём уравнение Используя формулу Ньютона—Лейбница, распишем Аппроксимируем второе слагаемое в правой части с помощью формулы прямоугольников Heсмотря на то, что второй аргумент по прежнему остаётся неизвестным, его можно заменить аппроксимацией с точностью до : Тогда имеем В качестве , можно взять, например, В результате получим искомые формулы для метода Рунге—Кутта 2-го порядка Приведём без доказательства формулы методов Рунге—Кутта 3-го и 4-го порядков: §9. Элементы теории массового обслуживания. Распределение Пуассона. Пуассоновский поток и его свойства. Достаточно часто имитационные модели возникают в теории массового обслуживания, в которой важную роль играет пуассоновский поток и распределение Пуассона. Поэтому, чтобы приступить к данной теме, следуют начать с рассмотрения распределения Пуассона и теоремы Пуассона. Рассмотрим схему Бернулли для однородной последовательности независимых испытаний: Вероятность появления единиц в n испытаниях задаётся биномиальным распределением: Теорема Пуассона. Пусть в схеме Бернулли при , таким образом, что . Тогда . Доказательство. При больших имеем При фиксированном дробь в правой части полученного выражения стремится к 1 при , поэтому всё выражение стремится к , что и требовалось доказать. §9.1. Простейший (пуассоновский) поток и его свойства. В теории массового обслуживания часто возникает рассмотрение потока событий, такого что вероятность наступления следующего события независима от времени наступления предыдущего. Такой поток называется простейшим или пуассоновским. Формальное определение даётся в терминах трёх нижеследующих свойств. Пусть вероятность наступления В отношении процесса сделаем нижеследующие предположения: 1) стационареность, т.е. зависит только от и от и не зависит от начала временного интервала; 2) отсутствие последействия, т.е. отсутствует влияние прошлого на наступление будущих событий 3) ординарность, т.е. вероятность наступления более чем 2-х событий за малый промежуток времени равна =o. Лемма 1. При малых Доказательство. При любом целом Пусть t — неотрицательное число. Тогда Т.к. является убывающей функцией времени, она удовлетворяет неравенствам Пусть и , т.ч. =t. Тогда Положим , тогда существует , такое что и . Тогда При малых Лемма доказана. Далее, по формуле полной вероятности Устремим к нулю. Положим Тогда Далее, В силу леммы имеем Устремим к нулю. Получим систему: Сделаем замену Получим систему Решая которую, находим что Из чего получаем искомую формулу для вероятности наступления событий за время t: Найдём плотность распределения вероятности для времени между наступлением соседних событий. Она должна удовлетворять функциональному уравнению: Решением данного уравнения является экспоненциальная функция Поскольку интеграл от плотности вероятности равен 1, находим что . Т.е. получаем экспоненциальное распределение с параметром : Матожидание экспоненциального распределения равно , что может быть интерпретировано как среднее время между наступлением соседних событий. §9.2. Получение экспоненциально распределённой случайной величины из равномерно распределённой. Для того, чтобы сгенерировать пуассоновский поток событий пользуясь стандартным датчиком псевдослучайных чисел, дающим равномерно распределённую случайную величину, нам следует научиться получать экспоненциально распределённую случайную величину из равномерно распределённой. Для этого нам потребуется следующая лемма Лемма. Пусть случайная величина имеет плотность распределения . Пусть — монотонно возрастающая гладкая функция и . Тогда Доказательство. Рассмотрим интегральные функции распределения и Пусть . Тогда Теперь пусть равномерно распределена на , а экспоненциально распределена на , и пусть . Тогда Т.к. . Поэтому получаем Заметим, что поскольку является равномерно распределённой на , то . также находится внутри данного интервала, поэтому логарифм корректно определён и отрицателен. При делении на получается положительное число в интервале , §10. Уравнения в частных производных. Разностные аппроксимации гиперболических уравнений первого порядка. Численное решение уравнений в частных производных представляет собой существенно более сложный процесс, чем решение обыкновенных дифференциальных уравнений. В частности, как мы увидим на примере гиперболических уравнений первого порядка конечно разностная аппроксимация является устойчивой далеко не всегда, а только при определённом соотношении между шагами сетки. Рассмотрим уравнение переноса Аппроксимация где и обозначают шаги по переменным и соответственно, принимает вид: Оказывается, что данная аппроксимация является устойчивой, только если выполнен спектральный признак устойчивости. Рассмотрим решения в виде Если при заданном законе стремления шагов и к нулю, существует , такое что , то схема устойчива и может быть использована для решения дифференциального уравнения, в противном случае — нет: численное решение начнёт неограниченно возрастать по модулю. Подставим выражение для решения в разностное уравнение. Получим Для выполнения спектрального признака устойчивости главную роль играет отношение : 1) при пробегает окружность в пределах единичного круга 2) при пробегает единичную окружность 3) при пробегает окружность объемлющую единичный круг. 4) при пробегает окружность вне единичного круга Поэтому схема устойчива только в случае . в противном случает схема является неустойчивой и не может быть применена. §10.1 Параболическое уравнение в частных производных. Условно и безусловно устойчивые схемы. Метод прогонки для нахождения решения по неявной схеме. Рассмотрим смешанную задачу для уравнения теплопроводности Используем следующие разностные аппроксимации для уравнений в частных производных: Для решения смешанной задачи для уравнения теплопроводности можно предложить две разностные схемы: преимущество первой схемы состоит в том, что вычисляется по явной формуле, однако как и в случае гиперболических уравнений, она является лишь условно устойчивой: для её устойчивости необходимо выполнение условия . Для второй схемы явная формула для вычисления не может быть применена, однако её серьёзное преимущество состоит в том, что она является безусловно устойчивой, т.е. может быть применена при любых значения и . Для нахождения решения по неявной схеме может быть использован метод прогонки, так же как и в случае решения краевых задача для обыкновенных дифференциальных уравнений второго порядка. Напомним его суть. Пусть дана разностная аппроксимация краевой задачи для уравнения второго порядка Метод прогонки состоит в нахождении решения в виде (обратный ход), где коэффициент и вычисляются по формулам: (прямой ход) Cначала выполняется прямой ход, а потом для нахождения самого решения выполняется обратный ход. В нашем случае аппроксимация принимает вид: Положим . Выполним прямой ход метода прогонки И потом обратный ход метода прогонки для получения решения задачи §10.2 Линейная и нелинейная регрессия. Метод наименьших квадратов Очень часто для нахождения тренда в экономике или регрессии в физике используется метод наименьших квадратов. Его применение основывается на предположении о том, что либо отклонение от тренда, либо ошибка измерения распределена нормально и на факте, что сумма нормально распределённых случайных величин тоже является нормально распределённой случайной величиной со среднеквадратическим отклонением равным квадратному корню из суммы квадратов среднеквадратических отклонений слагаемых. Метод применим как и для линейной, так и для нелинейной регрессий, главное, чтобы линейным являлось вхождение коэффициентов. По существу метод наименьших квадратов означает нахождение такой регрессии или тренда, которое обеспечивает минимальное общее среднеквадратичное отклонение. Пример 1. Рассмотрим пример построения линейной регрессии в виде для набора данных: 1 4 7 11 15 17 22 3 6 10 14 18 24 30 Необходимо минимизировать среднеквадратическое отклонение Для этого найдём частные производные по и и приравняем их к нулю. Получим систему: Приводя подобные слагаемые, получим Для нахождения коэффициентов системы составим таблицу: № 1 1 3 1 3 2 4 6 16 24 3 7 10 49 70 4 11 14 121 154 5 15 18 225 270 6 17 24 289 408 7 22 30 484 660 77 105 1185 1589 Итого получаем систему Решая которую, находим, что и . Итого, имеем уравнение регрессии Также метод наименьших квадратов может быть применён для нахождения нелинейной регрессии Пример 2. Рассмотрим построение регрессии в виде для данных, заданных таблицей: Как и в предыдущем примере необходимо минимизировать сумму Аналогичным образом составим систему уравнений, приравняв частные производные по и к нулю: Приводя подобные слагаемые, получим: Как и в предыдущем примере составим таблицу: № 1 1 14 1 14 1 2 3 11 0.33 3.67 0.11 3 4 11 0.25 2.75 0.062 4 6 9 0.67 1.5 0.028 5 7 8 0.14 1.14 0.020 6 9 7 0.11 0.78 0.012 7 10 5 0.10 0.50 0.01 40 65 2.60 24.34 1.242 Получаем систему решая которую, находим, что и . Итого имеем . §11 Оптимизационные модели. Условная оптимизация. Метод наикратчайшего градиентного спуска для безусловной оптимизации. Приступая к рассмотрению темы достаточно обширной темы оптимизационных моделей, хотелось бы начать с рассмотрения простейших задач условной оптимизации. Пусть дана целевая функция , где вектор означает набор переменных , которую необходимо оптимизировать при выполнении условий . Для решения данной задачи введём дополнительные переменные и новую целевую функцию . Тогда задача условной оптимизации сведётся к нахождению стационарных точек новой целевой функции . Пример 1. Пусть целевая функция равна и задано одно условие -1=0. Тогда новая целевая функция будет равна . Найдём её частные производные по , по и по : Получим систему Из второго уравнения следует, что либо , либо (возможно, вместе) равно 0. Однако равенство 0 переменной вступает в противоречие с первым уравнением, поэтому . Тогда из третьего уравнения находим, что , т.е надо рассмотреть две критические точки (-1, 0) и (1, 0). Первая точка является точкой минимума целевой функции, а вторая — точкой максимума соответственно. §11.1 Метод наикратчайшего градиентного спуска. Наиболее распространённым методом решения задач безусловной оптимизации является метод наикратчайшего градиентного спуска. Напомню, что градиентом называется вектор, составленный из частных производных В анализе функций от нескольких переменных в теореме о конечном приращении градиент играет ту же роль, что и производная в анализе функций одной переменной: Поэтому вектор градиента перпендикулярен линиям уровня и указывает направление максимального локального роста функции. Соответственно, противоположное направление указывает на максимальное убывание функции. Поэтому для нахождения локального максимума следует двигаться в направлении градиента функции, а для нахождения локального минимума — в противоположном направлении. §12. Линейная оптимизация. Симплекс–метод. Для решения задач линейной оптимизации, т.е. когда и целевая функция и условия являются линейными, используется несколько иная стратегия. Множеством точек, удовлетворяющим линейному неравенству, является полуплоскость или полупространство (или для больших размерностей полугиперпространтство). Пресечением нескольких полуплоскостей является выпуклый многоугольник, соответственно пересечением полупространств является выпуклый многогранник (в больших размерностях также возникает выпуклое множество). Экстремальное значение целевой функции достигается в одной из вершин выпуклого множества, или, в вырожденном случае на одном ребре или одной грани целиком. В двумерном случае задачу с небольшим количеством ограничений нетрудно решить графически, построив выпуклый многоугольник и перебрав все его вершины. Однако при росте количества измерений количество потенциальных вершин начинает резко расти поэтому необходимо использование симплекс–метода. Алгоритм данного метода основывается на построении симплекс–таблиц и перехода к от вершины к вершине, для которой значение целевой функции оказывается по крайней мере не хуже, чем для предыдущей. Проиллюстрируем работу алгоритма на следующих примерах. Пример 1. Рассмотрим следующую задачу линейной оптимизации: Для начала приведём задачу к каноническому виду, так чтобы все ограничения имели форму равенств, введя дополнительные переменные : Построим первую симплекс–таблицу, взяв дополнительные переменные в качестве базисных: Базис Свободный член Оценочное отношение 18 1 3 1 16 2 1 1 16 5 1 1 5 21 3 1 -2 -3 Столбец «базис» заполняем выбранными базисными переменными, столбец свободный член заполняем свободными членами условий, остальные столбцы заполняем коэффициентами из условий, и последнюю строчку заполняем коэффициентами целевой функции, взятыми с обратным знаком. Для выполнения шага алгоритма симплекс–метода сначала необходимо найти разрешающий элемент, для чего необходимо найти разрешающий столбец и разрешающую строку. Разрешающий элемент будет находиться на пересечении разрешающего столбца и разрешающей строки. Разрешающий столбец находим следующим образом. Если все элементы нижней строки являются положительными, то условие оптимальности выполнено и решение найдено. В противном случае в последней строке находим максимальный по молю отрицательный элемент — там и будет находиться разрешающий столбец. Для нашей таблицы он буде находиться там, где находится переменная . Для нахождения разрешающей строки заполним последний столбец симплекс–таблицы оценочным отношением, согласно следующему правилу. Разрешающее отношение равно: 1) , если а) и имеют разные знаки, б) и , в) ; 2) 0, если и ; 3) , если и имеют одинаковые знаки Выберем строчку, где разрешающее отношение является минимальным. В нашем случае это строка, где находится переменная . Таким образом, найден разрешающий элемент, который выделен жирным шрифтом и подчёркиванием. Выполним шаг алгоритма симплекс метода и перейдём к следующей таблице. Для этого перенесём переменную из разрешающего столбца в разряд базисных. В данном случае это будет . Заполняется новая таблица следующим образом: а) на место разрешающего элемента ставим единицу. б) столбцы, соответствующие базисным переменным заполняем нулями и единицами следующим образом: единица ставиться в строке, где находиться та же переменная, что и в соответствующем столбце, во всех остальных строчках ставим нули. в) элементы разрешающей строки делим на разрешающий элемент. г) во всех остальных случаях пользуемся правилом прямоугольника где означает разрешающий элемент, находящийся в строке с номером и столбце с номером . В результате получим следующую таблицу: Базис Свободный член Оценочное отношение 3 1 1 -3 3 11 2 1 -1 11/2=5.5 5 1 1 21 3 1 21/3=7 15 -2 3 Мы видим, что в последней строке присутствуют отрицательные элементы, поэтому критерий оптимальности не выполнен. Поэтому необходимо повторить шаг алгоритма, найдя разрешающий столбец (в данном случае это будет первый), вычислив оценочное отношение и найдя его минимум (в данном случае это будет 3 в первой строке), и, получив разрешающий элемент (выделен жирным шрифтом и подчёркиванием) переходим к новой таблице вышеуказанным правилам: Базис Свободный член Оценочное отношение 3 1 1 -3 5 -2 1 5 5/5=1 5 1 1 12 -3 9 1 12/9= 21 2 -3 Мы видим, что в последней строке присутствует отрицательный элемент, поэтому необходимо выполнить ещё один шаг алгоритма. Как и раньше, найденный разрешающий элемент выделен жирным шрифтом и подчёркиванием. Приходим к следующей таблице: Базис Свободный член 6 1 -0.2 0.6 1 -0.4 0.2 1 4 1 0.4 -0.2 3 0.6 -1.8 1 24 0.8 0.6 Как мы видим, в последней строке отрицательных элементов нет, поэтому критерий оптимальности выполнен. Искомое решение находиться в столбце свободных членов, остальные переменные равны нулю. Максимум, равный 24 достигается в точке (6,4). Пример 2. Рассмотрим следующую систему: Как и в предыдущем примере, сначала приведём систему к каноническому виду, так чтобы все ограничения имели вид равенств: Составим первую таблицу для системы: Базис Свободный член Оценочное отношение 300 1 3 1 100 150 1 1 1 150 -2 -3 В последней строке присутствуют отрицательные элементы, поэтому как и раньше найдём разрешающий столбец, разрешающие отношения и разрешающую строку. Разрешающий элемент будет находится на их пересечении (выделен жирным шрифтом и подчёркиванием). Выполним шаг алгоритма и получим следующую таблицу: Базис Свободный член Оценочное отношение 100 1/3 1 1/3 300 50 2/3 -1/3 1 75 300 -1 1 В нижней строке присутствует отрицательный элемент, поэтому необходимо выполнить ещё один шаг алгоритма (разрешающий элемент выделен жирным шрифтом иподчёркиванием) Базис Свободный член 75 1 1 -0.5 75 1 -0.5 1.5 375 0.5 1.5 В последней строке отсутствуют отрицательные элементы, поэтому критерий оптимальности выполнен. Максимум, равный 375 достигается в точке (75, 75). §12. Принцип оптимальности Беллмана для решения задач дискретной оптимизации. На практике достаточно часто возникают задачи, в которых управляемую систему необходимо перевести из начальной точки в конечную, подбирая управление таким образом, чтобы достичь экстремума целевой функции. В нижеследующем параграфе мы рассмотрим задачи дискретного оптимального управления, для решения которых будем использовать принцип Беллмана. Пусть дана управляемая система , которую нужно привести из состояния в состояние , выбирая на каждом шаге управление из множества допустимых управлений , оптимизируя целевую функцию , причём переход из одного состояния в другое осуществляется посредством уравнения состояния . В отношении задачи делаются нижеследующие предположения: 1) Дискретность. Задача оптимизации интерпретируется как шаговый процесс. 2) Аддитивность. Целевая функция являет собой сумму локальных функций на каждом шаге . 3) Отсутствие последействия или обратной связи. Это означает, что выбор управления на каждом шаге не оказывает воздействия на последующие или предыдущие шаги. Принцип Беллмана выбора оптимального управления состоит в том, чтобы выбирать управление на каждом шаге так, чтобы вместе с последующей траекторией, выбранная траектория была бы оптимальной для данного шага. Т.е. строится рекуррентный ряд функций начиная с конца: по следующему принципу. Рассмотрим последний шаг. На нём выбираем таким образом, чтобы Рассмотрим предпоследний шаг. Согласно принципу Беллмана: В силу уравнения состояния получаем Поэтому имеем Аналогичным образом на –том шаге Таким образом, получаем рекуррентные уравнения Беллмана для функций . Принцип Беллмана также означает, что любая часть оптимальной траектории является оптимальной на своём участке. Рассмотрим применение принципа Беллмана для решения задачи распределения инвестиций. Пример. Пусть 5 условных единиц материальных средств нужно разместить в четырёх предприятиях, прибыль которых в зависимости от инвестиций задаётся следующей таблицей 1 8 6 3 4 2 10 9 4 6 3 11 11 7 8 4 12 13 11 13 5 18 15 18 16 Следует максимизировать прибыль, которая задаётся формулой . Несмотря на то, что целевая функция является аддитивной, она не является линейной, поэтому применение методов линейной оптимизации не представляется возможным. Применим принцип Беллмана рассмотрев инвестирование как 4-шаговый процесс с уравнением состояния где означает остаток на том шаге, а — инвестиции в тое предприятие. При функция является монотонной, поэтому максимум достигается когда весь остаток является израсходованным, т.е. . Поэтому Далее имеем Функции , и могут быть найдены с помощью следующей таблицы. 1 1 0 + 4 = 4 4 0 + 4 = 4 6 1 0 + 6 = 6 8 1 1 3 + 0 = 3 6 + 0 = 0 8 + 0 = 8 2 2 0 + 6 = 6 7 1 0 + 7 = 7 10 1 0 + 10 =10 14 1 1 1 3 + 4 =7 6 + 4 = 10 8 + 6 = 14 2 4 + 0 = 4 9 + 0 = 0 10 + 0 = 10 3 3 0 + 8 = 8 9 1 0 + 9 = 9 13 1 2 0 + 13 =13 18 1 1 2 3 + 6 = 9 6 + 7 = 13 8 + 10 =18 2 1 4 + 4 = 8 9 + 4 = 13 10 + 16 =16 3 7 + 0 = 7 11 + 0 = 0 11 + 0 =11 4 4 0 + 13 =13 13 0 + 13 = 13 16 2 0 + 16 =16 21 1 1 3 3 + 8 =11 6 + 9 = 15 8 +13 = 21 2 2 4 + 6 = 10 9 + 7 = 16 10 + 10 = 20 3 1 7 + 4 = 11 11 + 4 = 15 11 + 6 = 17 4 11 + 0 =11 13 + 0 = 0 12 + 0 = 12 5 5 0 + 16 = 16 18 5 0 + 18 = 18 19 1 0 + 19 = 19 24 1 1 4 3 +13 = 16 6 + 13 = 19 8 +16 = 24 2 3 4 + 8 = 12 9 + 9 = 18 10 +13 = 23 3 2 7 + 6 =13 11 + 7 =18 11 + 10 = 21 4 1 11 + 4 =15 13 + 4 = 17 12 + 6=18 5 18 + 0 =18 15 + 0 = 15 18 + 0=18 Из таблицы также находим максимальную прибыль, равную 24 единицы, и оптимальное распределение инвестиций: <конец слайда> К сожалению, уравнения оказываются точно решаемыми далеко не всегда. Поэтому иногда приходится применять ЭВМ и различные численные методы, причём данный предмет представляет собой отдельную науку