线性规划建模及其单纯形法.ppt

《线性规划建模及其单纯形法.ppt》由会员分享，可在线阅读，更多相关《线性规划建模及其单纯形法.ppt（161页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章 线性规划建模及单纯形法1本章内容重点w线性规划模型与解的主要概念w线性规划的单纯形法,线性规划多解分析w线性规划应用建模21.线性规划的概念 例例2.1:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：产品甲产品乙设备能力（h）设备A3265设备B2140设备C0375利润（元/件）150025003问题：工厂应如何安排生产可获得最大的总利润？解：设变量xi为第i种(甲、乙)产品的生产件数(i=1,2)。根据题意，我们知道两种产品的生产受到设备能力(机时数)的限制。对设备A:两种产品

2、生产所占用的机时数不能超过65，于是我们可以得到不等式:3x1+2x265对设备B:两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式:2x1+x2404 对设备C:两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式:3x275；另外，产品数不可能为负，即x1,x20。同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润：z=1500 x1+2500 x2综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型：5目标函数目标函数 Maxz=1500 x1+2500

3、x2约束条件约束条件s.t.3x1+2x2652x1+x2403x275x1,x2 0 6 这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subject to”的缩写，表示“满足于”。因此，上述模型的含义是：在给定条件限制下，求使目标函数z达到最大的x1,x2的取值78910v以上两个例子的共同特点：(1)每个问题都有一组未知变量，表示所求方案，这组未知变量称为决策变量，通常这些变量取值是非负且连续。(2)存在一组约束条件，指决策变量取值时受到的各种可用资源的限制，表示为决策变量的线性等式或不等式(3)都有一个要

4、求的目标，并且这个目标可表示为一组决策变量的线性函数，称为目标函数，目标函数可以是求最大，也可以求最小。具有上述特征的数学模型就称为线性规划模型。11第二章线性规划线性规划问题的一般形式:目标函数：Max(Min)z=c1x1+c2x2+cnxn约束条件：a11x1+a12x2+a1nxn(=,)b1a21x1+a22x2+a2nxn(=,)b2.am1x1+am2x2+amnxn(=,)bm非负约束条件：x1，x2，xn012v目标函数：vMax(Min)z=c1x1+c2x2+cnxnv有两种形式：vMax，Minv约束条件：v三种情况，大于等于，小于等于，等于v非负约束条件13线性规划的

5、简洁形式142.15第二章线性规划16第二章线性规划17第二章线性规划vc-目标函数系数向量目标函数系数向量vb-右端项右端项vA-约束系数矩阵约束系数矩阵18第二章线性规划规范形式目标函数：Maxz=c1x1+c2x2+cnxn 约束条件：a11x1 +a12x2 +a1nxnb1a21x1 +a22x2 +a2nxnb2 .am1x1+am2x2+amnxnbm x1,x2,xn019标准形式目标函数：Maxz=c1x1+c2x2+cnxn 约束条件：a11x1 +a12x2 +a1nxn=b1a21x1 +a22x2 +a2nxn=b2 .am1x1+am2x2+amnxn=bm x1,

6、x2,xn020可以看出，线性规划的标准形式有如下四个特点:目标最大化约束为等式决策变量均非负右端项非负对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式 21 1.极小化目标函数的问题：设目标函数为 Minf=c1x1+c2x2+cnxn 则可以令z-f，该极小化问题与下面的极大化问题有相同的最优解，即 Maxz=-c1x1-c2x2-cnxn 但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即 Minf-Maxz22 2、约束条件不是等式的问题：设约束条件为 ai1 x1+ai2 x2+ain xnbi 可以引进一个新的变量s，使

7、它等于约束右边与左边之差 s=bi(ai1 x1+ai2 x2+ain xn)显然，s也具有非负约束，即s0，这时新的约束条件成为ai1 x1+ai2 x2+ain xn+s=bi23当约束条件为ai1 x1+ai2 x2+ain xnbi时，类似地令s=(ai1 x1+ai2 x2+ain xn)-bi显然，s也具有非负约束，即s0，这时新的约束条件成为ai1 x1+ai2 x2+ain xn-s=bi 24为了使约束由不等式成为等式而引进的变量s称为“松弛变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。25例：将以下线性规划问题转化为标准形

