Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Контрольная работа - Классы задач линейного, нелинейного и стохастического программирования. Вариант 3 - файл 1.doc


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

Доступные файлы (1):

1.doc206kb.08.12.2011 17:45скачать

содержание
Загрузка...

1.doc

Реклама MarketGid:
Загрузка...
МФ НОУ ВПО

«Санкт-Петербургский Гуманитарный университет Профсоюзов»

Контрольная работа
По дисциплине: «Методы оптимизации в экономике»

Тема: «Классы задач линейного, нелинейного и стохастического программирования»

Выполнил:
Проверила:


Мурманск

2010 г.

СОДЕРЖАНИЕ


ВВЕДЕНИЕ 3

1. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ 4

2. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ 9

ЗАКЛЮЧЕНИЕ 15

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 16


ВВЕДЕНИЕ



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

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

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

В контрольной работе необходимо решить следующие задачи:

  • рассмотреть ключевые понятия линейного, нелинейного и стохастического программирования;

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


^

1. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ



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

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

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

Метод «затраты-эффективность» также укладывается в схему нелинейного программирования.

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

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

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

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

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

.

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

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

В этом смысле шаговые методы поиска оптимума называются итеративными.

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

Некоторые методы организуются как комбинированные алгоритмы, использующие достоинства методов различных классов. Кроме того различают методы одномерной оптимизации ( – скаляр) и многомерной оптимизации ( – вектор).

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

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

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

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

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

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

,

где , – точки, расположенные на прямой .

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

Рассмотрим расчёт в пространстве двух переменных.

Из прямоугольного треугольника АВС можно записать , , . Таким образом, величины и есть не что иное, как направляющие косинусы выбранного направления по отношению к осям координат. Следовательно, можно переписать следующим образом: .

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

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

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

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

^

2. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ



Линейное программирование включает в себя ряд шагов:

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

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

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

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

Основная процедура является общей для формулирования всех задач линейного программирования [4]:

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

Шаг 2. Определение цели и ограничений на ресурсы.

Шаг 3. Описание цели через переменные задачи.

Шаг 4. Описание ограничений через переменные задачи.

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

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

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

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

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

Примерами типовых задач, решаемых при помощи методов линейного программирования, могут быть [1]:

  • задача об оптимальном использовании ресурсов при производственном планировании;

  • задача о смесях (планирование состава продукции);

  • транспортная задача.

Таким образом, линейное программирование является подходящим методом для моделирования распределения ресурсов, если цель и ограничения на ресурсы можно выразить количественно в форме линейных взаимосвязей между переменными.
^ 3. СТОХАСТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
В то время как детерминированные задачи оптимизации формулируются с использованием заданных параметров, реальные прикладные задачи обычно содержат некоторые неизвестные параметры. Когда параметры известны только в пределах определенных границ, один подход к решению таких проблем называется робастной оптимизацией. Этот подход состоит в том, чтобы найти решение, которое является допустимым для всех таких данных и в некотором смысле оптимально.

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

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

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

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

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

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

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

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

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


ЗАКЛЮЧЕНИЕ



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

Основными этапами математического моделирования являются:

  1. Построение модели. На этом этапе задается некоторый «нематематический» объект – явление природы, конструкция, экономический план, производственный процесс и т. д. При этом, как правило, четкое описание ситуации затруднено. Сначала выявляются основные особенности явления и связи между ними на качественном уровне. Затем найденные качественные зависимости формулируются на языке математики, то есть строится математическая модель. Это самая трудная стадия моделирования.

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

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

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

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ





  1. Аксенова, Р. Н. Экономико-математические методы. Математические методы и модели в экономике. / Р. Н. Аксенова – Владивосток, ДВГАЭУ, 2007. – 118 с.

  2. Бодров, В. И. Математические методы принятия решений: Учеб. пособие./ В. И. Бодров Тамбов: Изд-во Тамб. гос. тех. ун-та, 2008. – 124 с.

  3. Кремер, Н. Ш. Высшая математика для экономистов: Учебник для ВУЗов / Н. Ш. Кремер – М.: ЮНИТИ, 2008. – 439 с.

  4. Ричард, Т. Количественные методы анализа хозяйственной деятельности. / М. Ричард – М.: Дело и сервис, 2009. – 139 с.

  5. Эддоус, М. Методы принятия решения. – М. Эддоус – М.: ЮНИТИ, 2007. – 278 с.



Скачать файл (205.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru