简单线性规划问题课件

1、简单线性规划问题课件 简单线性规划（简单线性规划（2） 简单线性规划问题课件 【教学目标】【教学目标】 1 1进一步理解二元一次不等式表示平面区域进一步理解二元一次不等式表示平面区域 2.2.进一步理解线性规划的意义以及约束条件进一步理解线性规划的意义以及约束条件 、目标函数、可行解、可行域、最优解等基、目标函数、可行解、可行域、最优解等基 本概念；本概念； 3.3.进一步理解线性规划问题的图解法，并能进一步理解线性规划问题的图解法，并能 应用它解决一些简单的实际问题；应用它解决一些简单的实际问题； 4.4.会求线性规划的整点最优解。会求线性规划的整点最优解。 【教学重点】【教学重点】 用图解

2、法解决简单的线性规划问题用图解法解决简单的线性规划问题 【教学难点】【教学难点】 准确求得线性规划问题的最优解准确求得线性规划问题的最优解 简单线性规划问题课件 例1 某工厂用某工厂用A、B两种配件生产甲、乙两种产品，两种配件生产甲、乙两种产品， 每生产一件甲产品使用每生产一件甲产品使用4个个A配件耗时配件耗时1h，每生产一，每生产一 件乙产品使用件乙产品使用4个个B配件耗时配件耗时2h，该厂每天最多可从，该厂每天最多可从 配件厂获得配件厂获得16个个A配件和配件和12个个B配件，按每天工作配件，按每天工作8h 计算，该厂所有可能的日生产安排是什么？计算，该厂所有可能的日生产安排是什么？ 按甲

3、、乙两种产品分别生产按甲、乙两种产品分别生产x、y件，由件，由 已知条件可得二元一次不等式组已知条件可得二元一次不等式组 2 y828 4 x1 64 4 y1 23 x0 , xZ0 , xZ y0 , yZ0 , yZ xxy x y x y 简单线性规划问题课件 将上述不等式组表示成平面上的区域，图中的阴影部将上述不等式组表示成平面上的区域，图中的阴影部 分中的就代表所有可能的日生产安排。分中的就代表所有可能的日生产安排。 y x 48 4 3 o 提出新问题：提出新问题： 若生产一件甲产品获利若生产一件甲产品获利2万元，生万元，生 产一件乙产品获利产一件乙产品获利3万元，采用那种生产安

4、排利润最万元，采用那种生产安排利润最 大？大？ 把把z2x3y变形为变形为 它表示斜率为它表示斜率为 的的 直线系，直线系，z与这条直线与这条直线 的截距有关。的截距有关。 33 2z xy 3 2 M 引申：若甲、乙获利为若甲、乙获利为1万元、万元、2万元，则如何安排生产？万元，则如何安排生产？ 简单线性规划问题课件 例例2 要将两种大小不同规格的钢板截成要将两种大小不同规格的钢板截成A、B、C三种规格，三种规格， 每张钢板可同时截得三种规格的小钢板的块数如下表所示每张钢板可同时截得三种规格的小钢板的块数如下表所示 ： 解：解：设需截第一种钢板设需截第一种钢板x张，第一种钢板张，第一种钢板y

5、张，则张，则 规格类型规格类型 钢板类型钢板类型 第一种钢板第一种钢板 第二种钢板第二种钢板 A规格规格B规格规格C规格规格 2 12 1 3 1 2x+y15, x+2y18, x+3y27, x0 y0 作出可行域（如图）作出可行域（如图） 目标函数为目标函数为 z=x+y 今需要今需要A,B,C三种规格的成品分别为三种规格的成品分别为15，18，27块，问块，问 各截这两种钢板多少张可得所需三种规格成品，且使所各截这两种钢板多少张可得所需三种规格成品，且使所 用钢板张数最少。用钢板张数最少。 X张张 y张张 简单线性规划问题课件 x 0 y 2x+y=15 x+3y=27 x+2y=18

