第二章2010-1

《第二章2010-1》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章对偶问题在线性规划问题中，存在一个有趣的问题，即每一个线性规划问题都伴随有另一个线性规划问题，称它为对偶线性规划问题。【例】某企业用四种资源生产三种产品，工艺系数、资源限量及价值系数如下表：产品资源ABC资源限量Ⅰ986500Ⅱ547450Ⅲ832300Ⅳ764550每件产品利润1008070建立总收益最大的数学模型。【解】设x1，x2，x3分别为产品A，B，C的产量，则线性规划数学模型为：现在从另一个角度来考虑企业的决策问题。假如企业自己不生产产品，而将现有的资源转让或出租给其它企业，那么资源的转让价格是多少才合理？价格太高对方不愿意接受，价格太低本单位收益

2、又太少。合理的价格应是对方用最少的资金购买本企业的全部资源，而本企业所获得的利润不应低于自己用于生产时所获得的利润。这一决策问题可用下列线性规划数学模型来表示。设y1，y2，y3及y4分别表示四种资源的单位增殖价格，总增殖最低可用minw=500y1+450y2+300y3+550y4表示。企业生产一件产品A用了四种资源的数量分别是9，5，8和7个单位，利润是100,企业出售这些数量的资源所得的利润不能少于100，即同理，对产品B和C有价格不可能小于零，即有yi≥0,i=1,…,4.从而企业的资源价格模型为这是一个线性规划数学模型，称这一线性规划问题是前面生产计划问

3、题的对偶线性规划问题或对偶问题。生产计划的线性规划问题称为原始线性规划问题或原问题。一般的，原问题：maxz=CXAX≤bX≥0对偶问题：minw=YbYA≥CY≥0比较：maxzminw决策变量为n个约束条件为n个约束条件为m个决策变量为m个“≤”“≥”§2对偶问题的基本性质1、对称性对偶问题的对偶为原问题.推论：(1)max问题任一可解的目标值为min问题目标值的一个下界；(2)min问题任一可解的目标值为max问题目标值的一个上界。3、无界性若原问题(对偶问题)为无界解，则对偶问题(原问题)为无可行解。由性质2注：该性质的逆不存在。若原(对偶)问题为无可行解，

4、对偶(原问题)问题或为无界解，或为无可行解。4、最优性设X*，Y*分别为原问题和对偶问题可行解，当CX*=Y*b时，X*，Y*分别为最优解。5、对偶定理若原问题有最优解，那么对偶问题也有最优解，且目标值相等。∴Y*为对偶问题的最优解，且原问题和对偶问题的目标值相等。