第一章 线性规划及3.ppt

第一章线性规划及单纯形法,LP(linearprogramming)的基本概念LP是在有限资源的条件下，合理分配和利用资源，以期取得最佳的经济效益的优化方法。基本特点运筹学中应用最广泛的方法之一运筹学的最基本的方法之一，网络分析、整数规划、目标规划都是以线性规划为基础的解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大,第一章线性规划及单纯形法,研究对象如何合理使用有限的人力，物力和资金，使得收到最好的经济效益。某项任务确定后，如何合理使用人力，物力和资金，使成本最低。,第一节线性规划问题及其数学模型,问题的提出数学模型模型的标准形式问题的解,一、问题的提出,例1：某工厂在计划期内安排生产、两种产品，已知生产单位产品所需的设备台时、A、B两种原材料的消耗及两种产品每件可获利润见如下表所示：问如何安排计划使该工厂获利最多？,二、数学模型,分析步骤：1、确定决策变量：设生产产品Ix1kg，产品IIx2kg2、确定目标函数：MaxZ=2x1+3x23、确定约束条件：设备约束x1+2x28原材料A约束4x116原材料B约束4x212变量取值约束x10，x20,二、数学模型,得数学模型：MaxZ=2x1+3x2x1+2x284x1164x212x10，x20,二、数学模型,以上例子从数学上来讲，它们的共同特征是：（1）每个问题都用一组变量，或称决策变量(x1,x2,xn)表示某一方案，这组未知数的值就代表一个具体的方案，通常可根据决策变量所代表的事物特点，可对变量的取值加以约束，如非负约束。（2）都有一个目标要求，并且这个目标可表示为这组决策变量的线性函数(称为目标函数)，按研究问题的不同，要求目标函数实现最大化或最小化。,二、数学模型,（3）存在一定的限制条件(称为约束条件),这些条件都可以用关于决策变量的一组线性等式或不等式来表示。线性规划数学模型三要素：决策变量约束条件目标函数,二、数学模型,线性规划问题数学模型一般形式为：,简写形式：,二、数学模型,向量形式：矩阵和向量形式：,三、标准形式,标准型的主要特征：目标最大；约束等式；右端非负；变量非负。,三、标准形式,标准化方法：1目标最小化minZ等价于max(-Z)maxZ=-cjxj2右端项为负方程两端乘以-13约束条件为不等式加松弛变量、减剩余变量4变量非正做变换或,三、标准形式,练习：,答案：,基于线性规划问题：即线性规划标准形式。,四、解的概念,四、解的概念,可行解:满足约束条件(1.6b)，(1.6c)解X=(x1,x2,xn)T称为线性规划问题的可行解；所有可行解的集合称为可行域。最优解:满足条件(1.6a)的可行解称为线性规划问题的最优解。基:假设A是约束方程组的系数矩阵，其秩为m，B是矩阵A中由m列构成的满秩子矩阵(B的行列式的值不为0），则称B是线性规划问题的一个基。矩阵B是由m个线性无关的列向量组成，不失一般性，可假设：,称Pj(j=1，2，m)为基向量，与基向量Pj相对应的变量xj(j=1,2，m)为基变量，否则称为非基变量。,四、解的概念,基解：令所有非基变量等于零,求得的解称为基解。基解个数=基的个数,且非0分量的数目不大于方程个数m。基可行解：满足非负条件(1.8)的基解称为基可行解。由此可见,基可行解的非0分量的数目不大于m,并且都是非负的。一般地讲,基可行解的数目要小于基解的数目,至多相等。可行基：对应于基可行解的基称为可行基。,四、解的概念,以上提到的几种解的概念,可用下图来表示：,四、解的概念,第二节图解法,线性规划的图解法就是用几何作图的方法分析求出其最优解的过程。图解法简单直观，有助于了解线性规划问题求解的基本原理。适用对象：仅有两个变量的LP问题。,第二节图解法,求解思路：先将约束条件加以图解，求得满足约束条件的解的集合（即可行域），然后结合目标函数的要求从可行域中找出最优解。有关概念：（1）满足约束条件的变量的值，称为可行解。（2）全部可行解的集合，称为可行域。（3）使目标函数取得最优值的可行解，称为最优解。,一、图解法的步骤,例：,MaxZ=2x1+3x2x1+2x284x1164x212x10，x20,一、图解法的步骤,第一步：建立平面直角坐标系。（标出坐标原点,坐标轴的指向和单位长度。）第二步：图示约束条件，找出可行域。第三步：图示目标函数等值线。第四步：平移目标函数等值线，确定最优解。,4x1=16,x1+2x2=8,4x2=12,A(4,2),D,二、解的情况,唯一解无穷多解例无界解例无可行解（课本）,前两种情形为有最优解后两种情形为无最优解,三、启示,解的情况,三、启示,可行域存在，是一个凸集。若最优解存在，则一定是可行域的顶点或边界。求解思路设想：首先找出可行域的任一顶点，然后通过顶点对应的目标值的比较来求解最优解。,二、基本定理定理1若线性规划问题存在可行解，则该问题的可行域是凸集。引理线性规划问题的可行解为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的。定理2线性规划问题的基可行解X对应线性规划问题可行域(凸集)的顶点。定理3若线性规划问题有最优解，一定存在一个基可行解是最优解。,第三节单纯形法原理,三、单纯形法迭代原理,1、引例以例1来讨论线性规划的求解。先化为标准型式：MaxZ=2x1+3x2+0 x3+0 x4+0 x5x1+2x2+x3=84x1+x4=164x2+x5=12xj0，j=1,2,5,1、引例(续)则基变量为（x3,x4,x5），非基变量为(x1,x2)。基变量用非基变量表示得：x3=8-x1-2x2x4=16-4x1(1.1)x5=12-4x2Z=2x1+3x2+0 x3+0 x4+0 x5令非基变量等0求得基变量的值，即可得初始基可行解X0=（0，0，8，16，12）T，Z=0。,1、引例(续)从目标函数Z=2x1+3x2+0 x3+0 x4+0 x5可知：非基变量x1和x2的系数均为正数，生产哪种产品都会增加利润。因为x2的系数大于x1的系数，即生产单位产品比产品利润更高一些，故应优先多生产产品。当将x2定为换入变量后，为确保基可行解，必须从非基变量x3,x4,x5中换出一个，并保证x3,x4,x5都是非负。,1、引例(续)因x1=0，由(1.1)得到：x3=8-2x2x24x4=16x5=12-4x2x23即x2=min（8/2,12/4）=3，x5为换出变量。将x2与x5对换，得到x3+2x2=8-x1x4=16-4x14x2=12-x5用消元法得,1、引例(续)x3=2-x1+1/2x5x4=16-4x1(1.2)x2=3-1/4x5Z=9+2x1+0 x2+0 x3+0 x4-3/4x5求得新基可行解X1=（0,3,2,16,0）T，Z=9。从目标函数表达式中可以看出，非基变量x1系数为正，说明目标函数值还可以增大，X1不是最优解。令x1为换入变量，同理由以下方法确定换出变量：x3=2-x1x12x4=16-4x1x14x2=3,1、引例(续)即x1=min（2/1,16/4,）=2，x3为换出变量。将x1与x3对换，得到x1=2-x3+1/2x54x1+x4=16x2=3-1/4x5用消元法求得：x1=2-x3+1/2x5x4=8+4x3-2x5(1.3)x2=3-1/4x5Z=13+0 x1+0 x2-2x3+0 x4+1/4x5,1、引例(续)求得新基可行解X2=（2,3,0,8,0）T，Z=13。由于目标函数中非基变量x5系数为正，说明目标函数值还可以增大，X2不是最优解。再用上述方法继续迭代，得到另一个基可行解X3=（4,2,0,0,4）T,此时目标函数为：Z=14+0 x1+0 x2-3/2x3-1/8x4+0 x5。当前非基变量系数均为负，解最优。即当产品生产4件，产品生产2件，工厂才能得到最大利润14。,2、单纯形法迭代原理确定初始基可行解找单位矩阵作为初始基，求得初始基可行解。最优性检验及解的判别经过迭代后，将其代入目标函数,2、单纯形法迭代原理（续）,2、单纯形法迭代原理（续）最优性判别定理：当所有j0时，则当前基可行解为最优解。此时，若存在某非基变量xj有j=0，则该线性规划问题有无穷多最优解；反之，当所有非基变量的j0，又Pj0，表明线性规划问题有无界解。,2、单纯形法迭代原理（续）基变换：（a）确定换入变量设k=maxj|j0,xk为换入变量。（b）确定换出变量则xl为换出变量。（c）变量互换，用初等行变换方法求新的基可行解。,第四节单纯形法计算步骤,一、单纯形表单纯形表，是对上节讨论的方法步骤进行具体化、规范化、表格化。,第四节单纯形法计算步骤,二、计算步骤找到初始可行基，建立初始单纯形表。最优性检验。计算检验数，若所有j0，则问题已得到最优解，停止计算，否则转入下步。若某k0，且Pk0，则此问题是无界解，停止计算，否则转入下步。基变换。根据k=maxj|j0原则，确定xk为换入变量，再按确定xl为换出变量。以alk为主元素进行迭代，把xk所对应的列向量变为单位列向量，即alk变为1，同列中其它元素变为0，转第步。,第四节单纯形法计算步骤,例.用单纯形法求解例1。例1模型解：先将其化为标准型：MaxZ=2x1+3x2+0 x3+0 x4+0 x5x1+2x2+x3=84x1+x4=164x2+x5=12xj0，j=1,2,5取松弛变量x3、x4、x5为初始基变量,其对应的单位矩阵为基,得初始基可行解X0=（0，0，8，16，12）T，以此列出初始单纯形表。,第四节单纯形法计算步骤,0,1,0,0,x5,0,0,0,3,2,j,0,0,4,0,12,x5,0,1,0,0,4,16,x4,0,0,1,2,1,8,x3,0,x4,x3,x2,x1,b,XB,CB,0,0,3,2,cj,-3/4,0,0,0,2,j,1/4,0,0,1,0,3,x2,3,0,1,0,0,4,16,x4,0,-1/2,0,1,0,1,2,x3,0,x5,x4,x3,x2,x1,b,XB,CB,0,0,0,3,2,cj,0,-1/8,-1.5,0,0,j,0,-1/8,1/2,1,0,2,x2,3,1,1/2,-2,0,0,4,x5,0,0,1/4,0,0,1,4,x1,2,1/4,0,-2,0,0,j,1/4,0,0,1,0,3,x2,3,2,1,-4,0,0,8,x4,0,-1/2,0,1,0,1,2,x1,2,第四节单纯形法计算步骤,最后一行所有的检验数都已0,于是得到最优解：X*=(4,2,0,0,4)T,最优目标函数值为：Z*=14。,第五节单纯形算法的进一步讨论,一、人工变量法用单纯形法解题时，需要有一个单位阵作为初始基。当约束条件都是“”时，加入松弛变量就形成了初始基。但实际存在“”或“”型的约束，没有现成的单位矩阵。采用人造基的办法：人工构造单位矩阵在没有单位列向量的等式约束中加入人工变量，从而得到一个初始基。人工变量是人为加进的，只有它等于0时，约束条件才是它本来的意义。,第五节单纯形算法的进一步讨论,1、大M法假定人工变量在目标函数中的价值系数为(-M)(对于极大化目标),M为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。2、两阶段法第一阶段是先求出基可行解(或判断出原线性规划问题无解),第二阶段利用已求出的初始基可行解来求最优解。,第五节单纯形算法的进一步讨论,二、几个问题1.极小化问题解的最优性判别：检验数的判别由所有j0即为最优，变为所有j0为最优。2.退化解的情形：有两个以上值相等。3.无可行解的判别：当所有j0时，基变量中仍含有非零的人工变量，这就表示原问题无可行解。,第六节应用,人力资源分配问题例某昼夜服务的工交公交线路每天各时间段内所需司机和乘务人员数如下：,设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务员？解：设xi表示第i班次时开始上班的司机和乘务人员数，则minZ=x1+x2+x3+x4+x5+x6x6+x160 x1+x270 x2+x360 x3+x450 x4+x520 x5+x630 xi0,i=1,2,6,投资问题某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。问：应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？,解：设xij(i=1-5，j=1-4)表示第i年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的数学模型：Maxz=1.1x51+1.25x42+1.4x33+1.55x24x11+x12=200 x21+x22+x24=1.1x11x