线性规划数学模型的应用.ppt

第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用实用管理运筹学实用管理运筹学-基于基于ExcelExcel求解程序和求解模板求解程序和求解模板第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用本讲要讨论两方面的内容本讲要讨论两方面的内容1、线性规划模型应用的型式分类、线性规划模型应用的型式分类2、线性规划模型的应用、线性规划模型的应用 第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用型式分类型式分类按约束条件特征分类按约束条件特征分类资源分配问题（资源分配问题（）成本收益平衡问题（成本收益平衡问题（）网络配送问题（网络配送问题（=）混合问题混合问题 按目标函数特征分类按目标函数特征分类成本价值型问题成本价值型问题 统计型问题统计型问题 第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用按约束条件特征分类按约束条件特征分类型式分类型式分类资源分配问题的共性：资源分配问题的共性：使用的资源数量使用的资源数量可用的资源数量可用的资源数量 可用的资源数量使用的资源数量可用的资源数量使用的资源数量=松驰量松驰量 三种数据三种数据 每一种资源的可供量（每一种资源的可供量（bi）每一种活动所需要的各种资源数量每一种活动所需要的各种资源数量(aij)每一种活动所需要的绩效测度的单位贡献每一种活动所需要的绩效测度的单位贡献(cj)第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用按约束条件特征分类按约束条件特征分类型式分类型式分类成本收益平衡问题的共性成本收益平衡问题的共性 完成的水平完成的水平 最低可接受的水平最低可接受的水平 完成的水平最低可接受的水平完成的水平最低可接受的水平=剩余量剩余量 三种数据三种数据 每种收益的最低可接受水平每种收益的最低可接受水平（bi）每一种活动对每一种收益的贡献每一种活动对每一种收益的贡献(aij)每种活动的单位成本每种活动的单位成本(cj)第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用按约束条件特征分类按约束条件特征分类型式分类型式分类网络配送问题的共性网络配送问题的共性 提供的数量提供的数量=需要的数量需要的数量松驰量、剩余量均等于松驰量、剩余量均等于0第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用按约束条件特征分类按约束条件特征分类型式分类型式分类混合问题的共性混合问题的共性 约束条件有多种形式，没有一类占主导地位约束条件有多种形式，没有一类占主导地位 第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用型式分类型式分类目标函数特征分类目标函数特征分类成本价值型问题成本价值型问题:目标函数的变量系数具有成本或价格的成份。目标函数的变量系数具有成本或价格的成份。主要特征是各系数表示的是广义的成本或价格，主要特征是各系数表示的是广义的成本或价格，并且数值可大可小，可正可负。并且数值可大可小，可正可负。对这类问题进行灵敏度分析时，有必要对相差对这类问题进行灵敏度分析时，有必要对相差值所有目标函数系数的取值范围做详细的分析，值所有目标函数系数的取值范围做详细的分析，这种分析一般都可以得到非常有益的分析结果。这种分析一般都可以得到非常有益的分析结果。第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用型式分类型式分类目标函数特征分类目标函数特征分类统计型问题统计型问题:目标函数的变量系数不具有价值成份，只是目标函数的变量系数不具有价值成份，只是一组统计数字。其主要特征是各系数的值都一一组统计数字。其主要特征是各系数的值都一样，表示统计时各变量具有相同权重，并且大样，表示统计时各变量具有相同权重，并且大多都是多都是1。对于这类问题，因为目标函数的各个变量系对于这类问题，因为目标函数的各个变量系数都仅仅具有相同权重的统计意义，没必要对数都仅仅具有相同权重的统计意义，没必要对相差值和目标函数系数的取值范围做分析。相差值和目标函数系数的取值范围做分析。第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用线性规划模型的应用线性规划模型的应用第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用资源分配型资源分配型-产品自制与外购计划问题产品自制与外购计划问题 例例4.1 某工厂生产甲、乙、丙三种产品，这三种产品都要某工厂生产甲、乙、丙三种产品，这三种产品都要经过铸造、机械加工和装配三道工序。甲、乙两种产品的铸件经过铸造、机械加工和装配三道工序。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须由本厂铸造才可以外包协作，亦可以自行生产，但产品丙必须由本厂铸造才能保证质量。有关情况如下表所示，工厂为了获得最大利润，能保证质量。有关情况如下表所示，工厂为了获得最大利润，甲、乙、丙三种产品各应生产多少件？甲、乙两种产品的铸件甲、乙、丙三种产品各应生产多少件？甲、乙两种产品的铸件有多少由本公司铸造？有多少为外包协作？有多少由本公司铸造？有多少为外包协作？工工时时与成本与成本甲甲乙乙丙丙工时限制工时限制每件每件铸铸造工造工时时/小小时时51078000每件机械加工工每件机械加工工时时/小小时时64812000每件装配工每件装配工时时/小小时时32210000自行生自行生产铸产铸件每件成本件每件成本/元元354外包外包协协作作铸铸件每件成本件每件成本/元元56-机械加工每件成本机械加工每件成本/元元213装配每件成本装配每件成本/元元322每件每件产产品售价品售价/元元231816第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用资源分配型资源分配型-产品自制与外购计划问题产品自制与外购计划问题一、确定变量：一、确定变量：设设:x1、x2、x3分别为三道工序都由本工厂加工的甲、乙、丙三种产品的件数分别为三道工序都由本工厂加工的甲、乙、丙三种产品的件数 x4、x5分别为由外包协作铸造再由本工厂进行机械加工和装配的甲、乙两分别为由外包协作铸造再由本工厂进行机械加工和装配的甲、乙两种产品的件数种产品的件数。如下表。如下表:16-9=718-9=918-8=1023-10=1323-8=15单单位位产产品利品利润润161823每件每件产产品售价品售价4+3+2=96+1+2=95+1+2=85+2+3=103+2+3=8成本成本22233装配每件成本装配每件成本31122机械加工每件成本机械加工每件成本-6-5-外包外包协协作作铸铸件每件成本件每件成本4-5-3自行生自行生产铸产铸件每件成本件每件成本1000022233每件装配工每件装配工时时/小小时时1200084466每件机械加工工每件机械加工工时时/小小时时80007-10-5每件每件铸铸造工造工时时/小小时时x3x5x2x4x1变变量（量（产产量）量）可用工可用工时时丙丙乙乙甲甲成本费用单位：元成本费用单位：元第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用资源分配型资源分配型-产品自制与外购计划问题产品自制与外购计划问题 二、确定目标函数：二、确定目标函数：由上表可得每件产品的利润如下：由上表可得每件产品的利润如下：目标函数目标函数 15x1+10 x2+7x3+13x4+9x5 为最大为最大 三、约束条件三、约束条件:5x1+10 x2+7x38000 （铸造工时）（铸造工时）6x1+4x2+8x3+6x4+4x512000 (机械加工工时机械加工工时)3x1+2x2+2x3+3x4+2x510000 （装配工时）（装配工时）第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用资源分配型资源分配型-产品自制与外购计划问题产品自制与外购计划问题 max 15x1+10 x2+7x3+13x4+9x5；S.T.5x1+10 x2+7x38000 6x1+4x2+8x3+6x4+4x512000 3x1+2x2+2x3+3x4+2x510000 x1，x2，x3，x4，x50线性规划模型线性规划模型:第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用资源分配型资源分配型-产品自制与外购计划问题产品自制与外购计划问题可得结果可得结果:甲甲乙乙丙丙可用工可用工时时实际实际安排安排1600006000每件每件铸铸造工造工时时/小小时时51600=800051600=80008000每件机械加工工每件机械加工工时时/小小时时61600+4600=1200061600+4600=1200012000每件装配工每件装配工时时/小小时时31600+2600=600031600+2600=600010000利利润润23-8=1523-10=1318-8=1018-9=916-9=7总总利利润润151600+9600=2940051600+9600=29400结果分析见结果分析见P92第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用资源分配型资源分配型-连续投资问题连续投资问题 例例4.2 某部门现有资金某部门现有资金300万元，今后五年内考虑给以下的项目投资：万元，今后五年内考虑给以下的项目投资：项目项目A：从第一年到第五年每年年初都可投资，当年末能收回：从第一年到第五年每年年初都可投资，当年末能收回本利本利110。项目项目B：从第一年到第四年每年年初都可以投资，次年末收回：从第一年到第四年每年年初都可以投资，次年末收回本利本利125，但规定每年最大投资额不能超过，但规定每年最大投资额不能超过50万元。万元。项目项目C：第三年初需要投资，到第五年末能收回本利：第三年初需要投资，到第五年末能收回本利140，但，但规定最大投资额不能超过规定最大投资额不能超过100万元。万元。项目项目D：第二年初需要投资，到第五年末能收回本利：第二年初需要投资，到第五年末能收回本利155，但，但规定最大投资额不能超过规定最大投资额不能超过150万元。万元。应如何确定这些项目每年的投资额，从而使得第五年末拥有资应如何确定这些项目每年的投资额，从而使得第五年末拥有资金的本利金额最大？金的本利金额最大？第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用一、确定变量一、确定变量 如下表如下表:第第1年投年投资额资额第第2年投年投资额资额第第3年投年投资额资额第第4年投年投资额资额第第5年投年投资额资额项项目目Ax1x2x3x4x5项项目目Bx6x7x8x9项项目目Cx10项项目目Dx11资源分配型资源分配型-连续投资问题连续投资问题第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用第第1年年第第2年年第第3年年第第4年年第第5年年5年末收益年末收益项项目目Ax1x2x3x4x51.1 x5项项目目B（50/年）年）x6x7x8x91.25 x9项项目目C（100/年）年）x101.40 x10项项目目D（150/年）年）x111.55 x11 得得5年末总收益年末总收益:z1.1 x51.25 x9十十1.40 x101.55 x11 二、确定目标函数二、确定目标函数 此问题要求在第五年末该部门所拥有的资金额达到最大，即此问题要求在第五年末该部门所拥有的资金额达到最大，即目标函数最大化，看下表目标函数最大化，看下表:资源分配型资源分配型-连续投资问题连续投资问题第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用三、确定约束条件三、确定约束条件 因为项目因为项目A每年都可以投资，并且当年末都能收回本息，所以每年都可以投资，并且当年末都能收回本息，所以该部门每年都应把资金投出去，手中不应当有剩余的呆滞资金，该部门每年都应把资金投出去，手中不应当有剩余的呆滞资金，因此可处下表：因此可处下表：第第1年年第第2年年第第3年年第第4年年第第5年年项项目目Ax1x2x3x4x5项项目目B（50/年）年）x6x7x8x9项项目目C（100/年）年）x10项项目目D（150/年）年）x11当年投当年投资额资额x1+x6x2+x7+x11x3+x8+x10 x4+x9x5当年可投当年可投资额资额3001.1 x11.1 x2+1.25 x61.1 x3+1.25 x71.1 x4+1.25 x8资源分配型资源分配型-连续投资问题连续投资问题第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用第一年：第一年：x1+x6 300第二年：第二年：x2+x7+x11 1.1 x1 或或 -1.1 x1+x2+x7+x11 0第三年：第三年：x3+x8+x10 1.1 x2+1.25 x6 或或 -1.1 x2+x3-1.25 x6+x8+x10 0第四年：第四年：x4+x9 1.1 x3+1.25 x7 或或 -1.1 x3+x4-1.25 x7+x9 0第五年：第五年：x5 1.1 x4+1.25 x8 或或 -1.1 x4+x5-1.25 x8 0资源分配型资源分配型-连续投资问题连续投资问题第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用资源分配型资源分配型-连续投资问题连续投资问题另外，对项目另外，对项目B，C，D的投资额的限制有：的投资额的限制有：x650 (项目项目B每年限投每年限投50万元万元)x750 (项目项目B每年限投每年限投50万元万元)x850 (项目项目B每年限投每年限投50万元万元)x950 (项目项目B每年限投每年限投50万元万元)x10100 (项目项目C每年限投每年限投100万元万元)x11150 (项目项目D每年限投每年限投150万元万元)第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用资源分配型资源分配型-连续投资问题连续投资问题 max z=1.1 x51.25 x9十十1.40 x101.55 x11 S.T.x1+x6=300 -1.1 x1+x2+x7+x11=0 -1.1 x2+x3-1.25 x6+x8+x10=0 -1.1 x3+x4-1.25 x7+x9=0 -1.1 x4+x5-1.25 x8=0 x650 x750 x850 x950 x10100 x11150 xi0（i=1,2,.10,11）得连续投资问题的线性规划数学模型：得连续投资问题的线性规划数学模型：第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用资源分配型资源分配型-连续投资问题连续投资问题求解结果求解结果:第第1年年第第2年年第第3年年第第4年年第第5年年5年末收益年末收益项项目目Ax1=250 x2=79.545x3=0 x4=6.818x5=701.1 x5=77项项目目Bx6=50 x7=45.455x8=50 x9=501.25 x9=62.5项项目目Cx10=1001.40 x10=140项项目目Dx11=1501.55 x11=232.5当年投当年投资额资额x1+x6=300 x2+x7+x11=275x3+x8+x10=150 x4+x9=56.818x5=70当年可投当年可投资额资额3001.1 x1=2751.1 x2+1.25 x6=1501.1 x3+1.25 x7=56.8181.1 x4+1.25 x8=705年末年末总总收益收益512结果分析见结果分析见P96第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-合理排班问题合理排班问题 例例4.3 一家中型的新华书店根据市场多年客户购书情况一家中型的新华书店根据市场多年客户购书情况,经经过详细统计分析后过详细统计分析后,发现一周每天的客流量都呈现一些规律性的发现一周每天的客流量都呈现一些规律性的变化变化,需要对店内售货员安排做相应的调整需要对店内售货员安排做相应的调整,所需人员情况如下表所需人员情况如下表:时间时间所需要售所需要售货员货员人数人数时间时间所需要售所需要售货员货员人数人数星期一星期一20星期五星期五28星期二星期二24星期六星期六32星期三星期三25星期日星期日34星期四星期四20 为了保证售货员充分休息，要求售货员每周工作五天，休为了保证售货员充分休息，要求售货员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货员息两天，并要求休息的两天是连续的，问应该如何安排售货员的每天上班人数的每天上班人数，既满足工作需要，又使配备的售货员的人数，既满足工作需要，又使配备的售货员的人数最少？最少？第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-合理排班问题合理排班问题一、确定变量一、确定变量设：设：x1为星期一开始安排休息的人数为星期一开始安排休息的人数 x2为星期二开始安排休息的人数为星期二开始安排休息的人数 x3为星期三开始安排休息的人数为星期三开始安排休息的人数 x4为星期四开始安排休息的人数为星期四开始安排休息的人数 x5为星期五开始安排休息的人数为星期五开始安排休息的人数 x6为星期六开始安排休息的人数为星期六开始安排休息的人数 x7为星期日开始安排休息的人数为星期日开始安排休息的人数 先以每天安排休息人数来做决策，其结果也同先以每天安排休息人数来做决策，其结果也同时得到每天上班人数时得到每天上班人数 第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-合理排班问题合理排班问题二、确定目标函数二、确定目标函数 本问题目标是配备售货员的总人数为最少。本问题目标是配备售货员的总人数为最少。而而售货员的总人数为：售货员的总人数为：x1+x2+x3+x4+x5+x6+x7 所以目标函数为：所以目标函数为：min f=x1+x2+x3+x4+x5+x6+x7 第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-合理排班问题合理排班问题20周日周日周周1周周2周周3周周4周周5周周6242520283234x1x2x3x4x5x6x7三、约束条件三、约束条件x2+x3+x4+x5+x620 x4+x5+x6+x7+x125x5+x6+x7+x1+x220 x6+x7+x1+x2+x328x7+x1+x2+x3+x432x3+x4+x5+x6+x724x1+x2+x3+x4+x534第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-合理排班问题合理排班问题 min x1+x2+x3+x4+x5+x6+x7 S.T.x1+x2+x3+x4+x5 34 x2+x3+x4+x5+x6 20 x3+x4+x5+x6+x7 24 x1 +x4+x5+x6+x7 25 x1+x2 +x5+x6+x7 20 x1+x2+x3 +x6+x7 28 x1+x2+x3+x4 +x7 31 x1，x2，x3，x4，x5，x6，x70得排班问题的线性规划数学模型得排班问题的线性规划数学模型:第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-合理排班问题合理排班问题得求解结果：得求解结果：时间时间所需要人数所需要人数安排休息人数安排休息人数实际实际休息人数休息人数实际实际上班人数上班人数剩余人数剩余人数星期一星期一20131537-15=2222-20=2星期二星期二2401337-13=2424-24=0星期三星期三25121237-12=2525-25=0星期四星期四2051737-17=2020-20=0星期五星期五284937-9=2828-28=0星期六星期六3215 37-5=3232-32=0星期七星期七3423 37-5=3434-34=0合合计计18337741852第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-合理排班问题合理排班问题一、确定变量一、确定变量设：设：x1为星期一开始安排上班的人数为星期一开始安排上班的人数 x2为星期二开始安排为星期二开始安排上班上班的人数的人数 x3为星期三开始安排为星期三开始安排上班上班的人数的人数 x4为星期四开始安排为星期四开始安排上班上班的人数的人数 x5为星期五开始安排为星期五开始安排上班上班的人数的人数 x6为星期六开始安排为星期六开始安排上班上班的人数的人数 x7为星期日开始安排为星期日开始安排上班上班的人数的人数 本决策问题的另一种解法本决策问题的另一种解法第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-合理排班问题合理排班问题二、确定目标函数二、确定目标函数 本问题目标是配备售货员的总人数为最少。本问题目标是配备售货员的总人数为最少。而而售货员的总人数为：售货员的总人数为：x1+x2+x3+x4+x5+x6+x7 所以目标函数为：所以目标函数为：min f=x1+x2+x3+x4+x5+x6+x7 第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-合理排班问题合理排班问题三、约束条件三、约束条件20周日周日周周1周周2周周3周周4周周5周周6242520283234x1+x7+x6+x5+x4x2+x1+x7+x6+x5x3+x2+x1+x7+x6x4+x3+x2+x1+x7x5+x3+x3+x2+x1x6+x5+x4+x3+x2x7+x6+x5+x4+x3x5x6x7x1x2x3x4第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-合理排班问题合理排班问题得该问题的线性规划数学模型得该问题的线性规划数学模型:min x1+x2+x3+x4+x5+x6+x7 S.T.x1 +x4+x5+x6+x720 x1+x2 +x5+x6+x724 x1+x2+x3 +x6+x7 25 x1+x2+x3+x4 +x720 x1+x2+x3+x4+x5 28 x2+x3+x4+x5+x6 32 x3+x4+x5+x6+x734 x1，x2，x3，x4，x5，x6，x70第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-合理排班问题合理排班问题得求解结果：得求解结果：时间时间所需要人数所需要人数安排上班人数安排上班人数实际实际上班人数上班人数剩余人数剩余人数星期一星期一2012222-20=2星期二星期二2422424-24=0星期三星期三25132525-25=0星期四星期四2002020-20=0星期五星期五28122828-28=0星期六星期六3253232-32=0星期七星期七3443434-34=0合合计计18337185 2结果分析见结果分析见P100第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-套材下料问题套材下料问题 例例4.4 某工厂要做某工厂要做100套钢架，每套钢架需要套钢架，每套钢架需要长度分别为长度分别为2.9m，2.lm和和1.5m的圆钢各一根。已知的圆钢各一根。已知原料每根长原料每根长7.4m，问应如何下料，可使所用原料最，问应如何下料，可使所用原料最省？省？第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-套材下料问题套材下料问题套材下料问题的建模思路用的是穷举法：套材下料问题的建模思路用的是穷举法：将一根原材料可以截取圆钢的将一根原材料可以截取圆钢的所有所有不同不同的截法都列出来。再用最优化方法确定用多的截法都列出来。再用最优化方法确定用多少种哪些截法，以取得最优方案。少种哪些截法，以取得最优方案。这种方法可以用于属于该性质的一类决这种方法可以用于属于该性质的一类决策问题。策问题。第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-套材下料问题套材下料问题经分析本问题用原材料截取三种圆钢的所有不同截法如下表：经分析本问题用原材料截取三种圆钢的所有不同截法如下表：方案下料 （根）长度/m2.92.11.5合计余料第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-套材下料问题套材下料问题经分析本问题用原材料截取三种圆钢的所有不同截法如下表：经分析本问题用原材料截取三种圆钢的所有不同截法如下表：方案下料 （根）长度/m12.922.101.51合计7.3余料0.1第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-套材下料问题套材下料问题经分析本问题用原材料截取三种圆钢的所有不同截法如下表：经分析本问题用原材料截取三种圆钢的所有不同截法如下表：方案下料 （根）长度/m122.9212.1021.510合计7.37.1余料0.10.3第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-套材下料问题套材下料问题经分析本问题用原材料截取三种圆钢的所有不同截法如下表：经分析本问题用原材料截取三种圆钢的所有不同截法如下表：方案下料 （根）长度/m1232.92112.10211.5101合计7.37.16.5余料0.10.30.9第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-套材下料问题套材下料问题经分析本问题用原材料截取三种圆钢的所有不同截法如下表：经分析本问题用原材料截取三种圆钢的所有不同截法如下表：方案下料 （根）长度/m12342.921112.102101.51013合计7.37.16.5 7.4余料0.10.30.90第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-套材下料问题套材下料问题经分析本问题用原材料截取三种圆钢的所有不同截法如下表：经分析本问题用原材料截取三种圆钢的所有不同截法如下表：方案下料 （根）长度/m123452.9211102.1021031.510130合计7.37.16.5 7.4 6.3余料0.10.30.901.1第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-套材下料问题套材下料问题经分析本问题用原材料截取三种圆钢的所有不同截法如下表：经分析本问题用原材料截取三种圆钢的所有不同截法如下表：方案下料 （根）长度/m1234562.92111002.10210321.5101302合计7.37.16.5 7.4 6.3 7.2余料0.10.30.901.1 0.2第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-套材下料问题套材下料问题经分析本问题用原材料截取三种圆钢的所有不同截法如下表：经分析本问题用原材料截取三种圆钢的所有不同截法如下表：方案下料 （根）长度/m12345672.921110002.102103211.51013023合计7.37.16.5 7.4 6.3 7.26.6余料0.10.30.901.1 0.20.8第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-套材下料问题套材下料问题经分析本问题用原材料截取三种圆钢的所有不同截法如下表：经分析本问题用原材料截取三种圆钢的所有不同截法如下表：方案下料 （根）长度/m 1 2 3 4 5 6 7 82.9211100002.1021032101.510130234合计7.37.16.5 7.4 6.3 7.26.66余料0.10.30.901.1 0.20.8 1.4第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-套材下料问题套材下料问题方案下料 （根）长度/m第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-套材下料问题套材下料问题二、确定目标函数二、确定目标函数：本题的目标是做本题的目标是做100套钢架所用的原材料套钢架所用的原材料总数最少。总数最少。而所用的圆钢原材料为：而所用的圆钢原材料为：x1+x2+x3+x4+x5+x6+x7+x8所以目标函数为：所以目标函数为：min f=x1+x2+x3+x4+x5+x6+x7+x8第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-套材下料问题套材下料问题三、确定约束条件三、确定约束条件：2x1+x2+x3+x4100 （2.9m的圆钢总根数的圆钢总根数）2x2+x3+3x5+2x6+x7100 （2.1m的圆钢总根数的圆钢总根数）x1+x3+3x4+2 x6+3x7+4 x8100 （1.5m的圆钢总根数的圆钢总根数）第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-套材下料问题套材下料问题 min x1+x2+x3+x4+x5+x6+x7+x8xi 0(i=1,2.8)S.T.2x1+x2+x3+x4100 2x2+x3+3x5+2x6+x7100 x1+x3+3x4+2 x6+3x7+4 x8100 得线性规划数学模型：得线性规划数学模型：第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-套材下料问题套材下料问题方案下料 （根）长度/m第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-套材下料问题套材下料问题方案下料 （根）长度/m第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用成本收益平衡型成本收益平衡型-套材下料问题套材下料问题 本问题在建模时用到了以原材料根数为最本问题在建模时用到了以原材料根数为最少，各种圆钢的实际截取数大于等于需要数。少，各种圆钢的实际截取数大于等于需要数。从建模方法上看，还可以有下面几种，自己讨论：从建模方法上看，还可以有下面几种，自己讨论：用料根数最少用料根数最少,约束条件取等于关系约束条件取等于关系用料总长度最少用料总长度最少,约束条件取大于等于关系约束条件取大于等于关系 用料总长度最少用料总长度最少,约束条件取等于关系约束条件取等于关系 余料总长度最少余料总长度最少,约束条件取大于等于关系约束条件取大于等于关系 余料总长度最少余料总长度最少,约束条件取等于关系约束条件取等于关系 请大家自己讨论其合理性！请大家自己讨论其合理性！第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用混合型混合型-生产安排问题生产安排问题 例例4.5 某机械厂生产某机械厂生产I，III三种产品。每种产品均要经过三种产品。每种产品均要经过A，B两两道加工工序。设该厂有两种规格的设备能完成工序道加工工序。设该厂有两种规格的设备能完成工序A，它们以，它们以A1，A2表示；表示；有三种规格的设备能完成工序有三种规格的设备能完成工序B，它们以，它们以B1，B2，B3表示。产品表示。产品I可在工序可在工序A和和B的任何规格的设备上加工，产品的任何规格的设备上加工，产品可在工序可在工序A的任何一种规格的设备上加的任何一种规格的设备上加工，但完成工序工，但完成工序B时，只能在设备时，只能在设备B1上加工。产品上加工。产品III只能在设备只能在设备A2与与B2上加上加工。已知在各种设备上加工的单件工时、各种设备的有效台时以及满负荷操工。已知在各种设备上加工的单件工时、各种设备的有效台时以及满负荷操作时的设备费用如下表所示，另外己知产品作时的设备费用如下表所示，另外己知产品I，的原料单价分别为的原料单价分别为0.25元元/件，件，0.35元元/件和件和0.50元元/件，销售单价分别为件，销售单价分别为1.25元元/件，件，2.00元元/件和件和2.80元元/件。要求制定最优的产品加工方案，使该厂利润最大。件。要求制定最优的产品加工方案，使该厂利润最大。设备设备产产品品单单件工件工时时设备设备的有效台的有效台时时满负满负荷荷时时的的设备费设备费用用IIIIA15106000300A2791210000400B1684000200B24117000700B374000200第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用混合型混合型-生产安排问题生产安排问题一、确定变量一、确定变量设备设备工工时时设备设备的有效台的有效台时时满负满负荷荷时时的的设备费设备费用用产产品品I产产品品产产品品IIIA15106000300A2791210000400B1684000200B24117000700B374000200工时分配工时分配设备设备变变量（加工数量）量（加工数量）设备设备的有效台的有效台时时满负满负荷荷时时的的设备费设备费用用产产品品I产产品品产产品品IIIA1x1x26000300A2x3x4x510000400B1x6x74000200B2x8x97000700B3x104000200变量（加工数量）设置变量（加工数量）设置第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用混合型混合型-生产安排问题生产安排问题二、确定目标函数二、确定目标函数 本问题的目标是做出总利润为最大的决策方案。而总利润本问题的目标是做出总利润为最大的决策方案。而总利润要由销售额、材料成本、机时费核算，用下表来进行分析。要由销售额、材料成本、机时费核算，用下表来进行分析。第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用混合型混合型-生产安排问题生产安排问题二、确定目标函数二、确定目标函数最后利润最后利润=销售额销售额-材料成本材料成本-机时费机时费 =(1.25-0.25-0.25)x1+(2-0.35-0.5)x2+(1.25-0.25-0.28)x3+(2-0.35-0.36)x4+(2.8-0.5-0.48)x5-0.3x6-0.4 x7-0.4 x8-1.1 x9-0.35 x10即：即：max Z=0.75 x1+1.15 x2+0.72 x3+1.29 x4+1.82 x5-0.3x6-0.4 x7-0.4 x8-1.1 x9-0.35 x10第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用混合型混合型-生产安排问题生产安排问题三、确定约束条件三、确定约束条件 本题的约束条件有两个方面本题的约束条件有两个方面:一个是设备的有效台时数一个是设备的有效台时数,另一个是另一个是A、B两道工序上加工的总数量相等。就得到以下关系：两道工序上加工的总数量相等。就得到以下关系：5 x110 x26000 （设备（设备Al）7 x39 x412 x510000 （设备（设备A2）6 x68 x74000 （设备（设备B1）4 x811x97 000 （设备（设备B2）7x104000 （设备（设备B3）x1+x3 x6-x8-x10=0 （产品（产品I在工序在工序A，B上加工的数量相等）上加工的数量相等）x2+x4 x7=0 （产品（产品在工序在工序A，B上加工的数量相等）上加工的数量相等）x5 x9=0 （产品（产品III在工序在工序A，B上加工的数量相等）上加工的数量相等）xi0（i=1，2，3；10）第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用混合型混合型-生产安排问题生产安排问题得线性规划数学模型：得线性规划数学模型：max 0.75 x1+1.15 x2+0.772 x3+1.29x4+1.82 x5-0.3 x6-0.4 x7-0.4 x8-1.1 x9-0.35 x10 S.T.5 x110 x26000 7 x39 x412 x510000 6 x68 x74000 4 x811x97 000 7x104000 x1+x3 x6-x8-x10=0 x2+x4 x7=0 x5 x9=0 xi0（i=1，2，3；10）第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用混合型混合型-生产安排问题生产安排问题求解结果求解结果产品产品I产量产量产品产品产量产量产品产品III产量产量设备的有设备的有效台时效台时A1120006000A2230500324.110000B105004000B2858.6324.17000B3571.44000合计合计1430500324.1最优值：最优值：1200.57结果分析见结果分析见P119第四讲第四讲 线性规划数学模型的应用线性规划数学模型的应用混混合型合型-配料和混合问题配料和混合问题 例例4.6