《卫生管理运筹学所有课件及课后答案.ppt》由会员分享，可在线阅读，更多相关《卫生管理运筹学所有课件及课后答案.ppt（91页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、E-mail:wells_Mobilephonenumber:13408413321运筹学运筹学 OPERATIONAL RESEARCH第一第一节节线性规划问题及其数学模型线性规划问题及其数学模型第二第二节节线性规划问题的图解法线性规划问题的图解法第三第三节节单纯形法单纯形法第四第四节节应用实例应用实例第二章 线性规划线性规划（LP）是运筹学的一个重要分支线性规划研究的主要问题 一类是已有一定数量的资源（人力、物质、时间等），研究如何充分合理地使用它们，才能使某一目标（产量、利润）达到最大；另一类是当一项任务确定以后，研究如何统筹安排，才能使完成任务所耗费的资源量为最少；实际上，上述两类问题
2、是一个问题的两个不同的方面，都是求问题的最优解（max 或 min）；线性规划问题要求目标函数与约束条件函数都是线性的，而且目标函数只有一个。第一节 线性规划问题及数学模型例例1 某制药厂用甲、乙两台机器生产A、B两种药物。每种药物要经过两道工序，在甲机器上搅拌，在乙机器上包装。已知在未来一周内，甲、乙两台机器的使用时间分别不得超过40小时和30小时，生产每千克药物所需的加工时间如下表2-1所示。如果生产每千克药物A的利润是30元，B是25元，试问，如何安排这一周的生产，能使工厂利润最大？一、线性规划问题的提出表2-1 A、B两种药物在各机器上所需加工时间及各机器可用于加工的总时间 项 目每千
3、克药物A的加工时间（小时千克/）每千克药物B的加工时间（小时/千克）可用于加工的总时间（小时）甲机器2440乙机器3230目标函数：Max 约束条件：解：解：设 ，分别表示1周内生产A、B两种药物的数量（单位千克），Z表示1周的工厂利润，于是上述问题的数据模型为：例例2用三种原料B1、B2、B3配制某种食品，要求该食品中蛋白质、脂肪、糖、维生素的含量不低于15、20、25、30单位。营养成分营养成分原原 料料B B1 1B B2 2B B3 3蛋白质（单位蛋白质（单位/500/500克）克）5 56 68 8脂肪（单位脂肪（单位/500/500克）克）3 34 46 6糖（单位糖（单位/500
4、/500克）克）8 85 54 4维生素（单位维生素（单位/500/500克）克）101012128 8原料单价（单位原料单价（单位/500/500克）克）202025253030表2-2 以上三种原料的单价及每单位原料所含各种成分的数量，如下表2-2所示。问应如何配制该食品，使所需成本最低？解：解：设x1、x2、x3分别表示原料B1、B2、B3的用量，Z表示食品的成本，则这一食品配制问题变为：目标函数Min 约束条件：1.每一个问题都用一组决策变量（）表示某一方案；它们取不同的非负值，代表不同的具体方案。2.决策变量受到一些约束条件的限制，这些约束条件可以用一组线性等式或线性不等式来表示。3
5、.都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示。按问题的不同，目标函数可以是最大化，也可以是最小化。满足以上三个条件的数学模型称为线性规划线性规划二、线性规划问题的结构特征 线性规划问题的数学模型有以下共同特征：线性规划问题的一般形式线性规划问题的一般形式：目标函数：Max（Min）约束条件：式中称为价值系数价值系数；称为技术系数技术系数；称为限定系数限定系数（或称右端系数）一般地，假设线性规划数学模型中，有m个约束，有n个决策变量xj,j=1,2,n，线性规划数学模型的一般表达式可写成：（一）线性规划问题的标准形式（一）线性规划问题的标准形式（standardfor
6、mofLP）三、线性规划问题的标准型线性规划问题有不同的形式：目标函数有的要求max，有的要求min;约束条件可以是，也可以是，还可以是=；决策变量一般是非负约束，但也允许任意实数取值;一般形式的线性规划问题可以转化为标准形式的线性规划问题，以便于求解，规定标准形式如下：目标函数：Max约束条件：标准型中规定各约束条件的右端项bi0，否则等式两端乘以-1.线性规划问题的标准型为:1目标函数求最大值（或求最小值）2约束条件都为等式方程3决策变量xj非负4右端常数bi非负简写形式简写形式矩阵形式矩阵形式 Max s.t.Max s.t.（二）标准形式的转化（二）标准形式的转化1 1目标函数的转换目
7、标函数的转换 对于目标函数 Min 两边乘（-1）则 Max(-Z)=令即有Max=实际遇到的线性规划问题的数学模型都应先转化为标准形式后采用统一的方法求解.2.2.约束条件的转换约束条件的转换（1）约束条件是“”形式：在不等式的左端加入非负的变量（也称作松弛变量松弛变量）如：则可在不等式的左端加入一个松弛变量则该约束条件变为：其中（2）约束条件是“”形式：在不等式的左端减去一个非负的变量（称作剩余变量剩余变量，也可称松弛变量）如：则可在不等式的左端减去一个剩余变量 则该约束条件变为：其中（3）右端项为负值：在方程的两边乘以“1”，以保证右端项为正值 如：方程两边乘以1，得 3 3决策变量的转
8、换决策变量的转换（1）决策变量令其中将 带入到原问题使决策变量满足大于等于零的要求 （2）决策变量为自由变量自由变量 令，其中 因为之间大小关系不确定，故可以取遍整个实数域 例例3 3将下面线性规划问题化为标准形式 解：解：令其中其中，同时引入剩余变量，松弛变量则带入方程后得：1可行解：满足所有约束条件的解，称为线性规划问题的可行解可行解。2最优解：满足目标函数式的可行解，称为线性规划问题的最优解最优解。3最优值：对应于最优解的目标函数之值，称为最优值最优值。第二节 线性规划问题的图解法 线性规划问题的图解法简单直观，有助于了解线性规划问题求解的基本原理。对于只有2个决策变量的线性规划问题可以
9、采用图解法.一、线性规划问题的几个基本概念例例4仍以前面的例1为例，它可以用下面的数学模型来表示：二、图解法步骤步骤：建立平面直角坐标系，取x1为横轴，x2为纵轴 求满足约束条件的可行解区域 可行域可行域：满足所有约束条件的解的公共部分所构成的可行解的集合 凸集凸集：如果在形体内任意取两点连接一根直线，若线段上所有的点都在这个形体中 作目标函数的等值线簇，确定目标函数值增加方向 求出最优解 10 20 x1x215 1050AB（5，7.5）CZ=0Z=150Z=337.5图2-1 线性规划问题的图解法从图2-1可以看出可行域：四边形OABC最优解是如下两条直线的交点：解此方程组得到B点的值为
10、（5，7.5），即当 ，时，目标函数取得最大值Z=337.5 图解法时线性规划问题不必化为标准型。例例5用图解法解下面线性规划问题 s.t.100 200 300 400 500 600 x1x26005004003002001000ACB图2-2 目标函数求最小值的线性规划问题图解法C点的坐标可以从线性方程组：中求出，即此线性规划问题的最优解为：minZ=800 前面例4、例5的情形，线性规划问题有唯一最优解唯一最优解三、线性规划问题的形式与特点唯一最优解一定在凸集（可行解）的顶点（即角顶可行解）处取得.多重最优解多重最优解无界解无界解无最优解无最优解x1x1x2 x2 x1x2O10203
11、040102030405050无无可行解可行解即无最优解即无最优解max Z=10 x1+4x2由以上例题可知，线性规划的解有3种形式：唯一最优解唯一最优解：角顶可行解处取得多重最优解多重最优解：如果一个线性规划问题存在多重最优解，那么它至少有两个相邻的角顶可行解所对应的目标函数值相等，且达到最大值（或最小值）无最优解无最优解 可行域为空 可行域是一个无限空间（无界解）第三节 单纯形法只有2个决策变量的线性规划问题可以采用图解法求解；对于两个以上的多变量线性规划问题很难使用图解法求解，下面介绍一种求解线性规划问题最常用的方法-单纯形法单纯形法.（一）典型方程组（一）典型方程组 i1，2，m 式
12、中是重新排序后的变量为非负常数 一、单纯形法的基本原理对于n个决策变量，m个约束的标准型线性规划问题，通过初等变换必然能使其化成如下同解方程组：典典型型方方程程组组（二）基本变量（二）基本变量：如果变量xj在某一方程中系数为1，而在其它一切方程中的系数为零，则称xj为该方程中的基本变量。否则为非基本变量。基本变量的个数为线性无关的方程的个数。（三）基本解（三）基本解：在典型方程中，设非基本变量（自由未知量）为零，求解基本变量得到的解，称为基本解基本解。（四）基本可行解：（四）基本可行解：基本变量为非负的一组基本解称为基本可行解。基本解与基本可行解基本解与基本可行解例：对方程组 x1+x2-x3
13、+2x43 2x1+x2 -3x41 施行初等变换，可以得到：x1 +x3-5x4-2 x2-2x3+7x45 式和为典型方程组，基本变量是x1和x2，非基本变量为x3和x4。可得到基本解为：X=（-2 5 0 0）T 同样对、施行初等变换还可以得到：1.4 x1+x2-0.6 x3 2.2 -0.2 x1 -0.2 x3+x40.4 此时，基本变量为x2和x4，非基本变量为x1和x3。基本解为：X（0 2.2 0 0.4）T 非基本可行解基本可行解1 1 可行解与最优解：可行解与最优解：最优解一定是可行解，但可行解不一定是最优解。线性规划解之间的关系线性规划解之间的关系基本解不一定是可行解，
14、可行解也不一定是基本解。2 2 可行解与基本解：可行解与基本解：3 3 可行解与基本可行解可行解与基本可行解：基本可行解一定是可行解，但可行解不一定是基本解。基本可行解一定是基本解，但基本解不一定是基本可行解。4 4 基本解与基本可行解：基本解与基本可行解：5 5 最优解与基本解：最优解与基本解：最优解不一定是基本解，基本解也不一定是最优解。问题：最优解与基可行解？问题：最优解与基可行解？非可行解可行解基本可行解基本解线性规划的基本定理线性规划的基本定理定理定理1 若线性规划问题存在可行解，则问题的可行域是凸集。定理定理2 线性规划问题的基本可行解X对应线性规划问题可行域（凸集）的顶点。定理定
15、理3 若可行域有界，则线性规划问题一定最优解，且一定存在一个基本可行解是最优解。即线性规划的目标函数一定在可行域的顶点上达到最优。定理定理4 若目标函数在多个顶点达到最优，则顶点连线上也达到最优，有无穷多最优解。定理3,4描述了最优解在可行解集中的位置，若最优解唯一，则最优解只能在某一顶点上达到，若具有多重最优解，则最优解是某些顶点连线上取得，从而最优解是可行域的顶点或边界点，不可能是可行域的内点。若线性规划的可行域非空且有界，则一定有最优解；若可行解集无界，则线性规划可能有最优解，也可能没有最优解。定理3及4还给了我们一个启示，寻求最优解不是在无限个可行解中去找，而是在有限个基本可行解（顶点
16、）中去寻求。（五）单纯形法的原理（五）单纯形法的原理单纯形法的基本思路是：根据问题的标准形式，从可行域中的一个基本可行解（一个顶点）开始，转换到另一个基本可行解（顶点），并且使目标函数的值逐步增大；当目标函数达到最大值时，问题就得到了最优解。它是一种逐步逼近最优解的迭代方法。找出一个初始可行解找出一个初始可行解是否最优是否最优转移到另一个基本可行解转移到另一个基本可行解（使目标函数值逐步增大）（使目标函数值逐步增大）最优解最优解是是否否循循环环结束结束其步骤总结如下：其步骤总结如下：在用单纯形法求解线性规划问题时，应考虑的问题：1.建立初始基本可行解建立初始基本可行解2.最优性检验最优性检验3
17、.基本可行解的改进基本可行解的改进 1.1.建立初始基本可行解：建立初始基本可行解：在用单纯形法求解时，首先应将线性规划问题以标准形式表达、约束条件以典型方程组表示，确定初始基本可行解。初始基本可行解获取的步骤：1.将线性规划问题化为标准形式2.通过初等变换（行变换）将约束条件以典型方程组表示3.令非基变量等于零，得到基变量大于等于零的初始基本可行解。2.最优性检验最优性检验将上式代入目标函数式，整理后得 令(j=m+1，m+2，n)于是（2-6）典型方程组经过初等变换，得到一个基本可行解后，用非基变量表示基变量，约束方程化简为：（i=1，2，m）由于当j=1，2，m时，即 所以式2-6也可写
18、作 再令（j=1，2，n）为变量xj的检验检验数数 则 基本变量的检验检验数数为为0（1 1）最优解判别）最优解判别（2）无有限最优解判别）无有限最优解判别（3）无穷多最优解判别）无穷多最优解判别若X（0）为基本可行解且对一切j=1,2,n有0，则X（0）为最优解。若X（0）为基本可行解有一个0，且对一切i=1,2,m有ik0（ik为约束条件方程中的系数，k1，2，n）该线性规划问题无有限最优解（或称有无界解或无最优解）。若X（0）为基本可行解且对一切j=1,2,n有Cj0，存在某个非基本变量的检验数Cm+k=0，则线性规划有无穷多最优解应用向量的乘法可以把检验数的求法表示的更简明一些：设CB
19、表示基本变量在目标函数中的系数行向量，Pj表示变量xj在典型方程中的系数列向量，则：基本可行解的改进基本可行解的改进：若初始基本可行解X(0)不是最优解及不能判别无最优解时，需找一个新的基本可行解 1.进基变量的确定进基变量的确定 从最优解判别定理知道，当某个Cj0时，非基变量xj变为基变量不取零值可以使目标函数值增大，故我们要选基检验数大于0的非基变量换到基变量中去（称之为入基变量）。若有两个以上的Cj0，则为了使目标函数增加得更大些，一般选其中的Cj最大者的非基变量为入基变量。则对应的xk为进基变量。进基变量所在的列（k）称为枢列枢列。出基变量的确定出基变量的确定把已确定的入基变量在各约束
20、方程中的正的系数除以其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。这样在下一步迭代的矩阵变换中可以确保新得到的bj值都大于等于零。则基本变量为出基变量 出基变量所在的行（l）称为枢行枢行 枢行与枢列交点处的元素（lk）称为枢元枢元 单纯形法的计算步骤：找出初始基本可行解，建立初始单纯形表 检验对应于非基本变量的检验数 ，若对所有的 0（j1，2，n），则已得到最优解，计算最优值。否则，转入下一步。在所有 0中，若有一个 对应 的系数列向量，即对i1，2，m均有ik0，则此问题无有限最优解（或称有无界解或无最优解），停止计算。否则转入下一步。根据Max（0
21、），确定 为进基变量，再依据“最小比值规则”（）确定xl为出基变量。实施以枢元素为中心的初等变换，使约束方程组变为关于新的基本变量的典型方程组，得到新的单纯形表，重复第二步，一直到没有新的非基本变量可以改善目标函数为止。二、单纯形法的表格形式例例6现以本章第一节的例1来说明单纯形法的表上作业方法。解：引入两个松弛变量x3,x4，则标准形式为：s.t.CB cj302500bXBx1x2x3x40 x3241040200 x432013010302500Z=0表表2-3单纯形表求解例单纯形表求解例6（1）根据初始单纯形表可以看出：初始基本可行解是x10，x20，x340，x430此时目标函数值Z
22、（0 0）0此处初始基本可行解的含义是：当两种药物都不生产时，甲、乙两台机器的剩余可利用时间分别为40小时和30小时，此时的利润Z=0。解的最优性检验 检验数30（0 0）30=0（基本变量的检验数总等于零）由于0，0，所以初始基本可行解非最优解，。或 来代替基变量或需用非基变量25（0 0）25 25（0 0）25 迭代 由于，所以确定x1为进基变量 进一步求最小值：即从第二个方程中算出的商值最小，而第二个方程中的基本变量是x4，于是x4为出基变量。表中给第二个约束方程中x1的系数3加上方括号以突出其为枢元。CB cj302500bXBx1x2x3x40 x308/31-2/32015/20
23、 x1 12/301/31015050-10Z=300 表2-4 单纯形表求解例6（2）CB cj302500bXBx1x2x3x425x2013/8-1/415/230 x110-1/41/2500-15/8-35/4Z*=337.5表2-5 单纯形表求解例6（3）x15，x27.5，x30，x40即为最优解，最优值为Z*337.5 课堂练习：课堂练习：用单纯形法求解下列线性规划问题单纯形法求解线性规划问题的前提是：线性规划问题必须是标准形式，并且约束条件必须化为典型方程组。三、单纯形法的进一步讨论如果约束条件都是 的形式那么将每个约束条件的左边添加一个松弛变量即可化为标准形式，而且也得到了
24、典型方程组。（一）大（一）大M法法先将约束条件转化为标准形式，然后对不含基本变量的约束方程再添加一个非负变量，使方程组称为典型方程组的形式，我们称这种变量为人工变量人工变量。大大M法法：将人工变量记入目标函数中，并赋予一个极大的负系数，习惯上，这种系数记作M，其中M是极大的正数。这种通过引入人工变量和一个M值来求解线性规划问题的方法称为大M法（big M method）。如果约束条件含有“”的形式 例例7用大M法求解下列线性规划问题 解：解：引入松弛变量 和 ，将此线性规划问题化为标准形式为：加入一个加入一个人工人工变变量量CB cj3500-Mb xjXBx1x2x3x4x50 x31010
25、0440 x40201012-Mx5320011863+3M5+2M000Z=-18M3x11010040 x402010126-Mx502-3016305+2M-3-3M00Z=12-6M表2-6 大M法求解CB cj3500-Mb xjXBx1x2x3x4x53x110100440 x40031-1625x201-3/201/23009/20-5/2-MZ=273x1100-1/31/320 x30011/3-1/325x20101/206000-3/2-1-MZ*=36表2-6 大M法求解（二）单纯形法求解线性规划问题的几种特殊情况（二）单纯形法求解线性规划问题的几种特殊情况1.无可行解
26、无可行解 例如，使用大M法求解如下线性规划问题：将上述问题的约束条件中加入松弛变量、剩余变量和人工变量后得到：在第二次迭代时出现了如表2-7所示的情况 表2-7 CB Cj2030000MXB30011/10-3/100062010010030M00-1/10-7/10-11400-M0Z=780-4M表2-7最优解的值中 ，其最大的目标函数值是一个负无穷大的值。把最优解的值代入到约束方程，会发现第三个约束方程 =360且aik（i=1，2,m）则线性规划具有无界解退化基本可行解的判断退化基本可行解的判断:存在某个基变量为零的基本可行解。某医院24小时各时间段需要的护士人数如表2-11所示，护
27、士分别于2：00、6：00、10：00、14：00、18：00、22：00分六批上班，并要求必须连续工作8小时。试问：为满足每班所需要的护士数，医院至少应雇用多少名护士？请列出该问题的线性规划模型。时间段所需护士数2：006：00106：0010：001510：0014：002514：0018：002018：0022：001822：002：0012表2-11 医院各时段需要护士数第四节 应用举例一、人力资源分配问题 解：解：设表示x12：00开始上班的护土数；x2表示6：00开始上班的护土数；x3表示10：00开始上班的护土数；x4表示14：00开始上班的护土数；x5表示18：00开始上班的护
28、土数；x6表示22：00开始上班的护土数。则有 某卫生所配有医生、护士各1名。已知医生每天工作8小时，护士每天工作9小时。服务的项目是接生和做小手术。一次接生，医生要花0.5小时，护士同样要花0.5小时；一次小手术，医生要花1小时，护士要花1.5小时。对于该卫生所来说，每天容纳的手术的数量和接生的数量合计不能超过12次。假定一次小手术的收入为10元，一次接生的收入为4元。问怎样合理安排接生和手术的数量，使卫生所一天的收入最多？二、诊疗问题解：解：设每天手术数为x1，每天接生数为x2，则 使用单纯形法可求得最优解，即医生、护士每天手术3次，接生9次，这时可使卫生所的日收入最多，为66元（最优值）
29、。某制药企业生产I，II，III三种药品，每种药品均要经过A，B两道加工工序。设该厂有两种规格的设备能完成A工序，它们以A1，A2表示；有三种规格的设备能完成工序B，它们以B1，B2，B3表示。药品I可在工序A和B的各种规格的设备上加工。药品II可在工序A的任何一种规格的设备上加工，但完成B工序，只能在B1上加工。药品III只能在设备A2和B2上加工。已知在各种设备上加工的单件工时、各种设备的有效台时以及满负荷操作时的设备费用如表2-12所示。已知药品I，II，III的原料单价分别为2.5元，3.5元和5元。销售单价分别为12.5元、20元和28元。问如何制定最优的生产方案，可使该药厂的利润最
30、大？三、生产计划问题设备药品单件工时设备有效台时满负荷时的设备费用IIIIIIA1510 60003000A27 912100003210B16 8 40002500B2411 70007830B37 40002000表2-12 设备有效台时，药品单件工时表 解：解：设xijk表示药品i在工序j（工序A用1表示，工序B用2表示）的设备k上加工的数量（如x123表示药品I在工序B设备B3上加工的数量）。约束条件1：设备台时限制 药品在A、B两道工序上加工的数量相等 约束条件2：利润的计算公式如下：利润=（销售单价原料单价）该药品数（每台时的设备费用该设备实际使用的台时数）整理后得目标函数 根据计
31、算机计算，此线性规划问题的最优值Z11465.15（元）最优解为：某医院有一批长度为15分米的胶皮管原料，可以分别做成输液管、止血带和听诊器胶管。输液管、止血带和听诊器胶管所需要的长度分别为5.7分米、4.2分米和3.1分米，且各需要100根。试问应如何安排截法，使所用的胶皮管原料的总根数最少?解：为了找一个省料的套裁方案，必须先设计出较好的几个下料方案。这里首先要求每个方案下料后的料头较短（料头至少要小于2分米）；其次要求这些方案的总体能裁出输液管、止血带和听诊器胶管各100根，这就要求每个方案有着不同的裁减比例。为此我们设计如表2-13所示的截取方案。四、套裁下料问题方案12345输液管根
32、数（5.7分米）21100止血带根数（4.2分米）02021听诊器根数（3.1分米）10323总长（分米）14.514.11514.613.5料头（分米）0.50.900.41.5表2-13 胶皮管截取方案 令 表示第j种截法所用原材料的根数，则可得到如下数学模型：某制药厂用三种原料1，2，3混合调配出三种不同规格的注射药品甲、乙、丙。药品的规格要求、单价、每天供应的原料数量及原料单价如表2-14和表2-15所示。问该制药厂应如何安排生产，才能获利最大？五、配料问题药品名称规格要求单价（千元/公斤）甲原料1含量不少于50%原料2含量不超过25%50乙原料1不少于25%原料2不超过50%35丙不限25表2-14 药品规格要求原料名称每天最多供应量（公斤）单价（千元/公斤）11006521002536035表2-15 原料供应量解：解：设 表示第i种药品（分别用1，2，3表示药品甲、乙、丙）中原材料j的含量，则线性规划模型如下：简化后为：s.t.TheEndofChapter2