规划问题的教学例题

规划问题的教学例题一、引言规划问题在数学教学中占据着重要地位，它涉及到如何合理安排资源、制定最优策略以达成特定目标。通过解决规划问题，学生能够培养逻辑思维、分析问题和解决问题的能力，提升数学应用意识。本文将通过一系列具体的教学例题，系统地阐述规划问题的常见类型及解题方法，帮助学生更好地掌握这一重要知识领域。

二、线性规划问题

（一）例题1某工厂生产甲、乙两种产品，已知生产一件甲产品需要A原料4吨、B原料2吨；生产一件乙产品需要A原料3吨、B原料3吨。现有A原料120吨、B原料90吨，甲产品每件利润为7万元，乙产品每件利润为6万元。问如何安排生产，可使利润最大？

解题步骤1.设未知数：设生产甲产品\(x\)件，生产乙产品\(y\)件。2.列出约束条件：\(4x+3y\leq120\)（A原料限制）\(2x+3y\leq90\)（B原料限制）\(x\geq0\)，\(y\geq0\)（产品数量非负）3.确定目标函数：利润\(z=7x+6y\)，我们要在满足约束条件下使\(z\)最大。4.求解：先画出约束条件所表示的可行域。对于\(4x+3y=120\)，令\(x=0\)，则\(y=40\)；令\(y=0\)，则\(x=30\)，可得直线\(4x+3y=120\)与坐标轴的交点\((0,40)\)和\((30,0)\)，通过两点确定直线并画出直线及直线下方区域（因为是\(4x+3y\leq120\)）。对于\(2x+3y=90\)，令\(x=0\)，则\(y=30\)；令\(y=0\)，则\(x=45\)，可得直线\(2x+3y=90\)与坐标轴的交点\((0,30)\)和\((45,0)\)，画出直线及直线下方区域（因为是\(2x+3y\leq90\)）。再结合\(x\geq0\)，\(y\geq0\)，可行域是一个四边形区域（包括边界）。然后求目标函数\(z=7x+6y\)在可行域内的最大值。把目标函数变形为\(y=\frac{7}{6}x+\frac{z}{6}\)，\(\frac{z}{6}\)是直线\(y=\frac{7}{6}x+\frac{z}{6}\)在\(y\)轴上的截距，要使\(z\)最大，就是要使截距最大。通过平移直线\(y=\frac{7}{6}x\)，当直线经过可行域内的点时，找到在\(y\)轴上截距最大的情况。联立\(\begin{cases}4x+3y=120\\2x+3y=90\end{cases}\)，两式相减得\(2x=30\)，解得\(x=15\)，代入\(2x+3y=90\)得\(30+3y=90\)，解得\(y=20\)。即交点坐标为\((15,20)\)，把\((15,20)\)代入目标函数\(z=7x+6y\)得\(z=7×15+6×20=105+120=225\)（万元）。

所以，生产甲产品15件，乙产品20件时，利润最大为225万元。

（二）例题2某运输公司有7辆载重量为6吨的A型卡车与4辆载重量为10吨的B型卡车，有9名驾驶员。在建筑某段高速公路中，该公司承包了每天至少搬运360吨沥青的任务。已知每辆卡车每天往返的次数为A型车8次，B型车6次；每辆卡车每天的成本费A型车160元，B型车252元。问每天派出A型车与B型车各多少辆，公司所花的成本费最低？

解题步骤1.设未知数：设每天派出A型车\(x\)辆，B型车\(y\)辆。2.列出约束条件：\(x\leq7\)（A型车数量限制）\(y\leq4\)（B型车数量限制）\(x+y\leq9\)（驾驶员数量限制）\(6×8x+10×6y\geq360\)，化简得\(4x+5y\geq30\)（搬运任务限制）\(x\geq0\)，\(y\geq0\)（车辆数量非负）3.确定目标函数：成本\(z=160x+252y\)，要使\(z\)最小。4.求解：画出约束条件所表示的可行域。\(x\leq7\)是直线\(x=7\)及其左侧区域。\(y\leq4\)是直线\(y=4\)及其下方区域。\(x+y\leq9\)是直线\(x+y=9\)及其下方区域。\(4x+5y\geq30\)是直线\(4x+5y=30\)及其上方区域。可行域是一个多边形区域（包括边界）。把目标函数变形为\(y=\frac{160}{252}x+\frac{z}{252}\)，通过平移直线求在可行域内截距最小的情况。分别将可行域的顶点坐标代入目标函数。联立\(\begin{cases}x+y=9\\4x+5y=30\end{cases}\)，由\(x+y=9\)得\(x=9y\)，代入\(4x+5y=30\)得\(4(9y)+5y=30\)，\(364y+5y=30\)，\(y=6\)（舍去）。再通过解其他交点坐标并代入目标函数比较。当\(x=5\)，\(y=2\)时，\(z=160×5+252×2=800+504=1304\)（元）。

所以，每天派出A型车5辆，B型车2辆时，公司所花成本费最低为1304元。

三、任务分配规划问题