8、式 Minf=3.6x1-5.2x2+1.8x3s.t.2.3x1+5.2x2-6.1x34.1x1+3.3x3x1+x2+x3=38x1,x2,x30 解：首先,将目标函数转换成极大化：令 z=-fx1x2x326其次考虑约束，有2个不等式约束，引进松弛变量x4，x50。于是，我们可以得到以下标准形式的线性规划问题：Maxz=-3.6x1+5.2x2-1.8x3x1x2x3+x4x1x3-x5x1+x2+x3=38x1,x2,x3,x4,x50273.变量无符号限制的问题：在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令 xj=xj-xj”其中 xj0，xj”

9、0即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj和xj”的大小。284.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如bim，秩(A)=m，bRm。在约束等式中，令n维空间的解向量：x=(x1，x2，xn)T 68 中n-m个变量为零，如果剩下的m个变量在线性方程组中有唯一解，则这n个变量的值组成的向量x就对应于n维空间Rn中若干个超平面的一个交点。当这n个变量的值都是非负时，这个交点就是线性规划可行域的一个极点。根据以上分析，我们建立以下概念：(1)线性规划的基基：对于线性规划的约束条件Ax=b，x069 设B是A矩阵中

10、的一个非奇异(可逆)的mm子矩阵，则称B为线性规划的一个基。用前文的记号，A=(p1，p2，pn)，其中pj=(a1j，a2j，amj)TRm，任取A中的m个线性无关列向量pjRm构成矩阵B=(pj1，pj2，pjm)。那么B为线性规划的一个基。我们称对应于基B的变量xj1，xj2，xjm为基变量；而其他变量称为非基变量。70 可以用矩阵来描述这些概念。设B是线性规划的一个基，则A可以表示为 A=B,N x也可相应地分成 xB x=xN 其中x xB为m维列向量，它的各分量称为基基变变量量，与基B的列向量对应；xN为n-m列向量，它的各分量称为非基变量，与非基矩阵N的列向量对应。这时约束等式A

11、x=b可表示为 71 xB (B,N)=b xN 或 BxB+NxN=b 如果对非基变量xN取确定的值，则xB有唯一的值与之对应 xB=B-1b-B-1NxN 特别，当取xN=0，这时有xB=B-1b。关于这类特别的解，有以下概念。72(2)线性规划问题的基本解基本解、基本可行解基本可行解和可行可行基基：对于线性规划问题，设矩阵B=(pj1,pj2,pjm)为一个基，令所有非基变量为零，可以得到m个关于基变量xj1,xj2,xjm的线性方程，解这个线性方程组得到基变量的值。我们称这个解为一个基本解基本解；若得到的基变量的值均非负，则称为基基本本可可行行解解，同时称这个基B为可行基可行基73 矩

12、阵描述为，对于线性规划的解xBB-1bx=xN0称为线性规划与基B对应的基本解。若其中B-1b0，则称以上的基本解为一基本可行解，相应的基B称为可行基。74 我们可以证明以下结论：线性规划的基本可行解就是可行域的极点。这个结论被称为线性规划的基本定理，它的重要性在于把可行域的极点这一几何概念与基本可行解这一代数概念联系起来，因而可以通过求基本可行解的线性代数的方法来得到可行域的一切极点，从而有可能进一步获得最优极点。75 例2.9:考虑例的线性规划模型Maxz=1500 x1+2500 x2s.t.3x1+2x2+x3=652x1+x2+x4=403x2+x5=75x1,x2,x3,x4,x5

13、0注意，线性规划的基本解、基本可行解(极点)和可行基只与线性规划问题标准形式的约束条件有关。7632100A=P1,P2,P3,P4,P5=2101003001A矩阵包含以下10个33的子矩阵：B1=p1，p2，p3B2=p1，p2，p4B3=p1，p2，p5B4=p1，p3，p4B5=p1，p3，p5B6=p1，p4，p5B7=p2，p3，p4B8=p2，p3，p5B9=p2，p4，p5B10=p3，p4，p577 其中B4=0，因而B4不是该线性规划问题的基。其余均为非奇异方阵，因此该问题共有9个基。对于基B3=p1，p2，p5，令非基变量x3=0，x4=0，在等式约束中令x3=0，x4=

