武汉工程大学 运筹学02-线性规划的图解法

1、2.1 线性规划问题及其数学模型线性规划问题及其数学模型(1) 线性规划问题建模线性规划问题建模例例1 1、生产组织与计划问题、生产组织与计划问题A, B A, B 各生产多少各生产多少, , 可获最大利润可获最大利润? ?可用资源可用资源设备设备原料原料1原料原料2A B1 22 10 1单位利润单位利润50 100300台时台时400kg250kg建立线性规划模型的步骤：1）根据管理层的要求确定决策目标和收集相关数据。2）确定要做出的决策，引入决策变量。3）确定对这些决策的约束条件和目标函数。例例2 2 合理配料问题合理配料问题求：求：最低成本的原料混合方案最低成本的原料混合方案 原料原料

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 素最低含量素最低含量例例3 3、运输问题、运输问题 工工 厂厂 1 2 3 库存库存 仓仓 1 2 1 3 50 2 2 2 4 30 库库 3 3 4 2 10 需求需求 40 15 35运输运输单价单价求：求：运输费用最小的运输方案运输费用最小的运输方案。(2) 线性规划问题的特征：线性规划问题的特征：l决策变量：决策变量： 每个问题都用一组决策变量每个问题都用一组决策变量( (X X1 1 X Xn n) )表示，表示，这组

3、决策变量的值都代表一个具体方案。这组决策变量的值都代表一个具体方案。l目标函数：衡量决策方案优劣的函数，它是决策变量的目标函数：衡量决策方案优劣的函数，它是决策变量的线性函数，根据问题不同，目标函数实现最大化或最小线性函数，根据问题不同，目标函数实现最大化或最小化。化。l约束条件：分为两类约束条件：分为两类1 1）函数约束，一组决策变量的线性）函数约束，一组决策变量的线性函数函数=/=/=/=一个给定的数（右端项）。一个给定的数（右端项）。2 2）决策变量约）决策变量约束。束。具备以上三个要素的问题就称为具备以上三个要素的问题就称为 线性规划问题线性规划问题。0,.21221122222121

4、112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMinMax目标函数目标函数约束条件约束条件(3) 线性规划模型一般形式线性规划模型一般形式隐含的假设隐含的假设n比例性：决策变量变化引起目标的改变量与决策变量改比例性：决策变量变化引起目标的改变量与决策变量改变量成正比变量成正比n可加性：每个决策变量对目标和约束的影响独立于其它可加性：每个决策变量对目标和约束的影响独立于其它变量变量n连续性：每个决策变量取连续值连续性：每个决策变量取连续值n确定性：线性规划中的参数确定性：线性规划中的参数aij , bi , cj为确定值为确定

5、值2.2 线性规划问题的图解法线性规划问题的图解法 20,.1XbAXtsCXZMinMax定义定义1 1：满足约束：满足约束(2)(2)的的X=(X=(X X1 1 X Xn n) )称为线性规划问题的称为线性规划问题的可行解可行解，全部可行解的集合称为，全部可行解的集合称为可行域可行域。定义定义2 2：满足：满足(1)(1)的可行解称为线性规划问题的的可行解称为线性规划问题的最优解最优解。x1x2z=20000=50 x1+100 x2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE例例1.目标函数： Max z =

6、 50 x1 + 100 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 = 27500直观结论直观结论n若线性规划问题有解，则可行域是一个凸多边形若线性规划问题有解，则可行域是一个凸多边形（或凸多面体）；（或凸多面体）；n若线性规划问题有最优解，则若线性规划问题有最优解，则q唯一最优解对应于可行域的一个顶点；唯一最优解对应于可行域的一个顶点；q无穷多个最优解对应于可行域的一条边；无穷多个最优解对应于可行域的一条边；n若线性规

7、划问题有可行解，但无有限最优解，则若线性规划问题有可行解，但无有限最优解，则可行域必然是无界的；可行域必然是无界的；n若线性规划问题无可行解，则可行域必为空集。若线性规划问题无可行解，则可行域必为空集。2.3 2.3 线性规划问题的标准形式线性规划问题的标准形式0,.21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMinMax目标函数目标函数约束条件约束条件(1) 线性规划模型一般形式线性规划模型一般形式价值系数价值系数决策变量决策变量技术系数技术系数右端常数右端常数0,b,bbxxxbxaxaxa

8、bxaxaxabxaxaxatsxcxcxcZMaxm21nmnmnmmnnnnnn0,.21221122222121112121112211(2) 线性规划模型标准形式线性规划模型标准形式简记形式简记形式njxmibxatsxcZMaxjinjjijnjjj, 2 , 10, 2 , 1.11(3) 线性规划模型其它形式线性规划模型其它形式矩阵形式矩阵形式0.XbAXtsCXZMaxncccC21mnmmnnaaaaaaaaaA212222111211nxxxX21价值向量价值向量决策向量决策向量系数矩阵系数矩阵mbbbb21右端向量右端向量ncccC21nxxxX21价值向量价值向量决策向

