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

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


★ 解题方法与技巧

线性规划问题的四种求解方法
江苏溧阳中学( 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) 吕清平 线性规划问题是现实生活中一类...
线性规划问题的四种求解方法.pdf
线性规划问题的四种求解方法 - ? 解题方法与技巧 线性规划问题的四种求解方法 江苏溧阳中学( 213300) 线性规划问题是现实生活中一类重要的应 用问题, 它常用来...
线性规划中的整点问题求解方法.doc
线性规划中的整点问题求解方法 - 线性规划中的整点问题求解方法 线性规划是运筹学的一个重要分支,在实际生活中有着广泛的应用。新教材中增加了 线性规划的内容,...
03 第三章 几种特殊的线性规划问题及其解法.ppt
第三章 几种特殊的线性规划问题及其解法 第三章 几种特殊的线性规划 问题及其...特殊结构的线性规划模型,人们探讨了更为简便的求解方法,从而大大 简化了计算。 ...
一非线性规划问题的几种求解方法1 罚函数法(外点法)_图文.ppt
一非线性规划问题的几种求解方法1 罚函数法(外点法)_幼儿读物_幼儿教育_教育专区。一非线性规划问题的几种求解方法1 罚函数法(外点法) ...
运筹学判断题.doc
判断题: (共 83 道) 1、对于任意线性规划问题(含三维以上) ,它的基可行解...× 50、规划论、对策论、概率方法、统计分析法是军事运筹学常用的几种方法。√...
线性规划中的整点问题求解方法.doc
线性规划中的整点问题求解方法宜昌市一中 祝海燕 线性规划是运筹学的一个重要...总之,以上四种基本方法各有各的特点,因此有时要根据具体情况选择合适方法。 3...
第二章 线性规划问题解的性质.ppt
法一般过程 对于仅具有两个变量的线性规划问题,利用 作图的方法求最优解,简单...O x1 -x1+x2=1 x1+x2= -2 线性规划问题解的四种情况: ? 有唯一最优...
求解线性规划问题最优解时常遇到的几种特殊情况.pdf
求解线性规划问题最优解时常遇到的几种特殊情况 - 第 24 卷第 3 期 201
两参数线性规划问题的解法_论文.pdf
两参数线性规划问题的解法 - 用分块矩阵法讨论含有两个参数的线性规划问题的求解方法
用Excel求解线性规划问题的探究.doc
用Excel求解线性规划问题的探究 - 曲靖师范学院 本科生毕业论文 论文题目:用 Excel 求解线性规划问题的探究 作者、学号: 学院、年级:数学与信息科学学院 2010 级 ...
线性规划中目标函数的几种类型及其向量解法.pdf
线性规划中目标函数的几种类型及其向量解法_数学_高中教育_教育专区。中学数学...得最优解 . 值得说明的是: 利用这种方法 不仅能解决线性约束条件下线性 目标...
线性规划中几种内点算法的比较.doc
龙源期刊网 http://www.qikan.com.cn 线性规划中几种内点算法的比较 作者:...Dantzig 提出了求解线性规划问题的通用方法单纯形法, 大量的实际应用表明,...
线性规划与图解法.ppt
最优解:使目标函数达到最大值的可行解。 图解法线性规划问题的求解方法 一般有...通过图解法了解线性规划有几种解的形式 (唯一最优解;无穷多最优解;无界解;无...
图解法求解线性规划.doc
(线性规划解有四种情形,唯一最优解,无穷 多个最解,无界解,无可行解) 实验...在今 后的学习中,我也会利用所学的求解线性规划问题的方法,得到更好的掌握。...
运筹学 线性规划_图文.ppt
最优解:使目标函数达到最大值的可行解。 2.2 图解法线性规划问题的求解方法 ...通过图解法了解线性规划有几种解的形式。 (1)唯一最优解:一定对应于可行域的...
运筹期中考试.doc
运筹期中考试 - 习题详解 1.判断下列各题正误 (1)图解法提供了求解线性规划问题的通用方法。 ( × ) 图解法提供了求解线性规划问题的通用方法。 用单纯形法...
浅谈_线性规划中的整点最优解_的几种求法_图文.pdf
(湖州中学浙江湖州313000)((简单的线性规划问题》是高中数学教材必修5第三章《...的教 学研究和资料查阅我得到几种寻求“线性规划中的整点最优 解”的方法。 ...
Chap1_线性规划及其单纯形方法_图文.ppt
Operations Research 1.1.1 线性规划问题的提出解: 每一种标准卷纸可以有好几种切割的方式。例如 2米宽的卷纸可以切成四个 0.5 米宽的卷纸,也可以切成二个...
1.1 线性规划的数学模型_图文.pdf
1.1 线性规划的数学模型 - 管理运筹学--管理科学方法 李军 桂林电子科技大学商学院 本章框架 线性规划及单纯形法 ? 基本概念 ? ? 线性规划问题的数学...
更多相关标签: