Автор работы: Пользователь скрыл имя, 02 Декабря 2014 в 14:04, шпаргалка
15.Анализ чувствительности в ЛП. Суть графического метода анализа чувствительности. Геометрическая интерпретация активных и пассивных ограничений.
На практике многие экономические параметры (цены на продукцию и сырье, запасы сырья, спрос на рынке, заработная плата и т.д.) с течением времени меняют свои значения. Поэтому оптимальное решение задачи ЛП, полученное для конкретной экономической ситуации, после ее изменения может оказаться непригодным или неоптимальным. В связи с этим возникает задача анализа чувствительности задачи ЛП, а именно того, как возможные изменения параметров исходной модели повлияют на полученное ранее оптимальное решение.
Ограничения линейной модели классифицируются следующим образом:
Связывающие (активные, лимитирующие) ограничения – такое ограничение, для которого значение левой части, вычисляемое в оптимальной точке, равно значению правой части. Связывающие ограничения проходят через оптимальную точку.
Несвязывающие ограничения (пассивные, нелимитирующие) – ограничения, для которых оптимальные значения резерва или излишка являются положительными. Несвязывающие ограничения не проходят через оптимальную точку.
1.Общая характеристика ИО как комплексного научно-прикладного направления. Исследование операций – научная дисциплина, занимающаяся разработкой и практическим применением методов наиболее эффективного управления различными организационными системами. Цель: Формирование целостного представления о методологии исследования операций осуществляемых в экономических системах. Задачи : -уметь формализовать описание проблемной ситуации в экономической системе включающие допустимые области изменения показателей ее функционирования при ограниченных ресурсах; критерии эффективности операции и информацию о предпочтениях лица принимающего решения. -Изучить специфику математических методов отыскания и анализа наилучших решений для достижения цели операции. -Показать возможность применения моделей и методов исследований операций к анализу конкретной экономической системы.
Основные понятия и термины исследования операции. Операция – совокупность взаимосвязанных, целенаправленных действий. /Любое мероприятие, объединяемое единым замыслом и направленное к достижению определенной цели. Решение – сознательный выбор одной из ряда допустимых альтернатив./ Подлежащее осуществлению намерение, пригодное для достижения поставленной цели./ Сознательный выбор параметров организации операции из некоторой допустимой совокупности. Оперирующая сторона – определенное лицо. Участвующее в операции и стремящееся к достижению определенной цели или коллектив, объединенный организационным руководством и активно стремящийся к достижению поставленной цели. Действующие факторы операции – объективные условия и обстоятельства, определяющие особенности операции и непосредственно влияющие на ее исход. Критерий эффективности операции – количественный показатель, характеризующий соответствие между результатом принятых действий и целью операции. Фазовые переменные операции – показатели состояния объекта, отражающие ход проведения операции во времени. С позиции учета неопределенности действующих факторов все операции принято делить: 1.Детерминированные – при полностью известных и контролируемых условиях операции принятие управленческого решения однозначно приведет к достижению поставленных целей. 2.Стохастические – помимо заранее заданных условий, состояние объекта управления зависит от ряда неучтенных, принципиально неконтролируемых факторов: принятие и реализация управленческого решения не гарантирует достижение цели. 3.Игровая операция – осуществляется тогда, когда в ней участвует несколько заинтересованных сторон (партнеры, конкуренты) и некоторые факторы, от которых зависит достижение цели, неконтролируемы и нет данных судить о том, какое состояние системы более или менее вероятно. Состояние операции в некоторый момент времени t – совокупность ее фазовых переменных, проявляющихся в этот момент и отражающих объективно сложившееся положение дел. Исследователи операции – группа лиц, владеющих методологией принятия решения и использующих эти методы для анализа операции Лицо, принимающее решение (ЛПР) – это человек или группа людей, наиболее информированных о целях операции и возможностях оперирующей стороны, которым представлено право окончательного выбора, обладающих возможностями реализации этого выбора и на которых возложена вся полнота ответственности за результаты и последствия проведения операции. Исследование операций можно осуществлять: -При помощи научного метода (путем причинно-следственных связей) -Традиции -Др. Любой из этих подходов может быть либо дискретный (характеризующий, как люди осуществляют выбор), либо нормативный (характеризующий, как люди должны делать выбор). |
2.Основные элементы мат.модели операции. Этапы мат.моделирования в системе поддержки принятия решения. Модель – средство замещения объекта при непосредственном изучении тех его свойств, которые представляются важными для исследования. Математическая модель - это способ описания реальной жизненной ситуации (задачи) с помощью математического языка. Математическая модель операции в экономической системе – это формализованное описание допустимых действий оперирующей стороны и возможных последствий их реализации
Основные элементы математической модели операции: управляемые переменные – показатели состояний экономической системы, на которые ЛПР может непосредственно влиять и терминах, которых будет сформулировано решение. Пояснение: Лицо, принимающее решение (ЛПР) – это человек или группа людей, наиболее информированных о целях операции и возможностях оперирующей стороны, которым представлено право окончательного выбора, обладающих возможностями реализации этого выбора и на которых возложена вся полнота ответственности за результаты и последствия проведения операции. -неуправляемые переменные, т.е. ситуации, охватываемые проблемой, которыми не может управлять лицо, принимающее решение, но которые совместно с управляемыми переменными могут влиять на результаты выбора. -целевая функция – зависимость между ключевым показателем и управляемой переменной. -система ограничений
Основные этапы исследования операций в экономических системах: 1.Формулировка и конфигурация проблемы 1.1.Выявление субъекта операции 1.2.Первоначальная формулировка подлежащей рассмотрению проблемы 1.3.Необходимость учета многосторонних связей проблемосодержащей системы. 1.4Выделение наиболее существенных из установленных отношений, т.е. определение конфигурации решаемой проблемы 2.Постановка задачи исследования операции 2.1.Выявление возможностей выбора линии поведения ЛПР из существующих альтернатив 2.2.Наличие способов оценки ресурсов, требующихся для каждого варианта действий 2.3.Определение цели, достижение которой обозначает решение проблемы 2.4.Указание критерия эффективности операции (это количественная характеристика, которая имеет смысл экстремального значения наиболее важного показателя функционирования системы и выражает степень пригодности каждой допустимой альтернативы в качестве средства достижения целей и используется для отыскания наилучшей альтернативы) 3.Математическая
формулировка задачи (построение
мат модели операции)Осуществля 3.1.Вводятся обозначения параметров задачи и управляемых переменных 3.2.Строится функция цели 3.3.Записывается система ограничений 3.4.Указывается критерий выбора оптимального решения (максимизация или минимизация) 4.Сбор необходимой информации Параметр – это характеристика внешних условий, значение которой не зависит от решений, принимаемых ЛПР 5.Анализ математической модели операции 6.Формулировка принципа оптимальности 7.Отыскание оптимального решения 7.1 Применение методов
оптимизации к определению 8.Проверка полученных
результатов на их 9. Коррекция модели |
3.Понятие о мат.программировании. Классификация направлений, содержательные примеры задач. Специфика решения задач мат.программирования. Математическое программирование - математическая дисциплина, изучающая теорию и методы решения задач о нахождении экстремумов функций на множествах, определяемых линейными или нелинейными ограничениями в виде равенств или неравенств. Направления математического программирования:
1)Линейное программирование. ЛП предполагает, что существует единственная целевая функция (ЦФ), которая линейна и, множество, на котором ищется экстремум ЦФ, задается системой ограничений в виде линейных равенств или неравенств. Модели ЛП можно использовать в экономике для принятия крупномасштабных плановых решений в сложных ситуациях. 2)Нелинейное программирование. В НП предполагается, что ограничения или ЦФ могут быть функциями общего вида. К задачам нелинейного математического программирования относят: *выпуклое программирование. Включает задачи максимизации вогнутой функции на выпуклом множестве или минимизации выпуклой функции на выпуклом множестве. *целочисленное программирование. По смыслу значительной части экономических задача, относящихся к задачам ЛП, компоненты решения должны выражаться в целых числах, т.е. должны быть целочисленными. К ним относят, например, задачи, в которых переменные означают количество единиц неделимой продукции, число станков при загрузке оборудования, число судов при распределениях по линиям, число турбин в энергосистеме и т.п. *булевское программирование. Задачи Булевского программирования относятся к частному случаю задачи целочисленного линейного программирования, управляемые переменные в таких задачах задаются в виде индикаторов, принимающих только два возможных значения либо 0 либо 1. Наиболее известные из этих задач - это задача о назначениях (какого работника на какую должность принять), задача выбора маршрута (задача коммивояжера, задача почтальона). Для решения задач этого типа разрабатываются очень специфические алгоритмы, основанные на комбинаторике, графах и т.д. *динамическое программирование (управление многошаговыми процессами) – метод оптимизации, приспособленный к операциям, в которых процесс принятия решения может быть разбит на этапы (шаги). Такие операции называют многошаговыми. Модели ДП применяются при решении задач значительно меньшего масштаба, нежели задачи ЛП, например, при разработке правил управления запасами, устанавливающими момент пополнения запасов и размер пополняющего заказа, при разработке принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию и т.п.
Стандартной или основной задачей математического программирования считается следующая задача: Требуется минимизировать целевую функцию, в заданном виде, где f- общее обозначение зависимости наиболее существенного показателя от управляемых переменных. 1.ЦФ: Z=f(x)->min. (1) 2.Условия, задающие ограничения на управляемые переменные в виде неравенств: gi(x)≥0, i=1,..,k (2) Условия, задающие ограничения на управляемые переменные в виде равенств: hj(x)=0, j=k+1,…,m (3) 3.Оптимальное решение-вектор x=(x1,x2,…..xn)T принадлежит Rn (линейному нормированному пространству), где где gi(x), hj(x), f(x) предполагаются непрерывно дифференцируемыми.
Причем для стандартной задачи математического программирования используются следующие определения: План ЗМП – всякий вектор x, принадлежащий пространству Rn Допустимый план ЗМП – совокупность значений x=(x1,x2,…..xn)Т удовлетворяющая системе ограничений (2) и (3). Множество допустимых планов – множество, содержащее все возможные решения системы ограничений стандартной ЗМП: B={x|x принадлежит Rn; gi(x)≥0, i=1,..,k; hj(x)=0, j=k+1,…,m} Множество оптимальных планов – подмножество множества допустимых планов, содержащее те допустимые решения, которые обеспечивают экстремум функции цели. Q={x*|x* принадлежит B; f(x*)≤ f(x), любые x принадлежащие B} Решение ЗМП - пара (x*,Z*), состоящая из оптимального плана и оптимального значения функции цели. |
4.Выпуклые множества. Линейная комбинация выпуклых множеств. Замыкание и внутренность выпуклого множества. Выпуклая оболочка множества. Крайняя точка выпуклого множества, ее геометрическая иллюстрация. Соотношение понятий крайней точки и граничной точки. Дано: Пусть Х – линейное вещественное пространство; пусть С ⊂ X – подмножество множества Х, тогда С называется выпуклым, если оно целиком содержит прямолинейный отрезок, соединяющий любые две точки, принадлежащие этому множеству. Выпуклыми множествами могут быть не только многоугольники. Примерами выпуклых множеств являются круг, сектор отрезок, многоугольная область, куб, пирамида, многогранная область, полуплоскость, полупространство и т.п. Пересечение (общая часть) любого числа выпуклых множеств есть выпуклое множество. Пусть элементы x1,x2 ∈ C; пусть 0≤θ≤1 – любое вещественное число, отрезок [x1,x2]={ X/ x= x1+ θ(x2 - x1)= θx2 + (1- θ) x1; 0≤ θ≤1} (любая точка отрезка записывается таким образом) Пусть элементы , ∈ C и θ – любое вещественное число из промежутка от 0 до 1, то множество С является выпуклым множеством, если [, ] ⊂ С Ограниченное множество С из Х называется выпуклым, если любая прямая, проходящая через внутреннюю точку этого множества пересекает его границу в двух точках. Выпуклой оболочкой множества М называется пересечение всех выпуклых множеств, содержащих данное множество М; или минимальное выпуклое множество, содержащее данное. Линейная комбинация выпуклых множеств Линейной комбинацией выпуклых множеств Ki c коэффициентами ≥ 0 называется выпуклое множество
Где Ki – непустые выпуклые множества, принадлежащие линейному вещественному пространству, а – неотрицательные вещественные числа. Замыкание и внутренность выпуклого множества. Пусть множество С – выпуклое, тогда: Объединение множества С и всех его крайних точек называется замыкание выпуклого множества С, а совокупность всех внутренних точек множества С называется внутренностью выпуклого множества С. Множество точек называется замкнутым, если включает все свои граничные точки. Крайняя точка выпуклого множества, ее геометрическая иллюстрация. Соотношение понятий крайней точки и граничной точки. Среди точек выпуклого множества можно выделить внутренние, граничные и крайние точки. Точка множества называется внутренней, если в некоторой ее окрестности содержатся точки только данного множества. (под окрестностью точки плоскости (пространства) подразумевают круг (шар) с центром в этой точке.) Точка множества называется граничной, если в любой ее окрестности содержатся как точки, принадлежащие данному множеству, так и точки, не принадлежащие ему. Точка множества называется крайней, если она не является внутренней ни для какого отрезка, целиком принадлежащего данному множеству.
На рисунке приведены примеры различных точек многоугольника: внутренней (точки М), граничной (точка N) и крайних (точки A,B,C,D,E). Точка А – крайняя, так как для любого отрезка, целиком принадлежащего многоугольнику, например, отрезка AP, она не является внутренней; точка А – внутренняя для отрезка KL, но этот отрезок не принадлежит целиком многоугольнику. Для выпуклого множества угловые точки всегда совпадают с вершинами многоугольника (многогранника), в то же время для невыпуклого множества это не обязательно. |
5.Выпуклое многогранное множество и выпуклый многогранник. О представлении выпуклого многогранника. Выпуклой оболочкой множества М называется пересечение всех выпуклых множеств, содержащих данное множество М; или минимальное выпуклое множество, содержащее данное. Выпуклая оболочка конечного множества точек называется выпуклым многогранником. Определение 1. Замкнутое выпуклое ограниченное множество в Rn, имеющее конечное число угловых точек, называется выпуклым n-мерным многогранником. Определение 2. Замкнутое выпуклое неограниченное множество в Rn , имеющее конечное число угловых точек, называется выпуклой многогранной областью. Определение 3. Множество А Rn называется ограниченным, если найдется n-мерный шар, содержащий это множество.
Определение 4. Выпуклой линейной комбинацией точек называется выражение , где ti , . Теорема (теорема о представлении выпуклого многогранника). Любую точку выпуклого многогранника можно представить в виде выпуклой линейной комбинации его угловых точек. Вершина выпуклого многогранника - это такая точка, которая не является внутренней точкой никакого отрезка, концы которого принадлежат этому многограннику (см. рис 14). Этим свойством обладают только вершины.
|
7.Экстремальные свойства выпуклых функций. О глобальности локального условного минимума выпуклой функции на выпуклом множестве. О выпуклости множества точек минимума выпуклой функции. О единственности точки минимума строго выпуклой функции.
Функция будет являться строго выпуклой, если знак вышеуказанного неравенства сменить на строгий.
Однако проще всего определить выпуклую функцию геометрически. Для этого необходимо построить надграфик функции, который у выпуклой функции будет являться выпуклым множеством. Надграфик функции f(x) это множество таких точек, которое расположено надо графиком функции и на самом графике, кроме того, координата x которых лежит в области определения функции. Выделение задач выпуклого программирования в специальный класс объясняется экстремальными свойствами выпуклой функции. Основные экстремальные свойства выпуклых функций: 1. Множество точек минимума выпуклой функции, заданной на выпуклом множестве, - выпукло. 2. Пусть - выпуклая функция, заданная на замкнутом выпуклом множестве . Тогда локальный минимум на Х является и глобальным. 3. Если глобальный минимум достигается в двух различных точках, то он достигается и в любой точке отрезка, соединяющего данные точки. 4. Если - строго выпуклая функция, то ее глобальный минимум на выпуклом множестве Х достигается в единственной точке.
Критерий выпуклости: для того, чтобы непрерывно дифференцируемая функция была выпуклой на не пустом открытом выпуклом множестве С необходимо и достаточно, чтобы для любых двух векторов x,y принадлежащих множеству С выполнялось неравенство: f(y)-f(x)≥(grad f(x);y-x) Геометрический смысл: дифференцируемая функция является выпуклой тогда и только тогда, когда график ее целиком расположен выше касательной плоскости проведенной в любой точке поверхности. Экстре́мум — максимальное или Точка называется точкой локального максимума функции , если существует такая окрестность этой точки, что для всех из этой окрестности выполняется неравенство: . Точка называется точкой локального минимума функции , если существует такая окрестность этой точки, что для всех из этой окрестности . Глобальным экстремумом называют точку, в которой целевая функция имеет наибольшее (наименьшее) значение среди всех локальных экстремумов области определения. |
8.Функция Лагранжа. Седловая точка функции Лагранжа. Условие дополняющей нежесткости. Теоремы о связи седловой точки функции Лагранжа с решением задачи нелинейного программирования. Метод множителей Лагранжа (французский математик и механик) является одним из способов отыскания условного экстремума функции цели при ограничениях-равенствах при помощи построения вспомогательной функции Лагранжа, которая в области допустимых решений достигает максимума для тех же значений переменных x1, x2,… xn,что и ЦФ. Постановка задачи. Пусть решается стандартная задача математического программирования, для которой необходимо найти вектор x =(x1, x2,… xn)T, обеспечивающий минимальное значение ЦФ. Математическая модель задачи выглядит следующим образом: 1.ЦФ: Z=f(x)->min. (1) 2.x1, x2,… xn –управляемые переменные 3.Условия, задающие ограничения на управляемые переменные в виде равенств (накладываемая система ограничений): gi(x)=0, i=1,..,n (2) При этом оптимальное решение, то есть вектор x=(x1,x2,…..xn)T принадлежит Rn (линейному нормированному пространству), где где gi(x), hj(x), f(x) предполагаются непрерывно дифференцируемыми.
Составим функцию Лагранжа: L(x1,x2,…..xn, λ1 λ2,…, λm) = f(x1,x2,…..xn)+Σ(i=1 до m)λi*gi(x1,x2,…..xn), в которой введен набор новых неизвестных λ1 λ2,…, λm – постоянные (неопределенные) множители Лагранжа, при этом их количество равно количеству ограничений. Функция Лагранжа представляет собой линейную комбинацию ЦФ данной задачи математического программирования и функции, определяющие левые части уравнений из системы ограничений. Множитель Лагранжа измеряет чувствительность стоимости к изменению количества, значит он имеет размерность цены, его называют теневой ценой данного вида ресурса. Необходимо заметить следующее: предполагается, что функции f(x) и g1,g2,… gi являются непрерывно дифференцируемыми и n>m, а разность m-n называют числом степеней свободы задачи (1)-(2) Теорема Лагранжа. Для того, чтобы вектор x*=(x*1,x*2,…..x*n)Т являлся решением оптимизационной задачи (1)-(2)необходимо, чтобы существовал такой вектор λ*=(λ*i λ*i,…, λ*m )Т, что пара векторов (x*,λ*) удовлетворяла бы системе (n+m) алгебраических уравнений следующего вида: 1.Условие стационарности точки (x*, λ*) принадлежит Rn+Rm (!) 2.Условие допустимости (x*, λ*) принадлежит Rn+Rm (!) Областью определения введенной функции Лагранжа будет являться множество пар векторов (!)
Причем седловой точкой функции Лагранжа будет являться точка (!)
При условии, что выполняются неравенства (!)
Сформулируем теорему о связи седловой точки функции Лагранжа с решением задачи нелинейного программирования. Теорема. Пусть и все выпуклы и функции удовлетворяют условию регулярности по Слейтеру. Вектор является решением задачи тогда и только тогда, когда существует такой вектор , что Пояснение. Множество допустимых решений является регулярным по Слейтеру в том случае, когда существует хотя бы одна точка из области допустимых решений такая, что неравенства из системы ограничений ЗЛП буду выполняться. Если для задачи математического программирования (1)-(2) выполнены условия теоремы Куна-Такера: 1.Множество B0 – выпуклое. 2.Функции Z=f(x) и gi(x)являются выпуклыми на множестве B0 3.Допустимое множество В определено по формуле L’ и является регулярным по Слейтеру 4.Множество В* точек минимума (максимума) функции Z=f(x), принадлежащих множеству В непусто, т.е. (!)
То необходимым и достаточным условием оптимальности точки x*, принадлежащей множеству B0 , является существование такого вектора множителей Лагранжа: λ*=( λ1,λ2,.. λm)Т, принадлежащий ᴧ (лямбда большая), λi>=0 что пара векторов (x*, λ*) является седловой точкой функции Лагранжа на множестве B0×ᴧ (декартовое произведение)
Условия Куна-Такера для ЗЛП. Для того, чтобы пара векторов (x*, λ*) была седловой точкой функции Лагранжа L поставленной задачи в области x>=0 и λ>=0 необходимо и достаточно, чтобы выполнялись условия: (!)
Здесь введены обозначения: (!)
Условие дополняющей нежесткости λi*g i*=0 , i=1,m. Представляет собой систему решение которой соответствует следующей записи: λi*=0, gi(x*)≤0 (в системе) λi*<0, gi(x*)=0 (в системе) |
9.Задача выпуклого программирования. Построение допустимого множества задачи выпуклого программирования. Необходимое и достаточное условия существования оптимального решения задачи выпуклого программирования (Теорема Куна-Таккера). Выпуклое программирование – раздел математического программирования, в котором изучаются оптимизационные задачи для выпуклых функций на выпуклом множестве. Пусть Х – линейное вещественное пространство; пусть С ⊂ X – подмножество множества Х, тогда С называется выпуклым, если оно целиком содержит прямолинейный отрезок, соединяющий любые две точки, принадлежащие этому множеству. Пусть элементы x1,x2 ∈ C; пусть 0≤θ≤1 – любое вещественное число, отрезок [x1,x2]={ X/ x= x1+ θ(x2 - x1)= θx2 + (1- θ) x1; 0≤ θ≤1} (любая точка отрезка записывается таким образом) Пусть элементы , ∈ C и θ – любое вещественное число из промежутка от 0 до 1, то множество С является выпуклым множеством, если [, ] ⊂ С Ограниченное множество С из Х называется выпуклым, если любая прямая, проходящая через внутреннюю точку этого множества пересекает его границу в двух точках. (!)
Постановка задачи выпуклого программирования (ЗВП): Пусть B0 ,принадлежащее Rn, – выпуклое множество в n-мерном вещественном линейном пространстве. Функции f(x) и gi(x), i=1,p – определены и выпуклы на множестве B0. Требуется найти вектор x*, который обеспечит минимальное значение функции f(x) (Z=f(x)->min) на допустимом множестве В.
То есть решением ЗВП будет являться (x*, f*), где f*=minf(x), При описании множества B0 стараются чтобы было легко проверить условие , B0={x|x=(x1, x2,…,xn)Т, xi>=0, i=1,n} Для задачи нелинейного программирования, представленной в следующем виде (ограничения типа равенств в задаче отсутствуют) (!)
На допустимом множестве В необходимо найти вектор x*, который обеспечивал бы min(max) функции Z (f*=min(max)f(x), где x принадлежит множеству В) ( ( нргоп ( ошшшшшшш Для решения поставленной ЗНП необходимо все ограничения, имеющие знак больше равно (>=) привести к виду меньше равно (<=). Далее необходимо ввести функцию Лагранжа, имеющую вид: (!)
Областью определения введенной функции Лагранжа будет являться множество пар векторов (!)
Причем седловой точкой функции Лагранжа будет являться точка (!)
При условии, что выполняются неравенства (!)
Теорема Куна-Такера для ЗЛП. Пусть для поставленной задачи ЛП выполняются следующие условия: 1.Множество B0 – выпуклое. 2.Функции Z=f(x) и gi(x)являются выпуклыми на множестве B0 3.Допустимое множество В определено по формуле L’ и является регулярным по Слейтеру 4.Множество В* точек минимума (максимума) функции Z=f(x), принадлежащих множеству В непусто, т.е. (!)
Пояснение. Множество допустимых решений является регулярным по Слейтеру в том случае, когда существует хотя бы одна точка из области допустимых решений такая, что неравенства из системы ограничений ЗЛП буду выполняться. Тогда, при выполнении всех вышеуказанных пунктов, необходимым и достаточным условием оптимальности точки x*, принадлежащей множеству B0 , является существование такого вектора множителей лагранжа: λ*=( λ1,λ2,.. λm)Т, принадлежащий ᴧ (лямбда большая), λi>=0, что пара векторов (x*, λ*) является седловой точкой функции Лагранжа на множестве B0×ᴧ (декартовое произведение)
Условия Куна-Такера для ЗЛП. Для того, чтобы пара векторов (x*, λ*) была седловой точкой функции Лагранжа L поставленной задачи в области x>=0 и λ>=0 необходимо и достаточно, чтобы выполнялись условия: (!)
Здесь введены обозначения: (!)
|
6.Выпуклые функции. Определение строго выпуклой, сильно выпуклой и вогнутой функций; надграфик функции. Условия выпуклости в терминах первой производной. Критерий выпуклости дважды дифференцируемых функций. Связь между выпуклостью функции конечного числа переменных и выпуклостью функций одной переменной. Функция f(x) определяемая на С называется выпуклой на С, если для всех элементов множества С и вещественных 0≤θ≤1 выполняется неравенство. F(θx2+(1-θ)x1)≤ θf(x2)+(1-θ)f(x1) С геометрической точки зрения – для функции одной переменной хорда, соединяющая любые 2 точки графика выпуклой функции, лежит выше дуги, концами которого являются указанные точки. Если при любых значениях аргумента (х1 не равен х2) и 0<θ<1 имеет место строгое неравенство F (θx2+(1-θ)x1) < θf(x2) + (1-θ)f(x1), то функция называется строго выпуклой на множестве С. Функция f(x) определяемая на С называется вогнутой (строго вогнутой) на С, если -f(x) выпукла (строго выпукла) на множестве С. Надграфик — это множество точек, лежащих над графиком данной функции. Функция (её график выделен синим) и её надграфик (закрашено зеленым).
Необходимым и достаточным условием выпуклости функции является неотрицательная определенность матрицы вторых производных функции – матрицы Гессе (гессиана) |
10..Задача линейного программирования. Определение ключевых понятий линейного программирования: план, допустимый план, оптимальный план, базис, базисное решение, невырожденный опорный план, решение задачи мат.оптимизации. Линейное программирование — раздел математического программирования. ЛП предполагает, что существует единственная целевая функция (ЦФ), которая линейна и, множество, на котором ищется экстремум ЦФ, задается системой ограничений в виде линейных равенств или неравенств. Линейная функция – зависимость одной переменной от другой, которая задается по следующему правилу: каждому числу x принадлежащему множеству X ставится в соответствие число y из множества Y. Y=kx+b, где b и x – некоторые числа. Модели ЛП можно использовать в экономике для принятия крупномасштабных плановых решений в сложных ситуациях. Общей задаче линейного программирования принято считать задачу вида:
a11x1 + a12x2 + ... + a1nxn ≤ b1, a21x1 + a22x2 + ... + a2nxn ≥ b2, ... ... ... ... ... ... ... ... ... ... ... . . am1x1 + am2x2 + ... + amnxn = bm, i=1,m; j=1,n и дополнительное ограничение неотрицательности управляемых переменных – xj>=0. aij, bi, cj –заданные действительные числа.
В ЗЛП все переменные делятся на две группы: m-базисные, n-m – основные. Число базисных переменных = числу уравнений или неравенств. Для решения ЗЛП необходимо найти такие значения управляемых переменных x1*, x2* … xn* или вектор x=( x1*, x2* … xn*), которые удовлетворяют системе ограничений и определяют экстремальное (максимальное или минимальное) значение функции цели. Решение является оптимальным, если целевая функция принимает экстремальное значение. ЗЛП называется разрешимой, если существует упорядоченный набор конечных значений x1*, x2* … xn* <+∞, удовлетворяющий всем ограничениям системы и обращающий ЦФ в максимум или в минимум в зависимости от содержательной постановки задачи. Неразрешимость ЗЛП может быть обусловлена следующими условиями:
Ключевые понятия ЛП:
|
11.Основные свойства задачи линейного программирования. Эквивалентность базисных решений и крайних точек линейного многогранного множества. Линейное программирование — раздел математического программирования. ЛП предполагает, что существует единственная целевая функция (ЦФ), которая линейна и, множество, на котором ищется экстремум ЦФ, задается системой ограничений в виде линейных равенств или неравенств. Линейная функция – зависимость одной переменной от другой, которая задается по следующему правилу: каждому числу x принадлежащему множеству X ставится в соответствие число y из множества Y. Y=kx+b, где b и x – некоторые числа. Модели ЛП можно использовать в экономике для принятия крупномасштабных плановых решений в сложных ситуациях. К примеру, к линейному программированию относят задачи рационального ведения хозяйства. Они возникают тогда, когда в экономической системе существуют ограничения на имеющиеся в распоряжении ресурсы, необходимые для выполнения каждой из намеченных работ. Цель решения распределительной задачи – отыскание оптимального варианта распределения ресурсов по видам работ. Оптимальный вариант распределения позволяет получить результат, обеспечивающий, например, минимум общих затрат, максимум общего дохода или экстремальное значение какой-либо другой целевой функции, выражающей эффективность функционирования организации. К примеру, к ЛП относят: задача использования сырья, составления рациона, о раскрое материала. Общей задаче линейного программирования принято считать задачу вида:
a11x1 + a12x2 + ... + a1nxn ≤ b1, a21x1 + a22x2 + ... + a2nxn ≥ b2, ... ... ... ... ... ... ... ... ... ... ... . . am1x1 + am2x2 + ... + amnxn = bm, i=1,m; j=1,n и дополнительное ограничение неотрицательности управляемых переменных – xj>=0. aij, bi, cj –заданные действительные числа.
В ЗЛП все переменные делятся на две группы: m-базисные, n-m – основные. Число базисных переменных = числу уравнений или неравенств. Для решения ЗЛП необходимо найти такие значения управляемых переменных x1*, x2* … xn* или вектор x=( x1*, x2* … xn*), которые удовлетворяют системе ограничений и определяют экстремальное (максимальное или минимальное) значение функции цели. Решение является оптимальным, если целевая функция принимает экстремальное значение. ЗЛП называется разрешимой, если существует упорядоченный набор конечных значений x1*, x2* … xn* <+∞, удовлетворяющий всем ограничениям системы и обращающий ЦФ в максимум или в минимум в зависимости от содержательной постановки задачи. Неразрешимость ЗЛП может быть обусловлена следующими условиями:
Ключевые понятия ЛП:
Основные свойства задачи линейного программирования. Теорема 1. Множество допустимых планов задачи линейного программирования выпукло, если оно не пусто. Теорема 2. Множество оптимальных планов задачи ЛП выпукло, если оно не пусто. Теорема 3. «О достижимости оптимума в ЗЛП» Если ЦФ ЗЛП на max/min ограничена сверху/снизу, то эта задача имеет оптимальное решение на множестве допустимых планов. Крайняя точка – это точка выпуклого множества, если она не может быть выражена в виде выпуклой комбинации каких либо 2-х различных точек этого множества. Выпуклым многогранником называют замкнутое ограниченное выпуклое множество, если совокупность его крайних точек(вершин) конечна. Теорема 4. Для того, чтобы точка X = (x1, x2,…,xn) из допустимого множества ЗЛП была крайней необходимо и достаточно, чтобы координаты этой точки удовлетворили не менее чем n линейно независимых ограничениям как равенствам. Теорема 5. «Основная теорема ЛП» Если доп. множество ЗЛП не пусто и имеет хотя бы одну вершину (крайняя точка), то функция цели данной задачи достигает своего минимума в крайней точке множества допустимых планов этой задачи. Если ЦФ принимает минимальное значение более чем в одной крайней точке, то она достигает того же значения в любой точке являющейся выпуклой комбинацией этих крайних точек. Эквивалентность базисных решений и крайних точек линейного многогранного множества. 1. Каждому опорному/базисному
решению ЗЛП соответствует 2. Целевая функция ЗЛП
достигает своего оптимума в
крайней точке выпуклого |
12.Эквивалентные формы постановки ЗЛП, их особенности. Возможность приведения общей ЗЛП к каноническому виду. Линейное программирование — раздел математического программирования. ЛП предполагает, что существует единственная целевая функция (ЦФ), которая линейна и, множество, на котором ищется экстремум ЦФ, задается системой ограничений в виде линейных равенств или неравенств. Линейная функция – зависимость одной переменной от другой, которая задается по следующему правилу: каждому числу x принадлежащему множеству X ставится в соответствие число y из множества Y. T=kx+b, где b и x – некоторые числа. Модели ЛП можно использовать в экономике для принятия крупномасштабных плановых решений в сложных ситуациях. К примеру, к линейному программированию относят задачи рационального ведения хозяйства. Они возникают тогда, когда в экономической системе существуют ограничения на имеющиеся в распоряжении ресурсы, необходимые для выполнения каждой из намеченных работ. Цель решения распределительной задачи – отыскание оптимального варианта распределения ресурсов по видам работ. Оптимальный вариант распределения позволяет получить результат, обеспечивающий, например, минимум общих затрат, максимум общего дохода или экстремальное значение какой-либо другой целевой функции, выражающей эффективность функционирования организации. К примеру, к ЛП относят: задача использования сырья, составления рациона, о раскрое материала. 1. Общей
задачей линейного 1)Целевая функция: F(x)=Z(x1, x2,…xn)=c1x1+c2x2+…+cnxn= ->extr (1) 2)xj – управляемые переменные 3)Система ограничений (2): a11x1 + a12x2 + ... + a1nxn ≤ b1, a21x1 + a22x2 + ... + a2nxn ≥ b2, ... ... ... ... ... ... ... ... ... ... ... . . am1x1 + am2x2 + ... + amnxn = bm, i=1,m; j=1,n и дополнительное ограничение неотрицательности управляемых переменных – xj>=0. aij, bi, cj –заданные действительные числа.
В ЗЛП все переменные делятся на две группы: m-базисные, n-m – основные. Число базисных переменных = числу уравнений или неравенств. Для решения ЗЛП необходимо найти такие значения управляемых переменных x1*, x2* … xn* или вектор x=( x1*, x2* … xn*), которые удовлетворяют системе ограничений и определяют экстремальное (максимальное или минимальное) значение функции цели. Решение является оптимальным, если целевая функция принимает экстремальное значение. ЗЛП называется разрешимой, если существует упорядоченный набор конечных значений x1*, x2* … xn* <+∞, удовлетворяющий всем ограничениям системы и обращающий ЦФ в максимум или в минимум в зависимости от содержательной постановки задачи. Неразрешимость ЗЛП может быть обусловлена следующими условиями:
2.Математическая модель ЗЛП в стандартной форме
Замечание. Задачу, в которой требуется минимизировать ЦФ решают как ЗЛП в стандартной форме при помощи простого правила: max(Z(x))=-min(-Z(x)). 3.Математическая модель ЗЛП в канонической форме
4.Математическая модель ЗЛП в матричной форме
Здесь: А — матрица коэффициентов системы уравнений Х — матрица-столбец переменных задачи Ао — матрица-столбец правых частей системы ограничений
Все формы ЗЛП эквивалентны в том смысле, что каждую из них можно преобразовать в любую другую. Привести общую задачу ЛП к каноническому виду можно воспользовавшись правилом: Необходимо ввести в каждое неравенство системы ограничений балансовую переменную:
В ЦФ балансовые переменные вводятся с коэффициентом 0, т.е. балансовые переменные не оказывают влияния на значение функции цели. Если в общей ЗЛП не на все управляемые переменные наложены условия неотрицательности , то , чтобы свести такую задачу к стандартной, для каждой переменной xj вводят две новые неотрицательные переменные uj ≥0, vj≥0 и полагают xj=uj-vj.
|
13.Детерминированная модель управления запасами (модель Уилсона). Определение оптимального размера заказа средствами дифференцированного исчисления. |
|
14.Геометрические интерпретации ЗЛП для случаев одной, двух или трех управляемых переменных. Примеры ЗЛП, имеющих единственное решение, множество решений, когда множество допустимых планов пусто, когда целевая функция неограниченно возрастает, когда допустимое множество не ограниченно, но решение задачи существует. Линейное программирование — раздел математического программирования. ЛП предполагает, что существует единственная целевая функция (ЦФ), которая линейна и, множество, на котором ищется экстремум ЦФ, задается системой ограничений в виде линейных равенств или неравенств. Общей задаче линейного программирования принято считать задачу вида: 1)Целевая функция: F(x)=Z(x1, x2,…xn)=c1x1+c2x2+…+cnxn= ->extr 2)xj – управляемые переменные 3)Система ограничений: a11x1 + a12x2 + ... + a1nxn ≤ b1, a21x1 + a22x2 + ... + a2nxn ≥ b2, ... ... ... ... ... ... ... ... ... ... ... . . am1x1 + am2x2 + ... + amnxn = bm, i=1,m; j=1,n и дополнительное ограничение неотрицательности управляемых переменных – xj>=0. aij, bi, cj –заданные действительные числа.
Геометрически интерпретировать ЗЛП можно только для случаев 2-х или 3-х управляемых переменных (n=2, n=3), в таком случае, для решения ЗЛП строится 2-мерная или 3-мерная Декартова система координат соответственно. Наиболее наглядна эта интерпретация для случая n =2, т.е. для случая двух переменных х1 и х2. Пусть нам задана задача линейного программирования в стандартной форме: с1х1+с2х2 → maх - Целевая функция - Система ограничений Для решения задачи нам необходимо построить систему координат: Так как в условии присутствуют ограничения x1 ≥ 0 и x2 ≥ 0, то для решения ЗЛП будет использоваться лишь 1-я четверть системы координат. Далее на плоскости необходимо изобразить систему ограничений, данную в задаче. Для этого ограничение типа неравенства мы превращаем в равенство: и строим это равенство на координатной плоскости. Напомню, чтобы построить равенство, необходимо провести прямую через 2 точки. Например, первую точку можно найти, подставив в равенство x1 = 0. Получаем уравнение с одной неизвестной и находим неизвестное значение х2. Аналогично находим вторую точку, подставив в равенство х2=0. Аналогичным образом мы строим все ограничения, приведенные в условии задачи. После построение граничных линий необходимо определить, какая часть плоскости удовлетворяет каждому неравенству системы ограничений. Для этого необходимо выбрать пробную точку, НЕ лежащую на граничной линии, и подставить её координаты в рассматриваемое неравенство. Если координаты пробной точки удовлетворяют неравенству, то часть плоскости, которой принадлежит пробная точка, является решением неравенства. Пересечение частей плоскости, соответствующих отдельным неравенством системы ограничений, дает множество допустимых планов. Не приводя строгих доказательств, укажем те случаи, которые тут могут получится. 1.Основной случай - получающаяся область имеет вид ограниченного выпуклого многоугольника 2.Неосновной случай - получается неограниченный выпуклый многоугольник, имеющий вид, подобный изображенному на рисунке.Например, система ограничений имеет вид: Построив соответствующие три прямых и выяснив подходящие полуплоскости, обнаруживаем, что множество планов – неограниченный многоугольник. То есть треугольник, одну из вершин которого «отправили в бесконечность». 3.Наконец, возможен случай, когда неравенства система ограничений противоречат друг другу, и допустимая область вообще пуста. Про такую задачу говорят, что множество допустимых планов пусто.Например, система ограничений имеет вид: Легко убедиться, что ни одной точки, которая удовлетворяла бы всем трем условиям, найти не удастся – ограничения противоречивы (множество планов пусто). Следующим этапом решения ЗЛП графическим методом является построение линий уровня функции цели.
Рассмотри функцию цели:
с1х1+с2х2 → maх
Легко догадаться, что прямая будет двигаться параллельно самой себе в том направлении, которое дается вектором (c1c2) , так как это - вектор нормали к нашей прямой и одновременно вектор градиента функции:
f(x1,x2) = c1x1+c2x2 Допустим, с1х1+с2х2 = L.
На рисунке изображено семейство линий уровня:
Увеличивая L, мы начнем двигать нашу прямую, и её пересечение с допустимой областью будет изменяться. В конце концов, эта прямая выйдет на границу допустимой области - как правило, это будет одна из вершин многоугольника. Дальнейшее увеличение L приведёт к тому, что пересечение прямой с1х1+с2х2 = L с допустимой областью будет пустым. Поэтому, то положение прямой с1х1+с2х2 = L, при котором она вышла на граничную точку допустимой области, и даст решение задачи, а соответствующее значение L и будет оптимальным значением целевой функции. Однако, бывают случаи, когда пересечение прямой с1х1+с2х2 = L с многоугольником системы ограничений происходит не в конкретной точке, а на всей прямой: В таком случае говорят, что ЗЛП имеет множество решений, и все решения расположены на прямой ВА. Множество планов может являться неограниченным. На рисунке показано, что построив градиент целевой функции, мы видим, что максимум достигается в вершине L, тогда как по минимуму функция не ограничена (минимум L(x, y)→ -∞). Этот пример свидетельствует, что в случае неограниченного множества планов может обнаружиться неограниченность L(x, y) по максимуму, минимуму или по обоим критериям. В данном случае, если необходимо найти максимум функции, то можно сказать что решение ЗЛП существует, даже когда допустимое множество неограниченно. Если же необходимо найти минимум функции, то при данных условиях задача решение иметь не будет. Если же прямоугольник решений имеет вид: и целевая функция: с1х+с2y → maх, то в таком случае говорят, что целевая функция неограниченно возрастает. |
15.Анализ чувствительности в ЛП. Суть графического метода анализа чувствительности. Геометрическая интерпретация активных и пассивных ограничений. На практике многие экономические параметры (цены на продукцию и сырье, запасы сырья, спрос на рынке, заработная плата и т.д.) с течением времени меняют свои значения. Поэтому оптимальное решение задачи ЛП, полученное для конкретной экономической ситуации, после ее изменения может оказаться непригодным или неоптимальным. В связи с этим возникает задача анализа чувствительности задачи ЛП, а именно того, как возможные изменения параметров исходной модели повлияют на полученное ранее оптимальное решение. Ограничения линейной модели классифицируются следующим образом: Связывающие (активные, лимитирующие) ограничения – такое ограничение, для которого значение левой части, вычисляемое в оптимальной точке, равно значению правой части. Связывающие ограничения проходят через оптимальную точку. Несвязывающие ограничения (пассивные, нелимитирующие) – ограничения, для которых оптимальные значения резерва или излишка являются положительными. Несвязывающие ограничения не проходят через оптимальную точку. Аналогично ресурс, представляемый связывающим ограничением, называют дефицитным, а ресурс, представляемый несвязывающим ограничением, – недефицитным. Ограничение называют избыточным в том случае, если его исключение не влияет на область допустимых решений и, следовательно, на оптимальное решение. Выделяют следующие три задачи анализа на чувствительность модели: 1. Анализ влияния
сокращения или увеличения 1) на сколько можно увеличить (ограничения типа ) или уменьшить (ограничения типа ) запас дефицитного ресурса для улучшения оптимального значения ЦФ? 2) на сколько можно уменьшить (ограничения типа ) или увеличить (ограничения типа ) запас недефицитного ресурса при сохранении полученного оптимального значения ЦФ? 2. Выявление ресурса, увеличение (уменьшение) запаса которого наиболее выгодно. 3. Анализ изменения целевых коэффициентов: каков диапазон изменения коэффициентов целевой функции, при котором не меняется оптимальное решение?
Графический анализ: Чтобы графически определить максимальное изменение запаса дефицитного ресурса, улучшающее оптимальное решение, необходимо передвигать соответствующую прямую в направлении улучшения ЦФ до тех пор, пока это ограничение не станет избыточным. Чтобы графически определить максимальное изменение запаса недефицитного ресурса, не меняющее оптимального решения, необходимо передвигать соответствующую прямую до пересечения с оптимальной точкой. Для того чтобы выяснить, запас какого из дефицитных ресурсов выгоднее увеличивать в первую очередь, необходимо определить, какую пользу (например, прибыль) принесет увеличение запасов каждого из них на единицу. Для этих целей вводится понятие ценности дополнительной единицы -го ресурса (теневая цена):
.
То есть сначала наращивается запас ресурса, имеющего максимальное значение , затем – второе по величине и т.д. Графический анализ изменения целевых коэффициентов (например, цен на производимую продукцию), не приводящих к изменению оптимального решения, проводится путем вращения линии ЦФ. При увеличении коэффициента ЦФ или уменьшении коэффициента целевая прямая на графике вращается вокруг оптимальной точки по часовой стрелке. Если уменьшается или же увеличивается , то целевая прямая вращается вокруг оптимальной точки против часовой стрелки. |