14、0，解线性方程组：3x1+2x2+0 x5=652x1+x2+0 x5=400 x1+3x2+x5=75得到x1=15，x2=10，x5=45，对应的基本可行解：x=(x1,x2,x3,x4,x5)T=(15,10,0,0,45)T。于是对应的基B3是一个可行基。78 类似可得到x(2)=(5,25,0,5,0)T（对应B2）x(7)=(20,0,5,0,75)T（对应B5）x(8)=(0,25,15,15,0)T（对应B7）x(9)=(0,0,65,40,75)T（对应B10）是基本可行解；而x(3)=(0,32.5,0,7.5,-22.5)T（对应B9）x(4)=(65/3,0,0,-10

15、/3,75)T（对应B6）x(5)=(7.5,25,-7.5,0,0)T（对应B1）x(6)=(0,40,-15,0,-45)T（对应B8）是基本解。79 因此，对应基本可行解(极点)的B2B3B5B7B10都是可行基。这里指出了一种求解线性规划问题的可能途径，就是先确定线性规划问题的基，如果是可行基，则计算相应的基本可行解以及相应解的目标函数值。由于基的个数是有限的(最多个)，因此必定可以从有限个基本可行解中找到最优解。80利用求解线性规划问题基本可行解(极点)的方法来求解较大规模的问题是不可行的。单纯形法的基本思路是有选择地取基本可行解，即是从可行域的一个极点出发，沿着可行域的边界移到另一

16、个相邻的极点，要求新极点的目标函数值不比原目标函数值差。81由上节的讨论可知，对于线性规划的一个基，当非基变量确定以后，基变量和目标函数的值也随之确定。因此，一个基本可行解向另一个基本可行解的移动，以及移动时基变量和目标函数值的变化，可以分别由基变量和目标函数用非基变量的表达式来表示。同时，当可行解从可行域的一个极点沿着可行域的边界移动到一个相邻的极点的过程中，所有非基变量中只有一个变量的值从0开始增加，而其他非基变量的值都保持0不变。单单 纯纯 形形 法法82初始基本可行解初始基本可行解是否最优解或是否最优解或无限最优解无限最优解?结束结束沿边界找新沿边界找新的基本可行解的基本可行解NY单纯

17、形法的基本过程单纯形法的基本过程83考虑标准形式的线性规划问题：Maxz=c1x1+c2x2+cnxns.t.a11 x1+a12 x2+a1n xn=b1a21 x1+a22 x2+a2n xn=b2.am1 x1+am2 x2+amn xn=bmx1,x2,xn0 x1 c1 b1 a11 a12.a1n x2 c2 b2 a21 a22.a2nx=.C=.B B=.A=.xn cn bn am1 am2.amn 84这里，矩阵A表示为：A=(p1，p2，pn)，其中pj=(a1j，a2j，amj)TRm。若找到一个可行基，不防设B=(p1，p2，pm)，则m个基变量为x1,x2,xm，n

18、-m个非基变量为xm+1，xm+2，xn。通过运算，所有的基变量都可以用非基变量来表示：85 x1=b1-（a1m+1xm+1+a1m+2xm+2+a1nxn）x2=b2-（a2m+1xm+1+a2m+2xm+2+a2nxn）(2-11).xm=bm-（amm+1xm+1+amm+2xm+2+amnxn）把它们代入目标函数，得z=z+m+1xm+1+m+2xm+2+nxn(2-12)其中j=cj-（c1a1j+c2a2j+cm amj）我们把由非基变量表示的目标函数形式称为基B相应的目标函数典式典式。86单纯形法的基本步骤可描述如下：(1)寻找一个初始的可行基和相应基本可行解(极点)，确定基变

