一类最优指派问题的动态规划解法

考虑一类指派问题 :欲把 m项工作指派 n个人去完成 ( m≥ n) ,要求每项工作只能由一个人来做 ,第 i个人可以同时做 bi 项工作 ,其中 bi( bi≥ 1)是待求的未知数 ,i=1,2 ,… ,n,满足 ni=1bi =m,假定已知第 i人做第 j项工作所用的时间 cij≥ 0 ,i=1,2 ,… ,n;j=1,2 ,… ,m。文中给出了求解上述问题最优指派 (即使总耗用时间最小 )的动态规划解法。     

一类最优指派问题的动态规划模型

考虑一类指派问题：欲指派m个人去做n项工作(m≥n)，要求每个人只做一项工作，第j项工作可以由b_j个人共同去做，其中，b_j(b_j≥1)是待求的未知数，j=1,2,…,n,满足．假定已知第i人做第j项工作的效益为c_ij≥0,i=1,2,…m;j=1,2,…,n.本文建立了求解上述问题最优指派（即使总的效益最大)的动态规划模型．     

关于“一类最优指派问题的动态规划模型”的注记

考虑一类较一般的最优指派问题 :欲指派 m个人做 n项工作 (m≥n) ,要求每个人只做一项工作 ,第j项工作可以由 bj个人共同去做 ,其中 bj是待求未知数 ,满足 dj≤ bj≤ ej(即 ej,dj为第 j项工作所需人数的上下限 )及 ∑nj=1bj=m(即每个人都有工作 ) ,dj,ej为已知常数 ,j =1 ,… ,n.第 i人做第 j项工作的效益为 cij≥ 0 ,i =1 ,… ,m;j =1 ,… ,n.本文建立求解上述最优指派问题 (使总的效益最大 )的动态规划模型 ,并将文 [1]作为本文的特例 .     

柯西不等式中取等条件的妙用

设a1,n2,a3,…,an,b1,b2,b3,…,bn是实数,则（a1^2＋a2^2＋…＋an^2）（b1^2＋62^2＋…＋b1^2）≥（a1b1＋a1b2＋…＋anbn）^2,当且仅当bi=0（i=1,2,…,n）或存在一个数k,使得ai=kbi（i=1,2,…,n）时,等号成立．     

一类分式不等式的新证法

定理1 设ai,bi〉0（i=1,2,…，n）,若a1≥a2≥…≥an且b1≥b2≥…bn或a1≤a2≤…≤an且b1≤b2≤…≤bn,n≥2,r,t〉0,rn-t〉0,s=∑ni=1ai,则     

Radon不等式的推广及其应用

Radon不等式设ai≥0，bi〉0（i=1，2，…，n），l∈N，则 ^n∑i=1 ai^l＋1/bi^l≥（^n∑i=1 ai）^l＋1/（^n∑i=1 bi）^l 本文将（1）式推广如下：     

巧用柯西不等式证不等式竞赛题

设ai&;#183;bi∈R（i=1,2,…,n）则（a1^2＋a2^2＋…＋an^2）（b1^2＋b2^2＋…＋bn^2）≥（a1b1＋a2b2＋…＋anbn）^2.     

N×2N瓶颈指派问题及其阀门(threshold)算法

讨论把2N项任务(或工件)指派(安排)给N个人(或机器)的问题.已知人i处理(或加工)任务j的时间花费是cij,i=1,2,…,N,j=1,2,…,2N,要求每人恰承担2项任务,每项任务恰由1个人承担.怎样分派任务,使完成任务最慢的人所花的时间最少.     

一道不等式问题的探源、证明与推广

《数学教学》2012年第12期的数学问题874为：题目 已知 m,n∈N＋,m,n≥2,xi∈R＋（i=1,2,…,m）,（^m∑i=1）xi=S,n∈N＋,求证：（^m∑i=1）^n√xi/S-xi≥.看完此题,笔者不禁想起了文[1]中的不等式：题源1已知a,b,c为正数,求证：√a/（b＋c）＋√b/（c＋a）＋√c/（a＋b）〉2。     

