下载文档原格式
单纯形法和大M法都是线性规划中的求解方法。
单纯形法是一种在约束条件下寻找最优解的方法。
它通过不断地迭代和转换，寻找使目标函数值最大或最小的解。
单纯形法适用于具有线性约束和线性目标函数的优化问题。
大M法是一种处理线性规划问题的方法，当约束条件中存在“≤”的不等式约束时，可以用大M法来处理。
大M法通过引入一个非常大的数M，将原问题转化为标准形式，从而可以利用单纯形法进行求解。
大M法的关键在于如何选择合适的M值，以保证原问题的约束条件得以满足，并且目标函数取得最大或最小值。
综上所述，单纯形法和大M法都是解决线性规划问题的方法，其中单纯形法适用于具有线性约束和线性目标函数的优化问题，而大M 法则适用于处理含有“≤”的不等式约束的问题。
单纯形法第⼆章单纯形法2.1 单纯形法原理（⼤M法）例3 min z＝4x1＋3x2＋8x3x1＋x3≥2x2＋2x3≥5x j≥0（j=1，2，3）⼀、构造初始可⾏基（m×m单位阵）每个约束都有⼀个系数为+1的独有变量（基变量）1．引⼊附加变量，化为标准型（⾸先变为b≥0）x1＋x3－x4＝2x2＋2x3－x5＝5x j≥0（j=1，2，...,5）（x4、x5为附加变量）min z＝4x1＋3x2＋8x3＋0x4＋0x5假设化为标准型后,仍⽆初始可⾏基2. 若约束中附加变量系数为-1或原约束为等式，必须引⼊⼈⼯变量x1＋x3－x4＋x6＝2 ① (基变量为x6)x2＋2x3－x5＋x7＝5 ② (基变量为x7)x j≥0（j=1，2，...,7）（x6、x7为⼈⼯变量）⼈⼯变量>0时，约束被篡改3. ⽬标函数中附加变量系数为0，⽽⼈⼯变量系数为Mmin z＝4x1＋3x2＋8x3＋0x4＋0x5＋M x6＋M x7③M——罚因⼦（很⼤正数）⼤M法——罚函数法⼆、求出⼀个基本可⾏解1. ⽤⾮基变量表⽰基变量和⽬标函数由①：x6＝2－x1－x3＋x4④由②：x7＝5－x2－2x3＋x5⑤将④、⑤代⼊③：z＝(4-M)x1＋(3-M)x2＋(8-3M)x3＋M x4＋M x5＋7M ⑥检验数σj= ⑥式中各⾮基变量x j的系数，z＝z0＋∑σ∈Jj jj x（J为⾮基变量下标的集合）基变量的检验数＝02、求出⼀个基本可⾏解及相应z值令各⾮基变量为0，x1＝x2＝x3＝x4＝x5＝0由④、⑤、⑥得x6＝2，x7＝5，z＝7M三、最优性检验（求min）1．最优性检验的依据——检验数σｊ2．最优解判别定理：若在极⼩化问题中，对于某个基本可⾏解，所有检验数σｊ≥0，且⼈⼯变量为0，则这个基本可⾏解是最优解。
例3中，σ１＜0，σ２＜0，σ３＜0，需继续迭代3．⽆穷多组最优解判别定理：若在极⼩化问题中，对于某个基本可⾏解，所有检验数σｊ≥0，⼜有某个⾮基变量检验数为0，且⼈⼯变量为0，则线性规划问题有⽆穷多组最优解。
一、线性规划问题约束条件：不超过各工序可用时间非负约束1）0.7x1+x2≤6302) x1,x2≥0图解法：设定Z值然后带入值取各个公式的两个端点描点画图二、单纯形法步骤：标准化目标函数最大约束条件等式化≤引入松弛变量S ≥剩余变量e 右端非负Max Z=x1+x2. x1+2x2≤6 ,2x1+x2≤16,x1,x2≥0z−x1−x2=0 x1+2x2+s1=6 ,2x1+x2+s2=16 ,x1,x2,s1,s2 ≥0两组约束四个变量故有2个非基本变量，2个基本变量进入变量与离开变量的确定从非基本变量中找一个进入变量（进入到基本变量中），从基本变量中找一个离开变量（作为非基本变量）在Row 0 中，从左往右选择非基本变量中系数最小的作为进入变量（前面化为单位矩阵，为最优解）大M法：步骤同上，约束等式化≤引入松弛变量S ≥剩余变量e+人工变量a（=也是加a）min z=4x1+x2. s.t 3x1+x2=3 ,4x1+3x2≥6, x1+2x2≤4,x1,x2≥0 max z=−4x1−x2−Ma1−Ma2(M=100) s.t 3x1+x2+a1=3 , 4x1+3x2−e2+a2=6, x1+2x2+s3=4,x1,x2,e2,s3,a1,a2 ≥0M假定为无限大正值1.判断是否为最优解ROW a1 a2 系数化为0. 由于此时ROW 0 非基本变量的系数不全为非负数，因此，并非最优解。
进入变量与离开变量的确定重复以上步骤化为单位矩阵取得最优解。
两阶段法：第一阶段：引入人工变量a1,a2 min z=a1+a2 , max z=−a1−a2 min z=4x1+x2, s.t. 3x1+x2=3 ,4x1+3x2≥6 ,x1+2x2≤4,x1,x2≥0 max z=−a1−a2 s.t.3x1+x2+a1=3,4x1+3x2−e2+a2=6x1+2x2+s3=4,x1,x2,e2,s3,a1,a2≥0经过前面变换单位矩阵得到最优解的单纯形表第二阶段：min z=4x1+x2→max z=−4x1−x2将第一阶段最后最优解的单纯形表Row 0 替换为z+4x1+x2=0的系数然后重复上述步骤得到最优解。
第一章线性规划及单纯形方法主要内容线性规划的模型、标准型、图解法、解、单纯形法、大M法、两阶段法讲授重点线性规划问题的解、单纯形法、大M法、两阶段法教学方法讲授式、启发式本章知识结构图第一节线性规划问题及其数学模型一、问题的提出在生产和经营等管理工作中，需要经常进行计划或规划，即：在现有各项资源条件的限制下，如何确定方案，使预期目标达到最优。
看如下两个例子：例1美佳公司计划制造Ⅰ、Ⅱ两种家电产品。
已知各制造一件时分别占用的设备A,B的台时、调试时间、调试工序及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1—1所示。
问该公司应制造两种家电各多少件，使获取的利润为最大。
表 1—1I Ⅱ每天可用能力设备A(h) 设备B(h) 调试工序(h) 06152l15245利润(元) 2 1例2 捷运公司拟在下一年度的l～4月的4个月内需租用仓库堆放物资。
已知各月份所需仓库面积数列于表1—2。
仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1—3。
租借仓库的合同每月初都可办理，每份合同具体规定租用面积数和期限。
因此该厂可根据需要，在任何一个月初办理租借合同。
每次办理时可签一份，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。
表 1-2 单位：100m22二、线性规划问题的数学模型例1中先用变量x 1和x 2分别表示美佳公司制造家电I 和Ⅱ的数量。
这时该公司可获取的利润为(2x 1+x 2)元，令z=2x 1+x 2，因问题中要求获取的利润为最大，即max z 。
家电Ⅰ、Ⅱ的制造件数受设备A 、B 和调试工序能力的能力限制，同时家电Ⅰ、Ⅱ制造数量不可能为负值。
由此例1的数学模型可表为：目标函数 212max x x z += 约束条件⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤)1.1(0,)1.1(5)1.1(2426)1.1(1552121212d x x c x x b x x a x例2中若用变量x ij 表示捷运公司在第i(i=1，…，4)个月初签订的租借期方ｊ(ｊ＝1，…，4)个月的仓库面积的合同(单位为lOOm ２)。
