线性规划——单纯形法设计文档——《通用优化模块》编写人：徐天爽编写时间：2010年06月完成2010年06月整理目录第一部分功能概述 (1)第二部分理论知识 (2)2.1 线性规划标准型 (2)2.2单纯形法 (4)2.2.1修正单纯形法 (4)2.2.2Bland规则 (7)第三部分程序主要内容 (9)第四部分程序测试 (10)备注 (17)参考文献 (18)第一部分功能概述单纯形法是线性规划算法的一种。
由于若线性规划问题有最优解，则一定存在一个基本可行解是最优解，因此单纯形法是通过沿着可行集的边界，从一个顶点转移到改善当前目标函数值的相邻定点，以此来寻找最优解。
程序编写了加入Bland规则的修正单纯形法，只需用户给定设计变量个数、约束条件个数、约束条件系数，委托矩阵操作类MatrixOperation进行矩阵运算，即可实现线性规划问题的优化。
第二部分 理论知识线性规划问题具备以下性质：定理1 若线性规划问题的可行域X 非空，则X 是一个凸集。
定理2 线性规划问题的每一个基本可行解x 都对应于可行域X 的一个顶点。
定理3 若线性规划问题有最优解，则一定存在一个基本可行解是最优解。
定理4 若线性规划问题有最优解，则目标函数的最优值一定可以再可行域X 的某个顶点上达到。
2.1 线性规划标准型定义1 如果目标函数是设计变量的线性函数，且约束条件也是关于设计变量的线性等式或线性不等式，则相应的数学问题就称为一个线性规划问题。
单纯形法计算问题的最优值需要将原问题统一为标准形式。
定义线性规划问题的标准形式为：定义2 给定线性规划问题的标准型为()()11min ..1,2,,01,2,,nj jj n ij j i j j z c x s t a x b i m x j n ==⎧=⎪⎪⎪==⎨⎪⎪≥=⎪⎩∑∑ (1)其中()01,2,,i b i m ≥= 。
即对目标函数一律求最小值；设计变量均非负；约束条件除非负约束条件之外一律为等式约束；约束条件的右端项一律非负。
单纯形法原理单纯形表单纯形法原理与单纯形表的详实解析在数学领域中，特别是在线性规划问题的研究中，单纯形法是一种十分重要的求解方法。
它是由美国数学家乔治·丹齐格在1947年提出的一种迭代算法，用于解决具有多个变量和约束条件的优化问题。
本文将围绕单纯形法的原理和单纯形表这两个核心概念进行详细的解析。
一、单纯形法原理单纯形法的基本思想是通过一系列可行解逐步逼近目标函数的最大值或最小值。
这些可行解形成一个点集，称为单纯形。
每次迭代过程中，算法都会选择一个新的顶点作为下一个单纯形的顶点，这个新的顶点应该使目标函数有所改进。
重复这一过程，直到达到最优解或者满足停止准则为止。
单纯形法的步骤如下：1. 构造初始单纯形：首先，需要找到一个包含至少两个可行解的多边形，这就是初始单纯形。
2. 判断是否达到最优解：如果当前顶点的目标函数值已经是全局最优解，那么算法结束。
3. 选择换入变量：如果当前顶点不是最优解，那么需要选择一个非基变量来替换基变量。
这个被选中的非基变量应该是能够使目标函数最大化的变量。
4. 计算换出变量：确定了换入变量后，需要计算相应的换出变量。
这可以通过解一个线性方程组来实现。
5. 更新单纯形：用新选出的变量替换旧的变量，得到新的单纯形。
6. 回到第二步，继续判断是否达到最优解。
二、单纯形表单纯形表是单纯形法的重要工具，它记录了单纯形法每一步的详细信息。
每个列代表一个基变量，而每个行则代表一个约束条件。
表中还包括目标函数的系数、常数项以及松弛变量和剩余变量的系数。
在单纯形表中，每一行代表一个约束条件，包括它的系数、常数项以及松弛变量和剩余变量的系数。
每一列则代表一个基变量，包括它的系数和该变量对应的值。
在每一步迭代过程中，单纯形表都会被更新以反映当前的解状态。
通过观察单纯形表的变化，我们可以清楚地看到迭代过程是如何进行的，以及如何通过调整基变量来改进目标函数的值。
总结来说，单纯形法是一种有效的解决线性规划问题的方法，其核心在于构造并不断更新单纯形表，通过迭代寻找最优解。
