第一节线性规划问题及其数学模型第二节线性规划问题

《第一节线性规划问题及其数学模型第二节线性规划问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、*第一节  线性规划问题及其数学模型*第二节线性规划问题的图解法*第三节单纯形法*第四节线性规划的对偶问题*第五节线性规划在卫生管理中的应用第二章线性规划→第四节线性规划的对偶问题*线性规划对偶问题的概念*线性规划的对偶单纯形法*线性规划的灵敏度分析1.对偶单纯形法迭代的要点2.对偶单纯形法的优点及用途3.对偶单纯形法的适用范围对偶单纯形法1．确定换出变量：选择最负的基本变量为换出变量。2．确定换入变量：用换出变量那一行具有负值的系数分别去除同列的检验数，取最小商数所对应的变量为换入变量；如果换出变量那一行无负值的系数，则原问题无可行解。3．初等行运算:使枢元变为1,其他枢列位置变为

2、0。4．最优解检查。如果所得的基本解都是非负的，则此解即为最优解。如果基本解中还有负的数值，则重复第一步继续迭代，直到所有基变量为非负数为止。对偶单纯形法迭代的要点返回1．初始解可以是非可行解，当检验数都是小于等于零时，就可以进行基变换，这样就避免了增加人工变量，使运算简化。2．对变量较少，而约束条件很多的线性规化问题，可先将其变为对偶问题，再用对偶单纯形法求解，简化计算。3．用于灵敏度分析。对偶单纯形法的优点及用途返回①单纯形表检验数行全部非正（对偶可行）②变量取值可有负数（非可行解）对偶单纯形法在什么情况下使用注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表

3、。应用前提：有一个基，其对应的基满足:适合于解如下形式的线性规划问题对偶单纯形法的适用范围返回灵敏度分析（一）价值系数c发生变化：1.非基变量的系数发生变化2.基变量的系数发生变化3.若基变量的系数和非基变量的系数都变化（二）右端项b发生变化返回第三章特殊的线性规划第一节运输问题一、运输问题的数学模型和特征二、用表上作业法求解运输问题三、其它运输问题的处理第二节0-1规划问题第三节指派问题管理计划组织生产1生产2生产3销售1销售4销售2销售3原材料1原材料2原材料3原材料4物流一、运输问题的数学模型和特征一、运输问题的数学模型和特征例1：某制药公司在全国设有三个生产基地，其中某品种药

4、的日产量为：A1厂700箱，A2厂400箱，A3厂900箱。这些生产基地每天将这些药分别运往四个地区的经销部门，各经销部门每天的需求量为：B1部门300箱，B2部门600箱，B3部门500箱，B4部门600箱。已知从每个生产基地到各销售部门每箱药品的运价如表所示，问该制药公司应如何调运，使在满足各销售部门需要的情况下，总的运输费用最少？表4-1各生产基地到各销售部门每箱药品的运费生产基地销售部门B1B2B3B4A10.31.10.31.0A20.10.90.20.8A30.70.41.00.5（金额单位：元）表4-2运输表共有m+n个变量共有m+n个变量m+n个约束方程产销平衡运输问

5、题数学模型的特点（1）约束条件系数矩阵中元素等于0或1；（2）约束条件系数矩阵的每一列有两个非0元素，与每个变量在前m个约束方程和后n个约束方程中各出现一次相对应。对于产销平衡的运输问题，还有以下两个特点：（3）所有的结构约束方程都是等式；（4）各产地的产量之和等于各销地的销量之和。例1问题的运输表设X=（xij）为运输问题的一个解，则要求每步得到的X都必须是基本可行解，这就要求：（1）X必须满足模型中的所有约束条件；（2）基变量对应的约束方程组的系数列向量线性无关；（3）解中非0变量xij的个数不能多于（m+n-1）个；（4）基变量的个数在迭代过程中应该保持为（m+n-1）个。例1

6、问题的一个基本可行解（1）基变量有m+n-1个；（2）一定有最优解；（3）如果ai和bj都是整数，则一定有整数最优解。产销平衡的运输问题，有以下3条结论：返回二、用表上作业法求解运输问题(一)初始基本可行解的求法1．最小元素法最小元素0.1产量400和销量300最小者最小元素0.2最小元素0.3最小元素0.4最小元素0.50.30.10.20.4２．西北角法西北角（二）解的最优性检验１．闭回路法11=c11-c21+c23-c13=0.3-0.1+0.2-0.3=0.131=c31-c21+c23-c13+c14-c34=0.7-0.1+0.2-0.3+1.0-0.5=1.0找出

7、每一个空格(非基变量)的闭回路(只有一个顶点为空格，其他顶点均为填有数字的格)。12=c12-c32+c34-c14=1.1-0.4+0.5-1.0=0.222=c22-c32+c34-c14+c13-c23=0.9-0.4+0.5-1.0+0.3-0.2=0.124=c24-c14+c13-c23=0.8-1.0+0.3-0.2=-0.133=c33-c34+c14-c13=1.0-0.5+1.0-0.3=1.2注意：在运输问题中通常目标函数是求