现代物流运筹学 沈家骅 24320第2章线性规划单纯形法

《现代物流运筹学 沈家骅 24320第2章线性规划单纯形法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章线性规划单纯形法学习目标用单纯形法等进行求解，学习对偶问题及实际案例，使学生学会把实际问题归结为线性规划问题来进行优化，并能用一些常用的方法进行求解，从而培养和提高学生分析问题、解决实际问题的能力。培养优化思想，并能用一定的数学方法实现优化。线性规划问题的标准型2.1改进的单纯形法和对偶问题2.2线性规划问题的应用案例2.3单纯形法的原理2.4线性规划问题的Excel处理2.52.1线性规划问题的标准型•由上一章可知，线性规划模型有各种不同的形式；即目标函数可以求极大值，也可以求极小值；约束条件可以是等式也可以是不等式，

2、不等号可以是“≤”也可以是“≥”；决策变量一般是非负的，但在理论模型中可能会允许在区间（−∞，+∞）内取值。•为适应通用的代数求解方法，将不同形式的线性规划模型转化为统一的标准形式是十分必要的。•线性规划问题的数学模型，都是由决策变量、约束条件（线性等式或不等式）及目标函数（最大或最小）3部分组成的。•为了使线性规划问题的求解变得尽可能简化，我们需要规定线性规划模型的标准形式。2.1.1线性规划问题的标准型•一般线性规划问题的标准型为•或简记为•上述标准型有以下4个特征。（1）目标函数值总为求最大。（2）约束条件全为线性等式。（3

3、）约束条件右端常数项全部为非负数。（4）决策变量全大于或等于零。2.1.2非标准型线性规划问题的标准化（1）若目标函数取最小值minz = CX，由于求z的最小值就是求−z的最大值，所以可以将其转化为max(−z) = −CX。（2）当约束条件中第个方程出现ai1x1+ai2x2+…+ainxn≤bi时，则增加一个“松弛变量”xi1≥0，使它成为等式ai1x1+ai2x2+…+ainxn+xi1 = bi。•同样，当约束条件中第个方程出现ai1x1+ai2x2+…+ainxn≥bi时，则减去一个“松弛变量”xi1≥0，使它成

4、为等式ai1x1+ai2x2+…+ainxn−xi1=bi。（3）当决策变量xj不满足xj≥0时，则增加两个新的非负决策变量x'j≥0和x"j≥0，用x'j−x"j替代xj，即令xj=x'j−x"j。（4）当约束条件中第i个方程右端出现常数项bi＜0时，则在方程两边同时乘（−1），得到−bi＞0。•例2.1将下列非标准型线性规划问题化为标准型。•解按照前面的变换方法，执行下列步骤。（1）将minz转化为max(−z)。（2）令x3=x'3−x"3，且x'3≥0，x"3≥0。（3）将第一个约束方程的左边减去一个非负的松弛变量x4，

5、将第2、第3个约束方程的左边分别加上一个非负的松弛变量x5和x6。•这样，可以将原来的线性规划问题标准化为2.1.3单纯形法的基本步骤和计算•两个变量的线性规划问题可以用图解法进行求解，而当变量是三个或三个以上且约束条件又多时，可行域所在的凸集表现为一个凸多边形，在空间上必将是一个凸几何体。•因此我们几乎或实在无法通过作图来找可行域，更无法找到最优解，此时图解法就显得无能为力了，但这些问题可以利用单纯形法进行求解。（1）基变量—在标准型每一个约束方程中选一个变量xj，它在该方程中的系数为1，在其他方程中系数为零，这个变量xj就称为

6、基变量，或称为基础变量。•如有m个约束方程，就可得到m个基变量，其余变量就称为非基变量。（2）基本可行解—非基变量为零的可行解。（3）基本最优解—满足目标函数的基本可行解，简称为最优解。•例2.2求解线性规划问题，其模型如下：•解（1）将线性规划问题化为标准型。•引入松弛变量x3,x4,x5后将其转化为标准型，即（2）列出初始单纯形表（见表2.1），并在表中计算出检验数j。①zj行的计算。•用Cj列（Cj列指目标函数中基变量的系数CB）中各数乘决策变量列的相对应数后再相加，即，具体计算结果如下：②j行的计算。•j=Cj−zj

7、，即用Cj行各数减去zj行相对应数，称为检验数。•一般地，j≤0表示基本可行解达到最优；否则j中有一正数就要继续进行迭代运算，向最优解逼近。•这里，1= 3 − 0= 3，2= 2−0= 2，3=4=5= 0 − 0= 0，所以要继续迭代运算。（3）确定主元列，选择进基变量。（4）确定主元行，选择离基变量。（5）对增广矩阵用初等行变换将主元化为1，主元所在列其余元素化为零。（6）重新按第3步骤和第4步骤对表2.2确定主元列与主元行及主元，选择进基变量与离基变量。（7）对增广矩阵用初等行变换将主元[5]化为1，将主元[

8、5]所在第二列其余元素化为零，得表2.3。•例2.3求解线性规划问题，其模型如下：•解先化为标准型，再用单纯形法。•将求解的一系列单纯形表汇总于表2.4中。2.2改进的单纯形法和对偶问题2.2.1改进的单纯形法•单纯形法的实质是从一个基本可行解走向