运筹学之单纯型法.pptVIP

第三节 单纯型法（1） 解的概念 最优解： 使得目标函数达到最优的可行解 最优值： 最优解对应的目标函数值 目的： 求最优解和最优值 求解方法： 单纯形法 先研究AX=b 设 系数矩阵A是m×n矩阵，秩为m， B是A中m×m阶非奇异子矩阵（即|B|≠0），则称B是线性规划问题 的一个基。 B 是由m个线性独立的列向量组成 AX=BXB+NXN=b 令 非基变量XN=0 得BXB=b 和特解XB =B-1b 结合XN=0 称为对应于B的基本解 基本解个数=基的个数≤Cnm 基本可行解 可行的基本解 XB≥0 XN=0 可行基：对应的基本解也是可行解 基本可行解 可行的基本解 XB≥0 XN=0 可行基：对应的基本解也是可行解 最优基： 对应的基本可行解也是最优 基本可行解个数≤基的个数≤Cnm 基本可行解的非零分量均为正分量， 其正分量个数≤ m。 退化的基本可行解： 基本可行解的非零分量个数小于m时，也就是在基本可行解中一个或多于一个的基变量取零值时 基 本 可 行 解 定 义 基 本 定 理 问 题 例1－10 线性规划问题基本可行解的意义： 例1－11 例1－11 解的几何意义 求解思路 线性规划问题的解的概念 1.可行解 2.基 3.基可行解 4.可行基 1. 可行解 2. 基，基向量，基变量 基可行解 满足非负条件（1-6）的基解，称为基可行解. 基可行解的非零分量的数目也不大于m，并且都是非负的。 4. 可行基 对应于基可行解的基，称为可行基。 约束方程组(1-5)具有基解的数目最多是 个。一般基可行解的数目要小于基解的数目。 以上提到的几种解的概念，它们之间的关系可用图1-6表明。 另外还要说明一点，基解中的非零分量的个数小于m个时，该基解是退化解。在以下讨论时，假设不出现退化的情况。以上给出了线性规划问题的解的概念和定义，它们将有助于用来分析线性规划问题的求解过程。 图1-6 它们之间的关系 单纯形法求解线性规划的思路： 一般线性规划问题具有线性方程组的变量数大于方程个数，这时有不定的解。但可以从线性方程组中找出一个个的单纯形，每一个单纯形可以求得一组解，然后再判断该解使目标函数值是增大还是变小，决定下一步选择的单纯形。这就是迭代，直到目标函数实现最大值或最小值为止。这样问题就得到了最优解，先举一例来说明。 注： 单纯形是指0维中的点，一维中的线段，二维中的三角形，三维中的四面体，n维空间中的有n+1个顶点的多面体。例如在三维空间中的四面体，其顶点分别为(0，0，0)，(1，0，0)，(0，1，0)，(0，0，1)。具有单位截距的单纯形的方程是∑xi≤1，并且xi≥0，i=1,2,…,m。 3.1 举例 例6 试以例1来讨论如何用单纯形法求解。例1的标准型为： 约束方程(1-12)式的系数矩阵 从(1-12)式中可以看到x3,x4,x5的系数列向量 P3 ,P4,P5是线性独立的，这些向量构成一个基 对应于B的变量x3,x4,x5为 基变量. 将(1-13)式代入目标函数(1-11) 得到 当令非基变量x1=x2=0，便得到z=0。这时得到一个基可行解X(0) X(0)=(0,0,8,16,12)T 这个基可行解表示：工厂没有安排生产产品Ⅰ、Ⅱ；资源都没有被利用，所以工厂的利润指标z=0。 从分析目标函数的表达式(1-14)可以看到 非基变量x1,x2(即没有安排生产产品Ⅰ，Ⅱ)的系数都是正数，因此将非基变量变换为基变量，目标函数的值就可能增大。从经济意义上讲，安排生产产品Ⅰ或Ⅱ，就可以使工厂的利润指标增加。所以只要在目标函数(1-14)的表达式中还存在有正系数的非基变量，这表示目标函数值还有增加的可能，就需要将非基变量与基变量进行对换。 如何确定换入，换出变量 一般选择正系数最大的那个非基变量x2为换入变量，将它换入到基变量中去，同时还要确定基变量中有一个要换出来成为非基变量，可按以下方法来确定换出变量。 现分析(1-13)式，当将x2定为换入变量后，必须从x3,x4,x5中确定一个换出变量，并保证其余的都是非负，即x