6、 x+y =0 2x+y15, x+2y18, x+3y27, x0, xN y0 yN 直线直线x+y=12经过的整点是经过的整点是B(3,9)和和C(4,8)，它们是最优解，它们是最优解. 作出一组平行直线作出一组平行直线z=x+y， 目标函数目标函数z= x+y B(3,9) C(4,8) A(18/5,39/5) 当直线经过点当直线经过点A时时z=x+y=11.4, x+y=12 解得交点解得交点B,C的坐标的坐标B(3,9)和和C(4,8) 调整优值法调整优值法 2 4 6 1812827 2 4 6 8 10 15 但它不是最优整数解但它不是最优整数解.作直线作直线x+y=12 答

7、（略）答（略） 简单线性规划问题课件 x 0 y 2x+y=15 x+3y=27x+2y=18 x+y =0 2x+y15, x+2y18, x+3y27, x0, xN* y0 yN* 经过可行域内的整点经过可行域内的整点B(3,9)和和C(4,8)时，时，t=x+y=12是最优解是最优解. 答答:(略略) 作出一组平行直线作出一组平行直线t = x+y， 目标函数目标函数t = x+y B(3,9) C(4,8) A(18/5,39/5) 打网格线法打网格线法 在可行域内打出网格线，在可行域内打出网格线， 当直线经过点当直线经过点A时时t=x+y=11.4,但它不是最优整数解但它不是最优整

8、数解， 将直线将直线x+y=11.4继续向上平移继续向上平移， 12 1 2 1827 15 9 78 简单线性规划问题课件 练习练习某工厂家具车间造型两类桌子，每张桌子需某工厂家具车间造型两类桌子，每张桌子需 木工和漆工两道工序完成已知木工做一张型桌子分木工和漆工两道工序完成已知木工做一张型桌子分 别需要别需要1小时和小时和2小时，漆工油漆一张型桌子分别需要小时，漆工油漆一张型桌子分别需要 3小时和小时和1小时；又知木工、漆工每天工作分别不得超小时；又知木工、漆工每天工作分别不得超 过过8小时和小时和9小时，而两类型桌子分别获利润小时，而两类型桌子分别获利润2千元和千元和3 千元，试问工厂每

9、天应生产两类型桌子各多少张，才千元，试问工厂每天应生产两类型桌子各多少张，才 能获利润最大？能获利润最大？ 目标函数为目标函数为. 获利润为获利润为 千元，则千元，则 设每天生产型桌子张，设每天生产型桌子张， 型桌子张，每天所型桌子张，每天所A xB y Z .0 ,0 ,93 , 82 y x yx yx yxZ32 解：解： 简单线性规划问题课件 且与原点距离最大，此时取得最大值且与原点距离最大，此时取得最大值 上方平移至的位置时，直线经过可行域上的点，上方平移至的位置时，直线经过可行域上的点， l032 yx lM yxZ32 如图，作出可行域，把直线：如图，作出可行域，把直线： 向右向

10、右 引申：两类型桌子引申：两类型桌子 分别获利润分别获利润3千元千元 和和1千元，试问工千元，试问工 厂每天应如何安排厂每天应如何安排 生产生产 简单线性规划问题课件 答：每天应生产型桌子答：每天应生产型桌子2张，张， 型桌子型桌子3张才能张才能 解方程组解方程组 得得. , 93 , 82 yx yx 3 , 2M AB 获最大利润获最大利润 简单线性规划问题课件 以实际问题为背景的线性规划问题其求解的以实际问题为背景的线性规划问题其求解的 格式与步骤格式与步骤: (1)寻找线性约束条件寻找线性约束条件,线性目标函数线性目标函数; (2)由二元一次不等式表示的平面区域做出可行域由二元一次不等式表示的平面区域做出可行域; (3)在可行域内求目标函数的最优解在可行域内求目标函数的最优解; (4)注意问题的实