《简单的线性规划求最优解》由会员分享，可在线阅读，更多相关《简单的线性规划求最优解（5页珍藏版）》请在金锄头文库上搜索。
1、教你如何做出最佳选择简单的线性规划求最优解在线性约束条件下，求线性目标函数最值问题，称为“线性规划”。目标函 数z = f （x, y）取得最值时，变量x, y的对应解（x, y）称为最优解。若x, y e Z时，z 取得最值，称（x, y）为最优整数解，简称整解。点（x, y）的横、纵坐标都是整数， 称为整点。求最优整解问题出现在高中数学新教材中，常见的实际应用题型有两种，（1） 给出一定数量的人力、物力资源，问怎样安排能使完成的任务量最大，收益最大； （2）给出一项任务，问怎样统筹安排，能使完成这项任务投入的人力、物力最 小。因为研究的对象是人、物等个体，故x, y往往是整数，较x, y不
2、是整数时求 解困难，所以这是一个应用数学知识解决实际问题的新难点，加之教材介绍较为 笼统简略，对教师和学生的理解掌握造成了一定的困难，针对这一问题，总结两 种寻找最优整解的方法与大家探讨。这两种求解方法分别是：调整优值法（简称调值法）、枚举整点法（简称枚举 法）。调值法是先求非整点最优解，再借助不定方程，调整最优解，最后筛选出 最优解；枚举法，因为取得最值的整点分布在可行域内，可从x,y中选取系数的 绝对值较大的一个对其逐一取值，以此为标准分类讨论，取得另一变量的最值， 代入目标函数，比较函数值大小，找到最优解。下面通过几个典型例题，介绍一下这几种方法的具体运用。例 1（调整优值法）要将两种大
3、小不同的钢板截成 A、 B、 C 三种规格，每张 钢板可同时截得三种规格的小钢板的块数如下表所示：规格类型 钢板类型、A规格B规格C规格第一种钢板211第二种钢板123今需A、B、C三种规格的成品分别为15、18、27块，问各截这两种钢板多少张可得所需三种规格成品，且使所用钢板张数最少？解析：设需要第一种钢板x张，第二种钢板y张，钢板总数z张，则2 x + y 15目标函数 z x yx + 2 y 18x + 3 y 27x g N, y g N=+作出可行域如图所示，作出直线x y 0。作出一组平行直线x y t （其10A50中t为参数）。52x+y=15 K-b2y= IS015250
4、 K+3y=27其中经过可行域内的点且和原点距离最近的直线，经过直线x + 3y二27和直线2x + y = 15的交点A（兰，聖），直线方程为x + y =。5 55由于18和39都不是整数，而最优解x, y中，x, y必须都是整数，所以，可55行域内点a（158,39）不是最优解。J J 经过可行域内的整点（横坐标和纵坐标都是整数的点），且与原点距离最近的直线是x y 12。经过的整点是B（3，9）和C（4, 8），它们是最优解。故要截得所需三种规格的钢板，且使所截两种钢板的张数最少的方法有两 种，第一种截法是截第一种钢板 3 张、第二种钢板 9 张；第二种截法是截第一种 钢板4张、第二种
5、钢板8张。两种方法都最少要截两种钢板共12张。点评：在解线性规划问题时，常有一些实际问题需要变量取整数解时才有实 际意义，而当可行域中的最优解不是整数解时，需作出可行域的整点作出判断。 当直接观察比较困难时，应对可能的情况进行检验。线性规划整数解问题的一般 处理方法是：若区域“顶点”处恰为整点，那么它的最优解在“顶点”处取得（在 包括边界的情况下）；若区域的“顶点”不是整数点也不包括边界时，可以先算 出目标函数 z 的值，在可行域内适当放缩目标函数的值，使他为整数，且与 z 最接近，在 这条对应的直线，取可行域内的整点。如果没有整点，继续放缩，直至取到整点为止。这种方法称为调整优值法。也可以通
6、过画出网格，平移直线，运用图解法求得。例 2(枚举法) 某人有楼房一栋，室内面积共 180 m2 ,拟分隔成两类房间作为 旅游客房，大房间每间面积为 18 m2 ，可住游客 5 名，每名游客每天住宿费为 40 元，小房间每间面积为 15 m2 ，可住旅客3名，每名游客每天住宿费为50元， 装修大房间每间需 1000 元，装修小房间每间需 600 元，如果他只能筹款 8000 元用于装修，且假设游客能住满客房，它隔出大房间和小房间各多少间会获得最 大收益？最大收益是多少？解：设隔出大、小房间分别为x间，y间,收益为f元,则f 200x 150y，其中x, y满足6 x5 xx5 y 603 y
7、40 比- 切-A如图所示，由图解法易得f 200x 150y ,过点 空,607 7、时，目标函数 f 取得最大值。但x, y必须是整数，还需在可行区域内找出使目标函数f取得最大值的整 点。显然目标函数 f 取得最大值的整点一定是分布在可行区域的右上侧，则利用 枚举法即可求出整点最优值。这些整点有： (0, 12), (1, 10),(2, 9), (3, 8), (4, 6),(5, 5), (6, 3), (7,1 ), (8, 0)，分别代入 f 200x 150y。逐一验证，当取整点(0, 12 )或(3, 8)时，获得最大收益。所以获得最大收益有两种方案：1只隔出小房间12间。II隔出大房间3间，小房间8间，最大收益均为1800元。注：如果把装修考虑在内，则选择第一方案好。枚举整点法的主要步骤是验算-筛选，而优值调整法更注重推理计算。它们的共同步骤是：1. 建模(审题、设元、列式)，2.求解(画图、移线、求解)3.检验（还原）。总之，对于线性规划实际应用题，应采用数形结合的思想来分析、解答，各种方法各有利弊，在使用时要根据题设条件选用适当的方法解答。
