Математические модели

Классификация моделей

Основные понятия

Лекция № 6 Математическое моделирование

 

Слово «модель» (от латинского слова «modulus») означает меру, мерильный образец, норму. Под моделью понимается либо некий образ объекта, интересующего нас, либо прообраз некоторого объекта или системы объектов.

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

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

Применяемые в разных областях человеческой деятельности модели можно классифицировать по разным признакам:

- по характеру моделируемых объектов

- по сферам приложения

- по средствам моделирования.

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

Предназначение модели состоит в том, что она является инструментом обработки информации.

 

6. 3. Классификация решаемых экономических задач

По уровню информации о ситуации:

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

2.Стохастический уровень – уровень, при котором известно множество возможных вариантов условий и их вероятностное распределение.

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

По виду информации о ситуации :

1.Статический вид – информация о ситуации не меняется во времени и известна заранее.

2.Динамический вид – информация о ситуации зависит от времени, прошедшего от начала операции.

По виду критерия оптимальности :

1.Однокритериальные задачи.

2.Монокритериальные задачи.

По типу критерия оптимальности:

1.Линейные задачи.

2.Нелинейные задачи.

По типу области ограничения:

1.Выпуклая область.

2.Целочисленная область.

3.Булева область.

 

Линейное программирование Общая постановка задачи

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

Эта линейная функция называется целевой, а ограничения, которые математически записываются в виде уравнений или неравенств, называются системой ограничений.

Определение

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

Z(x)=C1X1+C2X2 + . . . +СJXJ + . . . +СnXn _ max(min)

при ограничениях:

где Xi — неизвестные;a ij , bj , Ci — заданные постоянные величины.

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

Математическая модель в более краткой записи имеет вид

Z(x) = ∑Ci Xi → max(min)

при ограничениях:

Определение Допустимым решением (планом) задачи линейного программирования называется вектор X = (х1, х2, ,...хn , ) , удовлетворяющий системе ограничений.

Множество допустимых решений образует область допустимых решений (ОДР).

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

Базисное допустимое решение

Является опорным решением, где r— ранг системы ограничений.

Виды математических моделей ЛП.

Математическая модель задачи ЛП может быть канонической и неканонической.

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

Если хотя бы одно ограничение является неравенством, то модель задачи ЛП является неканонической. Чтобы перейти от неканонической модели к канонической, необходимо в каждое неравенство ввести балансовую переменную хn+i .

Если знак неравенства <, то балансовая переменная вводится со знаком плюс, если знак неравенства >, то — минус. В целевую функцию балансовые переменные не вводятся.

Чтобы составить математическую модель задачи ЛП, необходимо:— ввести обозначения переменных;

— исходя из цели экономических исследований, составить целевую функцию;

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

Каждая задача линейного программирования, называемая прямой или исходной, тесно связана с другой задачей, ее называют двойственной.

Математические модели этих задач имеют следующий вид.

прямая задача: двойственная задача:

Эти задачи экономически могут быть сформулированы следующим образом.

Прямая задача: сколько и какой продукции хi(i-1, 2, … , n) надо произвести, чтобы при заданных стоимостях единицы продукции Сi, объемом имеющихся ресурсов bj (j=1,2,…, m) и нормах расхода ресурсов аij максимизировать выпуск продукции в стоимостном виде.

Двойственная задача: какова должна быть оценка единицы каждого ресурса yj (j=1, 2,…, m), чтобы при заданных bj, ci и аij минимизировать общую оценку затрат на все ресурсы.

Правила построения двойственной задачи по имеемой прямой задаче:

1.Если прямая задача решается на максимум, то двойственная задача решается на минимум; если прямая задача решается на минимум то двойственная на максимум;

2.В задаче на максимум ограничения неравенства имеют вид – ≤, а в задаче на минимум ;³–

3.Каждому ограничению прямой задачи соответствует переменная двойственной задачи, в другой модели ограничению двойственной задачи соответствует переменная прямой задачи;

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

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

6.Если на переменную прямой задачи наложено условие неотрицательности, то соответствующее ограничение двойственной задачи записывается как ограничение-неравенство, в противном случае – как ограничение равенство;

7.Если какое либо ограничение прямой задачи записано как равенство, то на соответствующую переменную двойственной задачи условие неотрицательности не налагается.

Пример:

Прямая задача: Двойственная задача:

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

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

