1、课程设计报告（运筹学设计报告）班级：应用数学 0402 班姓名：彭 港学号：0401020220运筹学课程设计报告实验序号： 日期： 2007 年 1 月 24 日班 级 数学 0402 姓 名 彭 港 学 号 0401020220实验名称 单纯形算法问题描述：单纯形算法的基本思想：就是从一个基本的可行解出发，求一个使目标函数更优的可行解，通过改进基本可行解来达到最优可行解。在单纯形法的计算过程中，因为每次的迭代计算较复杂，所以我们利用计算机实现该过程。实验目的：1. 了解单纯形法的算法。2. 通过单纯形法来解决实际线性规划问题3. 学习和提高应用一门语言编程的能力实验原理与数学模型：对于一个
2、线性规划问题： 1212max3846.,0zxstx我们可以通过加入松弛变量，人工变量和剩余变量使线性规划问题转换成如下的标准形式：1234531425ma0846.0,.zxxxstj此时我们对形如上式的线性规划问题可以以如下步骤进行求解：一、在线性规划问题中找出一组初始可行基 二、根据初始可行基可以确定一组解，对这组解进行最优性检验与解的判别 三、基变换，此步骤主要利用检验数等确定换入变量与换出变量 四、对系数矩阵进行相应的迭代，也就是进行矩阵变换，求解出换入换出后的一组可行解 。如此的利用上述的步骤，进行计算直到求解出一组最优解为止。实验所用软件及版本：Microsoft Visual
3、 C+ 6.0主要内容：单纯形算法计算过程：1) 输入各参数（价值系数向量 C，约束条件系数矩阵 A，初始基变量X）2) 计算所有检验数是否都小于等于零，若不是转下一步，否则计算最优值，并返回对应的最优解3) 若不是所有检验数都小于等于零，则判断大于零的检验数对应的约束条件系数矩阵的列是否都小于等于零，若是则存在无界解返回，否则转下一步4) 选定换入变量和换出变量5) 对约束条件系数矩阵进行变换，变换完成转第二步实验过程记录（含：基本步骤、主要程序清单及异常情况记录等）：程序：/用例测试文件#include using namespace std;#define MAX_G 50 /宏定义 变
4、量个数最大值#include “danchunxing.cpp“void main()float AMAX_GMAX_G=1,2,1,0,0,4,0,0,1,0,0,4,0,0,1;float cMAX_G=2,3,0,0,0;float bMAX_G=8,16,12;int xbMAX_G=2,3,4;float opt;opt=DanChunXing(cout0)*(st+i)=*(b+i)/Aih;else*(st+i)=9999999;min=*st;l=0;for(i=1;i*(st+i)min=*(st+i);l=i;/存入换出变量的下标*(Xb+l)=h;temp=Alh;/开始
5、矩阵变换*(b+l)=*(b+l)/temp;for(i=0;in;i+)Ali=Ali/temp;for(j=0;jm;j+)if(j!=l)tmp=Ajh;for(i=0;in;i+)Aji=Aji-Ali*tmp;*(b+j)=*(b+j)-*(b+l)*tmp;/结束矩阵变换程序运算实例：1234512345max008416. 20,12,.zxxstxxj程序运算结果：目标最优值为:14对应的最优解为: x0 x4 x1可以判断基解中是否含有非零Press any key to continue思考与深入：单纯形法，作为一个比较成熟的算法来求解线性规划问题，此程序只求解关于最大值问题，对于求解最小值问题，我们可以化为最大值进行求解，对于增加人工变量的线性规划问题的标准形式，无论用大 M 法还是两阶段法，此程序同样适用，当用两阶段法时，需要对进行单纯形求解的函数调用两次即可。不过需要注意的，在确定是无可行解，还是最优解时，需要检查是否含有人工变量，对一个变量是否是人工变量较难确定，所以需要自己确定是否有最优解。教师评语：
