第一章线性规划(LinearProgramming)第一章线性规划线性规划问题的数学模型线性规划问题的数学模型线性规划问题的数学模型线性规划问题的数学模型线性规划问题的数学模型线性规划问题的数学模型线性规划问题的数学模型线性规划问题的数学模型线性规划问题的数学模型线性规划问题的数学模型线性规划问题的数学模型线性规划问题的数学模型线性规划问题的数学模型线性规划问题的数学模型线性规划问题的数学模型线性规划问题的数学模型线性规划问题的数学模型线性规划问题的数学模型线性规划问题的数学模型线性规划问题的数学模型线性规划问题的数学模型图解法图解法的步骤图解法图解法（唯一解）图解法（无穷多解）目标函数求极小图解法(无界解)x1图解法单纯形法基本原理单纯形法基本原理单纯形法的计算步骤案例：理解单纯性法的原理模型的标准型为：解：约束方程组的系数矩阵为：是线性独立的，（构成矩阵的秩为3）对应于B的变量X3，X4，X5为基变量，而X1，X2为非基变量。从式（1）中可以得到令非基变量x1，x2=0，得到Z=0，这时得到一个初始基可行解为同时，还要确定原基变量中有一个要换出来成为非基变量，方法如下。现分析式（2），将X2定为入基变量后，必须从X3，X4，X5中还出一个，并保证其余变量非负，x3，x4，x5>=0.则当x1=0（不生产第一种产品），x2入基时，由式（2）得到：从式（3）中知：只有选择x2=min（4/2，—，6/4）=3/2时，才能使式（2-10）成立。而当x2=3/2时，原来的基变量x5=0，x3>0,x4>0,这就决定了用x2去替代x5（以后将这一规则称为规则）为了求得以x3，x4，x2为基变量的一个基可行解和进一步分析问题，需将式（2）中x2的位置与x5的位置对换，得到：用高斯消去法，将式（4）中x2的系数列向量变换为单位列向量。其运算步骤为：(3)’=(3)/4;(1)’=(1)–2×(3)’;(2)’=(2),将结果仍按原顺序排列，得：再将式（5）代入目标函数，得到：令非基变量X1=X5=0，得到Z=9/2,并得到另一个基可行解X(1)X(1)=(0,3/2,1,8,0)T从目标函数表达式（2-13）中可以看出，非基变量X1的系数是正的，说明目标函数还可以增大，X(1)不一定是最优解。于是再用上述方法，确定换入、换出变量，继续迭代，得到另一个基本可行解X(2)X(2)=（1,3/2,0,4,0)T再经过一次迭代，再得到一个基本可行解X(3)为：X(3)=（2,1,0,0,2）T而这时的目标函数的表达式为：再分析式（6），可知所有非基变量X3，X4的系数都是负数，所以当X3=X4=0时，目标函数达到最大值，所以X(3)是最优解，即x1=2，x2=1单纯形法的本质：在可行域顶点寻优单纯形法的计算步骤单纯形法的具体步骤当所有约束条件均为“≤”形式的不等式时，利用化标准型的方法，在每个约束条件的左端加上一个松弛变量，这些松弛变量的系数矩阵即为单位矩阵。对于约束条件为“≥”或“=”的情况，需用人工变量法。关于人工变量法将在后面介绍。式（）中，为基变量，其对应的变量为基变量，模型中的其它变量为非基变量。令所有非基变量等于0，即可得到一个解：因为有b≥0，所有满足非负条件，为基可行解。考虑：怎么得到初始可行解对于最大化问题，如果表中所有非基变量检验数<0，则表中的基可行解就是问题的最优解，计算停止。否则转入下一步。对于求最大化问题，若>0,j=m+1,…,n中，若有某个检验数对应的决策变量xk的系数列向量Pk≤0，则此问题无最优解，停止计算；否则转入下一步。（3）进行基变换通过上式可选定XL为换出变量。（当有一个以上的变量可以换出时，可选择下标较大者）。称alk为主元素，它所在的行为主元行，它所在的列为主元列。（4）换基迭代以alk为主元素进行迭代（利用高斯消去法——行变换），把Xk对应的列向量换基迭代中的具体计算方法：补充说明：为什么选检验数最大的变量入基对于一般的线性规划问题，经过迭代后，相应的解可以表示为：带入目标函数：于是：单纯形法计算步骤的示例约束方程组的系数矩阵：其中，（P3，P4）线性独立，且组成单位矩阵，所以构成该规划问题的一个基对应于B的变量x3，x4为基变量，而x1，x2而非基变量。根据原约束条件可得：2）初始单纯形表。在上表中，顶行cj是目标函数中各变量的价值系数；cB为初始基变量的价值系数，她们都为0；检验数行各非基变量的检验数分别为：取最大的检验数对应的变量入基，即X2入基根据规则，确定出基变量，计算得：因为10对应X4这一行，所以X4为换出变量，X2所在列和X4所在行的交叉元素为a22，即“3”为主元素。以3为主