线性规划与目标规划.doc

线性规划与目标规划.DOC:..,本小节重点介绍在军事通信网分析和规划中常用的两类模型一一线性规划和目标规划。:一是如何有效利用现有的人力、物力完成更多的任务;二是在预定的任务目标下,如何耗用最少的人力、物力去实现目标。这些规划问题的数学模型都是由3个要素组成:一是变量,或称决策变量,是需要确定的未知量,用来表明规划中的用数量表示的方案;二是目标函数,它是决策变量的线性函数,按优化目标在该函数前加上max或min;三是约束条件,它是含决策变量的线性等式或不等式。下面,以一个具体的例子來说明问题。例5・1某通信连计划用两种通信设备A和B进行通信联络,建网方式有甲、乙两种,。问:两种方式的组网数各为多少时,能在规定的条件下,使得提供的话路总数z达到最大?:设",X?分别为甲、乙两种方式的组网数,则由己知条件,容易得到该问题的线性规划模型为:目标函数:maxz=18%]+15x23X[+x2<24约束条件:(2舛+2兀2520兀],x2>0一般地,规定线性规划问题的标准形式如下:maxz=XcA冃工qx・=®(z=1,2,...,7/7)>0(J=1,2,.・・,z?)其中,{亏}(丿=1,2,・・・,")是决策变量,maxz=£c/Xj为目标函数,工4内=勺,;=1;=1i= ,x.>0(j=l,2,为约束条件,.(subjectto的缩写)为约束于。约束条件右端的常数项勺全为非负。对于非标准形式的线性规划问题可以通过引入松弛变量等转化为标准形式。所谓松弛变量,是指在化为标准形式时,使约束不等式变为等式时所加入的变量。对不符合标准形式(或称非标准形式)的线性规划问题,可分别通过下列方法化为标准形式。(1)目标函数为求极小值,即为:minz=n=XCJXJ冃因为求minz等价于求max(-z),令z'=-z,即化为maxz'=-工c内j=i(2)约束条件的右端项勺V0时,只需将等式或不等式两端同乘一1,则等式右端项必大于零。(3)约束条件为不等式。当约束条件为“5”时,如5x,+x2<23,可令x3=23-5x,-x2,得5x,+x2+x3=23,显然x3>0:当约束条件为时,如4^+3x2>25,可令%=4西+3兀2-25,得4+3x2-x4=25,显然兀》0;式中的变量兀3,x4>0,即为引入的松弛变量,引进模型后它们在目标函数屮的系数均为零。(4)取值无约束的变量。如果变量x代表某产品当年计划数之差,显然x的取值可能是正也可能是负,这时可令x= 其中/>0,Z>0,将其代入线性规划模型即可。(5)对兀50的情况,令/=-x,显然/>0o满足约束条件的解X=(壬,兀2,…,兀)称为问题的可行解,可行解的全体称为可行域;使目标函数达到最大值的可行解称为最优解。可行域是一个凸多边形,最优解若存在一定在其某个顶点上取得。所谓凸集C,是指对任何X,,X2gC,有qX]+(1—q)X2wC(0vgv1)。顶点X(gC):不存在XpX2gC,使得X-aXx+