Теоремы двойственности.

Первая теорема двойственности: Если одна из двойственных задач имеет оптимальное решение, то и другая задача имеет оптимальное решение, причем экстремальные значения целевых функций совпадают Z(X)=Z'(Y). Если одна из двойственных задач неразрешима вследствие неограниченности целевой функции на множестве допустимых решений, то система ограничений другой задачи противоречива.

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

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

Вторая теорема двойственности: Для того чтобы план Х* и Y* пары двойственных задач были оптимальными, необходимо и достаточно выполнение условий:

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

если < bj, то ;

если 0, то> .

Аналогично,

 

если > ;

 

если 0 то> .

Экономически это означает, что если по некоторому оптимальному плану X*= производства расход j-го ресурса меньше его запаса bj, то в оптимальном плане соответствующая двойственная оценка единицы этого ресурса равна нулю. Если же в некотором оптимальном плане оценок его j-й элемент больше нуля, то в оптимальном плане производства расход соответствующего ресурса равен его запасу. Отсюда следует вывод: двойственные оценки могут служить мерой дефицитности ресурсов. Дефицитный ресурс, т.е. полностью используемый по оптимальному плану производства, имеет положительную оценку, а избыточный ресурс, т.е. не используемый полностью имеет нулевую оценку.

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

В последнем выражении дифференциалы заменим приращениями. Тогда получим выражение:

,

если , тогда , Экономическое содержание третьей теоремы двойственности: двойственная оценка численно равна изменению целевой функции при изменении соответствующего ресурса на единицу. Двойственные оценки yj часто называются скрытыми теневыми или маргинальными оценками ресурсов.

 

Симплексный метод решения задач ЛП

Общая постановка задачи Симплексный метод – метод последовательного улучшения плана. Метод является универсальным, так как позволяет решить практически любую задачу линейного программирования. Математическая модель задачи приводится к каноническому (стандартному) виду. Заполняется опорная симплекс – таблица с использованием коэффициентов целевой функции и системы ограничений. Решается задача по алгоритму. Идея симплексного метода заключается в том, что начиная с некоторого исходного опорного решения осуществляется последовательно направленное перемещение по допустимым решениям к оптимальному. Значение целевой функции для задач на максимум не убывает. Так как число допустимых решений конечно, то через конечное число шагов получим оптимальное решение.

Алгоритм симплексного метода

1.Математическую модель задачи привести к каноническому (стандартному) виду.

2. Построить начальную симплекс-таблицу исходя из стандартного вида.

3. Найти разрешающий столбец. В строке коэффициентов ЦФ найти значение с самим маленьким отрицательным числом. Этот столбец и будет разрешающим.

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

5.Построить новую симплекс-таблицу-второй шаг.

При построении новой таблицы убрать из базиса строку с переменной разрешающей строки в предыдущей таблице. Ввести в базис строку с названием разрешающего столбца предыдущей таблицы.

Построение ведущей строки в новой таблице. Почленно поделить всю разрешающую строку на разрешающий элемент.

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

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

Прямая задача на минимум решается следующим образом:

- Написать математическую модель двойственной задачи в стандартном виде

- Решить двойственную модель симплекс - методом

- Записать ответ.

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

Для этого достаточно воспользоваться соответствием переменных прямой и двойственной задач в последней симплекс-таблице.

Х1 x2 … xn S1 S2 … Sm
S1 S2 … Sm y1 y2 … ym

 

Транспортная задача

Постановка задачи:

Однородный груз сосредоточен у m поставщиков в объемах а1, а2, …, аm.

Данный груз необходимо доставить n потребителям в объемах, b1, b2, … , bn.

Известен Сij (i= 1, 2, … , m; j=1, 2 ,…, n) – стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю.

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

 

bj аi b1 b2 … bn
А1 С11 С12 … С1n
А2 С21 С22 … С2n
… … … … …
аm Cm1 Cm2 ... Cmn

Переменными (неизвестным) транспортной задачи являются xij (i=1,2,…,m; j=1,2,…,n) – объемы перевозок от каждого i-го поставщика j-му потребителю. Эти переменные могут быть записаны в виде матрицы перевозок.

Математическая модель транспортной задачи

Математическая модель транспортной задачи в общем виде имеет вид:

Целевая функция задачи Z(X) выражает требование обеспечить минимум суммарных затрат на перевозку всех грузов. Вторая группа из уравнений ограничений записанных в общем виде, выражает требование, что запасы всех m, поставщиков вывозятся полностью, а также полностью должны удовлетворятся запросы всех n потребителей. Последнее неравенство является условием неотрицательности всех переменных.

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

такая задача называется сбалансированной, а её модель закрытой. Если же это равенство не выполняется, то задача называется несбалансированной (с неправильным балансом), а её модель – открытой.

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

Математическая модель двойственной задачи:

если целевая функция Z’ стремится к минимуму то в системе ограничении меняется знак: экономический смысл перемененных двойственной задачи:

Ui – условная оценка i-го поставщика (условная плата поставщика перевозчику);

Vj – условная оценка j-го потребителя (условная плата потребителя перевозчику).

Ui, Vj – называются потенциалами.

Определения:

1.Если задача открыта, то необходимо добавить фиктивного поставщика или потребителя с недостающим объемом поставки и нулевой стоимостью перевозки. Распределение поставки фиктивному потребителю (поставщику), идет в последнюю очередь.

2.Клетка в плане перевозок называется базисной (закрытой), если в нее ставится перевозка.

3.Количество базисных клеток определяется соотношением r=m+n-1. опорное решение не может иметь базисных клеток больше, чем r.

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

5.Если в задаче указана не только стоимость перевозки, но и стоимость производства товара, тогда необходимо сложить эти стоимости с учетом перевозки товара от i-го поставщика j-му потребителю. Кроме того, математическая модель составляется с учетом этой суммарной стоимости.

Алгоритм решения транспортных задач.

1.Составить опорный план, т.е. начальное приближение.

2.Составить математическую модель исходной прямой и математическую модель двойственной задач.

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

Метод наименьшего элемента.

1.Сбалансировать задачу (убедиться, что задача сбалансирована).

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

3.В выбранную клетку поставить максимально возможную грузоперевозку для потребителя от поставщика.

4.Проверить, остался ли нераспределенным груз у этого поставщика.

5.Если груз распределен не полностью, то применяем п.2 относительно строки этого поставщика. Продолжать до тех пор, пока груз этого поставщика будет полностью распределен.

Если груз поставщика распределен полностью, проверить, полностью ли удовлетворен объем потребителя.

Если потребитель полностью удовлетворен, то применить пункт 2 относительно оставшихся поставщиков и потребностей в таблице.

Если объем потребителя полностью не удовлетворен, тогда применяется пункт 2 относительно соответствующего столбца.

6.Проверить план на вырожденность. Количество базисных клеток должно быть равным r=m+n-1.

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

7.Проверить на оптимальность и по возможности дальше улучшить, перейдя к методу потенциалов.

Метод потенциалов.

1.Для всех базисных клеток создать систему уравнений вида .

Выбрать переменную Ui или Vj, которой соответствует наибольшее количество занятых клеток, приравнять её к нулю, решить систему уравнений относительно Ui и Vj и найти эти значения.

2.Для всех свободных клеток составить и проверить выполнение неравенств:

Условия оптимальности: если для всех свободных клеток выполняется это неравенство, то тогда найден оптимальный план.

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

3.Находим клетку, где сильнее всего не выполняется неравенство. Если таких клеток несколько, то выбирается любая. В эту клетку ставим W со знаком «+».

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

- В строке и столбце должно быть четное число W;

- Контур меняет направление только в базисных клетках;

- Коэффициент W меняет свой знак с «+» на «-» поочередно в углах контура.

5.После построения контура отметить, в каких базисных клетках коэффициент W стоит с отрицательным знаком. Из этих клеток найти клетку с наименьшим значением перевозки, коэффициент W будет равен перевозке в выбранной клетке.

6.Найти новый план, перераспределив найденное значение W по контуру с учетом знаков «+» и «-», прибавляя или уменьшая стоящую в клетке перевозку.

7.Проверить новый план в соответствии в п.2, если неравенства для свободных клеток выполняются, значит найденный план оптимален.

Если в математической модели целевая функция прямой задачи на максимум (Zmax), то задача решается методом максимального элемента. т.е. грузоперевозка (Xij) распределяется при составлении опорного плана с учетом наибольшего значения Cij аналогично алгоритма метода наименьшего элемента. В методе потенциалов проверяется выполнение неравенства .

 

Целочисленное программирование.

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

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

Задача целочисленного программирования формулируется следующим образом:

