10简单线性规划问题2精要.ppt

练习题 1、某厂拟生产甲、乙两种适销产品，每件销售收入分别为3000元、2000元，甲、乙产品都需要在A、B两种设备上加工，在每台A、B上加工1件甲所需工时分别为1h、2h，加工1件乙所需工时分别为2h,1h.A、B两种设备每月有效使用台时数分别为400h和500h。如何安排生产可使收入最大？ Z＝ 3x＋2y 变形为它表示斜率为 的直线系，Z与这条直线的截距有关。 备用题已知的 三边长 满足 求 的取值范围。 * * x y o 简单的线性规划问题（二） 二.回顾解线性规划问题的步骤 （2）移：在线性目标函数所表示的一组平行线 中，利用平移的方法找出与可行域有公共点且纵 截距最大或最小的直线 （3）求：通过解方程组求出最优解； （4）答：作出答案。 （1）画：画出线性约束条件所表示的可行域； 例1．A、B两个居民小区的居委会组织本小区的中学生，利用双休日去市郊的敬老院参加献爱心活动，两个小区都有同学参加。已知A区的每位同学往返车费是3元，每人可为5位老人服务；B区的每位同学往返车费是5元，每人可为3位老人服务。如果要求B区参与活动的同学比A区的同学多，且去敬老院的往返总车费不超过37元。怎样安排参与活动同学的人数，才能使受到服务的老人最多？受到服务的老人最多是多少人？ 解：设A、B两区参与活动的人数分别为x，y受到服务的老人人数为z， 则z=5x+3y， 应满足的约束条件是 化简得 根据上述不等式组，作出表示可行域的平面区域，如图阴影部分所示。 画直线l0：5x+3y=0，平行移动l0到直线l的位置，使l过可行域中的某点，并且可行域内的其它各点都在l的包含直线l0的同一侧。 该点到直线l0的距离最大，则这一点的坐标使目标函数取最大值。 容易看出，点M符合上述条件，点M是直线x－5y+1=0与直线3x+3y=37的交点。 解方程组 得点M(4，5)。 因此，当x=4，y=5时，z取得最大值，并且zmax=5×4+3×5=35. 答：A、B两区参与活动同学的人数分别为4，5时，受到服务的老人最多，最多为35人。 制约 的所有相应整数值， 说明：最优整数解常有两种处理方法，一种是: 通过打出网格求整点，关键是作图要准确；另一 种是:先确定区域内点的横坐标范围，确定 或y 的所有整数值，再代回原不等式组，得出 一元一次不等式组，再确定 ，再用 即先固定 的 例2: 例3、要将两种大小不同规格的钢板截成A、 B、C三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示 ： 规格类型 钢板类型 第一种钢板 第二种钢板 A规格 B规格 C规格 2 1 2 1 3 1 今需要A,B,C三种规格的成品分别为15，18，27块，问各截这两种钢板多少张可得所需三种规格成品，且使所用钢板张数最少。 解：设需截第一种钢板x张、第二种钢板y张，可得 x 0 y 2x+y=15 x+3y=27 x+2y=18 x+y =0 2x+y≥15, { x+2y≥18, x+3y≥27, x≥0, x∈N* y≥0 y∈N* 经过可行域内的整点B(3,9)和C(4,8)且和原点距离最近的直线是x+y=12，它们是最优解. 答:(略) 作出一组平行直线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=11.4继续向上平移, 2x+y=15 x+3y=27 x+2y=18 x+y =0 直线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 x+y=12 解得交点B,C的坐标B(3,9)和C(4,8) 调整优值法 2x+y≥15, { x+2y≥18, x+3y≥27, x≥0, x∈N* y≥0 y∈N* x 0 y 1. 线性规划的讨论范围：教材中讨论了两个变量的线性规划问题，这类问题可以用图解法来求最优解，但涉及更多变量的线性规划问题不能用图解法来解； 2. 求线性规划问题的最优整数解时，常 用打网格线和调整优值的方法，这要求作图必须精确，线性目标函数对应的直线斜率与其他直线的斜率关系要把握准确 15 ex2 解：设投资方对甲、乙两个项目各投资x、y万元 依题意线性约束条件为： 目标函数为： 作出可行域 可知直线Z=x+0.5y通过点