.10.第1章线性规划及单纯形法对例1中提出的问题，一般只要在铁皮四个角上剪去四个边长各为文的正方形，折叠起来就做成一个容器，容积为V=（a-2r）2t：要使容积最大，就是要确定的值，使V达到最大，例2中提出的问题要复杂-些.假定用，和2分别表示I、Ⅱ两种产品在计划期内的产量，因设备A在计划期内的可用时间为12h，不允许超过，于是有2+22≤12.对设备B、C也可列出类似的不等式：41≤16；5z2≤15.企业的月标是在各种设备能力允许的条件下，使总的利润收人2=21+3r2为最大：因此例2可归结为：约束于（subjectto），或简写为s.t.(211+2x2≤12≤164元15元2≤1511t，12≥0使2=2z1+3x2max比较上述两个例子，从数学角度讲，都是求极值的问题，但例1中除变量取值要求非负外无其他更多限制，这类问题可以用微积分中已学过的求极值的古典方法解决；而例2中变量的取值要受一系列条件的限制，求解这类带附加限制条件的极值问题是运筹学中规划论部分研究的内容1一2 线性规划问题的数学模型通常称现实世界中人们关心、研究的实际对象为原型.模型是指将某一部分信息简缩、提炼而构造的原型替代物.数学模型则是对现实世界的一个特定对象，为达到一定自的，根据内在规律做出必要的简化假设，并运用适当数学工具得到的个数学结构.从上述例子看到规划问题的数学模型包含三个组成要素：（1）决策变量，指决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量；（2）目标函数，指问题要达到的目的要求，表示为决策变量的函数：（3）约束条件，指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式.如果在规划问题的数学模型中，决策变量为可控的连续变量，目标函数和约束条件都是线性的，这类模型称为线性规划问题的数学模型，一般线性规划尚题的数学模型可表示为以下儿种形式：max（或min)=cii+C22++Cs.t.anzi +ai2r2+..+aint(或-,=)bia21+a222+.+a2（或=，）b2(1.1)......amla1tam272+..+amnzn≤（或=，=）bm(31,2,",n≥0
81一般线性规划问题的数学模型11以上模型的简写形式为：max(或min)zc-1+Car,≤（或=，≥)b,（(i = l,,m)(1.2)=1≥0G = l,",n)用向量形式表达时，上述模型可写为：max（或min)=Cx(1.3a)s.t. [2Pp,≤(或 =,≥)b(1.3b)1= 1≥0(1.3c)[a132式中C=(cl,"，Cu);X :C2,[b1[ajb2a2b=P, =.:Lbm.an用矩阵形式来表示可写为：max（或min）z=Cxs.t.AX≤（或，≥)b(1.4)Ix≥0[ail.ana12a21a22a2nA=三::Lam!am2amnA称为约束方程组变量的系数矩阵，或简称约束变量的系数矩阵，1一3 线性规划问题的标准形式由于目标函数和约束条件内容和形式上的差别，线性规划问题可以有多种多样，为了便于讨论，规定线性规划问题的标准形式如下：7(1.5a)maxzC1+1
第1章线性规划及单纯形法:12s.t.(1.5b)aur,=b,(i=l.,m),-1(1.5c)( = 1,",n)x,≥0标准形式的线性规划模型中，目标函数为求极大值（有些书上规定是求极小值），约束条件全为等式，约束条件右端常数项b，全为非负值，变量又，的取值为非负，对不符合标准形式（或称非标准形式）的线性规划问题，可分别通过下列方法化为标准形式1.目标函数为求极小值，即为：57min=cyr因为求min之等价于求max（一之），令=一之，即化为：max =-c(-c,)r,r=E2.约束条件为不等式，当约束条件为“≤”时，如2+22≤12，可令=12-2，-22或2+22+=12，显然3≥0.当约束条件为“时，如10，+122≥18，可令4=10+122-18或101+122-#4=18，x4≥0.和4是新加上去的变量，取值均为非负，加到原约束条件中去的目的是使不等式转化为等式，其中工3称为松弛变量，4一般称为剩余变量，其实质与3相同，故也有统称松弛变量的.松弛变量或剩余变量在实际间题中分别表示未被充分利用的资源和超用的资源数，均未转化为价值和利润，所以引进模型后它们在自标函数中的系数均为零3.取值无约束的变量，如果变量代表某产品当年计划数与上一年计划数之差，显然的取值可能是正也可能为负，这时可令=一”，其中≥0，α"≥0，将其代入线性规划模型即可.4.变量≤0.可令，=-，显然，≥0【例3】将下述线性规划模型化为标准形式min=r1+22+313s.t.f-2r + r2 + r3≤93ri+12+213≥43x-22-3r=-6≤02≥0取值无约束【解】令=2，=-（0，≥0)，i=-，并按上述规则将问题转化为：max=xi-2a2-3x3+3x3+014+0r5
51一般线性规划问题的数学模型，13.=9s.t.[2xi+ 2 + xs- z3+ x43ri+r2+2xj-2r3-75=43i+2x2+3x3-3r3= 6i,r2,r3,r3,as,rs≥01一4线性规刺问题的解线性规划问题(1.6a)maxzLcr1=1s.t.(1.6b)(i=l,.,m)ar, =b,(1.6c)( =1,",n)r20求解线性规划问题，就是从满足约束条件（1.6b）、（1.6c）的方程组中找出一个解，使目标函数（1.6a）达到最大值、可行解满足上述约束条件（1.6b）、（1.6c）的解X=（1，，，）T称为线性规划问题的可行解，全部可行解的集合称为可行域，最优解使目标函数（1.6a）达到最大值的可行解称为最优解，基设A为约束方程组（1.6b）的m×n阶系数矩阵（设n>m），其秩为m：B是矩阵A中的一个mXm阶的满秩子矩阵，称B是线性规划问题的一个基．不失一般性，设Fa11..aim:B=/:=(Pi,.,Pm)Laml..amm]B中的每一个列向量P，（=1，"，m）称为基向量，与基向量P对应的变量，称为基变量：线性规划中除基变量以外的其他变量称为非基变量，基解在约束方程组（1.6b）中，令所有非基变量xm+1=m+2==αn=0，又因为有lBl十0①，根据克拉默规则，由m个约束方程可解出m个基变量的惟一解Xz=（a1，，m）.将这个解加上非基变量取0的值有X（ri，2，"，工m，0，，0)T，称X为线性规划问题的基解．显然在基解中变量取非零值的个数不大于方程数m，又基解的总数不超过Cm个，基可行解满足变量非负约束条件（1.6c）的基解称为基可行解可行基对应于基可行解的基称为可行基①IB表示B的行列式
第 1 章线性规划及单纯形法14[例4]在下述线性规划问题中，列出全部基、基解、基可行解和指出最优解，max2=2x1+3x2+0x3+0r4+0r5=12S.t.[2a+2x2+x3= 164元1+r45x2= 15+ 35(r,≥0 (j=1,,5)写出约束方程组的系数矩阵【解】P,P2P3P4Ps2100240010A=50001矩阵A的秩≤3所以只要找出3个列向量组成的矩阵满秩，这3个向量就是线性规划问题的一个基.令与基对应的变量为基变量，其余变量为非基变量，令非基变量等于零，求解方程组就可找出基解．表1-1列出了本例线性规划表中用*标注的为最优解，问题的全部基、基解，指出娜些是基可行解，表 1-1基解目标函数值基是基可行解？3132&334Es17300否4-2P1P2P340是15 *30P43P1P2是1405420PP2Ps8是040154P1P3Ps否1201560-8P1P4P's9是6160P203P3P41816- 15否060P2P4Ps0是1615P40012P3Ps图解法82为了便于建立"维空间中线性规划问题的概念及便于理解求解一般线性规划问题的单纯形法的思路，先介绍图解法，这种方法的优点是直观性强，计算方便，但缺点是只适用于问题中有两个变量的情况，图解法的步骤是：建立