当前位置：文档之家› 最小重量算法设计

最小重量算法设计

最小重量机器设计问题

一、实验目的

1、了解回溯法和分支限界法的基本思想。

2、运用回溯法和分支限界法解决最小重量机器设计问题。

二、实验要求

最小重量机器设计问题：设某一机器由n个部件组成，每一种部件可以从m个不同的供应商处购得。设w ij是从供应商j处购得的部件i的重量，c ij是相应的价格。试设计一个算法，给出总价格不超过c的最小重量机器设计。分别用回溯法和分支限界法实现问题的算法。

三、算法思想和实现

1、回溯法

（1）此问题是一棵排列树，设开始时bestx=[-1,-1,……,-1]则相应的排列树由x[0:n-1]的所有排列构成。

（2）找最小重量机器设计的回溯算法Backtrack是类machine的公有成员。私有数据成员整型数组Savex保存搜索过的路径，到达叶节点后将数据赋值给数组bestx。成员bestw记录当前最小重量，cc表示当前花费，cw表示当前的重量。

（3）在递归函数Backtrack中，在保证总花费不超过c的情况下：

当i=n时，当前扩展结点是排列树的叶节点。此时搜索到一个解，判断此时的最小重量是否小于当前最小重量，若小于则更新bestw，并得到搜索路径bestx。

当i

using namespace std;

#define N 3

#define M 3

int w[N][M]={{1,2,3},{3,2,1},{2,2,2}};

int c[N][M]={{1,2,3},{3,2,1},{2,2,2}};

class machine

{public:

void InitMachine(int C);

void Backtrack(int i);

void printsave();

private:

int COST;//题目中的C

int cw;//当前的重量

int cc;//当前花费

int bestw;//当前最小重量

int bestx[N];//最优解

int savex[N];//savex[i]如果为j，表示第i个零件应该选用第j个人供应的

}；

void machine::InitMachine(int C){

COST=C;

cw=cc;

bestw=-1;//初值为-1，标记最小重量是否变化

for(int j=0;j

bestx[j]=-1;

}

void machine::Backtrack(int i)

{ if(i>=N)//达到叶子节点

{if(cw

{

bestw=cw;

cout<<"************************************"<

cout<<"搜索路径的bestw:"<

for(int k=0;k

{

cout<

savex[k]=bestx[k];

cout<

}

return；

}

for(int j=0;j

{

if((cc+c[i][j]0))

{cc+=c[i][j];

cw+=w[i][j];

bestx[i]=j;

Backtrack(i+1);

bestx[i]=-1;

cc-c[i][j];

cw-=w[i][j];

}

void machine::printsave(){

if(bestw==-1) { cout<<"输入的总价格太小！"<

}

else {

cout<<"************************"<

cout<<"最优重量（bestw ）是："<

for(int k=0;k

cout<<"第"<

cout<

}

int main(){

mach Mach;

cout<<"输入总价格不超过的C:";

cin>>C;//输入最小花费

Mach.InitMachine(C);

Mach.Backtrack(0);

Mach.printsave();

return 0;

}

2、分支限界法

解空间为一棵排列树，采用优先队列式分支限界法找出所给的最小重量机器设计，开始时，将排列树的根节点置为当前扩展结点。在初始扩展结点处还设有选定部件是哪个供应商提供的，故cv=0，cw=0，position=0，peer=0，1≤i≤n。x[1:n]记录供应商的选择while完成对排列树内部结点的有序扩展。循环体内依次从活结点优先队列中取出具有最小重量的结点，依次为当前扩展结点。并且花费不超过c并加以扩展，队列为空时则结束循环。当peer=n时，此时扩展结点是叶节点，得到当前的最小重量和最优解数组x。若peer

#include "fstream.h"

#include "iostream.h"

struct nodetype {

int peer;

struct nodetype *parent;

int position;

double cw;

double cv;

double r; };

struct nodetype *queues[100000000];

/////////////////////////////////小根堆///////////////////////////////

void insert(struct nodetype *x, int oldlast) //x是要插入的数{ //oldlast是目前堆的元素数目

int last = oldlast+1;

queues[last]=x；

int i=last;

while((i > 1)&&(queues[i]->r < queues[i/2]->r)) {

struct nodetype *temp;

temp=queues[i];

queues[i]=queues[i/2];

queues[i/2]=temp;

i = i/2;

}

} //last是当前堆的元素个数，执行该函数后

struct nodetype * deletemin(int last,struct nodetype *a[]) { //返回堆的第一个元素（即最小元素）

struct nodetype *temp;

temp=a[1];

a[1]=a[last];

last --;

int i = 1;

int j=0;

while(i <= last/2)

{ if((a[2*i]->r < a[2*i+1]->r)||(2*i == last)) j = 2*i;

elsej=2*i+1;

if(a[i]->r > a[j]->r) {

struct nodetype *temp;

temp=a[i];

a[i]=a[j];

a[j]=temp;

i = j;

}

else return(temp);

}

return(temp);

}

void main() /////////////////////////////////小根堆/////////////////////////////// {

ifstream fin("input.txt");

ofstream fout("output.txt");

int n,m,c;

fin>>n;fin>>m;fin>>c;

double **w=new double*[n+1];

double **cc=new double*[n+1];

for(int i=1;i<=n;i++){

w[i]=new double[m+1];

cc[i]=new double[m+1];

}

for(i=1;i<=n;i++)

for(int j=1;j<=m;j++)

fin>>cc[i][j];

for(i=1;i<=n;i++)

for(int j=1;j<=m;j++)

fin>>w[i][j];

double *cmin=new double[n+1];

double *wmin=new double[n+1];

for(i=1;i<=n;i++) {

cmin[i]=cc[i][1];

wmin[i]=w[i][1];

for(int j=2;j<=m;j++) {

if(cmin[i]>cc[i][j]) cmin[i]=cc[i][j];

if(wmin[i]>w[i][j]) wmin[i]=w[i][j];

}

double *rc=new double[n+1];//剩余部件最小价格和double *rw=new double[n+1];//剩余部件最小重量和

rc[n]=0;rw[n]=0;

for(i=n-1;i>=1;i--) {

rc[i]=rc[i+1]+cmin[i+1];

rw[i]=rw[i+1]+wmin[i+1];

}

struct nodetype *node=new struct nodetype;

node->peer=0;

node->cv=0;

node->cw=0;

node->position=0;

node->r=rw[1]+wmin[1];

insert(node,0);

int cpeer=0;

int q_len=1;

bool isend=false;

while(!isend&&q_len>0)

{ node=deletemin(q_len,queues);

q_len--;

if(node->peer==n) {

isend=true;

fout<cw<

for(int k=n;k>=1;k--) {

x[k]=node->position;

node=node->parent;

}

for(k=1;k<=n;k++) fout<

fout<

for(int j=1;j<=m;j++)

{ if(node->cv+cc[node->peer+1][j]+rc[node->peer+1]<=c) {

cpeer=node->peer+1;

struct nodetype *node_add=new struct nodetype ;

node_add->peer=cpeer;

node_add->cv=node->cv+cc[cpeer][j];

node_add->cw=node->cw+w[cpeer][j];

node_add->r=node_add->cw+rw[cpeer];

node_add->position=j;

node_add->parent=node;

insert(node_add,q_len);

q_len++;

}

if(q_len<=0) { fout<<"No Solution!"<

return;}

}

四、结果

input.txt

3 3 4

1 2 3

3 2 1

2 2 2

1 2 3

3 2 1

2 2 2

output.txt

1 3 1

五、总结

分支限界法与回溯法对当前扩展结点所采用的扩展方式不同。在分支限界法中，每一个结点只有一次机会成为扩展结点。而在回溯法中，每一个活结点有多次机会成为扩展结点。

最优化课程设计

《最优化》课程设计题目：牛顿法与阻尼牛顿法算法分析学院: 数学与计算科学学院专业：数学与应用数学姓名学号：廖丽红 1000730105 欧艳 1000730107 骆宗元 1000730122 沈琼赞 1000730127 指导教师：李向利日期：2012年11月08日

摘要本文基于阻尼牛顿法在解决无约束最优化问题中的重要性，对其原理与算法予以讨论。论文主要是参阅大量数学分析和最优化理论方法，还有最优化方法课程以及一些学术资料，结合自己在平时学习中掌握的知识，并在指导老师的建议下，拓展叙述牛顿法和其改进方法——阻尼牛顿法的优缺点，同时针对阻尼牛顿法的基本思路和原理进行研究，其搜索方向为负梯度方向，改善了牛顿法的缺点，保证了下降方向。关键词：无约束牛顿法下降方向阻尼牛顿法最优解

Abstract This thesis is based on the importance of the damping Newton's method to solve unconstrained optimization problems, we give the discussion about its principles and algorithms. We search a large number of mathematical analysis and optimization theory methods, optimization methods courses, as well as some academic information ,and at the same time combined with knowledge we have learning in peacetime and thanks to the instructor's advice, we also give an expanding narrative for the Newton's method and the improved method -- damping Newton method's advantages and disadvantages, and make a study of the basic ideas and principles for damping Newton method at the same time , we find that a negative gradient direction is for the search direction of the damping Newton method, this method improves the shortcomings of the Newton method which can ensure the descent direction. Keywords: unconstrained , Newton's method , descent direction , damping Newton's method ,optimal solution

小型气动机械手的设计

小型气动机械手的设计摘要：本文主要进行了气动机械手的总体结构设计和气动设计。机械手的机械结构由气缸、气爪和连接件组成，可按预定轨迹运动，实现对工件的抓取、搬运和卸载。气动部分的设计主要是选择合适的控制阀，设计合理的气动控制回路，通过控制和调节各个气缸压缩空气的压力、流量和方向来使气动执行机构获得必要的力、动作速度和改变运动方向，并按规定的程序工作。气动机械手作为机械手的一种, 它具有结构简单、重量轻、动作迅速、平稳、可靠、节能和不污染环境等优点而被广泛应用。关键词：气动机械手；气缸；控制阀；回路；设计 Design of Small Pneumatic Manipulator Abstract:This article mainly has carried on the overall structural design and aerodynamic design of pneumatic manipulator. Robot mechanical structure is composed of a cylinder, a pneumatic claw and a connecting piece, according to a predetermined trajectory, on a workpiece gripping, conveying and unloading. Pneumatic main part of the design is to choose appropriate control valve, the rational design of pneumatic control circuit, the control and regulation of each cylinder of compressed air pressure, flow and direction to the pneumatic actuator to obtain the necessary force, speed of action and change the direction of movement, and according to the prescribed procedures work.Pneumatic machinery as a manipulator, which has the advantages of simple structure, light weight, quick action, stable, reliable, energy saving and no pollution to environment has been widely used. Key words: Pneumatic manipulator; cylinder; control valve; Circuit; the design 1 前言机械工业是国民的装备部，是为国民经济提供装备和为人民生活提供耐用消费品的产业。不论是传统产业，还是新兴产业，都离不开各种各样的机械装备，机械工业所提供装备的性能、质量和成本，对国民经济各部门技术进步和经济效益有很大的和直接的影响。机械工业的规模和技术水平是衡量国家经济实力和科学技术水平的重要标志。因此，世界各国都把发展机械工业作为发展本国经济的

计算机算法设计与分析期末考试复习题

1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14．广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．背包问题的贪心算法所需的计算时间为（ B ）。

最优化课程设计--共轭梯度法算法分析与实现

最优化课程设计--共轭梯度法算法分析与实现(设计程序) 题目共轭梯度法算法分析与实现班级 / 学号 14140101/2011041401011 学生姓名黄中武指导教师王吉波王微微课程设计任务书课程名称最优化方法课程设计院(系) 理学院专业信息与计算科学课程设计题目共轭梯度法算法分析与实现课程设计时间: 2014 年 6月 16日至 2014 年 6月 27日课程设计的要求及内容: [要求] 1. 学习态度要认真，要积极参与课程设计，锻炼独立思考能力; 2. 严格遵守上机时间安排; 3. 按照MATLAB编程训练的任务要求来编写程序; 4. 根据任务书来完成课程设计论文; 5. 报告书写格式要求按照沈阳航空航天大学“课程设计报告撰写规范”; 6. 报告上交时间:课程设计结束时上交报告; 7. 严禁抄袭行为，一旦发现，课程设计成绩为不及格。一、运用共轭梯度法求解无约束最优化问题要求:1)了解求解无约束最优化问题的共轭梯度法; 2)绘出程序流程图; 3)编写求解无约束最优化问题的共轭梯度法MATLAB程序; 4)利用编写文件求解某无约束最优化问题;

5)给出程序注释。指导教师年月日负责教师年月日学生签字年月日沈阳航空航天大学课程设计成绩评定单课程名称最优化理论与算法课程设计院(系) 理学院专业信息与计算科学课程设计题目共轭梯度法算法分析与实现学号 2011041401011 姓名黄中武指导教师评语: 课程设计成绩指导教师签字年月日最优化方法课程设计沈阳航空航天大学课程设计用纸目录目录一、正文 (1) 二、总结 ............................................................... 8 参考文献 ............................................................... 9 附录 .. (10) 第 I 页最优化方法课程设计沈阳航空航天大学课程设计用纸正文一、正文一无约束最优化问题的共轭梯度法

最小重量算法设计

最小重量机器设计问题一、实验目的 1、了解回溯法和分支限界法的基本思想。 2、运用回溯法和分支限界法解决最小重量机器设计问题。二、实验要求最小重量机器设计问题：设某一机器由n个部件组成，每一种部件可以从m个不同的供应商处购得。设w ij是从供应商j处购得的部件i的重量，c ij是相应的价格。试设计一个算法，给出总价格不超过c的最小重量机器设计。分别用回溯法和分支限界法实现问题的算法。三、算法思想和实现 1、回溯法（1）此问题是一棵排列树，设开始时bestx=[-1,-1,……,-1]则相应的排列树由x[0:n-1]的所有排列构成。（2）找最小重量机器设计的回溯算法Backtrack是类machine的公有成员。私有数据成员整型数组Savex保存搜索过的路径，到达叶节点后将数据赋值给数组bestx。成员bestw记录当前最小重量，cc表示当前花费，cw表示当前的重量。（3）在递归函数Backtrack中，在保证总花费不超过c的情况下：当i=n时，当前扩展结点是排列树的叶节点。此时搜索到一个解，判断此时的最小重量是否小于当前最小重量，若小于则更新bestw，并得到搜索路径bestx。当i using namespace std; #define N 3 #define M 3 int w[N][M]={{1,2,3},{3,2,1},{2,2,2}}; int c[N][M]={{1,2,3},{3,2,1},{2,2,2}}; class machine {public:

最优化方法课程设计

湖南****大学课程设计资料袋理学院学院（系、部）2013-2014 学年第一学期课程名称最优化方法指导教师黄力职称讲师学生姓名**** 专业班级数学与应用数学101班学号********** 学生姓名**** 专业班级数学与应用数学101班学号********* 学生姓名**** 专业班级数学与应用数学101班学号********* 题目最优化方法成绩起止日期2013 年12 月16 日～2013 年12 月23 日目录清单序号材料名称资料数量备注 1 课程设计任务书 1 2 课程设计说明书 1 3 附件：课程设计主要模块实现代码 1 张4 5 6

湖南******大学课程设计任务书 2013—2014 学年第1学期理学院学院（系、部）数学与应用数学专业101 班课程名称：最优化方法设计题目：求解各类最优化问题完成期限：自2013 年12 月16 日至2013 年12月23 日共 1 周任务及内容设计的任务：1、掌握Lingo和Matlab软件的相关知识； 2、熟练掌握相关Lingo和Matlab语句的编辑和运用； 3、运用所学最优化方法知识完成对各类最优化问题的求解。内容包括：求解各类最优化问题，包括：铁板问题、配棉问题、连续投资问题、销售问题、整数规划模型。进度安排起止日期工作内容 2013.12.16~2013.12.17 查找资料并分析 2013.12.18~2013.12.20 列出不等式算法，实现相关算法并运算相关程序2013.12.21~2013.12.22 整理所解决的问题的相关资料 2013.12.23 完成课程设计报告主要参考资料[1]蒋邵忠.线性规划与网络优化.杭州：浙江大学出版社，1992. [2]赵凤治，周继英.约束最优化计算方法.北京：科学出版社，1991. [3]施光燕，钱伟懿，庞丽萍.最优化方法.北京：高等教育出版社，2007.8 [4]林锉云，董加礼.多目标优化的方法和理论.长春：吉林教育出版社，1992. [5]张延华，许阳明.MATLAB使用指南.北京：科学技术文献出版社，1998. [6]施阳，李俊等.MATLAB语言工具箱——TOOLBOX实用指南.西安：西北工业大学出版社，1998. 指导教师（签字）：年月日系（教研室）主任（签字）：年月日

《算法分析与设计》期末试题及参考答案

《算法分析与设计》期末试题及参考答案一、简要回答下列问题： 1.算法重要特性是什么？ 1.确定性、可行性、输入、输出、有穷性 2. 2.算法分析的目的是什么？ 2.分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。 3. 3.算法的时间复杂性与问题的什么因素相关？ 3. 算法的时间复杂性与问题的规模相关，是问题大小n的函数。 4.算法的渐进时间复杂性的含义？ 4．当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。 5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？ 5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度： W(n) = max{ T(n，I) } , I∈Dn 平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和： A(n) =∑P(I)T(n，I) I∈Dn 6.简述二分检索（折半查找）算法的基本过程。 6. 设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较，如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2]

最优化方法课程设计-斐波那契法分析与实现-完整版(新)

所谓的光辉岁月，并不是以后，闪耀的日子，而是无人问津时，你对梦想的偏执。最优化方法题目：斐波那契法分析与实现院系：信息与计算科学学院专业：统计学姓名学号：小熊熊 11071050137 指导教师：大胖胖日期： 2014 年 01 月 10 日

摘要科学的数学化是当代科学发展的一个主要趋势，最优化理论与算法是一个重要的数学分支，它所研究的问题是讨论在众多的方案中什么样的方案最优以及怎样找出最优方案. 一维搜索是指寻求一元函数在某个区间上的最优点的方法.这类方法不仅有实用价值，而且大量多维最优化方法都依赖于一系列的一维最优化.本文就斐波那契法的一维搜索进行了详细的分析，并且成功的用 MATLAB 实现了斐波那契法求解单峰函数的极小值问题. 斐波那契法的一维搜索过程是建立在一个被称为斐波那契数列的基础上进行的，斐波那契法成功地实现了单峰函数极值范围的缩减.从理论上来说，斐波那契法的精度比黄金分割法要高.但由于斐波那契法要事先知道计算函数值的次数，故相比之下，黄金分割法更为简单一点，它不需要事先知道计算次数，并且当n 7 时，黄金分割法的收敛速率与斐波那契法越来越接近.因此，在实际应用中，常常采用黄金分割法. 斐波那契法也是一种区间收缩算法，和黄金分割法不同的是：黄金分割法每次收缩只改变搜索区间的一个端点，即它是单向收缩法. 而斐波那契法同时改变搜索区间的两个端点，是一种双向收缩法. 关键字：一维搜索斐波那契法单峰函数黄金分割法MATLAB

Abstract Mathematical sciences is a major trend in contemporary scientific development, optimization theory and algorithms is an important branch of mathematics, the problems it was discussed in numerous research programs in the best of what programs and how to find the optimal solution . One-dimensional search is the best method of seeking functions of one variable on the merits of a certain interval. Such methods not only have practical value, but also a large number of multi-dimensional optimization methods rely on a series of one-dimensional optimization article on Fibonacci the one-dimensional search method carried out a detailed analysis, and successful in MATLAB Fibonacci method for solving unimodal function minimization problem. Fibonacci method of one-dimensional search process is based on the Fibonacci sequence is called a Fibonacci conducted on, Fibonacci method successfully achieved a unimodal function extreme range reduction. Theory , Fibonacci method accuracy is higher than the golden section method, but the number of times due to the Fibonacci method to calculate function values to know in advance, so the contrast, the golden section method is more simply, it does not need to know in advance the number of calculations and at that time, the rate of convergence of golden section and the Fibonacci method getting closer, so in practical applications, often using the golden section method. Fibonacci method is also a range contraction algorithm, and the golden section method the difference is: golden section each contraction only one endpoint to change the search range that it is unidirectional shrinkage law Fibonacci search method while changing the two endpoints of the range, is a two-way contraction method. Key words: one-dimensional search Fibonacci method unimodal function Golden Section function MATLAB

最小重量机器设计问题+工作分配问题

一、算法实现题5-3 最小重量机器设计问题设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设w[i][j]是从供应商j处购得的部件i的重量，c[i][j]是相应的价格，给出总价格不超过d的最小重量机器设计。 1、解题说明这是一个最优规划问题，采用本章回溯法来求解。解空间是一个子集树，因此通过递归函数对解空间进行深度优先搜索，只要在当前结点，只要满足限定条件和限界条件，则递归下一层，否则就尝试下一个供应商。 Backtrack(1)实现对整个解空间的回溯搜索，Backtrack（i）搜索解空间中第i层子树。类Machine的数据成员记录界空间中结点信息。在算法Backtrack中，当i>n的时候，算法搜索至叶节点，得到一个新的可行解，与当前最优解进行比较，并更新最优值。当i<=n的时候，当前扩展结点是解空间中的内部结点。该结点有m个子节点。若满足当前总费用小于最大总费用，并且当前总重量小于最小总重量，那么以深度优先的方式递归地对可行子树进行搜索，或剪去不可行子树。 2、程序代码 #include #include using namespace std; class Machine{ //机器类 public: Machine(){ //构造函数 cw=cc=0; minw=1000; ifstream in("input.txt"); //从文件输入 in>>n>>m>>d; bestprovider=new int[m+1]; //初始化最优供应商和供应商数组 provider=new int[m+1]; c=new double*[n+1]; //创建部件价格二维数组 for(i=1;i<=n;i++) c[i]=new double[m+1]; for(i=1;i<=n;i++) //从文件读入价格 for(int j=1;j<=m;j++) in>>c[i][j]; w=new double*[n+1]; //创建部件重量二维数组 for(i=1;i<=n;i++)

《算法分析与设计》期末复习题

一、选择题 1．一个.java文件中可以有（）个public类。 A．一个B．两个C．多个D．零个 2．一个算法应该是（） A．程序B．问题求解步骤的描述 C．要满足五个基本特性D．A和C 3．用计算机无法解决“打印所有素数”的问题，其原因是解决该问题的算法违背了算法特征中的（）A．唯一性B．有穷性C．有0个或多个输入D．有输出 4．某校有6位学生参加学生会主席竞选，得票数依次为130，20，98，15，67，3。若采用冒泡排序算法对其进行排序，则完成第二遍时的结果是（） A．3，15，130，20，98，67B．3，15，20，130，98，67 C．3，15，20，67，130，98 D．3，15，20，67，98，130 5．下列关于算法的描述，正确的是（） A．一个算法的执行步骤可以是无限的B．一个完整的算法必须有输出 C．算法只能用流程图表示D．一个完整的算法至少有一个输入 6．Java Application源程序的主类是指包含有（）方法的类。 A、main方法 B、toString方法 C、init方法 D、actionPerfromed方法 7．找出满足各位数字之和等于5的所有三位数可采用的算法思路是（） A．分治法B．减治法C．蛮力法D．变治法 8．在编写Java Application程序时，若需要使用到标准输入输出语句，必须在程序的开头写上( )语句。 A、import java.awt.* ; B、import java.applet.Applet ; C、import java.io.* ; D、import java.awt.Graphics ; 9．计算某球队平均年龄的部分算法流程图如图所示，其中：c用来记录已输入球员的人数，sum用来计算有效数据之和，d用来存储从键盘输入的球员年龄值，输入0时表示输入结束。

最优化算法-第1次实验内容 ( 1 )

《最优化算法》实验指导书1 一、实验名称：Lingo软件的介绍及使用二、实验目的：熟悉LINGO软件的使用方法、功能，会求解一般线性规划问题和简单非线性规划模型。针对实际问题，会建立线性规划模型并求解。三、实验内容 1、熟悉LINGO软件的启动步骤。 2、熟悉LINGO软件的各菜单、命令按钮的作用。 3、学会如何使用LINGO的帮助文件。 4、学会输入线性规划模型和简单非线性规划模型的基本格式，并能看懂求解结果。四、实验步骤 1启动LINGO软件的步骤。当你在windows下开始运行LINGO系统时，会得到类似下面的一个窗口：外层是主框架窗口，包含了所有菜单命令和工具条，其它所有的窗口将被包含在主窗口之下。在主窗口内的标题为LINGO Model –LINGO1的窗口是LINGO的默认模型窗口，建立的模型都要在该窗口内编码实现。 LINGO包含了内置的建模语言，允许以简练、直观的方式描述较大规模的优化问题。模型中所需数据可以以一定的格式保存在独立的文件中。下面举两个例子。 2、示例：用LINGO求解线性规划 12 12 12 12 min z2x2x 2x5x12 s.t.x2x10 x,x0 =+ +≥ ? ? +≤ ? ?≥ ? 则在LINGO的模型窗口中输入如下代码：min=2*x1+2*x2; 2*x1+5*x2>=12;

x1+2*x2<=10; 注：（1）在输入目标函数时，因变量Z可不要输，只输“＝”及后面表达式；（2）用＊号表示乘号（3）每一个约束条件或目标函数后用分号“；”结束；（4）非负约束可以不要输入，软件默认变量是非负的。（5）可以用“！”开始写说明语句，但说明语句后也要用分号“；”结束。然后点击工具条上的运行图标，屏幕上出现 Rows= 3 Vars= 2 No. integer vars= 0 ( all are linear) Nonzeros= 8 Constraint nonz= 4( 1 are +- 1) Density=0.889 Smallest and largest elements in abs value= 1.00000 12.0000 No. < : 1 No. =: 0 No. > : 1, Obj=MIN, GUBs <= 1 Single cols= 0 (以上这段是对模型的描述) Optimal solution found at step（最优解在第1步被找到）: 1 Objective value（目标函数值）: 4.800000 （下列显示的是最优解） Variable(变量) Value（值） Reduced Cost （缩减成本系数） X1 0.0000000 1.200000 X2 2.400000 0.0000000 （下列显示的是松驰变量或剩余变量） Row Slack or Surplus Dual Price （行）（松弛变量或剩余变量）（检验数，对偶问题的解） 1 4.800000 -1.000000 2 0.0000000 -0.4000000 3 5.200000 0.0000000 结论：原规划的最优解是x1=0，x2=2.4；最优值为4.8 注释： Reduced cost 是指缩减成本系数，基变量的一定为0，对非基变量表示该变量每增加一个单位，目标函数值减少的量（对求解max的函数而言）。 Dual price 对偶价格，表示当对应的约束有微小变动时，目标函数的变化率。 3、LINGO软件的菜单命令（LINGO WINDOWS命令）（一）文件菜单（File Menu）（1）新建（New）从文件菜单中选用“新建”命令、单击“新建”按钮或直接按F2键可以创建一个新的“Model”窗口。在这个新的“Model”窗口中能够输入所要求解的模型。（2）打开（Open）从文件菜单中选用“打开”命令、单击“打开”按钮或直接按F3键可以打开一个已经存在的文本文件。这个文件可能是一个Model文件。（3）保存(Save) 从文件菜单中选用“保存”命令、单击“保存”按钮或直接按F4键用来保存当前活动窗口（最前台的窗口）中的模型结果、命令序列等保存为文件。

机械手设计汇总

第一章（第二章绪论课题研究的目的及意义随着工业自动化程度的提高，工业现场的很多易燃、易爆等高危及重体力劳动场合必将由机器人所代替。这一方面可以减轻工人的劳动强度，另一方面可以大大提高劳动生产率。例如，目前在我国的许多中小型汽车生产以及轻工业生产中，往往冲压成型这一工序还需要人工上下料，既费时费力，又影响效率。为此，我们把上下料机械手作为我们研究的课题。工业机械手是工业物流自动化中上网重要装置之一，是当今世界新技术革命的一个重要标志。工业机械手是典型的机电一体化产品。工业机械手的产生和推广是社会生产和发展的需要，也是现代生产和科技发展的新技术产品。工业机械手已经在工业生产、资源开发、社会服务、排险救灾以及军事技术等方面发挥着愈来愈大的应用。工业机械手的应用和推广已经并将获得极大的效益。例如在机械制造工业、汽车工业等生产中采用电焊、弧焊、喷漆等机械手，可以大大提高劳动生产率，保证产品质量，改善劳动条件。又如在微电子、医药等生产部门，采用机械手操作，可以消除人对产品的污染、确保产品质量。机械手可以在有毒、噪音、高温、易燃、易爆等危险有害的环境中代替人长期稳定的工作，从根本上解决了操作者的安全保障问题。因而在这方面应用和推广机器人技术是十分迫切和必要的。近代工业机械手的原型可以从本世纪40代算起。当时适应核技术的发展需要开发了处理放射性材料的主从机械手。50年代初美国提出了“通用重复操作机器人”的方案，59年研制出第一工业机械手原型。由于历史条件和技术水平关系，在60年代机械手发展较慢。进入70年代后，焊接、喷漆机械手相继在工业中应用和推广。随着计算机技术、控制技术、人工智能的发展、机械手技术得到迅速发展，出现了更为先进的可配视觉、触觉的机器人所应用的机械手。如美国Unimation公司PUMA系列工业机器人相关的机械手，即使由直流伺服驱动、关节式结构、多cpu微机控制、采用专用语言编程的技术先进的机械手。到了80、90年代机器人及相关的机械手开始在工业上普及应用。据统计1980年全世界约有两万台机器人在工业上应用，而到今年增长更快。今年已近开发出

机械优化设计实例

机械优化设计实例压杆的最优化设计压杆是一根足够细长的直杆，以学号为p值，自定义有设计变量的尺寸限制值，求在p一定时d1、d2和l分别取何值时管状压杆的体积或重量最小？（内外直径分别为d1、d2）两端承向轴向压力，并会因轴向压力达到临界值时而突然弯曲，失去稳定性，所以，设计时，应使压应力不超过材料的弹性极限，还必须使轴向压力小于压杆的临界载荷。解：根据欧拉压杆公式，两端铰支的压杆，其临界载荷为：I——材料的惯性矩，EI为抗弯刚度 1、设计变量现以管状压杆的内径d1、外径d2和长度l作为设计变量 2、目标函数以其体积或重量作为目标函数 3、约束条件以压杆不产生屈服和不破坏轴向稳定性，以及尺寸限制为约束条件，在外力为p的情况下建立优化模型： 1） 2）

3）罚函数：传递扭矩的等截面轴的优化设计解：1、设计变量： 2、目标函数

以轴的重量最轻作为目标函数： 3、约束条件： 1）要求扭矩应力小于许用扭转应力，即：式中：——轴所传递的最大扭矩 ——抗扭截面系数。对实心轴 2）要求扭转变形小于许用变形。即：扭转角：式中：G——材料的剪切弹性模数 Jp——极惯性矩，对实心轴： 3）结构尺寸要求的约束条件：若轴中间还要承受一个集中载荷，则约束条件中要考虑：根据弯矩联合作用得出的强度与扭转约束条件、弯曲刚度的约束条件、对于较重要的和转速较高可能引起疲劳损坏的轴，应采用疲劳强度校核的安全系数法，增加一项疲劳强度不低于许用值的约束条件。

二级齿轮减速器的传动比分配二级齿轮减速器，总传动比i=4，求在中心距A最小下如何分配传动比？设齿轮分度圆直径依次为d1、d2、d3、d4。第一、二级减速比分别为i1、i2。假设d1=d3,则：七辊矫直实验罚函数法是一种对实际计算和理论研究都非常有价值的优化方法，广泛用来求解约束问题。其原理是将优化问题中的不等式约束和等式约束加权转换后，和原目标函数结合成新的目标函数，求解该新目标函数的无约束极小值，以期得到原问题的约束最优解。考虑到本优化程序要处理的是一个兼而有之的问题，故采用混合罚函数法。一）、优化过程（1）、设计变量以试件通过各矫直辊时所受到的弯矩为设计变量：（2）、目标函数

最优化方法课程设计-斐波那契法分析与实现-完整版

最优化方法题目：斐波那契法分析与实现院系：信息与计算科学学院专业：统计学姓名学号：小熊熊 11071050137 指导教师：大胖胖日期： 2014 年 01 月 10 日

机械手设计

一、总体方案设计 1.1设计任务基本要求: 设计一个多自由度机械手（至少要有三个自由度）将最大重量为40Kg的工件，由车间的一条流水线搬到别一条线上；二条流水线的距离为：1000mm；工作节拍为：70s；工件：最大直径为160mm 的棒料； 1.2总体方案确定 1.2.1自由度自由度是指机器人所具有的独立坐标轴运动的数目，但是一般不包括手部（末端操作器）的开合自由度。自由度表示了机器人灵活的尺度，在三维空间中描述一个物体的位置和姿态需要六个自由度。机械手的自由度越多，越接近人手的动作机能，其通用性就越好，但是结构也越复杂，自由度的增加也意味着机械手整体重量的增加。轻型化与灵活性和抓取能力是一对矛盾，，此外还要考虑到由此带来的整体结构刚性的降低，在灵活性和轻量化之间必须做出选择。工业机器人基于对定位精度和重复定位精度以及结构刚性的考虑，往往体积庞大，负荷能力与其自重相比往往非常小。一般通用机械手有5～6个自由度即可满足使用要求（其中臂部有3个自由度，腕部和行走装置有2～3个自由度），专用机械手有1～2个自由度即可满足使用要求。在控制器的作用下，它执行将工件从一条流水线拿到另一条流水线这一动作。在满足前提条件上尽量使结构简单，所以我们这次选择5自由度机械手。 1.2.2机械手基本形式的选择常见的工业机械手根据手臂的动作形态,按坐标形式大致可以分为以下4种: (1)直角坐标型机械手：

特点：操作机的手臂具有三个移动关节，其关节轴线按直角坐标配置。优缺点：结构刚度较好，控制系统的设计最为简单，但其占空间较大，且运动轨迹单一，使用过程中效率较低。结构图： (2)圆柱坐标型机械手：特点：操作机的手臂至少有一个移动关节和一个回转关节，其关节轴线按圆柱坐标系配置。优缺点：结构刚度较好，运动所需功率较小，控制难度较小，但运动轨迹简单，使用过程中效率不高。结构图：