线性规划问题的基本理论ppt课件.ppt

《线性规划问题的基本理论ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章第2节线性规划问题的基本理论一、线性规划问题的标准化二、线性规划问题的解三、线性规划问题的几何意义一、线性规划问题的标准化一般形式目标函数：Max（Min）z=c1x1+c2x2+…+cnxn约束条件：a11x1+a12x2+…+a1nxn≤（=,≥）b1a21x1+a22x2+…+a2nxn≤（=,≥）b2…………am1x1+am2x2+…+amnxn≤（=,≥）bm决策变量：x1，x2，…，xn≥(≤)0标准形式目标函数：Maxz=c1x1+c2x2+…+cnxn约束条件：a11x1+a12x2+…+a1nxn=b1

2、a21x1+a22x2+…+a2nxn=b2…………am1x1+am2x2+…+amnxn=bm决策变量：bi≥0x1，x2，…，xn≥0一般型和标准型的区别可以看出，线性规划的标准形式有如下四个特点：目标最大化；约束为等式；决策变量均非负；右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:1、极小化目标函数的问题：设目标函数为Minf=c1x1+c2x2+…+cnxn(可以)令z＝-f，则该极小化问题与下面的极大化问题有相同的最优解，即Maxz=-c1x1-c2x2-…-cnxn但必须

3、注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即Minf＝-Maxz2、约束条件不是等式的问题：设约束条件为ai1x1+ai2x2+…+ainxn≤bi可以引进一个新的变量s，使它等于约束右边与左边之差（一般称S为松弛变量）s=bi–(ai1x1+ai2x2+…+ainxn)显然，s也具有非负约束，即s≥0，这时新的约束条件成为ai1x1+ai2x2+…+ainxn+s=bi当约束条件为ai1x1+ai2x2+…+ainxn≥bi时，类似地令s=(ai1x1+ai2x2+…+ainxn)-bi显然

4、，s也具有非负约束，即s≥0，这时新的约束条件成为ai1x1+ai2x2+…+ainxn-s=bi称S为剩余变量。不等式情况下：当≤，引入松弛变量s当≥，引入剩余变量s松弛变量：需要补充的资源剩余变量：没有使用的资源如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。3、右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如bi<0，则把该等式约束两端同时乘以-1，得到：-ai1x1-ai2x2-…-ainxn=-bi。4、决策变量不定：当Xi<0，令

5、Xi`=-Xi，则Xi``>o当某一个变量xj没有非负约束时，可以令xj=xj’-xj”其中xj’≥0，xj”≥0即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj’和xj”的大小。例：将以下线性规划问题转化为标准形式Minf=2x1-3x2+4x3s.t.3x1+4x2-5x3≤62x1+x3≥8x1+x2+x3=-9x1,x2,x3≥0解：首先,将目标函数转换成极大化：令z=-f=-2x1+3x2-4x3其次考虑约束，有2个不等式约束，引进松弛变量x4，和剩余变量x5≥0。第三个约束条件的右端值为负，

6、在等式两边同时乘-1。通过以上变换，可以得到以下标准形式的线性规划问题：Maxz=-2x1+3x2-4x3s.t.3x1+4x2-5x3+x4=62x1+x3-x5=8-x1-x2-x3=9x1,x2,x3,x4,x5≥0练习：P24习题3（1）和（2）作业：P24习题3（3）二、线性规划问题的解1、解的情况2、几个重要的解概念1、解的情况（1）存在有限最优解：a）唯一最优解b）无穷多个最优解（2）不存在最优解a）无有限最优解（无界解）b）无可行解（可行域空）判断题：线性规划问题无有限最优解的充要条件是可行域为空？2、几个重要

7、的解概念（1）可行解、可行域、最优解、最优值（2）基、基本解（3）基本可行解（基可行解）（4）可行基（1）可行解、可行域、最优解、最优值满足约束条件(1-2)、(1-3)式的解X=(x1,x2，…，xn)T，称为线性规划问题的可行解，其中使目标函数达到最大值的可行解称为最优解。由可行解组成的集合就是可行域（满足约束条件不等式所有点组成的集合），将最优解代目标函数得到的函数值就是最优值。例：Maxz=1500x1+2500x2s.t.3x1+2x2≤652x1+x2≤403x2≤75x1,x2≥0（2）基、基本解设B为A中的一个

8、基，令Ax=b，中所有的非基变量（n-m个）为0，得出的解x，称为是B的基本解。x1x2x3x4x5bi321006521010400300175P1P2P3P4P5A=（P1，P2，P3，P4，P5）B=（P1，P2，P3），基变量（x3x4x5）非基变量（x1x2），B的