Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы...

^ Общая задачка оптимизации
Целью работы коммерческой компании является получение прибыли. Хоть какое управленческое решение (будь то решение о количестве приобретаемого продукта, либо решение о предназначении цены на реализуемый продукт, либо решение о подаче Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... рекламы в газету и т.д.) будет оказывать влияние на прибыль в огромную либо наименьшую сторону. Эти решения являются оптимизационными, другими словами всегда существует возможность избрать наилучшее решение из нескольких вероятных Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы.... Представим для себя, что все управленческие решения принимаются лучшим образом. Другими словами, все характеристики, на которые может оказывать влияние компания, являются хорошими. Тогда компания будет получать наивысшую прибыль (больше получить при данных критериях нереально Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы...). Для того чтоб найти, как управленческие решения, принимаемые работниками компании оптимальны, можно использовать способы математического программирования.

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

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

В общем виде математическая постановка задачки математического программирования состоит в определении большего либо меньшего значения мотивированной функции Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... f (х1, х2, ..., хn) при критериях gi(х1, х2, ..., хn)  bi; (i =1,2,…m), где f и gi; – данные функции, а bi – некие действительные числа.

задачки математического программирования делятся на задачки линейного и нелинейного программирования Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы.... если все функции f и gi линейные, то соответственная задачка является задачей линейного программирования. Если же хотя бы одна из обозначенных функций нелинейная, то соответственная задачка является задачей нелинейного программирования Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы....

В общем виде задачка линейного программирования (ЗЛП) ставится последующим образом:

Отыскать вектор , максимизирующий линейную форму

(1)

и удовлетворяющий условиям

(2)

(3)

Линейная функция именуется мотивированной функцией задачки. Условия (2) именуются многофункциональными, а (3) - прямыми ограничениями задачки.

Вектор , составляющие которого удовлетворяют Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... многофункциональным и прямым ограничениям задачки, будем именовать планом, либо допустимым решением ЗЛП.

Все допустимые решения образуют область определения задачки линейного программирования, либо область допустимых решений. Допустимое решение, максимизирующее мотивированную функцию f(x), именуется хорошим Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... планом задачки

,

где - наилучшее решение ЗЛП. Будем считать, что ЗЛП записана в канонической форме, если ее мотивированная функция максимизируется, ограничения имеют вид равенств с неотрицательной правой частью и все переменные неотрицательны Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы....

На практике отлично зарекомендовали себя последующие модели, относящиеся к оптимизационным: модели определения хорошей производственной программки, модели рационального смешивания компонент, рационального раскроя, рационального размещения компаний некой отрасли на определенной местности, модели формирования рационального Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... ранца ценных бумаг, модели транспортной задачки.

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

Более обычным и приятным способом линейного программирования (ЛП) является графический способ. Он применяется для решения задач ЛП с 2-мя переменными.

Разглядим Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... задачку ЛП в стандартной форме записи:



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

Каждое неравенство этой системы геометрически определяет полуплоскость с Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... граничной прямой ai1 x1 + ai2 x2 = bi , i=1,2,…m. Условия неотрицательности определяют полуплоскости, соответственно, с граничными прямыми x1=0,x2 =0. Система совместна, потому полуплоскости, как выпуклые огромного количества, пересекаясь, образуют общую часть Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы..., которая является выпуклым обилием и представляет собой совокупа точек, координаты каждой из которых являются решением данной системы. Совокупа этих точек именуют многоугольником решений. Он может быть точкой, отрезком, лучом, многоугольником, неограниченной Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... многоугольной областью.

Таким макаром, геометрически задачка линейного программирования (ЗЛП) представляет собой отыскание таковой точки многоугольника решений, координаты которой доставляют линейной функции цели наибольшее (малое) значение, при этом допустимыми решениями являются все точки многоугольника Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... решений.

Линейное уравнение обрисовывает огромное количество точек, лежащих на одной прямой. Линейное неравенство обрисовывает некую область на плоскости. Определим, какую часть плоскости обрисовывает неравенство 2х1+3х2 12. Во-1-х, построим прямую 2х Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы...1+3х2=12. Эта ровная проходит через точки (6, 0) и (0, 4). Для того чтоб найти, какая полуплоскость удовлетворяет неравенству нужно избрать всякую точку на графике, не принадлежащую прямой, и подставить ее координаты в неравенство. Если неравенство будет производиться, то Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... данная точка является допустимым решением и полуплоскость, содержащая точку, удовлетворяет

