计算理论2011.1.ppt

线性规划基本概念线性规划基本概念生产计划问题生产计划问题?如何合理使用有限的人力,物力和资金,使得收到最好的经济效益。?如何合理使用有限的人力,物力和资金,以达到最经济的方式,完成生产计划的要求。例例1 1 生产计划问题(资源利用问题) 生产计划问题(资源利用问题) 胜利家具厂生产桌子和椅子两种家胜利家具厂生产桌子和椅子两种家具。桌子售价具。桌子售价 50 50元元/ / 个,椅子销售价格个,椅子销售价格 30 30 元元/ / 个,生产桌子和椅子要求需要木工和个,生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木油漆工两种工种。生产一个桌子需要木工工4 4 小时,油漆工小时,油漆工 2 2 小时。生产一个椅子小时。生产一个椅子需要木工需要木工 3 3 小时,油漆工小时,油漆工 1 1 小时。该厂每小时。该厂每个月可用木工工时为个月可用木工工时为 120 120 小时,油漆工工小时,油漆工工时为时为 50 50 小时。问该厂如何组织生产才能小时。问该厂如何组织生产才能使每月的销售收入最大? 使每月的销售收入最大? 解: 解: 将一个实际问题转化为线性规划模型有以下将一个实际问题转化为线性规划模型有以下几个步骤: 几个步骤: 解: 解: 将一个实际问题转化为线性规划模型有以下将一个实际问题转化为线性规划模型有以下将一个实际问题转化为线性规划模型有以下几个步骤: 几个步骤: 几个步骤: 1 : .确定决策变量: x x 1 1= =生产桌子的数量生产桌子的数量 x x 2 2= =生产椅子的数量生产椅子的数量解: 解: 将一个实际问题转化为线性规划模型有以下将一个实际问题转化为线性规划模型有以下将一个实际问题转化为线性规划模型有以下几个步骤: 几个步骤: 几个步骤: 1 : .确定决策变量: .确定决策变量: x xx 1 11= ==生产桌子的数量生产桌子的数量生产桌子的数量 x xx 2 22= ==生产椅子的数量生产椅子的数量生产椅子的数量 2 : .确定目标函数: 家具厂的目标是销售收入最大家具厂的目标是销售收入最大 max z=50x max z=50x 1 1 +30x +30x 2 2 解: 解: 将一个实际问题转化为线性规划模型有以下将一个实际问题转化为线性规划模型有以下将一个实际问题转化为线性规划模型有以下几个步骤: 几个步骤: 几个步骤: 1 : .确定决策变量: .确定决策变量: x xx 1 11= ==生产桌子的数量生产桌子的数量生产桌子的数量 x xx 2 22= ==生产椅子的数量生产椅子的数量生产椅子的数量 2 : .确定目标函数: .确定目标函数: 家具厂的目标是销售收入最大家具厂的目标是销售收入最大家具厂的目标是销售收入最大 max z=50x max z=50x max z=50x 1 11 +30x +30x +30x 2 22 3 3. .确定约束条件: 确定约束条件: 4x 4x 1 1 +3x +3x 2 2 ?? 120 120 ( (木工工时限制) 木工工时限制) 2x 2x 1 1 +x +x 2 2 ?? 50 50 ( (油漆工工时限制) 油漆工工时限制) 解: 解: 将一个实际问题转化为线性规划模型有以下将一个实际问题转化为线性规划模型有以下几个步骤: 几个步骤: 1 : .确定决策变量: x x 1 1= =生产桌子的数量生产桌子的数量 x x 2 2= =生产椅子的数量生产椅子的数量 2 : .确定目标函数: 家具厂的目标是销售收入最大家具厂的目标是销售收入最大 max z=50x max z=50x 1 1 +30x +30x 2 2 3 3. .确定约束条件: 确定约束条件: 4x 4x 1 1 +3x +3x 2 2 ?? 120 120 ( (木工工时限制) 木工工时限制) 2x1+x2 2x1+x2 ?? 50 50 ( (油漆工工时限制) 油漆工工时限制) 4 : .变量取值限制: 一般情况,决策变量只取正值(非负值) 一般情况,决策变量只取正值(非负值) x x 1 1 ?? 0, x 0, x 2 2 ?? 0 0 数学模型数学模型 max S=50x max S=50x 1 1 +30x +30x 2 2 . 4x