《运筹学02-线性规划的图解法》由会员分享，可在线阅读，更多相关《运筹学02-线性规划的图解法（30页珍藏版）》请在金锄头文库上搜索。
1、12.1 线性规划问题及其数学模型(1) 线性规划问题建模例1、生产组织与计划问题A, B 各生产多少, 可获最大利润?可用资源设备 原料1 原料2A B1 2 2 1 0 1单位利润50 100300台时 400kg 250kg2建立线性规划模型的步骤：1）根据管理层的要求确定决策目标和收集相关 数据。 2）确定要做出的决策，引入决策变量。 3）确定对这些决策的约束条件和目标函数。3例2 合理配料问题求：最低成本的原料混合方案原料 A B 每单位成本1 4 1 0 22 6 1 2 5 3 1 7 1 64 2 5 3 8每单位添 加剂中维生 12 14 8 素最低含量4例3、运输问题工 厂
2、1 2 3 库存仓 1 2 1 3 50 2 2 2 4 30库 3 3 4 2 10需求 40 15 35运输 单价求：运输费用最小的运输方案。5(2) 线性规划问题的特征：l决策变量： 每个问题都用一组决策变量(X1 Xn)表示， 这组决策变量的值都代表一个具体方案。l目标函数：衡量决策方案优劣的函数，它是决策变量的 线性函数，根据问题不同，目标函数实现最大化或最小 化。l约束条件：分为两类1）函数约束，一组决策变量的线性 函数=/=/=一个给定的数（右端项）。2）决策变量约 束。具备以上三个要素的问题就称为 线性规划问题。6目标函数约束条件(3) 线性规划模型一般形式7隐含的假设l比例性
3、：决策变量变化引起目标的改变量与决策变量改 变量成正比l可加性：每个决策变量对目标和约束的影响独立于其它 变量l连续性：每个决策变量取连续值l确定性：线性规划中的参数aij , bi , cj为确定值82.2 线性规划问题的图解法定义1：满足约束(2)的X=(X1 Xn)称为线性规划问题的 可行解，全部可行解的集合称为可行域。定义2：满足(1)的可行解称为线性规划问题的最优解。9x1x2z=20000=50x1 +100x2z=27500=50x1 +100x2z=0=50x1+100 x2z=10000=50x1 +100x2CBAD E例1.目标函数：Max z = 50 x1 + 100
4、 x2 约束条件：s.t. x1 + x2 300 (A)2 x1 + x2 400 (B)x2 250 (C)x1 0 (D)x2 0 (E)得到最优解：x1 = 50， x2 = 250 最优目标值 z = 2750010直观结论n若线性规划问题有解，则可行域是一个凸多边形（ 或凸多面体）；n若线性规划问题有最优解，则q唯一最优解对应于可行域的一个顶点；q无穷多个最优解对应于可行域的一条边；n若线性规划问题有可行解，但无有限最优解，则可 行域必然是无界的；n若线性规划问题无可行解，则可行域必为空集。112.3 线性规划问题的标准形式目标函数约束条件(1) 线性规划模型一般形式12价值系数决
5、策变量技术系数右端常数(2) 线性规划模型标准形式13简记形式(3) 线性规划模型其它形式14矩阵形式价值向量决策向量系数矩阵右端向量15价值向量决策向量右端向量向量形式列向量16对于各种非标准形式的线性规划问题，我们总可 以通过以下变换，将其转化为标准形式:(4) 一般型向标准型的转化l目标函数l目标函数为极小化l约束条件l分两种情况：大于零和小于零l决策变量l可能存在小于零的情况17(4) 一般型向标准型的转化SLP的特点n（1）目标函数取极大n（2）所有约束条件均由等式表示n（3）所有决策变量取非负值n（4）每一约束的右端常数(资源向量的分量 )均为非负值线性规划问题标准形式的特点181
6、.极小化目标函数的问题：设目标函数为Min f = c1x1 + c2x2 + + cnxn 则可以令z -f ，该极小化问题与下面的 极大化问题有相同的最优解，即Max z = -c1x1 - c2x2 - - cnxn 但必须注意，尽管以上两个问题的最优解 相同，但他们最优解的目标函数值却相差一个 符号，即Min f - Max z192、约束条件不是等式的问题：设约束条件为 ai1 x1+ai2 x2+ +ain xn bi可以引进一个新的变量s ，使它等于约束右 边与左边之差s = bi (ai1 x1 + ai2 x2 + + ain xn )显然，s 也具有非负约束，即s0，这时新
7、的约束条件成为ai1 x1+ai2 x2+ +ain xn+s = bi变量 s 称为松弛变量20lMax Z=40X1+ 50X2X1 +2X2 30 s.t 3X1 +2X2 60 引入松弛变量X3、 X4、X5 2X2 24 X1 , X2 0lMax Z=40X1+ 50X2+0 X3 +0 X4+0 X5 X1 +2X2 + X3 30 s.t 3X1 +2X2 + X4 602X2 + X5 24 X1 , X5 021当约束条件为ai1 x1+ai2 x2+ +ain xn bi 时，类似地令s = (ai1 x1+ai2 x2+ +ain xn)- bi 显然，s 也具有非负约
8、束，即s0，这时新的约 束条件成为ai1 x1+ai2 x2+ +ain xn-s = bi变量s称为剩余变量22Max Z=2X1+ 5X2+6X3 +8X44X1+6X2+ X3 +2X4 12 s.t X1+ X2+7X3+5X4 14 2X2+ X3+3X4 8 X1 , , X4 0 引入剩余变量：X5、X6、X7Max Z=2X1+ 5X2+6X3 +8X4 4X1+6X2+ X3 +2X4 - X5 12 s.t X1+ X2+7X3+5X4 - X6 142X2+ X3+3X4 - X7 8 X1 , , X7 0233. 决策变量如果某个变量的约束条件为或者可令或者代入原问题
9、如果某个变量为自由变量（无非负限 制），则可令且24X1+X2 5s.t -6 X1 10X20令 X1 = X1 +6 -6+6 X1+6 10+60 X1 16X1 +X2 11s.t X1 16X1 , X2 0253X1+2X2 8s.t X1 -4X2 14X20, X1 无限制令X1= X1- X1 3 X1 -3 X1 “ +2X2 8s.t X1 - X1 “ - 4X2 14X1 , X1“ ,X2 026例：将线性规划模型 Min Z = -X1+2X2 -3X3X1+X2 +X3 7s.t X1 -X2 +X3 2X1，X20，X3无限制化为标准型四个方面考虑272.4
10、图解法的灵敏度分析灵敏度分析：建立数学模型和求得最优解后，研究 线性规划的一个或多个参数（系数）ci , aij , bj 变化时，对最优解产生的影响。 2.4.1 目标函数中的系数 ci 的灵敏度分析考虑例1的情况， ci 的变化只影响目标函数等值线的斜率， 目标函数 z = 50 x1 + 100 x2 在 z = x2 (x2 = z 斜率为0 ) 到 z = x1 + x2 (x2 = -x1 + z 斜 率为 -1 )之间时，原最优解 x1 = 50，x2 = 100 仍是最优解。n一般情况：z = c1 x1 + c2 x2 写成斜截式 x2 = - (c1 / c2 ) x1 +
11、 z / c2 目标函数等值线的斜率为 - (c1 / c2 ) ，当 -1 - (c1 / c2 ) 0 （*） 时，原最优解仍是最优解。28n假设产品的利润100元不变，即 c2 = 100，代到式（*）并整理得0 c1 100 n假设产品的利润 50 元不变，即 c1 = 50 ，代到式（*）并整理得50 c2 + n假若产品、的利润均改变，则可直接用式（*）来判断。n假设产品、的利润分别为60元、55元，则- 2 - (60 / 55) - 1 那么，最优解为 z = x1 + x2 和 z = 2 x1 + x2 的交点 x1 = 100，x2 = 200 。292.4.2 约束条件
12、中右边系数 bj 的灵敏度分析当约束条件中右边系数 bj 变化时，线性规划的可行域发生变化，可能引起最优解的变化。考虑例1的情况： 假设设备台时增加10个台时，即 b1变化为310，这时可行域扩大，最优解为 x2 = 250 和 x1 + x2 = 310 的交点 x1 = 60，x2 = 250 。变化后的总利润 - 变化前的总利润 = 增加的利润(5060+ 100250) - (50 50+100 250) = 500 ，500 / 10 = 50 元说明在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润，称为该约束条件的对偶价格。30假设原料 A 增加10 千克时，即 b2变化为410，这时可行域扩 大，但最优解仍为 x2 = 250 和 x1 + x2 = 300 的交点 x1 = 50，x2 = 250 。此变化对总利润无影响，该约束条件的对偶价格 为 0 。解释：原最优解没有把原料 A 用尽，有50千克的剩余，因此增 加10千克值增加了库存，而不会增加利润。在一定范围内，当约束条件右边常数增加1个单位时（1）若约束条件的对偶价格大于0，则其最优目标函数值得 到改善（变好）；（2）若约束条件的对偶价格小于0，则其最优目标函数值受 到影响（变坏）；（3）若约束条件的对偶价格等于0，则最优目标函数值不变。