任意n个完备二分图的并图的k－优美性和算术性

证明了对于正整数k,n,si,ti（si,ti≥2,i=1,2,…,n）,图n/U/i=1,Ksi,ti是k-优美图;对于正整数k,d（d≥2）,k≠0（roodd）及n,si,ti（si,ti≥2,i=1,2,…,n）,图n/U/i=1,Ksi,ti是（k,d）-算术图,前一结论推广了文[6]的相应结果。     

一个分式型不等式定理及其应用

引理　若xi∈R ,i=1,2,…,n,则1)　1nΣni=1xαi≥1nΣni=1xiα(α≥1或α<0)2)　1nΣni=1xαi≤1nΣni=1xiα(0<α<1)注　此引理可由琴生(Jensen)不等式推出.因篇幅有限,这里不再赘述,读者可参阅参考文献〔1〕和〔2〕.定理1　若ai、bi∈R ,i=1,2,…,n,γ≥2或γ<0,β>0,则Σni=1aribβi≥n1-r β.Σni=1airΣni=1biβ证明　由已知和柯西不等式,得Σni=1bβiΣni=1aribβi=Σni=1bβi2Σni=1aγibβi2≥Σni=1bβi.aγibβi2=Σni=1aγ2i2(1)由引理1)和2),得Σni=1aγ2i2≥n2-γΣni=1aiγ及Σni=1bβi-1≥n-1 βΣni=1bi-β(β≥1或0<β<…     

一个不等式的推广

不等式1n∑i=n1aim≥(1n∑i=n1ai)m,其中m∈N ,ai>0,(i=1,2,…,n)可推广为:∑ni=1piaim≥(∑ni=1piai)m.(1)其中m≥1,ai>0,pi>0,(i=1,2,…,n)且∑ni=1pi=1,不等式1n∑i=n1aim≤(1n∑i=n1ai)m,其中00,(i=1,2,…,n)可推广为:∑ni=1piaim≤(∑ni=1piai)m.(2)其中0相似文献   

Radon不等式的推广及其应用

Radon不等式[1]设ai≥0,bi>0(i=1,2,…,n),l∈N,则∑ni=1ail 1bil≥(∑ni=1ai)l 1(∑ni=1bi)l(1)本文将(1)式推广如下:设ai≥0,bi>0(i=1,2,…,n),l∈N,k∈N ,则∑ni=1ail kbil≥(∑ni=1ai)l k(∑ni=1bi)lnk-1(2)证记(2)式左端为A,B=∑ni=1bi.由均值不等式,得以下n个不等式:a1l kb1lA bB1 bB1 … bB1l个 1n 1n … 1nk-1个≥(l k)a1l kABlnk-1.同理a2l kb2lA bB2 … bB2 1n … 1n≥l( lk k)a2.……anl kbnlA bBn … bBn 1n … 1n≥l (kl k)anABlnkq-1.将以上n个不等式的两边分别相加,得AA lBB (k-1)≥(l lk AkB)lni∑=nk1-a1i.约去…     

一道东南数学奥林匹克试题的推广

题目(第三届(2006年)东南数学奥林匹克第6题):求最小的实数m,使不等式m(a3 b3 c3)≥6(a2 b2 c2) 1(1)对满足a b c=1的任意正实数a,b,c恒成立.本文给出此题的一个推广.推广设ai>0,i=1,2,…,n,n≥2,∑ni=1ai=1,B>0,A>-Bn,求最小的实数m,使不等式m∑ni=1ai3≥A∑ni=1ai2 B(2)恒成立.注:在推广中取n=3,A=6,B=1即得上述东南竞赛题.解ai=1n,i=1,2,…,n,得m≥An Bn2.下面证明,当ai>0,i=1,2,…,n,n≥2,∑ni=1ai=1,B>0,A>-Bn时,有(An Bn2)∑ni=1ai3≥A∑ni=1ai2 B(3)下面证明(3)式成立.不妨设a1≥a2≥…≥an,则a12≥a22≥…≥an2,由切比雪夫不…     

分数次积分的多线性换位子

设L是L2(Rn)上解析半群的无穷小生成算子,其积分核具有高斯界,L-α/2表示L的分数次积分算子,其中0＜α＜n.对自然数m,若bi(i=1,2,…,m)表示Rn上有界平均振荡函数,则由分数次积分L-α/2与bi(i=1,2,…,m)生成多线性交换子是从Lp(Rn)到Lq(Rn)是有界的,其中1＜p＜α/n,1/q=1/p-α/n.     

不等式〔∑from i=1 to n (a_i~3)〕〔∑from i=1 to n (b_i~3)〕〔∑from i=1 to n (c_i~3)〕≥〔∑ from i=1 to n (a_ib_ic_i)〕~3的恒等式构造

文[1]为证明2001年第42届IMO第2题而通过独特的思路给出了一个恒等式:设实数ai,bi∈R,A3=n∑i=1ai3,B3=n∑i=1bi3,且AB≠0,则有恒等式n∑i=1ai3 2/3n∑i=1bi3 1/3=n∑i=1ai2bi 13A2Bn∑i=12aiA biBaiA-biB2(1)根据恒等式(1),我们自然会考虑更一般形式的3×N维形式的不等式n∑i=1ai3n∑i=1bi3n∑i=1ci3≥n∑i=1aibici3(2)通过对(2)的研究,本文通过构造方法给出了式(2)的一个新的恒等式.定理设实数ai,bi∈R,A=3∑ni=1ai3,B=3∑ni=1bi3,C=3∑ni=1ci3,且ABC≠0,则有恒等式3(n∑i=1ai3)(n∑i=1bi3)n∑i=1ci3=n∑i=1aibici ABC6Ω(3)其…     

巧用柯西不等式证不等式竞赛题

设ai,bi∈R(i=1,2,…,n),则(a12 a22 … a2n)(b12 b22 … b2n)≥(a1b1 a2b2 … anbn)2(1)当且仅当且bi=λai(i=1,2,…,n)时,(1)式取等号.这就是著名的柯西不等式,它还有如下等价形式:设ai,bi>0(i=1,2,…,n),则a12b1 ab222 … ban2n>(ab11 ab22 …… abnn)2(2)当且仅当且ab11     

一个不等式的推广

文[1]，[2]给出了一个不等式：设αi〉0,pi≥0（i=1,2,…,n）且p1＋p2＋…＋pn=1，则1/n↑∑↑i=1pi/αi≤n↑П↑i=1αi^pi≤n∑↑i=1piαi。     

对一道奥赛题的再探索

第三届(2006年)东南数学奥林匹克第6题为:求最小的实数m,使不等式m(a3 b3 c3)≥6(a2 b2 c2) 1对满足a b c=1的任意正实数a,b,c恒成立.文[1]将该题推广如下:设ai>0(i=1,2,…,n,n≥2),∑ni=1ai=1,B>0,A Bn>0,求最小的实数m,使不等式m∑ni=1ai3≥Ai∑=n1ai2 B恒成立.本文将对该题作进一步的探索.引理(幂平均值不等式)若α≥β>0,ai>0(i=1,2,…,n),则∑ni=1aiαn1α≥∑ni=1aiβn1β(1)特别地,当β=1,α≥1时有∑ni=1aiαn≥∑ni=1ainα(2)证略.探究1设α>β≥1,A>0,B>0,求最小的实数m,使不等式m∑ni=1aiα≥Ai∑=n1αiβ B(n≥2,n∈N)(3)对…     

A Refinement of the Arithmetic-geometric Means Inequality

We suppose throughout that(1)m,n∈N,a_i,a_ij,q_j,p,x are all positive numbers;∑_j=1~n q_j=1,l≥1,λ>0,(i=1,2,…,m;j=1,2,…,n).