下载文档原格式
第 六 次课 2学时本次课教学重点：单纯形法原理、基变换、最优检验 本次课教学难点：单纯形法原理、基变换、最优检验 本次课教学内容：第五章 单 纯 形 法§1 单纯形法的基本思路和原理一、 单纯形法的基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是,则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。
直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。
通过第二章例1的求解来介绍单纯形法:在加上松弛变量之后我们可得到标准型如下： 目标函数： max 50x1+100x2 约束条件：x1+x2+s1≤300， 2x1+x2+s2≤400， x2+s3≤250.xj ≥0 （j=1，2）,sj ≥0 （j=1，2,3） 它的系数矩阵⎪⎪⎪⎭⎫ ⎝⎛==100100101200111),,,,(54321p p p p p A其中pj 为系数矩阵A 第j 列的向量。
A 的秩为3,A 的秩m 小于此方程组的变量的个数n ，为了找到一个初始基本可行解，先介绍以下几个线性规划的基本概念。
二、基本概念基： 已知A 是约束条件的m ×n 系数矩阵，其秩为m 。
若B 是A 中m ×m 阶非奇异子矩阵（即可逆矩阵），则称B 是线性规划问题中的一个基。
基向量：基B 中的一列即称为一个基向量。
基B 中共有m 个基向量。
非基向量：在A 中除了基B 之外的一列则称之为基B 的非基向量。
基变量：与基向量pi 相应的变量xi 叫基变量，基变量有m 个。
非基变量：与非基向量pj 相应的变量xj 叫非基变量，非基变量有n －m 个。
由线性代数的知识知道，如果我们在约束方程组系数矩阵中找到一个基，令这个基的非基变量为零，再求解这个m 元线性方程组就可得到唯一的解了，这个解我们称之为线性规划的基本解。
在此例中我们不妨找到了 ⎪⎪⎪⎭⎫ ⎝⎛=1010010113B 为A 的一个基，令这个基的非基变量x １，s2为零，这时约束方程就变为基变量的约束方程：x2+s1≤300，x2=400， x2+s3=250.求解得到此线性规划的一个基本解：x1=0，x2=400，s1=－100，s2=0，s3=－150由于在这个基本解中s1=－100，s3=－150，不满足该线性规划s1≥0，s3≥0的约束条件，显然不是此线性规划的可行解，一个基本解可以是可行解，也可以是非可行解，它们之间的主要区别在于其所有变量的解是否满足非负的条件。
单纯形法1. 什么是单纯形法单纯形法（Simplex Method）是一种数学优化方法，用于在线性规划问题中寻找最优解。
其基本思想是通过不断地在可行解空间中移动，逐步优化目标函数的值，直到找到最优解。
单纯形法是由美国数学家乔治·达内策在20世纪40年代开发的，成为线性规划问题求解的一种经典方法。
2. 单纯形法的基本原理单纯形法的基本原理是通过构造一系列的顶点组合，这些顶点组合构成了可行解空间的一个多面体，称为单纯形。
每次移动都是在单纯形的边界上进行，直到找到最优解。
2.1 线性规划问题的标准形式在使用单纯形法求解线性规划问题之前，首先需要将问题转化为标准形式。
线性规划问题的标准形式包括以下特征：•最大化目标函数或最小化目标函数•约束条件为等式或不等式•决策变量为非负数2.2 单纯形法的步骤单纯形法的求解步骤如下：1.初始化：将线性规划问题转化为标准形式，并找到初始可行解。
2.检验最优性：计算当前基可行解对应的目标函数值，判断是否达到最优解。
3.寻找进入变量：通过计算目标函数的系数与约束条件中的系数之比，找到使目标函数值最大（或最小）增长的变量。
4.寻找离开变量：从进入变量所属列中选择合适的变量离开基，使得新的基可行解依然满足约束条件。
5.更新基：将进入变量换入基，将离开变量换出基，得到新的基可行解。
6.重复步骤 2-5，直到找到最优解或判断无界。
2.3 单纯形表在单纯形法的求解过程中，通过使用单纯形表（Simplex Table）来记录每一步的计算结果和变量的取值。
单纯形表是一个矩阵，包含基变量、非基变量、目标函数系数、约束条件左边的系数等信息，方便进行计算和调整。
3. 单纯形法的优缺点3.1 优点•单纯形法是一种简单直观的求解线性规划问题的方法，容易理解和实现。
•单纯形法对于规模较小的问题，可以得到精确的最优解。
•单纯形法可以处理带有不等式约束的问题，适用范围广。
3.2 缺点•单纯形法在解决大规模问题时，计算复杂度较高，效率较低。
单纯形法一、基本概念二、思路与原理三、基本步骤一、基本概念LP: Max(Min)Z = CX (1)AX=b (2)X≥ 0 (3)其中，A=(aij)m×n，一般，m<n，且R(A)=m。
1.基：已知A=(aij)m×n ，其秩为m(R(A)=m) 。
从A中任取m个线性无关的列向量构成的矩阵B，（即B是A中m×m阶非奇异子矩阵（即可逆矩阵）），则称B是线性规划问题中的一个基。
注：一个LP问题的基的个数是不唯一的，最多为：个。
2.基向量,非基向量：基B中的一列pi称为一个基向量。
A中基B之外的一列pj称为一个非基向量。
注：一个LP有m个基向量， n－m个非基向量。
3.基变量,非基变量：与基向量pi相应的变量xi称基变量；与非基向量pj相应的变量xj称非基变量。
注：一个LP有m个基向量， n－m个非基向量。
4.基本解,基本可行解,基本最优解对于一个基B，令所有的非基变量为0，求得满足（2）式的解，称作一个基本解。
注：即求解一个m元的线性方程组，由线性代数知识得知，可得到唯一的一组解。
若求得的基本解又满足（3）式，则称此基本解为基本可行解。
若基本可行解又满足（1）式，即使得目标函数达到最优值，则又称此基本可行解为基本最优解。
5.可行基，最优基与基本可行解相对应的基称作可行基；与基本最优解相对应的基称作最优基。
注：基本可行解可行基例：求出下列LP问题的所有基本解，基本可行解，基本最优解。
MaxZ = 50 x1 + 100 x2x1 + x2 ≤ 3002 x1 + x2 ≤ 400s.t. x2 ≤ 250x1 , x2 ≥ 0标准化，得：MaxZ = 50 x1 + 100 x2 + 0x3 + 0x4 + 0x5x1 + x2 + x3 = 3002 x1 + x2 + x4= 400s.t. x2 + x5= 250xj≥ 0(j=1～5)其中， 1 1 1 0 0 ,基有 -1=9个。