19、量、非基变量以及基变量、非基变量(全部等于0)和目标函数的值，并将目标函数和基变量分别用非基变量表示；87(2)在用非基变量表示的目标函数表达式(2-12)中，我们称非基变量xj的系数(或其负值)为检验数记为j。若j0，那么相应的非基变量xj，它的值从当前值0开始增加时，目标函数值随之增加。这个选定的非基变量xj称为“进基变量”，转(3)。如果任何一个非基变量的值增加都不能使目标函数值增加，即所有j非正，则当前的基本可行解就是最优解，计算结束；88(3)在用非基变量表示的基变量的表达式(2-11)中，观察进基变量增加时各基变量变化情况，确定基变量的值在进基变量增加过程中首先减少到0的变量xr，

20、满足，=minbi/aijaij0=br/arj这个基变量xr称为“出基变量”。当进基变量的值增加到时，出基变量xr的值降为0时，可行解就移动到了相邻的基本可行解(极点)，转(4)。89如果进基变量的值增加时，所有基变量的值都不减少，即所有aij非正，则表示可行域是不封闭的，且目标函数值随进基变量的增加可以无限增加，此时，不存在有限最优解，计算结束；(4)将进基变量作为新的基变量，出基变量作为新的非基变量，确定新的基、新的基本可行解和新的目标函数值。在新的基变量、非基变量的基础上重复(1)。90 例：用单纯形法的基本思路解例的线性规划问题 Maxz=1500 x1+2500 x2s.t.3x1

21、+2x2+x3=652x1+x2+x4=403x2+x5=75x1,x2,x3,x4,x5091第一次迭代：(1)取初始可行基B10=(p3,p4,p5)，那么x3，x4，x5为基变量，x1，x2为非基变量。将基变量和目标函数用非基变量表示：z=1500 x1+2500 x2x3=65-3x1-2x2x4=40-2x1-x2x5=75-3x2当非基变量x1,x2=0时，相应的基变量和目标函数值为x3=65，x4=40，x5=75，z=0，得到当前的基本可行解：x=(0,0,65,40,75)T，z=0。这个解对应于图2-7的D、E交点。92(2)选择进基变量。在目标函数z=1500 x1+25

22、00 x2中，非基变量x1，x2的系数都是正数，因此x1，x2进基都可以使目标函数z增大，但x2的系数为2500，绝对值比x1的系数1500大，因此把x2作为进基变量可以使目标函数z增加更快。选择x2为进基变量，使x2的值从0开始增加，另一个非基变量x1保持零值不变。93(3)确定出基变量。在约束条件 x3=65-3x1-2x2x4=40-2x1-x2x5=75-3x2中，由于进基变量x2在3个约束条件中的系数都是负数，当x2的值从0开始增加时，基变量x3、x4、x5的值分别从当前的值65、40和75开始减少，当x2增加到25时，x5首先下降为0成为非基变量。这时，新的基变量为x3、x4、x2

23、，新的非基变量为x1、x5，当前的基本可行解和目标函数值为：x=(0，25，15，15，0)T，z=62500。这个解对应于图中的C、D交点94第二次迭代：(1)当前的可行基为B7=(p2,p3,p4)，那么x2，x3，x4为基变量，x1，x5为非基变量。将基变量和目标函数用非基变量表示：z=62500+1500 x1(2500/3)x5x2=25(1/3)x5x3=15-3x1+(2/3)x5 x4=15-2x1+(1/3)x595(2)选择进基变量。在目标函数z=62500+1500 x1(2500/3)x5中，非基变量x1的系数是正数，因此x1进基可以使目标函数z增大，于是选择x1进基，

24、使x1的值从0开始增加,另一个非基变量x5保持零值不变。(3)确定出基变量,在约束条件x2=25(1/3)x5x3=15-3x1+(2/3)x5x4=15-2x1+(1/3)x596中，由于进基变量x1在两个约束条件中的系数都是负数，当x1的值从0开始增加时，基变量x3、x4的值分别从当前的值15、15开始减少，当x1增加到5时，x3首先下降为0成为非基变量。这时，新的基变量为x1、x2、x4，新的非基变量为x3、x5，当前的基本可行解和目标函数值为：x=(5，25，0，5，0)T，z=70000。这个解对应于图中的A、C交点。97第三次迭代：(1)当前的可行基为B2=(p1,p2,p4)，那

