Сообщение vicvolf » 21 дек 2009, 18:31
[quote name='Pavlovsky' date='21.12.2009, 6:57' post='132030']
K чему все это? To что целевая функция (ЦФ) бинарных переменных обладающая свойством аддитивности достигает максимума при F(1,1,…1), очевидно.
Добрый день!
Это пока не было доказано. назовем это Теоремой 1.
Эта теорема будет использована при доказательстве Теоремы 2, которая c Ваших слов не является очевидной.
Теорема 2
Пусть требуется найти условный максимум ЦФ бинарных переменных F(x1,x2,….xN) при одновременном выполнении условий на функции ограничений (ФО):
G1(x1,x2,….xN)<=G10G2(x1,x2,….xN)<=G20.......................................GN(x1,x2,….xN)<=GN0, где G10, G20, …. GN0 – постоянные.При этом ЦФ и ФО обладают свойством аддитивности, и выполнятся условия для ЦФ: F(0,0,…1)=>F(0,0….1,0)=>…….=>.F(1,0,……0) (1),
a также выполняются условия для ФО:
G1(0,0,…1)<=G1(0,0….1,0)<=…….<=.G1(1,0,……0) (2) G2(0,0,…1)<=G2(0,0….1,0)<=…….<=.G2(1,0,……0) ......................................................................................... GN(0,0,…1)<=GN(0,0….1,0)<=…….<=GN(1,0,……0).Требуется доказать, что при указанных условиях, максимум ЦФ достигается на последовательности «пожирающих единиц»: (0,……..0,1), (0,……..1,1)……..(1,1,…….1).ДоказательствоHa основании условия (2) и аддитивности ФО для любой функции GK (K=1, 2…N) выполняется:GK (0,0,…..1,1)<=GK (0,0,….1,.0,1)<=GK(0,0,….1,.0,0,1)<=….<= GK(1,0,….0,.0,1)<= GK(1,0,….0,.1,0)<= GK(1,0,….1,.0,0) <=….<= GK(1,1,….0,.0,0).Таким образом, на указанной последовательности бинарных переменных ФО убывают и достигают минимума в точке (0,0,….0,.1,1).Аналогично получаем, чтоGK(0,0,…..1,1,1)<= GK(0,0,….1,.0,1,1)<= GK(0,0,….1,1,.0,0,1)<=….<= GK(1,1,….0,.0,1)<= GK(1,1,….0,.1,0)<= GK(1,1,0….1,.0,0)<=….<= GK(1,1,1,….0,.0,0)Таким образом, на указанной последовательности бинарных переменных ФО убывают и достигают минимума в точке (0,0,….1,1,1).Аналогично можно показать и для других членов «пожирающей последовательности» и в том числе для GK(0,1,…..1,1,1).C другой стороны, для любой функции GK (K=1, 2…N), благодаря аддитивности, выполняется: GK(0,0….1,1…..1)=GK(0,0….0,1…..1)+GK(0,0….1,0…..0). Так GK(0,0….1,0…..0)=>0, то GK(0,0….1,1…..1)=> GK(0,0….0,1…..1), те любая функция GK является возрастающей на последовательности «пожирающих единиц» и естественно достигает значения GK0 на данной последовательности.
Однако в силу того, что функция GK (K=1, 2…N), как было выше доказано, принимает на последовательности «пожирающих единиц» минимальное значение, то корни уравнения GK(x1,x2,……xN)=GK0 (x10,x20, …xN0) принимают на этой последовательности максимальное значение, т.e содержат большее число «1», чем на любой другой последовательности.
Учитывая, что ЦФ по условию также является аддитивной, то для нее выполняется:
F(0,0,……1,1,…1) = F(0,0,……0,1,…1)+ F(0,0,……1,0,…0). Так как F(0,0,……1,0,…0)=>0, то F(0,0,……1,1,…1) => F(0,0,……0,1,…1). Следовательно, ЦФ является возрастающей функцией на «пожирающей последовательности» и в точке (x10,x20, …xN0), содержащей большее число «1», достигает своего максимального значения.
B силу выполнения для ЦФ условия (1), на основании теоремы 1, в точке (x10,x20, …xN0) достигается максимум ЦФ не только среди точек «пожирающей последовательности», но и среди всех точек, где выполняются условия на ФО.
Последний раз редактировалось
vicvolf 29 ноя 2019, 17:06, всего редактировалось 1 раз.
Причина: test