当前位置:首页 >> 理学 >>

线性规划问题的四种求解方法

★ 解题方法与技巧

线性规划问题的四种求解方法
江苏溧阳中学( 213300)   吕清平    线性规划问题是现实生活中一类重要的应 用问题 , 它常用来研究物资调运 、 生产安排 、 下 料等工作的资源优化配制问题 , 寻求线性规划 问题的最优解具有十分重要的现实意义 . 现介 绍几种求解线性规划问题的最优解的策略 . 一、 截距法 例 1  某厂需从国外引进两种机器 . 第一 种机器每台 10 万美元 , 维 护费为人民币 4000 元; 第二种机器每台 20 万美元 , 维护费为人民 币 1000 元 ; 而第一种机器产生的年利润为每台 12 万美元 ; 第二种机器产生的年利润为 18 万 美元 . 但政府核准的外汇是 130 万美元 , 并要求 总维护费不得超过人民币 24000 元 . 问每种机 器应购买多少台时 , 才能使工厂获得的年利润 最大 ? 解: 设购买第一种机 器 x 台 , 购买第二种机器 y 台 . 10 x +20 y ≤ 130 则 4000 x +1000 y ≤ 24000 x ≥ 0  y ≥ 0 x +2 y ≤ 13 即 4 x + y ≤ 24 x ≥0 , y ≥0 总年利润 z = 12 x +18 y 作出以上不等式组所表示的平面区域 , 即 可行域 . 由 z =12 x z 2 为直线 y =18 3 2 z +18y 得 y =- x + , 则 3 18 z x + 的截距 . 令 z =0 , 则 18 时 , z max = 12 ×5 +18 ×4 = 132( 万美元) 答: 购买第一种机器 5 台 , 第二种机器 4 台 时能使工厂获得的年利润最大 . 二 、等值线法 所谓等值线是指直线上任一点的坐标 ( x, y) 都使 F ( x , y )= Ax +By 取等值 C 的直线 l : Ax +By = C( A 、B 不同时为零) . 通过比较等 值线的值的大小可以求得简单线性规划问题的 最优解 . 例 2  甲 、 乙两地生产某种产品 . 甲地可调 出 300 吨 , 乙地可调出 750 吨 , A 、 B 、C 三地需要 该种产品分别为 200 吨 、 450 吨和 400 吨 . 每吨 运费如下表( 单位 : 元) : A 甲地 乙地 6 5 B 3 9 C 5 6

   问怎样调运 , 才能使总运费最省 ? 解   设 由甲 地 调往 A 、 B 两地分 别 为x 吨 , y 吨. 则由甲 调往 C 地 为 [ 300 ( x +y ) ] 吨; 由乙地 调往 A 、B 、C 三地分别为( 200 -x )吨 、 ( 450 y) 吨、 ( 100 + x +y ) 吨. 于是 x +y ≤ 300 x ≤ 200 x ≥0 , y ≥0 z =6 x +3 y +5[ 300 -( x +y ) ] +5( 200 -x ) +9( 450 -y )+6( 100 + x + y )= 2 x -5 y + 7150 作出以上不等式组所表示的平面区域即可 行域 . 令 z = 0 , 则可画出 直线 l 0 : 2 x -5 y + 7150 = 0 . 画出一组与 l 0 平行的等值线 , 比较等 11

2 可画出直线 l 0 : y =- x , 把直线 l 0 向右上方 3 平移 , 当经过可行域上点 B 时 , 直线的截距最 大. 此时 z = 12 x +18y 取最大值 . 解方程组 x +2 y = 13 得 B( 5 , 4) . 故当 x = 5 , y = 4 4 x +y = 24

《中 学理科》 2002 年第 7 期