25、么x1，x2，x4为基变量，x3，x5为非基变量。将基变量和目标函数用非基变量表示：z=70000500 x3500 x5x1=5(1/3)x3+(2/9)x5x2=25(1/3)x5x4=5+(2/3)x3(1/9)x598(2)选择进基变量。在目标函数z=70000500 x3500 x5 中，非基变量x3、x5的系数均不是正数，因此进基都不可能使目标函数z增大，于是得到最优解，x*=(5，25，0，5，0)T，最优目标值为z*=70000。这个解对应于图2-7的A、C交点。我们也称相应的基B2=(p1,p2,p4)为最最优优基基。计算结束。99v表格单纯形法表格单纯形法v考虑：考虑：bi

26、0i=1,mMaxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxnb1a21x1+a22x2+a2nxnb2am1x1+am2x2+amnxnbm x1，x2，xn0100v加入松弛变量：加入松弛变量：Maxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn+xn+1=b1a21x1+a22x2+a2nxn+xn+2=b2am1x1+am2x2+amnxn+xn+m=bm x1，x2，xn，xn+1，xn+m0(2-13)101v1.初始单纯形表考虑(2-13)，xn+1，xn+2，xn+m对应的一个基是单位矩阵，得到一个基本可行解为：x1=x

27、2=xn=0;(非基变量)xn+1=b1,xn+2=b2，xn+m=bm(基变量)用非基变量来表示基变量为：102对于一般情况，如果标准形式的目标函数为：将上面的式子代入，可以得到：其中，103显然，xj=0j=1,n;xn+i=bii=1,m是基本可行解。对应的基是单位矩阵。以下是初始单纯形表：104在初始单纯形表的基础上，进行迭代，可以得到一般形式的单纯形表105v1.在单纯形表中，所有 ,则当前基本可行解是最优解；否则若 ，则可选xk进基v2.若表中xk列的所有系数aik0，则没有有限最优解，计算结束；否则继续以下步骤；v3.在i列选最小的值，对应基变量作为出基变量。取ark为主元；v4

28、.建立一个与原表相同的空表，把第r行乘以1/ark,所得结果填入第r行；对于i不等于r行，把第r行乘以-(aik/ark)之后与原表中第i行相加，所得结果填入第i行；在XB列中r行位置填入xk，在cB列中用ck代替r行原来位置106单纯形法的矩阵描述107v这样矩阵可以分块记为A=(B,N)，相应的，向量x和c可以记为：等式约束Ax=b可以写成由于基B可逆，即可以得到(2-17)108这就是在约束条件下，基变量用非基变量表示的形式对于一个确定的基B，目标函数z可以写成：(2-18)将(2-17)代入以上目标函数表达式，得到目标函数z用非基变量表出的形式109其中为检验数(这里的检验数与前面的检

29、验数差一个符合)110当xn=0时，相应的解为就是对应于基B的基本解如果B是一个可行基，则有111用矩阵向量表示的单纯形表112例化标准形式：例化标准形式：Maxz=1500 x1+2500 x2s.t.3x1+2x2+x3=652x1+x2+x4=403x2+x5=75x1,x2,x3,x4,x50最优解x1=5x2=25x4=5（松弛标量，表示B设备有5个机时的剩余）最优值z*=70000113一般线性规划问题的处理考虑一般的线性规划标准问题：bi0i=1,mMaxz=c1x1+c2x2+cnxn.a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2.am1x1

30、+am2x2+amnxn=bm x1，x2，xn0114v系数矩阵中不含单位矩阵。这时没有明显的基本可行解，常常采用引入非负人工变量的方法来求的初始基本可行解v引入人工变量xn+i0（i=1,m）v变约束为下面的标准形式115v人工变量xn+i（i=1,m）对应的一个基是单位矩阵，得到一个基本可行解为v这时，迭代总是在基本可行解的范围内进行，一旦找到不含这些引入的人工变量的基本可行解，迭代就可以回到原问题的范围进行。v常用两种方法：大M法和两步法116大M法引入人工变量xn+i0（i=1,m）及充分大正数M。得到：Maxz=c1x1+c2x2+cnxn-Mxn+1-Mxn+ms.t.a11 x

