《第1讲 单纯形法》由会员分享，可在线阅读，更多相关《第1讲 单纯形法（12页珍藏版）》请在金锄头文库上搜索。
1、第一章 线性规划及单纯形法、问题的提出目标函数例题1某公司计划制造I、II两种家电产品。已知各制造一件 时分别占用的设备 A、B 的台时、调试工序时间及每天可用于这两种 家电的能力、各售出一件时的获利情况见下表。问该公司应制造两种项目III每天可用能力设备A0515设备 B6224调试工序115利润21家电各多少件，使获取的利润为最大。建立数学模型：m ax z=2x +x125x1526x+2x2412x+ x50斗约束方程s.t. 012建模练习 1（下料问题）： 某工厂有要做100套钢架，每套由长 2.9米、 2.1米和 1.5米的圆 钢各一根组成，已知原料长 7.4米，问应如何下料使需
2、用的原材料最 省。有一批长度为 180厘米的钢管，需截成 70、 52和 35厘米3种管 料。它们的需求量分别不少于 100、 150和 100根。问应如何下料才 能使钢管的消耗量为最少？建模练习 1答案：min Z =x +x +x +x +x +x +x +x 112345678min Z =5x +6x +23x +5x +24x +6x +23x +5x21232x+ x+ x+ x12342x+ x+3xs.t.23x+x+3x134xx ,x,x ,x,x ,x123456745678100+2x+ x150567+2x+3x +5x100678x08建模练习 2（运输问题）：某地
3、有 3个有色多发金属矿厂，生产同一种金属矿石，分别运往4 四冶炼厂，每个矿厂的产量、每个冶炼厂的需求量、以及每个矿厂 到每个冶炼厂的单位运费见下表，问：应如何安排运输，使总的运费A11.520.33100A270.81.4280A31.20.322.550需求量50708030二、图解法图解法还有几种可能的结果X1建模练习 3（指派问题）：设有四项工作分派给四个人来做，每项工作只能由一个人来做， 每个人只能做一项工作。希望安排人选，发挥各人特长又能使总的效 率最大。各人对各项工作的效率见下表：工作人员、ABCD甲0.60.20.30.1乙0.70.40.30.2丙0.8100.70.3丁0.7
4、0.70.50.41.有无穷多最优解；max z=2x +x12x + x 612x +2x 8s.t. 12x 0122.有无界解；max z= x +x12-2x + x 41 2s.t.彳 x x 0123.无解。 max z=3x +4x12x + x 6 12x 2s.t. 1x 012三、线性规划问题的解max Z=为 c xjjj=1st 1 j=ia x =bij j i(i=1,2,x 0(j=1,2,n)j线性规划的标准型的条件：AX= b； XM 0o 即：约束方程均为等式方程；所有变量均为非负变量。线性规划的规范型的条件：AX= b； XM 0； bM 0,且A中含有
5、一个单位矩阵 Io规范型的作用是我们可以从规范型中马上确定一个基可行解(顶 点)。任何线性规划问题均可化为标准型，但不一定可以化为规范型。 松驰变量，剩余变量，人工变量。可行解：满足全部约束条件的解。最优解：使目标函数达到最优的可行解。基，基变量，非基变量。基解：基变量的唯一解，与非基变量为 0，所组合成的解基可行解：满足非负约束条件的基解。可行基：对应于基可行解的基。凸集：如果集合C中任意两个点X、X2,其连线上的所有点也 都是集合C中的点，称C为凸集。顶点：对点XG C,若在C中找不到两个不同的点X、X2,使 X=aX+(1-a)X2 ( 0VaV 1)成立，则 X 为 C 的一个顶点。定
6、理1：若线性规划问题存在可行解，则可行解域是凸集。定理 2：线性规划问题的每个基可行解对应于其可行解域的 一个顶点。即基可行解是可行解域的顶点，可行解域的顶点是基 可行解。定理 3：若线性规划问题有最优解，一定存在一个基可行解 是最优解（或最优解必在某个顶点上得到）。定理4：可行解域的顶点个数是有限的，不超过Cm个。？2、单纯形法的计算步骤：求初始基可行解，列出初始单纯形表。最优性检验。若R 0,且基变量中不含人工变量时，即得最 优解。当R.0时，如有PjW0,则问题为无界解，计算结束；否则 转下一步。确定入基变量。任选R.行中一个大于0的数所对应的变量为 i入基变量，一般取大数。 0 max
7、 （5 IQ o!jjbialkb确定出基变量。0 min J j la 0 ,= a ikij作旋转变换，并返回第步。例题 1：max z=3x +4x12x + x 612x + 2 x 8s.t. J 1 2x 0解：将原线性规划模型化为规范型如下：max z=3x +4x +0x +0x +0x45 =6123x + x +x123x + 2x+x12 4x +x2x 0, i=l,2.,5i建立单纯形表，并作旋转计算。s.t. =8=35出基c34000CBXx1x2x3X4x5b00X311100660X412010880X5010013-Z3400003X111100660X40
8、1-110220X50100133-Z01-300-183x102-1044X201-11020x5001-111-Z00-2-10-20、目标函数值旋转的原因：用非基变量来表示基变量进行解释。 规律：Max：行大列小（检验数行取大于0中的最大者，0列中取最小者）; Min：行小列小（检验数行取小于0中的最小者，0列中取最小者）。五、单纯形法的进一步讨论 回顾已学过的单纯形法的特点：从某一规范形出发，因为规范型可立即确定出一个基可行解。 根据检验数确定入基变量。根据0 规则确定出基变量。旋转运算（初等行变换），解出新的基可行解（表现形式为新 的规范型）。例题：m inZ=x +6x -7x -
9、4x +xl 23455x -4x +10x +x +x =6123 4 5s.t. 0, i=1,2.,5如何找出该线性规划问题的初始基。2x35-X + X +x=623s.t. 0, i=l,2.,5ix -10x+5x -3x =-121345s.t. 0, i=1,2.,5i1、人工变量法（包括两阶段法、大M法）最优解中，人工变量取值必须为 0。例题：max z=-3x +x13x + x +x 1s.t. q 1233x +x =923x 0, i=1,2,3i化为规范型：max z=-3x +x +0x +0x -Mx -Mx134567x + x +x +x= 41234-2x
10、 +x - x -x +x =1s.t. q 123563x +x+x =9237x 0, i=1,2,.,7i大M法添加人工变量后，希望人工变量等于 0，为此需要人工变量对目 标函数产生影响，一般设人工变量在目标函数中的系数为 M（ min 型）或者一M （max型）。两阶段法在 M 法便于手工计算，但不便于计算机计算，为此，提出两阶 段法。第一阶段：希望人工变量等于 0，构造仅含人工变量的目标函数 并要求实现最小化。第二阶段：将第一阶段计算得到的最终表，去掉人工变量，将目 标函数换回原问题的目标函数，作为第二阶段计算的初始表，继续单 纯形法，直至求到最优解。例题见教材 P3233。2、单纯形表中解的性质判断退化解在确定换出变量时，如果两个e值相等，就会出现退化解，此时, 下一表的基可行解中至少一个基变量为 0。无可行解当求解结果中，基变量中仍含有非 0 人工变量时，表明问题无可行解。C1c1c2 cnCXxx xx xbeBB12mm+1ncx100aabei11,m+11n11cx010aabe222,m+12n22 cx001a *abemmm,m+1mnmm-ZRRRRR-Zi2mm+1n0-惟一最优解 Rj0(j=m+1,n)； 片工。(i=1,m)。条件表示任何再入基和出基过程都会使其目标值劣化。 无穷最优解 RW0 (j=m+1,n)； 包鼻。(i=1
