资源描述：
《线性规划与目标规划》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、5.1规划论基础规划论是运筹学中应用最为广泛的一个分支，本小节重点介绍在军事通信网分析和规划中常用的两类模型一一线性规划和目标规划。5.1.1线性规划1.问题和模型线性规划问题主要有以下2种：一是如何有效利用现有的人力、物力完成更多的任务;二是在预定的任务目标下，如何耗用最少的人力、物力去实现目标。这些规划问题的数学模型都是由3个要素组成：一是变量，或称决策变量，是需要确定的未知量，用来表明规划中的用数量表示的方案；二是目标函数，它是决策变量的线性函数，按优化目标在该函数前加上max或min；三是约
2、束条件，它是含决策变量的线性等式或不等式。下面，以一个具体的例子來说明问题。例5・1某通信连计划用两种通信设备A和B进行通信联络，建网方式有甲、乙两种，有关数据见表5.1。问：两种方式的组网数各为多少时，能在规定的条件下，使得提供的话路总数z达到最大？表5.1有关数据表单网所需P网有十甲乙设备数量A3124B2220单网能提供的话路数1815解：设"，X?分别为甲、乙两种方式的组网数，则由己知条件，容易得到该问题的线性规划模型为：目标函数：maxz=18%]+15x23X[+x2<24约束条件：（2
3、舛+2兀2520兀],x2>0一般地，规定线性规划问题的标准形式如下：maxz=XcA冃工qx・=®(z=1,2,...,7/7)s.t.仃Xj>0(J=1,2,.・・,z?)其中，｛亏｝(丿=1,2,・・・,")是决策变量，maxz=£c/Xj为目标函数，工4内=勺，;=1;=1i=,x.>0(j=l,2,为约束条件，s.t.(subjectto的缩写)为约束于。约束条件右端的常数项勺全为非负。对于非标准形式的线性规划问题可以通过引入松弛变量等转化为标准形式。所谓松弛变量，是指在化为标准形式时，使
4、约束不等式变为等式时所加入的变量。对不符合标准形式(或称非标准形式)的线性规划问题，可分别通过下列方法化为标准形式。(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
5、^+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,…，兀)称为问题的可行解，可行解的全体称为可行域；使目标函数达到最大值的可行解称为最优解。可行域是一个凸多
6、边形，最优解若存在一定在其某个顶点上取得。所谓凸集C,是指对任何X,,X2gC,有qX]+(1—q)X2wC(0vgv1)。顶点X(gC):不存在XpX2gC,使得X-aXx+(l-6f)X2GC(O<6Z<1)o所谓凸多边形，就是把一个多边形任意一边向两方无限延长成为一条直线，如果多边形的其它各边均在此直线的同旁，那么这个多边形就叫做凸多边形。如图5.1,多边形ABCDEF,把线段AF向两方无限延长，此多边形的其它各边AB、BC、CD、DE、EF均在此直线的同旁，所以多边形ABCDEF是凸多边形。
7、F图5.1凸多边形值得注意的是，在凸多边形的定义屮，延长的这一边是凸多边形的任意一边。图5.2屮的多边形ABCDEF,若分别把AB、BC、CD、DE各边延长为直线，这时均满足凸多边形的定义，但这时并不能说多边形是凸多边形。因为，延长线段AF为直线后，多边形其它各边并不在此直线的同旁。同样，把线段FE延长为直线后，又有类似的情况出现。在二维情况下可用图解法或计算顶点的枚举法求解,但衣决策变量较多吋,图解法失图5.2凹多边形例5.2求解线性问题minS=7x,+5x2效，枚举法计算量较大，通常用基于线
8、性方程组变换的单纯形法进行求解。1.图解法(又称几何法)图解法是对于只是两个决策变量的线性规划问题，在平面内建立直角坐标系，使每个决策变量的取值在一个数轴上表示出来，可行解就成为平面上的点，可行域就是平面上的一个共域，从而最优解必定是在这个平面区域内(包括边界上)的点。根据目标函数在这个平面区域内的取值找出使目标函数取得最优值的点(即最优解)。理论及解的-些特性，也为我7兀］+5兀2=°图解法便于我们理解和了解线性规划问题的一些概念、们进一步学习单纯方法提供一个直观图
