第三章 不等式 第三讲 线性规划问题
科目 高三数学 班级 姓名 时间 2015-10-02
一．复习目标：
1.能用二元一次不等式(组) 表示平面区域，会求表示区域的面积
2.会求目标函数最值及约束条件、目标函数中的参变量的取值范围.
3.能利用线性规划方法设计解决实际问题的最优方案．
二．学习过程：
(一)知识梳理：阅读课本，自主梳理总结以下几个问题：
1.如何用二元一次不等式(组)表示平面区域？
2.线性规划的相关概念
(1)什么是约束条件？目标函数？线性规划问题？
(2)什么是可行域？可行解？最优解？
3.利用图解法解决线性规划问题的一般步骤
第一步：设出 ，列出 ，确立 ， 第二步：根据约束条件，画出 ，
第三步：作出目标函数的等值线(等值线是指 )． 第四步：求出 ．在可行域内平行移动目标函数等值线，从图中能判定问题有 ，或者是有 ，或是 ． 思考：
(1)点P 1和P 2位于直线Ax ＋By ＋C ＝0的两侧(或异侧)的充要条件是什么？
(2)可行解与最优解有何关系？最优解是否唯一？
(二）题型分析与研究
考点一 二元一次不等式(组)表示平面区域
例1.不等式组??
???≤≥-+≤-+203062y y x y x 表示的平面区域的面积为
考点二 求目标函数的最值 (常见的目标函数有哪些？)
例3.(1)设变量x ，y 满足约束条件??
???≥≤--≥-+10202y y x y x ，则目标函数z ＝x ＋2y 的最小值
为
(2)在平面直角坐标系xOy 中，M 为不等式组??
???≤-+≥-+≥--083012022y x y x y x ，所表示的区域上一动
点，则直线OM 斜率的最小值为
(3)变量x ，y 满足??
???≥≤-+≤+-102553034x y x y x ,(1)设z ＝y x ，求z 的最小值;(2)设z ＝x 2＋y 2，求z 的取值范围．
考点三 求线性规划中的参数问题
例3.(1)x ，y 满足约束条件??
???≥+-≤--≤-+02202202y x y x y x ,若z ＝y －ax 取得最大值的最优解不唯．．一．
，则实数a 的值为
(2)当实数x ，y 满足??
???≥≤--≤-+101042x y x y x 时，1≤ax ＋y ≤4恒成立，则实数a 的取值范
围是________．
考点四 线性规划的实际应用
例4.某玩具生产公司每天计划生产卫兵、骑兵、伞兵这三种玩具共100个，生产一个卫兵需5分钟，生产一个骑兵需7分钟，生产一个伞兵需4分钟，已知总生产时间不超过10小时．若生产一个卫兵可获利润5元，生产一个骑兵可获利润6元，生产一个伞兵可获利润3元．
(1)用每天生产的卫兵个数x 与骑兵个数y ，表示每天的利润W (元)；
(2)怎样分配生产任务才能使每天的利润最大，最大利润是多少？
线性规划模型及其举例 摘要：在日常生活中，我们常常对一个问题有诸多解决办法，如何寻找最优方案，成为关键，本文提出了线性规划数学模型及其举例，在一定约束条件下寻求最优解的过程，目的是想说明线性规划模型在生产中的巨大应用。 关键词：资源规划；约束条件；优化模型；最优解 在工农业生产与经营过程中，人们总想用有限的资源投入，获得尽可能多的使用价值或经济利益。如：当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多，利润最大）。 一.背景介绍 如果产出量与投入量存在（或近似存在）比例关系，则可以写出投入产品的线性函数式： 1()n i ij j j f x a x ==∑，1,2,,,1i m m =+ (1) 若将（1）式中第（1m +）个线性方程作为待求的目标函数，其余m 个线性方程作为资源投入的限制条件（或约束条件），则（1）式变为： OPT. 1()n j j j f x c x ==∑ ST. 1 n ij j j a x =∑> ( =, < )i b , 1,2,,i m = (2) 0,j x ≥ 1,2,,j n =… （2）式特点是有n 个待求的变量j x （1,2,,j n =…）；有1个待求的线性目标函数()f x ，有m 个线性约束等式或不等式，其中i b （1,2,,i m =…）为有限的资源投入常量。将客观实际问题经过系统分析后，构建线性规划模型，有决策变量，目标函数和约束条件等构成。 1．决策变量（Decision Variable,DV ）在约束条件范围内变化且能影响（或限定）目标函数大小的变量。决策变量表示一种活动，变量的一组数据代表一个解决方案，通常这些变量取非负值。 2．约束条件（Subject To,ST ）在资源有限与竞争激烈的环境中进行有目的性的一切活动，都
11（2），12,14,18 习题 2-1 判断下列说法是否正确： （1） 任何线性规划问题存在并具有惟一的对偶问题； T （2） 对偶问题的对偶问题一定是原问题；T （3） 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之， 当对偶问题无可行解时，其原问题具有无界解；F （4） 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优 解； （5） 若线性规划问题中的b i ，c j 值同时发生变化，反映到最终单纯形表中，不会出 现原问题与对偶问题均为非可行解的情况； （6） 应用对偶单纯形法计算时，若单纯形表中某一基变量x i <0，又x i 所在行的元素全 部大于或等于零，则可以判断其对偶问题具有无界解。 （7） 若某种资源的影子价格等于k ，在其他条件不变的情况下，当该种资源增加 5个单位时，相应的目标函数值将增大5k ； （8） 已知y i 为线性规划的对偶问题的最优解，若y i >0，说明在最优生产计划中第 i 种资源已经完全耗尽；若y i =0，说明在最优生产计划中的第i 种资源一定有剩余。 2-2将下述线性规划问题化成标准形式。 ????? ? ?≥≥-++-≤+-+-=-+-+-+-=无约束 43 214321432143214321,0,,232142224.5243max )1(x x x x x x x x x x x x x x x x st x x x x z 2-3分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基 可行解对应图解法中可行()?????≥≤≤-+-=++-+-=无约束 321 3213213 21,0,06 24 .322min 2x x x x x x x x x st x x x z 域的哪一顶点。 ()??? ??≥≤+≤++=0,8259 43.510max 12 1212121x x x x x x st x x z ()??? ??≥≤+≤++=0,242615 53.2max 22 121212 1x x x x x x st x x z 2-4已知线性规划问题，写出其对偶问题： 5 43212520202410max x x x x x z ++++=
线性规划的实际应用题解题步骤 广东 王远征 在近几年的高考试卷中出现了求线性目标函数在线性约束条件下的最大（小）值应用题，本文以高考试题为例，介绍解题的模式和一般步骤． 一、线性规划问题的数学模型如下： 已知???????≤++++≤++++≤++++n m nm n n n m m m m b x a x a x a x a b x a x a x a x a b x a x a x a x a ΛΛΛΛΛ3322112232322212111313212111 （I ） 其中ij a ，i b 都是常数，i x 是非负变量． (n i ,,3,2,1Λ= m j ,,3,2,1Λ=)． 求m m x c x c x c x c z ++++=Λ332211 的最大（小）值，其中i c 是常数． 我们将（I ）称为线性约束条件，把m m x c x c x c x c z ++++=Λ332211称为目标函数． 二、解题的一般步骤： 1． 建模：在读懂题意的前提下，写出反映实际问题的线性约束条件和目标函数表达式； 2． 作出可行解、可行域：将线性约束条件中的每个不等式当作等式，在平面直角坐标 系中作出相应的直线，并确定原不等式所表示的半平面，然后作出所有半平面的交 集； 3． 作出目标函数的等值线； 4． 求出最优解：在可行域内，平移目标函数的等值线，从图中能判断实际问题的解的 情况，有唯一最优解，或无最优解，或有无穷最优解． 三、典型试题解析 例（07年高考山东）本公司计划2008年在甲、乙两个电视台做总时间不超过300分钟的广告，广告总费用不超过9万元，甲、乙电视台的广告收费标准分别为500元/分钟和200元/分钟，规定甲、乙两个电视台为该公司所做的每分钟广告，能给公司事来的收益分
简单的线性规划问题 [ 学习目标 ] 1.了解线性规划的意义以及约束条件、目标函数、可行解、可行域、最优解等基本概念 .2. 了解线性规划问题的图解法，并能应用它解决一些简单的实际问题． 知识点一线性规划中的基本概念 知识点二线性规划问题 1．目标函数的最值 线性目标函数 z＝ax＋by (b≠0)对应的斜截式直线方程是 y＝－a x＋z，在 y 轴上的 截距是z， b b b 当 z 变化时，方程表示一组互相平行的直线． 当 b>0，截距最大时， z 取得最大值，截距最小时， z 取得最小值； 当 b<0，截距最大时， z 取得最小值，截距最小时， z 取得最大值． 2．解决简单线性规划问题的一般步骤在确定线性约束条件和线性目标函数的前提下，解决简单线性规划问题的步骤可以概括为：“画、移、求、答”四步，即， (1)画：根据线性约束条件，在平面直角坐标系中，把可行域表示的平面图形准确地画出来，可行域可以是封闭的多边形，也可以是一侧开放的无限大的平面区域．(2)移：运用数形结合的思想，把目标函数表示的直线平行移动，最先通过或最后通过的顶点 (或边界 )便是最优解． (3)求：解方程组求最优解，进而求出目标函数的最大值或最小值． (4)答：写出答案．
知识点三简单线性规划问题的实际应用 1．线性规划的实际问题的类型 (1)给定一定数量的人力、物力资源，问怎样运用这些资源，使完成的任务量最大，收到的效益最大； (2)给定一项任务，问怎样统筹安排，使完成这项任务耗费的人力、物力资源量最小．常见问题有： ①物资调动问题例如，已知两煤矿每年的产量，煤需经两个车站运往外地，两个车站的运输能力是有限的，且已知两煤矿运往两个车站的运输价格，煤矿应怎样编制调动方案，才能使总运费最小？ ②产品安排问题例如，某工厂生产甲、乙两种产品，每生产一个单位的甲种或乙种产品需要的A、B、C 三种 材料的数量，此厂每月所能提供的三种材料的限额都是已知的，这个工厂在每个月中应如何安排这两种产品的生产，才能使每月获得的总利润最大？ ③下料问题例如，要把一批长钢管截成两种规格的钢管，应怎样下料能使损耗最小？2．解答线性规划实际应用题的步骤 (1)模型建立：正确理解题意，将一般文字语言转化为数学语言，进而建立数学模型，这需要在学习有关例题解答时，仔细体会范例给出的模型建立方法． (2)模型求解：画出可行域，并结合所建立的目标函数的特点，选定可行域中的特殊点作为最优解． (3)模型应用：将求解出来的结论反馈到具体的实例中，设计出最佳的方案． 题型一求线性目标函数的最值 y≤2， 例 1 已知变量 x，y 满足约束条件 x＋y≥1，则 z＝3x＋y 的最大值为 ( ) x－y≤1， A ． 12 B ．11 C ．3 D ．－ 1 答案 B 解析首先画出可行域，建立在可行域的基础上，分析最值点，然后通过解方程组得最值点 的坐标，代入即可．如图中的阴影部分，即为约束条件对应的可行域，当直线y＝－3x＋z 经 y＝2，x＝ 3，
如何认识线性规划实际问题中有关最优解的精确问题 课本线性规划第二节，提到两个实际问题，一个要求将最优解精确到0.1，一个要求将最优解是整数，如果说师生们对例4的答案还可接受的话，那么，例3到最后四舍五入式的解答实在让人难以把握，况且最优解应为（12.3，34.5），那么关于这种最优解需要得到精确的题目有没有统一的解答步骤，我的回答是有。 在实际问题中，可行域一般都是一整片区域不存在间断现象，所以题目所要求的最优解无论精确到0.1还是精确到0.01，符合要求的最优解都确实存在在可行域中，我们要做的应该是把它找出来，而不是通过任何手段去精确。如何才能把它找出来呢？我的办法是，不考虑x、y需要精确的要求，先依其他条件列出不等式组，作出可行域，求出符合题中其他条件的最优解，然后看此最优解是否符合题目要求，若符合，则即为所求解．若不符合，则应继续滑动参照线，求出经过可行域内的符合要求的且与原点距离最远（或最近）的点的直线，在该线经过可行域的部分上寻找最优解即可。具体操作请看以下示范 课本例3、某工厂生产甲、乙两种产品，已知生产甲种产品1t需消耗A种矿石10t、B种矿石5t、煤4t；生产乙种产品1t需消耗A种矿石4t、B种矿石4t、煤9t。每1 t甲种产品的利润是600元，每1 t甲种产品的利润是1000元。工厂在生产这两种产品的计划中要求消耗A种矿石不超过300t、B种矿石不超过200t、煤不超过360t。甲、乙两种产品应各生产多少（精确到0.1t），能使利润总额达到最大？ 解：设生产甲、乙两种产品分别为x t、y t，利润总额为z元，那么
104300542004936000 x y x y x y x y +≤??+≤?? +≤??≥?≥?? Z=600x+1000y 作直线l ：600x+1000y=0 即直线l ：3x+5y=0 把直线l 向右上方平移，使其划过可行域，此时3x+5y>0 当直线经过点M 3601000 (,)2929时3x+5y 达到最大,即z 也达到最大， 此时3x+5y=6080 29 ≈209.655, 若要将最优解精确到0.1，需将直线向回平移到3x+5y=209.6 由35209.649360 x y x y +=??+=? 得到3x+5y=209.6与可行域左边界的交点A （12.343,34.514） 由35209.654200x y x y +=??+=? 得到3x+5y=209.6与可行域右边界的交 点B （12.431,34.462） 可知有可能成为最优解的点的横坐标为12.4 代入3x+5y=209.6得到纵坐标约为34.48，不符合题目精确到0.1要求
简单的线性规划应用题解析 1．某人有楼房一幢，室内面积共180㎡,拟分隔两类房间作为旅游客房．大每间面积为18㎡，可住游客5名，每名游客每天住宿费为40元；小房间每间面积为15㎡，可住游客3名，每名游客每天住宿费为50元；装修大房间每间需1000元，装修小房间每间需600元．如果他只能筹款8000元用于装修，且游客能住满客房，他应隔出大房间和小房间各多少间，能获得最大收益？ 设应隔出大、小房间分别为x ,y 间，此时收益为z 元，则 1815180 1000600800000 x y x y x y +≤??+≤? ? ≥??≥? 200150z x y =+ 将上述不等式组化为 6560 534000 x y x y x y +≤??+≤? ? ≥??≥? 作出可行域，如图⑴，作直线l:200x+150y=0,即l:4x+3y=0. 将直线l 向右平移，得到经过可行域的点B ，且距原点最远的直线l 1. 解方程组 6560 5340 x y x y +=?? +=? 图⑴
得最优解 20 7 60 7 2.9 8.6 x y =≈ ? ? =≈ ? 但是房间的间数为整数，所以，应找到是整数的最优解． ①当x=3时，代入5x+3y=40中，得401525 338 y- ==>，得整点（3，8），此时z=200×3＋150×8=1800（元）; ②当x=2时,代入6x+5y=60中，得601248 559 y- ==>，得整点（2，9），此时z=200×2＋150×9=1750（元）； ③当x=1时,代入6x+5y=60中，得60654 5510 y- ==>，得整点（1，10）,此时z=200×1＋150×10=1700（元）； ④当x=0时,代入6x+5y=60中，得60 512 y==，得整点（0，12），此时 z=150×12=1800（元）． 由上①～④知，最优整数解为（0，12）和（3，8）． 答：有两套分隔房间的方案：其一是将楼房室内全部隔出小房间１２间；其二是隔出大房间３间，小房间８间，两套方案都能获得最大收益为１８００元． 2．某家具厂有方木料90m3,五合板60㎡，准备加工成书桌和书橱出售．已知生产每张书桌需要方木料0.1 m3、五合板2㎡，生产每个书橱需要方木料0.2 m3、五合板1㎡，出售一张书桌可获得利润80元，出售一个书橱可获得利润120元．如果只安排生产书桌，可获利润多少？如果只安排生产书橱，可获利润多少？怎样安排生产可使所得利润最大？ 【解析】将已知数据列成下表: 用完五合板，此时获利润为80×300=24000（元）； ⑵只生产书橱因为90÷0.2=450，600÷1=600，所以，可产生450个书橱，用完方木料.此时获利润为120×450=54000（元）；
第10章资源分配模型与线性规划 线性规划是运筹学中研究的比较早，理论上已趋向成熟并且应用广泛是解决最优化问题非常有效地工具。早在20世纪30年代末，前苏联数学家康托洛维奇首先提出了资源分配模型的线性规划，于1947年由美国人丹茨格提出了线性规划的单纯算法，较好的解决了线性规划的求解问题，从而奠定了线性规划作为一门学科的基石。 线性规划研究的对象大体可分为两大类： （1）在现有的人、财、物等资源的条件下，研究如何合理的计划、安排，可使得某一目标达到最大，如产量、利润目标等。 （2）在任务确定后，如何计划、安排，使用最低限度的人、财等资源，去实现该任务，如使生产成本、费用自小等。 （3）线性规划中研究的问题要求目标与约束条件函数均是线性的，并且只有一个目标函数。在经济管理问题中，大量的问题是线性的，有的可以转化为现行的，从而线性规划有着极大地应 用价值。 §10.1 线性规划问题 在经济管理中，经常遇到一类如何合理的使用有限的劳动力、设备、资金等资源，异化的最大的效益的问题。 例 1 某工厂生产甲、乙两种产品，生产这两种产品要消耗某种原料。生产每吨产品所需要的原料量及所占设备时间，见表10-1.该厂每周所能得到的原料为16吨，每周设备能多开15个台班，且根据市场需要，甲种产品每周产量不应超过4吨。已知该厂生产每吨甲、乙两种产品的利润分别为15万元及6万元。问：该厂应如何安排两种产品才能是每周获得的利*最大？ 简历数学模型社该厂每周安排生产甲种产品的产量为x1吨，乙种产品为x2吨，则每周所能获得的利润总额为z=15x1+6x2（万元）。但生产量的大小要受到原料量技术倍的限制及市场最大需求量的制约，即x1，x2要满足一下一组不等式条件： 3x1+2x2≤16， 5x2+x2≤15，（10—1） x≤4， 此外，产品x1，x2还应是非负的数： x1≥0，x2≥0. （10—2） 因此从数学角度看，x1，x2应在满足资源约束（10-1）及非负约束（10-2）条件下，使利润z取最大值： Max z=15x1+6x2. （10—3） 经过以上分析，可将一个生产安排问题抽象为满足一组约束条件下，寻求变量x1，x2，使目标函数达到最大值得一个线性规划。 同样，在经济生活中为了达到一定的目标，应如何组织生产，或合理安排工艺流程，或调整产品的成分等，以使消耗为最少，一下给出一个求目标函数最小化的线性规划问题。 例2某公司需要生产某产品，需要Ⅰ，Ⅱ两种原料至少35吨，其中原料Ⅰ至少购进10吨。但由于Ⅰ，Ⅱ两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨原料Ⅰ需要2个小时，加工每吨原料Ⅱ需要1小时，而公司总共有60个加工小时。又知道每吨原料Ⅰ的价格为4万吨，每吨原料Ⅱ的价格为6万元，试问：在满足生产需要的前提下，在公司加工能力的范围内，如何购买Ⅰ，Ⅱ两种原料，是的购进成本最低？
应用题最后一卷 三题 一、类型 基本不等式 1、某种商品第一天销售价为42元,以后每天提价2元,且在开始销售的前30天内每天的销售量与上市天数的关系是5100()x g x x +=(其中x 为天数). (1)写出上市30天内商品销售价格与天数x 的关系式. (2)求销售30天内,哪一天的销售额最小,并求出最小值. 二、类型 换元成二次函数 2、销售甲、乙两种商品所得利润分别是12,y y 万元，它们与投入资金x 万元的关系分别为 12,y a y bx ==（其中,,m a b 都为常数） ，函数12,y y 对应的曲线12,C C 如图所示． （1）求函数12,y y 的解析式； （2）若该商场一共投资8万元经销甲、乙两种商品，求该商场所获利润的最大值． 解：（1）由题意0835m a m a +=???+=?? ，解得5 4,54-==a m ， 14,(0)5 y x =≥………………………………………………4分 又由题意588=b 得5 1=b 215 y x =(0)x ≥……………………………………………7分 （2）设销售甲商品投入资金x 万元，则乙投入（8x -）万元 由（1 ）得41(8)55 y x =+-，(08)x ≤≤………………………10分 ,(13)t t =≤≤，则有 2149555y t t =-++=2113(2)55 t --+，(13)t ≤≤， 当2=t 即3=x 时,y 取最大值135 . 答：该商场所获利润的最大值为135 万元．………………………………16分
线性规划的应用题三题 1、 某企业生产甲、乙两种产品，已知生产每吨甲产品要用A 原料3吨、B 原料2吨；生产每吨乙产品要用A 原料1吨、B 原料3吨．销售每吨甲产品可获得利润5万元、每吨乙产品可获得利润3万元，该企业在一个生产周期内消耗A 原料不超过13吨、B 原料不超过18吨，那么该企业可获得的最大利润是万元． 【解析】设生产甲产品x 吨、乙产品y 吨， 则获得的利润为z ＝5x ＋3y . 由题意得????? x ≥0，y ≥0，3x ＋y ≤13，2x ＋3y ≤18， 可行域如图阴影所示． 由图可知当x 、y 在A 点取值时，z 取得最大值，此时x ＝3，y ＝4，z ＝5×3＋3×4＝27(万元)．
线性规划模型在生活中的实际应用 一、线性规划的基本概念 线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题.满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域.决策变量、约束条件、目标函数是线性规划的三要素. 二、线性规划模型在实际问题中的应用 （1）线性规划在企业管理中的应用范围 线性规划在企业管理中的应用广泛，主要有以下八种形式： 1.产品生产计划：合理利用人力、物力、财力等，是获利最大. 2.劳动力安排：用最少的劳动力来满足工作的需要. 3.运输问题：如何制定运输方案，使总运费最少. 4.合理利用线材问题：如何下料，使用料最少. 5.配料问题：在原料供应的限制下如何获得最大利润. 6.投资问题：从投资项目中选取方案，是投资回报最大. 7.库存问题：在市场需求和生产实际之间，如何控制库存量从而获得更高利益.
8.最有经济计划问题：在投资和生产计划中如何是风险最小 . （2）如何实现线性规划在企业管理中的应用 在线性规划应用前要建立经济与金融体系的评价标准及企业的计量体系，摸清企业的资源.首先通过建网、建库、查询、数据采集、文件转换等，把整个系统的各有关部分的特征进行量化，建立数学模型，即把组成系统的有关因素与系统目标的关系，用数学关系和逻辑关系描述出来，然后白较好的数学模型编制成计算机语言，输入数据，进行计算，不同参数获取的不同结果与实际进行分析对比，进行定量，定性分析，最终作出决策. 3.3 线性规划在运输问题中的应用 运输是物流活动的核心环节，线性规划是运输问题的常用数学模型，利用数学知识可以得到优化的运输方案. 运输问题的提出源于如何物流活动中的运输路线或配送方案是最经济或最低成本的.运输问题解决的是已知产地的供应量，销地的需求量及运输单价，如何寻找总配送成本最低的方案；运输问题包含产销平衡运输问题和产销不平衡运输问题；通常将产销不平衡问题转化为产销平衡问题来处理；运输问题的条件包括需求假设和成本假设.需求假设指每一个产地都有一个固定的供应量所有的供应量都必须配送到目的地.与之类似，每一个目的地都有一个固定的需求量，整个需求量都必须有出发地满足；成本假设指从任何一个产地到任何一个销地的配送成本和所配送的数量的线性比例关系.产销平衡运输问题的一般提法是： 假设某物资有m个产地a1，a2，?，am;各地产量分别为b1，b2，?，bn，物资从产地Ai运往销地Bj的单位运价为cij,满足：
线性规划专题 一、命题规律讲解 1、 求线性（非线性）目标函数最值题 2、 求可行域的面积题 3、 求目标函数中参数取值范围题 4、 求约束条件中参数取值范围题 5、 利用线性规划解答应用题 一、线性约束条件下线性函数的最值问题 线性约束条件下线性函数的最值问题即简单线性规划问题，它的线性约束条件是一个二元一次不等式组，目标函数是一个二元一次函数，可行域就是线性约束条件中不等式所对应的方程所表示的直线所围成的区域，区域内的各点的点坐标(),x y 即简单线性规划的可行解，在可行解中的使得目标函数取得最大值和最小值的点的坐标(),x y 即简单线性规划的最优解。 例1 已知43 35251x y x y x -≤-?? +≤??≥? ，2z x y =+，求z 的最大值和最小值 例2已知,x y 满足124126x y x y x y +=?? +≥??-≥-? ，求z=5x y -的最大值和最小值 二、非线性约束条件下线性函数的最值问题 高中数学中的最值问题很多可以转化为非线性约束条件下线性函数的最值问题。它们的约束条件是一个二元不等式组，目标函数是一个二元一次函数，可行域是直线或曲线所围成的图形（或一条曲线段），区域内的各点的点坐标(),x y 即可行解，在可行解中的使得目标函数取得最大值和最小值的点的坐标 (),x y 即最优解。 例3 已知,x y 满足，2 2 4x y +=，求32x y +的最大值和最小值 例4 求函数4 y x x =+[]()1,5x ∈的最大值和最小值。
三、线性约束条件下非线性函数的最值问题 这类问题也是高中数学中常见的问题，它也可以用线性规划的思想来进行解决。它的约束条件是一个二元一次不等式组，目标函数是一个二元函数，可行域是直线所围成的图形（或一条线段），区域内的各点的点坐标(),x y 即可行解，在可行解中的使得目标函数取得最大值和最小值的点的坐标(),x y 即最优解。 例5 已知实数,x y 满足不等式组10101x y x y y +-≤??-+≥??≥-? ，求22 448x y x y +--+的最小值。 例6 实数,x y 满足不等式组0 0220 y x y x y ≥?? -≥??--≥? ，求11y x -+的最小值 四、非线性约束条件下非线性函数的最值问题 在高中数学中还有一些常见的问题也可以用线性规划的思想来解决，它的约束条件是一个二元不等式组，目标函数也是一个二元函数，可行域是由曲线或直线所围成的图形（或一条曲线段），区域内的各点的点坐标(),x y 即可行解，在可行解中的使得目标函数取得最大值和最小值的点的坐标(),x y 即最优解。 例7 已知,x y 满足y 2 y x +的最大值和最小值
简单的线性规划问题 [学习目标] 1.了解线性规划的意义以及约束条件、目标函数、可行解、可行域、最优解等基本概念.2.了解线性规划问题的图解法，并能应用它解决一些简单的实际问题． 知识点一 线性规划中的基本概念 1．目标函数的最值 线性目标函数z ＝ax ＋by (b ≠0)对应的斜截式直线方程是y ＝－a b x ＋z b ，在y 轴上的截距是z b ， 当z 变化时，方程表示一组互相平行的直线． 当b >0，截距最大时，z 取得最大值，截距最小时，z 取得最小值； 当b <0，截距最大时，z 取得最小值，截距最小时，z 取得最大值． 2．解决简单线性规划问题的一般步骤 在确定线性约束条件和线性目标函数的前提下，解决简单线性规划问题的步骤可以概括为：“画、移、求、答”四步，即， (1)画：根据线性约束条件，在平面直角坐标系中，把可行域表示的平面图形准确地画出来，
可行域可以是封闭的多边形，也可以是一侧开放的无限大的平面区域． (2)移：运用数形结合的思想，把目标函数表示的直线平行移动，最先通过或最后通过的顶点(或边界)便是最优解． (3)求：解方程组求最优解，进而求出目标函数的最大值或最小值． (4)答：写出答案． 知识点三简单线性规划问题的实际应用 1．线性规划的实际问题的类型 (1)给定一定数量的人力、物力资源，问怎样运用这些资源，使完成的任务量最大，收到的效益最大； (2)给定一项任务，问怎样统筹安排，使完成这项任务耗费的人力、物力资源量最小． 常见问题有： ①物资调动问题 例如，已知两煤矿每年的产量，煤需经两个车站运往外地，两个车站的运输能力是有限的，且已知两煤矿运往两个车站的运输价格，煤矿应怎样编制调动方案，才能使总运费最小？ ②产品安排问题 例如，某工厂生产甲、乙两种产品，每生产一个单位的甲种或乙种产品需要的A、B、C三种材料的数量，此厂每月所能提供的三种材料的限额都是已知的，这个工厂在每个月中应如何安排这两种产品的生产，才能使每月获得的总利润最大？ ③下料问题 例如，要把一批长钢管截成两种规格的钢管，应怎样下料能使损耗最小？ 2．解答线性规划实际应用题的步骤 (1)模型建立：正确理解题意，将一般文字语言转化为数学语言，进而建立数学模型，这需要在学习有关例题解答时，仔细体会范例给出的模型建立方法． (2)模型求解：画出可行域，并结合所建立的目标函数的特点，选定可行域中的特殊点作为最优解．
线性规划模型在实际生活中的应用 【摘要】线性规划在实际生活中扮演着很重要的角色，研究对象是计划管理工作中有关安排和估值的问题,其广泛应用于经济等领域，是实际生活中进行管理决策的最有效的方法之一。解决的主要问题是在给定条件下,按某一衡量指标来寻找安排的最优方案。本文通过对例题利用线性规划分析，如何合理的分配利用，最终找到最优解使企业利润最大，说明了线性规划在实际生活中的应用，而且对线性规划问题模型的建立，模型的解进行了分析，运用图解法和单纯形法解决问题。 【关键词】线性规划、建模、实际生活、图解法、单纯形法 前言：线性规划（Linear programming,简称LP）是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法。英文缩写LP。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。 在实际生活中，经常会遇到一定的人力、物力、财力等资源条件下，如何精打细算巧安排，用最少的资源取得最大的效益的问题，而这正是线性规划研究的基本容，它在实际生活中有着非常广泛的应用．任何一个组织的管理者都必须对如何向不同的活动分配资源的问题做出决策，即如何有效地利用人力、物力完成更多的任务，或在预定的任务目标下如何耗用最少的人力、物力去实现目标。在许多情况下，大量不同的资源必须同时进行分配，需要这些资源的活动可以是不同的生产活动，营销活动，金融活动或者其他一些活动。随着计算技术的不断发展，使成千上万个约束条件和决策变量的线性规划问题能迅速地求解，更为线性规划在经济等各领域的广泛应用创造了极其有利的条件。线性规划已经成为现代化管理的一种重要的手段。本文运用常用的图解法和单纯形法解决利润最大化决策问题，贴近生活，很好的吧线性规划应用到生活实践中。 1、简单线性问题步骤简单介绍 建模是解决线性规划问题极为重要的环节，一个正确的数学模型的建立要求建模者熟悉线性规划的具体实际容，要明确目标函数和约束条件，通过表格的形式把问题中的已知
线性规划最优解的几种可能情况： 1.有唯一的最优解（可行域为封闭的有界区域、可行域为非封闭的无界区域） 2.有一个以上的最优解（可行域为封闭的有界区域、可行域为非封闭的无界区域） 3.无界解（目标函数无界，即虽有可行解，但在可行域中，目标函数可以无限增大或无限 减小） 4.无可行解（可行域为空集） Min型与Max型单纯形表的唯一区别： 检验数反号 Min型单纯形表中 -当检验数均大于等于零时为最优； -令负检验数中最小的对应变量为换入变量。 Max型单纯形表中 -当检验数均小于等于零时为最优； -令正的检验数中最大的对应变量为换入变量。 ①②②③④⑤⑤⑥⑴⑵⑵⑶ 解的几种情况在单纯形表上的体现（Max型）： 1）唯一最优解判别：最优表中所有非基变量的检验数非零,则线性规划具有唯一最优解。2）多重最优解判别：最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解（或无穷多最优解）。 3）无界解判别：某个检验数大于零且换入变量对应的列中所有的分量皆非正，则线性规划具有无界解。 4）无可行解的判断：当用大M单纯形法计算得到最优解并基变量中还存在非零人工变量时，则表明原问题无可行解。 5）退化解的判别：存在某个基变量为零的基本可行解。 4.2 对偶问题的基本性质 1.对称性对偶问题的对偶是原问题。 2.弱对偶性若X是原问题的可行解，Y是对偶问题的可行解，则存在 求目标函数最大化时，在单纯形表中： ①如果检验数均非正，而b列中有负值，这时使用 对偶单纯形法； ②如果所有bi ≥0, 检验数有正值，使用 单纯形法: ③如果b列中有负值，且检验数中有正值，这时必须引入 人工变量，建立新的单纯形表，重新计算
线性规划常见题型及解法 由已知条件写出约束条件，并作出可行域，进而通过平移直线在可行域内求线性目标函数的最优解是最常见的题型，除此之外，还有以下六类常见题型。 一、求线性目标函数的取值范围 例1、若x、y满足约束条件 ，则z=x+2y的取值范围是（） A、[2,6] B、[2,5] C、[3,6] D、（3,5] 解：如图，作出可行域，作直线l：x+2y＝0，将 l向右上方平移，过点A（2,0）时，有最小值 2，过点B（2,2）时，有最大值6，故选A 二、求可行域的面积
例2、不等式组 表示的平面区域的面积为（） A、4 B、1 C、5 D、无穷大 解：如图，作出可行域，△ABC的面积即为所求，由梯形OMBC的面积减去梯形OMAC的面积即可，选B 三、求可行域中整点个数 例3、满足|x|＋|y|≤2的点（x，y）中整点（横纵坐标都是整数）有（） A、9个 B、10个 C、13个 D、14个
解：|x|＋|y|≤2等价于 作出可行域如右图，是正方形内部（包括边界），容易得到整点个数为13个，选D 四、求线性目标函数中参数的取值范围 例4、已知x、y满足以下约束条件 ，使z=x+ay(a>0)取得最小值的最优解有无数个，则a的值为（） A、－3 B、3 C、－1 D、1
解：如图，作出可行域，作直线l：x+ay＝0，要使目标函数z=x+ay(a>0)取得最小值的最优解有无数个，则将l向右上方平移后与直线x+y＝5重合，故 a=1，选D 五、求非线性目标函数的最值 例5、已知x、y满足以下约束条件 ，则z=x2+y2的最大值和最小值分别是（） A、13，1 B、13，2 C、13， D、 ， 解：如图，作出可行域,x2+y2是点（x，y）到原点的距离的平方，故最大值为点A（2,3）到原点的距离的平方，即|AO|2=13，最小值为原点到直线2x＋y－2=0的距离的平方，即为
线性规划问题最优解的确定与改进 线性规划是运筹学的一个重要分支。自1947年丹捷格（G.B.Dantzig ）提出了一般线性规划问题求解的方法——单纯形法之后，线性规划在理论上趋向成熟，在实用中日益广泛与深入。线性规划最优解求解问题，在《运筹学》本科版给出了图解法和单纯形法。 一般线性规划问题的标准型为： 1 max (14)n j j i z c x ==-∑ 1,1,2(15)0,1,2,(16) n i j j i j j a x b i m x j n ===-≥=-?∑???? 满足约束条件（1-5）式、（1-6）式的解12(,,,)T n X x x x = ，称为线性规划问题的可行解，其中使目标函数达到最大值的可行解称为最优解。 2009年中国科教创新导刊，第三十期李高秀写的《线性规划中最优解的准确确定》中详细介绍了图解法的过程，图解法适合于二元线性规划问题，对于多元线性规划问题图解法相对较难。 图解法过程： 1 线性目标函数最值的分析 对于线性目标函数Z=ax+by ，若b ≠0时，目标函数可变为a z y x b b =-+，则是直线a z y x b b =-+在y 轴上的截距。 (1)b>0时，随着直线a z y x b b =-+的平移，直线在与可行域有公共点的条件下，它在y 轴上的截距 z b 最大时z 最大；当z b 最小时z 最小。 (2)b<0时，随着直线a z y x b b =-+的平移，直线在与可行域有公共点的条件下，它在y 轴上的 截距z b 最大时z 最小；当z b 最小时z 最大。 由以上两点可知，要求线性目标函数z=ax+by 的最大最小值要注意y 的系数b 的正负和平移直线在y 轴上的截距。 2 在图上分别作出约束函数和目标函数，平移目标函数线到可行域的交点时，要把目标函数的斜率与相交于这一点的直线的斜率进行比较 上述的最值分析是确定平移目标函数的大概方向，而这次是确定最优解的确凿位置。斜率比较大
教你如何做出最佳选择 ——简单的线性规划求最优解 在线性约束条件下，求线性目标函数最值问题，称为“线性规划”。目标函数),(y x f z =取得最值时，变量y x ,的对应解),(y x 称为最优解。若Z y x ∈,时，z 取得最值，称),(y x 为最优整数解，简称整解。点),(y x 的横、纵坐标都是整数，称为整点。 求最优整解问题出现在高中数学新教材中，常见的实际应用题型有两种，（1）给出一定数量的人力、物力资源，问怎样安排能使完成的任务量最大，收益最大； （2）给出一项任务，问怎样统筹安排，能使完成这项任务投入的人力、物力最小。因为研究的对象是人、物等个体，故y x ,往往是整数，较y x ,不是整数时求解困难，所以这是一个应用数学知识解决实际问题的新难点，加之教材介绍较为笼统简略，对教师和学生的理解掌握造成了一定的困难，针对这一问题，总结两种寻找最优整解的方法与大家探讨。 这两种求解方法分别是：调整优值法(简称调值法)、枚举整点法(简称枚举法)。调值法是先求非整点最优解，再借助不定方程，调整最优解，最后筛选出最优解；枚举法，因为取得最值的整点分布在可行域内，可从y x ,中选取系数的绝对值较大的一个对其逐一取值，以此为标准分类讨论，取得另一变量的最值，代入目标函数，比较函数值大小，找到最优解。 下面通过几个典型例题，介绍一下这几种方法的具体运用。 例1（调整优值法）要将两种大小不同的钢板截成A 、B 、C 三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示： 今需A 、B 、C 三种规格的成品分别为15、18、27块，问各截这两种钢板多少张可得所需三种规格成品，且使所用钢板张数最少？ 解析：设需要第一种钢板x 张，第二种钢板y 张，钢板总数z 张，则
线性规划问题的最优解 引言 线性规划是运筹学的一个基本分支，其应用极其广泛，其作用以为越来越多的人所重视。线性规划主要就实际问题抽象成数学形式，即求一组变量的值，在满足一定的约束条件下，是某个目标达到最小或最大，而这些约束条件用可以用一组线性不等式或线性方程来表示。而求得目标函数的最优解尤为重要，本文就线性规划问题的最优解求解方法作出阐述，并举出实例加以强化，同时也指出了线性规划问题应用于生产与运作管理的重要性。 1.线性规划问题的最优解探讨 1.1线性规划问题的提出 考虑下面的线性规划问题的标准型： 目标函数： CX Z =min (1) 约束条件： ? ??≥=0X b AX (2) 其中，),,,(21n c c c C =,T n x x x X ),,,(21 =,T m b b b b ),,,(21 =,n m ij a A ?=)(阶矩阵。设B 是A 中m 个线性无关的列向量构成的一个基，m m ij a B ?=)( 阶矩阵，这样将矩阵A 分成两个部分，即A=),(N B ,X=),(N B X X ,C=()N B C C ,,B X ,B C 为基B 对应的非基变量和系数，N X ,N X 为N 对应的非基变量和系数，这样将线性规划问题改写为： minZ ()N B C C ,=?? ? ???B B X X (3) 约束条件：
?????≥=?? ????0),(N B N B X X b X X N B (4) 经过矩阵变换，得出关于基B 的标准型如下： 1min -=B C Z B +(N C -1-B C B N)N X (5) 约束条件： ???≥=+--0,11N B N B X X b B NX B X (6) T m b b b b B ),,,(' '21'1 =- ?????? ? ? ? =++++++-mn mm mm n m m n m m a a a a a a a a a N B 212221 2121111 将（5）（6）展开为： =Z min ' 1i m i i b c ∑=+ ∑ +=n m j 1 (' 1 ij m i i j a c c ∑=-)j x (7) 约束条件： i n m j j ij i b x a x '1 ' =+ ∑+= ,m i ,,2,1 = (8) 0≥j x ,n j ,,2,1 = (9) 令 ' 1 0i m i i b c Z ∑== , =j σ' 1 ij m i i j a c c ∑=- ,n m m j ,,2,1 ++= ,称j σ为检验数。 1.2最优解判别准则 准则一：若 T m b b b X )0,,0,,,,('2'1')1( = ，为对应于基B 的基本可行解，且对于一切的 n m m j ,,2,1 ++= ，j σ>0 ，则X 为线性规划问题的最优解。
线性规划应用题 例⒈（ 2004 年江苏卷）制定投资计划时，不仅要考虑可能获得的盈利，而且要考虑可能 出现的亏损 .某投资人打算投资甲、乙两个项目. 根据预测，甲、乙项目可能的最大盈利 率分别为100﹪和 50﹪，可能的最大亏损率分别为30﹪和 10﹪ . 投资人计划投资金额不 超过 10 万元，要求确保可能的资金亏损不超过 1.8 万元 . 问投资人对甲、乙两个项目各 投资多少万元，才能使可能的盈利最大？ 例⒉（ 2010广东卷）某营养师要为某个儿童预定午餐和晚餐。已知一个单位的午餐含 12 个单位的碳水化合物 6 个单位蛋白质和 6 个单位的维生素 C ；一个单位的晚餐含8 个单位的碳水化合物， 6 个单位的蛋白质和10 个单位的维生素 C.另外，该儿童这两餐需要 的营养中至少含64 个单位的碳水化合物，42 个单位的蛋白质和54 个单位的维生素 C.如果一个单位的午餐、晚餐的费用分别是 2.5 元和 4 元，那么要满足上述的营养要求， 并且花费最少，应当为该儿童分别预定多少个单位的午餐和晚餐？ 例⒊预算用2000 元购买单价为50 元的桌子和20 元的椅子，希望使桌椅的总数尽可能的多，但椅子数不少于桌子数且不多于桌子数的 1.5 倍，问桌、椅各买多少才行？ 练习： P89 例 3、变式训练3
作业 ⒈（ 2003年北京卷）某厂生产 A、B两种产品，需甲、乙、丙三种原料，每生产一吨产品需 耗原料如下表 .现有甲原料200吨，乙原料360吨，丙原料300吨，若产品生产后能全部销售，试问 A、 B各生产多少吨能获最大利润 . 甲乙丙利润（万元 / 吨） A产品4937 B产品541012 ⒉（ 2007 山东）本公司计划2008 年在甲、乙两个电视台做总时间不超过300 分钟的广告，广告总费用不超过9 万元，甲、乙电视台的广告收费标准分别为500 元/分钟和200元/分钟，规定甲、乙两个电视台为该公司所做的每分钟广告，能给公司事来的收益分别 为 0.3 万元和 0.2 万元．问该公司如何分配在甲、乙两个电视台的广告时间，才能使公司 的收益最大，最大收益是多少万元？