Конспект лекций по дисциплине «Методы оптимальных решений»
Скачать 465.49 Kb.
|
| Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «ФИНАНСОВЫЙ УНИВЕРСИТЕТ ПРИ ПРАВИТЕЛЬСТВЕ РОССИЙСКОЙ ФЕДЕРАЦИИ» __________________________________________________________________ Тульский филиал Кафедра математики и информатики Конспект лекций по дисциплине «Методы оптимальных решений» для студентов, обучающимся по направлению 080100.62 «Экономика» Квалификация (степень) бакалавр Составил: к.ф.-м.н., доцент кафедры математики и информатики Луценко Алексей Георгиевич Рассмотрено и одобрено на заседании кафедры кафедры математики и информатики протокол № ___ от «___»____________ 2013 г. ^ Общее представление о задаче оптимизации 1. Математические методы и модели в экономике. Основные понятия и общая классификация. Иллюстрация на конкретных примерах Определение 1. Математическая модель в экономике или экономико-математическая модель (ЭММ) – математическое описание исследуемого экономического процесса. Эта модель выражает закономерности экономического процесса с помощью математических соотношений. Единой классификации ЭММ к настоящему времени не выработано. В общем виде ЭММ разделяют следующим образом:
По предназначению ЭММ различают следующим образом:
По математическому аппарату ЭММ различают следующим образом:
Определение 2. Математические методы в экономике или экономико-математические методы – это методы разработки, исследования и принятий решений по экономико-математическим моделям. Общепринятой классификации этих методов также не существует. Можно выделить следующие группы методов:
В процессе решения экономических задач с применением математических методов можно выделить следующие основные этапы:
^ Определение 1. Принцип оптимальности – выбор такого управленческого решения  , где  – его компоненты, которое наилучшим образом учитывает внутренние возможности и внешние условия производственной деятельности хозяйствующего субъекта.Математическая запись принципа оптимальности в общем случае имеет вид:  , где:^ – область возможных (допустимых) решений; f(X) – целевая функция. Критерий оптимальности должен быть выражен количественно и соответствовать общей цели деятельности рассматриваемой системы. Традиционные критерии оптимальности – «максимум прибыли», «минимум затрат» и т.д. ^ общая классификация. Примеры практических приложений Определение 1. Задача оптимального программирования имеет вид:
f(X) – целевая функция (ЦФ), зависящая от вектора X; Обозначение  говорит о том, что в каждом конкретном ограничении возможен один из этих знаков. Ограничения (3.1) называются функциональными ограничениями, а (3.2) – прямыми ограничениями.Более компактно:
Вектор X называется допустимым решением (допустимым планом задачи оптимального программирования), если его компоненты удовлетворяют системе ограничений (3.4) и (3.5).План  называется оптимальным планом задачи оптимального программирования, если  .Определение 2. Решить задачу оптимального программирования – это значит:
Задачи оптимального программирования классифицируют по следующим признакам:
^ Если в задаче оптимизации отсутствует условие неотрицательности переменных, а функциональные ограничения имеют вид равенств, то такую задачу называют классической задачей оптимизации:
Если все функции  ,  непрерывны вместе с частными производными первого порядка, то для решения задачи оптимизации можно применить классический метод множителей Лагранжа.Алгоритм: 1. Сначала составляют функцию Лагранжа:
2. Далее вычисляют для функции (4.3) частные производные первого порядка по всем переменным и  , приравнивают их нулю и получают систему уравнений:
3. Если удается найти все решения системы (4.4), то для определения глобального максимума или минимума достаточно найти значения функции в соответствующих точках области определения задачи и выбрать наибольшее или наименьшее значение функции. Замечание. Теоретической основой метода является следующее утверждение: если функция f(X) в точке  имеет экстремум, то существует вектор  такой, что точка  является решением системы уравнений (4.4).^ Задача об использовании ограниченных ресурсов. Задача о размещении производственных заказов. Задача о раскрое строительных материалов [1, с.30-31, 33-35]. ^ Задача об инвестициях [1, с.41-42, 45]. Задача о «ранце». Задача о «рационе». Задача о распределении рекламного бюджета. Тема 2: Линейное программирование ^ Наиболее изученными задачами оптимизации являются задачи линейного программирования (ЗЛП), для которых разработан универсальный метод решения – симплекс-метод (метод последовательного улучшения плана). Определение 1. Задача линейного программирования имеет вид:
Вектор называется допустимым решением (допустимым планом) ЗЛП, если его компоненты удовлетворяют системе ограничений (6.2) и (6.3).План называется оптимальным планом (оптимальным решением) ЗЛП, если , т.е. допустимый план, который дает максимум или минимум целевой функции.Определение 2. Канонической формой записи ЗЛП называется задача вида:
Любую ЗЛП можно привести к каноническому виду (КЗЛП). Чтобы неравенства обратились в равенства достаточно:
^ Для выработки наглядных представлений о ЗЛП рассмотрим графический метод, который может быть применен в случае решения ЗЛП с двумя переменными:
Геометрически ЗЛП представляет собой отыскание в многоугольнике решений такой угловой точки, координаты которой дают максимальное (минимальное) значение линейной целевой функции, причем допустимыми решениями являются все точки многоугольника решений. Алгоритм решения ЗЛП с двумя переменными графическим методом
^ Возможны следующие особые случаи:
^ Сначала кратко напомним некоторые математические понятия и факты. Теорема 1. Если функция непрерывна на замкнутом ограниченном множестве конечномерного евклидова пространства, то она ограничена на нем и достигает наименьшего и наибольшего значений. Определение 1. Любые m переменных системы m линейных уравнений с n переменными (m < n) называются основными, если определитель из коэффициентов при них отличен от нуля. Тогда остальные n-m переменных называются неосновными (свободными). Определение 2. Базисным решением системы m линейных уравнений с n переменными (m < n) называется всякое её решение, в котором неосновные переменные имеют нулевое значение. Определение 3. Решение системы m линейных уравнений с n переменными (m < n) называется допустимым, если в нём все основные переменные неотрицательны. Теорема. Существует взаимнооднозначное соответствие между угловыми точками множества допустимых решений системы m линейных уравнений с n переменными (m < n) и её допустимыми базисными решениями. Сначала необходимо ЗЛП привести к каноническому виду (КЗЛП). Доказано, что оптимальное решение ЗЛП (если оно существует и притом единственное) совпадает с одним из допустимых базисных решений системы ограничений, следовательно, с угловой точкой многогранника решений. Однако для реальных задач число допустимых базисных решений может быть очень велико и провести перебор всех угловых точек многогранника затруднительно. Этот перебор можно сократить, используя идею симплексного метода (метод предложен в 1949 г. американским ученым Дж. Данцигом). Для реализации симплекс-метода – метода последовательного улучшения плана – необходимо знать три основные операции:
Замечание. Если первоначальное базисное решение недопустимо, то удобно использовать симплекс-метод с искусственным базисом. ^ Рассмотрим основные понятия и выводы специального раздела линейного программирования — теории двойственности. С каждой задачей линейного программирования определенным образом тесно связана другая линейная задача, называемая двойственной. Первоначальная задача называется исходной или прямой. Связь исходной и двойственной задач заключается, в частности, в том, что решение одной из них может быть получено непосредственно из решения другой. Хорошо разработанный математический аппарат линейного программирования позволяет не только получать с помощью эффективных вычислительных процедур оптимальный план, но и делать ряд экономически содержательных выводов, основанных на свойствах задачи, двойственной к исходной ЗЛП. Каждая из задач двойственной пары фактически является самостоятельной задачей линейного программирования и может быть решена независимо от другой задачи. Однако при определении симплексным методом оптимального плана одной из задач находится решение и другой задачи. Правило построения двойственной задачи по отношению к исходной задаче определяется системой соотношений:
Двойственная задача составляется согласно следующим правилам: 1) целевая функция исходной задачи формулируется на максимум, а целевая функция двойственной задачи — на минимум, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид «», а в задаче на минимум — «». 2) матрица, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица в двойственной задаче получаются друг из друга транспонированием; 3) число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи; число ограничений двойственной задачи равно числу переменных в исходной задаче; 4) коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи, а правыми частями в ограничениях двойственной задачи — коэффициенты при неизвестных в целевой функции исходной задачи; 5) каждому ограничению одной задачи соответствует переменная другой задачи: номер переменной совпадает с номером ограничения; при этом ограничению, записанному в виде неравенства «», соответствует переменная, связанная условием неотрицательности. Основные утверждения о двойственных задачах содержатся в двух следующих теоремах Теорема 1 (основная теорема двойственности). Если одна из двойственных задач разрешима, то разрешима и другая, причем экстремальные значения целевых функций задач равны:  . ^ .Теорема 2 (о дополняющей нежесткости). Если при подстановке компонент оптимального плана в систему ограничений исходной задачи i-е ограничение обращается в неравенство, то i-я компонента оптимального плана двойственной задачи равна нулю. Если i-я компонента оптимального плана двойственной задачи положительна, то i-е ограничение исходной задачи удовлетворяется ее оптимальным решением как строгое равенство. То есть для оптимальных планов двойственных задач имеют место соотношения:  ,которые позволяют, зная оптимальное решение одной из двойственных задач, найти оптимальное решение другой задачи. ^ Составим экономико-математическую модель задачи оптимального использования ресурсов на максимум прибыли. Теперь сформулируем двойственную задачу. Пусть некая организация решила закупить все ресурсы рассматриваемого предприятия. При этом необходимо установить оптимальную цену на приобретаемые ресурсы у1, у2, y3, … сходя из следующих объективных условий: — покупающая организация старается минимизировать общую стоимость ресурсов; — за каждый вид ресурсов надо уплатить не менее той суммы, которую хозяйство может выручить при переработке сырья в готовую продукцию. Оптимальные значения переменных двойственной задачи называют двойственными оценками (теневыми ценами, объективно обусловленными оценками). ^ можно интерпретировать так: предприятию безразлично, производить ли продукцию по оптимальному плану X и получить максимальную прибыль либо продать ресурсы по оптимальным ценам Y и возместить от продажи равные ей минимальные затраты на ресурсы. Экономико-математический анализ оптимальных решений базируется на свойствах двойственных оценок. В пределах устойчивости двойственных оценок (для определения этих границ существуют математические соотношения, которые реализованы в «Отчете по устойчивости» Excel) имеют место следующие свойства. 1. Величина двойственной оценки того или иного ресурса показывает, насколько возросло бы максимальное значение целевой функции, если бы объем данного ресурса увеличился на одну единицу (двойственные оценки измеряют эффективность малых приращений объемов ресурсов в конкретных условиях данной задачи). Сказанное позволяет выявить направления «расшивки» узких мест, обеспечивающие получение наибольшего экономического эффекта, а также целесообразность изменения в структуре выпуска продукции с позиций общего оптимума. 2. Двойственные оценки отражают сравнительную дефицитность различных видов ресурсов в отношении принятого в задаче показателя эффективности. Оценки показывают, какие ресурсы являются более дефицитными (они будут иметь самые высокие оценки), какие менее дефицитными и какие совсем недефицитны (избыточны). 3. Двойственные оценки позволяют определять своеобразные «нормы заменяемости ресурсов»: имеется в виду не абсолютная заменяемость ресурсов, а относительная; т.е. заменяемость с точки зрения конечного эффекта и лишь в конкретных условиях данной задачи. 4. Двойственные оценки служат инструментом определения эффективности отдельных хозяйственных решений (технологических способов), с их помощью можно определять выгодность производства новых изделий, эффективность новых технологических способов: если  — выгодно,если  — невыгодно.^ Теорема об оценках. Значения переменных yi в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов bi системы ограничений (неравенств прямой задачи) на величину  : .Решая ЗЛП симплексным методом, мы одновременно решаем двойственную задачу. Значения переменных двойственной задачи yi в оптимальном плане называют, как выше уже отмечено, объективно обусловленными, или двойственными оценками. Из теоремы об оценках  известно, что колебание величины bi приводит к увеличению или уменьшению  . Оно определяется величиной yi в случае, когда при изменении величин bi значения переменных yi в оптимальном плане соответствующей двойственной задачи остаются неизменными. Поэтому необходимо найти такие интервалы изменения каждого из свободных членов системы ограничений исходной ЗЛП, в которых оптимальный план двойственной задачи не менялся бы.Для двойственных оценок оптимального плана весьма существенное значение имеет их предельный характер. Точной мерой влияния ограничений на функционал оценки являются лишь при малом приращении ограничения. Известно, что оценки не меняют своей величины, если не меняется набор векторов, входящих в базис оптимального плана, тогда как интенсивность этих векторов (значения неизвестных) в плане могут меняться. ^ Транспортная задача является одной из наиболее распространенных задач линейного программирования и находит широкое практическое приложение. ^ (об оптимальном закреплении потребителей к поставщикам). Некоторый однородный продукт, сосредоточенный у m производителей (поставщиков) Ai в количестве ai  единиц, необходимо доставить n потребителям Bj в количестве bj  единиц. Известна стоимость cij перевозки единицы груза от поставщика i к потребителю j. Необходимо составить план перевозок, позволяющий с минимальными затратами перевезти все грузы и полностью удовлетворить потребителей.Часто исходные данные транспортной задачи записывают в виде таблицы (матрицы) планирования:
Составим экономико-математическую модель (транспортная задача относится к двухиндексным задачам линейного программирования):
 ;
 .Таким образом, модель транспортной задачи имеет следующий вид:
