图解法例题和答案--上课专用

1、2010年8月管理工程学院运筹学运筹学1图解法图解法图解法步骤可行解及可行解集的特性线性规划问题解的特点单纯形法的思路2010年8月管理工程学院运筹学运筹学2一一 、图解法步骤、图解法步骤建立坐标系建立坐标系找出可行域找出可行域绘出目标函数图形绘出目标函数图形求出最优解求出最优解2010年8月管理工程学院运筹学运筹学3例题例题12010年8月管理工程学院运筹学运筹学4 例例1.2的数学模型如下：的数学模型如下： max z2x13x2 2x12x212 (1) x1 2x2 8 (2) 4 x1 16 (3) 4x2 12 (4) x1,，x2 0 (5)解：最优解为解：最优解为(4, 2)，

2、最优值为，最优值为14。即企业生产。即企业生产、产品最产品最佳方案是：佳方案是： 生产生产4件产品件产品，2件产品件产品，能获取利润，能获取利润14元。元。x 2x1Q2Q3Q1Q42010年8月管理工程学院运筹学运筹学5例题例题22010年8月管理工程学院运筹学运筹学6二、线性规划解其他的情况二、线性规划解其他的情况 1. 1.无穷多最优解无穷多最优解 将上例中的目标函数变为将上例中的目标函数变为 max z2x14x2 2x12x212 (1) x1 2x2 8 (2) 4 x1 16 (3) 4x2 12 (4) x1,，x2 0 (5)则则Q2Q3线段上的任意点都使线段上的任意点都使目

3、标函数值目标函数值z达到最大，即该达到最大，即该问题有无穷多最优解。问题有无穷多最优解。x 2x1Q2Q3Q1Q42010年8月管理工程学院运筹学运筹学7例题例题32010年8月管理工程学院运筹学运筹学82.无界解（或无最优解）无界解（或无最优解）例例2的数学模型如下：的数学模型如下： max z2x13x2 s.t. 4 x1 16 x1,，x2 0 若上例中的约束条件只考若上例中的约束条件只考虑虑(3)和和(5)时，问题具有无界解。时，问题具有无界解。 原因：建立实际问题的数学模原因：建立实际问题的数学模型时漏了某些必要的资源约束。型时漏了某些必要的资源约束。x 2x12010年8月管理工

4、程学院运筹学运筹学9例题例题42010年8月管理工程学院运筹学运筹学103.无可行解无可行解 max z2x13x2 s.t. 2x12x212 x1 x2 8 x1,，x2 0原因：约束条件之间相互矛盾原因：约束条件之间相互矛盾x 2x1682010年8月管理工程学院运筹学运筹学11例题例题52010年8月管理工程学院运筹学运筹学12三、目标函数最小化的线性规划问题：三、目标函数最小化的线性规划问题：例例 某公司由于生产需要，共需要某公司由于生产需要，共需要A、B两种原料至少两种原料至少350吨吨（A、B两种原料有一定替代性），其中两种原料有一定替代性），其中A原料至少购进原料至少购进125

5、吨。但吨。但由于由于A、B两种原料的规格不同，各自所需要的加工时间也是不同两种原料的规格不同，各自所需要的加工时间也是不同的，加工每吨的，加工每吨A原料需要原料需要2个小时，加工每吨个小时，加工每吨B原料需要原料需要1小时，而小时，而公司共有公司共有600个加工小时。又知道每吨个加工小时。又知道每吨A原料的价格为原料的价格为2万元，每吨万元，每吨B原料的价格为原料的价格为3万元，试问在满足生产需要的前提下，在公司加万元，试问在满足生产需要的前提下，在公司加工能力范围内，如何购买工能力范围内，如何购买A、B两种原料，使得购进成本最低？两种原料，使得购进成本最低？解：解：设设 为购进原料为购进原料

6、A的吨数，的吨数， 1x 为购进原料为购进原料B的吨数，的吨数， 2x可以得到线性规划模型如下：可以得到线性规划模型如下：2010年8月管理工程学院运筹学运筹学1335021 xx1251x600221 xx1x2x目标函数：目标函数： ,32min21xxf约束条件：约束条件： ,35021 xx,1251x,600221 xx. 0, 021xx在直线在直线 与直线与直线 35021 xx600221 xx的交点处的交点处, 即点即点 处处, 目标函数达到最小值。目标函数达到最小值。 A原料原料250吨，吨， B原料原料100吨，吨， 成本最小。成本最小。 100,250即购买即购买 可使

7、可使 100,250解：（写出前四个步骤）2010年8月管理工程学院运筹学运筹学14购买的原料购买的原料A A与原料与原料B B的总量为：的总量为： )(吨350100250所需工时为：所需工时为： )(小时60010012502原料原料A A的购进量的购进量250250吨比吨比A A的最底限的最底限125125吨多购进了吨多购进了 )(吨1251252502010年8月管理工程学院运筹学运筹学15四、图解法分析（对单纯形法的启示）四、图解法分析（对单纯形法的启示）求解线性规划问题解情况有：唯一最优解、无穷多求解线性规划问题解情况有：唯一最优解、无穷多最优解、无界解、无可行解。最优解、无界解、无可行解。若线性规划问题可行域存在，则可行域是一个凸集。若线性规划问题可行域存在，则可行域是一个凸集。若线性规划问题的最优解存在，则最优解或最优解若线性规划问题的最优解存在，则最优解或最优解之一（无穷多解时）一定能够在可行域（凸集）的之一（无穷多解时）一定能够在可行域（凸集）的某顶点找到。某顶点找到。解题思路：找到凸集的任一顶点，计算目标函数值；解题思路：找到凸集的任一顶点，计算目标函数值；比较相邻顶