Решение управленческих задач с помощью методов матпрограммирования

 

Курский Государственный Университет

 

 

 

 

 
 

 
Реферат по дисциплине: 
Основы теории принятия решений  
На тему: 
«Решение управленческих задач  
с помощью методов матпрограммирования» 
 

 

                                               

 

 

                                                    

                                                     Преподаватель: Желанова Оксана Евгеньевна 
                                                         Выполнила: Студентка 1 курса, группы 15А 
                                                                   Мягких Маргарита Анатольевна  
 
 
 
                                                    2014

 

Содержание 
 
Введение………………………………………………………………. 
1. Математическое программирование, методы  математического программирования……………………………………………………. 
2. Линейное программирование……………………………………... 
3. Нелинейное программирование…………………………………... 
4. Стохастическое программирование………………………………. 
5. Динамическое программирование………………………………... 
Заключение …………………………………………………………....

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

 

 
 

 

 

 

 

 

 

 

 

 

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

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

 

Линейное программирование

Это один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование». 
Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ)» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда стали широко применяться составления программ при решении математических, инженерных, экономических и других задач.  
Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми.

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

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

 

 

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

· рационального использования сырья и материалов; задачи оптимизации раскроя;

· оптимизации производственной программы предприятий;

· оптимального размещения и концентрации производства;

· составления оптимального плана перевозок, работы транспорта;

· управления производственными запасами;

· и многие другие, принадлежащие сфере оптимального планирования.

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

Первые постановки задач линейного программирования были сформулированы известным советским математиком Л.В.Канторовичем, которому за эти работы была присуждена Нобелевская премия по экономике.

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

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

 

 

 

 

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

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

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

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

 

 

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

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

Разработанные ныне методы решения задач нелинейного программирования могут быть разделены на ряд больших групп:

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

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

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

 

 

 

 

 

 

Стохастическое программирование

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

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

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