《运筹学：02-对偶原理》由会员分享，可在线阅读，更多相关《运筹学：02-对偶原理（12页珍藏版）》请在金锄头文库上搜索。
1、对偶原理对偶原理线形规划的对偶问题线形规划的对偶问题原问题：原问题：胜利家具厂生产桌子和椅子两种家具。桌子售价胜利家具厂生产桌子和椅子两种家具。桌子售价50元元/张，椅子张，椅子销售价格销售价格30元元/把，生产桌子和椅子要求需要木工和油漆工两种工种。生把，生产桌子和椅子要求需要木工和油漆工两种工种。生产一张桌子需要木工产一张桌子需要木工4小时，油漆工小时，油漆工2小时。生产一把椅子需要木工小时。生产一把椅子需要木工3小时，小时，油漆工油漆工1小时。该厂每个月可用木工工时为小时。该厂每个月可用木工工时为120小时，油漆工工时为小时，油漆工工时为50小小时。问该厂如何组织生产才能使每月的销售收入
2、最大？时。问该厂如何组织生产才能使每月的销售收入最大？新问题：新问题：胜利家具厂每个月可用木工工时为胜利家具厂每个月可用木工工时为120小时，油漆工工时为小时，油漆工工时为50小小时。该企业自己生产桌子和椅子两种家具。生产一张桌子需要木工时。该企业自己生产桌子和椅子两种家具。生产一张桌子需要木工4小时，小时，油漆工油漆工2小时。生产一把椅子需要木工小时。生产一把椅子需要木工3小时，油漆工小时，油漆工1小时。桌子售价小时。桌子售价50元元/张，椅子销售价格张，椅子销售价格30元元/把。现有一企业欲租用胜利家具厂木工和漆工，把。现有一企业欲租用胜利家具厂木工和漆工，请问木工和漆工的租金是多少请问木
3、工和漆工的租金是多少 才能使双方可以接受？才能使双方可以接受？新问题分析新问题分析1、双方信息是对称的，即租借方知道桌子和椅子的市场价、双方信息是对称的，即租借方知道桌子和椅子的市场价格，胜利家具厂应该知道租借方能够了解桌子和椅子的格，胜利家具厂应该知道租借方能够了解桌子和椅子的市场价格；市场价格；2、租借方所出租金，应该是胜利家具厂能够接受的；、租借方所出租金，应该是胜利家具厂能够接受的；3、租借方希望所出租金最少；、租借方希望所出租金最少；4、胜利家具厂收获的租金不应比自己生产桌子和椅子所获、胜利家具厂收获的租金不应比自己生产桌子和椅子所获得的收益低；得的收益低；5、 胜利家具厂要价是租借
4、方可以接受的；胜利家具厂要价是租借方可以接受的；6、研究该问题时，只考虑工时资源，不考虑其它资源的消、研究该问题时，只考虑工时资源，不考虑其它资源的消耗和成本。耗和成本。新问题表格描述新问题表格描述桌子桌子椅子椅子总工时总工时木工木工43120漆工漆工2150单价单价5030生产量生产量X1X2木工木工漆工漆工单价单价桌子桌子4250椅子椅子3130总工时总工时12050租金租金Y1Y2原原问问题题新新问问题题新问题模型新问题模型1 1、租借方应支付租金：、租借方应支付租金： w = 120y1 + 50y22 2、所出租金应该是胜利家、所出租金应该是胜利家具厂可以接受的：具厂可以接受的： 1
5、) 4y1 + 2y2 50 2) 3y1 + y2 303 3、租金不应该是负数：、租金不应该是负数： y1, y2 04 4、所出租金应该最少，问、所出租金应该最少，问题是题是最小最小问题。问题。新问题线形规划模型：新问题线形规划模型：min w = 120y1 + 50y2s.t. 4y1 + 2y2 50 3y1 + y2 30 y1, y2 0该模型被称为原线形该模型被称为原线形规划模型的对偶模型，规划模型的对偶模型，该问题被称为原问题该问题被称为原问题的对偶问题。的对偶问题。模型比较模型比较min w = 120y1 + 50y2s.t. 4y1 + 2y2 50 3y1 + y2
6、 30 y1, y2 0max z = 50xmax z = 50x1 1+ 30x+ 30x2 2s.t. 4xs.t. 4x1 1+3x+3x2 2 120 120 2x 2x1 1+ x+ x2 2 5050 x x1 1, x, x2 2 0 0原问题模型对偶问题对偶问题模型模型规范对偶关系规范对偶关系a11a12a1nb1a21a22a2nb2am1am2amnbmc1c2cnx1x2xna11a21am1c1a12a22am2c2a1na2namncnb1b2bmy1y2ym原问题P对偶问题D标准对偶关系标准对偶关系对偶问题D原问题P对偶性质对称性：规范原始问题和对偶问题互为对偶问题；弱对偶性：设X、Y为原始问题和对偶问题的任一可行解， 则CTX BTY;最优性：设X、Y为原始问题和对偶问题的可行解， 若 CTX =BTY 则X、Y分别为原始问题和对偶问题的最优解；线形规划的对偶定理：（1）若其中一个问题有最优解，则另一个问题也有最优解，且最优值相等；（2）若一个问题的解无界，则另一个问题无可行解。对偶变量的经济解释对偶问题最优解Y*是资源B对最优目标Z*的边际贡献，是资源的边际价值，也称为影子价值。1、Y*代表影子价格2、Y*代表影子利润对偶问题的经济解释利用Excel求解对偶问题一、对偶单纯形法；二、利用Excel求解对偶问题 1、求解原问题； 2、求解对偶问题。