неравенству. Комфортной для использования при подстановке в неравенство является начало координат. Подставим х1=х2=0 в неравенство 2х1+3х212. Получим 20+3012. Данное утверждение Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... является верным, как следует, неравенству 2х1+3х212 соответствует нижняя полуплоскость, содержащая точку (0.0). Это отражено на графике, изображенном на рис.1.






Рис. 1. Неравенству 2х1+3х212 соответствует нижняя полуплоскость.


Аналогично можно изобразить графически каждое ограничение Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... задачки линейного программирования.

Решением каждого неравенства системы ограничений ЗЛП является полуплоскость, содержащая граничную прямую и расположенная по одну сторону от нее. Скрещение полуплоскостей, любая из которых определяется подходящим неравенством системы, именуется областью Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... допустимых решений либо областью определения. Нужно держать в голове, что область допустимых решений удовлетворяет

.

условиям неотрицательности (xj 0, j=1,…,n). Координаты хоть какой точки, принадлежащей области определения являются допустимым решением задачки.

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


.

Этот вектор указывает направление наискорейшего конфигурации це­левой функции. Ровная Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... , перпендикулярная вектору–градиенту, является линией уровня мотивированной функции. В хоть какой точке полосы уровня мотивированная функция воспринимает одно и то же значение. Приравняем мотивированную функцию неизменной величине “a”. Меняя значение “a Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы...”, получим семейство параллельных прямых, любая из которых является линией уровня.

Принципиальное свойство полосы уровня линейной функции заключается в том, что при параллельном смещении полосы в одну сторону уровень только растет, а при смещении в Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... другую сторону – убывает.

С геометрической точки зрения в задачке линейного программирования ищется такая угловая точка либо набор точек из допустимого огромного количества решений, на котором достигается самая верхняя (нижняя) линия уровня Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы..., расположенная далее (поближе) других в направлении наискорейшего роста.

Графический способ решения ЗЛП состоит из последующих шагов.

  1. Строится многоугольная область допустимых решений ЗЛП – ОДР,

  2. Строится вектор-градиент ЦФ в какой-либо точке Х Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы...0 принадлежащей ОДР –

.

3. Линия уровня C1x1+C2x2 = а (а–неизменная величина) - ровная, перпендикулярная вектору –градиенту – передвигается в направлении этого вектора в случае максимизации f(x1,x2) до того времени, пока не покинет Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... пределов ОДР. Предельная точка (либо точки) области при всем этом движении и является точкой максимума f(x1,x2).

4. Для нахождения ее координат довольно решить два уравнения прямых, получаемых из соответственных Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... ограничений и дающих в скрещении точку максимума. Значение f(x1,x2), отысканное в получаемой точке, является наибольшим.

При минимизации f(x1,x2) линия уровня перемещается в направлении, обратном вектору-градиенту. Если ровная при Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... собственном движении не покидает ОДР, то соответственный максимум либо минимум f(x1,x2) не существует.

Если линия уровня параллельна какому-либо многофункциональному ограничению задачки, то наилучшее значение ЦФ будет достигаться Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... в хоть какой точке этого ограничения, лежащей меж 2-мя хорошими угловыми точками, и, соответственно, неважно какая из этих точек является хорошим решением ЗЛП.

Разглядим графическое решение задач линейного программирования на последующем примере.

Задачка 1. о Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... планировании выпуска продукции пошивоч­ному предприятию. (Задачка о костюмчиках).

Намечается выпуск 2-ух видов костюмов - мужских и дамских. На дамский костюмчик требуется 1 м шерсти, 2 м лавсана и 1 человеко-день трудозатрат. На мужской костюмчик Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... - 3,5 м шерсти, 0,5 м лавсана и 1 человеко-день трудозатрат. Всего имеется 350 м шерсти, 240 м лавсана и 150 человеко-дней трудозатрат. Tребуется найти, сколько костюмов каждого вида нужно сшить, чтоб обеспечить наивысшую прибыль, если прибыль Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... от реализации дамского костюмчика составляет 10 валютных единиц, а от мужского - 20 валютных единиц. При всем этом следует подразумевать, что нужно сшить более 60 мужских костюмов.

