3.3.2简单的线性规划问 第2课时
复司回顺 解线性规划问题的步骤: (1)列:设出未知数列出约束条件和目标函数 (2)画:画可行域; (3)移:作l,利用平移的方法找出与可行域有公共 点且纵截距最大或最小的直线; (4)求:通过解方程组求出最优解; (5)答:作出答案
解线性规划问题的步骤： （3）移：作l0，利用平移的方法找出与可行域有公共 点且纵截距最大或最小的直线； （4）求：通过解方程组求出最优解； （5）答：作出答案。 （2）画：画可行域； （1）列：设出未知数,列出约束条件和目标函数； 一、复习回顾
练习:求z=3x+5y的最大值和最小值使xy满足约束条件 5x+3y≤15, y≤x+1, x-5y≤3. J=x+1 B,25) Z=17 n x-5y=3 若约束条件改为 5x+3y≤15, y≤x A(-2,-1) 5x+3=15 x-5y<3. 3x+5y=0
5 3 15, 1, 5 3. x y y x x y + + − 3 5 1 A B x y o 5x + 3y = 15 y = x + 1 x − 5y = 3 (1.5,2.5) (-2,-1) Zmax =17 Zmin =-11 练习：求z=3x+5y的最大值和最小值,使x,y满足约束条件 C 3x+5y=0 若约束条件改为 5 3 15, 1, 5 3. x y y x x y + + −
二、例题分析 例1、某公司计划2011年在甲、乙两个电视台做总时间不超过 300分钟的广告,广告总费用不超过9万元。甲、乙电视台的 广告收费标准分别为500元/分钟和200元分钟。假定甲、乙两 个电视台为该公司所做的每分钟广告,能给公司带来的收益分别 为0.3万元和0.2万元,问该公司如何分配在甲、乙两个电视台 的广告时间,才能使公司的收益最大,最大收益是多少万元? 解:设公司在甲电视台和乙电视台做广告的时间分别 为x分钟和分钟,总收益为元,由题意得 x+y≤300 x+y≤300 500x+200y≤90005x+2y≤900 x≥0,y≥0 x≥0,y≥0 目标函数为z=3000x+2000y
例1、某公司计划2011年在甲、乙两个电视台做总时间不超过 300分钟的广告，广告总费用不超过9万元。甲、乙电视台的 广告收费标准分别为500元/分钟和200元/分钟。假定甲、乙两 个电视台为该公司所做的每分钟广告，能给公司带来的收益分别 为0.3万元和0.2万元，问该公司如何分配在甲、乙两个电视台 的广告时间，才能使公司的收益最大，最大收益是多少万元？ 解：设公司在甲电视台和乙电视台做广告的时间分别 为x分钟和y分钟，总收益为z元，由题意得 300 500 200 90000, 0, 0 x y x y x y + + 目标函数为z=3000x+2000y. 二、例题分析 300 5 2 900 0, 0 x y x y x y + + 即
作出二元一次不等式组所表示的平面 区域,即可行域,如图 500 3 将z=3000x+2000化为y=-。x+ 22000 300 M 3 这是一组斜率为-二,纵截距为 2 2000 的平行直线 O100\300 由图知,当直线M点时,目标函数取得最大值 联立 x+y=300 5x+2y=900 解得x=100,y=200 点M(100,200,∴m=3000+2000=700000 答:该公司在甲电视台做100分钟广告,在乙电视台做 200分钟广告。公司的收益最大,最大值为70万元
作出二元一次不等式组所表示的平面 区域，即可行域，如图. 由图知，当直线l过M点时，目标函数取得最大值 300 , 5 2 900 x y x y + = + = 联立 ∴点M (100，200), 答：该公司在甲电视台做100分钟广告，在乙电视台做 200分钟广告。公司的收益最大，最大值为70万元. 解得x=100，y=200， ∴zmax=3000x+2000y=700000(元) 将z=3000x+2000y化为 . 3 1 2 2000 y x z = − + 3 1 2 2000 这是一组斜率为 − ，纵截距为 z 的平行直线
例3、要将两种大小不同规格的钢板截成A、B、C三种规格,每 张钢板可同时截得三种规格的小钢板的块数如下表所示: 规格类型 钢板类型 A规格 B规格C规格 第一种钢板X张 2 第二种钢板y张 2 3 今需要A,B,C三种规格的成品分别为15,18,27块,问各截这两 种钢板多少张可得所需三种规格成品,且使所用钢板张数最少。 解:设需截第一种钢板x张,第一种钢板y张,则 2x+y≥15, x+2y≥18, x+3y>27, 目标函数为zx+y x>0,x∈N 作出可行域(如图) y≥0,x∈N
例3、要将两种大小不同规格的钢板截成A、B、C三种规格，每 张钢板可同时截得三种规格的小钢板的块数如下表所示： 解：设需截第一种钢板 x 张，第一种钢板y 张，则 规格类型 钢板类型 第一种钢板 第二种钢板 A规格 B规格 C规格 2 1 2 1 3 1 作出可行域（如图） 目标函数为 z=x+y 今需要A,B,C三种规格的成品分别为15，18，27块，问各截这两 种钢板多少张可得所需三种规格成品，且使所用钢板张数最少。 X张 y张 2x+y≥15, x+2y≥18, x+3y≥27, x≥0,x∈N y≥0,x∈N
作出可行域(如图)p 凋整优值 目标函数为zx+y 20 化为y=x+z 这是斜率为-1,纵 12B(3,9) x+y=12 截距为的一组平 18/5,39/5C(48) 行直线, 当直线经过点A时 =x+y=11.4 8121620242830x x+3=27 但它不是最优整数解, 2x+y=15x+2y=18 y 作直线x+y=12解得交点BC的坐标B3,9)和C(4,8) 直线x+y=12经过的整点是B(39)和C(4,8),它们是最优解 答(略
2x+y=15 x+2y=18 x+3y=27 x y O 4 8 12 16 20 4 8 12 16 20 24 28 30 B(3,9) A(18/5,39/5) C(4,8) x+y =0 直线x+y=12经过的整点是B(3,9)和C(4,8)，它们是最优解. 目标函数为z= x+y 化为y=-x+z 当直线经过点A时 z=x+y=11.4 解得交点B,C的坐标B(3,9)和C(4,8) 调整优值法 但它不是最优整数解， 作直线 x+y=12 答（略） x+y=12 作出可行域（如图） 这是斜率为-1，纵 截距为z的一组平 行直线
在可行域內找些最解、纜唑觊整 数解问懣的一亦宏是: 1、若区域‘顶点”处恰好为整点,那么它就是最优 解;(在包括边界的情况下) 2、若区域“顶点”不是整点或不包括边界时,应先 求出该点坐标,并计算目标函数值Z,然后在可行域 内适当放缩目标函数值,使它为整数,且与Z最接近, 在这条对应的直线中,取可行域内整点,如果没有整 点,继续放缩,直至取到整点为止。 3、在可行域内找整数解,一般采用平移找解法,即 打网络、找整点、平移直线、找出整数最优解
在可行域内找出最优解、线性规划整 数解问题的一般方法是： 1、若区域“顶点”处恰好为整点，那么它就是最优 解；（在包括边界的情况下） 2、若区域“顶点”不是整点或不包括边界时，应先 求出该点坐标，并计算目标函数值Z，然后在可行域 内适当放缩目标函数值，使它为整数，且与Z最接近， 在这条对应的直线中，取可行域内整点，如果没有整 点，继续放缩，直至取到整点为止。 3、在可行域内找整数解，一般采用平移找解法，即 打网络、找整点、平移直线、找出整数最优解
练习某工厂用A、B两种配件生产甲、乙两种产品,每生产 件甲产品使用4个A配件耗时1h,每生产一件乙产品使 用4个B配件耗时2h,该厂每天最多可从配件厂获得16个A 配件和12个B配件,按每天工作8h计算,该厂所有可能的 日生产安排是什么? 解:设甲、乙两种产品 A配件B配件耗时 分别生产x、p件,则有甲产品4 0 乙产品0 42 x+2y≤8总数16128 4x≤16 x+2y≤8 4y≤12 →10≤x≤4(x,y∈Z) x≥O 0≤y≤3 1≥0
练习.某工厂用A、B两种配件生产甲、乙两种产品，每生产 一件甲产品使用 4 个A配件耗时 1h，每生产一件乙产品使 用4个B配件耗时2h，该厂每天最多可从配件厂获得16个A 配件和12个B配件，按每天工作8 h计算，该厂所有可能的 日生产安排是什么？ 解：设甲、乙两种产品 分别生产x、y件，则有 2 8 0 4 0 3 x y x y + (x，y∈Z) 2 8 4 16 4 12 0 0 x y x y x y ＋ A配件 B配件 耗时 甲产品 乙产品 总数 4 0 1 0 4 2 16 12 8
练习某工厂用A、B两种配件生产甲、乙两种产品,每生产 件甲产品使用4个A配件耗时1h,每生产一件乙产品使 用4个B配件耗时2h,该厂每天最多可从配件厂获得16个A 配件和12个B配件,按每天工作8h计算,该厂所有可能的 日生产安排是什么? x+2y≤8 0≤x≤4(x,y∈Z 0≤y≤3 右图阴影部分中的整点 3 (坐标为整数就代表所 2○ 有可能的日生产安排 6 x+21=8
2 8 0 4 0 3 x y x y + (x，y∈Z) x y O 4 8 4 2 2 6 x=4 y=3 x+2y=8 右图阴影部分中的整点 (坐标为整数)就代表所 有可能的日生产安排。 练习.某工厂用A、B两种配件生产甲、乙两种产品，每生产 一件甲产品使用 4 个A配件耗时 1h，每生产一件乙产品使 用4个B配件耗时2h，该厂每天最多可从配件厂获得16个A 配件和12个B配件，按每天工作8 h计算，该厂所有可能的 日生产安排是什么？