对偶性及对偶单纯形法.ppt

2-4 ..11生产计划问题(资源利用问题)生产计划问题(资源利用问题)胜利家具厂生产桌子和椅子两种家具。桌子胜利家具厂生产桌子和椅子两种家具。桌子售价售价5050元元//个,椅子销售价格个,椅子销售价格30/30/个,生产桌子个,生产桌子和椅子要求需要木工和油漆工两种工种。生产和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工一个桌子需要木工44小时,油漆工小时,油漆工22小时。生产小时。生产一个椅子需要木工一个椅子需要木工33小时,油漆工小时,油漆工11小时。该厂小时。该厂每个月可用木工工时为每个月可用木工工时为120120小时,油漆工工时小时,油漆工工时为为5050小时。问该厂如何组织生产才能使每月的小时。问该厂如何组织生产才能使每月的销售收入最大?销售收入最大?数学模型数学模型max g = 50xmax g = 50x1 1 + 30x+ 30x2 2 . 4x . 4x1 1 + 3x+ 3x2 2 ?? 120 120 2x 2x1 1 + x+ x2 2 ?? 50 () 50 () x x11,x,x2 2 ?? 0 0如果我们换一个角度,考虑另外一如果我们换一个角度,考虑另外一种经营问题。种经营问题。假如有一个企业家有假如有一个企业家有一批等待加工的订单,有意利用该家一批等待加工的订单,有意利用该家具厂的木工和油漆工资源来加工他的具厂的木工和油漆工资源来加工他的产品。因此,他要同家具厂谈判付给产品。因此,他要同家具厂谈判付给该厂每个工时的价格。可以构造一个该厂每个工时的价格。可以构造一个数学模型来研究如何既使家具厂觉得数学模型来研究如何既使家具厂觉得有利可图肯把资源出租给他,又使自有利可图肯把资源出租给他,又使自己付的租金最少?己付的租金最少?假设假设yy11, y, y2 2 分别表示每个木工和分别表示每个木工和油漆工工时的租金,则所付租金最油漆工工时的租金,则所付租金最小的目标函数可表示为:小的目标函数可表示为:min s = 120 ymin s = 120 y1 1 + 50 y+ 50 y22目标函数中的系数目标函数中的系数120120,,50 50 分别表分别表示可供出租的木工和油漆工工时数。示可供出租的木工和油漆工工时数。该企业家所付的租金不能太低,该企业家所付的租金不能太低,否则家具厂的管理者觉得无利可图否则家具厂的管理者觉得无利可图而不肯出租给他。因此他付的租金而不肯出租给他。因此他付的租金应不低于家具厂利用这些资源所能应不低于家具厂利用这些资源所能得到的利益:得到的利益:4 y4 y1 1 + 2y+ 2y2 2 ?? 50 50 3 y 3 y1 1 + y+ y2 2 ?? 30 30 y y11, y, y2 2 ?? 0 0得到另外一个数学模型:得到另外一个数学模型:min s = 120ymin s = 120y1 1 + 50y+ 50y22 . 4 y . 4 y1 1 + 2y+ 2y2 2 ?? 50 50 3 y 3 y1 1 + y+ y2 2 ?? 30 () 30 () y y11, y, y2 2 ?? 0 0模型模型()()和模型和模型()()既有区别又有既有区别又有联系。联系在于它们都是关于家具联系。联系在于它们都是关于家具厂的模型并且使用相同的数据,区厂的模型并且使用相同的数据,区别在于模型反映的实质内容是不同别在于模型反映的实质内容是不同的。模型的。模型()()是站在家具厂经营者是站在家具厂经营者立场追求销售收入最大,模型立场追求销售收入最大,模型()()是则站在家具厂对手的立场追求所是则站在家具厂对手的立场追求所付的租金最少。付的租金最少。如果模型如果模型()()称为原问题,称为原问题,则模型则模型()()称为对偶问题。称为对偶问题。任何线性规划问题都有对偶问题,任何线性规划问题都有对偶问题,而且都有相应的意义。而且都有相应的意义。例例2 .2 2 .2 营养配餐问题营养配餐问