《第4章--确定性决策——线性规划初步解析课件》由会员分享，可在线阅读，更多相关《第4章--确定性决策——线性规划初步解析课件（87页珍藏版）》请在金锄头文库上搜索。
1、第第4 4章章 确定性决策确定性决策线性规线性规划初步划初步pp线性规划问题线性规划问题pp线性规划模型线性规划模型pp线性规划的图解线性规划的图解pp可行域的性质可行域的性质pp线性规划的基本概念线性规划的基本概念pp基础解、基础可行解基础解、基础可行解pp单纯形表单纯形表pp线性规划的矩阵表示线性规划的矩阵表示线性规划问题n生产计划问题n配料问题n背包问题n运输问题n指派问题1. 生产计划问题（Production Planning）产品甲产品乙产品丙产品丁设备能力（小时）设备A1.51.02.41.02000设备B1.05.01.03.58000设备C1.53.03.51.05000利润
2、（元/件）5.247.308.344.18某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占有的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：求使得总利润最大的生产计划。产品甲产品乙产品丙产品丁设备能力（小时）设备A1.51.02.41.02000设备B1.05.01.03.58000设备C1.53.03.51.05000利润（元/件）5.247.308.344.18设四种产品的产量分别为x1，x2，x3，x4，总利润为z，线性规划模型为：max z=5.24x1+7.30 x2+8.34x3+4.18x4s.t. 1.5x1+1.0
3、 x2+2.4x3+1.0 x42000 1.0 x1+5.0 x2+1.0 x3+3.5x48000 1.5x1+3.0 x2+3.5x3+1.0 x45000 x1, x2, x3, x40目标函数约束条件变量非负约束这个问题的最优解为：x1=294.12件，x2=1500件，x3=0，x4=58.82件最大利润为：z=12737.06元。问题：三个约束条件可以改为等式吗？2. 配料问题（Material Blending）某工厂要用四种合金T1、T2、T3、T4为原料，经熔炼成为新的不锈钢G。这四种原料含铬（Cr）、锰（Mn）和镍（Ni）的含量（），这四种原料的单价以及新的不锈钢G所要求
4、的Cr、Mn、Ni的最低含量（）如下表：T1T2T3T4GCr3.214.532.191.763.20Mn2.041.123.574.332.10Ni5.823.064.272.734.30单价（元/公斤）115978276要求配100公斤不锈钢G，并假定在配制过程中没有损耗。求使得总成本最低的配料方案。T1T2T3T4GCr3.214.532.191.763.20Mn2.041.123.574.332.10Ni5.823.064.272.734.30单价（元/公斤）115978276min z=115x1+97x2+82x3+76x4s.t. 0.0321x1+0.0453x2+0.0219
5、x3+0.0176x43.20 Cr的含量下限约束 0.0204x1+0.0112x2+0.0357x3+0.0433x42.10 Mn的含量下限约束 0.0582x1+0.0306x2+0.0427x3+0.0273x44.30 Ni的含量下限约束 x1+x2+x3+x4=100 物料平衡约束 x1, x2, x3, x40设四种原料分别选取x1，x2，x3，x4公斤，总成本为z。这个问题的最优解为：x1=26.58, x2=31.57, x3=41.84，x4=0（公斤）, 最低成本为z=9549.87元。问题：如果某一种成分的含量既有下限，又有上限怎么办？3. 背包问题（Knapsack
6、 Problem）一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价格如下表：物品1物品2物品3重量（公斤/件）104120价值（元/件）177235求背包中装入每种物品各多少件，使背包中物品总价值最高。设三种物品的件数各为x1，x2，x3件，总价值为z。max z=17x1+72x2+35x3s.t. 10 x1+41x2+20 x350 x1，x2，x30 x1，x2，x3为整数这是一个整数规划问题（Integer Programming）。这个问题的最优解为： x1=1件，x2=0件，x3=2件，最高价值z=87元物品1物品2物品3重量（公斤/件）10
7、4120价值（元/件）1772354. 运输问题（Transportation）某种物资从两个供应地A1，A2运往三个需求地B1，B2，B3。各供应地的供应量、各需求地的需求量、每个供应地到每个需求地每吨物资的运输价格如下表：运价（元/吨）B1B2B3供应量（吨）A123535A247825需求量（吨）10302060求总运费最低的运输方案。运价（元/吨）B1B2B3供应量（吨）A123535A247825需求量（吨）10302060A1A2B3B2B135吨25吨10吨30吨20吨235478运价（元/吨）B1B2B3供应量（吨）A123535A247825需求量（吨）10302060设从两
8、个供应地到三个需求地的运量（吨）如下表：B1B2B3A1x11x12x13A2x21x22x23运价（元/吨）B1B2B3供应量（吨）A123535A247825需求量（吨）10302060min z=2x11+3x12+5x13+4x21+7x22+8x23s.t. x11+x12+x13 =35 供应地A1 x21+x22+x23 =25 供应地A2 x11 +x21 =10 需求地B1 x12 +x22 =30 需求地B2 x13 +x23 =20 需求地B3 x11, x12, x13, x21, x22, x230 运量（吨）B1B2B3供应量（吨）A130535A2101525需求
9、量（吨）10302060这个问题的最优解表示如下：最小总运费为：z=330+55+410+815=275元A1A2B3B2B135吨25吨10吨30吨20吨23547830吨5吨10吨15吨5. 指派问题（Assignment Problem）有n项任务由n个人完成，每项任务交给一个人，每人都有一项任务。由i个人完成j项任务的成本（或效益）为cij。求使总成本最小（或总效益最大）的分配方案。设：张、王、李、赵四位老师被分配教语文、数学、物理化学四门课程，每位老师教一门课，每门课由一位老师教。根据这四位老师以往教课的情况，他们分别教四这门课程的平均成绩如下表。要求确定哪一位老师上哪一门课，使四门
10、课的平均总成绩最高。语文数学物理化学张92688576王82917763李83907465赵93618375设：语文数学物理化学张x11x12x13x14王x21x22x23x24李x31x32x33x34赵x41x42x43x44max z=92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24+ 83x31+90 x32+74x33+65x34+93x41+61x42+83x43+75x44s.t. x11+x12+x13+x14=1 (1) x21+x22+x23+x24=1 (2) x31+x32+x33+x34=1 (3) x41+x42+x4
11、3+x44=1 (4) x11+x21+x31+x41=1 (5) x12+x22+x32+x42=1 (6) x13+x23+x33+x43=1 (7) x14+x24+x34+x44=1 (8) xij=0,1最优解为：x14=1，x23=1，x32=1，x41=1，max z=336即张老师教化学，王老师教语文，李老师教数学，赵老师教语文。语文数学物理化学张0001王0010李0100赵1000语文数学物理化学张92688576王82917763李83907465赵93618375四门课的总分可以达到336分。线性规划模型min(max) z=c1x1+c2x2+cnxns.t. a11
12、x1+a12x2+a1nxn (, )b1 a21x1+a22x2+a2nxn (, )b2 am1x1+am2x2+amnxn (, )bm x1, x2, , xn 0 (, Free)线性规划模型的目标函数必须是变量的线性函数，约束条件必须是变量的线性等式或不等式。如右的问题就不是线性规划问题：线性规划的标准形式目标函数为极小化，约束条件全部为等号约束，所有变量全部是非负的，这样的线性规划模型称为标准形式min z=c1x1+c2x2+cnxns.t. a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1, x
13、2, , xn 0 线性规划模型用矩阵和向量表示min z=c1x1+c2x2+cnxns.t. a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1, x2, , xn 0 线性规划模型用矩阵和向量表示（续）因此，线性规划模型可以写成如下矩阵和向量的形式线性规划模型总结线性规划模型的结构n目标函数 ：max，minn约束条件：,=,n变量符号：0, 0, Free线性规划的标准形式n目标函数：minn约束条件 ：=n变量符号 ：0线性规划问题的标准化n极大化目标函数转化为极小化n小于等于约束条件转化为等号约束n大于
14、等于约束条件转化为等号约束n变量没有符号限制（Free）的标准化n变量小于等于0的标准化 max z=2x1-3x2+x3令 z=-z，z=-2x1+3x2-x3新的目标函数 min z=-2x1+3x2-x3取得极小化的最优解时，这个最优解同时使原目标函数值取得最大化的最优解。但两个问题最优解的目标函数值相差一个负号。极大化目标函数问题转化为极小化目标函数例如，对于以下两个线性规划问题max z=2x1+3x2s.t. x1+x23 x21 (A) x1, x20min z=-2x1-3x2s.t. x1+x23 x21 (B) x1, x20它们的最优解都是x1=2, x2=1，但(A)的
15、最大化的目标函数值为max z=7，(B)的最小化的目标函数值为min z=-7 2x1+3x2-4x35引进松弛变量(Slack variable) x4=5-(2x1+3x2-4x3)，把松弛变量x4加在约束条件左边，就可以将小于等于约束变为等式。 2x1+3x2-4x3+x4=5由此可以知道，松弛变量x40。如果有一个以上小于等于约束，要对于每一个约束引进不同的松弛变量。例如： 2x1+3x2-4x35 3x1-2x2+5x38在两个约束中分别引进松弛变量x4，x50 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 +x5=8小于等于约束条件转化为等号约束将不等式约束变为等式
16、约束。例如： 2x1+3x2-4x35 3x1-2x2+5x38在两个约束的左边分别减去松弛变量x4，x50 2x1+3x2-4x3-x4 =5 3x1-2x2+5x3 -x5=8大于等于约束条件转化为等号约束没有符号限制的变量，用两个非负变量之差表示。例如：max z=x1+2x2-3x3s.t. 2x1+3x2-4x35 3x1-2x2+5x38 x10, x2:free, x30先将目标函数转化为极小化，并在约束中引进松弛变量，把不等式约束变为等式。Min z=-x1-2x2+3x3s.t. 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 -x5=8 x10, x2:free, x3, x4, x50变量没有符号限制(Free)的标准化Min z=-x1-2x2+3x3s.t. 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3-x5=8 x10, x2:free, x3, x4, x50然后，令x2=x2-x2”，其中x2,x2”0。代入模型，消去x2Min z=-x1-2(x2-x”2)+3x3s.t. 2x1+3(x2-x”2)-4x3+x4 =5 3x
