运筹学基础及应用第五版 胡运权第一章.ppt

1、1 .一般线性规划问题的数学模型，2 .图解法，3 .单纯形法原理，4 .单纯形法的计算顺序，5 .进一步讨论单纯形法，6 .单纯形法的改进，7 .例子和Matlab的解法，第一章线性规划和单纯形法，1 .一般线性规划问题的数学模型，如附图所示一、问题的提出，有企业计划生产I、ii两种产品。 这两种产品要分别用a、b、c、d四种设备加工。 生产产品I，各设备分别为2、1、4、0h，生产产品ii，各设备必须分别为2、2、0、4h。 已知在各设备的计划期间生产这两种产品的能力分别为12、8、16、12h，另外，生产产品I的企业可以获得2元利润，生产产品ii的企业可以获得3元利润，企业可以安排生产两

2、种产品多少1 .一般线性规划问题的数学模型，条件：实现目的：2，线性规划问题的数学模型，三个组成部分：1 .决策变量：是决策者为了实现计划目标所采取的方案、措施，问题中应确定的未知量。 2 .目标函数：指定要实现问题的目的的请求，并且是被表示为决策变量的函数。 3 .约束条件：根据在确定变量取值时接收的各种可用资源的限制，被表示为包含确定变量的方程式或不等式。 一般线性规划问题的数学模型：目标函数：制约条件：简称：矩阵形为：中：三，线性规划问题的标准形，标准形：标准形的特征：4 .决定变量的值不为负。 1 .目标函数求极大值，2 .制约条件都是方程式，制约条件右端的常数项都不是负，一般的线性规

3、划问题是标准型：1 .目标函数是极小值：令：即：2 .制约条件是不等式：(1)制约条件是“”的情况：可能：很明显，(2)制约条件是“”的情况称为剩馀变量。缓和变量和剩馀变量统称为缓和变量，(3)目标函数中的缓和变量的系数表示缓和变量和剩馀变量分别未被充分利用的资源和超过的资源，所以没有被转换成价值和利益，所以在目标函数中系数为0。 3 .取值没有制约的变量。 如果变量x表示产品的年计划数和上一年计划数的差，则x取的值是正还是负是明确的，在此情况下，可以：例如，将下一个线性计划建模为标准形，解：取标准形：求解线性计划问题：从满足约束方程和约束不等式的决定变量中取值，找到目标函数为最大的值。 四、

4、线性规划问题的解、可行解：满足制约条件的解称为可执行解，可执行解的集合称为可执行域。 最佳解：使目标函数为最大值的可执行解。 基：约束方程的满秩子矩阵被称为规划问题的一个基，基中的各列向量被称为基向量，与基向量相对应的变量被称为基变量，其他变量被称为非基变量。 基解：在制约方程式中，所有的非基变量都为0，可以解基变量的唯一的解，该解和非基变量的0一起构成基解。 基本可执行解：满足变量的非负的基本解称为基本可执行解，可执行基：对应于基本可执行解的基本称为可执行基，例4说明基本、基本变量、基本可执行解和可执行基是什么，实现目的： n维空间中线性规划问题的概念的确立和解决一般的线性规划问题的单求解下

5、一个线性规划问题：2 .线性规划问题的图解法，画出线性规划问题的可能域：目标函数的几何意义：确定最佳解：图解法的步骤：建立坐标系，建立满足图中所示约束条件的解的范围，创建目标函数的图表，确定最佳解。无限多最佳解的情况：目标函数和某个制约条件正好平行，没有边界解(或没有最佳解)的情况：可执行域上没有边界，没有可执行解的情况：制约条件没有共同范围，图解法的启发：线性规划问题的情况：唯一最佳解，无限多最佳解，没有边界解线性规划问题存在可执行域时，如果在可执行域中存在作为凸集的线性规划问题的最佳解，则最佳解或最佳解之一一定能在可执行域的顶点取得的解题的想法是，首先寻找凸集的任一顶点，计算其目标函数值。

6、 比较该相邻顶点的函数值，如果更好，则按点移动，直到找到最佳解为止。 3 .单纯形法的原理、凸集：如果是集合c中的任意两点，其连接上的所有点都是集合c中的点。 上图的(1)(2)是凸点集合，(3)(4)不是凸点集合，因为顶点：对于凸点集合c中的点x，不存在c中的其他两个不同点，所以x在它们的连接上时，将x称为凸点集合的顶点。 一、线性规划问题的基本定理，定理一线性规划问题中存在可执行解的话，问题的可执行域就是凸集。 定理二线性规划问题的基本可执行解x对应于线性规划问题可执行域(凸集)的顶点。 定理三、线性规划问题中如果有最佳解的话，必然存在一个基本可行的解才是最佳解。 根据以上三个定理求出线性

7、规划问题的最佳解，只要比较与可执行区域(凸集)的各顶点对应的目标函数值即可，最大的是我们求出的最佳解。 定理1 :如果LP模型中存在可执行解，则可执行区域为凸集。 证明：假设maxz=CXst.AX=bX0，其可能域为c，X1、X2为其可能解，X1X2，则X1c、X2c，即AX1=b、AX2=b、X10、X20， x为x1、x2连接线上的点，即x=x c是凸集合。 三个基本定理：引理：线性规划问题的可执行解X=(x1，x2，xn)T为基本可执行解的充分条件是，与x的正分量对应的系数列向量是线性独立的。 证明： (1)必要性：与x基本可执行解x的正分量对应的系数列向量的线性独立，可以设为X=(x

8、1，x2，xk，0，0)T，如果x是基本可执行解，则根据基本可执行解的定义，与x1，x2，xk对应的系数列向量P1，P2，Pk是线性的(2)充分性：设与x正分量对应的系数列向量的线性独立x为基本可能解的a的等级为m，则x的正分量的个数km； 当k=m时，x1、x2和xk的系数列向量P1、P2、 Pk构成基础，8756； x基本上是可能的解。 在k0、xj=0时，yj=ZJ=0，8756； pjyj=，j=1，n，pjyj=b(1)，j=1，r，pjzj=b(2)，j=1，r，(yj-zj)pj=0，j=1，r，(1)-(2)是必要的，(y1-Z1 ) P1 (y1 z1=CX1=CX0-C=z

9、max-C、z2=cX2=cx0c=zmaxcz0=zmaxz1、z0=zmaxz2、8756； z1=z2=z0，即X1、X2也是最佳解，如果X1、X2还不是顶点，则顶点可以这样递归地推论直到成为最佳解为止。 因此，基本上找到可行的解作为最佳解是必然的。 定理3 :线性计划模型中如果有最优解，基本上一定存在可执行的解。 证明：如果X0=(X10，X20，xn0)T是线性规划模型的最佳解，则z0=zmax=CX0的X0基本上不是可能的解，即不是顶点，足够小的话，X1=X0-0，x2=x0，即x1， x2是可能的解，简单的形法的计算步骤：初始基本上是可能的解，STOP，y，n，二，确定初始基本可

10、行解，线性规划问题的最佳解必须在基本可行解中获得，我们首先找到了初始基本可行解。 然后，切换至可以在别的基础上执行的解，直到找到最佳解为止。给出的线性规划问题：所以约束方程的系数矩阵为：因为该矩阵包含一个单位子矩阵，所以以该单位矩阵为基础，一个基本可执行解：其标准形式为：三，从初始基本可执行解变换为另一个基本可执行解，对初始可执行解的系数矩阵进行初等行变换，构建一个新的单位矩阵从一个基本可执行解到另一个基本可执行解的转换在不损失一般性的情况下，基本可执行解X0=(x10，x20，x0，XM 0，0， 0)T，前m个分量为正值，秩为m，其系数矩阵为p1p2、 pmpm1、 pj.pnb 10、0

11、a1、m1a1j1nb101、0a2、m1a2ja2nb200、1am m 1amjamnbm， 喀嚓喀嚓喀嚓喀嚓喀嚓喀嚓地653即Pj=aijpi，移项，两端乘以0 (2)，i=1，m，i=1，m 通过全部将xi0-aij0取得得足够小，i=1、m、X1=(x10-a1j、x20-a2j、xm0-amj、0、0)T也是可以理解的。 假设min-aij0=-，则X1的前m个组件中至少有一个xL1为0。 xi0，aij，aLj，xL0，I，8756； p1、P2、PL-1、PL 1、Pm、Pj与线性没有关系。x1也是基本上可能的解。 四、最优检查和解的判别，四、最优检查和解的判别，在所有情况下，

12、与现有顶点相对应的基本可执行解是最优解。 在所有情况下，还有一个非基变量，在能发现的情况下，这个线性规划问题有无限的最佳解。 3 .存在一个者，存在向量的所有分量，并且可选地，如果是一定的，则存在边界解。 由于0，有以下结论： z1=z0 j，4 .简单形法的计算步骤，第一步：求初始可执行解的列初始简单形表，表的最上列是各变量的目标函数中的系数，最左列是各基变量的目标函数中的系数。 2 .表的最后一行是检查数。 第二步：进行最佳性检查，表中所有的检查数，表中的基本可执行解是问题的最佳解，到现在为止计算了，不然就转到下一步。 第三步：转换为新的基本可执行解，构建新的单纯形表，1 .确定变换变量，

13、2 .确定变换变量，3 .转换为新的单纯形表，(1)、(2)、(3)检测常数的求出方法与初始单纯形表的求出方法相同，第四步重复三个步骤，例子5用简单形式法求解线性规划问题，解：把原来的线性规划问题变成标准形式的第一步骤：基于系数矩阵的单位矩阵部分，得到初始基的可执行解，列出初始简单形式表，第三步骤：1 .确定变换变量，2 .确定变换变量由于上表中所有的检验数都在零以下，所以得到了最佳解，最佳解为：代入目标函数，最佳值：计算检验数具有相同的值时，可以从其中选择一个变量作为代入变量。 如果计算值相同，也可以从其中选择一个作为转换变量。 注意：5 .简单形法的进一步研究，一、人工变量法，上节例5的线

14、性规划问题的考察：化标准形：其系数矩阵为：系数矩阵中存在单位矩阵，因此容易找到初始可执行基。 然而，可能不同，考虑下一个线性规划问题：标准型：例6，此问题的系数矩阵：因为此矩阵中不包含单位矩阵，所以很难找到初始基础。 当这个线性规划问题的系数矩阵不包含单位矩阵时，我们通常采用添加人工变量的方法，人工构建单位矩阵。 这种方法是人工变量法。 为了构建单位矩阵，在系数矩阵中添加了两列单位列向量，系数矩阵为：线性规划问题的制约条件为：人为地添加，因此被称为对应的变量，人工变量。在添加目标函数中人工变量的系数：人工变量之前，在线性规划问题的标准形式中，每个约束条件都已经是等式约束，并且为了确保等式约束是

15、不变的，在最佳解中，人工变量的取值必须为0。 因此，如果将目标函数中的人工变量的系数设为任意大的负值来表示为“”的话，只要人工变量不使值为零，目标函数就不能极大化。 由于目标函数加：m处理人工变量的方法，大m法，求解过程：所以最佳解是：二，二阶段法，大m处理人工变量时，计算机求解产生了错误，从而产生了二阶段法。 的双曲馀弦值。 第一阶段：首先，解决目标函数中只包含人工变量的线性规划问题。 将目标函数中其他变量的系数设为零，将人工变量的系数设为某个正的常数(一般为1 )，在保持原来的问题约束条件的同时，求出将该目标函数极小化时的解。 第二阶段：从第一阶段的最终单纯形表中删除人工变量，根据原问题的目标函数继续寻找原问题的最佳解。 三、关于解的判别，所有情况下，又有一个非基变量，可以发现的情况下，这个线性规划问题有无限的最佳解。 例7 .解线性规划问题：在图解法中，我们知道这个问题有无限解。 其标准形为：用单纯形法计算，最终的单纯形表为：从表中得到最佳解