Найти такое решение план Х=(х1, х2,…, хn), при котором линейная функция принимает максимальное или минимальное значение при ограничениях.

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

Понятия о методе ветвей и границ.

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

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

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

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

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

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

Если же полученное оптимальное решение не целочисленное, то строится дополнительное линейное ограничение. Оно обладает следующими свойствами:

1.Оно должно быть линейным;

2.Должно отсекать найденный оптимальный не целочисленный план;

3.Не должно отсекать ни одного целочисленного плана.

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

1.Построить систему координат x10х2 и выбрать масштаб.

2.Найти область допустимых решений (ОДР) системы ограничений задачи.

3.Построить целевую функцию, являющуюся линией уровня и на ней указать направление нормали.

4.Переместить линию целевой функции по направлению нормали через ОДР, чтобы она из секущей стала касательной к ОДР и проходила через наиболее удаленную от начала координат точку. Эта точка будет являться точкой экстремума, т.е. решением задачи.

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

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

6.Выделить у этих координат область с целочисленными значениями.

7.Определить новые координаты и построить граф.

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

 

Динамическое программирование.

Постановка задачи.

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

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

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

Управление – совокупность решений, принимаемых на каждом этапе для влияния на ход развития процесса.

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

Решение на каждом шаге называется «шаговым управлением».

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

При распределении средств между предприятиями шагами целесообразно считать номер очередного предприятия; при распределении на несколько лет ресурсов деятельности предприятия – временной период. В других задачах разделение на шаги вводится искусственно.

Требуется найти такое управление (х), при котором выигрыш обращался бы в максимум:

F(x)=

Где F – выигрыш за операцию;

Fi(xi) – выигрыш на i-м шаге;

х – управление операцией в целом;

хi – управление на i-м шаге (i=1,2,…,m). В общем случае шаговые управления (х1, х2, … хm) могут стать числами, векторами, функциями.

То управление (х*), при котором достигается максимум, называется оптимальным управлением. Оптимальность управления состоит из совокупности оптимальных шаговых управлений х* = х*1, х*2, … х*m

F* = max {F*(х*)} – максимальный выигрыш, который достигается при оптимальном управлении х*.

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

Принцип оптимальности Беллмана

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

Суть принципа:

Каковы бы ни были начальное состояние на любом шаге и управление, выбранное на этом шаге, последующие управления должны выбираться ОПТИМАЛЬНЫМИ относительно состояния, к которому придет система в конце каждого шага.

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

Условная оптимизация

Безусловная оптимизация

Si – состояние системы на i-м шаге. Основная рекуррентная формула динамического программирования в случае решения задачи максимизации имеет вид:

, где максимум в данной формуле берется по всем возможным решениям в ситуации, когда система на шаге m находится в состоянии i.

Величина fm(i) – есть максимальная прибыль завершения задачи из состояния i, если предположить, что на шаге m, система находится в состоянии i.

Максимальная прибыль может быть получена максимизацией суммы прибылей самого шага m и максимальной прибыли шага (m+1) и далее, чтобы дойти до конца задачи.

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

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

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

Задача динамического программирования начинает решаться с конца, т.е. с последнего шага. Решается задача в 2 этапа:

1 этап (от конца к началу по шагам): Проводится условная оптимизация, в результате чего находится условные оптимальные управления и условные оптимальные выигрыши по всем шагам процесса.

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

 

Элементы теории игр

Основные понятия.

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

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

Игра называется антагонистической или игрой с нулевой суммой, если выигрыш одного из игроков равен проигрышу другого, поэтому для полного «задания» игры достаточно указать величину выигрыша первого игрока.

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

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

Такие стратегии называются оптимальными.

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

Матрица, элементы которой характеризуют выигрыш первого игрока (МЫ –игрок А) и проигрыш второго (игрок В) при их возможных стратегиях (обозначается |αij|), называется платежной матрицей игры.

Величина α = max min aij называется нижней ценой игры – j i гарантированный выигрыш игрока А при применении игроком В своих стратегий. Находится путем выбора минимального значения из aij в каждой строке платежной матрицы игры (получаем столбец) и из этих минимальных значений находится максимальное, которое и соответствует нижней цене игры α.

Величина β = min max aij называется верхней ценой игры –i j минимальный проигрыш игрока В при применении игроком А своих стратегий. Находится путем выбора максимального значения из aij по столбцам (получим строку) и из этих максимальных значений находится минимальное значение, которое и соответствует верхней цене игры β.

