(完整版)简单的线性规划问题(附答案)
简单的线性规划问题 [ 学习目标 ] 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，
破解线性规划中的整点问题
破解线性规划中的整点问题 河南省三门峡市卢氏一高（472200）赵建文 Email:zhaojw1968@https://www.wendangku.net/doc/7b4985911.html, 线性规划中的整点问题是高中数学线性规划中的重要一类问题，是高中数学的一个难点，本文将整数线性规划问题解法作以简单介绍供同学们学习时参考. 例 某商店计划同时销售某品牌电热水器和太阳能热水器，由于市场需求旺盛，这两种产品供不应求，因该商店根据具体情况（如成本、员工工资）确定产品的月采购量，具体数据如下，问这两种产品各采购多少时，才能使总利润最大？最大利润是多少？ 分析：本题是整数规划问题，设采购电热水器x 台、太阳能热水器y 台，列出约束条件和目标函数，用图解法解之. 解析：设月采购电热水器x 台、太阳能热水器y 台，月总利润为z 元，则 1000300030000100050011000 ,x y x y x y N +≤??+≤??∈? ，即330222 ,x y x y x y N +≤??+≤??∈?，目标函数为 z =800600x y + 作出可行域如图所示， 作直线l ：86x y +=0， 平移直线z =800600x y +知过M 3638( ,)55时，max z =10320，但x =365，y =385不是整数，所以可行域内点M 3638( ,)55不是整点最优解. 求整点最优解 解法一 网格平移法 首先在可行域内打网格，其次描出M 3638(,)55 附近的所有整点，接着平移直线l ：86x y +=0，会发现当移至（8，6）时，直线在y 轴上截距最大，即max z =10000元. 解法二 特值检验法 由图可知目标函数取得最大值的整点应分布在可行域右上侧靠近边界的区域，一次取得满足条件的整点，（0，10），（1，9），（2，9），（3，9）（4，8），（5，8），（6，8），（7，7），（8，6），（8，5），（9，4），（10，2），（10，1），（11，0）.将这些点分别代入z =800600x y +，求出各点对应的值，经验证可知，在整点(8,6)处max z =10000元. 解法三 调整最优法 单位产品所需资金 月资金供应量（百元） 电热水器 太阳能热水器 成本 10 30 300 工资 10 5 110 单位利润 8 6
必修五——线性规划无数个最优解问题、乘1问题-答案
必修五——线性规划无数个最优解问题、乘1问题 答案和解析 【答案】 1.D 2.A 3.C 4.C 5.A 6.B 7.D 8.B 9.C 10.B 11.B 【解析】 1. 解：作出不等式组{x +y ≥1 x ?y ≥?12x ?y ≤2 表示的平面区域， 得到如图的△ABC 及其内部，其中A （1，0），B （0，1），C （3，4） 设z =F （x ，y ）=ax +by （a ＞0，b ＞0），将直线l ：z =ax +by 进行平移， 当l 经过点C 时，目标函数z 达到最大值 ∴z 最大值=F （3，4）=3a +4b =7，可得17（3a +4b ）=1因此，3a +4b =17 （3a +4b ）（3a +4b ）=17（25+12b a +12a b ） ∵12b a +12a b ≥2√12b a ?12a b =24∴17（25+24）≥17×49=7， 即当且仅当a =b =1时，3a +4b 的最小值为7故选：D 作出题中不等式组表示的平面区域，得如图的△ABC 及其内部，再将目标函数z =ax +by 对应的直线进行平移，可得当x =3，y =4时，z 最大值为3a +4b =7．然后利用常数代换结合基本不等式，可得当且仅当a =b =1时，3a +4 b 的最小值为7． 本题给出二元一次不等式组，在已知目标函数z =ax +by 最大值为7的情况下求3a +4b 的最小值．着重考查了运用基本不等式求最值和简单的线性规划等知识，属于中档题． 2. 解：满足约束条件{x +y ?4＜0y ≥x x ≥0的可行域如下图所示
∵y?5x?1表示可行域内一点（x ，y ）与P （1，5）连线的斜率 又∵k PA =5?41?0=1，k PB =5?22?1=-3， ∴y?5x?1的范围是（-∞，-3）∪（1，+∞） 故选A 画出满足约束条件的可行域，分析目标函数的几何意义，数形结合即可分析出目标函数的取值范围． 本题考查的知识点是简单线性规划的应用，其中分析出目标函数的几何意义是表示可行域内一点（x ，y ）与P （1，5）连线的斜率是解答的关键． 3. 解：由约束条件{y ≥0 y ?x +1≤0y ?2x +4≥0作出可行域如图， 由z =y -ax （a ≠0），得y =ax +z ， ∵a ≠0， ∴要使z =y -ax （a ≠0）取得的最优解（x ，y ）有无数个， a 不能为负值，当a ＞0时，直线y =ax +z 与线段AC 所在直线重合时，使z =y -ax 取得最大值的最优解有无数个； 直线y =ax +z 与线段BC 所在直线重合时，使z =y -ax 取得最小值的最优解有无数个．
使用Excel规划求解解 线性规划问题
使用Excel规划求解解线性规划问题 引言 最近，开始学习运筹学，期望通过学习后能够解决许多困扰自已的难题。 刚开始时，选了很多教材，最后以Hamdy A.Taha著的《Operations Research:An Introduction》开始学习。（该书已由人民邮电出版社出版，书名《运筹学导论-初级篇（第8版）》，不知为什么，下载链接中只有该书配套的部分习题解答，而书中所说的光盘文件找不到下载的地方，因为中译本没有配光盘，因此也就错过了许多示例文件。不知道哪位有配套光盘文件，可否共享？？？） 线性规划求解的基本知识 线性规划模型由3个基本部分组成： ?决策变量（variable） ?目标函数（objective） ?约束条件（constraint） 示例：营养配方问题 （问题）某农场每天至少使用800磅特殊饲料。这种特殊饲料由玉米和大豆粉配制而成，含有以下成份： 特殊饲料的营养要求是至少30%的蛋白质和至多5%的纤维。该农场希望确定每天最小成本的饲料配制。 （解答过程） 因为饲料由玉米和大豆粉配制而成，所以模型的决策变量定义为： x1=每天混合饲料中玉米的重量（磅） x2=每天混合饲料中大豆粉的重量（磅） 目标函数是使配制这种饲料的每天总成本最小，因此表示为： min z=0.3×x1+0.9×x2 模型的约束条件是饲料的日需求量和对营养成份的需求量，具体表示为： x1+x2≥800 0.09×1+0.6×2≥0.3(x1+x2) 0.02×1+0.06×2≤0.05(x1+x2) 将上述不等式化简后，完整的模型为：
min z=0.3×1+0.9×2 s.t.x1+x2≥800 0.21×1-0.3×2≤0 0.03×1-0.01×2≥0 x1,x2≥0 可以使用图解法确定最优解。下面，我们介绍使用Excel的规划求解加载项求解该模型。使用Excel规划求解解线性规划问题 步骤1安装Excel规划求解加载项 单击“Office按钮——Excel选项——加载项——（Excel加载项）转到”，出现“加载宏”对话框，如下图所示。选择“规划求解加载项”，单击“确定”。 此时，在“数据”选项卡中出现带有“规划求解”按钮的“分析”组，如下图所示。 步骤2设计电子表格 使用Excel求解线性规划问题时，电子表格是输入和输出的载体，因此设计良好的电子表格，更加易于阅读。本例的电子表格设计如下图所示：
对线性规划整点问题的探究(蒋政)
对线性规划整点问题的探究 一、精确图解法求整数最优解 ( 课本P88习题16 ) 某运输公司有7辆载重量为6t 的A 型卡车与4辆载重量为10t 的B 型卡车，有9名驾驶员。在建筑某段高速公路中，此公司承包了每天至少搬运360t 沥青的任务。已知每辆卡车每天往返的次数为A 型卡车8次，B 型卡车6次，每辆卡车每天往返的成本费A 型车160元，B 型车252元。每天派出A 型车和B 型车各多少辆公司所花的成本费最低？ 解：设每天派出A 型车x 辆、B 型车y 辆，公司所花的成本为z 元，则 0x 70y 4x y 9 68x 106y 360x,y Z ≤≤??≤≤??+≤????+??≥?∈??即0x 70y 4 x y 94x 5y 30x,y Z ≤≤??≤≤? ? +≤??+≥?∈?? z=160x+252y. 如图可行域是ABCD 围成的区域， 作直线160x+252y=0，图形中两直线160x+252y=0和4x+5y=30接近平行， 比较直线斜率k=160252- >-4 5 , 平移直线160x+252y=0，由图可知在A （7， 2 5 ）处取到最小值，但A 不是整数解。 在可行域内共有（3，4），（4，3），（4，4），（5，2），（5，3），（6，2），（6，3），（7，1），（7，2）整数解，经检验只有（5，2）是最优解，此时z=160×5+252×2=1304元。 这种方法适用于区域是封闭区域，且区域内的整数点可数，坐标网络画出来容易在图上识别哪些整点在可行域内。 二、利用近似解估算整数最优解 (课本P63例4) 要将两种不同的钢板截成A 、B 、C 三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示： 今需要A 、B 、C 三种规格的成品分别为15、18、27块，问各截这两种钢板多少张可得所需的三种规格成品，且所使用钢板张数最少。 解：设需截取第一种钢板x 张，第 二种钢板y 张，则 2x y 15x 2y 18x 3y 27x,y 0,x,y N +≥??+≥? ? +≥??≥∈? 目标函数z=x+y, 如图可行域是阴影部分，目标函数在A 点取到最优解。解方程组 x 3y 272x y 15+=?? +=? 得A （185，39 5） 但不是整数解， 规格类型 钢板类型 A 规格 B 规格 C 规格 第一种钢板 2 1 1 第二种钢板 1 2 3 2018 16 14 12 10 8 6 4 2 -15-10-5 51015 x+y=12 x+3y=27 x+2y=18 2x+y=15 A B C D E x O y x+y=9 4x+5y=3 160x+252y=0 A B C D
简单线性规划问题教案
332简单线性规划问题 “简单的线性规划”是在学生学习了直线方程的基础上，介绍直线方程的一个简 单应用，这是《新大纲》对数学知识应用的重视?线性规划是利用数学为工具，来研究一定的人、财、物、时、空等资源在一定条件下，如何精打细算巧安排，用最少的资源，取得最大的经济效益?它是数学规划中理论较完整、方法较成熟、应用较广泛的一个分支，并能解决科学研究、工程设计、经营管理等许多方面的实际问题?中学 所学的线性规划只是规划论中的极小一部分，但这部分内容体现了数学的工具性、应用性，同时也渗透了化归、数形结合的数学思想，为学生今后解决实际问题提供了一种重要的解题方法一一数学建模法.通过这部分内容的学习，可使学生进一步了解数学在解决实际问题中的应用，培养学生学习数学的兴趣和应用数学的意识和解决实际问题的能力 依据课程标准及教材分析，二元一次不等式表示平面区域以及线性规划的有关概念比较抽象，按学生现有的知识和认知水平难以透彻理解，再加上学生对代数问题等 价转化为几何问题以及数学建模方法解决实际问题有一个学习消化的过程，故本节知 识内容定为了解层次 本节内容渗透了多种数学思想，是向学生进行数学思想方法教学的好教材，也是培养学生观察、作图等能力的好教材 本节内容与实际问题联系紧密，有利于培养学生学习数学的兴趣和“用数学”的意识以及解决实际问题的能力 教学重点重点是二元一次不等式（组）表示平面的区域教学难点难点是把实际问题转化为线性规划问题，并给出解答?解决难点的关键是根据实际问题中的已知条件，找出约束条件和目标函数，利用图解法求得最优解?为突 出重点，本节教学应指导学生紧紧抓住化归、数形结合的数学思想方法将实际问题数学化、代数问题几何化课时安排2课时 三维目标 一、知识与技能 1. 掌握线性规划的意义以及约束条件、目标函数、可行解、可行域、最优解等基本概念； 2. 运用线性规划问题的图解法，并能应用它解决一些简单的实际问题I 二、过程与方法 1. 培养学生观察、联想以及作图的能力，渗透集合、化归、数形结合的数学思想，提高学生“建模”和解决实际问题的能力； 2. 结合教学内容，培养学生学习数学的兴趣和“用数学”的意识，激励学生创新. 三、情感态度与价值观 1. 通过本节教学着重培养学生掌握“数形结合”的数学思想，尽管侧重于用“数”研究“形”，但同时也用“形”去研究“数”，培养学生观察、联想、猜测、 归纳等数学能力； 2. 结合教学内容，培养学生学习数学的兴趣和“用数学”的意识，激励学生勇于 创新.
最新单纯形法解线性规划问题
一、用单纯形第Ⅰ阶段和第Ⅱ阶段解下列问题 s.t. 解：1)、将该线性问题转为标准线性问题 一、第一阶段求解初始可行点 2)、引入人工变量修改约束集合 取人工变量为状态变量，问题变量和松弛变量为决策变量，得到如下单纯形表，并是所有决策变量的值为零，得到人工变量的非负值。 2 -2 -1 1 2 1 1 -1 -1 1 2 -1 -2 1 2 5 -2 -4 1 -1 1 5 0 0 0 0 0 3)、对上述单纯形表进行计算，是目标函数进一步减小，选为要改变的决策变量，计算改变的限值。 2 -2 -1 1 2 1 1 1 -1 -1 1 0 2 -1 -2 1 2 0 5 -2 -4 1 -1 1 5 1 0 0 0 0 0 0 1 0 0 0 4)、由于，为人工变量，当其到达零值时，将其从问题中拿掉保证其值不会再变。同时将以改变的决策变量转换为状态变量。增加的值使目标函数值更小。 1 -3 1 1 1 0 1 1 -1 1
1 -3 1 1 1 0 0 0 0 0 0 0 0 5）使所有人工变量为零的问题变量的值记为所求目标函数的初始可行点，本例为， 二、第二阶段用单纯形法求解最优解 -2 2 1 0 1 1 -1 0 -2 1 2 1 5 1 3 要使目标函数继续减小，需要减小或的值，由以上计算，已经有两个松弛变量为零，因此或不能再减小了，故该初始可行点即为最优解。
2、求解问题 s.t. 如果目标函数变成，确定使原解仍保持最优的c值范围，并把目标函数最 大值变达成c的函数。 解：先采用单纯形法求解最优解，再对保持最优解时C值的范围进行讨论。 1）将问题华为标准线性问题 s.t. 2）用单纯形表表示约束条件，同时在不引入人工变量的前提下，取松弛变量得初始值为零值，求解初始解和最优解 10 -1 -1 -1 10 -20 1 5 1 -20 -2 -1 -1 0 0 0 0 要使目标函数继续减小，可以增大，增大的限值是10。 10 -1 -1 -1 10 0 -20 1 5 1 -20 -10 -2 -1 -1 0 -20 0 0 0 10 0 0 3）转轴。将为零的松弛变量和决策变量交换进行转轴 10 -1 -1 -1 10 -10 4 0 -1 -10 0 -20 1 1 2 -20
图解法和单纯形法求解线性规划问题
图解法和单纯形法求解以下线性规划问题 1.1 图解法解线性规划问题 只含两个变量的线性规划问题，可以通过在平面上作图的方法求解，步骤如下： (1)以变量x1为横坐标轴，x2为纵坐标轴，适当选取单位坐标长度建立平面坐标直 角坐标系。由变量的非负性约束性可知，满足该约束条件的解均在第一象限内。 (2)图示约束条件，找出可行域（所有约束条件共同构成的图形）。 (3)画出目标函数等值线，并确定函数增大（或减小）的方向。 (4)可行域中使目标函数达到最优的点即为最优解。 然而，由于图解法不适用于求解大规模的线性规划问题，其实用意义不大。 1.2 单纯形法解线性规划问题 它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。 单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。 单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。 1.3 线性规划问题的标准化 使用单纯形法求解线性规划时，首先要化问题为标准形式
表格法解线性规划问题
表格法解线性规划问题 【教学目标】 知识目标：理解用表格法解线性规划问题的方法和步骤. 能力目标：通过例子详细地介绍了表格法解线性规划问题的过程，并引入了线性规划标准型的概念，归纳总结了表格法 解线性规划问题的步骤. 【教学重点】理解用表格法解线性规划问题的方法和步骤. 【教学难点】理解用表格法解线性规划问题的方法和步骤. 【教学设计】 1、表格法也称单纯形法，是解线性规划问题的常用方法，使用该 方法时，首先要将一般的线性规划问题化为标准型.在教材中给出了化标准型的方法.讲解时一定要注意b≥0以及变量的非负性. 2、表格法解线性规划问题的过程，教材中归纳为五个步骤，这实 际上是一个算法，可以利用前面介绍过的算法知识来学习. 3、初始表格中初始解组的确定是关键，一般可取松弛变量，但当 标准型中没有这样的变量满足初始解组的要求时，通常要通过添加人工变量来解决，本教材没有就这方面的问题进行深入讨论（一般的运筹学教材中都可找到该容）. 4、表格在转换时（通常称为转轴），教材中提到用加减消元法来转 轴.教师可就这部分容作适当的讲解. 5、由于通常的表格转换要进行多次，而表头部分是不变的，因此 可以将多表格合并起来，具体样式可参见5.5节表5-16.
【教学过程】 5.3.1线性规划问题的标准形式 求线性规划问题的图解法虽然直观简便，但对多于两个变量的情况就不能适用了，对于多于两个决策变量的线性规划问题，可以用什么方法呢？ 下面介绍一种用表格的方法来求解线性规划问题的解. 表格法是根据单纯形法而专门设计的一种计算表格. 单纯形法（Simple Method ）是求解线性规划问题的主要方法，该法由丹赛（Dantzig ）于1947年提出，后经过多次改进而成，是求解线性规划问题的实用算法.由上节的叙述可知，如果线性规划问题的最优解存在，则必定可以在其可行解集合的顶点（极点）中找到．因此，寻求一个最优解就是在其可行域的各个极点中搜索最优点.单纯形法实质上是一个迭代过程，该迭代即是从可行域的一个极点移到另一个近邻的极点，直到判定某一极点为最优解为止. 为使用表格法，首先介绍线性规划问题的标准形式. 一般的线性规划问题中目标函数可能是求最大(或最小)值，而线性约束条件中可能是线性方程，也可能是线性不等式，约束条件中约束方程（或不等式）的个数也未必就比决策变量的个数少，这些问题对于线性规划的求解，带来极大的不便，为此，引入下述标准形式： 求目标函数最大值 n n x c x c x c x c Z ++++=...m ax 332211 (用和式表示为j j n j x c Z ∑==1max )
Excel规划求解操作指南线性规划问题的建模与求解
Excel规划求解操作指南(一) ——线性规划问题的建模与求解 内容摘要：《Excel规划求解操作指南》旨在比较通俗地来说明规划求解的步骤和怎么利用它来解决问题，便于大家自学或查询。本文主要介绍Excel规划求解的预备知识、线性规划问题的建模初步方法和利用Excel求解线性规划的步骤。 关键词：Excel 线性规划建模求解 第二次世界大战以来，运筹学成功地解决了许多经济管理问题，作为一门现代科学得到了广泛应用，规划论是运筹学的最重要的分支。计算机的应用为运筹学的发展提供了强大的支持，利用Excel可以解决通常情况下的规划求解问题。但是，使用过Excel的朋友，很多可能都不了解什么是规划求解，而知道有此功能的朋友，也很少有利用此功能来完成实际问题，或者学习时懂了，学过就忘了。《Excel规划求解操作指南》试图比较通俗地来说明规划求解的步骤和怎么利用它来解决问题，便于大家自学或查询。本文是该操作指南的一部分，其他部分将陆续向大家介绍。 一、预备知识 1、规划求解程序安装 在OFFICE的重要组件EXCEL中，有一个规划求解的加载宏。加载该宏之后，就可以利用EXCEl的规划求解功能进行规划求解。在EXCEL2003版本中，通过点击菜单【工具】——【加载宏】，在加载宏对话框中选择【规划求解】项，便可以加载该宏。如果计算机提示无法安装，那么需要插入OFFICE光盘，再进行安装。 2、规划求解的常用函数 （1）SUM函数 利用SUM函数，可以自动求出所选中的单元格数据的和。 首先，选中输出结果的单元格，输入“=”，在下拉菜单中选择“SUM”，得到函数参数对话框 然后，将光标放在Number框中，选中需要求和的单元格，确定。 在菜单栏中会出现输入内容以供检查。例如，
线性规划经典例题及详细解析
一、已知线性约束条件，探求线性目标关系最值问题 1. 设变量x 、y 满足约束条件?? ? ??≥+-≥-≤-1122y x y x y x ，则y x z 32+=的最大值为 。 二、已知线性约束条件，探求非线性目标关系最值问题 2. 已知1,10,220x x y x y ≥?? -+≤??--≤? 则22x y +的最小值是 。 3. 已知变量x ，y 满足约束条件+201-70x y x x y -≤??≥??+≤? ，则 y x 的取值范围是（ ）. A. [95，6] B.（－∞，9 5 ]∪[6，＋∞） C.（－∞，3]∪[6，＋∞） D. [3，6] 三、 研究线性规划中的整点最优解问题 4. 某公司招收男职员x 名，女职员y 名，x 和y 须满足约束条件?? ? ??≤≥+-≥-.112,932, 22115x y x y x 则1010z x y =+的最大 值是 。 四、已知最优解成立条件，探求目标函数参数范围问题 5. 已知变量x ，y 满足约束条件14 22x y x y ≤+≤??-≤-≤? 。若目标函数z ax y =+（其中0a >）仅在点(3,1)处 取得最大值，则a 的取值范围为 。 6. 已知x 、y 满足以下约束条件5503x y x y x +≥?? -+≤??≤? ，使z=x+a y (a >0) 取得最小值的最优解有无数个，则a 的 值为（ ） A. －3 B. 3 C. －1 D. 1 五、求可行域的面积 7. 不等式组260302x y x y y +-≥?? +-≤??≤? 表示的平面区域的面积为 （ ） A. 4 B. 1 C. 5 D. 无穷大 解析： 图1
如何认识线性规划实际问题中有关最优解的精确问题
如何认识线性规划实际问题中有关最优解的精确问题 课本线性规划第二节，提到两个实际问题，一个要求将最优解精确到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要求
线性规划单纯形法(例题)
《吉林建筑工程学院城建学院人文素质课线性规划单纯形法例题》 ? ? ??≥=+ +=+++++=?? ? ??≥≤+≤++=0 ,,,24 261553).(002max ,,0,24 261553).(2max 14.1843214213 214 321432121212 1x x x x x x x x x x t s x x x x z x x x x x x x x t s x x z 标准型得到该线性规划问题的，分别加入松驰变量在上述线性规划问题中法求解线性规划问题。分别用图解法和单纯形）】 （页【为初始基变量， 选择43,x x )1000(00)0010(01 )2050(12)6030(24321=?+?-==?+?-==?+?-==?+?-=σσσσ 为出基变量。为进基变量，所以选择41x x
3 /1)6/122/10(00 )0210(03 /1)3/1240(10)1200(24321-=?+-?-= =?+?-==?+?-==?+?-=σσσσ 为出基变量。 为进基变量，所以选择32x x 24 /724/528/11012/112/124/1100 021110 120124321-=?+-?-=-=-?+?-==?+?-==?+?-=）（）（）（）（σσσσ 4 33 4341522max , )4 3,415(),(2112= +?=+===x x z x x X T T 故有：所以，最优解为
??? ??? ?≥=+ +=+=+ ++++=?????? ?≥≤+≤≤+=0,,,,18232424).(0002max ,,,0 ,182312212 ).(52max 24.185432152142315 43215432121212 1x x x x x x x x x x x x t s x x x x x z x x x x x x x x x t s x x z 标准型得到该线性规划问题的，分别加入松驰变量在上述线性规划问题中法求解线性规划问题。分别用图解法和单纯形）】 （页【 )000010(00001000000000100520200052300010254321=?+?+?-==?+?+?-==?+?+?-==?+?+?-==?+?+?-=σσσσσ）（）（）（）（ 为出基变量。为进基变量，所以选择42x x
线性规划习题精讲
线性规划常见题型及解法 线性规划是新教材中新增的内容之一，由已知条件写出约束条件，并作出可行域，进而通过平移直线在可行域内求线性目标函数的最优解是最常见的题型，除此之外，还有以下六类常见题型。 一、求线性目标函数的取值范围 例1、若x、y满足约束条件 2 2 2 x y 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、不等式组 260 30 2 x y x y y +-≥ ? ? +-≤ ? ?≤ ? 表示的平面区域的面积为（） A、4 B、1 C、5 D、无穷大 解：如图，作出可行域，△A B C的面积即为所求，由梯形OM B C的面积减去梯形OM A C的面积即可，选B 三、求可行域中整点个数 例3、满足|x|＋|y|≤2的点（x，y）中整点（横纵坐标都是整数）有（） A、9个 B、10个 C、13个 D、14个 解：|x|＋|y|≤2等价于 2(0,0) 2(0,0) 2(0,0) 2(0,0) x y x y x y x y x y x y x y x y +≤≥≥ ? ?-≤≥ ? ? -+≤≥? ?--≤ ? 作出可行域如右图，是正方形内部（包括边界），容易得到整点个数为13个，选 D 四、求线性目标函数中参数的取值范围 例4、已知x、y满足以下约束条件 5 50 3 x y x y x +≥ ? ? -+≤ ? ?≤ ? ，使z=x+ay(a>0)取得 最小值的最优解有无数个，则a的值为（） A、－3 B、3 C、－1 D、1 解：如图，作出可行域，作直线l：x+a y＝0，要使目标函数z=x+a y(a>0)取得最小值的最优解有无数个，则将l向右上方平移后与直线x+y＝5重合，故a=1，选 D 五、求非线性目标函数的最值
1用“线性规划问题的最优解在边界上”简解高考题
用“线性规划问题的最优解在边界上”简解高考题 线性规划问题是指在线性约束条件(即关于变量y x ,的二元一次不等式或不等式组)下，求线性目标函数by ax z +=的最大值或最小值问题.在线性规划问题中，满足线性约束条件的解),(y x 叫做可行解，可行解的集合叫做可行域(可行域的边界是直线、射线或线段)，使目标函数取得最值的可行解叫做这个线性规划问题的最优解.求解线性规划问题，通常是通过平移初始直线0=+by ax 来解决的，所以有下面的结论： (1)若线性规划问题存在最优解，则最优解一定在边界上. (2)若目标函数by ax z +=在两个不同的点B A ,处均取到最大值或均取到最小值，则初始直线0=+by ax 与直线AB 平行(此时线段AB 一定是可行域的边界，且线段AB 上的所有点都是最优解). (3)若可行域有凸顶点，则目标函数在可行域的所有凸顶点处的函数值中的最大(小)值就是目标函数的最大(小)值. 下面用这些结论简解几道线性规划题. 题1 (2015年高考山东卷理科第6题)已知x ，y 满足约束条件?????x －y ≥0，x ＋y ≤2，y ≥0. 若z ＝ax ＋y 的最大值为4，则a ＝( ) A ．3 B ．2 C ．－2 D ．－3 解 B.题中的可行域为图1中的OAB ?(其顶点坐标分别是)0,2(),1,1(),0,0(B A O )及其内部的区域. 图1 再由结论(3)，可得3=a 或2.再检验，得2=a . 题2 (2015年高考福建卷文科第10题)变量x ，y 满足约束条件?????x ＋y ≥0，x －2y ＋2≥0，mx －y ≤0. 若z ＝
使用单纯形法解线性规划问题
使用单纯形法解线性规划问题 要求：目标函数为：123min 3z x x x =-- 约束条件为： 123123 1312321142321,,0 x x x x x x x x x x x -+≤??-++≥?? -+=??≥? 用单纯形法列表求解，写出计算过程。 解： 1） 将线性规划问题标准化如下： 目标函数为：123max max()3f z x x x =-=-++ s.t.： 123412356 1371234567211 42321,,,,,,0 x x x x x x x x x x x x x x x x x x x -++=??-++-+=??-++=??≥? 2） 找出初始基变量，为x 4、x 6、x 7，做出单纯形表如下： 表一：最初的单纯形表 变量 基变量 x 1 x 2 x 3 x 4 x 5 x 6 x 7 b i x 4 1 -2 1 1 0 0 0 11 x 6 -4 1 2 0 -1 1 0 3 x 7 -2 0 1 0 0 0 1 1 -f -3 1 1 3） 换入变量有两种取法，第一种取为x 2，相应的换出变量为x 6，进行第一次迭代。迭代后新的单纯形表为： 表二：第一种换入换出变量取法迭代后的单纯形表 变量 基变量 x 1 x 2 x 3 x 4 x 5 x 6 x 7 b i x 4 -7 5 1 -2 2 3
x2-4120-1103 x7-20100011 -f10-101-10-3 由于x1和x5对应的系数不是0就是负数，所以此时用单纯形法得不到最优解。 表一中也可以把换入变量取为x3，相应的换出变量为x7，进行一次迭代后的单纯形表为： 表三：第二种换入换出变量取法迭代后的单纯形表 变量 基变量x1x2x3x4x5x6x7 b i x43-20100-110 x60100-11-21 x3-20100011 -f-110000-1-1 4）表三中，取换入变量为x2，换出变量为x6，进行第二次迭代。之后的单纯形 表为： 表四：第二次迭代后的单纯形表 变量 基变量x1x2x3x4x5x6x7 b i x43001-22-512 x20100-11-21 x3-20100011 -f-10001-11-2 5）表四中，取换入变量为x7，换出变量为x3，进行第三次迭代。之后的单纯形 表为： 表五：第三次迭代后的单纯形表 变量 基变量x1x2x3x4x5x6x7 b i x4-7051-22017 x2-4120-1103 x7-20100011 -f10-101-10-3可以看出，此时x1，x5对应的系数全部非零即负，故迭代结束，没有最优解。 结论： 综上所述，本线性规划问题，使用单纯形法得不到最优解。
线性规划整点问题
线性规划整点问题 1.某电脑用户计划使用不超过500元的资金购买单价分别为60元、70元的单片软件和盒装磁盘，根据需要，软件至少买3片，磁盘至少买2盒，不同的选购方式有多少种？（7） 2.配制,A B两种药剂，需要甲、乙两种原料，已知配一剂A种药品需要甲料3mg，乙料5mg，配一剂B种药品需要甲料5mg，乙料4mg. 今有甲料20mg，乙料25mg，若,A B两种药至少各配一剂，问共有多少种配制方法？(8) 3.有一批同规格的钢条，每根钢条有两种切割方式，可截成长度为a的钢条2根，长度为b的钢条1根；或截成长度为a的钢条1根，长度为b的钢条3根；现长度为a的钢条至少需要15根，长度为b的钢条至少需要27根.问：如何切割可使钢条用量最省？ （()() 4,8,3,9） 4. 有一批同规格的钢条，每根钢条有两种切割方式，可截成长度为a的钢条2根，长度为b的钢条3根；或截成长度为a的钢条3根，长度为b的钢条1根. (1)现需2根a长与1根b长配成一套，问按两种切割方式进行切割应满足的比例是多少? (2)如果长度为a的钢条至少需要50根，长度为b的钢条至少需要45根.问：如何切割 可使钢条用量最省？（1：4；()() 13,8,12,9） 5.某人有一栋楼房，室内面积共计2 m拟割成两类房间作为旅游客房，大房间每间 180, 面积为2 15, m可住游m可住游客5名，每名游客每天住宿费40元；小房间每间面积为2 18, 客3名，每名游客每天住宿费50元. 装修大房间每间需要1000元，装修小房间每间需要600元，如果他只能筹款8000元用于装修，且游客能注满客房，他应隔出大房间和小房间多少间，能获得最大效益?(()() 0,12,3,8) 6.某厂用甲、乙两种原料生产,A B两种产品，制造,A B一吨产品分别需要的各种原料 （1）在现有原料的条件下，如何组织生产才能使利润最大? （2）每吨产品B的利润限制在什么范围内变化，原最优解才会不改变？