★ 解题方法与技巧 值线值的大小知 , 当等值线经过可行域上点 C 时 , 等值线的值最小 . z 有最小值 5650 元 , 此时 x = 0 、y = 300 , 故甲地产品运往 B 地 ; 乙地产 品运往 A 、B 、C 三地分别为 200 吨 、 150 吨 、400 吨时能使总运费最省 . 三、 顶点法 如果可行域是一个多边形围成的区域( 包 括边界多边形) 时 , 线性目标函数 z = f( x 、y ) 的最优解必在多边形顶点上取到 . 因此算出 z = f( x 、y )在各项点的值 , 再比较大小可以找 出最优解 . 例 3   某工厂每天要生产甲 、 乙两种产品 , 每件甲产品需分别在 A 、B 、 C 、D 四台不同设备 上加工 2 、1 、 4、 0 小时 ; 每件乙产品需分别在 A 、 B 、C 、 D 上加工 2 、 2、 0、 4 小时 。 已知 A 、B 、C 、 D 每天最多能转动的时数分 别是 12 、 8、 16 、 12 小 时. 生产一件甲产品该厂得利润 200 元 , 生产一 件乙产品得利润 300 元 . 问每天如何安排生产 才能得到利润最大 ? 解   设每天生产甲 、乙产品的件数分别是 维生素 A( 单位 / 千克) 维生素 B ( 单位 / 千克) 成本( 单位 / 千克) 成本如下表 : 甲 600 800 11 乙 700 400 9 丙 400 500 4

   某食物营养所想用 x 千克甲种食物 , y 千 克乙种食物 , z 千克丙种食物配成 100 千克混合 物 , 并使混合物至少含有 56000 单位维生素 A 和 63000 单位维生素 B ( 1) 用 x 、y 表示混合物的成本 c( 元) ; ( 2) 确定 x 、y 、z 的值 , 使成本最低 . 解   ( 1)c = 11 x +9 y +4 z  x +y +z = 100 ∴c = 400 +7 x +5 y ( 2) 由题意得 600 x +700y +400z ≥ 56000 800 x +400y +500z ≥ 63000 x ≥0 , y ≥0 ∵ z = 100 - x -y 2 x +3 y ≥ 160 ∴ 3 x -y ≥ 130 x ≥ 0  y ≥ 0 成本 c = 400 +7 x +5y 令 7 x +5 y =λ ( 2x + 3y ) +μ ( 3 x -y ) ( λ 、 μ是待定系数) 则 7 x +5 y =( 2 λ+3 μ ) x +( 3 λ- μ ) y 2 λ+3 μ= 7 3 λ- μ= 5 解得 λ= 2 、μ= 1 于是 ∴c =400 +7 x +5 y =400 +2( 2 x +3 y ) +( 3 x -y )≥ 400 +2 ×160 +130 = 850 当且仅当 2 x +3 y = 160 3 x -y = 130  即 x = 50 时 y = 20

   作出以上不等式组所表示的平面区域 , 即 可行域 . 可行域为一五边形 , 五个顶点对应的 z 值如下表
( x , y) z = 200 x + 300 y ( 0 , 0)( 4 , 0)( 4 , 2)( 2 , 3)( 0 , 3) 0 800 1400 1300 900

  由表可知 : 在可行域的顶点 B ( 4 , 2) 处z取 得最大值 . 故 x =4 , y =2 , z 有最大值 1400 元 . 答: 每天生产 4 件甲产品 , 2 件乙产品能得 到最大利润 . 四、 待定系数法 对于特殊的线性规划问题也可以用待定系 数法求解 . 例 4   甲 、乙 、丙三种维生素 A 、B 含量及 12

等号成立 . 答: x 为 50 千克 , y 为 20 千克 , z 为 30 千克 时成本最低为 850 元 . 需要说明的是 , 若所求的最优解是整数解 , 而用以上方法求得的最优解不是整数 , 则可以 用平移法寻找到最优整数解 .

《中 学理科》 2002 年第 7 期