Выигрыш, соответствующий оптимальному решению, называется ценой игры γ. Цена игры удовлетворяет неравенству α ≤ γ ≥ β.Такие игры называются играми в смешанных стратегиях.

Если нижняя и верхняя цены игра совпадают, то их общее значение α = β = γ чистой ценой игры или седловой точкой. Такие игры называются играми в чистых стратегиях.

Минимаксные стратегии, соответствующие цене игры, являются оптимальными стратегиями, а их совокупность (АiВj) – оптимальным решением или решением игры.

Игра, в которой интересы игроков противоположны называется антагонистичной.

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

Человек в играх с «природой» старается действовать осмотрительно, второй игрок (природа и т.п.) действует случайно.

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

 

Системы массового обслуживания

Формулировка задачи и характеристики СМО

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

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

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

Основными элементами СМО являются источники заявок; их входящий поток; каналы обслуживания и выходящий поток. Это изображено на рис.

Входящий каналы выходящий поток очередь обслуживания поток

В зависимости от характера формирования очереди СМО различают:

1)системы с отказами, в которых при занятости всех каналов обслуживания заявка не встает в очередь и покидает систему необслуженной;

2)системы с неограниченными ожиданиями, в которых заявка встает в очередь, если в момент ее поступления все каналы были заняты.

3)системы смешанного типа с ожиданием и ограниченной длиной очереди: заявка получает отказ, если приходит в момент, когда все места в очереди заняты. Заявка, попавшая в очередь, обслуживается обязательно.

По числу каналов обслуживания СМО делятся на одноканальные и многоканальные.

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

Рассмотрим в отдельности элементы СМО.

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

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

Ординарность потока определяется невозможностью одновременного появления двух или более заявок.

Отсутствие последействия характеризуется тем, что поступление заявки не зависит от того, когда и сколько заявок поступило до этого момента. В этом случае вероятность того, что число заявок, поступивших на обслуживание за промежуток времени t, равно k, определяется по закону Пуассона.

Pk(t)=( (λt)k / k! ) е-λt

где λ – интенсивность потока заявок, т.е. среднее число заявок в единицу

времени: λ=1/τ (чел/мин, р/ч, автом/дн, кВт/ч), где τ – среднее значение интервала времени между двумя соседними заявками;

k – число заявок, поступивших на обслуживание за промежуток времени t. Для такого потока время между двумя соседними заявками распределено экспоненциально с плотностью вероятности: f(t)= λ е-λt

Случайное время ожидания в очереди начала обслуживания считают распределенным экспоненциально: f(t)=υе-υt

где υ – интенсивность движения очереди, т.е. среднее число заявок

приходящихся на обслуживание в единицу времени: υ=1/tоч,

где tоч – среднее значение времени ожидания в очереди.

Выходящий поток заявок связан с потоками обслуживания в канале, где

длительность обслуживания tобс является случайной величиной и часто подчиняется показательному закону распределения с плотностью

f(tобс)= μe-μt

где μ – интенсивность потока обслуживания, т.е. среднее число заявок, обслуживаемых в ед. времени: μ=1/ tобс(чел/мин, р/дн, кг/ч, докум/дн)

где t – среднее время обслуживания.

Важной характеристикой СМО, объединяющей λ и μ, является интенсивность нагрузки ρ=λ/ μ

Рассмотрим n-канальные разомкнутые СМО.

СМО с отказами

Основные понятия

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

9.2.2 Формулы для расчета установившегося режима

1. Вероятность простая каналов обслуживания, когда нет заявок (k=0):

P0=1/(Σ ρk / k!)

2. Вероятность отказа в обслуживании, когда поступившая на обслуживание заявка найдет все каналы занятыми (k=n):

Pотк= Pn =P0ρn / n

3. Вероятность обслуживания: Робс= 1- Pотк _

4. Среднее число занятых обслуживанием каналов: _ n3=ρ Робс

5. Доля каналов, занятых обслуживанием: k3= n3/n

6. Абсолютная пропускная способность СМО: A=λ Робс

СМО с неограниченным ожиданием

Основные понятия

Заявка, поступившая в систему с неограниченным ожиданием и нашедшая все каналы занятыми, становится в очередь, ожидая освобождения одного из каналов.