31、1+a12 x2+a1n xn+xn+1=b1 a21 x1+a22 x2+a2n xn+xn+2 =b2.am1 x1+am2 x2+amn xn+xn+m =bmx1，x2，xn ，xn+1，xn+m0117这样构造了一个新问题。这样，求解这个新问题就从最大化的角度迫使人工变量取零，以达到求解原问题最优解的目的显然，xj=0j=1,n;xn+i=bii=1,m是基本可行解。对应的基是单位矩阵。结论：若得到的最优解满足xn+i=0i=1,m则是原问题的最优解；否则，原问题无可行解。118例：Maxz=5x1+2x2+3x3-x4s.t.x1+2x2+3x3=152x1+x2+5x3=20 x

32、1+2x2+4x3+x4=26x1,x2,x3,x40119Maxz=5x1+2x2+3x3-x4-Mx5-Mx6s.t.x1+2x2+3x3+x5=152x1+x2+5x3+x6=20 x1+2x2+4x3+x4=26x1,x2,x3,x4,x5,x60120大大M法法得到最优解：(25/3，10/3，0，11)T最优目标值：112/3121v例 用大M法解下列线性规划解：首先将数学模型化为标准形式解：首先将数学模型化为标准形式系数矩阵中不存在系数矩阵中不存在单位矩阵，无法建单位矩阵，无法建立初始单纯形表立初始单纯形表122v故人为添加两个单位向量，得到人工变量单纯形法数学模型：其其中中：M

33、 M是是一一个个很很大大的的抽抽象象的的数数，不不需需要要给给出出具具体体的的数数值值，可可以以理理解解为为它它能能大大于于给给定定的的任任何何一一个个确确定定数数值值；再再用用前前面面介介绍绍的的单单纯纯形形法法求求解解该该模模型型，计计算算结结果见下表。果见下表。123Cj32-100-M-MCBXBBx1x2x3x4x5x6x7i0 x64-431-10104-Mx5101-1201005-Mx712-21000113-2M2+M-1+2M-M0 x63-650-1013/5-Mx58-3300108/3-1x312-210005-6M5M0-M002x23/56/5101/50-Mx5

34、31/53/5003/5131/3-1x311/52/5012/50500002x213010123x131/310015/3-1x319/300102/3000-5-25/3124v两阶段法：v引入人工变量xn+i0，i=1,m；v构造:Maxz=-xn+1-xn+2-xn+ms.t.a11x1+a12x2+a1nxn+xn+1=b1a21x1+a22x2+a2nxn+xn+2=b2.am1x1+am2x2+amnxn+xn+m=bm x1,x2.xn,xn+1,xn+m0125 第一阶段求解上述问题：显然，xj=0j=1,n;xn+i=bii=1,m 是基本可行解,它对应的基是单位矩阵。结

35、论：若得到的最优解满足xn+i=0i=1,m则是原问题的基本可行解;否则，原问题无可行解。得到原问题的基本可行解后，第二阶段求解原问题。126例：Maxz=5x1+2x2+3x3-x4s.t.x1+2x2+3x3=152x1+x2+5x3=20 x1+2x2+4x3+x4=26x1,x2,x3,x40127 第一阶段问题Maxz=-x5-x6 s.t.x1+2x2+3x3+x5=152x1+x2+5x3+x6=20 x1+2x2+4x3+x4=26x1,x2,x3,x4,x5,x60128第一阶段第一阶段得到原问题的基本可行解:(0，15/7，25/7，52/7)T129第二阶段第二阶段 把基

