332简单的线性规划问题B.ppt

《332简单的线性规划问题B.ppt》由会员分享，可在线阅读，更多相关《332简单的线性规划问题B.ppt（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章 不等式不等式3.3.2 3.3.2 简单的线性规划问题简单的线性规划问题 符洪峰符洪峰如果若干年后的你成为某如果若干年后的你成为某工厂的厂长，你将会面对工厂的厂长，你将会面对生产安排、资源利用、人生产安排、资源利用、人力调配的问题力调配的问题【引例】：【引例】：某工厂用某工厂用A A、B B两种配两种配件生产甲、乙两种产件生产甲、乙两种产品，每生产一件甲产品，每生产一件甲产品使用品使用4 4个个A A配件并耗配件并耗时时1h1h，每生产一件乙，每生产一件乙产品使用产品使用4 4个个B B配件并配件并耗时耗时2h2h，该厂每天最，该厂每天最多可从配件厂获得多可从配件厂获得1616个

2、个A A配件和配件和1212个个B B配件，配件，按每天工作按每天工作8h8h计算，计算，该厂所有可能的日生该厂所有可能的日生产安排是什么？产安排是什么？ 数据分析表：数据分析表：日生产日生产满足满足402乙产品乙产品041甲产品甲产品B配件配件（个）（个）A配件配件（个）（个）每件耗时每件耗时（h）12816应用举例应用举例248642【优化条件】：【优化条件】：若生产一件甲产若生产一件甲产品获利品获利2万元，生万元，生产一件乙产品获产一件乙产品获利利3万元，采用哪万元，采用哪种生产安排获得种生产安排获得利润最大？利润最大？ M M ( ( 4 4 , , 2 2 ) )233zyx 23z

3、xy应用举例应用举例zmax=24+32=14线性规划：求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题 可行解 ：满足线性约束条件的解(x，y)叫可行解； 可行域 ：由所有可行解组成的集合叫做可行域； 最优解 ：使目标函数取得最大或最小值的可行解叫线性规划问题的最优解。 解线性规划问题的步骤：解线性规划问题的步骤： 2 2、在线性目标函数所表示的一组平行、在线性目标函数所表示的一组平行 线中，用平移的方法找出与可行域有公线中，用平移的方法找出与可行域有公 共点且纵截距最大或最小的直线；共点且纵截距最大或最小的直线； （注意（注意y y的系数的系数“+ +，-”-”）

4、3 3、通过、通过解方程组求出最优解；解方程组求出最优解； 4 4、作出、作出答案。答案。 1 1、画、画出线性约束条件所表示的可行域；出线性约束条件所表示的可行域；画画移移求求答答 解线性规划应用问题的一般步骤：1、理清题意，列出表格；、理清题意，列出表格；2、设好变元，列出线性约束条件、设好变元，列出线性约束条件 （不等式组）与目标函数；（不等式组）与目标函数；3、准确作图；、准确作图；4、根据题设精确度计算。、根据题设精确度计算。例例1 营养学家指出，成人良好的日常饮食应该至少提营养学家指出，成人良好的日常饮食应该至少提供供0.075kg的碳水化合物，的碳水化合物，0.06kg的蛋白质，

5、的蛋白质，0.06kg的脂肪，的脂肪，1kg食物食物A含有含有0.105kg碳水化合物，碳水化合物，0.07kg蛋白质，蛋白质，0.14kg脂肪，花费脂肪，花费28元；而元；而1食物食物B含有含有0.105kg碳水化合物，碳水化合物，0.14kg蛋白质，蛋白质，0.07kg脂肪，脂肪，花费花费21元。为了满足营养专家指出的日常饮食要求，元。为了满足营养专家指出的日常饮食要求，同时使花费最低，需要同时食用食物同时使花费最低，需要同时食用食物A和食物和食物B多少多少kg？食物kg碳水化合物kg蛋白质/kg脂肪kgAB分析：将已知数据列成表格分析：将已知数据列成表格0.1050.1050.070.1

6、40.140.07日常饮食含量0.0750.060.06解：设每天食用解：设每天食用xkg食物食物A，ykg食物食物B，总成本为总成本为z，那么，那么00671461475770006.007.014.006.014.007.0075.010.0105.0yxyxyxyxyxyxyxyx目标函数为：目标函数为：z28x21y作出二元一次不等式组所表示的平面区域，即可行域作出二元一次不等式组所表示的平面区域，即可行域把目标函数把目标函数z28x21y 变形为变形为xyo5/75/76/73/73/76/72834zxy 它表示斜率为它表示斜率为随随z变化的一组平行直变化的一组平行直线系线系34