（一）例题1有四项任务\(A\)、\(B\)、\(C\)、\(D\)，要分配给甲、乙、丙、丁四个人去完成。每个人完成各项任务所需时间如下表所示：

|任务\(\downarrow\)人员\(\rightarrow\)|甲|乙|丙|丁||||||||A|10|5|9|18||B|13|14|16|11||C|3|2|4|4||D|18|6|10|9|

问如何分配任务，可使总完成时间最短？

解题步骤1.匈牙利算法：第一步，找出每行的最小值，然后从每行中减去这个最小值。第一行最小值是5，得到：|任务\(\downarrow\)人员\(\rightarrow\)|甲|乙|丙|丁||||||||A|5|0|4|13||B|2|3|5|0||C|1|0|2|2||D|12|0|4|3|第二步，找出每列的最小值，然后从每列中减去这个最小值。|任务\(\downarrow\)人员\(\rightarrow\)|甲|乙|丙|丁||||||||A|4|0|2|11||B|1|3|3|0||C|0|0|0|0||D|11|0|2|1|第三步，用最少的直线覆盖所有的0。可以发现用三条直线（第一行、第二行、第三列）可以覆盖所有0。第四步，在没有被直线覆盖的数中找出最小值1，从没有被直线覆盖的数中减去1，在直线相交的数上加1。得到：|任务\(\downarrow\)人员\(\rightarrow\)|甲|乙|丙|丁||||||||A|3|0|2|10||B|0|3|3|0||C|1|1|1|0||D|10|0|2|0|第五步，再用最少的直线覆盖所有的0，发现此时需要四条直线，说明已得到最优分配。最优分配方案为：甲做\(B\)任务，乙做\(A\)任务，丙做\(C\)任务，丁做\(D\)任务。总完成时间为\(13+5+4+9=31\)。

（二）例题2某车间有甲、乙、丙三台机床，可用于加工三种零件\(A\)、\(B\)、\(C\)。已知这三台机床加工这三种零件所需的工时如下表所示：

|机床\(\downarrow\)零件\(\rightarrow\)|A|B|C|||||||甲|3|5|9||乙|4|2|8||丙|8|1|2|

每个零件都需要加工，问如何分配机床加工任务，可使总的加工工时最少？

解题步骤1.同样采用匈牙利算法：第一步，找出每行最小值并减去。第一行最小值3，得到：|机床\(\downarrow\)零件\(\rightarrow\)|A|B|C|||||||甲|0|2|6||乙|2|0|6||丙|7|0|1|第二步，找出每列最小值并减去。|机床\(\downarrow\)零件\(\rightarrow\)|A|B|C|||||||甲|0|2|5||乙|2|0|5||丙|7|0|0|第三步，用最少直线覆盖所有0。可以用三条直线覆盖所有0。第四步，在未被覆盖数中找最小值2，未覆盖数减2，直线相交数加2。得到：|机床\(\downarrow\)零件\(\rightarrow\)|A|B|C|||||||甲|0|0|3||乙|0|0|3||丙|9|0|2|第五步，再用最少直线覆盖所有0，此时需要四条直线，已得最优分配。最优分配方案：甲加工\(A\)零件，乙加工\(B\)零件，丙加工\(C\)零件。总加工工时为\(3+2+2=7\)。

四、资源分配规划问题

（一）例题1某公司有资金100万元，准备投资甲、乙、丙三个项目。已知投资甲项目可获利20%，投资乙项目可获利15%，投资丙项目可获利25%。但投资甲项目需占用资金30万元及10个工作日的时间；投资乙项目需占用资金20万元及20个工作日的时间；投资丙项目需占用资金50万元及30个工作日的时间。该公司有资金100万元，且可提供60个工作日的时间。问如何分配投资，可使公司获得最大利润？

解题步骤1.设未知数：设投资甲项目\(x\)万元，投资乙项目\(y\)万元，投资丙项目\(z\)万元。2.列出约束条件：\(x+y+z\leq100\)（资金限制）\(\frac{10}{30}x+\frac{20}{20}y+\frac{30}{50}z\leq60\)，化简得\(\frac{1}{3}x+y+\frac{3}{5}z\leq60\)（工作日时间限制）\(x\geq0\)，\(y\geq0\)，\(z\geq0\)（投资金额非负）3.确定目标函数：利润\(z=0.2x+0.15y+0.25z\)，要使\(z\)最大。4.求解：利用线性规划的方法求解。先将\(\frac{1}{3}x+y+\frac{3}{5}z\leq60\)两边同乘15化为\(5x+15y+9z\leq900\)。联立\(\begin{cases}x+y+z=100\\5x+15y+9z=900\end{cases}\)，由\(x+y+z=100\)得\(x=100yz\)，代入\(5x+15y+9z=900\)得：\(5(100yz)+15y+9z=900\)，\(5005y5z+15y+9z=900\)，\(10y+4z=400\)，\(5y+2z=200\)，\(y=40\frac{2}{5}z\)。代入目标函数\(z=0.2(100yz)+0.15y+0.25z\)，