36、本可行解填入表中得到原问题的最优解:(25/3，10/3，0，11)T最优目标值：112/3130 注意：单纯形法中1、每一步运算只能用矩阵初等行变换；2、表中第3列(b列)的数总应保持非负（0）；3、当所有检验数均非正（0）时，得到最优单纯形表。若直接对目标求最小时，要求所有检验数均非负；4、当最优单纯形表存在非基变量对应的检验数为零时，可能存在无穷多解；131 5、关于退化和循环。如果在一个基本可行解的基变量中至少有一个分量xBi=0(i=1,2,m)，则称此基本可行解是退化的基本可行解。一般情况下，退化的基本可行解（极点）是由若干个不同的基本可行解（极点）在特殊情况下合并成一个基本可行解

37、（极点）而形成的。退化的结构对单纯形迭代会造成不利的影响。132 可能出现以下情况：进行进基、出基变换后，虽然改变了基，但没有改变基本可行解（极点），目标函数当然也不会改进。进行若干次基变换后，才脱离退化基本可行解（极点），进入其他基本可行解（极点）。这种情况会增加迭代次数，使单纯形法收敛的速度减慢。在特殊情况下，退化会出现基的循环，一旦出现这样的情况，单纯形迭代将永远停留在同一极点上，因而无法求得最优解。133 在单纯形法求解线性规划问题时，一旦出现这种因退化而导致的基的循环，单纯形法就无法求得最优解，这是一般单纯形法的一个缺陷。但是实际上，尽管退化的结构是经常遇到的，而循环现象在实际问题中

38、出现得较少。尽管如此，人们还是对如何防止出现循环作了大量研究。1952年Charnes提出了“摄动法”，1954年Dantzig，Orden和Wolfe又提出了“字典序法”，134 合理利用线材问题：如何下料使用材最少。合理利用线材问题：如何下料使用材最少。配料问题配料问题：在原料供应量的限制下如何获取最大利润。：在原料供应量的限制下如何获取最大利润。投资问题投资问题：从投资项目中选取方案，使投资回报最大：从投资项目中选取方案，使投资回报最大产品生产计划产品生产计划：合理利用人力、物力、财力等，使获：合理利用人力、物力、财力等，使获利最大利最大劳动力安排劳动力安排：用最少的劳动力来满足工作的需

39、要运输：用最少的劳动力来满足工作的需要运输问题：如何制定调运方案，使总运费最小问题：如何制定调运方案，使总运费最小线性规划应用线性规划应用135数学规划的建模有许多共同点，要遵循下列原则：(1)容易理解。建立的模型不但要求建模者理解，还应当让有关人员理解。这样便于考察实际问题与模型的关系，使得到的结论能够更好地应用于解决实际问题(2)容易查找模型中的错误。这个原则的目的显然与(1)相关。常出现的错误有：书写错误和公式错误136(3)容易求解。对线性规划来说，容易求解问题主要是控制问题的规模，包括决策变量的个数和约束条件的个数。这条原则的实现往往会与(1)发生矛盾，在实现时需要对两条原则进行统筹

40、考虑137 建立线性规划模型的过程可以分为四个步骤：(1)设立决策变量(2)明确约束条件并用决策变量的线性等式或不等式表示(3)用决策变量的线性函数表示目标，并确定是求极大（Max）还是极小（Min）(4)根据决策变量的物理性质研究变量是否有非负性138 例某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：人力资源分配的问题人力资源分配的问题设司机和乘务人员分别在各时间段一开始时上班，并连续工作8h，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?139 解：设xi表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。目标函数：目标函数

41、：Minx1+x2+x3+x4+x5+x6约束条件：约束条件：.x1+x660 x1+x270 x2+x360 x3+x450 x4+x520 x5+x630 x1,x2,x3,x4,x5,x60140例:某工厂要做100套钢架，每套用长为的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？套裁下料问题套裁下料问题解:考虑下列各种下料方案（按一种逻辑顺序给出）把各种下料方案按剩余料头从小到大顺序列出141假设x1,x2,x3,x4,x5分别为上面前5种方案下料的原材料根数。我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5约束条件：s.t.x1+2x2+x

42、41002x3+2x4+x51003x1+x2+2x3+3x5100 x1,x2,x3,x4,x50142例明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如下表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？生产计划的问题生产计划的问题143解：解：设x1,x2,x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数144 求xi的利润:

43、利润=售价-各成本之和可得到xi（i=1,2,3,4,5）的利润分别为15、10、7、13、9元。这样我们建立如下数学模型：目标函数:Max15x1+10 x2+7x3+13x4+9x5约束条件：s.t.5x1+10 x2+7x380006x1+4x2+8x3+6x4+4x5120003x1+2x2+2x3+3x4+2x510000 x1,x2,x3,x4,x50145生产计划问题例例某厂生产某厂生产、三种产品，都分别经三种产品，都分别经A、B两道工序加工。设两道工序加工。设A工序可分别在设备工序可分别在设备A1和和A2上完上完成，有成，有B1、B2、B3三种设备可用于完成三种设备可用于完成B

44、工序。已工序。已知产品知产品可在可在A、B任何一种设备上加工；产品任何一种设备上加工；产品可可在任何规格的在任何规格的A设备上加工，但完成设备上加工，但完成B工序时，只能工序时，只能在在B1设备上加工；产品设备上加工；产品只能在只能在A2与与B2设备上加工。设备上加工。加工单位产品所需工序时间及其他各项数据如下表，加工单位产品所需工序时间及其他各项数据如下表，试安排最优生产计划，使该厂获利最大。试安排最优生产计划，使该厂获利最大。146设备产品设备有效台时设备加工费（单位小时）A15106000300A2791210000321B1684000250B24117000783B374000200

45、原料费（每件）0.250.350.5售价（每件）1.252.002.8147解：设xijk表示产品i在工序j的设备k上加工的数量。约束条件有：148目标是利润最大化，即利润的计算公式如下：带入数据整理得到：149v因此该规划问题的模型为：150 例:某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如下表。问：该厂应如何安排生产，使利润收入为最大？配料问题配料问题151解：设xij表示第i种（甲、乙、丙）产品中原料j 的含量。这样我们建立数学模型时，要考虑：对于甲：x11，x12，x13；对于乙：x21，x22，x23；对于丙：x31，x32，x33；对于原料1：x11，

46、x21，x31；对于原料2：x12，x22，x32；对于原料3：x13，x23，x33；152目标函数：利润最大，利润=收入-原料支出约束条件：规格要求4个；供应量限制3个。Maxz=-15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33153s.t.0.5x11-0.5x12-0.5x130（原材料1不少于50%）x11x12x130（原材料2不超过25%）x21x22x230（原材料1不少于25%）-0.5x21+0.5x22-0.5x230（原材料2不超过50%）x11+x21+x31100(供应量限制）x12+x22+x32100(供应量限制）x1

47、3+x23+x3360(供应量限制）xij0,i=1,2,3;j=1,2,3154 例：某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。投资问题投资问题155据测定每万元每次投资的风险指数如下表：156a)应如何确定这些项目的每

48、年投资额，使得第五年年末拥有资金的本利金额为最大？b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？问：问：157 解1)确定决策变量：连续投资问题设xij(i=1,2,3,4,5，j=1,2,3,4)表示第i年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下决策变量：Ax11 x21 x31 x41 x51Bx12 x22 x32 x42Cx33Dx241582)约束条件：约束条件：第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是：x11+x12=200第二年：B次年末才

49、可收回投资故第二年年初的资金为x11，于是：x21+x22+x24x11第三年：年初的资金为x21x12，于是x31+x32+x33x21x12第四年：年初的资金为x31x22，于是 x41+x42x31x22第五年：年初的资金为x41x32，于是x51x41x32B、C、D的投资限制：xi230(i=1，2，3，4)，x3380，x24100159a)Maxzx51x42x33x24s.t.x11+x12=200 x21+x22+x24x11x31+x32+x33x21x12x41+x42x31x22x51x41x32xi230(i=1、2、3、4)，x3380，x24100 xij0(i=1,2,3,4,5；j=1,2,3,4）3）目标函数及模型：）目标函数及模型：160b)Minf=(x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33x24s.t.x11+x12200 x21+x22+x24x11x31+x32+x33x21x12x41+x42x31x22x51x41x32xi230(i=1、2、3、4)，x3380，x24100 x51x42x33x24330 xij0(i=1,2,3,4,5；j=1,2,3,4）161