7、是直线在是直线在y轴上轴上的截距，当截距最的截距，当截距最小时，小时，z的值最小。的值最小。28zM 如图可见，当直线如图可见，当直线z28x21y 经过可经过可行域上的点行域上的点M时，截距时，截距最小，即最小，即z最小。最小。M点是两条直线的交点，解方程组点是两条直线的交点，解方程组6714577yxyx得得M点的坐标为：点的坐标为：7471yx所以所以zmin28x21y16 由此可知，每天食用食物由此可知，每天食用食物A143g，食物，食物B约约571g，能够满足日常饮食要求，又使花费最低，能够满足日常饮食要求，又使花费最低，最低成本为最低成本为16元。元。 例2 要将两种大小不同的钢

8、板截成A、B、C三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示 A规格 B规格 C规格 第一种钢板 2 1 1 第二种钢板 1 2 3今需要A、B、C三种规格的成品分别为15、18、27块，问各截这两种钢板多少张可得所需三种规格成品，且使所用钢板张数最少. 解：设需截第一种钢板x张，第二种钢板y张2x + y x + 2 y x + 3 y x y 约束条件是作出可行域见课本图3.3-12目标函数是z=x+y此问题中，钢板张数为整数，在一组平行直线x+y=t中（t为参数），经过的整点是B(3,9) 和C(4,8),它们是最优解518虽然直线经过点A时，与原点距离最近，539经过可

9、行域内的整点（横坐标和纵坐标都是整数的点）且与原点距离最近的直线是x+y=12,但是由但是由得得273152yxyx539518yx即点A( , )坐标不是整点，不合题意答：要截得所需三种规格的钢板，且使所截两种钢板的张数最少的方法有两种，第一种截法是截第一种钢板3张、第二种钢板9张；第二种截法是截第一种钢板4张，截第二种钢板8张.两种方法都最少要截两种钢板共12张。练习练习1 1、一个化肥厂生产甲、乙两种混合肥料，生产、一个化肥厂生产甲、乙两种混合肥料，生产1 1车皮甲种肥料的主要原料是磷酸盐车皮甲种肥料的主要原料是磷酸盐4t4t、硝酸盐、硝酸盐18t18t；生；生产产1 1车皮乙种肥料需要

10、的主要原料是磷酸盐车皮乙种肥料需要的主要原料是磷酸盐1t1t、硝酸盐、硝酸盐15t15t。现库存磷酸盐。现库存磷酸盐10t10t、硝酸盐、硝酸盐66t66t，在此基础上生产，在此基础上生产这两种混合肥料。列出满足生产条件的数学关系式，这两种混合肥料。列出满足生产条件的数学关系式，并画出相应的平面区域。并计算生产甲、乙两种肥料并画出相应的平面区域。并计算生产甲、乙两种肥料各多少车皮，能够产生最大的利润？各多少车皮，能够产生最大的利润？解：设解：设x、y分别为计划生产甲、乙两种混合分别为计划生产甲、乙两种混合肥料的车皮数，于是满足以下条件：肥料的车皮数，于是满足以下条件：xyo0y0 x6615y

11、18x10y4x解：设生产甲种肥料解：设生产甲种肥料x车皮、乙种肥料车皮、乙种肥料y车皮，能够产车皮，能够产生利润生利润Z万元。目标函数为万元。目标函数为Zx0.5y，可行域如图：，可行域如图：把把Zx0.5y变形为变形为y2x2z，它表示斜率为，它表示斜率为2，在，在y轴上的截距为轴上的截距为2z的一组直线系。的一组直线系。 xyo由图可以看出，当直线经过可行域上的点由图可以看出，当直线经过可行域上的点M时，时，截距截距2z最大，即最大，即z最大。最大。 故生产甲种、乙种肥料各故生产甲种、乙种肥料各2车皮，能够产生最大利润，车皮，能够产生最大利润，最大利润为最大利润为3万元。万元。M 容易求

12、得容易求得M点的坐标为点的坐标为（2，2），则），则Zmin3练习2.某厂拟生产甲、乙两种适销产品，每件销售收某厂拟生产甲、乙两种适销产品，每件销售收入分别为入分别为3000元、元、2000元，甲、乙产品都需要在元，甲、乙产品都需要在A、B两种设备上加工，在每台两种设备上加工，在每台A、B上加工上加工1件甲所需工时分件甲所需工时分别为别为1h、2h，A、B两种设备每月有效使用台数分别为两种设备每月有效使用台数分别为400h和和500h。如何安排生产可使收入最大？。如何安排生产可使收入最大？ 解解 设每月生产甲产品设每月生产甲产品x件，生产乙产品件，生产乙产品y件，每月收件，每月收入为入为z，目标函数为，目标函数为Z3x2y，满足的条件是，满足的条件是0050024002yxyxyx Z 3x2y 变形为变形为它表示斜率为它表示斜率为 的直线系，的直线系，Z与这条直线的截距有关。与这条直线的截距有关。223zxy23XYO400200250500 当直线经过点当直线经过点M时，截距最大，时，截距最大，Z最大。最大。M解方程组解方程组50024002yxyx可得可得M（200，100）Z 的最大值的最大值Z 3x2y800故生产甲产品故生产甲产品200件，件，乙产品乙产品100件，收入件，收入最大，为最大，为80万元。万元。