Основной характеристикой качества обслуживания является время ожидания (время пребывания заявки в очереди).

Для таких систем характерно отсутствие отказа в обслуживании, т.е.

Pотк=0 и Робс=1.

Для систем с ожиданием существует дисциплина очереди:

1)обслуживание в порядке очереди по принципу «первым пришел – первым обслужен»;

2)случайное неорганизованное обслуживание по принципу «последний пришел - первым обслужен»;

3)обслуживание с приоритетами по принципу «генералы и полковники вне очереди».

Формулы для расчета установившегося режима

1. Вероятность простоя каналов, когда нет заявок (k=0):

P0=1/Σ(ρк/к!)+ρn+1/n!(n-ρ)

Предполагается, что ρ/n<1, т.е. интенсивность нагрузки меньше числа каналов.

2. Вероятность занятости обслуживанием k заявок: Pk= ρк P0/k!, 1≤ k≤ n

3. Вероятность занятости обслуживанием всех каналов: Pn =P0ρn / n!

4. Вероятность того, что заявка ожидается в очереди: Роч= ρn+1/n!(n-ρ)* P0

5. Среднее число заявок в очереди: _

Lоч= ρn+1/(n+λ)!(n-ρ)2* P0

6. Среднее время ожидания заявки в очереди: _ _tоч= Lоч/λ

7. Среднее время ожидания заявки в СМО: _ _tсмо= tоч+ tобс

8. Среднее число занятых обслуживанием каналов: _n3=ρ

9. Среднее число свободных каналов: _ _nсв= n- n3 _

10. Коэффициент занятости каналов обслуживания: k3= n3/ n

11. Среднее число заявок в СМО: _ _ _z= Lоч+ n3

СМО с ожиданием и с ограниченной длиной очереди

Основные понятия

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

Основной характеристикой качества системы является отказ заявке в обслуживании.

Ограничения на длину очереди могут быть из-за:

1)ограничения сверх времени пребывания заявки в очереди;

2)ограничения сверх длины очереди;

3)ограничения общего времени пребывания заявки в системе.

Формулы для установившегося режима

1. Вероятность простоя каналов, когда нет заявок (k=0):

P0=1 : {Σ ρк/к!+ρn+1/n!(n-ρ)[1-(ρ/n)m]}

n – число каналов;

m – длина накопителя;

ρ – интенсивность нагрузки;

К – число заявок, поступивших на обслуживание за промежуток времени t.

2. Вероятность отказа в обслуживании: Pотк= ρn+m/n!n m*P0

3. Вероятность обслуживания: Робс= 1- Pотк

4. Абсолютная пропускная способность: A=λ Робс

5. Среднее число занятых каналов: _

n3=A/μ= λ Робс/μ=ρ Робс, где ρ=λ/ μ

6. Среднее число заявок в очереди:

Lоч= ρn+1/n*n! * 1-(ρ/n)m(m+1-mρ/n) / (1-ρ/n)2 * P0

7. Среднее время ожидания обслуживания: _ _tоч= Lоч/λ

8. Среднее число заявок в системе: z= Lоч+ n3

Среднее время пребывания в системе: tсмо= z/λ

 

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

Основные понятия.

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

Пример простой нелинейной задачи:

Предприятие для производства какого-то продукта расходует два средства в количестве х и y соответственно. Это факторы производства, например, машины и труд, два различных вида сырья и т.п., а х и y – затраты факторов производства.

Факторы производства считаются взаимозаменяемыми. Если это «труд» и «машины», то можно применять такие методы производства, при которых величина затрат в сопоставлении с величиной затрат труда оказывается больше или меньше (производство более или менее трудоемкое).

Объем производства, выраженный в натуральных или стоимостных единицах, является функцией затрат производства

Z = f (х, y). Эта зависимость называется производственной функцией.

Совокупные издержки выражаются формулой с1х1 + с2y2 = в.

Требуется при данных совокупных издержках определить количество факторов производства, которое максимизирует объем продукции Z.

Математическая модель задачи:

Определить такие переменные х и у, удовлетворяющие условиям

с1х1+с2у=в, х≥0, у≥0,

при которых функция z=f(х, у) достигнет максимума.

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

Понятие условного экстремума вводится для случая, когда число переменных n не меньше 2 (n≥2).

Разница между глобальным и локальным экстремумами предоставлена

на рисунке:

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