В рассмотренной модели предполагается, что суммарные запасы равны суммарным потребностям, т.е.
Транспортная задача, в которой суммарные запасы и суммарные потребности совпадают, называется закрытой транспортной задачей, в противном случае получаем открытую транспортную задачу. Замечание. Решение открытой ТЗ проводится сведением к закрытой ТЗ (введением фиктивного поставщика или фиктивного потребителя):
Стоимость перевозки единицы груза до фиктивного потребителя или от фиктивного поставщика приравнивается нулю, так как груз в обоих случаях фактически не перевозится. ^ Задача о назначениях является частным случаем транспортной задачи, в котором все значения ai и bj равны 1. Такая задача возникает при распределении людей на должности или работы, водителей на машины, рабочих на станки, автомашин на маршруты, групп по аудиториям и т.п.^ (об оптимальном закреплении исполнителей на работы). Имеется n видов работ и n исполнителей этих работ. Известна эффективность cij выполнения исполнителем i работы j. Требуется так назначить исполнителей по видам работ, чтобы суммарный эффект от назначений был максимальным. Часто исходные данные задачи о назначениях записывают в виде таблицы (матрицы) планирования:
Составим экономико-математическую модель (задача о назначениях относится к двухиндексным задачам линейного программирования):
  ;
 .Таким образом, модель задачи о назначениях имеет следующий вид:
Замечание. Если число исполнителей m не равно числу работ n (т.е. задача является открытой), то возможно применение двух способов:
 ;  ;
;  .Решение средствами MS Excel При решении задачи о назначениях необходимо учитывать, что переменные принимают значения «0» или «1». Поэтому при заполнении диалоговова окна Поиск решения в поле Ограничения необходимо ввести требование двоичности (бинарности в MS Office 2010) изменяемых переменных:  ^ Задачи оптимизации, в которых переменные должны быть целыми числами, называются задачами целочисленного (дискретного) программирования:
Для получения целочисленных решений применяются специальные методы:
Решение средствами MS Excel Дискретная оптимизация проводится аналогично решению непрерывной задачи. Отличие состоит в том, что при заполнении диалоговова окна Поиск решения в поле Ограничения необходимо ввести требование целочисленности изменяемых переменных:  | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
;
.
.
.
,
,
.
, 
,
– заданные постоянные величины.
, перпендикулярно ему провести прямую (линию уровня).
, где xij – количество единиц груза, перевозимых от поставщика i 
;
, которая выражает стоимость перевозок всех грузов;
, 
.
;
.
, где
, которая выражает суммарный эффект от назначений;
, 
целые неотрицательные числа,Добавить документ в свой блог или на сайт
Похожие:
 | Курсовая работа состоит из введения, 3 глав, заключения и списка использованной литературы | | Конспект лекций по дисциплине «Инвестирование» для студентов экономических специальностей всех форм обучения Сост.: В. М. Гридасов... |
| Опорный конспект лекций по дисциплине «Делопроизводство» для студентов 2 курса (3 семестр) сгф для направления 101100. 62 «Гостиничное... | | Федеральное государственное образовательное учреждение высшего профессионального образования |
| «Тульский филиал Финансового университета при Правительстве Российской Федерации» | | Безопасность в чрезвычайных ситуациях и гражданская оборона. Конспект лекций. Рубцов Б. Н. М. Миит, 2001 |
| Конспект лекций по дисциплине «Публичное администрирование» (для студентов специальности 06. 05. 02) | | Конспект лекций по дисциплине «Публичное администрирование» (для студентов специальности 06. 05. 02) |
| Целью кр закрепления и углубления теоретических знаний и умений студента в области оптимизации устройств различного назначения. В... | | Тема №1 (4 часа) Назначение, основные параметры и состав каналообразующих устройств 5 |