第一章 线性规划与单纯形方法 1.ppt

下载

下载

32积分

40积分

下载

40积分

VIP价：32积分

运筹学 OPERATIONAL RESEARCH 燕山大学经济管理学院 运筹学课程教学课题组编制 * 第一章 线性规划及单纯形法 第一节 线性规划问题及其数学模型 一、线性规划问题的提出 二、线性规划问题与模型的建立举例 三、线性规划的数学模型 四、线性规划模型的应用 五、线性规划问题的标准形式 一、线性规划问题： 在既定的资源限制条件下，如何通过统筹安排，改进生产组织或计划，合理安排人力、物力资源，组织生产过程，使总的经济效益为最好。 规划问题—— 返回 Ⅰ　　Ⅱ 每天可用能力 设备A 0 5 15 设备B 6 2 24 调试工序 1 1 5 利润 2 1 二、举例 例1 生产计划问题 两种家电各生产多少, 可获最大利润? 5x2  15 6x1 + 2x2  24 x1 + x2  5 x1，x2  0 max Z= 2x1 +x2 解:设两种家电产量分别为变量x1 ， x2 转到 例2 求：最低成本的原料混合方案 原料\维生素 A B Ｃ 每单位成本 1 4 1 0 2 2 6 1 2 5 3 1 7 1 6 4 2 5 3 8 维生素最低含量 12 14 8 解：设每单位添加剂中原料i的用量为xi(i =1,2,3,4) minZ= 2x1 + 5x2 +6x3+8x4 4x1 + 6x2 + x3+2x4 12 x1 + x2 +7x3+5x4 14 2x2 + x3+3x4  8 xi  0 (i =1,…,4) 返回 转到 三、线性规划模型特点 决策变量：向量(x1… xn)T 决策人要考虑和控制的因素非负 约束条件：线性等式或不等式 目标函数：Z=ƒ(x1 … xn) 线性式，求Z极大或极小 （一）一般式 Max(min)Z=C1X1+ C2X2+…+CnXn a11X1+ a12X2+…+ a1nXn (=, )b1 a21X1+ a22X2+…+ a2nXn (=, )b2 … … … am1X1+ am2X2+…+ amnXn (=, )bm Xj 0(j=1,…,n) 目标函数 价值系数 技术系数 右端项常数 决策变量 （二）隐含的假设 比例性：决策变量变化引起目标的改变量与决策变量改变量成正比 可加性：每个决策变量对目标和约束的影响独立于其它变量 连续性：每个决策变量取连续值 确定性：线性规划中的参数aij , bi , ci为确定值 返回 四、线性规划模型的应用 市场营销 生产计划制定 库存管理 运输问题 财政、会计 人事 设备管理 城市管理 返回 例：某工厂在计划期内要安排两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗及资源限制如下表所示： 该厂每生产一单位产品Ⅰ可获利50元，每生产一单位产品Ⅱ可获利100元，两种产品应分别生产多少？ （一）生产计划问题 产品Ⅰ 产品Ⅱ 资源限制 设备 1 1 300台时 原料A 2 1 400 原料B 0 1 250 获利 50 100 解：设x1, x2为决策变量， x1为生产产品Ⅰ的数量， x2为生产产品Ⅱ的数量。 max Z=50x1+100x2 x1+x2  300 2x1 +x2  400 x2  250 x1  0, x2  0 设备 产品 设备有效台时 设备加工费 Ⅰ Ⅱ Ⅲ A1 A2 B1 B2 B3 5 7 6 4 7 10 9 8 12 11 6000 10000 4000 7000 4000 原料费 售价 （41页例10）试安排获利最多的生产计划。 Max Z= ()(x11 + x12+ x13 + x14+ x15+ x16) + ()(x21 +x22) +() x3 (5x11+5 x12+ 5x13+ 10x21)（7 x14 +7 x15 + 7x16 +9 x22+12 x3）（ 6 x11 + 6x14 + 8x21 +8 x22）（ 4 x12 + 4x15 + 11x3）（7 x13+ 7x16 ） 5x11+5 x12+ 5x13+ 10x21  6000 7 x14 +7 x15 + 7x16 +9 x22+12 x3  10000 6 x11 + 6x14 + 8x21 +8 x22 4000 4 x12 + 4x15 + 11x3  7000 7 x13+ 7x16  4000 xij  0 （二）配料问题 例： 湖景医院的营养师正准备为刚做完手术的儿科小患者提供牛奶配方的营养品以加强其体力恢复。营养品有三种可能的成分构成：鸡蛋奶油冻、冰激淋、奶油糖果味糖浆。三种营养品所含的营养、营养成分的限制、成本等资料如下表所示，在成本最小的情况下，用多少单位的三种成分混合才能满足表中要求做成牛奶配方的营养品？ A B C 营养限制量 胆固醇 50 150 90  175 饱和脂肪 0 100 50  150 蛋白质 70 10 0  200 热量 30 80 200  100 成本 15 25 10 （美分） 解：设牛奶配方的营养品中含鸡蛋奶油冻、冰激淋、奶油糖果味糖浆的数量分别为x1、x2、x3 minZ= + + 50x1 + 150x2 + 90 x3  175 100x2 + 50x3 150 70x1+ 10 x2 200 30x1 + 80x2 + 200 x3 100 xi  0 (i =1,…,4) （三）换班问题(46页14题) 例：某昼夜服务的公交线路，每天各时间段内所需要的司机和乘务员数如下表。设司机和服务员分别在各时间段一开始时上班，并连续工作8小时，问该公交路线怎样安排司机和乘务员，才能既满足工作需要又配备最少的司机和乘务员？ 班次 时间 所需人数 1 6：00-10：00 60 2 10：00-14：00 70 3 14：00-18：00 60 4 18：00-22：00 50 5 22：00- 2：00 20 6 2：00- 6：00 30 解：设xi为第i班开始上班的人数。 minZ= x1 + x2 +x3+x4+x5+x6 x1 + x6  60 x1 + x2  70 x2+ x3  60 x3 + x4  50 x4 + x5  20 x5 +x6  30 xi  0 (i =1,…,6) 例：捷运公司拟在下一年度的1-4月的4个月内需租用仓库堆放物资，已知各月所需仓库面积入表一。仓库租借费用随合同期限而定，合同期越长，折扣越大，具体见表二。租借仓库的合同每月初都可办理，每份合同具体规定租用面积数和期限。该厂可在任何一月办理租借合同，每次办理一份或若干份均可。为使租借费用最小，公司应如何选择签订合同的最优决策？ minZ= 2800（ x11 + x21 +x31+x41 ） +4500（ x12 + x22+x32）+6000（ x13 + x23 ）+7300x14 x11 + x12 +x13+x14 15 x12 + x13 +x14+x21 +x22+x23  10 x13 + x14 +x22+x23 +x31+x32  20 x14 + x23 +x32+x41  12 xij  0 (i =1,…,4; j =1,…,4) （四）运输问题 仓库\工厂 1 2 3 库存 甲 2 1 3 50 乙 2 2 4 30 丙 3 4 2 10 需求 40 15 35 求最小运费的运输方案 设xij为i 仓库运到 j工厂的原棉数量(i ＝1，2，3， j ＝1，2，3) minZ= 2x11 + x12+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33 x11 +x12+x13  50 x21+x22+x23  30 x31+x32+x33  10 x11 +x21+x31 = 40 x12 +x22+x32 = 15 x13 +x23+x33 = 35 xij  0 要解决的问题的目标可以用数值指标反映 对于要实现的目标有多种方案可选择 有影响决策的若干约束条件 返回 五、线性规划的标准形式 （一）一般式 （二）矩阵式 （三）向量式 （四）化标准形式 返回 (一) 一般型 MaxZ=C1X1+ C2X2+…+CnXn a11X1+ a12X2+…+ a1nXn =b1 a21X1+ a22X2+…+ a2nXn =b2 … … … … am1X1+ am2X2+…+ amnXn =bm Xj 0(j=1,2,…,n) 其中 bi 0 (i=1,2,…,m) 返回 (二) 矩阵型 maxZ=CX AX=b X 0 P1 P2 ……… Pn a11 a12 ……… a1n 其中 A= a21 a22 ……… a2n ………………… am1 am2 ………amn … X1 X= X2 Xn C=(C1 C2 …Cn ) b1 b= b2 bm … 返回 (三) 向量型 X1 AX=(P1 P2 …Pn ) X2 = b Xn … P1 X1+ P2 X2 + … +Pn Xn=b 返回 (四) 化标准型 1. 约束条件 3. 变量 2. 目标函数 返回 4. 右端项系数 1. 约束条件 例1 maxZ=2X1+ X2 +0·X3 +0·X4+0·X5 5x2  15 6x1 + 2x2  24 x1 + x2  5 xi 0 +X3 =15 +X4 =24 +X5 = 5 松弛变量 例2 minZ=2X1+ 5X2+6X3 +8X4 返回 4x1 + 6x2 + x3+2x4 12 x1 + x2 +7x3+5x4 14 2x2 + x3+3x4  8 xi  0 (i =1,…,4) - X5 =12 - X6 =14 - X7 =8 剩余变量 7） +0X5+0X6 +0X7 令Z' = -Z 2. 目标函数 x o Z -Z minZ=2X1+ 5X2+6X3 +8X4 maxZ= -2X1 - 5X2 -6X3 -8X4 返回 3. 变量 例 3X1+2X2  8 X1 -4X2 14 X20 令X1= X1'- X1 " 3 X1' -3 X1 " +2X2  8 X1' - X1 " - 4X2  14 X1' , X1" ,X2 0 例 X1+X2  5 -6  X1  10 X20 -6+6  X1+6  10+6 令X1' = X1 +6 0  X1' 16 X1' +X2  11 X1' 16 X1' , X2 0 返回 X1+X2 +X3 -9 -X1-X2 -X3  9 例：将 min Z = -X1+2X2 -3X3 X1+X2 +X3 7 X1 -X2 +X3 2 X1，X20，X3无限制 化为标准型 解：① 令X3 =X4 - X5 ② 加松弛变量X6 ③ 加剩余变量X7 ④ 令Z'= -Z maxZ'= X1 -2X2 +3X4 -3X5 X1 +X2 +X4 -X5 +X6 =7 X1 -X2 +X4 -X5 - X7 =2 X1 , X2 , X4 , … , X7 0 返回 练习： 将minZ= + + 50x1 + 150x2 + 90 x3  175 100x2 - 50x3  -30 70x1+ 10 x2  200 30x1 + 80x2 + 200 x3  100 xi  0 (i =1,2) 化为标准型 研究对象 有一定的人力、财力、资源条件下，如何合理安排使用，效益最高 某项任务确定后，如何安排人、财、物，使之最省 返回 第二节 图解法 一、线性规划问题的可行域与最优解 二、图解法的步骤 三、线性规划问题求解的可能结局 四、图解法的启示 * * AX=b (1) X  0 (2) maxZ=CX (3) 定义1：满足约束(1)、(2)的X=(X1 …Xn)T称为LP问题的可行解，全部可行解的集合称为可行域。 定义2：满足(3)的可行解称为LP问题的最优解 一、线性规划问题的可行域与最优解 * 二、图解法的步骤 建立平面直角坐标系 根据约束条件找出可行域 图示目标函数 确定最优解 * X1+2X2≤6 X1-2X2≥1 Z=X1+X2 X2 X1 X2 X1 X2 X1 * 例1：maxZ=40X1+ 50X2 X1+2X2  30　①　 3X1+2X2  60　② 2X2  24　③ X1 , X2 0 * 例2： maxZ=40X1+ 80X2 X1+2X2  30 ① 3X1+2X2  60 ② 2X2  24 ③ X1 , X2 0 * X1 =6+ +(1-  )·15 X2=12+ +(1-  )· X1 =15-9 X2 =+ (0   1) X= =  +(1- ) maxZ=1200 X1 6 15 X2 12 三、线性规划问题求解的可能结局 * 唯一解 无穷多解 无有限最优解 无可行解 有最优解 无最优解 * 四、两个变量的LP问题的解的启示： (1)可行域为凸多边形。 (2)若有最优解，定可在可行域的顶点得到。 X(1) X(2) 凸多边形 凹多边形 X(1) X(2) (3)可以找到所有的顶点，比较其对应的目标函数值的大小。 第三节 LP问题的几何意义 * 一、LP问题解的概念 二、几个基本定理 * 定义1：满足约束(2)、(3)的X=(X1 …Xn)T称为LP问题的可行解，全部可行解的集合称为可行域。 定义2：满足(1)的可行解称为LP问题的最优解 AX=b (2) X  0 (3) maxZ=CX (1) 返回 * AX=b (2) X  0 (3) maxZ=CX (1) 定义3：基(基阵) ——A（秩为m）中一个子矩阵B是可逆矩阵(满秩子矩阵)，则方阵B称为LP问题的一个基。 定义4：在约束方程中，对应于基B， X=(x1,x2,…,xm,0, …,0)T, 称为LP问题的基解。 定义4：基解——对应于基B ，X= 为AX=b的一个解。 B-1 b 0 * 定义5：基本可行解——基B，基本解X= 若B-1 b0(满足非负约束条件)，称基B为可行基。 最优解、最优基 B-1 b 0 * 例1：Max Z=50x1+100x2 X1+X2 ≤ 300 2X1+X2≤400 X2 ≤250 X1 , X20 X1+ X2 +X3 = 300 2X1+X2 + X4 =400 X2 +X5 =250 Xi0 * X2 X1 A 可行解 可行域 最优解 * 例：给定约束条件 -X3+X4 =0 X2 +X3 +X4 =3 -X1 +X2 +X3+X4 =2 Xj 0 ( j=1,2,3,4 ) 求出基变量是X1 , X3 , X4的基本解，是不是可行解？ * 凸集——D是n维欧氏空间的一个集合 X(1), X(2)∈D,若任一个满足 X= X(1)+(1-) X(2) (0   1) 有X∈D 定义6： X(1) , X(2) , … ,X(k) 是n维欧氏空间中的k个点，若有一组数 µ1 , µ2 , … , µk 满足 0  µi 1 (i=1,… ,k) * 定义7  µ i =1 k i=1 有点 x= µ1 X(1) + … + µk X(k) 则称点X为 X(1) , X(2) , … ,X(k) 的凸组合。 凸组合 凸集D, 点 XD，若找不到两个不同的点X(1) , X(2) D 使得 X= X(1) +(1-  ) X(2) (0< <1) 则称X为 D的顶点。 * 定义3 顶点 * 定理1：若LP问题存在可行解，其可行解域一定是凸集。 定理2：LP问题的基可行解X对应于可行域D的顶点。 可行解 基本解 定理3：可行域有界，最优值必可在顶点得到 LP问题解的性质 若(LP)问题有可行解，则可行解集(可行域)是凸集(可能有界，也可能无界)，有有限个顶点。 * (LP)问题的基本可行解 可行域的顶点。 若(LP)问题有最优解，必可以在基本可行解(顶点)达到。 返回 * 第四节 单纯形法 单纯形法的基本思路：根据线性规划问题的标准，从可行域中某个基可行解（一个顶点）开始，转换到另一个基可行解（顶点），并且使目标函数达到最大值时，线性规划问题就得到了最优解。 * (1) 确定初始基可行解 (2) 判定解是否最优 (3) 由一个基可行解→另一个基可行解。 一、单纯形法的基本思路 * 二、 单纯形法原理 初始基可行解的确定 标准化，加入松弛变量、剩余变量或人工变量，构造m×m单位矩阵。 * x1 +a1 m+1 xm+1 +……+a1 n xn =b1 x2 +a2 m+1 xm+1 +……+a2 n xn =b2 xm +amm+1 xm+1 +……+amn xn =bn 1 0…0 a1m+1 …a1n 0 1…0 a2m+1 …a2n ……………………… 0 0…1 amm+1 …amn A= * 例1：maxZ=2X1 +3X2 X1 +2X2 ≤8 4X1 ≤16 4X2 ≤ 12 X1 ， X2 0 X1 +2X2 +X3 =8 4X1 + +X4 =16 4X2 +X5 =12 X1 … X5 0 1 2 1 0 0 A= 4 0 0 1 0 0 4 0 0 1 X=(0 0 8 16 12)T Z=0 * 例1：minZ=2X1 +3X2 X1 +2X2 ≥8 4X1 ≥16 4X2 ≥ 12 X1 ， X2 0 1 2 -1 0 0 A= 4 0 0 -1 0 0 4 0 0 -1 X=(0 0 -8 -16 -12)T Z=0 X1 +2X2 -X3 =8 4X1 -X4 =16 4X2 -X5 =12 X1 … X5 0 * 例2：minZ=2X1 +3X2 X1 +2X2 ≥8 4X1 ≥16 4X2 ≥ 12 X1 ， X2 0 1 2 -1 0 0 1 0 0 A= 4 0 0 -1 0 0 1 0 0 4 0 0 -1 0 0 1 X=(0 0 0 0 0 8 16 12)T Z=36M X1 +2X2 -X3 +X6 =8 4X1 -X4 +X7 =16 4X2 -X5 +X8 =12 X1 … X8 0 +0X3+0X4+0X5+MX6+MX7+MX8 * 例3：maxZ=2X1 +3X2 X1 +2X2 =8 4X1 ≤16 4X2 ≥ 12 X1 ， X2 0 X1 +2X2 +X5 =8 4X1 +X3 =16 4X2 -X4 +X6 =12 X1 … X6 0 +0X3+0X4-MX5-MX6 1 2 0 0 1 0 A= 4 0 1 0 0 0 0 4 0 -1 0 1 X=(0 0 16 0 8 12)T Z= -20M * 例1：maxZ=2X1 +3X2 X1 +2X2 ≤8 4X1 ≤16 4X2 ≤ 12 X1 ， X2 0 X1 +2X2 +X3 =8 4X1 +X4 =16 4X2 +X5 =12 X1 … X5 0 2. 判定解是否最优(目标函数值是否为最优) 需要计算检验数σj * Z =0 + 2 X1+ 3 X2 X3 =8-( X1+ 2X2 ) X4=16-4X1 X5 =12-4X2 令X1 = X2 =0 X(1) =(0, 0, 8,16, 12)T Z(1) =0 Z=0+2X1+3X2 当X1从0↗或X2从0↗ Z从0↗ * CB (Ci) XB (Xi) b x1 x2 x3 x4 x5 θ 2 3 0 0 0 0 x3 8 1 2 1 0 0 0 x4 16 4 0 0 1 0 0 x5 12 0 4 0 0 1 σ 2 3 0 0 0 * 3.基变换 (1) 决定换入变量： maxσj =σm+k ，则Xm+k 为换入变量 σj>0 (2) 决定换出变量： * 定理2：对X(1)，若有某个非基变量Xm+k→σm+k>0 且相应的Pm+k =(a1m+k ,… ,amm+k )T  0，则原问题无有限最优解。 * σm+k 0 …… …… a1m+k 0 arm+k 1 amm+k 0 初等行变换 Pm+k = … … … … 4. 以arm+k（主元）为中心，换基迭代 * X1 +2X2 +X3 =8 4X1 +X4 =16 4X2 +X5 =12 X1 … X5 0 X3 =8 -X1 -2X2 X4 =16 -4X1 X5 =12- 4X2 Z =0 + 2 X1+ 3 X2 X3 = 2 - X1+1/2X5 X4 =16 -4X1 X2 = 3 -1/4X5 Z =9 + 2 X1 -3/4X2 * CB XB b x1 x2 x3 x4 x5 θ 2 3 0 0 0 0 x3 8 1 2 1 0 0 4 0 x4 16 4 0 0 1 0 _ 0 x5 12 0 4 0 0 1 3 Z=0 σ 2 3 0 0 0 * CB XB b x1 x2 x3 x4 x5 θ 2 3 0 0 0 0 x3 0 x4 0 x5 3 0 1 0 0 1/4 16 4 0 0 1 0 2 1 0 1 0 -1/2 2 4 - σ 2 0 0 0 -3/4 Z=9 x2 3 * CB XB b x1 x2 x3 x4 x5 θ 2 3 0 0 0 0 x3 0 x4 3 x2 2 1 0 1 0 -1/2 8 0 0 -4 1 2 3 0 1 0 0 1/4 4 12 - σ 0 0 -2 0 1/4 Z=13 2 x1 * CB XB b x1 x2 x3 x4 x5 θ 2 3 0 0 0 2 x1 0 x4 3 x2 4 1 0 0 1/4 0 4 0 0 -2 1/2 1 2 0 1 1/2 -1/8 0 σ Z=14 0 0 -1/8 0 x5 三、单纯形法基本步骤 * (1) 确定初始基，初始基本可行解 (3) 若有σk >0，Pk全 0，停， 没有有限最优解； 否则转(4) (2) 对应于非基变量检验数σj全 0。 若是，停，得到最优解； 若否，转(3)。 * θ= min aim+k >0 = bi aim+k br arm+k 定Xr为换出变量，arm+k为主元。 由最小θ比值法求： maxσj =σm+k→Xm+k 换入变量 σj>0 (4) * 转(2) σm+k 0 …… …… a1m+k 0 arm+k 1 amm+k 0 初等行变换 Pm+k = … … … … (5) 以arm+k为中心，换基迭代 * 四、 单纯形表 X1 X2 … Xm Xm+1 … Xm+k … Xn CB XB b C1 C2 … Cm Cm+1 … Cm+k … Cn C1 X1 b1 1 0 … 0 a1m+1 … a1m+k … a1n C2 X2 b2 0 1 … 0 a2m+1 … a2m+k … a2n Cr Xr br 0 0 … 0 arm+1 … arm+k … arn Cm Xm bm 0 0 … 1 amm+1 … amm+k … ann … … … … … … … … … … … … … … z 0 0 … 0 σm+1 … σm+k … σn * 例1：maxZ=50X1 +100X2 X1 +X2 ≤300 2X1 +X2 ≤400 X2 ≤250 X1 ， X2 0 X1 +X2 + X3 =300 2X1 +X2 + X4 =400 X2 + X5 =250 Xi 0 * CB XB b x1 x2 x3 x4 x5 θ 50 100 0 0 0 0 x3 300 1 1 1 0 0 300 0 x4 400 2 1 0 1 0 400 0 x5 250 0 1 0 0 1 250 Z=0 σ 50 100 0 0 0 * CB XB b x1 x2 x3 x4 x5 θ 50 100 0 0 0 0 x3 50 1 0 1 0 -1 50 0 x4 150 2 0 0 1 -1 75 100 x2 250 0 1 0 0 1 - Z=25000 σ 50 0 0 0 -100 * CB XB b x1 x2 x3 x4 x5 θ 50 100 0 0 0 50 x1 50 1 0 1 0 -1 50 0 x4 50 0 0 -2 1 1 0 100 x2 250 0 1 0 0 1 100 Z=27500 σ 0 0 -50 0 -50 * 五、几点说明 （1）非基变量的检验数为0，LP问题有无穷多最优解 例 maxZ=X1 +2X2 X1  4 X2  3 X1+2X2  8 X1 , X2 0 X1 +X3 = 4 X2 +X4 = 3 X1+2X2 +X5= 8 X1 … X5 0 * CB XB b x1 x2 x3 x4 x5 θ 1 2 0 0 0 0 x3 4 1 0 1 0 0 0 x4 3 0 1 0 1 0 0 x5 8 1 2 0 0 1 Z=9 σ 1 2 0 0 0 - 3 4 * CB XB b x1 x2 x3 x4 x5 θ 1 2 0 0 0 0 x3 0 x4 0 x5 2 1 0 0 -2 1 3 0 1 0 1 0 4 1 0 1 0 0 4 - 2 σ 1 0 0 -2 0 Z=6 x2 2 * CB XB b x1 x2 x3 x4 x5 θ 1 2 0 0 0 0 x3 2 x2 0 x5 2 1 0 0 -2 1 3 0 1 0 1 0 2 0 0 1 2 -1 1 3 - σ 0 0 0 0 -1 Z=8 x1 1 * CB XB b x1 x2 x3 x4 x5 θ 1 2 0 0 0 0 x3 2 x2 1 x1 4 1 0 1 0 0 2 0 1 -1/2 0 1/2 1 0 0 1/2 1 -1/2 σ 0 0 0 0 -1 Z=8 x4 0 * X(1)= (2,3) Z(1)=8 X(2)= (4,2) Z(2)=8 无穷多解 * (2) 最小值问题 例： 求 minZ=X1 -X2+X3 -3X5 X2+X3 - X4+2X5 = 6 X1+2X2 -2X4 = 5 2X2 + X4+3X5 +X6 = 8 X1 … X6 0 * CB XB b x1 x2 x3 x4 x5 x6 θ 1 -1 1 0 -3 0 1 x3 6 0 1 1 -1 2 0 1 x1 5 1 2 0 -2 0 0 0 x6 8 0 2 0 1 3 1 σ 0 -4 0 3 -5 0 Z=11 3 - 8/3 * CB XB b x1 x2 x3 x4 x5 x6 θ 1 -1 1 0 -3 0 1 x3 1 x1 0 x6 x5 -3 8/3 0 2/3 0 1/3 1 1/3 5 1 2 0 -2 0 0 2/3 0 -1/3 1 -5/3 0 -2/3 - 5/2 4 σ 0 -2/3 0 14/3 0 5/3 Z=-7/3 * CB XB b x1 x2 x3 x4 x5 x6 θ 1 -1 1 0 -3 0 1 x3 1 x1 -3 x5 x2 -1 1 -2/3 0 0 1 1 1/3 5/2 1/2 1 0 -1 0 0 3/2 1/6 0 1 -2 0 -2/3 σ 1/3 0 0 4 0 5/3 Z=-4 * (3)退化 maxZ=10X1 + 12X2 3X1+4X2 +X3 =6 4X1+ X2 +X4 =2 3X1 +2X2 +X5 =3 X1 …… X50 * 退化解 X *=(0, 3/2, 0, 1/2, 0)T Zmax=18 * 第五节 单纯形法的进一步讨论 (一) 大M法： 判定无解条件：当进行到最优表时，仍有人工变量在基中，且≠0，则说明原问题无可行解。 * 例1： maxZ= 6X1 +4X2 2X1 +3X2  100 4X1 +2X2  120 X1 =14 X2  22 X1 X2 0 * maxZ=6X1+4X2-MX6 -MX7 2X1 +3X2 +X3 =100 4X1 +2X2 +X4 =120 X1 +X6 =14 X2 - X5 +X7 = 22 X1 … X7 0 * CB XB b x1 x2 x3 x4 x5 x6 x7 θ 6 4 0 0 0 -M -M 0 x3 100 2 3 1 0 0 0 0 0 x4 120 4 2 0 1 0 0 0 -M x6 14 1 0 0 0 0 1 0 -M x7 22 0 1 0 0 -1 0 1 Z=-36M σ M+6 M+4 0 0 -M 50 30 14 0 0 - * CB XB b x1 x2 x3 x4 x5 x6 x7 θ 6 4 0 0 0 -M -M 0 x3 72 0 3 1 0 0 -2 0 0 x4 64 0 2 0 1 0 -4 0 6 x1 14 1 0 0 0 0 1 0 -M x7 22 0 1 0 0 -1 0 1 Z=84-22M σ 0 M+4 0 0 -M 24 32 - -6-M 0 22 * CB XB b x1 x2 x3 x4 x5 x6 x7 θ 6 4 0 0 0 -M -M 0 x3 6 0 0 1 0 3 -2 -3 0 x4 20 0 0 0 1 2 -4 -2 6 x1 14 1 0 0 0 0 1 0 4 x2 22 0 1 0 0 -1 0 1 Z=172 σ 0 0 0 0 4 2 10 - -6-M -4-M - * CB XB b x1 x2 x3 x4 x5 x6 x7 θ 6 4 0 0 0 -M -M 0 x5 2 0 0 1/3 0 1 -2/3 -1 0 x4 16 0 0 -2/3 1 0 -8/3 0 6 x1 14 1 0 0 0 0 1 0 4 x2 24 0 1 1/3 0 0 -2/3 0 Z=180 σ 0 0 -4/3 0 0 -10/3-M -M * (二) 两阶段法： 原问题 maxZ= Cj xj j=1 n  xj  0 j=1 n  aij xj =bi ( i=1,2, …,m) * 作辅助问题 minW= yi i=1 m  Xj ， yi  0 j=1 n  aij xj + yi =bi ( i=1,2, …,m) 解题过程： 第1阶段：解辅助问题 当进行到最优表时，①、若W=0, 则得到原问题的一个基本可行解，转入第2阶段。 ②、若W>0, 则判定原问题无可行解。 * 两阶段法原理： (1) 辅助问题的基本可行解X(0) 为最优解，对应最小值=0 则X(0) 的前n个分量是原问题的基本可行解。 (2) 原问题有可行解时，辅助问题最优值 =0 * 总结： (1) LP数学模型及标准型 maxZ=CX AX=b (b0) X0 (2) LP问题解的性质：图解法 * (3) 单纯形法： 1) 标准型中有单位基。 2)标准型中没有单位基，用大M法加人工变量，使之构成单位基。 求maxZ时，目标中－MXj 求minZ时，目标中＋MXj 3) 判定最优解定理： maxZ问题，检验数σ  0 minZ问题，检验数σj 0 * 4) 解的几种情况： 唯一解 无穷多解：最优表中非基变量检验数有为0者。 无界解： max,σj > 0 但Pj  0 min,σj < 0 但Pj  0 无可行解：最优表中人工变量在基中，且≠0。 建模有问题 5) 退化解问题 * * (广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划) (合理下料，配料，“生产计划、库存、劳力综合”) (合理物资库存量，停车场大小，设备容量) (预算，贷款，成本分析，投资，证券管理) (人员分配，人才评价，工资和奖金的确定) (维修计划，设备更新) (供水，污水管理，服务系统设计、运用) * * *