Невозможно отобразить презентацию
mathematicsSimilar presentations:
ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
ИССЛЕДОВАНИЕ ОПЕРАЦИЙ.
Финансовый Университет при Правительстве РФ Кафедра «Прикладная математика».
Попов Виктор Юрьевич Лекция3.
Выпуклые множества вRn Определение.
МножествоМ Rn называется выпуклым , еслиА ,ВМ => s A + (1-s)BМ,s [0;1].MAB Выпуклое множествоMAB МножествоM не является выпуклым Примеры выпуклых множеств.
Примеры не выпуклых множеств.
Полупространства, выпуклые многогранные области.
Определение.
Полупространством вRn называется множество всех точек{X= (x1,x2,..xn):а1х1+а2х2 +...+аnхn+а00}а1,а2 ,...аn,а0 — заданы,а12+а2 +…+аn20.
Теорема.
полупространствоП вRn есть выпуклое множество.
Доказательство.
ПустьП:а1х1+а2х2 +...+аnхn+а0 0 (*).
РассмотримХ=(х1,х2 ,...хn),Y=(y1,y2 ,...yn) П (*).
Докажем, что еслиZ[X,Y], то ZП.Z[X,Y ] =>Z=sX +(1-s)Y,s [0,1].z1=sх1 +(1-s)y1 ,… ,zn=sхn +(1-s)yn Подставим в (*)а1(sх1 +(1-s)y1 )+...+аn (sхn +(1-s)yn )+b==s(а1х1 +...+аnхn+b)+ +(1-s)(а1y1 +...+аnyn+b)=( 0)+( 0)=>0==>ZП Лемма.
Пересечение нескольких выпуклых множеств есть выпуклое множество.LMNBA Доказательство.
Пусть М = L N, где L, N выпуклы.
Пусть А M и B М => A L и BL.
L выпуклое => [А,В] L.
Пусть А M и B М => A N и BN.
N выпуклое => [А,В] N.
=> [А,В] М => М - выпуклое.
Следствие.
Пересечение нескольких полупространств вRn - выпуклое множество.
Определение.
ПересечениеМ нескольких полупространств вRn называется выпуклой многогранной областью вRn.
Выпуклая многогранная область в Rn задается системой линейных неравенств.ВR2 вместо «многогранные» говорят «многоугольные».
Замечание.
плоскость вRn есть выпуклое множество.
а1х1+а2х2 +...+аnхn +b=0 <==>а1х1+а2х2 +...+аnхn+b0,а1х1+а2х2 +...+аnхn+b0.
Точка называется внутренней для множества, если она принадлежит этому множеству вместе с некоторой окрестностью.
Точки множества.
Точка называется граничной для множества, если ее окрестность содержит точки как принадлежащие, так и не принадлежащие этому множеству.
Множество называется замкнутым, если оно содержит все свои граничные точки.
Множество называется открытым, если все его точки- внутренние.
Множество называется ограниченным, если оно содержится внутри сферы (параллелепипеда) конечного радиуса (конечного объема).
Определение.
Ограниченная выпуклая многогранная областьMRn называется выпуклым многогранником вRn.
Угловые точки выпуклых многогранных областей Определение.
ТочкаС выпуклой многогранной областиMRn называется вершиной, или угловой точкой области М , если НЕ представленияС в видеC=sA +(1-s)B , гдеAМ,BМ и 0<s<1.
Пусть областьMRn задана с помощью системыk линейных неравенств (k>n ).
Выберем какие-либоn из этих неравенств и заменим их равенствами.
Если эта система имеет единственное решениеX , причемXM , тоX -вершина множестваM.
Таким путем могут быть получены все вершиныM.
Примечание Необходимо решитьCnk=n!/k!(n-k )! систем линейных уравнений Выпуклая оболочка системы точек вRn.
Определение.
ПустьА1,А2 ,...,Аp — некоторый набор точек изRn.
точкаА :A= s1А1+s2А2 +...+spАp, гдеsi0,s1+s2 +...+sp =1, называется выпуклой линейной комбинацией точекА1,А2 , ...,Аp.
Определение.
Множество всех выпуклых линейных комбинаций точекА1,А2 , ...,Аp называется выпуклой оболочкой системы точекА1,А2 , ...,Аp и обозначается <А1,А2 , ...,Аp> (другое обозначение: conv(А1,А2 ,...,Аp) от английского «convex» — выпуклый).
Теорема.
МножествоL= <А1,А2 ,...,Аp> есть наименьшее из всех выпуклых множеств, содержащих точкиА1,А2 , ...,Аp.
Доказательство.
Нам необходимо доказать три утверждения:1.L содержит каждую из точекА1,А2 , ...,Аp.2.
L выпукло.
3.
Каково бы ни было выпуклое множествоМ, содержащее каждую из точекА1,А2 , ...,Аp, справедливо включениеLМ.1.А1=1·А1 +0 ·А2 +...+0 ·Аp=>А1L, аналогичноА2 L, ...,АзL.
2.
Пусть p=3, т.е.А1,А2,А3.
ПустьВ иСL:B=s1А1+s2А2+s3А3,si0,s1+s2+s3=1,C=t1А1+t2А2+t3А3 , ti0,t1+t2+t3=1 точкаХ[ ВС ] имеет вид X= s B +tС , где s, t 0 , s + t = 1 => X=s (s1А1 + s2А2+ s3А3)+ t (t1А1+ t2А2+t3А3)= =(ss1+tt1 ) А1 + (ss2+tt2)А2 +(ss3+tt3)А3.
Коэффициенты приА1,А2,А3 (…) 0, а их сумма = (s s1 +t t1 ) + (s s2 +t t2 ) + (s s3 + t t3 ) = = s (s1+ s2+ s3 ) +t (t1+ t2+t3 )= s + t = 1.=>Х L => L - выпукло.
3.
p=3.
Пусть М— какое-либо выпуклое множество , содержащее каждую из точек А1 , А2 , А3.
Рассмотрим точкуL:s1А1+ s2А2+s3А3, si 0, s1+s2+s3=1.
=> s1А1+ s2А2==(s1+s2)(s1А1/(s1+s2 )+ s2А2/(s1+s2)).
Точка B= s1А1/(s1+s2 )+ s2А2/(s1+s2)[А1А2 ].
Так какМ выпуклое множество=>ВМ.s1А1+ s2А2+s3А3=(s1+s2 )B+s3А3==(s1+s2+s3 ) ( (s1+s2 )B/(s1+s2+s3 )+ +s3А3/(s1+s2+s3 ) )=C.
где точкаС[ВА3 ] =>СМ.=> выпуклая линейная комбинация точек А1 , А2 , А3 М =>LМ.
Теорема точка многоугольника является выпуклой линейной комбинацией его угловых точек.1A2A3AkApAMN M = t А1 + s N;
s ,t 0, s + t = 1.
N= p А2 + q А3 ;
p, q 0, p + q =1.М = t А1+ s p А2 + s q А3= tА1+lА2 +m А3t,l, m 0 и t + l + m = 1.
M= t А1+lА2 +m А3 + 0 А4 +...
+0 Аp.
Экстремальные значения линейной функции на выпуклой многогранной области.
Теорема Линейная функция достигает экстремума в угловой точке выпуклого множества;
причем, если линейная функция достигает экстремума в нескольких угловых точках выпуклого многогранного множества , она также достигает экстремума в любой выпуклой линейной комбинации этих точек.
1.Пусть X* - точка экстремума, тогда Z(X*) > Z(X)XG.
ПустьX* не является угловой точкой.
Тогда X*=k1X1+k2X2 +...+knXn, ki0,k1+k2 +..+kn =1, где Xi- угловые точкиG.
Найдем Z(X*) = СХ* ==Ck1X1 +C k2X2 +...+C knXn == k1CX1 + k2CX2 +...+ knCXn ==k1Z(X1 )+ k2Z(X2 )+...+ knZ(Xn ) ПустьmaxZ(Xj ) =Z(Xk).=>Z (X*)k1Z(Xk)+k2Z(Xk )+...+knZ(Xk)=Z(Xk)(k1+k2 +..+kn )=Z(Xk).
Противоречие! X* — экстремальное решение и в задаче на максимум Z(X*) > Z(X)XG.
=> X* является угловой точкой выпуклой области допустимых решений G.
Пусть угловые точки выпуклой области X1 , X2 , …, Xp являются экстремальными решениями , т.е.Z(X1) =Z(X2 ) = ...
=Z(Xp)иZ(X1 ) > Z(X)XG.
X*= k1X1+k2X2 +...+kpXp, ki0 , k1+k2 +..+kp =1 ;
Z(X*) = СХ* ==Ck1X1 +C k2X2 +...+C kpXp == k1CX1 + k2CX2 +...+ kpCXp ==k1Z(X1 )+ k2Z(X2 )+...+ kpZ(Xp )=Z(X1)(k1+k2 +..+kp )=Z(X1).
решениеX* также является оптимальным.
ОБЩАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯМ атематическое программирование — это раздел высшей математики, посвященный решению экстремальных задач для функций нескольких переменных при наличии ограничений на переменные.
Определение Математические методы исследования операций линейное нелинейное динамическое стохастическое теория игр Математическое программирование теория массового обслуживания теория управления запасами История Математическое программирование возникло в 30-е годы XX века.
Венгерский математик Б.
Эгервари в 1931 году решил задачу, называемую проблемой выбора.
Американский ученый Г.У.
Кун обобщил этот метод, после чего он стал называться« венгерским » методом.
В 1939 году российский ученый Л.В.
Канторович разработал метод разрешающих множителей решения задач линейного программирования.
В 1947 году американский ученый Дж.
Данциг описал один из основных методов решения задач линейного программирования – симплекс- метод.
1)выбор переменных задачи;
2) составление системы ограничений;
3) выбор целевой функции.
Построение математической модели экономической задачи Переменные задачи - величиныХ= (х1,х2 ,...хn), характеризующие экономический процесс.
Система ограничений - система уравнений и неравенств, которым удовлетворяют переменные задачи .
Следует из экономических условий.
Целевая функция - функция переменных задачи, экстремум которой требуется найти.
Если целевая функция и система ограничений линейны , то задача математического программирования называется задачей линейного программирования (ЗЛП).
Формулировка ЗЛП.
min(max)...01cxcxczn,....,...,...212221211212111mnmnmnbxaxaxabxaxaxabxaxaxa означает " " , " " или "=".0 ...,,0,021nx:RnX МножествоХ называется допустимым или областью допустимых решений (ОДР)Xxn);(21 допустимое решение Функцияz - целевая функция.
(min)max)(xz.);(21Xxn min(max):*xzXx оптимальное решение Каноническая форма ЗЛП min(max)...01cxcxczn,....,...,...212221211212111mnmnmnbxaxaxabxaxaxabxaxaxa0 ...,,0,021nx:RnX Стандартная форма ЗЛП min(max)...01cxcxczn,....,...,...212221211212111mnmnmnbxaxaxabxaxaxabxaxaxa означает " " или "".0 ...,,0,021nx:RnX Матричная форма ЗЛП min(max)0cXCXzTBAX0Xnx ...,,21 Если то ЗЛП называется целочисленной целые числа, ЗЛП может быть сведена как к канонической, так и к стандартной форме.
Стандартная=>каноническаяininibxaxaxa...)121:0iyininibyxaxaxa...21ininibxaxaxa...)21:0iyininibyxaxaxa...21~)3jx:0,0jxjx Каноническая=>cтандартная 1) Выделить базисные и свободные переменные;
2) Выразить базисные через свободные;
3) Подставить в неравенства для базисных переменных и целевую функцию;
Примерmin31721354321xz0,149352354321431531321xmin109355231xz0,041039023531314315312x Примеры ЗЛП 1) Задача оптимального использования ресурсов.aij(i =1,2,...,m;j =1,2,...,n ) — расходi -го pecypса на производство единицыj-й продукции.P1,P2 ,...Pn — виды продукции.S1,S2 , ...Sm— ресурсыB=(b1,b2 , ...bm ) — объемы ( запасы) ресурсовС=(c1,c2 , ...cn ) — прибыль от реализации единицы продукции.X=(x1,x2 , ...xn ) — объемы производства продукции.maxTCXXzTBAX0X 2) Задача о составлении рациона питания (о диете).aij(i =1,2,...,m;j =1,2,...,n ) — содержаниеi -го вещества в единицеj -го продукта .P1,P2 ,...Pn — продукты питания.S1,S2 , ...Sm— полезные веществаB=(b1,b2 , ...bm ) — мин.
сут.
потребностьС=(c1,c2 , ...cn ) — цена единицы продукта.X=(x1,x2 , ...xn ) — количество продуктов.minTCXXzTBAX0X 3) Транспортная задачаA1,A2 , ...Am— поставщикиa1,a2 , ...am — запасы однородного грузаmia1— суммарный запас грузаB1,B2 , ...Bn— потребителиb1,b2 ,...bn— потребностиnjb1— суммарная потребностьcij — стоимость перевозки единицы грузаAiВj — транспортный тариф.
Потребители Поставщики1B2B…jB…nB Запасы1A11xc12xc…jxc1…nxc1a2A21xc22xc…jxc2…nxc2a … … … … … … … …iA1ixc2ixc…ijxc…inxcia … … … … … … … …mA1mxc2mxc…mjxc…mnxcma Потребности1b2b…jb…nb Транспортная таблицаminjijxcXz11min)(njbxjmiij,1,1miaxinjij,1,1.,1;,10njmixij 1.
Доставка необходимого количества груза в каждый пункт назначения;
2.
Вывоз имеющегося груза из всех пунктов отправления;
3.
Исключение обратных перевозок 4) Задача о назначенияхA1,A2 , ...Am— работники : каждый может выполнять одну работуBj , из работ:B1,B2 , ...Bn.cij — производительность труда работникаАi , на рабочем местеBj Кого и куда назначить , чтобы добиться максимальной производительности труда? Каждый работник может быть назначен только на одну работу.xij — назначениеi -го работника на j-ю работу.xij = 1, еслиi -й работник назначается на яj-ю работу;xij = 0, если не назначается.
При назначенииi -го работника наj -ю работу производительность равнаcijxij.minjijxcXz11max)(njxmiij,1,1mixnjij,1,1.,1;,10njmixij 5) Составление оптимального портфеля ценных бумаг (задача о банке).
Пусть инвестирование денежных средств сопровождается получением ценных бумаг( активов): акций, облигаций, валюты, векселей.
Если денежные средства вложены в несколько объектов, полученные от инвестирования ценные бумаги образуют портфель активов.
Доходность портфеля характеризуется средневзвешенной доходностью его составляющих.
Для портфеля из двух активов:D=WaDa+WbDb, где D — общая доходность портфеля;Wa — удельный вес актива А;Da — доходность актива А;Wb — удельный вес актива В,Db - доходность актива В.
Риск— количественная мера неопределенности будущей стоимость ценных бумаг.Ai, (i = 1...m ) — активы;
Di — ожидаемые доходы;
Wi — доли каждого актива в портфеле— управляемые переменные;
R — риск портфеля — средневзвешенная величина рисков активов ri Оптимальные Wi — максимальный ожидаемый доход при условии заданного макс.
уровня риска.
Ограничения: 1) риск портфеля R Rmax 2) в каждый актив обязательно должны быть проведены положительные инвестиции;
3) все средства должны быть полностью инвестированы.miDWD1max1RrWRmi1miWmiWi,2,10 ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Задача с двумя переменнымиminmax21xcxcz,.,212221211212111mbxaxabxaxabxaxa0,021x Пусть система ограничений совместна , т.е.
имеет решение , а многоугольник ее решений( ОДР) ограничен.
Каждое из неравенств определяет полуплоскость с границейаi1х1+аi2x2=bi,i =1, 2, ...,n илих1=0,x2=0.
Представим этот многоугольник на плоскости Ох1x2.2x1xABCDE021,cNmaxmin Линейная функция при фиксированныхz является уравнением семейства | | прямых21xcxcz constxcxc21 -линии уровняz(X) вектор нормали к линиям уровня21,cN Линия уровня, имеющая общие точки с ОДР и расположенная так, что ОДР целиком находится в одной из полуплоскостей , называется опорной прямой.
Теорема.
Значения целевой функции в точках линии уровня увеличиваются , если линию уровня перемещать параллельно начальному положению в направлении вектора нормали , и уменьшаются при перемещении в против вектора нормали.2x1x21,xMn0'2'1,xP ДоказательствоABCD ПустьZ(X) =c1x1 +с2x2 — целевая функция.21,cn нормаль из начала координатnCDnABCDAB,|| линии уровняnPMCDxMABxP||:,21'2'121'2'1,xOMxOPOMnxcxcMZ,21PMnOPnPMOPn,PZnPMPZnPMnPZ,1,1 Алгоритм решения задачи линейного программирования с двумя переменными графическим методом 1.
Строится ОДР.
2.
Из начала координат строится вектор нормали N=(c1,c2).3.
Перпендикулярно векторуN проводится линия уровняc1x1+с2x2 =0, проходящая через начало координат.4.
Линия уровня перемещается до положения опорной прямой, на которой будет находиться максимум или минимум функции.
В зависимости от вида ОДР и целевой функции z(X) ЗЛП имеет единственное решение2x1xABCDE021,cNmax имеет∞ много решений2x1xABCDE021,cN не имеет ни одного оптимального решения2x1xAB021,cN Графическим методом можно решать ЗЛП в канонической форме приn-r 2 где n — число неизвестных;
r — ранг матрицы системы.
Если уравнения системы ограничений линейно независимы, тоr = m — числу уравнений.
Теорема.
ОДР ЗЛП— выпуклое множество.
Опорное решение ЗЛП и его взаимосвязь с угловыми точками Столбцы матрицы ограничений канонического вида ЗЛП называются векторами условий.
Опорным решением ЗЛП называется такое допустимое решениеX(x10, x20 ,..., xm0, 0, ..., 0), для которого векторы условий соответствующие положительным координатам линейно независимы.
Базисом опорного решения называется базис системы векторов условий ЗЛП, в состав которого входят векторы, соответствующие отличным от нуля координатам опорного решения.
Теорема.
опорное решение является угловой точкой ОДР.
Теорема.
угловая точка ОДР является
Финансовый Университет при Правительстве РФ Кафедра «Прикладная математика».
Попов Виктор Юрьевич Лекция3.
Выпуклые множества вRn Определение.
МножествоМ Rn называется выпуклым , еслиА ,ВМ => s A + (1-s)BМ,s [0;1].MAB Выпуклое множествоMAB МножествоM не является выпуклым Примеры выпуклых множеств.
Примеры не выпуклых множеств.
Полупространства, выпуклые многогранные области.
Определение.
Полупространством вRn называется множество всех точек{X= (x1,x2,..xn):а1х1+а2х2 +...+аnхn+а00}а1,а2 ,...аn,а0 — заданы,а12+а2 +…+аn20.
Теорема.
полупространствоП вRn есть выпуклое множество.
Доказательство.
ПустьП:а1х1+а2х2 +...+аnхn+а0 0 (*).
РассмотримХ=(х1,х2 ,...хn),Y=(y1,y2 ,...yn) П (*).
Докажем, что еслиZ[X,Y], то ZП.Z[X,Y ] =>Z=sX +(1-s)Y,s [0,1].z1=sх1 +(1-s)y1 ,… ,zn=sхn +(1-s)yn Подставим в (*)а1(sх1 +(1-s)y1 )+...+аn (sхn +(1-s)yn )+b==s(а1х1 +...+аnхn+b)+ +(1-s)(а1y1 +...+аnyn+b)=( 0)+( 0)=>0==>ZП Лемма.
Пересечение нескольких выпуклых множеств есть выпуклое множество.LMNBA Доказательство.
Пусть М = L N, где L, N выпуклы.
Пусть А M и B М => A L и BL.
L выпуклое => [А,В] L.
Пусть А M и B М => A N и BN.
N выпуклое => [А,В] N.
=> [А,В] М => М - выпуклое.
Следствие.
Пересечение нескольких полупространств вRn - выпуклое множество.
Определение.
ПересечениеМ нескольких полупространств вRn называется выпуклой многогранной областью вRn.
Выпуклая многогранная область в Rn задается системой линейных неравенств.ВR2 вместо «многогранные» говорят «многоугольные».
Замечание.
плоскость вRn есть выпуклое множество.
а1х1+а2х2 +...+аnхn +b=0 <==>а1х1+а2х2 +...+аnхn+b0,а1х1+а2х2 +...+аnхn+b0.
Точка называется внутренней для множества, если она принадлежит этому множеству вместе с некоторой окрестностью.
Точки множества.
Точка называется граничной для множества, если ее окрестность содержит точки как принадлежащие, так и не принадлежащие этому множеству.
Множество называется замкнутым, если оно содержит все свои граничные точки.
Множество называется открытым, если все его точки- внутренние.
Множество называется ограниченным, если оно содержится внутри сферы (параллелепипеда) конечного радиуса (конечного объема).
Определение.
Ограниченная выпуклая многогранная областьMRn называется выпуклым многогранником вRn.
Угловые точки выпуклых многогранных областей Определение.
ТочкаС выпуклой многогранной областиMRn называется вершиной, или угловой точкой области М , если НЕ представленияС в видеC=sA +(1-s)B , гдеAМ,BМ и 0<s<1.
Пусть областьMRn задана с помощью системыk линейных неравенств (k>n ).
Выберем какие-либоn из этих неравенств и заменим их равенствами.
Если эта система имеет единственное решениеX , причемXM , тоX -вершина множестваM.
Таким путем могут быть получены все вершиныM.
Примечание Необходимо решитьCnk=n!/k!(n-k )! систем линейных уравнений Выпуклая оболочка системы точек вRn.
Определение.
ПустьА1,А2 ,...,Аp — некоторый набор точек изRn.
точкаА :A= s1А1+s2А2 +...+spАp, гдеsi0,s1+s2 +...+sp =1, называется выпуклой линейной комбинацией точекА1,А2 , ...,Аp.
Определение.
Множество всех выпуклых линейных комбинаций точекА1,А2 , ...,Аp называется выпуклой оболочкой системы точекА1,А2 , ...,Аp и обозначается <А1,А2 , ...,Аp> (другое обозначение: conv(А1,А2 ,...,Аp) от английского «convex» — выпуклый).
Теорема.
МножествоL= <А1,А2 ,...,Аp> есть наименьшее из всех выпуклых множеств, содержащих точкиА1,А2 , ...,Аp.
Доказательство.
Нам необходимо доказать три утверждения:1.L содержит каждую из точекА1,А2 , ...,Аp.2.
L выпукло.
3.
Каково бы ни было выпуклое множествоМ, содержащее каждую из точекА1,А2 , ...,Аp, справедливо включениеLМ.1.А1=1·А1 +0 ·А2 +...+0 ·Аp=>А1L, аналогичноА2 L, ...,АзL.
2.
Пусть p=3, т.е.А1,А2,А3.
ПустьВ иСL:B=s1А1+s2А2+s3А3,si0,s1+s2+s3=1,C=t1А1+t2А2+t3А3 , ti0,t1+t2+t3=1 точкаХ[ ВС ] имеет вид X= s B +tС , где s, t 0 , s + t = 1 => X=s (s1А1 + s2А2+ s3А3)+ t (t1А1+ t2А2+t3А3)= =(ss1+tt1 ) А1 + (ss2+tt2)А2 +(ss3+tt3)А3.
Коэффициенты приА1,А2,А3 (…) 0, а их сумма = (s s1 +t t1 ) + (s s2 +t t2 ) + (s s3 + t t3 ) = = s (s1+ s2+ s3 ) +t (t1+ t2+t3 )= s + t = 1.=>Х L => L - выпукло.
3.
p=3.
Пусть М— какое-либо выпуклое множество , содержащее каждую из точек А1 , А2 , А3.
Рассмотрим точкуL:s1А1+ s2А2+s3А3, si 0, s1+s2+s3=1.
=> s1А1+ s2А2==(s1+s2)(s1А1/(s1+s2 )+ s2А2/(s1+s2)).
Точка B= s1А1/(s1+s2 )+ s2А2/(s1+s2)[А1А2 ].
Так какМ выпуклое множество=>ВМ.s1А1+ s2А2+s3А3=(s1+s2 )B+s3А3==(s1+s2+s3 ) ( (s1+s2 )B/(s1+s2+s3 )+ +s3А3/(s1+s2+s3 ) )=C.
где точкаС[ВА3 ] =>СМ.=> выпуклая линейная комбинация точек А1 , А2 , А3 М =>LМ.
Теорема точка многоугольника является выпуклой линейной комбинацией его угловых точек.1A2A3AkApAMN M = t А1 + s N;
s ,t 0, s + t = 1.
N= p А2 + q А3 ;
p, q 0, p + q =1.М = t А1+ s p А2 + s q А3= tА1+lА2 +m А3t,l, m 0 и t + l + m = 1.
M= t А1+lА2 +m А3 + 0 А4 +...
+0 Аp.
Экстремальные значения линейной функции на выпуклой многогранной области.
Теорема Линейная функция достигает экстремума в угловой точке выпуклого множества;
причем, если линейная функция достигает экстремума в нескольких угловых точках выпуклого многогранного множества , она также достигает экстремума в любой выпуклой линейной комбинации этих точек.
1.Пусть X* - точка экстремума, тогда Z(X*) > Z(X)XG.
ПустьX* не является угловой точкой.
Тогда X*=k1X1+k2X2 +...+knXn, ki0,k1+k2 +..+kn =1, где Xi- угловые точкиG.
Найдем Z(X*) = СХ* ==Ck1X1 +C k2X2 +...+C knXn == k1CX1 + k2CX2 +...+ knCXn ==k1Z(X1 )+ k2Z(X2 )+...+ knZ(Xn ) ПустьmaxZ(Xj ) =Z(Xk).=>Z (X*)k1Z(Xk)+k2Z(Xk )+...+knZ(Xk)=Z(Xk)(k1+k2 +..+kn )=Z(Xk).
Противоречие! X* — экстремальное решение и в задаче на максимум Z(X*) > Z(X)XG.
=> X* является угловой точкой выпуклой области допустимых решений G.
Пусть угловые точки выпуклой области X1 , X2 , …, Xp являются экстремальными решениями , т.е.Z(X1) =Z(X2 ) = ...
=Z(Xp)иZ(X1 ) > Z(X)XG.
X*= k1X1+k2X2 +...+kpXp, ki0 , k1+k2 +..+kp =1 ;
Z(X*) = СХ* ==Ck1X1 +C k2X2 +...+C kpXp == k1CX1 + k2CX2 +...+ kpCXp ==k1Z(X1 )+ k2Z(X2 )+...+ kpZ(Xp )=Z(X1)(k1+k2 +..+kp )=Z(X1).
решениеX* также является оптимальным.
ОБЩАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯМ атематическое программирование — это раздел высшей математики, посвященный решению экстремальных задач для функций нескольких переменных при наличии ограничений на переменные.
Определение Математические методы исследования операций линейное нелинейное динамическое стохастическое теория игр Математическое программирование теория массового обслуживания теория управления запасами История Математическое программирование возникло в 30-е годы XX века.
Венгерский математик Б.
Эгервари в 1931 году решил задачу, называемую проблемой выбора.
Американский ученый Г.У.
Кун обобщил этот метод, после чего он стал называться« венгерским » методом.
В 1939 году российский ученый Л.В.
Канторович разработал метод разрешающих множителей решения задач линейного программирования.
В 1947 году американский ученый Дж.
Данциг описал один из основных методов решения задач линейного программирования – симплекс- метод.
1)выбор переменных задачи;
2) составление системы ограничений;
3) выбор целевой функции.
Построение математической модели экономической задачи Переменные задачи - величиныХ= (х1,х2 ,...хn), характеризующие экономический процесс.
Система ограничений - система уравнений и неравенств, которым удовлетворяют переменные задачи .
Следует из экономических условий.
Целевая функция - функция переменных задачи, экстремум которой требуется найти.
Если целевая функция и система ограничений линейны , то задача математического программирования называется задачей линейного программирования (ЗЛП).
Формулировка ЗЛП.
min(max)...01cxcxczn,....,...,...212221211212111mnmnmnbxaxaxabxaxaxabxaxaxa означает " " , " " или "=".0 ...,,0,021nx:RnX МножествоХ называется допустимым или областью допустимых решений (ОДР)Xxn);(21 допустимое решение Функцияz - целевая функция.
(min)max)(xz.);(21Xxn min(max):*xzXx оптимальное решение Каноническая форма ЗЛП min(max)...01cxcxczn,....,...,...212221211212111mnmnmnbxaxaxabxaxaxabxaxaxa0 ...,,0,021nx:RnX Стандартная форма ЗЛП min(max)...01cxcxczn,....,...,...212221211212111mnmnmnbxaxaxabxaxaxabxaxaxa означает " " или "".0 ...,,0,021nx:RnX Матричная форма ЗЛП min(max)0cXCXzTBAX0Xnx ...,,21 Если то ЗЛП называется целочисленной целые числа, ЗЛП может быть сведена как к канонической, так и к стандартной форме.
Стандартная=>каноническаяininibxaxaxa...)121:0iyininibyxaxaxa...21ininibxaxaxa...)21:0iyininibyxaxaxa...21~)3jx:0,0jxjx Каноническая=>cтандартная 1) Выделить базисные и свободные переменные;
2) Выразить базисные через свободные;
3) Подставить в неравенства для базисных переменных и целевую функцию;
Примерmin31721354321xz0,149352354321431531321xmin109355231xz0,041039023531314315312x Примеры ЗЛП 1) Задача оптимального использования ресурсов.aij(i =1,2,...,m;j =1,2,...,n ) — расходi -го pecypса на производство единицыj-й продукции.P1,P2 ,...Pn — виды продукции.S1,S2 , ...Sm— ресурсыB=(b1,b2 , ...bm ) — объемы ( запасы) ресурсовС=(c1,c2 , ...cn ) — прибыль от реализации единицы продукции.X=(x1,x2 , ...xn ) — объемы производства продукции.maxTCXXzTBAX0X 2) Задача о составлении рациона питания (о диете).aij(i =1,2,...,m;j =1,2,...,n ) — содержаниеi -го вещества в единицеj -го продукта .P1,P2 ,...Pn — продукты питания.S1,S2 , ...Sm— полезные веществаB=(b1,b2 , ...bm ) — мин.
сут.
потребностьС=(c1,c2 , ...cn ) — цена единицы продукта.X=(x1,x2 , ...xn ) — количество продуктов.minTCXXzTBAX0X 3) Транспортная задачаA1,A2 , ...Am— поставщикиa1,a2 , ...am — запасы однородного грузаmia1— суммарный запас грузаB1,B2 , ...Bn— потребителиb1,b2 ,...bn— потребностиnjb1— суммарная потребностьcij — стоимость перевозки единицы грузаAiВj — транспортный тариф.
Потребители Поставщики1B2B…jB…nB Запасы1A11xc12xc…jxc1…nxc1a2A21xc22xc…jxc2…nxc2a … … … … … … … …iA1ixc2ixc…ijxc…inxcia … … … … … … … …mA1mxc2mxc…mjxc…mnxcma Потребности1b2b…jb…nb Транспортная таблицаminjijxcXz11min)(njbxjmiij,1,1miaxinjij,1,1.,1;,10njmixij 1.
Доставка необходимого количества груза в каждый пункт назначения;
2.
Вывоз имеющегося груза из всех пунктов отправления;
3.
Исключение обратных перевозок 4) Задача о назначенияхA1,A2 , ...Am— работники : каждый может выполнять одну работуBj , из работ:B1,B2 , ...Bn.cij — производительность труда работникаАi , на рабочем местеBj Кого и куда назначить , чтобы добиться максимальной производительности труда? Каждый работник может быть назначен только на одну работу.xij — назначениеi -го работника на j-ю работу.xij = 1, еслиi -й работник назначается на яj-ю работу;xij = 0, если не назначается.
При назначенииi -го работника наj -ю работу производительность равнаcijxij.minjijxcXz11max)(njxmiij,1,1mixnjij,1,1.,1;,10njmixij 5) Составление оптимального портфеля ценных бумаг (задача о банке).
Пусть инвестирование денежных средств сопровождается получением ценных бумаг( активов): акций, облигаций, валюты, векселей.
Если денежные средства вложены в несколько объектов, полученные от инвестирования ценные бумаги образуют портфель активов.
Доходность портфеля характеризуется средневзвешенной доходностью его составляющих.
Для портфеля из двух активов:D=WaDa+WbDb, где D — общая доходность портфеля;Wa — удельный вес актива А;Da — доходность актива А;Wb — удельный вес актива В,Db - доходность актива В.
Риск— количественная мера неопределенности будущей стоимость ценных бумаг.Ai, (i = 1...m ) — активы;
Di — ожидаемые доходы;
Wi — доли каждого актива в портфеле— управляемые переменные;
R — риск портфеля — средневзвешенная величина рисков активов ri Оптимальные Wi — максимальный ожидаемый доход при условии заданного макс.
уровня риска.
Ограничения: 1) риск портфеля R Rmax 2) в каждый актив обязательно должны быть проведены положительные инвестиции;
3) все средства должны быть полностью инвестированы.miDWD1max1RrWRmi1miWmiWi,2,10 ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Задача с двумя переменнымиminmax21xcxcz,.,212221211212111mbxaxabxaxabxaxa0,021x Пусть система ограничений совместна , т.е.
имеет решение , а многоугольник ее решений( ОДР) ограничен.
Каждое из неравенств определяет полуплоскость с границейаi1х1+аi2x2=bi,i =1, 2, ...,n илих1=0,x2=0.
Представим этот многоугольник на плоскости Ох1x2.2x1xABCDE021,cNmaxmin Линейная функция при фиксированныхz является уравнением семейства | | прямых21xcxcz constxcxc21 -линии уровняz(X) вектор нормали к линиям уровня21,cN Линия уровня, имеющая общие точки с ОДР и расположенная так, что ОДР целиком находится в одной из полуплоскостей , называется опорной прямой.
Теорема.
Значения целевой функции в точках линии уровня увеличиваются , если линию уровня перемещать параллельно начальному положению в направлении вектора нормали , и уменьшаются при перемещении в против вектора нормали.2x1x21,xMn0'2'1,xP ДоказательствоABCD ПустьZ(X) =c1x1 +с2x2 — целевая функция.21,cn нормаль из начала координатnCDnABCDAB,|| линии уровняnPMCDxMABxP||:,21'2'121'2'1,xOMxOPOMnxcxcMZ,21PMnOPnPMOPn,PZnPMPZnPMnPZ,1,1 Алгоритм решения задачи линейного программирования с двумя переменными графическим методом 1.
Строится ОДР.
2.
Из начала координат строится вектор нормали N=(c1,c2).3.
Перпендикулярно векторуN проводится линия уровняc1x1+с2x2 =0, проходящая через начало координат.4.
Линия уровня перемещается до положения опорной прямой, на которой будет находиться максимум или минимум функции.
В зависимости от вида ОДР и целевой функции z(X) ЗЛП имеет единственное решение2x1xABCDE021,cNmax имеет∞ много решений2x1xABCDE021,cN не имеет ни одного оптимального решения2x1xAB021,cN Графическим методом можно решать ЗЛП в канонической форме приn-r 2 где n — число неизвестных;
r — ранг матрицы системы.
Если уравнения системы ограничений линейно независимы, тоr = m — числу уравнений.
Теорема.
ОДР ЗЛП— выпуклое множество.
Опорное решение ЗЛП и его взаимосвязь с угловыми точками Столбцы матрицы ограничений канонического вида ЗЛП называются векторами условий.
Опорным решением ЗЛП называется такое допустимое решениеX(x10, x20 ,..., xm0, 0, ..., 0), для которого векторы условий соответствующие положительным координатам линейно независимы.
Базисом опорного решения называется базис системы векторов условий ЗЛП, в состав которого входят векторы, соответствующие отличным от нуля координатам опорного решения.
Теорема.
опорное решение является угловой точкой ОДР.
Теорема.
угловая точка ОДР является