Модель задачки.

Введем последующие обозначения: х1 - число дамских Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... костюмов; x2 - число мужских костюмов.

Прибыль от реализации дамских костюмов составляет 10х1, а от реализации мужских 20х2, т.е. нужно максимизировать мотивированную функцию

f(x) = 10 х1 + 20 х2 -> max.

Ограничения задачки имеют вид:

х1 + х Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы...2  150

2 х1 + 0.5 х2  240

х1 + 3.5 х2  350

х2 60

х1  0

1-ое ограничение по труду х1 + х2  150. Ровная х1 + х2 = 150 проходит через точки (150, 0) и (0, 150).

Р
ис. 2. Решением первого неравенства является нижняя полуплоскость.


2-ое ограничение по лавсану Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... 2 х1 + 0.5 х2  240. Ровная 2 х1 + 0.5 х2 = 240 проходит через точки (120, 0) и (0, 480). Третье ограничение по шерсти х1 + 3.5 х2  350. Добавим 4-ое ограничение по количеству мужских костюмов х2  60. Решением этого неравенства является полуплоскость, лежащая выше прямой х2 = 60. На Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... рис.3. заштрихована область допустимых решений.


Рис. 3. Заштрихована область допустимых решений.


Д
ля определения направления движения к оп­тимуму построим вектор-градиент , координаты которого являются личными производными мотивированной функции, т.е. = (10;20).

Что бы выстроить Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... этот вектор, необходимо соединить точку (10;20) с началом координат. При макси­мизации мотивированной функции нужно двигаться в направ­лении вектора-градиента, а при минимизации — в противо­положном направлении. Для удобства можно строить век­тор Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы..., пропорциональный вектору . Так, на рис. 2.1.6. изобра­жен вектор градиент (30;60).

В нашем случае движение полосы уровня будем осущест­влять до ее выхода из области допустимых решений. в последней, угловой точке достигается максимум мотивированной функции Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы.... Для нахождения координат этой точки довольно решить два уравнения прямых, получаемых из соответственных ограничений и дающих в скрещении точку максимума: х1 + 3.5 х2 = 350

х1 + х2 = 150 .

Отсюда лег­ко записать решение Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... начальной ЗЛП: max f(x) = 2300 и дости­гается при x1=70 и x2=80 (рис. 4.)

Р
ис.4. Максимум мотивированной функции достигается в точке (70, 80).




Задачка 2. Для производства 2-ух видов продукции А1 и А2 употребляют три вида ресурсов S Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы...1, S2, S3, припасы которых составляют  и  усл.ед. Расход ресурсов на  ед. продукции приведен в таблице:

^ Виды ресурсов

Припасы ресурсов

Расходы ресурсов на 1 изд.







А1

А2
S1






S2







S3









Прибыль
 руб.

 руб.

Нужно составить таковой Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... план производства продукции, который обеспечит самую большую прибыль от ее реализации.

Составим экономико-математическую модель (ЭММ) задачки.

Пусть нужно выпустить изделий A1 - x1 шт., а изделий А2 - x2 шт. Тогда прибыль Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... F = 2x1 + 3x2 max

xx



xx



x



x

x

Решим задачку графически.



xx







xx 







к.т. <в) – заходит




2)

2xx







2xx 







к.т.  <в) – заходит




3)

x







xxниже прямой




4)

x1правее Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... ОX




5)

x2выше ОX1




Линия уровня

F xx F 




xx 




q показывает направление возрастания F.



max F достигается в т. С

т.С

xx 



xx 



 x 



xx 

xx Общая задача оптимизации - Краткий конспект лекций и лабораторная работа №1 по курсу «Экономико-математические методы... 

xx 
























x 
















x


















Таким макаром, нужно выпустить xшт. изделий А1, x2шт. изделий А2, чтоб получить max F ден.ед.




obshegorodskaya-dobrovolcheskaya-akciya.html
obshegumanitarnie-disciplini.html
obshehozyajstvennij-i-sinergicheskij-effekt.html