线性规划和单纯形方法

1、关于线性规划与单纯形方法1第一张，PPT共一百二十九页，创作于2022年6月2第一节 线性规划问题及数学模型一、实例二、线性规划问题（LP问题）的共同特征三、两变量线性规划问题的图解法四、线性规划问题的标准型五、标准型LP问题解的概念六、可行解、基解和基可行解举例第二张，PPT共一百二十九页，创作于2022年6月3一、实例例1 生产计划问题(书P8)Step 1:明确问题，设定决策变量 设I、II两种产品的产量分别为x1, x2 。Step 2: 确定约束条件产品 I II资源限量设备 1 2 8台时原料A 4 0 16公斤原料B 0 4 12公斤 利润 2 3问应如何安排生产使该厂获利最多？

2、第三张，PPT共一百二十九页，创作于2022年6月4说明：OBJ 表示Objective; s.t. 表示Subject to Step 3: 给出目标函数Step 4: 整理数学模型第四张，PPT共一百二十九页，创作于2022年6月5例2 下料问题 现要做100套钢架，每套需2.9米、2.1米和1.5米的圆钢各一根。已知原料长7.4米，问如何下料，使用的原料最少（余料最少或根数最少）？分析： 最简单的做法是：每根7.4米长的原材料各截取三种规格的元钢一根，则料头为0.9米，100套则浪费材料90米。关键是要设计套裁方案，不能有遗漏。第五张，PPT共一百二十九页，创作于2022年6月6解：设

3、x1, x2 , x3, x4 , x5分别代表五种不同的原料用量方案。0.86.6310 x50.37.1021x40.27.2220 x30.17.3102x207.4301x1余料合计1.5米2.1米2.9米方案余料最少的LP模型：第六张，PPT共一百二十九页，创作于2022年6月7根数最少的LP模型：料头最省根数最少解1: x1=30, x2=10, x4=50; 料头Z=16, 根数90。可以做100套钢架，无圆钢剩余。与解1相同解2: x1=100, x3=50; 料头Z=10, 根数150。可以做100套钢架, 但余1.5m圆钢300根。与解1相同第七张，PPT共一百二十九页，创

4、作于2022年6月8LP是数学规划的一个重要分支，数学规划着重解决资源的优化配置，一般可以表达成以下两个问题中的一个：（1）当资源给定时，要求完成的任务最多；（2）当任务给定时，要求为完成任务所消耗的资源最少。 若上述问题的目标约束都能表达成变量的线性关系，则这类优化问题称LP问题。 LP是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。第八张，PPT共一百二十九页，创作于2022年6月9 目标函数用决策变量的线性函数来表示。按问题的不同，要求目标函数实现最大化和最小化。 每一个问题变量都用一组决策变量（x1, x2, , xn）表示某一方案，这组决策变量的值代表一个具体方案，这些

5、变量是非负且连续的。 存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。结论：线性规划是研究在一组线性不等式或线性等式约束下，使得某一线性目标函数取最大或最小的极值问题。二、线性规划问题（LP问题）的共同特征第九张，PPT共一百二十九页，创作于2022年6月10Max(Min) Z=c1x1+c2x2+cnxn (1) a11x1+a12x2+a1nxn ( =, ) b1 a21x1+a22x2+a2nxn ( =, ) b2 s.t. (2) am1x1+am2x2+amnxn ( =, ) bm xj0, j=1,2, ，n (3)(1)目标函数；(2)约束条件；(3

6、)决策变量非负n变量个数； m约束行数； cj价值系数；bi右端项或限额系数； aij技术系数；xj决策变量线性规划模型的一般形式为：第十张，PPT共一百二十九页，创作于2022年6月11线性规划模型的紧缩形式n变量个数； m约束行数； cj价值系数；bi右端项或限额系数； aij技术系数；xj决策变量第十一张，PPT共一百二十九页，创作于2022年6月12练习题：是否为线性规划模型？第十二张，PPT共一百二十九页，创作于2022年6月131.线性不等式的几何意义 半平面作出LP问题的可行域作出目标函数的等值线移动等值线到可行域边界得到最优点2.图解法步骤三、两变量线性规划问题的图解法第十三张

