5第五章 线性规划

1机械优化设计2第五章线性规划第一节线性规划问题及其数学模型第二节线性规划的图解法第三节单纯形法第四节人工变量法第五节线性规划的应用模型3第一节线性规划问题及其数学模型一、问题的提出例1某企业在计划期内要安排生产I、II两种产品，己知生产单位产品所需要的设备台时及A、B两种原材料的消耗，如表2-1所示。该企业每生产一件产品I可获利2元，每生产一件产品II可获利3元，问应如何安排计划使该企业获利最多?III限制设备128台时原材料A4016kg原材料B0412kg4解设x1、x2分别表示在计划期内产品I、II的产量。则该计划问题可用数学模型表示为：目标函数约束条件2132maxxxz0,12416482212121xxxxxx5例2某企业生产A、B两种产品，均需经过两道工序。每生产1吨产品A需要经第一道工序加工2小时，第二道工序加工3小时；每生产1吨产品B需要经第一道工序加工3小时，第二道工序加工4小时。可供利用的第一道工序工时为12小时，第二道工序工时为24小时。生产产品B的同时产出副产品C，每生产1吨产品B，可同时得到2吨产品C而毋需增加任何费用。副产品C若能销出则可盈利，否则只能报废。己知销售产品A每吨能盈利400元，产品B每吨能盈利1OOO元，副产品C每销售1吨可盈利300元，而报废1吨产品C则要损失200元。据市场预测，在计划期内产品C的最大销量为5吨。请根据以上背景材料列出线性规划模型，以确定A、B两种产品的产量，使企业总盈利为最大。6解设产品A的产量为xl，产品B的产量为x2，产品C的销售量为x3,产品C的报废量为x4。这样，产品C的产量可以用x3+x4来表示。可以得到下例线性规划模型：目标函数约束条件432123104maxxxxxZ0,,244312325232121213243xxxxxxxxxxx7从以上两例可以看出，它们都是属于一类优化问题。它们的共同特征：(1)每一个问题都用一组决策变量(x1，x2,…,xn)表示某一方案；这组决策变量的值就代表一个具体方案，一般这些变量取值是非负的。(2)存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。(3)都有一个要求达到的目标，它可用决策变量的线性函数(称为目标函数)来表示。按问题的不同，要求目标函数实现最大化或最小化。8满足以上三个条件的数学模型称为线性规划的数学模型。其一般形式为：目标函数约束条件在线性规划的数学模型中，方程(2．1)称为目标函数；(2．2)、(2．3)称为约束条件；(2．3)也称为变量的非负约束条件。nnxcxcxcz2211`max(min)(2.1)0,,,,),(),(2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxa(2.2)（2.3）9二、线性规划问题的标准型标准型为简写为nnxcxcxcz2211max0,,,21221122222121112121111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxaMnjjjxcz1maxnjxmibxaMjnjijij,,2,10,,2,11110在标准型中规定各约束条件的右端项bi≥0。用矩阵描述时为：0maxXbAXCXz其中00000;,,,212111211nmnmmnPPPaaaaaaA称A为约束条件的m×n维系数矩阵，一般m＜n；m,n＞0；b为资源向量；C为价值向量；X为决策变量向量。以下讨论如何化标准型的问题。(1)若要求目标函数实现最小化，即minz＝CX。(2)约束方程为不等式。11例3将例l的数学模型化为标准型。解例l的数学模型为0,1241648232max21212121xxxxxxxxz在各不等式中分别加上一个松弛变量x3,x4,x5，使不等式变为等式。这时得到标准型：0,,,,1241648200032max54321524132154321xxxxxxxxxxxxxxxxxz(3)若存在取值无约束的变量x，可令xxx其中0,xx。12例4将下述线性规划问题化为标准型。为无约束321321321321321,0,5232732minxxxxxxxxxxxxxxxz(1)用x4-x5替换x3，其中x4,x5(2)在第一个约束不等式(3)在第二个约束不等式(4)令z′＝-z，把求minz改为求maxz′；即可得到该问题的标准型。0,,,,,5)(232)(70032max76542154217542165421765421xxxxxxxxxxxxxxxxxxxxxxxxxxz0；号的左端加入松弛变量x6；号的左端减去剩余变量x7；解步骤为：13三、线性规划问题的解的概念可行解与非可行解满足约束条件和非负条件的解X称为可行解，满足约束条件但不满足非负条件的解X称为非可行解基解令非基变量XN=0，求得基变量XB的值称为基础解即XB=B1bXB是基础解的必要条件为XB的非零分量个数m基可行解基解XB的非零分量都0时，称为基可行解，否则为基非可行解基可行解的非零分量个数m时，称为退化解14关于标准型解的若干基本概念：标准型有n+m个变量，m个约束行“基”的概念在标准型中，技术系数矩阵有n+m列，即A=(P1,P2,…,Pn+m)A中线性独立的m列，构成该标准型的一个基，即B=(P1,P2,…,Pm)，|B|0P1,P2,…,Pm称为基向量与基向量对应的变量称为基变量，记为XB=(x1,x2,…,xm)T，其余的变量称为非基变量，记为XN=(xm+1,xm+2,…,xm+n)T，故有X=XB+XN最多有个基mnmC15线性规划标准型问题解的关系约束方程的解空间基解可行解非可行解基可行解退化解16第二节线性规划的图解法例5用图解法求解例l。解在以x1,x2为坐标轴的直角坐标系中，非负条件x1,x20是指第一象限。代表以直线x1+2x2＝8为边界的左下方的x1+2x28，4x116和4x2问题的解(称可行解)，因而此区域是例l的线性规划问题的解集合，称它为例l的每个约束条件都代表一个半平面。如约束条件x1+2x2半平面，若同时满足x1,x212的约束条件的点，8是0，必然落在由这三个半平面交成的区域内。由例l的所有约束条件为半平面交成的区域见图2-2中的阴影部分。阴影区域中的每一个点(包括边界点)都是这个线性规划可行域。170x1x2123412347568Q4Q3Q2Q1x1+2x2=84x1=164x2=12图2-2再分析目标函数z＝2x1+3x2，在这坐标平面上，它可表示以z为参数、-2/3为斜率3/3/212zxx位于同一直线上的点，的一族平行线：具有相同的目标函数值，因而称它为“等值线”。当z值由小变大时，直线3/3/212zxx沿其法线方向向右上方移动。当移动到2Q点时，使z值在可行域边界上实现最大化(见图2-3)，这就得到了例l的最优解22,QQ点的坐标为(4，2)，于是可计算出z＝14。180x1x2123412347568Q4Q3Q2Q1x1+2x2=84x1=164x2=12图2-3这说明该企业的最优生产计划方案是：生产产品I4件，生产产品II2件，可得最大利润为14元。上例中求解得到的问题的最优解是唯一的，但对一般线性规划问题,求解结果还可能出现以下几种情况：19(1)无穷多最优解(多重解)。若将例1中的目标函数变为求maxz＝2x1十4x2则表示目标函数中以参数z的这族平行直线与约束条件x1+2x2平行。当z值由小变大时，将与线段32QQ重合(见图2-4)。线段32QQ上任意一点都使z取得相同的最大值，这个线性规划问题有无穷多最优解(多重解)。8的边界线0x1123412347568Q4Q3Q2Q1X2图2-420X1X2012341234图2-5(2)无界解。对下述线性规划问题0,242max21212121xxxxxxxxz用图解法求解结果见图2-5。从图中可以看到，该问题可行域无界，目标函数值可以增大到无穷大，称这种情况为无界解或无最优解。21(3)无可行解。如果在例l的数学模型中增加一个约束条件－2x1+x2该问题的可行域为空集，即无可行解，也不存在最优解。4，从图解法中直观地看到，当线性规划问题的可行域非空时，它是有界或无界凸多边形。若线性规划问题存在最优解，它一定在可行域的某个顶点得到；若在两个顶点同时得到最优解，则它们连线上的任意一点都是最优解，即有无穷多最优解。0x1x2123412347568Q4Q3Q2Q1x1+2x2=84x1=164x2=12图2-2-1-2－2x1+x2≥422第三节单纯形法一、单纯形法的基本思想单纯形法的基本思路是：根据问题的标准，从可行域中某个基可行解(一个顶点)开始，转换到另一个基可行解(顶点)，并且使目标函数达到最大值时，问题就得到了最优解。1．举例2．初始基可行解的确定12345123142512345max2300028416412,,,,0zxxxxxxxxxxxxxxxxx231234512312100(,,,,)4001004001100(,,)0100018164124z=2APPPPPBPPP34531241521对应的变量x,x,x为基变量xx-2xxxxxx+=200z2345122(0)T3x+0x0x+0xx+3x令非基变量x=x得，从而得一个基可行解X=(0,0,8,16,12)24显然，不是最优解。（1）换入基变量的选择，原则是选目标函数中系数最大的非基变量，例题中选x2进基。后演化为最大σ原则。（2）换出变量的选择，例题中选x2进基x1为非基变量令其为0得从中看出只有选择因此选对应的基变量x5出基。后演化为最小θ原则。用x2替换x5得80160124032452x-2xxxx2min(8/2,,12/4)3x才能满足上式。152164134392409zxxz315412515(1)T1xx+x2xxxx令非基变量x=x得，从而得一个新的基可行解X=(0,3,2,16,0)25显然，不是最优解。需再迭代，选x1进基x5＝0得13552532164030x=min(2/1,16/4,-)=2x12284213411324xxzx314121343xx0xxx出基xxxxxx5013xz35(2)T令非基变量x=x得，从而得一个新的基可行解X=(2,3,0,8,0)26显然，不是最优解。需再迭代，选x5进基x3＝0得552554442343412+282x01304x=min(-,4,12)=4x144142211228311428xxxxzxx14153x0xxx出基xxxxx014z34(3)T令非基变量x=x得，从而得一个新的基可行解X=(4,2,0,0,4)所有目标函数中的非基变量系数为负数得到最优解。273．最优性检验与解的判别1112111,111222,112,111max