《管理运筹学 第2章 线性规划的图解法(zy)》由会员分享，可在线阅读，更多相关《管理运筹学 第2章 线性规划的图解法(zy)（22页珍藏版）》请在金锄头文库上搜索。
1、管 理 运 筹 学第二章 线性规划问题的计算机求解 1 线性规划问题的提出及其数学模型 2 图解法及单纯型法解题思路 3 “管理运筹学”软件的操作方法1管 理 运 筹 学在管理中一些典型的线性规划应用 合理利用线材问题：如何在保证生产的条件下，下料最少 配料问题：在原料供应量的限制下如何获取最大利润 投资问题：从投资项目中选取方案，使投资回报最大 产品生产计划：合理利用人力、物力、财力等，使获利最 大 劳动力安排：用最少的劳动力来满足工作的需要 运输问题：如何制定调运方案，使总运费最小1 线性规划问题的提出及其数学模型2管 理 运 筹 学1 线性规划问题的提出及其数学模型例1. 某工厂在计划期
2、内要安排、两种产品的生 产，已知生产单位产品所需的设备台时及A、B两 种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位、产品才能使 工厂获利最多？3管 理 运 筹 学1 线性规划问题的提出及其数学模型 线性规划模型： 决策变量： x1：产品的产量， x2：产品的产量 目标函数：Max z = 50 x1 + 100 x2 约束条件： s.t. x1 + x2 3002 x1 + x2 400 x2 250x1 , x2 04管 理 运 筹 学1 线性规划问题的提出及其数学模型例2 某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少
3、购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？5管 理 运 筹 学1 线性规划问题的提出及其数学模型决策变量： x1：原料A的购买量，x2：原料B购买量目标函数： Min f = 2x1 + 3 x2约束条件：s.t. x1 + x2 350x1 1252 x1 + x2 600x1 , x2 0 6管 理 运 筹 学1 线性规划问
4、题的提出及其数学模型 建模过程1.理解要解决的问题，了解解题的目标和条件；2.定义决策变量（ x1 ，x2 ， ，xn ），每一组值表 示一个方案；3.用决策变量的线性函数形式写出目标函数，确定最 大化或最小化目标；4.用一组决策变量的等式或不等式表示解决问题过程 中必须遵循的约束条件7管 理 运 筹 学1 线性规划问题的提出及其数学模型 一般形式决策变量设置： x1， x2， ， xn 目标函数： Max （Min） z = c1 x1 + c2 x2 + + cn xn 约束条件： s.t. a11 x1 + a12 x2 + + a1n xn （ =, ）b1a21 x1 + a22 x
5、2 + + a2n xn （ =, ）b2 am1 x1 + am2 x2 + + amn xn （ =, ）bmx1 ，x2 ， ，xn 0 8管 理 运 筹 学例1.目标函数：Max z = 50 x1 + 100 x2 约束条件：s.t. x1 + x2 300 (A)2 x1 + x2 400 (B)x2 250 (C)x1 0 (D)x2 0 (E)得到最优解：x1 = 50， x2 = 250 最优目标值 z = 275002 图解法及单纯型法解题思路对于只有两个决 策变量的线性规划问 题，可以在平面直角 坐标系上作图表示线 性规划问题的有关概 念，并求解。下面通过例1详细 讲解其
6、方法：9管 理 运 筹 学2 图解法及单纯型法解题思路(1)分别取决策变量X1 , X2 为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。x2x1X20X2=0x2x1X10X1=010管 理 运 筹 学2 图解法及单纯型法解题思路（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300x1+x2300x1+x2=3001001002002x1+x24002x1+x2=40030020030040011管 理 运 筹 学2 图解法及单纯型法解题思路（3）
7、把五个图合并成一个图，取各约束条件的公共部分，如 图2-1所示。100100x2250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图2-112管 理 运 筹 学2 图解法及单纯型法解题思路（4）目标函数z=50x1+100x2，当z取某一固定值时得到一条直 线，直线上的每一点都具有相同的目标函数值，称之为“等 值线”。平行移动等值线，当移动到B点时，z在可行域内实 现了最大化。A，B，C，D，E是可行域的顶点，对有限个 约束条件则其可行域的顶点也是有限的。x1x2z=20000=50x1+100x2图2-2z=27500=50x
8、1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBAD E13管 理 运 筹 学2 图解法及单纯型法解题思路 重要结论： 如果线性规划有最优解，则一定有一个可行域 的顶点对应一个最优解； 无穷多个最优解。若将例1中的目标函数变为 max z=50x1+50x2，则线段BC上的所有点都代表 了最优解； 无界解。即可行域的范围延伸到无穷远，目标 函数值可以无穷大或无穷小。一般来说，这说 明模型有错，忽略了一些必要的约束条件； 无可行解。若在例1的数学模型中再增加一个约 束条件4x1+3x21200，则可行域为空域，不存在 满足约束条件的解，当然也就不存在最优解了 。
9、14管 理 运 筹 学 例2 采用图解法。（练习）100200300400500600100200300400600500x1 =125x1+x2 =3502x1+3x2 =8002x1+3x2 =9002x1+x2 =6002x1+3x2 =1200x1 x2 Q2 图解法及单纯型法解题思路Q点坐标（250，100）为最优解15管 理 运 筹 学2 图解法及单纯型法解题思路 单纯型法是用来求解线性规划问题的方法 其求解思路:（1）找到一个可行域上的顶点（初始基可行解 ）作为待考查的解。（2）将该解和与其相邻的顶点（基可行解）相 比较，若该解优于相邻解，则该解为整个线性规划 问题的最优解；否则
10、将更优的相邻解代替当前考查 的解。（3）重复第（2）步，直至找到解的情况，计 算结束。16管 理 运 筹 学3 “管理运筹学”软件的操作方法“管理运筹学”2.0版（Window版），是1.0版（DOS版）的升级版。它包括：线性规划、运输问题、整数规划（0-1整数规划、纯整数规划和混合整数规划）、目标规划、对策论、最短路径、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、决策分析、预测问题和层次分析法，共15个子模块。17管 理 运 筹 学例1.目标函数：Max z = 50 x1 + 100 x2 约束条件：s.t. x1 + x2 300 (A)2 x1 + x2 400 (
11、B)x2 250 (C)x1 0 (D)x2 0 (E)3 “管理运筹学”软件的操作方法1.软件使用演示：（演示例1）第一步：点击“开始”-“程序”- “管理运筹学2.0”，弹出主窗口。18管 理 运 筹 学3 “管理运筹学”软件的操作方法第二步：选择所需子模块，点击主窗口中的相应按钮。本题中选用“线性规划”方法。点击按钮弹出如下界面：19管 理 运 筹 学3 “管理运筹学”软件的操作方法第三步：点击“新建”按钮，输入数据。本题中共有2个变量，4个约束条件，目标函 数取MAX。点击“确定”后，在表中输入Cj,bi和aij等值，并确定变量的正负约束。输入数值后的界面如下。20管 理 运 筹 学3 “管理运筹学”软件的操作方法第四步：点击“解决”按钮，得出计算结果。本题的运行结果界面如下。21管 理 运 筹 学3 “管理运筹学”软件的操作方法第五步：分析运行结果。 本题中目标函数的最优值是27500，x1=50, x2=250 。 22