7、，PPT共一百二十九页，创作于2022年6月144x1=164x2=12x1+2x2=8x1x248Q1 4Q4 30例3 （书P8）：Q2(4,2)Z=2x1+3x2 做目标函数2x1+3x2的等值线，与阴影部分的边界相交于Q2(4,2)点，表明最优生产计划为：生产I产品4件，生产II产品2件。Q3第十四张，PPT共一百二十九页，创作于2022年6月15目标函数z=ax1+bx2的值递增的方向与系数a、b有关a0, b0a0X1X2a0, b0, b0z=ax1+bx2目标函数等值线：ax1+bx2=k移项x2=-a/bx1+k/b目标函数等值线在纵轴上的截距为k/b第十五张，PPT共一百二

8、十九页，创作于2022年6月16例4Z=36第十六张，PPT共一百二十九页，创作于2022年6月17例 用图解法求解线性规划问题4x1=164x2=12x1+2x2=8x1x248Q1 4 Q4 30Q2(4,2)Z=2x1+4x2当Z值由小变大时，将与Q2Q3重合Q2Q3上任意一点都是最优解有无穷多最优解（多重解）Q3(2,3)第十七张，PPT共一百二十九页，创作于2022年6月18例 用图解法求解线性规划问题可行域无界无界解（ “无有限最优解”或“最优解无界”）约束条件过分宽松x2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=00可行域无解（不闭合）一定就会出现无界解吗？第十八

9、张，PPT共一百二十九页，创作于2022年6月19例 用图解法求解线性规划问题可行域无界唯一最优解X*=(1,0)，对应于点Ax2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=00第十九张，PPT共一百二十九页，创作于2022年6月20例 用图解法求解线性规划问题可行域无界无穷多最优解对应于点B沿着OB向右上方发出的射线上的所有点x2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=00第二十张，PPT共一百二十九页，创作于2022年6月21例（书P11）： 无可行解（可行域为空）x14x1=164x2=12x1+2x2=8x248Q1 4Q4 30-2-2x1+x2=4

10、无最优解第二十一张，PPT共一百二十九页，创作于2022年6月223.图解法的作用 能解决少量问题 揭示了线性规划问题的若干规律解的类型可行域类型唯一最优解无穷多最优解最优解无界（无有限最优解）无解（不存在可行域）非空有界无界空集规律1：第二十二张，PPT共一百二十九页，创作于2022年6月23规律2：线性规划问题的可行域为凸集线性规划问题凸集的顶点个数是有限的最优解可在凸集的某顶点处达到 第二十三张，PPT共一百二十九页，创作于2022年6月24 小结：图解法的基本步骤：1在直角坐标系作出可行域S的区域（一般是一个凸多边形）2令目标函数值取一个已知的常数k，作等值线：c1x1+c2x2=k3

11、对于max问题，让目标函数值k由小变大，即让等值线进行平移，若它与可行域S最后交于一个点（一般是S的一个顶点），则该点就是所求的最优点，若与S的一条边界重合，此时边界线上的点均是最优点4将最优点所在的两条边界线所代表的方程联立求解，即得最优解X*，把最优解X*带入目标函数，得最优值Z*=CX*注意：若是求目标函数最小值，等值线向反方向移动第二十四张，PPT共一百二十九页，创作于2022年6月25四、线性规划问题的标准型1.标准型 （1）目标函数：max（2）约束条件：等式（3）变量约束：非负 xj0（4）资源限量：非负bi 0标准型的构成要素第二十五张，PPT共一百二十九页，创作于2022年6

12、月262.线性规划标准型的紧缩形式第二十六张，PPT共一百二十九页，创作于2022年6月273.线性规划标准型的向量和矩阵表达式矩阵式: Max Z=CTX s.t. AX=b X0 n向量式: Max Z= cjxj j=1 n s.t. Pjxj=b j=1 xj 0, j=1,2, . ,n第二十七张，PPT共一百二十九页，创作于2022年6月284.所有LP问题均可化为标准型（1）最小转换成最大y1=f(x)y2=-f(x)xyx*y1*y2*第二十八张，PPT共一百二十九页，创作于2022年6月29（2）不等式约束条件转换成等式约束条件（3）变量约束转换（4）把bi0转换成bi0第二

13、十九张，PPT共一百二十九页，创作于2022年6月30例5 化标准型可化为1.处理决策变量2.处理目标函数3.约束条件不等式4.处理约束条件右端 常数项第三十张，PPT共一百二十九页，创作于2022年6月31例6 化标准型1.处理决策变量2.处理目标函数3.约束条件不等式4.处理约束条件右端 常数项第三十一张，PPT共一百二十九页，创作于2022年6月32Max Z =x1+2x2+3x4-3x5+0 x6+0 x7 s.t. x1 - x2 + x4 - x5+x6 = 7 x1+x2 + x4 - x5 - x7 = 2 -3x1 -x2+3x4 -3x5 = 5 x20 , xj0, j

14、=1,4,5,6,7Max Z =x1+2x2+3(x4-x5)+0 x6+0 x7 s.t. x1 - x2 +(x4 - x5 ) +x6 = 7 x1+x2 +(x4 - x5 ) - x7 = 2 -3x1 -x2+3(x4 -x5) = 5 x20 , xj0, j=1,4,5,6,7最终结果中间结果第三十二张，PPT共一百二十九页，创作于2022年6月33课堂练习第三十三张，PPT共一百二十九页，创作于2022年6月34五、标准型LP问题解的概念第三十四张，PPT共一百二十九页，创作于2022年6月35（1）（2）（3）约束系数矩阵：x1x2x3x4x5例：第三十五张，PPT共一百

15、二十九页，创作于2022年6月36约束系数矩阵：可能的基矩阵是A中任意三个列的组合，共10个。第三十六张，PPT共一百二十九页，创作于2022年6月37令B = =( P1 , P2 , , Pm ) 且| B | 0 ，则称Pj (j=1,2,m) 为基向量。与基向量Pj对应的变量xj称为基变量，记为XB = ( x1 , x2 , , xm )T，其余的变量称为非基变量，记为XN = ( xm+1 , xm+2 , , xn ) T 。第三十七张，PPT共一百二十九页，创作于2022年6月38第三十八张，PPT共一百二十九页，创作于2022年6月39第三十九张，PPT共一百二十九页，创作于

16、2022年6月40B1=(P1,P2)：基令：XB1=(x1,x2)x1=0， x2=2X=(0, 2, 0, 0)XB1=(0, 2)对应于B1的基解为也是基可行解第四十张，PPT共一百二十九页，创作于2022年6月41线性规划标准型问题解的关系约束方程的解空间基解可行解非可行解基可行解第四十一张，PPT共一百二十九页，创作于2022年6月42例7 Max Z =2x1+3x2 s.t. x1+ 2x28 4x1 16 4x2 12 x1, x2 0六、可行解、基解和基可行解举例非基变量基变量图中的点x4, x5x1=4x2=3x3= -2A基解x3, x5x1=2x2=3x4=8B基可行解

17、x3, x4x1=4x2=2x5=4C基可行解，最优解x2, x4x1=4x3=4x5=12D基可行解x2, x3x1=8x4= -16x5=12E基解x1, x5x2=3x3=2x4=16F基可行解x1, x3x2=4x4=16x5= -4G基解x1, x2x3=8x4=16x5=12H基可行解4x1=164x2=12x1+2x2=8x1x20Z=2x1+3x2ABCDEFGH标准型第四十二张，PPT共一百二十九页，创作于2022年6月43例8第四十三张，PPT共一百二十九页，创作于2022年6月44LP标准型问题解的结论 根据LP的图解法及解的基本概念可知：基解对应约束条件的交点；基可行解

18、对应可行域的顶点某个基可行解一定是最优解，即一定在可行域的顶点上得到最优解。第四十四张，PPT共一百二十九页，创作于2022年6月45第二节 LP问题的基本理论一、基本概念第四十五张，PPT共一百二十九页，创作于2022年6月46判断以下图形哪些是凸集，哪些不是凸集？判断下列集合是否凸集？第四十六张，PPT共一百二十九页，创作于2022年6月47定理1 LP问题的可行域为一凸集。 二、基本定理第四十七张，PPT共一百二十九页，创作于2022年6月48引理 线性规划问题的可行解X=(x1, x2, , xn)T是基可行解的充要条件为X的正分量所对应的系数列向量是线性独立的。第四十八张，PPT共一

