线性规划模型

1、第5章 线性规划模型 4.1 线性规划问题及其数学模型4.2 线性规划的求解方法 4.3 对偶规划及灵敏度分析4.4 应用举例-奶制品的生产与销售例1 生产计划问题美佳公司计划制造和两种家电产品。已知各制造一件时分别占用的设备A，B的台数、调试时间、调试工序、每天可用于这两种家电的能力、各售出一件时的获利情况，如表5.1所示。问该公司应制造两种家电各多少件，才能获取的利润最大？每天可用能力设备A/h0515设备B/h6224调试工序/h115利润/元211个公司 或获利4元/个获利1元/个x1制造家电数量x2制造家电数量获利 2x1 获利 x2 加工能力决策变量 目标函数 每天获利约束条件非负

2、约束 线性规划模型(LP)基本模型例2 运输问题工厂例3 营养问题 某饲养场饲养供实验用的动物。已知动物生长对饲料中的三种营养成份：蛋白质、矿物质和维生素特别敏感。每个动物每天至少需要蛋白质70g，矿物质3g，维生素10mg。该饲养场现有五种饲料，每种饲料10kg的成本如下：饲料A1A2A3A4A5成本27435单位:元每一千克饲料中所含的营养成分表饲 料蛋白质/g矿物质/g维生素/mgA10.300.100.05A22.000.050.10A31.000.020.02A40.600.200.20A51.800.050.08 我们希望确定既能满足动物需求，又使总成本为最低的饲料配方建立相应的数

3、学模型。解: 设动物每天食用的混合饲料中所含的第j种饲料Aj 的数量为xj(kg), 混合饲料的总成本为y, 则上述问题的数学模型为一般的营养问题可叙述如下：所以线性规划问题的数学模型的一般形式为它的变量满足不难看出，上面这些问题虽然各式各样，但它们的数学模型却有相同的数学形式，即求一个线性函数的最大值(或最小值)，而这个线性函数的变量是非负的，满足一组线性等式或不等式。 我们把具有这种模型的问题称为线性规划问题。5.1.2 线性规划模型 线性规划问题的数学模型有许多种，目标函数有求最小值的，有求最大值的；约束条件有的是“”形式的，也有“”或“”形式的。我们希望能把各种不同形式的线性规划问题的

4、数学模型化为一种统一的标准形式，这样只要对标准形式找出一种解法，就可以解决其余不同形式的线性规划问题了。 线性规划问题的数学模型的一般形式 规定下列形式的线性规划问题为标准形式：其中 均为常数，且 线性规划问题标准形式的矩阵表示：其中 求解方法软件实现法X=lp(c,A,b)对偶规划及灵敏度分析9/24/202215例1 美佳公司利用该公司资源生产两种家电产品的线性规划模型为：设y1，y2，y3分别表示设备A、B和调试工序单位时间的价格。则0y1+6y2+y325y1+2y2+y31对生产产品的全部资源的定价。假如另一公司想收购美佳公司的资源，美佳公司出让自己资源的条件是什么？出让代价不低于用

5、同等资源组织生产两种产品所能获得的利润。对生产产品的全部资源的定价。产品的利润产品的利润9/24/202216原问题与对偶问题的数据比较 原问题对偶问题x1x2原关系min wy10515y26224y3115对偶关系max z = min wmax z219/24/202217二、对称形式对偶问题的一般形式定义：满足下列条件的线性规划问题称为具有对称形式：其变量均具有非负约束，其约束条件当目标函数求极大时取“”号，当目标函数求极小时均取“”号。则其对偶问题的一般形式为：若原问题的一般形式为：yi(i=1,2,，m)代表第i种资源的估价。9/24/202218矩阵形式表示的原问题与对偶问题原问

6、题：对偶问题：令ww对偶问题令zz对偶问题的对偶是原问题9/24/202219四、对偶问题的写法在写对偶问题时，要特别注意上表中原问题与其对偶问题的对应关系。9/24/2022202-3 影子价格当线性规划原问题求得最优解xj*( j =1,2,n )时，其对偶问题也得到最优解yi*( i =1,2,m )，且两者的目标函数值相等。即bi：线性规划原问题右端项，代表第 i 种资源的拥有量；yi*：对偶变量，代表在最优资源利用条件下对单位第 i 种资源的估价，称为影子价格。影子价格也称为机会成本，它是根据具体的经济目标、技术水平和资源条件作出的对资源利用的评价市场价格：是资源在市场上流通的实际价

7、格，它由整个社会的经济技术状况决定。返回本章目录9/24/202221根据 求 bi 的偏导数得：这说明，原问题某一约束条件的右边常数bi增加一个单位时，则由此引起最优目标函数值的增加量，就等于与该约束相对应的对偶变量的最优值。这样一来，在有限资源条件下使收益最大化这一类问题中，就可以把对偶变量的最优值，看成是相应资源每一单位对于目标函数的贡献，即这些资源被充分利用时所能带来的收益。从而， yi* 的值就相当于对单位 i 种资源在实现最大利润时的一种价格估计。这种估计是针对具体企业，具体产品而存在的一种特殊价格，称之为影子价格，它与市场价格不同。若仅从经济上考虑，当某种资源的市场价格低于影子价

8、格时，企业就可以考虑买进这种资源；当市场价格高于影子价格时，企业则可以出售这种资源。随着资源的买进卖出，它的影子价格也将随之变化，直到影子价格与市场价格保持同等水平时，才处于平衡状态。9/24/202222影子价格的应用（1）用影子价格判别资源的供求关系如果线性规划的原问题在得到最优解时，某个约束条件为严格的不等式，即最优解中该约束的松弛变量的值大于零，即表明该种资源有剩余，供大于求。增加这种资源时，目标函数值不会有任何改善。如果线性规划的原问题在得到最优解时，某个约束条件为严格的等式，即最优解中该约束的松弛变量的值等于零，即表明该资源恰恰用完。这种资源增加一个单位，目标函数值就改进一个影子价

9、格。由此可见，影子价格大于零，说明资源紧缺；影子价格等于零，说明资源有剩余。影子价格愈大，说明该资源愈紧缺，该种资源每增加一个单位所相应增加的目标函数值愈大。9/24/202223（2）应用影子价格来合理分配资源算出各种资源的影子价格后，可参考影子价格高低顺序合理分配资源，高者优先投资。同时，也可以参考资源的影子价格，合理地确定各种资源的价格。企业生产计划5.4 奶制品的生产与销售 空间层次工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划.时间层次若短时间内外部需求和内部资

10、源等不随时间变化，可制订单阶段生产计划，否则应制订多阶段生产计划.本节课题例1 加工奶制品的生产计划1桶牛奶 3kgA1 12h 8h 4kgA2 或获利24元/kg 获利16元/kg 50桶牛奶 时间480h 至多加工100kgA1 制订生产计划，使每天获利最大 35元可买到1桶牛奶，买吗？若买，每天最多买多少? 可聘用临时工人，付出的工资最多是每小时几元? A1的获利增加到 30元/kg，应否改变生产计划？ 每天：问题1桶牛奶 3kgA1 12h 8h 4kgA2 或获利24元/kg 获利16元/kg x1桶牛奶生产A1 x2桶牛奶生产A2 获利 243x1 获利 164 x2 原料供应

11、劳动时间 加工能力 决策变量 目标函数 每天获利约束条件非负约束 线性规划模型(LP)时间480h 至多加工100kgA1 50桶牛奶 每天基本模型模型分析与假设 比例性 可加性 连续性 xi对目标函数的“贡献”与xi取值成正比 xi对约束条件的“贡献”与xi取值成正比 xi对目标函数的“贡献”与xj取值无关 xi对约束条件的“贡献”与xj取值无关 xi取值连续 A1,A2每千克的获利是与各自产量无关的常数每桶牛奶加工A1,A2的数量, 时间是与各自产量无关的常数A1,A2每千克的获利是与相互产量无关的常数每桶牛奶加工A1,A2的数量,时间是与相互产量无关的常数加工A1,A2的牛奶桶数是实数

12、线性规划模型模型求解 软件实现 LINGO model:max = 72*x1+64*x2;milk x1 + x250;time 12*x1+8*x2480;cpct 3*x1100;end Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.0000

13、00 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000 20桶牛奶生产A1, 30桶生产A2，利润3360元. 结果解释 Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.00

14、0 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000 model:max = 72*x1+64*x2;milk x1 + x250;time 12*x1+8*x2480;cpct 3*x1100;end三种资源“资源” 剩余为零的约束为紧约束（有效约束） 原料无剩余时间无剩余加工能力剩余40结果解释 Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Variable Val

15、ue Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000最优解下“资源”增加1单位时“效益”的增量 影子价格 35元可买到1桶牛奶，要买吗?35 48, 应该买！ 聘用临时工人付出的工资最多每小时几元? 2元！原料增加1单位, 利润增长48 时间增加1单位, 利润增长2 加工能力增长不影响利润Ran

16、ges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable AllowableVariable Coefficient Increase Decrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease MILK 50.00000 10.00000 6.666667

17、TIME 480.0000 53.33333 80.00000 CPCT 100.0000 INFINITY 40.00000 最优解不变时目标函数系数允许变化范围 敏感性分析 (“LINGO|Ranges” ) x1系数范围(64,96) x2系数范围(48,72) A1获利增加到 30元/kg，应否改变生产计划? x1系数由24 3=72增加为303=90，在允许范围内 不变！(约束条件不变)结果解释 Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowabl

18、eVariable Coefficient Increase Decrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease MILK 50.00000 10.00000 6.666667 TIME 480.0000 53.33333 80.00000 CPCT 100.0000 INFINITY 40.00000影子价格有意义时约束右端的允许变化范围 原料最多增加10

19、时间最多增加53 35元可买到1桶牛奶, 每天最多买多少?最多买10桶!(目标函数不变)充分条件 !例2 奶制品的生产销售计划 在例1基础上深加工1桶牛奶 3kgA1 12h 8h 4kgA2 或获利24元/kg 获利16元/kg 0.8kgB1 2h, 3元1kg获利44元/kg 0.75kgB2 2h, 3元1kg获利32元/kg 制订生产计划，使每天净利润最大 30元可增加1桶牛奶，3元可增加1h时间，应否投资？现投资150元，可赚回多少？50桶牛奶, 480h 至多100kgA1 B1，B2的获利经常有10%的波动，对计划有无影响？ 每天销售10kgA1的合同必须满足，对利润有什么影响

20、？1桶牛奶 3kg A1 12h 8h 4kg A2 或获利24元/kg 获利16元/kg 0.8kg B12h, 3元1kg获利44元/kg 0.75kg B22h, 3元1kg获利32元/kg 出售x1 kg A1, x2 kg A2， x3 kg B1, x4 kg B2原料供应 劳动时间 加工能力 决策变量 目标函数 利润约束条件非负约束 x5 kg A1加工B1， x6 kg A2加工B2附加约束 基本模型模型求解 软件实现 LINGO Global optimal solution found. Objective value: 3460.800 Total solver iter

21、ations: 2 Variable Value Reduced Cost X1 0.000000 1.680000 X2 168.0000 0.000000 X3 19.20000 0.000000 X4 0.000000 0.000000 X5 24.00000 0.000000 X6 0.000000 1.520000 Row Slack or Surplus Dual Price 1 3460.800 1.000000 MILK 0.000000 3.160000 TIME 0.000000 3.260000 CPCT 76.00000 0.000000 5 0.000000 44.0

22、0000 6 0.000000 32.00000Global optimal solution found. Objective value: 3460.800 Total solver iterations: 2 Variable Value Reduced Cost X1 0.000000 1.680000 X2 168.0000 0.000000 X3 19.20000 0.000000 X4 0.000000 0.000000 X5 24.00000 0.000000 X6 0.000000 1.520000 Row Slack or Surplus Dual Price 1 3460

