第2章 线性规划的对偶理论与灵敏度分析2.1VIP专享VIP免费

第2章线性规划的对偶理论与灵敏度分析§2.1线性规划的对偶问题随着线性规划应用的逐步深入，人们发现一个线性规划问题往往伴随者与之配对的、两者有密切联系的另一个线性规划问题。将其中一个称为原问题，另一个称为对偶问题。自从对偶理论提出以来，已经有了相当深入的研究。对偶理论深刻揭示了原问题与其对偶问题的内在的联系，由对偶理论引伸出来的对偶解有着重要的经济意义，是经济学中重要的概念。对偶理论充分显示出线性规划理论逻辑上的严谨性与结构上的对称性，它是线性规划理论的重要成果。2.1.1对偶线性规划问题例2.1.1某家具厂木器车间加工木门与木窗两种产品，加工木门收入为56元/扇，加工木窗收入为30元/扇。加工一扇木门需要木工4小时，油漆工2小时；加工一扇木窗需要木工3小时，油漆工1小时。该家具厂每天可用木工总工时120小时，油漆工总工时50小时。问该家具厂应如何安排加工任务才能使每天收益最大？12121212121256304312025000LINGO(2.1.1)15201440xxmaxzxxxxs.t.xxx,xx,x,maxz解：设该车间每天安排加工木门扇，木窗扇，则可建立线性规划数学模型为通过可求得的最优解为：。即该车间每天加工木门15扇、木窗20扇使收入最大，收入可达1440元。（2.1.1）现在从另一个角度来考虑该车间的加工问题。假若有一个个体经营者，手中有一批木器家具生产订单，由于人手不足不能加工出来，他想利用该车间的木工和油漆工来完成他的订单。他要考虑付给木工和油漆工每个工时的报酬，使得该车间能够愿意替他加工这批订单，又使自己支付的工时费最少。器车间能够接受，木工4小时、油漆工2小时能加工一扇木门，创造收入56元，小时可以加工一扇木窗，创造收入30元，支付的工时费不低于30元，即必须12y,y设分别表示支付每个木工工时和每个油漆工工时的价格，为了使木124256yy支付的工时费不低于56元，即必须满足；木工3小时、油漆工112330yy。满足同时，该个体经营者的目标为每日所支付的工时费1212050Wyy最少。因此所建立的线性规划问题数学模型为：将线性规划模型（2.1.2）称为（2.1.1）的对偶线性规划问题，两者之有着紧密的联系。它们都是使用了木器加工车间的数据，只是这些数据在模型中所处的位置不同，反映所要表达的含义也不相同。（2.1.1）是反映追求木器车间收入最大的数学模型，（2.1.2）是寻求个体经营者支给木器车间工时费最少的数学模型。一般地，给定线性规划问题：1212121212050425633000minWyyyys.t.yyy,y（2.1.2）用LINGO求得（2.1.2）的最优解为：122241440y,y,minW112211112211211222221122012nnnnnnmmmnnmjmaxzcxcx...cxaxax...axbaxax...axb.................................................s.t.axax...axbxj,,...,n（LP）（2.1.3）称线性规划问题112211121211121222221122012mmmmmmnnmnmniminWbyby...byayay...aycayay...aycs.t..................................................ayay...aycyi,,...,m（DLP）（2.1.4）为（2.1.3）的对偶线性规划问题。或者对线性规划问题maxz..CXAXbstXo（LP）（2.1.5）称线性规划问题minW.YbYACstYo（DLP）（2.1.6）为（2.1.5）的对偶线性规划问题。11121112122222121212nnmmmnnmnmaaaxbaaaxbaaaxbc,c,,c)y,y,,y)，，（，（AXbCY其中证明对于线性规划问题（2.1.6）改写求目标函数最大化且不等式约束条件两边同乘以（-1）不等式反向，则maxW=-W.YbYACstYo（2.1.7）()maxW().YbYACstYo即（2.1.8）定理2.1.1（对称定理）对偶问题的对偶问题是原问题。（2.1.8）式的对偶线性规划问题是minz.CXAXbstXo（2.1.9）将（2.1.9）式改写成求目标函数最大化且不等式约束条件两边同乘以（-1）不等式反向，则maxzz.CXA...