线性规划模型.ppt

《线性规划模型.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、电І数量x2制造家电П数量获利2x1获利x2加工能力决策变量目标函数每天获利约束条件非负约束线性规划模型(LP)基本模型例2运输问题工厂例3营养问题某饲养场饲养供实验用的动物。已知动物生长对饲料中的三种营养成份：蛋白质、矿物质和维生素特别敏感。每个动物每天至少需要蛋白质70g，矿物质3g，维生素10mg。该饲养场现有五种饲料，每种饲料10kg的成本如下：饲料A1A2A3A4A5成本27435单位:元每一千克饲料中所含的营养成分表饲料蛋白质/g矿物质/g维生素/mgA10.300.100.05A22.

3、000.050.10A31.000.020.02A40.600.200.20A51.800.050.08我们希望确定既能满足动物需求，又使总成本为最低的饲料配方建立相应的数学模型。解:设动物每天食用的混合饲料中所含的第j种饲料Aj的数量为xj(kg),混合饲料的总成本为y,则上述问题的数学模型为一般的营养问题可叙述如下：所以线性规划问题的数学模型的一般形式为它的变量满足不难看出，上面这些问题虽然各式各样，但它们的数学模型却有相同的数学形式，即求一个线性函数的最大值(或最小值)，而这个线性函数的变量

4、是非负的，满足一组线性等式或不等式。我们把具有这种模型的问题称为线性规划问题。5.1.2线性规划模型线性规划问题的数学模型有许多种，目标函数有求最小值的，有求最大值的；约束条件有的是“≤”形式的，也有“≥”或“＝”形式的。我们希望能把各种不同形式的线性规划问题的数学模型化为一种统一的标准形式，这样只要对标准形式找出一种解法，就可以解决其余不同形式的线性规划问题了。线性规划问题的数学模型的一般形式规定下列形式的线性规划问题为标准形式：其中均为常数，且线性规划问题标准形式的矩阵表示：其中求解方法软件实现

5、法X=lp(c,A,b)对偶规划及灵敏度分析7/22/202115例1美佳公司利用该公司资源生产两种家电产品的线性规划模型为：设y1，y2，y3分别表示设备A、B和调试工序单位时间的价格。则0y1+6y2+y3≥25y1+2y2+y3≥1对生产Ⅰ产品的全部资源的定价。假如另一公司想收购美佳公司的资源，美佳公司出让自己资源的条件是什么？出让代价不低于用同等资源组织生产两种产品所能获得的利润。对生产Ⅱ产品的全部资源的定价。产品Ⅰ的利润产品Ⅱ的利润7/22/202116原问题与对偶问题的数据比较原问题对偶

6、问题x1x2原关系minwy105≤15y262≤24y311≤5对偶关系maxz=minwmaxz21≥≥7/22/202117二、对称形式对偶问题的一般形式定义：满足下列条件的线性规划问题称为具有对称形式：其变量均具有非负约束，其约束条件当目标函数求极大时取“≤”号，当目标函数求极小时均取“≥”号。则其对偶问题的一般形式为：若原问题的一般形式为：yi(i=1,2,…，m)代表第i种资源的估价。7/22/202118矩阵形式表示的原问题与对偶问题原问题：对偶问题：令w′＝－w对偶问题令z＝－z′对

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

8、源利用的评价市场价格：是资源在市场上流通的实际价格，它由整个社会的经济技术状况决定。返回本章目录7/22/202121根据求bi的偏导数得：这说明，原问题某一约束条件的右边常数bi增加一个单位时，则由此引起最优目标函数值的增加量，就等于与该约束相对应的对偶变量的最优值。这样一来，在有限资源条件下使收益最大化这一类问题中，就可以把对偶变量的最优值，看成是相应资源每一单位对于目标函数的贡献，即这些资源被充分利用时所能带来的收益。从而，yi*的值就相当于对单位i种资源在实现