23、.800 1.000000 MILK 0.000000 3.160000 TIME 0.000000 3.260000 CPCT 76.00000 0.000000 5 0.000000 44.00000 6 0.000000 32.00000结果解释每天销售168 kgA2和19.2 kgB1， 利润3460.8（元）8桶牛奶加工成A1，42桶牛奶加工成A2，将得到的24kgA1全部加工成B1 除加工能力外均为紧约束结果解释Global optimal solution found. Objective value: 3460.800 Total solver iterations: 2 V

24、ariable Value Reduced Cost X1 0.000000 1.680000 X2 168.0000 0.000000 X3 19.20000 0.000000 X4 0.000000 0.000000 X5 24.00000 0.000000 X6 0.000000 1.520000 Row Slack or Surplus Dual Price 1 3460.800 1.000000 MILK 0.000000 3.160000 TIME 0.000000 3.260000 CPCT 76.00000 0.000000 5 0.000000 44.00000 6 0.00

25、0000 32.00000增加1桶牛奶使利润增长3.1612=37.92增加1h时间使利润增长3.26 30元可增加1桶牛奶，3元可增加1h时间，应否投资？现投资150元，可赚回多少？投资150元增加5桶牛奶,可赚回189.6元(大于增加时间的利润增长).结果解释B1,B2的获利有10%的波动，对计划有无影响 Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 24.00

26、0000 1.680000 INFINITY X2 16.000000 8.150000 2.100000 X3 44.000000 19.750002 3.166667 X4 32.000000 2.026667 INFINITY X5 -3.000000 15.800000 2.533334 X6 -3.000000 1.520000 INFINITY 敏感性分析 B1获利下降10%，超出X3 系数允许范围B2获利上升10%，超出X4 系数允许范围波动对计划有影响生产计划应重新制订：如将x3的系数改为39.6计算，会发现结果有很大变化. Global optimal solution fo

27、und. Objective value: 3460.800 Total solver iterations: 2 Variable Value Reduced Cost X1 0.000000 1.680000 X2 168.0000 0.000000 X3 19.20000 0.000000 X4 0.000000 0.000000 X5 24.00000 0.000000 X6 0.000000 1.520000 Row Slack or Surplus Dual Price 1 3460.800 1.000000 MILK 0.000000 3.160000 TIME 0.000000

28、 3.260000 CPCT 76.00000 0.000000 5 0.000000 44.00000 6 0.000000 32.00000结果解释x1从0开始增加一个单位时，最优目标函数值将减少1.68Reduced Cost有意义也是有条件的(LINGO没有给出)每天销售10kgA1的合同必须满足，对利润有什么影响？公司利润减少1.6810=16.8（元）最优利润为 3460.8 16.8 = 3444 问题1. 如何下料最节省 ? 例1 钢管下料 问题2. 客户增加需求：原料钢管:每根19m 50根4m20根6m15根8m客户需求节省的标准是什么？由于采用不同切割模式太多, 会增加生

29、产和管理成本,规定切割模式不能超过3种. 如何下料最节省？10根5m按照客户需要在一根原料钢管上安排切割的一种组合,如: 切割模式余料1m 4m 6m 8m 余料3m 4m 6m 6m 合理切割模式的余料应小于客户需要钢管的最小尺寸.余料3m 8m 8m 钢管下料 为满足客户需要，按照哪些种合理模式切割，每种模式切割多少根原料钢管，最为节省？合理切割模式2. 所用原料钢管总根数最少 .模式4m钢管根数6m钢管根数8m钢管根数余料(m)14003231013201341203511116030170023钢管下料问题1 节省的两种标准1. 原料钢管剩余总余量最小 .xi 按第i 种模式切割的原料

30、钢管根数(i=1,7) 约束满足需求 决策变量 目标1（总余量）按模式2切割12根,按模式5切割15根,共27根,余料27m. 模式4m根数6m根数8m根数余料14003m23101m32013m41203m51111m60301m70023m需求502015最优解：x2=12, x5=15, 其余为0；最优值：27.整数约束： xi 为整数目标2（总根数）钢管下料问题1 约束条件不变 最优解：x2=15, x5=5, x7=5, 其余为0；最优值：25.xi 为整数按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35m .目标2切割减少了2根, 但余料增加8m, 为什么?与目标1的结果“