[企业管理]MBA运筹学2第二-五章 线性规划.ppt
《[企业管理]MBA运筹学2第二-五章 线性规划.ppt》由会员分享,可在线阅读,更多相关《[企业管理]MBA运筹学2第二-五章 线性规划.ppt(61页珍藏版)》请在三一文库上搜索。
1、第二三四五章 线性规划,2.1 线性规划问题与标准形式 2.2 线性规划问题的几何解释 2.3 单纯型法方法,问题的提出(1),【例】派公司是一个生产高尔夫器材的小型公司,公司决定生产中高价位的高尔夫袋。产品的生产过程有四个程序:切割并印染原材料、缝合、成型、检查和包装,不同价位高尔夫袋生产程序的耗时信息如下表,表中还列出了派公司在本轮生产过程中每个部门的最大生产时间。,问题的提出(2),会计部门的数据表明,生产一个标准袋的利润是10美元,生产一个高级袋的利润是9美元。如何安排两种产品的生产才能使公司获得最大利润?,问题的提出(3),设x1、x2分别为两种高尔夫袋的生产量,则该计划问题可用如下
2、数学模型表示为:,2.1 线性规划问题与标准形式 典例1-生产计划问题,例2. 某工厂在计划期内要生产产品I和产品II这两种产品,已知生产单位产品所需的设备台时及A、B两种设备计划期的有效台时,如下表: 问如何安排生产最有利?,解设产品I和产品II的产量分别为x1和x2件, 利润为Z, 则:,Z = x1 + 2 x2,Max,目标函数,2 x1 + 2 x2 8 0 x1 + 2 x2 4 x1 , x2 0,约束条件 S.t.,非负条件,above,典例2-配料问题,Z = 3x1 + 2 x2,Min,目标函数,12 x1 + 3 x2 4 2 x1 + 3 x2 2 3 x1 + 15
3、 x2 5 x1 + x2 = 1 x1 , x2 0,约束条件 S.t.,典例3-食谱问题,例3,问在满足营养的条件下,如何安排食谱最有利?,解:设每人每周食用大米、白菜、鸡蛋、猪肉的数量分别为x1、 x2、 x3、 x4,Z=C1x1+ C2x2+ C3x3+ C4x4,Min,a11x1+ a12x2+ a13x3+ a14x4 b1,=,a21x1+ a22x2+ a23x3+ a24x4 = b2 a31x1+ a32x2+ a33x3+ a34x4 = b3 x1, x2 , x3 , x4 0,食谱问题的拓展,问在满足营养的条件下,如何安排食谱最有利?,Z=C1x1+ C2x2+
4、 C3x3+ C4x4 + . + Cnxn,Min,a11x1+ a12x2+ a13x3+ a14x4 + a1nxn = b1,a21x1+ a22x2+ a23x3+ a24x4 + a2nxn = b2 a31x1+ a32x2+ a33x3+ a34x4 + a3nxn = b3 am1x1+ am2x2+ am3x3+ am4x4 + amnxn = bm x1, x2 , x3 , . xn 0,数学模型,New Bedford Steel炼焦煤供应问题,New Bedford Steel (NBS)是一家小型的炼钢企业。炼焦煤(coking coal)是NBS公司炼钢时所必需
5、的一种原材料,每年的需求量是100至150万吨。现在到了该公司计划明年生产的时候了,他们收到了来自八家供应商的报价。,New Bedford Steel炼焦煤供应问题,根据对未来的形势估计和生产现状的考察,NBS计划明年要定购1,225千吨的炼焦煤。这些炼焦煤的平均可燃率至少要达到19%。为了不影响劳工关系,NBS决定至少50%的炼焦煤要来自于工会煤矿。另外,每年由火车运输的炼焦煤量至多不超过650千吨,而由卡车运输的炼焦煤量至多不超过720千吨。 现在要解决以下问题: 为了使炼焦煤的成本最小,应该从各个供应商处定购多少吨炼焦煤? NBS的总供应成本是多少? NBS的平均供应成本是多少?,NB
6、S供应问题的数学表达,变量: A = 从 Ashley 处定购的炼焦煤量(千吨) B = 从 Bedford 处定购的炼焦煤量(千吨) C = 从 Consol 处定购的炼焦煤量(千吨) D = 从 Dunby 处定购的炼焦煤量(千吨) E = 从 Earlam 处定购的炼焦煤量(千吨) F = 从 Florence 处定购的炼焦煤量(千吨) G = 从 Gaston 处定购的炼焦煤量(千吨) H = 从 Hopt 处定购的炼焦煤量(千吨),供应成本成: 49.5A + 50B + 61C + 63.5D + 66.5E + 71F + 72.5G + 80H 供应约束: A + B + C
7、+ D + E + F + G + H = 1,225 工会煤矿的约束: A + B C + D E + F G H 0 卡车运输量约束: B + D + E + F 720 火车运输量约束: A + C + G + H 650 平均可燃率约束: 可改写成: 4A 3B C + D + 2E + 3F + 4G + 6H 0 各煤矿的炼焦煤供应量约束: A 300,B 600,C 510,D 655,E 575,F 680,G 450, H 490 非负约束: A 0,B 0,C 0,D 0,E 0,F 0,G 0,H 0,NBS的炼焦煤供应问题的线性最优化模型,MINIMIZE COST=4
8、9.5A+50B+61C+63.5D+66.5E+71F+72.5G+80H SUBJECT TO: SUPPLY: A + B + C + D + E + F + G + H = 1,225 UNION: A + B C + D E + F G H 0 TRUCK: B + D + E + F 720 RAIL: A + C + G + H 650 VOL: 4A 3B C + D + 2E + 3F + 4G + 6H 0 ACAP: A 300 BCAP: B 600 CCAP: C 510 DCAP: D 655 ECAP: E 575 FCAP: F 680 GCAP: G 450
9、HCAP: H 490 NONNEGATIVITY CONDITIONS: A0, B0, C0, D0, E0, F0, G0, H0,NBS的炼焦煤供应问题的线性最优化模型,求解,得: A= 55千吨, B=600千吨, C= 0千吨, D= 20千吨, E=100千吨, F= 0千吨, G=450千吨, H= 0千吨; 最小成本 = 73,267.50千美元; 平均供应成本 = 73,267.50 / 1,225 = 59.81美元/吨,二、线性规划数学模型的几种表达形式,一般形式 目标函数: Max (Min) z = c1 x1 + c2 x2 + + cn xn 约束条件: s.t
10、. a11 x1 + a12 x2 + + a1n xn ( =, )b1 a21 x1 + a22 x2 + + a2n xn ( =, )b2 am1 x1 + am2 x2 + + amn xn ( =, )bm x1 ,x2 , ,xn 0,简写形式 目标函数: Max (Min) z = 约束条件: s.t. ( =, )bi , i=1,2, m xj 0 , j=1 , 2 , . n,向量形式 C=(c1 , c2, , cn ) 价值向量,二、线性规划数学模型的几种表达形式,限定向量,变量xj对应的系数列向量,二、线性规划数学模型的几种表达形式,矩阵形式,约束条件系数矩阵,第
11、二节 线性规划问题的标准形式,一、标准形式 目标函数: Max z = c1 x1 + c2 x2 + + cn xn 约束条件: s.t. a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn = bm x1 ,x2 , ,xn 0,或,即:同时满足如下四个条件: 目标函数求极大 约束条件全为等式 约束条件右端常数项全为非负 变量取值全为非负,2.1 线性规划问题与标准形式,为了今后讨论的方便,我们称以下两种形式的线性规划问题为线性规划的规范形式(Canonical
12、 Form): min zCTX s.t. AXb X0 max zCTX s.t. AXb X0,2.1 线性规划问题与标准形式,而称以下的形式为标准形式(Standard Form): max zCTX s.t. AXb X0 对于各种非标准形式的线性规划问题,我们总可以通过以下的变换,将其转化为标准形式。 1 极小化目标函数的问题 2 约束条件不是等式的问题 3 变量无符号限制的问题,1 极小化目标函数的问题,设目标函数为,令zz,则以上极大化问题和极小化问题有相同的最 优解,即,但必须注意,尽管以上两个问题的最优解相同,但他们 最优解的目标函数值却相差一个符号,即,min zmax z
13、 ,2 约束条件不是等式的问题,设约束条件为 ( i=1,2,m) 可以引进一个新的变量xn+i,使它等于约束右边与左边之差 显然xn+I也具有非负约束,即xn+i0,这时新的约束条件成为 当约束条件为,2 约束条件不是等式的问题,时,类似地令,则同样有xn+i0,新的约束条件成为,为了使约束由不等式成为等式而引进的变量xn+i称为“松弛变量”。如果原问题中有若干个非等式约束,则将其转化为标准形式时,必须对各个约束引进不同的松弛变量。,3 变量无符号限制的问题,在标准形式中,每一个变量都有非负约束。当一个变量xj没有非负约束时,可以令 xj=xj-xj” 其中 xj0,xj”0 即用两个非负变
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 企业管理 企业管理MBA运筹学2第二-五章 线性规划 MBA 运筹学 第二
链接地址:https://www.31doc.com/p-1999833.html