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

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