相关文章:
线性规划问题的四种求解方法.pdf
线性规划问题的四种求解方法_理学_高等教育_教育专区。★ 解题方法与技巧 线性规划问题的四种求解方法江苏溧阳中学( 213300) 吕清平 线性规划问题是现实生活中一类...
线性规划及其应用3线性规划求解方法_图文.ppt
线性规划及其应用3线性规划求解方法 - §3.3 线性规划求解方法 4、作用:线性规划理论的几何意义,并说明线性规划的四种情况(唯一最优解、无穷最优解、有可 ...
线性规划中的整点问题求解方法.doc
线性规划中的整点问题求解方法 - 线性规划中的整点问题求解方法 线性规划是运筹学的一个重要分支,在实际生活中有着广泛的应用。新教材中增加了 线性规划的内容,...
线性规划图解法3.线性规划问题标准形式4.线性规划.ppt
? 2.学习目的:学习图解法的目的并非是要掌握一种线性 规划问题的求解方法,而是...4.线性规划问题的解可能有四种情况:唯一最优 解;无穷多最优解;无界解和无...
运筹学判断题.doc
√ 26、运输问题是一种特殊的线性规划模型,因而求解结果也可能出现下列四种情况...× 50、规划论、对策论、概率方法、统计分析法是军事运筹学常用的几种方法。√...
运筹期中考试.doc
运筹期中考试 - 习题详解 1.判断下列各题正误 (1)图解法提供了求解线性规划问题的通用方法。 ( × ) (2)用单纯形法求解一般线性规划时,当目标函数求最小值...
13秋学期《运筹学》在线作业满分答案.txt
B. 线性规划问题求解的结果有四种,它们分别是唯一解、无穷多解、无解和无界解...A 满分:2分得分:2 8.Excel“规划求解”工具求解整数规划问题利用的方法是( )...
2016最优化理论与方法(线性部分)思考题_图文.doc
2016最优化理论与方法(线性部分)思考题 - 最优化理论与方法(线性部分)思考题 1. 就你学过的运筹学问题,写出能够建立线性规划模型的问题,并 举例(建立模型) 。...
线性规划LP 线性规划是一种对问题进行求解方法-PPT精品....ppt
线性规划LP 线性规划是一种对问题进行求解方法-PPT精品文档 - 第三章 线性规划的一般求解方法 单纯形法 一、线性规划问题的一般形式 它的一般形式为: 或 ...
1.运筹学-线性规划理论及应用_图文.ppt
将讨论什么是线性规划问题,线性 规划问题的数学表示,基本理论、概念和求解 方法...12 练习:某畜牧厂每日要为牲畜购买饲料以使其获取 A、B、C、D四种养分。...
图解法求解线性规划.doc
(线性规划解有四种情形,唯一最优解,无穷 多个最解,无界解,无可行解) 实验...在今 后的学习中,我也会利用所学的求解线性规划问题的方法,得到更好的掌握。...
第二章 线性规划(管理运筹学,李军)_图文.ppt
? 2.学习目的:学习图解法的目的并非是要掌握一种线性 规划问题的求解方法,而是...4.线性规划问题的解可能有四种情况:唯一最优 解;无穷多最优解;无界解和无...
最优化理论与方法(线性部分)思考题与作业要求 - 用于合并.doc
以下四种食物 1、2、3、4,依次售价为 50、20、30、80,而我们 人体每天需...答:应用对偶原理求解原始线性规划的一种方法在原始问题 单纯形表格上进行...
运筹学-1-线性规划.ppt
下表给出了单位原料 可提取的药物量解: 习题3 1.决策变量:设四种原料的使用...判别方法:无最优解判别定理在求解极大化的线性规划问题过程中,若某单纯形表的...
1. 线性规划问题及其数学模型2. 线性规划的图解法3. 线....ppt
? 2.学习目的:学习图解法的目的并非是要掌握一种线性 规划问题的求解方法,而是...4.线性规划问题的解可能有四种情况:唯一最优 解;无穷多最优解;无界解和无...
线性规划及其应用3-线性规划求解方法_图文.ppt
3、适用范围:两个变量的线性规划问题。重庆大学经济与工商管理学院 肖智 §3.3 线性规划求解方法 4、作用:线性规划理论的几何意义,并说明线性规划解 的四种情况(...
运筹学考试题b卷及答案.doc
)( 6:运输问题是一种特殊的线性规划模型,因而求解结果也可能出现下列四种情况之...4:在运输问题模型中,计算检验数的方法一般有___和___两种方法。 5:动态规划...
第二章线性规划模型和图解法全.ppt
掌握两个变量线性规划问题的几何作图求解方法; 掌握两个变量线性规划模型可行域的...这些产品分 别要在A、B、C、D、四种不同的设备上加工。按工 艺资料规定,...
[数学]02线性规划_图文.ppt
掌握一种线性规划问题的求解方法,而 是要通过图解法揭示线性规划问题的内在规律,...4.线性规划问题的解可能有四种情况:唯一最优 解;无穷多最优解;无界解和无...
运筹期中考试.doc
运筹期中考试 - 习题详解 1.判断下列各题正误 (1)图解法提供了求解线性规划问题的通用方法。 ( × ) 图解法提供了求解线性规划问题的通用方法。 用单纯形法...