19、百二十九页，创作于2022年6月49定理2 线性规划问题的基可行解对应于可行域的顶点。（即：若X是LP问题的可行解，则“X是LP问题的基可行解”等价于“X是LP问题可行域顶点”）因为X是基可行解，则其对应的向量组a1,a2, ,am线性无关(mm时，有xj=xj(1)= xj(2)= 0.第四十九张，PPT共一百二十九页，创作于2022年6月50第五十张，PPT共一百二十九页，创作于2022年6月51第五十一张，PPT共一百二十九页，创作于2022年6月52第五十二张，PPT共一百二十九页，创作于2022年6月53定理3 若可行域有界，则LP问题的目标函数一定可以在其可行域的顶点上达到最优。引

20、理 若S是有界凸集，则任何一点XS可表示为S的顶点的凸组合。第五十三张，PPT共一百二十九页，创作于2022年6月54 线性规划问题的可行域是凸集(定理1)；凸集的顶点对应于基可行解(定理2)，基可行解(顶点)的个数是有限的；若线性规划有最优解，必在可行域某顶点上达到(定理3)。因此,我们可以在有限个基可行解中寻找最优解。 由线性代数知，对标准形LP问题，用枚举法可以求出所有基解，再通过观察找出其中的可行解（基可行解），进而找出最优解。但如果变量和方程较多，比如m=50，n=100，所有基解有可能达1029个，即使计算机每秒能求解1亿个这样的方程组，也需要30万亿年！因此，必须寻求有效的算法。

21、 为加快计算速度，算法必须具有两个功能，一是每得到一个解，就来检验是否已经最优，若是停止。二是若不是最优，要保证下一步得到的解不劣于当前解。这就是线性规划的单纯形法。 第五十四张，PPT共一百二十九页，创作于2022年6月55第三节 单纯形法一、基本思想检验解的最优性结束Y枢轴运算（旋转运算）确定另一个基本可行解N化LP问题为标准型，确定一个初始基本可行解 化LP问题为标准型，从可行域的某个基可行解（一个顶点）开始，转换到另一个基可行解（另一个顶点），并使目标函数值得到改善，如此反复，从而求得问题的最优解。其实质是逐步迭代（逼近）法。第五十五张，PPT共一百二十九页，创作于2022年6月56单

22、纯形法举例（P20）化为标准型二、基本原理举例第五十六张，PPT共一百二十九页，创作于2022年6月571. 初始基可行解的确定要得到一个初始基可行解，必须找到一个初始可行基。由于典型示例标准化后，x3、x4、x5的系数列向量构成单位矩阵，该矩阵B0是一个基，并且是一个可行基（可以证明，标准化后的单位矩阵一定是可行基）。第五十七张，PPT共一百二十九页，创作于2022年6月58 令非基变量x10、x2 0，得到基可行解及相应的目标函数值，X(0) (0,0,8,16,12)T， Z(0) 0。结论： （1）在标准化的LP问题的约束系数矩阵中，只要存在单位矩阵，就可求得初始基可行解； （2）基变

23、量确定后，目标函数和基变量均可表示成非基变量的代数和形式（如(6)和(5)），从而便于求出基可行解及相应的目标函数值。第五十八张，PPT共一百二十九页，创作于2022年6月592. 最优性检验 考察变换后的目标函数(6)式，非基变量x1、x2的系数都为正数，若让x1、x2取正值，则目标函数值会增大。因此，应将非基变量x1、x2变换成基变量。结论： 在非基变量的代数和形式表示的目标函数中，若非基变量的系数（称为检验数）为正，则目标函数值还有增加的可能，表明当前的基可行解不是最优解。第五十九张，PPT共一百二十九页，创作于2022年6月60 当确定x2为换入变量后， x1还是非基变量，故 x10。

24、现在要保证x3、x4、x50，即(5)当 x2 min（8/2，12/4） =3 （最小比值规则）可保证 x5 =0则x5为换出变量。新的基变量为x3、x4、x2 ，新的可行基为B1(P3, P4 , P2)确定换入变量：一般选择正系数最大的非基变量为换入变量。确定换出变量：（a）保证换出的变量取值为0，变成非基量；（b）其它的变量取值为非负。3. 确定新的基可行解（基变换）第六十张，PPT共一百二十九页，创作于2022年6月614. 旋转迭代 基变量确定后，旋转迭代就是把目标函数和基变量均表示成非基变量x1、x5的代数和形式。可用高斯消去法实现。 令非基变量x10、x5 0，得到新的基可行解

25、及相应的目标函数值，X(1) (0,3,2,16,0)T， Z(1) 9。返回至第二步，直至求出最优解。第六十一张，PPT共一百二十九页，创作于2022年6月62这时目标函数的表达式是z=141.5x30.125x4，当将x1定为换入变量后，继续利用上述方法确定换出变量，继续迭代，再得到一个基可行解X(2)=(2,3,0,8,0)T，这时目标函数的表达式是z=132x3+1/4x5，再经过一次迭代，再得到一个基可行解X(3)=(4,2,0,0,4)T4x1=164x2=12x1+2x2=8x1x248Q1 4Q4 30Q2 (4,2)Z=2x1+3x2 Q3 将上述方程组求解过程，用列表形式表

26、达，即为线性规划单纯形表。第六十二张，PPT共一百二十九页，创作于2022年6月63以x2为主元素以x1为主元素例 2x1+ x2+ 2x3=10 (1) 3x1+ 3x2+ x3= 6 (2) x1+ 1/2x2+ x3= 5 (1)0 x1+ 3/2x2-2x3= -9 (2)(2)-(1)3/2, (1)/2 x1+ 0 x2+ 5/3x3= 80 x1+ x2 - 4/3x3= -6(1)-(2) /3, (2) 2/3三、旋转运算结论：旋转运算就是矩阵的初等变换，是高斯消元第六十三张，PPT共一百二十九页，创作于2022年6月64结论：如果LP问题通过单纯形法迭代到某步时，所有检验数

27、0,则该LP问题已得到最优解。Max Z=CXs.t. AX=b X0若cj-CBB-1Pj=j0, 则ZZ0, Z0即为最优解. (基变量的检验数必为0)令A=(B,N), X= XB ,C=(CB,CN) XN由AX=b (B,N) XB =b BXB+NXN=b B-1BXB+B-1NXN=B-1b XN XB=B-1bB-1NXN (2)将(2)式代入目标函数得Z=CX = (CB,CN) XB =CBXB+CNXN= CB (B-1b-B-1NXN)+CNXN XN = CBB-1b+(CN-CBB-1N)XN = Z0 + (cj-CBB-1Pj)xj xj为非基变量 四、检验数公

28、式第六十四张，PPT共一百二十九页，创作于2022年6月65对于线性规划问题：Max Z=CTX AX=b，X0，可用如下三个判别定理来判别线性规划问题是否已经获得最优解或为无界解。判别定理1 设X为线性规划的一个基可行解，且对于一切jJ（J为非基变量的下标集）有j0，则X为线性规划的最优解。判别定理2 设X为线性规划的一个基可行解，且对于一切jJ（J为非基变量的下标集）有j 0，同时有某个非基变量的检验数k=0( kJ)，则该线性规划有无穷多最优解；设X为线性规划的一个基可行解，且对于一切jJ（J为非基变量的下标集）有j 0，则该线性规划有唯一最优解。判别定理3 设X为线性规划的一个基可行解

29、，若有k0 ( kJ) ，且pk0，即aik 0（i=1,m），则该线性规划问题具有无界解（无最优解）。第六十五张，PPT共一百二十九页，创作于2022年6月66一、步骤Step 1. 化LP问题为标准型,建立初始单纯形表;Step 2. 若所有检验数0,则最优解已达到。 否则,计算 , 选取k 所对应的变量xk 为进基变量;Step 3. 计算 ,选取l 所对应的变量xl 为出基变量;Step 4. 以alk为主元素进行旋转运算,转Step 2;第四节 单纯形法的步骤第六十六张，PPT共一百二十九页，创作于2022年6月67cj CB XB b x1 x2 xm xm+1 xn j 基可行解

30、： x1=b1, x2=b2, , xm=bm , xm+1=xm+2= =xn= 01.初始单纯形表c1 c2 cm cm+1 cnc1 x1 c2 x2 cm xmb1 b2 bm1 0 0 a1, m+1 a1n0 1 0 a2, m+1 a2n 0 0 1 am, m+1 amn0 0 0 m+1 n-CBTB-1b第六十七张，PPT共一百二十九页，创作于2022年6月68对于上述单纯形表：（1）一个基对应一个单纯形表，且单纯形表中必须有一个初始单位基。（2）从单纯形表中，可立即得到一个基可行解： x1=b1, x2=b2, , xm=bm , xm+1=xm+2= =xn= 0（3）

31、用检验数的计算公式很容易计算检验数，并可根据三个判别定理判别上述基可行解是否为最优解或线性规划问题无最优解。第六十八张，PPT共一百二十九页，创作于2022年6月692.进基变量的选择cj c1 c2 cm cm+1 ck cn CB XB b x1 x2 xm xm+1 xk xn c1 x1 c2 x2 cm xmb1 b2 bm 1 0 0 a1, m+1 a1k a1n 0 1 0 a2, m+1 a2k a2n 0 0 1 am, m+1 amk amnj -CBTB-1b 0 0 0 m+1 k n选取 所对应的变量xk 为进基变量。第六十九张，PPT共一百二十九页，创作于2022

32、年6月703.出基变量的选择cj c1 cl cm cm+1 ck cn CB XB b x1 xl xm xm+1 xk xn c1 x1 cl xl cm xmb1 bl bm 1 0 0 a1, m+1 a1k a1n 0 1 0 al, m+1 alk aln 0 0 1 am, m+1 amk amn1lmj -CBTB-1b 0 0 0 m+1 k n选取 所对应的变量xl 为出基变量。第七十张，PPT共一百二十九页，创作于2022年6月714.旋转运算cj c1 cl cm cm+1 ck cn CB XB b x1 xl xm xm+1 xk xn c1 x1 cl xl cm

33、 xmb1 bl bm 1 0 0 a1,m+1 a1k a1n 0 1 0 al,m+1 alk aln 0 0 1 am,m+1 amk amnj ck xkbl /alk0 1/alk 0 al, m+1/alk1 aln/alk b11 -a1k/alk 0 a1, m+1 0 a1nbm0 -amk/alk1 am, m+1 0 amn第七十一张，PPT共一百二十九页，创作于2022年6月72二、实例化为标准型第七十二张，PPT共一百二十九页，创作于2022年6月73单纯型表算法 X(0) (0,0,8,16,12)T以1为主元素进行旋转运算，x1为换入变量， x3为换出变量 0 q

34、i 3 0 0 x5 x2 x3 x40 x4 x3XB b sj 0 x1CB 2 cj x1 cj x2 x3 x4 x5 1 4 0 2 0 4 1 0 0 0 1 0 0 0 1 2 3 0 0 0 b816 12 XB x3 x4 x5 CB 0 0 0以4为主元素进行旋转运算，x2为换入变量，x5为换出变量 sj 2 3 0 0 0 qi 8/2 12/44 x2 3主元列主元行 0 0 0 1/43 1 4 0 1 016 0 0 1 1 0 -1/22X(1) (0,3,2,16,0)T 2 0 0 -3/4 016/4 2/1 1第七十三张，PPT共一百二十九页，创作于202

35、2年6月74此时达到最优解。X*=(4,2), max Z=14。 0 qi 3 0 0 x5 x2 x3 x40 x4 x23 XB b sj x1CB 2 cj 0 qi 3 0 0 x5 x2 x3 x4x23 x1XB b sj 2 x1CB 2 cj 0 0 0 1/43 10 -2 0 1/4 0 x1 2 0 1 1 0 -1/22 2 0-4 128 08/2 12 x50 0 -2 1/2 14 0 1 0 1/4 04 0 1/2 -1/8 0 02 10 -3/2 -1/8 0 0X(3) (4,2,0,0,4)TX(2) (2,3,0,8,0)T以2为主元素进行旋转运算

36、，x5为换入变量，x4为换出变量第七十四张，PPT共一百二十九页，创作于2022年6月754x1=164x2=12x1+2x2=8x1x2484O三、单纯形表与图解法的对应关系X1=(0,0)T, Z1=0X2=(0,3)T, Z2=9X3=(2,3)T, Z3=13X4=(4,2)T, Z4=14Q1Q2QQ3基可行解 基可行解 迭代 顶点 相邻的顶点迭代 图解法：单纯形表算法：第七十五张，PPT共一百二十九页，创作于2022年6月76对于极小化问题，其最优解的判定定理和进基变量的选取和极大化问题刚好相反，如下所示：判别定理1 设X为线性规划的一个基可行解，且对于一切jJ（J为非基变量的下标

37、集）有j0，则X为线性规划的最优解。判别定理2 设X为线性规划的一个基可行解，且对于一切jJ（J为非基变量的下标集）有j0，同时有某个非基变量的检验数k=0( kJ)，则该线性规划有无穷多最优解；设X为线性规划的一个基可行解，且对于一切jJ（J为非基变量的下标集）有j 0，则该线性规划有唯一最优解。判别定理3 设X为线性规划的一个基可行解，若有k0 ( kJ) ，且pk0，即aik 0（i=1,m），则该线性规划问题具有无界解（无最优解）。在进基可行解的转换过程中，进基变量的选取原则是：minj |j 0, 而k对应列向量Pk0, 则此LP问题有无界解.第九十六张，PPT共一百二十九页，创作于

38、2022年6月974.在最优表中出现某非基变量检验数为0（无穷多最优解）第九十七张，PPT共一百二十九页，创作于2022年6月98CBXBbx1x2x3x4x50 x340012/3-1/34x260101/203x14100-2/31/3cj -Zj-360000-10 x46003/21-1/24x2301-3/401/43x1810100cj -Zj-360000-1cj034000结论：若线性规划问题存在某非基变量检验数为0,而其对应列向量Pk0,仍可判断线性规划问题有无穷多最优解。第九十八张，PPT共一百二十九页，创作于2022年6月99例1 某工厂要用三种原材料D、P、H混合调配出

39、三种不同规格的产品A、B、C。已知产品的规格要求、单价和原材料的供应量、单价。该厂应如何安排生产使利润最大？产品名称规格要求单价(元/kg）A原材料D不少于50%原材料P不超过25%50B原材料D不少于25%原材料P不超过50%35C不限25原材料名称每天最多供应量(kg)单价(元/kg)D10065P10025H6035第六节 应用举例解：设A中D、P、H的含量为x11、x12、x13 B中D、P、H的含量为x21、x22、x23 C中D、P、H的含量为x31、x32、x33第九十九张，PPT共一百二十九页，创作于2022年6月100用单纯形法计算得结果：每天生产A产品200kg,分别需要原

40、料:D为100kg;P为50kg;H为50kg. 总利润收入Z=500元/天.第一百张，PPT共一百二十九页，创作于2022年6月101max=-15*x11+25*x12+15*x13-30*x21+10*x22+0*x23-40*x31+0*x32-10*x33;x11+x21+x31=100;x12+x22+x32=100;x13+x23+x33=0.50;x12/(x11+x12+x13)=0.25;x22/(x21+x22+x23)=0.50;end第一百零一张，PPT共一百二十九页，创作于2022年6月102例2华津机器制造厂专为拖拉机厂配套生产柴油机。今年头四个月收到的订单数量分

41、别为2500台，4500台，2000台，5000台柴油机。该厂正常生产每月可生产柴油机3000台，利用加班还可以生产1500台。正常生产成本为每台5000元，加班生产还要追加1500元成本，库存成本为每台每月200元。华津厂如何组织生产才能使生产成本最低？假设第一月初和第四月末库存为0变量意义(生产成本/台、能力）xi第i月正常生产台数(5000、3000)yi第i月加班生产台数(6500、1500)zi第i月月初库存(200/月.台)需求2500、4500、2000、5000第一百零二张，PPT共一百二十九页，创作于2022年6月103设xi为第i月正常生产的柴油机数，yi为第i月加班生产的

42、柴油机数，zi为第i月月初柴油机的库存数。第一百零三张，PPT共一百二十九页，创作于2022年6月104min=5000*(x1+x2+x3+x4)+6500*(y1+y2+y3+y4)+200*(z2+z3+z4);x1+y1-z2=2500;x2+y2+z2-z3=4500;x3+y3+z3-z4=2000;x4+y4+z4=5000;x1=3000; x2=3000; x3=3000; x4=3000; y1=1500; y2=1500; y3=1500; y4=1500;一月二月三月四月正常生产台数3000300030003000加班生产台数0100001000月初库存数量050001

43、000第一百零四张，PPT共一百二十九页，创作于2022年6月105例3 某部门在今后5年内连续给以下项目投资： 项目A，第一年至第四年每年年初投资，次年末回收本利115%； 项目B，第三年初投资，第五年末回收本利125%，最大投资额 不超过4万元； 项目C，第二年初投资，第五年末回收本利140%，最大投资额 不超过3万元； 项目D，五年内每年初可购买公债，当年末归还，并加利息6%。 该部门现有资金 10万元，问该如何确定投资方案，使第五年末拥有的资金本利和最大？12345Ax1Ax2Ax3Ax4ABx3BCx2CDx1Dx2Dx3Dx4Dx5D第一百零五张，PPT共一百二十九页，创作于202

44、2年6月106第一年第二年第三年第四年第五年第一百零六张，PPT共一百二十九页，创作于2022年6月107max=1.15*x4A+1.4*x2C+1.25*x3B+1.06*x5D;x1A+x1D=100000;x2A+x2C+x2D=1.06*x1D;x3A+x3B+x3D=1.06*x2D+1.15*x1A;x4A+x4D=1.06*x3D+1.15*x2A;x5D=1.06*x4D+1.15*x3A;x3B=40000;x2C=3000;50*x1 +60*x2 +20*x3+10*x4 =55;400*x1 +200*x2 +300*x3+500*x4 =800; Global op

45、timal solution found. Objective value: 10.00000 Total solver iterations: 0 Variable Value Reduced Cost X1 0.000000 10.66667 X2 0.000000 3.333333 X3 3.333333 0.000000 X4 0.000000 1.333333用Lingo求解第一百零九张，PPT共一百二十九页，创作于2022年6月110例5：产品配套问题 某厂生产一种产品，由两个B1 零件和三个B2零件配置组装而成。该厂有A1、A2、A3三种机床可加工上述两种零件，每种机床的台数以及

46、每台机床每个工作日全部用于加工某一种零件的最大产量（即生产率：件/日）见下表。试求该产品产量最大的生产方案。机床生产率（件/日）机床数量机床类型零件B2零件B118104A3354520302A23A1难点：1) 同一台机床加工零件B1和 B2的时间分配；2)零件B1和 B2的配套问题，2:3构成一件产品。第一百一十张，PPT共一百二十九页，创作于2022年6月111解：（1）决策变量 根据题意，设每台Ai (i=1,2,3)机床每个工作日加工Bj(j=1,2)零件的时间为xij(工作日)；Z为零件B1和 B2按2:3比例配套的产品数量（套/日）。（2）约束条件 工时约束： 机床A1：x11+

47、 x12=1 机床A2：x21+ x22=1 机床A3：x31+ x32=1 配套约束： 零件B1的产量：320 x112 35 x21 4 10 x31 零件B2的产量：330 x122 45 x22 4 18 x32第一百一十一张，PPT共一百二十九页，创作于2022年6月112非负约束 xij 0 (i=1,2,3；j=1,2) （3）目标函数 max Z=f第一百一十二张，PPT共一百二十九页，创作于2022年6月113设每台Ai (i=1,2,3)机床每个工作日加工Bj(j=1,2)零件的时间为xij(工作日)；Z为零件B1和 B2按2:3比例配套的产品数量（套/日）。 max Z=

48、f x11+ x12=1 x21+ x22=1 x31+ x32=1 xij 0 (i=1,2,3；j=1,2) 第一百一十三张，PPT共一百二十九页，创作于2022年6月114 max=f;x11+x12=1;x21+x22=1;x31+x32=1;f=30*x11+35*x21+20*x31;f=70;x2+x3=60;x3+x4=50;x4+x5=20;x5+x6=30;x6+x1=60;end Global optimal solution found. Objective value: 150.0000 Total solver iterations: 4 Variable Valu

49、e Reduced Cost X1 60.00000 0.000000 X2 10.00000 0.000000 X3 50.00000 0.000000 X4 0.000000 0.000000 X5 30.00000 0.000000 X6 0.000000 0.000000第一百一十七张，PPT共一百二十九页，创作于2022年6月118例7 某快递公司下设一个快件分拣部，处理每天到达和外寄的快件。根据统计资料及经验预测，每天各时段快件数量如表所示时段到达快件数时段到达快件数10:00前500014:00-15:00300010:00-11:00400015:00-16:00400011:

50、00-12:00300016:00-17:00450012:00-13:00400017:00-18:00350013:00-14:00250018:00-19:002500第一百一十八张，PPT共一百二十九页，创作于2022年6月119快件分拣由机器操作，分拣效率为每台500件/h，每台机器操作时需要配一名职工，共有11台机器。分拣部一部分是全日制职工，上班时间分别为10:00-18:00,11:00-19:00和12:00-20:00，每人每天工资150元；另一部分是非全日制职工，每天上班5小时，分别是13:00-18:00, 14:00-19:00和15:00-20:00，每人每天工资80元。快件处理的规则是从每整点起可处理该整点前到达的快件。因快件有时间性要求，凡是12:00前到达的快件必须在14:00以前处理完；15:00以前到达的，必须在17: