jlmao-运筹学-上机报告-v2.0.doc

自动化系上机实验报告（课程名称：运筹学） 学生姓名：李志荣 学号：2012104021088/4/2017 6:36:32 上午 第 1 页 共 21 页上 机 实 验 报 告班级： 121 专业/方向：测控姓名： 李志荣学号： 201210402108实 验 成 绩(10 分制)上机实验名称：编程实现 Simplex 算法求解 LP 问题上机时间：2014-5-28 上机地点：信自楼 234 自动化系机房一、实验目的和要求1、目的： 掌握单纯形算法的计算步骤，并能熟练使用该方法求解线性规划问题 了解算法程序实现的过程和方法2、要求： 使用熟悉的编程语言编制单纯形算法的程序 独立编程，完成实验，撰写实验报告并总结二、实验内容和结果1、单纯形算法的步骤及程序流程图单纯形算法的步骤对于一般的标准形式线性规划问题(求极小问题),首先给定一个初始基本可行解设初始基为 B,然后执行如下步骤： (1).解 ,求得 ，Bxb1Bxb0,Nfc令 计 算 目 标 函 数 值 1(12.,)imi以 记 的 第 个 分 量(2).计算单纯形乘子 w, ,得到BwC,对于非基变量，计算判别数1BwC,可直接计算1ii izcpc单纯形算法的程序流程图自动化系上机实验报告（课程名称：运筹学） 学生姓名：李志荣 学号：2012104021088/4/2017 6:36:32 上午 第 2 页 共 21 页令1BAc,R 为非基变量集合max{}kiR若判别数 ,则得到一个最优基本0k可行解，运算结束；否则，转到下一步(3).解 ,得到 ；若kByp1kkyBp,即 的每个分量均非正数，0ky则停止计算，问题不存在有限最优解，否则，进行步骤(4).确定下标 r,使:0min,0trkktkbbtkyy且rBx为 离 基 变 量 ,,rk Bpk为 进 基 变 量 用 替 换 得 到 新 的 基 矩 阵 ,还 回 步 骤 (1)2、单纯形算法程序的规格说明（程序以附录形式给出） 。

输入：（运行程序所需输入的参数）2 2 1 0 04 0 0 1 00 5 0 0 1自动化系上机实验报告（课程名称：运筹学） 学生姓名：李志荣 学号：2012104021088/4/2017 6:36:32 上午 第 3 页 共 21 页2 3 0 0 012 16 150 0 0输出：（程序执行之后的结果）自动化系上机实验报告（课程名称：运筹学） 学生姓名：李志荣 学号：2012104021088/4/2017 6:36:32 上午 第 4 页 共 21 页功能描述：求解单纯形法3、使用所编程序求解如下 LP 问题并给出结果例：编程求解 LP 问题：自动化系上机实验报告（课程名称：运筹学） 学生姓名：李志荣 学号：2012104021088/4/2017 6:36:32 上午 第 5 页 共 21 页12345612456max00128.40,.,jzxxstxx输入：2 2 1 0 0 01 2 0 1 0 01 0 0 0 1 00 1 0 0 0 12 3 0 0 0 012 8 16 120 0 0 0结果：自动化系上机实验报告（课程名称：运筹学） 学生姓名：李志荣 学号：2012104021088/4/2017 6:36:32 上午 第 6 页 共 21 页三、实验总结1、上机过程中出现的问题及解决方法。

输入会出现输错的情况 解决：重新输入自动化系上机实验报告（课程名称：运筹学） 学生姓名：李志荣 学号：2012104021088/4/2017 6:36:32 上午 第 7 页 共 21 页2、本次实验的体会深深地感受到计算机的强大，手工要很长时间甚至无法完成的计算，计算机瞬间就可以计算出结果自动化系上机实验报告（课程名称：运筹学） 学生姓名：李志荣 学号：2012104021088/4/2017 6:36:32 上午 第 8 页 共 21 页【附录】单纯形算法程序（C、C++、matlab 语言或其它，请注明！）/* HELLO.C -- Hello, world */#include#include#define m 3#define n 5 /*定义未知量的个数 */float M=1000000.0;float A[m][n]; /*用于记录方程组的数目和系数;*/float C[n]; /*用于存储目标函数中各个变量的系数*/float b[m]; /*用于存储常约束条件中的常数 */float CB[m]; /*用于存储基变量的系数*/float seta[m]; /*存放出基与入基的变化情况*/float delta[n]; /*存储检验数矩阵*/float x[n];int num[m]; /*用于存放出基与进基变量的情况*/float ZB=0; /*记录目标函数值 */void input();void print();int danchunxing1();int danchunxing2(int a);void danchunxing3(int a,int b);/*检查校验数 delta如果所有校验数 delta0){flag=0;break;}/*flag=1 当前解为最优解，返回主函数-1*/if(flag==1)return -1;/*从第 1 列的校验数开始检查，寻找最大的校验数 delta 并返回校验数最大的列号*/for(i=0;imax){max=delta[i];k=i;}}自动化系上机实验报告（课程名称：运筹学） 学生姓名：李志荣 学号：2012104021088/4/2017 6:36:32 上午 第 9 页 共 21 页return k;}/*确定入基变量input：int a 入基变量对应的列号output：如果所有校验数 delta0)seta[i]=b[i]/A[i][k];else seta[i]=M;}/*寻在最小的 seta，确定入基变量 */min=M;for(i=0;i=seta[i]){min=seta[i];j=i;}}num[j]=k+1;CB[j]=C[k];return j;}/*迭代计算，重新获得单纯性表?*/void danchunxing3(int p,int q) {int i,j,c,l;自动化系上机实验报告（课程名称：运筹学） 学生姓名：李志荣 学号：2012104021088/4/2017 6:36:32 上午 第 10 页 共 21 页float temp1,temp2,temp3;c=p;/*主元素所在行号*/l=q;/*主元素所在列号*/temp1=A[c][l]; /*记录主元素 *//*主元素所在行的 b 的计算*/b[c]=b[c]/temp1;/*主元素所在行的 a 的计算*/for(j=0;j> f=[10;5]>> A=[3 4;5 2]>> b=[9;8]>> lb=zeros(2,1)>>[x,fval,exitflag,output,lambda]=linprog(f,A,b,[],[],lb)运行结果：>> f=[10;5]f =105>> A=[3 4;5 2]A =3 45 2自动化系上机实验报告（课程名称：运筹学） 学生姓名：李志荣 学号：2012104021088/4/2017 6:36:32 上午 第 14 页 共 21 页>> b=[9;8]b =98>> lb=zeros(2,1)lb =00>> [x,fval,exitflag,output,lambda]=linprog(f,A,b,[],[],lb)Optimization terminated successfully.x =1.0e-009 *0.01360.1457fval =17.5exitflag =1output = iterations: 5cgiterations: 0algorithm: 'lipsol'自动化系上机实验报告（课程名称：运筹学） 学生姓名：李志荣 学号：2012104021088/4/2017 6:36:32 上午 第 15 页 共 21 页lambda = ineqlin: [2x1 double]eqlin: [0x1 double]upper: [2x1 double]lower: [2x1 double]>> 【分析与比较】：请用图解法画出上述问题的可行解域(用阴影线标记)，并标记出所有顶点的位置和最优解的位置(可手工绘图完成！)。

2、0-1 规划问题的求解题目：试用 Matlab 优化工具箱求解 0-1 规划问题：1234512345max873.50,izxxstori解：求解问题的 Matlab 程序： 运行结果：三、实验总结自动化系上机实验报告（课程名称：运筹学） 学生姓名：李志荣 学号：2012104021088/4/2017 6:36:32 上午 第 16 页 共 21 页1、上机过程中出现的问题及解决方法输入错误，仔细检查看哪里输错了。