第三章单纯形

第三章单纯形第1页，课件共45页，创作于2023年2月它的一般形式为：其中，,，是已知数，是待决策的变量。一、线性规划问题的一般形式第2页，课件共45页，创作于2023年2月第3页，课件共45页，创作于2023年2月一般情况下m<n,m,n为正整数,分别表示约束条件的个数和决策变量的个数,称为约束条件(Subjectto)。

称为变量的非负约束条件。其余的变量可取正值、负值、或零值，称这样的变量为符号无限制变量或自由变量。

线性规划模型的特征是：一组决策变量，一组约束条件。一个目标函数。目标函数和约束条件都是线性的。

第4页，课件共45页，创作于2023年2月由前面一般形式可知,线性规划问题可能有各种不同的形式。目标函数有实现最大化也有实现最小化的;约束条件可以是“”形式、“”形式不等式,有的是等式

决策变量有时有非负限制有时没有。这种多样性给讨论问题代来了不便。为了便于今后讨论，我们就要规定线性规划问题的标准型第5页，课件共45页，创作于2023年2月二、线性规划问题的标准行式是什么？

如何将一个LP问题的一般形式转换为

标准形式？

(1)、这里规定的标准形式为：

第6页，课件共45页，创作于2023年2月

这里我们假设bi

0(i=1,2,···,m),否则两端同时乘以“-1”。第7页，课件共45页，创作于2023年2月简记为：第8页，课件共45页，创作于2023年2月用矩阵表示为：第9页，课件共45页，创作于2023年2月用列向量表示为：第10页，课件共45页，创作于2023年2月（2）为了把一般形式的LP变换为标准形式，必须消除其不等式约束和符号无限制变量。

目标函数的转换

约束条件的转换

变量的非负约束的转换

任何形式的线性规划数学模型都可以转换成标准型的线性规划第11页，课件共45页，创作于2023年2月例4:试将如下线性规划问题化成标准型解：令x3=x4-x5,x4,x5

0,(1)式左端加上非负松弛变量x6,(2)式左端减去非负剩余变量x7,则可将上述线性规划问题化成如下的标准型:第12页，课件共45页，创作于2023年2月第13页，课件共45页，创作于2023年2月三、什么是可行解、可行域，可行域的几何结构？

满足所有约束条件的决策变量，称为可行解或可行点(feasiblepoint)。使目标函数值最大的可行解称为最优解所有可行点组成的集合称为可行域（feasibleregion），记为D.给定一个LP问题可行域D,下列三种情况必居其一第14页，课件共45页，创作于2023年2月

D=ø称该问题无解或不可行。

Dø且可行域有界。则线性规划问题一定存在最优解。这时最优解唯一，也可能有无穷多。

Dø，且可行域为无界，则线性规划问题或者有最优解（唯一或无穷多）也可能没有有限的最优解。

当可行域非空时，可行域的几何结构为(多面)凸集

第15页，课件共45页，创作于2023年2月四、基本解、基本可行解

(basicsolution、basicfeasiblesolution)秩（A）=m，则矩阵A中存在一个m阶满秩子方阵B。称B矩阵为线性规划问题的一个基。第16页，课件共45页，创作于2023年2月第17页，课件共45页，创作于2023年2月第18页，课件共45页，创作于2023年2月解之间的关系可行解：满足约束条件 最优解：满足约束条件，同时使目标函数值最优。基础解：满足且非零分量的数目不大于方程的个数m。 基可行解：是基础解又是可行解。基最优解：满足约束条件，且无非零分量，或非零分量对应的列向量现性无关，同时使目标函数值最优。

第19页，课件共45页，创作于2023年2月五、LP问题的几何意义（单纯形表的数学原理）

若线性规划问题存在可行域，则其可行域D是凸集线性规划问题的可行解为基可行解的充要条件是的正分量所对应的系数列向量线性无关。X是基本可行解的充分必要条件是X是可行域D的顶点一个标准的LP问题，若有可行解，则至少有一个基本可行解一个标准的LP问题，若有有限的最优值，则一定存在一个基本可行解是最优解。第20页，课件共45页，创作于2023年2月若线性规划问题存在可行域，则其可行域D是凸集第21页，课件共45页，创作于2023年2月线性规划问题的可行解X为基可行解的充要条件是X的正分量所对应的系数列向量线性无关。第22页，课件共45页，创作于2023年2月X是基本可行解的充分必要条件是X是可行域D的顶点

第23页，课件共45页，创作于2023年2月第24页，课件共45页，创作于2023年2月由以上定理可知，最优解一定在某一基本可行解处达到。因此单纯形法的基本思想是：先找一个基本可行解，然后判断它是否为最优解，如不是，就找一个更好的基本可行解，再进行判断，如此迭代进行，直到找到最优解或者判断该问题无界。

六、单纯形法(Simplexmethod)第25页，课件共45页，创作于2023年2月

1．单纯形表

为了计算的方便，我们可以将单纯形法的全部计算过程在一个类似增广矩阵的数表上进行，这种表格称单纯形表，不同的教材设计表格稍有不同，这里设计如下：第26页，课件共45页，创作于2023年2月2．

单纯形方法步骤

Step1转换一般的LP模型为标准型。Step2找一个初始可行基。Step3计算单纯形表中的各矩阵。Step4构造单纯形表。Step5判断最优解，是，则结束。否则，转入下一步。Step6换基迭代，返回Step5。第27页，课件共45页，创作于2023年2月

如何得到第一个基本可行解？

为了得到初始基本可行解，要首先找到初始基本可行基，设B为约束矩阵的一个m阶子式，如果B非奇异，则矩阵B是一个基，

进一步，若，那么B是初始基本可行基。

就是初始基本可行解。找初始基本可行基的方法如下

1．观察法与试验法。2.大M法。3.两阶段法

第28页，课件共45页，创作于2023年2月如何判断基本可行解是最优解？

对线性规划问题的求解结果可能出现唯一最优解、无穷多最优解、无界解和无可行解四种情况，

第29页，课件共45页，创作于2023年2月第30页，课件共45页，创作于2023年2月第31页，课件共45页，创作于2023年2月

找入基变量找出基变量定轴心项作行变换交换变量

如何进行换基迭代

第32页，课件共45页，创作于2023年2月——掌握线性规划问题的数学原理及代数的单纯形解法是学习LP的最高境界。

——掌握这一方法对于以后的学习大有裨益，希望同学们发扬十二分的耐心和钻研精神。第33页，课件共45页，创作于2023年2月例题、用单纯形法求解第34页，课件共45页，创作于2023年2月１．化为满秩标准形第35页，课件共45页，创作于2023年2月2、写出初始单纯形表

第36页，课件共45页，创作于2023年2月第37页，课件共45页，创作于2023年2月3、判断基本可行解是最优解

由于检验数有正数，且对应的列向量不全为负，故进行换基迭代，第38页，课件共45页，创作于2023年2月

4、换基迭代

选上表中的为轴心项

第39页，课件共45页，创作于2023年2月5、判断、由于检验数有正数且对应的列向量不全为负，故进行换基迭代，选上表中的为轴心项

第40页，课件共45页，创作于2023年2月由单纯形表得一基最优解，

由于有非基变量的检验数为零，则此线性规划有无穷解。选上表中的为轴心项.

第41页，课件共45页，创作于2023年2月

原线性规划所有最优解为：

由此表的另一最优解所有最优解为：第42页，课件共45页，创作于2023年2月如何用QM软件求解LP问题