9、量决策向量mbbbb21右端向量右端向量向量形式向量形式0.1XbxPtsCXZMaxjnjjnjjjjaaaP21列向量列向量对于各种非标准形式的线性规划问题，我们总可对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式以通过以下变换，将其转化为标准形式: :(4) 一般型向标准型的转化一般型向标准型的转化l目标函数目标函数l目标函数为极小化目标函数为极小化l约束条件约束条件l分两种情况：大于零和小于零分两种情况：大于零和小于零l决策变量决策变量l可能存在小于零的情况可能存在小于零的情况(4) 一般型向标准型的转化一般型向标准型的转化SLPSLP的特点的特点n（1 1

10、）目标函数目标函数取极大取极大n（2 2）所有）所有约束条件约束条件均由等式表示均由等式表示n（3 3）所有）所有决策变量决策变量取非负值取非负值n（4 4）每一约束的）每一约束的右端常数右端常数( (资源向量的分资源向量的分量量) )均为非负值均为非负值线性规划问题标准形式的特点线性规划问题标准形式的特点1.1.极小化目标函数的问题：极小化目标函数的问题： 设目标函数为设目标函数为 Min f = c1x1 + c2x2 + + cnxn 则可以令则可以令z z -f-f ，该极小化问题与下面的，该极小化问题与下面的极大化问题有相同的最优解，即极大化问题有相同的最优解，即 Max z = -

11、c1x1 - c2x2 - - cnxn 但必须注意，尽管以上两个问题的最优解但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个相同，但他们最优解的目标函数值却相差一个符号，即符号，即 Min f - Max z2 2、约束条件不是等式的问题：、约束条件不是等式的问题： 设约束条件为设约束条件为 ai1 x1+ai2 x2+ +ain xn bi 可以引进一个新的变量可以引进一个新的变量s s ，使它等于约束右，使它等于约束右边与左边之差边与左边之差 s = bi (ai1 x1 + ai2 x2 + + ain xn ) 显然，显然，s s 也具有非负约束，即也具有

12、非负约束，即s s00， 这时新的约束条件成为这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn+s = bi 变量变量 s s 称为称为松弛变量松弛变量lMax Z=40X1+ 50X2 X1 +2X2 30 s.t 3X1 +2X2 60 引入引入松弛变量松弛变量X3、 X4、X5 2X2 24 X1 , X2 0 0lMax Z=40X1+ 50X2+0 X3 +0 X4+0 X5 X1 +2X2 + X3 30 s.t 3X1 +2X2 + X4 60 2X2 + X5 24 X1 , X5 0 0当约束条件为当约束条件为 ai1 x1+ai2 x2+ +ain xn

13、bi 时，类似地令时，类似地令 s = (ai1 x1+ai2 x2+ +ain xn)- bi 显然，显然，s 也具有非负约束，即也具有非负约束，即s0，这时新的约，这时新的约束条件成为束条件成为 ai1 x1+ai2 x2+ +ain xn-s = bi变量变量s s称为称为剩余变量剩余变量Max Z=2X1+ 5X2+6X3 +8X4 4X1+6X2+ X3 +2X4 12 s.t X1+ X2+7X3+5X4 14 2X2+ X3+3X4 8 X1 , , X4 0 0引入引入剩余变量剩余变量：X5、X6、X7Max Z=2X1+ 5X2+6X3 +8X4 4X1+6X2+ X3 +2

14、X4 - X5 12 s.t X1+ X2+7X3+5X4 - X6 14 2X2+ X3+3X4 - X7 8 X1 , , X7 0 03. 决策变量决策变量如果某个变量的约束条件为如果某个变量的约束条件为jjlx 或者或者jjlx 可令可令jjjlxy或者或者jjjxly代入原问题代入原问题如果某个变量为自由变量（无非负限如果某个变量为自由变量（无非负限制），则可令制），则可令 0,jjjjjxxxxx0jl且且 X1+X2 5s.t -6 X1 10 X2 0 0令令 X1 = X1 +6 -6+6 X1+6 10+6 0 X1 16 X1 +X2 11s.t X1 16 X1 , X

15、2 0 0 3X1+2X2 8 s.t X1 -4X2 14 X2 0,0, X1 无限制无限制 令令X1= X1- X1 3 X1 -3 X1 +2X2 8 s.t X1 - X1 - 4X2 14 X1 , X1 ,X2 0 0例：将线性规划模型例：将线性规划模型 Min Z = -X1+2X2 -3X3 X1+X2 +X3 7 s.t X1 -X2 +X3 2 X1，X2 0，X3无限制无限制 化为标准型化为标准型四个方面考虑四个方面考虑2.4 2.4 图解法的灵敏度分析图解法的灵敏度分析 灵敏度分析：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）ci , aij ,

16、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 + z / c2 目标函数等值线的斜率为 - (c1 / c2 ) ， 当 -1 - (c1

17、/ c2 ) 0 （*） 时，原最优解仍是最优解。n假设产品的利润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 。 2.4.2 约束条件中右边系数约束条件中右边系数 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元利润，称为该约束条件的对偶价格。 假设原料 A 增加