当前位置:文档之家› 单纯形法程序

单纯形法程序

单纯形法程序
单纯形法程序

/*单纯形法程序*/

/*p46--5(2)*/

#include "stdio.h"

main()

{

int i,j,r,k,l,jj[4],m=4,n=7,maxjj,mini,count=0;

float

a[4][7]={{0,2,-1,1,0,0,0},{60,3,1,1,1,0,0,},{10,1,-1,2,0,1,0},{20,1, 1,-1,0,0,1}};

float

b[4][4],e[4][4],t[4][4],y[4],maxcj,tb[4],tp[4],cb[4],cj[7],theta,lk,z; jj[1]=4;jj[2]=5;jj[3]=6;

for(i=0;i

for(j=0;j

b[i][j]=0.0;

for(i=1;i

printf("*********************************\n");

for(i=0;i

{ for(j=0;j

printf("%6.1f",a[i][j]);printf("\n");}

for(i=1;i

for(j=1;j

{ y[j]=0.0;

for(i=1;i

for(j=1;j

{

for(r=1;r

if(jj[r]==j){cj[j]=0.0;break; }

cj[j]=a[0][j];

for(i=1;i

}

maxcj=cj[1]; maxjj=1;

for(j=2;j

if(maxcj

{ maxcj=cj[j]; maxjj=j;}

k=maxjj;

for(j=1;j0)

{ count++;

for(i=1;i

{ tb[i]=0.0;

for(r=1;r

for(i=1;i

{ tp[i]=0.0;

for(r=1;r

/*for(i=1;i

for(i=1;i

printf("tb--tp\n"); */

theta=1000.0;

for(j=1;j

{ if(tp[j]>0)

if (theta>tb[j]/tp[j])

{ theta=tb[j]/tp[j]; mini=j;}

}

/* printf("LLL=%d Theta=%f\n",mini,theta); */

l=mini;

lk=tp[l];

jj[l]=k;

printf("*********************************\n");

for(i=0;i

for(j=0;j

e[i][j]=0.0;

for(i=1;i

for(i=1;i

e[l][l]=1.0/lk;

for(i=1;i

{ for(j=1;j

for(j=1;j

{ t[i][j]=0.0;

for(r=1;r

for(i=1;i

{ for(j=1;j

{ b[i][j]=t[i][j];

printf("%6.1f",b[i][j]);}

printf(" x%d\n",jj[i]);

}

for(i=1;i

for(j=1;j

{ y[j]=0.0;

for(i=1;i

for(j=1;j

{

for(r=1;r

if(jj[r]==j){cj[j]=0.0;break; }

cj[j]=a[0][j];

for(i=1;i

}

maxcj=cj[1]; maxjj=1;

if(maxcj

{ maxcj=cj[j]; maxjj=j;}

k=maxjj;

for(j=1;j

}

for(i=1;i

{ tb[i]=0.0;

for(r=1;r

z=0.0;

for(i=1;i

{ cb[i]=a[0][jj[i]];

printf(" x%d=%6.1f\n",jj[i],tb[i]);

z+=tb[i]*cb[i];}

printf(" Max_z=%5.1f THE_count=%d\n",z,count);

}

/*p37--li1-13*/

#include "math.h"

#include "stdio.h"

main()

{

int i,j,r,k,l,jj[4],m,n,maxjj,mini,count=0;

float

b[4][4],e[4][4],t[4][4],y[4],maxcj,tb[4],tp[4],cb[4],cj[7],theta,lk,z; float

a[4][6]={{0,700,1200,0,0,0},{360,9,4,1,0,0,},{200,4,5,0,1,0},{300, 3,10,0,0,1}};

m=4;n=6;

jj[1]=3;jj[2]=4;jj[3]=5;

for(j=0;j

b[i][j]=0.0;

for(i=1;i

printf("*********************************\n");

for(i=0;i

{ for(j=0;j

printf("%6.1f",a[i][j]);printf("\n");}

for(i=1;i

for(j=1;j

{ y[j]=0.0;

for(i=1;i

for(j=1;j

{

for(r=1;r

if(jj[r]==j){cj[j]=0.0;break; }

cj[j]=a[0][j];

for(i=1;i

}

maxcj=cj[1]; maxjj=1;

for(j=2;j

if(maxcj

{ maxcj=cj[j]; maxjj=j;}

k=maxjj;

for(j=1;j

while(maxcj>0.0001)

{ count++;

for(i=1;i

{ tb[i]=0.0;

for(i=1;i

{ tp[i]=0.0;

for(r=1;r

/*for(i=1;i

for(i=1;i

printf("tb--tp\n"); */

theta=1000.0;

for(j=1;j

{ if(tp[j]>0)

if (theta>tb[j]/tp[j])

{ theta=tb[j]/tp[j]; mini=j;}

}

/* printf("LLL=%d Theta=%f\n",mini,theta); */

l=mini;

lk=tp[l];

jj[l]=k;

printf("*********************************\n");

for(i=0;i

for(j=0;j

e[i][j]=0.0;

for(i=1;i

for(i=1;i

e[l][l]=1.0/lk;

for(i=1;i

{ for(j=1;j

for(j=1;j

{ t[i][j]=0.0;

for(i=1;i

{ for(j=1;j

{ b[i][j]=t[i][j];

printf("%6.1f",b[i][j]);}

printf(" x%d\n",jj[i]);

}

for(i=1;i

for(j=1;j

{ y[j]=0.0;

for(i=1;i

for(j=1;j

{

for(r=1;r

if(jj[r]==j){cj[j]=0.0;break; }

cj[j]=a[0][j];

for(i=1;i

}

maxcj=cj[1]; maxjj=1;

for(j=2;j

if(maxcj

{ maxcj=cj[j]; maxjj=j;}

k=maxjj;

for(j=1;j

} /*while--end*/

for(i=1;i

{ tb[i]=0.0;

for(r=1;r

z=0.0;

for(i=1;i

{ cb[i]=a[0][jj[i]];

printf(" x%d=%6.1f\n",jj[i],tb[i]);

z+=tb[i]*cb[i];}

printf(" Max_z=%5.1f THE_count=%d\n",z,count);

}

/*p47--6(5)*/

#include "math.h"

#include "stdio.h"

main()

{

int i,j,r,k,l,jj[4],m,n,maxjj,mini,count=0,ok=0;

float

b[4][4],e[4][4],t[4][4],y[4],maxcj,tb[4],tp[4],cb[4],cj[8],theta,lk,z; float

a[4][8]={{0,-1,-1,3,0,0,-1000,-1000},{11,1,-2,1,1,0,0,0},{3,2,1,-4,0 ,-1,1,0},{1,1,0,-2,0,0,0,1}};

m=4;n=8;

jj[1]=4;jj[2]=6;jj[3]=7;

for(i=0;i

for(j=0;j

b[i][j]=0.0;

for(i=1;i

printf("*********************************\n");

for(i=0;i

{ for(j=0;j

printf("%6.1f",a[i][j]);printf("\n");}

for(i=1;i

for(j=1;j

{ y[j]=0.0;

for(i=1;i

for(j=1;j

{

for(r=1;r

if(jj[r]==j){cj[j]=0.0;break; }

cj[j]=a[0][j];

for(i=1;i

}

maxcj=cj[1]; maxjj=1;

for(j=2;j

if(maxcj

{ maxcj=cj[j]; maxjj=j;}

k=maxjj;

for(j=1;j

while(maxcj>0.001&&count<5)

{ count++;

for(i=1;i

{ tb[i]=0.0;

for(r=1;r

for(i=1;i

{ tp[i]=0.0;

for(r=1;r

/*for(i=1;i

for(i=1;i

for(i=1;i

if (ok==-1)

{ printf("*** z\030 \354 ***\n");

return;} */

theta=1000.0;

for(j=1;j

{ if(tp[j]>0.01)

if (theta>tb[j]/tp[j])

{ theta=tb[j]/tp[j]; mini=j;}

}

/* printf("LLL=%d Theta=%f\n",mini,theta); */

l=mini;

lk=tp[l];

jj[l]=k;

printf("*********************************\n"); /* getchar();*/

for(i=0;i

for(j=0;j

e[i][j]=0.0;

for(i=1;i

for(i=1;i

e[l][l]=1.0/lk;

for(i=1;i

{ for(j=1;j

/* for(j=1;j

for(i=1;i

for(j=1;j

{ t[i][j]=0.0;

for(r=1;r

for(i=1;i

{ for(j=1;j

{ b[i][j]=t[i][j];

printf("%6.1f",b[i][j]);}

printf(" x%d\n",jj[i]);

}

for(i=1;i

for(j=1;j

{ y[j]=0.0;

for(i=1;i

for(j=1;j

{

for(r=1;r

if(jj[r]==j){cj[j]=0.0;break; }

cj[j]=a[0][j];

for(i=1;i

}

maxcj=cj[1]; maxjj=1;

for(j=2;j

if(maxcj

{ maxcj=cj[j]; maxjj=j;}

k=maxjj;

for(j=1;j

} /*while--end*/

for(i=1;i

{ tb[i]=0.0;

for(r=1;r

z=0.0;

for(i=1;i

{ cb[i]=a[0][jj[i]];

printf(" x%d=%6.1f\n",jj[i],tb[i]);

z+=tb[i]*cb[i];}

printf(" Max_z=%5.1f THE_count=%d\n",z,count);

}

/*p47---6(3)*/

#include "math.h"

#include "stdio.h"

main()

{

int i,j,r,k,l,jj[4],m,n,maxjj,mini,count=0;

float

b[4][4],e[4][4],t[4][4],y[4],maxcj,tb[4],tp[4],cb[4],cj[8],theta,lk,z; float

a[4][7]={{0,-4,-1,0,0,-1000,-1000},{3,3,1,0,0,1,0},{6,4,3,-1,0,0,1}, {4,1,2,0,1,0,0}};

m=4;n=7;

jj[1]=5;jj[2]=6;jj[3]=4;

for(i=0;i

for(j=0;j

b[i][j]=0.0;

for(i=1;i

printf("*********************************\n");

for(i=0;i

{ for(j=0;j

printf("%6.1f",a[i][j]);printf("\n");}

for(i=1;i

for(j=1;j

{ y[j]=0.0;

for(i=1;i

for(j=1;j

{

for(r=1;r

if(jj[r]==j){cj[j]=0.0;break; }

cj[j]=a[0][j];

for(i=1;i

}

maxcj=cj[1]; maxjj=1;

for(j=2;j

if(maxcj

{ maxcj=cj[j]; maxjj=j;}

k=maxjj;

for(j=1;j

while(maxcj>0.001)

{ count++;

for(i=1;i

{ tb[i]=0.0;

for(r=1;r

for(i=1;i

{ tp[i]=0.0;

for(r=1;r

/*for(i=1;i

for(i=1;i

printf("tb--tp\n"); */

theta=1000.0;

for(j=1;j

{ if(tp[j]>0.01)

if (theta>tb[j]/tp[j])

{ theta=tb[j]/tp[j]; mini=j;}

}

/* printf("LLL=%d Theta=%f\n",mini,theta); */

l=mini;

lk=tp[l];

jj[l]=k;

printf("*********************************\n"); /* getchar();*/

for(i=0;i

for(j=0;j

e[i][j]=0.0;

for(i=1;i

for(i=1;i

e[l][l]=1.0/lk;

for(i=1;i

{ for(j=1;j

/* for(j=1;j

for(i=1;i

for(j=1;j

{ t[i][j]=0.0;

for(r=1;r

for(i=1;i

{ for(j=1;j

{ b[i][j]=t[i][j];

printf("%6.1f",b[i][j]);}

printf(" x%d\n",jj[i]);

}

for(i=1;i

for(j=1;j

{ y[j]=0.0;

for(i=1;i

for(j=1;j

{

for(r=1;r

if(jj[r]==j){cj[j]=0.0;break; }

cj[j]=a[0][j];

for(i=1;i

}

maxcj=cj[1]; maxjj=1;

for(j=2;j

if(maxcj

{ maxcj=cj[j]; maxjj=j;}

k=maxjj;

for(j=1;j

} /*while--end*/

for(i=1;i

{ tb[i]=0.0;

for(r=1;r

z=0.0;

for(i=1;i

{ cb[i]=a[0][jj[i]];

printf(" x%d=%6.1f\n",jj[i],tb[i]);

z+=tb[i]*cb[i];}

printf(" Max_z=%5.1f THE_count=%d\n",z,count);

}

最优化实验报告(单纯形法的matlab程序,lingo程序)

实验一:线性规划单纯形算法 一、实验目的 通过实验熟悉单纯形法的原理,掌握Matlab 循环语句的应用,提高编程的能力和技巧。 二、实验用仪器设备、器材或软件环境 Windows Xp 操作系统 ,Matlab6.5,计算机 三、算法 对于一般的标准形式线性规划问题(求极小问题),首先给定一个初始 基本可行解。设初始基为B,然后执行如下步骤: (1).解B Bx b =,求得1 B x B b -=,0,N B B x f c x ==令计算目标函数值 1(1,2,...,)i m B b i -=i 以b 记的第个分量 (2).计算单纯形乘子w , B wB C =,得到1 B w C B -=,对于非基变量,计算判别数 1i i i B i i z c c B p c σ-=-=-,令 max{}k i i i R z c σ∈=-,R 为非基变量集合 若判别数0k σ≤ ,则得到一个最优基本可行解,运算结束;否则,转到下一步 (3).解k k By p =,得到 1 k k y B p -=;若0k y ≤,即k y 的每个分量均非正数,则停止计算,问题不存在有限最优解,否则,进行步骤(4). (4).确定下标r,使 { } :0 min ,0 t r rk tk tk b b tk y y t y y >=>且r B x 为离基变量。 k x 为进基变量,用k p 替换r B p ,得到新的基矩阵B ,返回步骤(1)。 对于极大化问题,可以给出完全类似的步骤,只是确定进基变量的准则不同。对于极大化问题,应令 min{}k k j j z c z c -=-

四、计算框图 是 否 是 否 开始 初始可行解B 令1,0,B N B B x B b b x f c x -==== 计算单纯形乘子1 B w c B -=,计算判别数,i j j wp c j R σ=-∈(非基变量) 令max{,}k j j R σσ=∈ 0?k σ≤ 得到最优解 解方程k k By p =,得到1k k y B p -=。 0?k y ≤ 不存在有限最优解 确定下标r ,是 { }:0 min ,0 t r rk tk tk b b tk y y t y y >=>且 k x 为进基变量,用 k p 替换r B p ,得到新的基矩阵B

C语言程序设计形考任务1答案

一、选择题(共40分,每小题2分) 题目1 在每个C语言程序中都必须包含有这样一个函数,该函数的函数名为()。选择一项: A. main B. MAIN C. name D. function 正确答案是:main 题目2 C语言源程序文件的缺省扩展名为()。 选择一项: A. cpp B. exe C. obj D. c 正确答案是:c 题目3 由C语言目标文件连接而成的可执行文件的缺省扩展名为()。 选择一项: A. cpp B. exe C. obj

正确答案是:exe 题目4 程序运行中需要从键盘上输入多于一个数据时,各数据之间应使用的分隔符为()。 选择一项: A. 空格或逗号 B. 逗号或回车 C. 逗号或分号 D. 空格或回车 正确答案是:空格或回车 题目5 每个C语言程序文件的编译错误被分为()。 选择一项: A. 1类 B. 2类 C. 3类 D. 4类 正确答案是:2类 题目6 不符合C语言规定的复合语句是()。 选择一项: A. {}

C. {x=0;} D. {y=10} 正确答案是:{y=10} 题目7 C语言程序中的基本功能模块为()。 选择一项: A. 表达式 B. 标识符 C. 语句 D. 函数 正确答案是:函数 题目8 在一个函数定义中,函数头包括的3个部分依次为函数类型、函数名和()。选择一项: A. 表达式 B. 语句 C. 参数表 D. 函数体 正确答案是:参数表 题目9 在一个程序文件中,若要使用#include命令包含一个用户定义的头文件,则此头文件所使用的起止定界符为一对()。

选择一项: A. 尖括号 B. 双引号 C. 单引号 D. 花括号 正确答案是:双引号 题目10 在C语言程序中,多行注释语句使用的开始标记符为()。 选择一项: A. // B. /* C. */ D. ** 正确答案是:/* 题目11 在printf()函数调用的格式字符串中,若使用格式符为“%c”,则对应输出的数据类型为()。 选择一项: A. char B. int C. float D. double 正确答案是:char

单纯形法matlab

数 学 软 件 与 实 验 数学与信息科学学院 信息与计算科学

单纯形法的Matlab程序如下:function [xx,fm]=myprgmh(m,n,A,b,c) B0=A(:,1:m); cb=c(:,1:m); xx=1:n; sgm=c-cb*B0^-1*A; h=-1; sta=ones(m,1); for i=m+1:n if sgm(i)>0 h=1; end end while h>0 [msg,mk]=max(sgm); for i=1:m sta(i)=b(i)/A(i,mk); end [mst,mr]=min(sta); zy=A(mr,mk); for i=1:m

if i==mr for j=1:n A(i,j)=A(i,j)/zy; end b(i)=b(i)/zy; end end for i=1:m if i~=mr for j=1:n A(i,j)=A(i,j)-A(i,mk)*A(mr,j); end b(i)=b(i)-A(i,mk)*b(mr); end end B1=A(:,1:m); cb(mr)=c(mk); xx(mr)=mk; sgm=c-cb*B1*A; for i=m+1:n if sgm(i)>0 h=1;

end end end fm=c*xx; 例题: 编写下列求解如下线性规划问题的单纯形法函数min f'x s.t ax<=b(其中b>=0) 函数形式function [x,fval,it,op]=singl(f,a,b) 输出中x为最优解 fval为最优值 it为迭代次数 无最优解op=0 有最优解op=1 编写程序如下: function [x,fval,it,op]=singl(f,a,b) [m,n]=size(a); c=[a eye(m) b;f' zeros(1,m+1)]; fval=0; x=zeros(m+n,1); op=1; it=0; e=zeros(1,m); lie=find(f<0); l=length(lie); while(l>0) for j=1:l d=find(c(:,lie(j)));

C语言程序设计形考任务3

一、选择题(共30分,每小题2分) 题目1 在下面的函数声明语句中,存在着语法错误的是()。 选择一项: a. AA(int a, int b) b. AA(int, int) c. AA(int a; int b) d. AA(int a, int) 正确答案是:AA(int a; int b) 题目2 在下面的保留字中,不能作为函数的返回值类型的是()。 选择一项: a. void b. int c. enum d. long 正确答案是:enum 题目3 假定p是一个指向float型数据的指针,则p+1所指数据的地址比p所指数据的地址增加的字节数为( )。 选择一项: a. 1 b. 2

c. 4 d. 8 正确答案是:4 题目4 假定a为一个数组名,在下面的表达式中,存在语法错误的是( )。 选择一项: a. a[i] b. *a++ c. *a d. *(a+1) 正确答案是:*a++ 题目5 用calloc函数创建具有10个整型元素的一维数组的正确语句是()。选择一项: a. int *p=calloc(10,2); b. int *p=calloc(10); c. int *p=calloc(10,4); d. int *p=malloc(10) 正确答案是:int *p=calloc(10,4); 题目6 假定变量m定义为“int m=7;”,则下面正确的语句为()。 选择一项: a. int p=&m;

b. int *p=&m; c. int &p=*m; d. int *p=m; 正确答案是:int *p=&m; 题目7 假定k是一个double类型的变量,则定义变量p的正确语句为()。 选择一项: a. double p=&k; b. int *p=&k; c. double &p=*k; d. char *p="Thank you!"; 正确答案是:char *p="Thank you!"; 题目8 若有语句为“int a[10], x, *pa=a;”,要把数组a中下标为3的元素值赋给x,则不正确的语句为()。 选择一项: a. x=pa[3]; b. x=*(a+3); c. x=a[3]; d. x=*pa+3; 正确答案是:x=*pa+3; 题目9 假定有语句为“int b[10]; int *pb;”,则下面不正确的赋值语句为()。

matlab单纯形法

%求解标准型线性规划:max c*x;s.t. A*x=b;x>=0 %本函数中的A是单纯初始表,包括:最后一行是初始的检验数,最后一列是资源向量b %N是初始的基变量的下标 %输出变量sol是最优解 %输出变量val是最优值,kk是迭代次数 function [sol,val,kk]=ssimplex(A,N) [mA,nA]=size(A); kk=0; %迭代次数 flag=1; while flag kk=kk+1; if A(mA,:)<=0 %已找到最优解 flag=0; sol=zeros(1,nA-1);%给每个变量赋初值0 for i=1:mA-1 sol(N(i))=A(i,nA);%给基变量赋新值(替换0) end %给出最优解 val=-A(mA,nA); else for i=1:nA-1 if A(mA,i)>0&A(1:mA-1,i)<=0 %问题有无界解 disp('have infinite solution!'); flag=0; break; end end if flag %还不是最优表,进行转轴运算 temp=0; for i=1:nA-1 if A(mA,i)>temp temp=A(mA,i); inb=i; % 进基变量的下标 end end %选择最大检验数纵向对应的变量为进基变量 sita=zeros(1,mA-1); for i=1:mA-1 if A(i,inb)>0 sita(i)=A(i,nA)/A(i,inb); end end temp=inf; for i=1:mA-1 if sita(i)>0&sita(i)

单纯形法matlab程序

算法实现与分析 算法1.单纯形法 具体算例: 标准化后: 用单纯形法求解,程序如下: clear clc M=1000000; A=[3,2,-3,1,0;1,-2,1,0,1];%系数矩阵 C=[-3,1,2,M,M,0];%价值矩阵 B=[6;4]; Xt=[4 5]; for i=1:length(C)-1 D=0; for j=1:length(Xt) D=D+A(j,i)*C(Xt(j)); end xi(i)=C(i)-D; end s=[]; for i=1:length(xi) if xi(i)<0 s=[s,i]; end end f=length(s); h=1; while(f) for k=1:length(s) j=1; A x=[]; for i=1:length(Xt) if A(i,s(k))>0 x(j)=i;

j=j+1; end end x if(length(x)+1==1) break; end y=1 x for i=1:length(x) if B(x(i))/A(x(i),s(k))

c语言程序设计形考任务二标准答案

c语言程序设计形考任务二答案

————————————————————————————————作者:————————————————————————————————日期:

一、选择题(共20分,每小题2分) 当处理特定问题时的循环次数已知时,通常采用的语句是()。 a. for b. while c. do-while d. switch 题目2 在switch语句的每个case块中,假定都是以break语句结束的,则此switch语句容易被改写成的语句是()。 a. for b. if c. do d. while 题目3 for语句能够被改写成的语句是()。 a. 复合 b. if c. switch

d. while 题目4 下面循环语句执行结束后输出的i值为()。 for(int i=0; in/2) {cout<

int i=0; do i++; while(i*i<10); a. 4 b. 3 c. 5 d. 2 题目7 在下面的一维数组定义中,有语法错误的选项是()。 a. int a[]={1,2,3}; b. int a[10]={0}; c. int a[]; d. int a[5]; 题目8 在下面的二维数组定义中,语法正确的选项是()。 a. int a[5][]; b. int a[][5]; c. int a[][3]={{1,3,5},{2}}; d. int a[](10);

单纯形法MATLAB程序

单纯形法(Matlab 程序) %%单纯形法( Matlab 程序) a=input('input the major matrix A '); b=input('input the matrix b '); n=input('input the judgement '); %%为计数器(确定循环次数) g=0; while g<40 %%确定非负 alength=max(size(n)); blength=max(size(b)); m=0; for i=1:alength if n(i)>=0 m=m+1; end end; if m==alength x=b; break end; %%找 K s=min(n); for i=1:alength if n(i)==s k=i; break end; end; %%a[i,k] 的非负性 m=0; for i=1:blength if a(i,k)<0 m=m+1; end; end; if m==blength

disp('x does not exit'); judge=1; break end; %%找 L 确定主元 cc=100000; for i=1:blength if a(i,k)>0 if (b(i)/a(i,k))< cc cc=b(i)/a(i,k); end end end; for i=1:blength if a(i,k)~=0 if (b(i)/a(i,k))==cc l=i; break end end end; %%计算 ,a 标准化 zu=a(l,k); aa=a; for i=1:l-1 for j=1:alength aa(i,j)=a(i,j)- a(l,j)*a(i,k)/a(l,k); end end; for i=l+1:blength for j=1:alength aa(i,j)=a(i,j)- a(l,j)*a(i,k)/a(l,k); end end; for j=1:alength aa(l,j)=a(l,j)/zu; end; %%b勺判别 bb=b; bb(l)=b(l)/zu; for i=1:l-1 bb(i)=b(i)- b(l)*a(i,k)/a(l,k); end; for i=l+1:blength bb(i)=b(i)- b(l)*a(i,k)/a(l,k); end; b=bb; %%确定判别数

运用Matlab进行线性规划求解(实例)

线性规划 线性规划是处理线性目标函数和线性约束的一种较为成熟的方法,目前已经广泛应用于军事、经济、工业、农业、教育、商业和社会科学等许多方面。 8.2.1 基本数学原理 线性规划问题的标准形式是: ????? ??????≥=+++=+++=++++++=0,,,min 21221122222121112 121112211n m n mn m m n n n n n n x x x b x a x a x a b x a x a x a b x a x a x a x c x c x c z 或 ???? ?????=≥===∑∑==n j x m i b x a x c z j n j i j ij n j j j ,,2,1,0,,2,1,min 1 1 写成矩阵形式为: ?? ???≥==O X b AX CX z min 线性规划的标准形式要求使目标函数最小化,约束条件取等式,变量b 非负。不符合这几个条件的线性模型可以转化成标准形式。 MATLAB 采用投影法求解线性规划问题,该方法是单纯形法的变种。 8.2.2 有关函数介绍 在MATLAB 工具箱中,可用linprog 函数求解线性规划问题。 linprog 函数的调用格式如下: ●x=linprog(f,A,b):求解问题minf'*x ,约束条件为A*x<=b 。 ●x=linprog(f,A,b,Aeq,beq):求解上面的问题,但增加等式约束,即Aeq*x=beq 。若没有不等式约束,则令A=[ ],b=[ ]。 ●x=linprog(f,A,b,Aeq,beq,lb,ub):定义设计x 的下界lb 和上界ub ,使得x 始终在该范围内。若没有等式约束,令Aeq=[ ],beq=[ ]。 ●x=linprog(f,A,b,Aeq,beq,lb,ub,x0):设置初值为x0。该选项只适用于中型问题,默认时大型算法将忽略初值。 ●x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options):用options 指定的优化参数进行最小化。 ●[x,fval]=linprog(…):返回解x 处的目标函数值fval 。 ●[x,lambda,exitflag]=linprog(…):返回exitflag 值,描述函数计算的退出条件。 ●[x,lambda,exitflag,output]=linprog(…):返回包含优化信息的输出参数output 。 ●[x,fval,exitflag,output,lambda]=linprog(…):将解x 处的拉格朗日乘子返回到lambda 参数中。

单纯形法基本原理

工程优化设计中单纯形法的基本原理 张云龙 (大连海洋大学土木工程学院辽宁大连116023) 摘要:从实例出发提出线性规划的数学模型,给出图解法的基本原理,进而重点讲述它的标准解法——单纯形法。在此基础上进一步讨论单纯形法的推广,即大M法和两相法。 关键词:线性规划图解法单纯形法大M法 THE BASIC PRINCIPLES OF SIMPLEX METHOD TO THE ENGINEERING OPTIMIZE DESIGN ZHANG Y un-long (Dalian Ocean University, College of Civil Engineering, Liaoning, Dalian 16023) Abstract: From the instance of the starting linear programming mathematical model of the basic principles of the graphic method, and then focus on the standard solution - simplex method. To promote further discussion on this basis, the simplex method, that is, the big M method and two-phase method. Key W ords: Linear programming;Graphic method;Simplex Method; Big M Method 1引言 在工程优化设计问题中,当约束集由一组线性函数所确定时,其最优化问题的求解已有比较系统的技巧。如果连目标函数也是线性的,也即线性规划问题,则是目前对规划问题研究最透彻最完善的一类问题,而且有比较成熟的解法。线性规划在工程实例中的应用已相当广泛。 虽然大多数设计问题是非线性的,但对线性规划的研究仍然占据突出地位。其原因是:有一部分实际问题,诸如运输问题,分配问题等,确实可以用线性规划问题来求解。尤为重要的是,对于几乎所有规划问题的讨论都与线性规划有关,有时用线性逼近法去直接求解非线性问题;有时则利用线性规划,作为求解在最优化过程中所提出的那些子问题的一个工具,例如,可用来求解可行方向法中的方向寻求问题等错误!未找到引用源。。 因此,深刻理解线性规划问题及其标准解法——单纯形法,显得尤为关键。 2线性规划问题 2.1数学模型 线性规划主要解决:如何利用现有的资源,使得预期目标达到最优。例如,美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试工序及每天可用于这两种家电的能力、各售出一件时的获利情况,如表1-1所示。问该公司应制造两种家电各多少件,使获取的利润最大? 表1-1 工时及利润简表

多目标线性规划的若干解法及MATLAB实现

多目标线性规划的若干解法及MATLAB 实现 一.多目标线性规划模型 多目标线性规划有着两个和两个以上的目标函数,且目标函数和约束条件全是线性函 数,其数学模型表示为: 11111221221122221122max n n n n r r r rn n z c x c x c x z c x c x c x z c x c x c x =+++??=+++?? ??=+++? (1) 约束条件为: 1111221121122222112212,,,0 n n n n m m mn n m n a x a x a x b a x a x a x b a x a x a x b x x x +++≤??+++≤?? ??+++≤?≥?? (2) 若(1)式中只有一个1122i i i in n z c x c x c x =+++ ,则该问题为典型的单目标线性规划。我们记:()ij m n A a ?=,()ij r n C c ?=,12(,,,)T m b b b b = ,12(,,,)T n x x x x = , 12(,,,)T r Z Z Z Z = . 则上述多目标线性规划可用矩阵形式表示为: max Z Cx = 约束条件:0 Ax b x ≤?? ≥? (3) 二.MATLAB 优化工具箱常用函数[3] 在MA TLAB 软件中,有几个专门求解最优化问题的函数,如求线性规划问题的linprog 、求有约束非线性函数的fmincon 、求最大最小化问题的fminimax 、求多目标达到问题的fgoalattain 等,它们的调用形式分别为: ①.[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub) f 为目标函数系数,A,b 为不等式约束的系数, Aeq,beq 为等式约束系数, lb,ub 为x 的下 限和上限, fval 求解的x 所对应的值。 算法原理:单纯形法的改进方法投影法 ②.[x,fval ]=fmincon(fun,x0,A,b,Aeq,beq,lb,ub ) fun 为目标函数的M 函数, x0为初值,A,b 为不等式约束的系数, Aeq,beq 为等式约束

国家开放大学电大《C语言程序设计》网络课形考任务3作业及答案

国家开放大学电大《C语言程序设计》网络课形考任务3作业及答案 形考任务3 一、选择题(共30分,每小题2分) 题目1 在下面的函数声明语句中,存在着语法错误的是()。 选择一项: a. AA(int a, int b) b. AA(int, int) c. AA(int a; int b) d. AA(int a, int) 题目2 在下面的保留字中,不能作为函数的返回值类型的是()。 选择一项: a. void b. int c. enum d. long 题目3 假定p是一个指向float型数据的指针,则p+1所指数据的地址比p所指数据的地址增加的字节数为( )。选择一项: a. 1 b. 2 c. 4 d. 8 题目4 假定a为一个数组名,在下面的表达式中,存在语法错误的是( )。 选择一项: a. a[i] b. *a++ c. *a d. *(a+1)

选择一项: a. int *p=calloc(10,2); b. int *p=calloc(10); c. int *p=calloc(10,4); d. int *p=malloc(10) 题目6 假定变量m定义为“int m=7;”,则下面正确的语句为()。 选择一项: a. int p=&m; b. int *p=&m; c. int &p=*m; d. int *p=m; 题目7 假定k是一个double类型的变量,则定义变量p的正确语句为()。 选择一项: a. double p=&k; b. int *p=&k; c. double &p=*k; d. char *p="Thank you!"; 题目8 若有语句为“int a[10], x, *pa=a;”,要把数组a中下标为3的元素值赋给x,则不正确的语句为()。选择一项: a. x=pa[3]; b. x=*(a+3); c. x=a[3]; d. x=*pa+3; 题目9 假定有语句为“int b[10]; int *pb;”,则下面不正确的赋值语句为()。 选择一项: a. pb=b; b. pb=&b[0];

实验二:MATLAB编程单纯形法求解

北京联合大学 实验报告 项目名称:运筹学专题实验报告 学院:自动化专业:物流工程 班级: 1201B 学号:2012100358081 姓名:管水城成绩: 2015 年 5 月 6 日

实验二:MATLAB 编程单纯形法求解 一、实验目的: (1)使学生在程序设计方面得到进一步的训练;,掌握Matlab (C 或VB)语言进行程序设计中一些常用方法。 (2)使学生对线性规划的单纯形法有更深的理解. 二、实验用仪器设备、器材或软件环境 计算机, Matlab R2006 三、算法步骤、计算框图、计算程序等 本实验主要编写如下线性规划问题的计算程序: ?? ?≥≥≤0 ,0..min b x b Ax t s cx 其中初始可行基为松弛变量对应的列组成. 对于一般标准线性规划问题: ?? ?≥≥=0 ,0..min b x b Ax t s cx 1.求解上述一般标准线性规划的单纯形算法(修正)步骤如下: 对于一般的标准形式线性规划问题(求极小问题),首先给定一个初始基本可行解。设初始基为B,然后执行如下步骤: (1).解B Bx b =,求得 1 B x B b -=,0,N B B x f c x ==令计算目标函数值 1(1,2,...,)i m B b i -=i 以b 记的第个分量 (2).计算单纯形乘子w, B wB C =,得到1 B w C B -=,对于非基变量,计算判别 数1i i i B i i z c c B p c σ-=-=-,可直接计算 σ =1 B A c c B --令 max{}k i R σσ∈=,R 为非基变量集合 若判别数0k σ≤ ,则得到一个最优基本可行解,运算结束;否则,转到下一 步 (3).解k k By p =,得到 1 k k y B p -=;若0k y ≤,即k y 的每个分量均非正数, 则停止计算,问题不存在有限最优解,否则,进行步骤(4).确定下标r,使 { }:0 min ,0 t r rk tk tk b b tk y y t y y >=>且r B x 为离基变量, ,r k B x p k 为进基变量,用p 替换得到新的基矩阵B,还回步骤(1) ;

C语言程序设计形考任务4

一、选择题(共30分,每小题2分) 题目1 假定有“ struct BOOK{chartitle[40]; float price;}; struct 则不正确的语句为( )。 选择一项: a. struct BOOK *x=malloc(book); b. struct BOOK x={"C++ Programmi ng",27.0}; c. struct BOOK *x=malloc(sizeof(struct BOOK)); d. struct BOOK *x=&book; 正确答案是:struct BOOK *x=malloc(book); 题目2 假定有“ struct BOOK{char title[40]; float price;} book; 句为( )。 选择一项: a. struct BOOK x= & book; b. struct BOOK *x=&book; c. struct BOOK x=calloc(BOOK); d. struct BOOK *x=BOOK; 正确答案是:struct BOOK *x=&book; 题目3 在结构类型的定义中,不同数据成员的定义项之间采用的分隔符是 选择一项: a. 句点 b. 冒号 c. 分号 d. 逗号 正确答案是:分号 题目4 假定一个结构类型的定义为“ struct A{i nt a,b; double c;}; 长度为( )。BOOKbook; ”,,贝M确的语,则该类型的

选择一项: a. 8 b. 10 c. 12 d. 16 正确答案是:16 题目5 假定一个结构类型的定义为“ struct D{i nt a; D* n ext;}; ”,则该类型的长度为()。 选择一项: a. 4 b. 8 c. 12 刁d. 16 正确答案是:8 题目6 假定要访问一个结构指针变量x中的数据成员a,则表示方法为()。 选择一项: a. x.a b. x->a c. x(a) d. x{a} 正确答案是:x->a 题目7 与结构成员访问表达式https://www.doczj.com/doc/0617548375.html,等价的表达式为()。 选择一项: a. x->n ame b. &x->n ame c. (&x)->n ame d. (*x)->n ame 正确答案是:(&x)-> name

单纯形法的matlab实现(20200814192014)

大连民族学院 数学实验报告 课程:____________________ 最优化方法______________________ 实验题目: ___________ 单纯形法的matlab实现 ___________________ 系别:______________________ 理学院________________________ 专业:__________________ 信息与计算科学____________________ 姓名:__________________________________________________ 班级:_____________________ 信息102班 ____________________ 指导教师:___________________ 葛仁东_______________________ 完成学期:2013 年__9 ___________ 月_2________ 日

实验目的: 实验方法和步骤(包括数值公式、算法步骤、程序) : 考察标准形式的线性规划问题: min f(x) C T x s.t Ax b, x 0 设x(k)F为一个基本可行解,单纯形方法首先检验它的最优性。如果它不是最优的,确定与该顶点相连的一条使目标函数下降的边;接下来确定沿这个边移

动多远可以到达另一个更优的相邻点,也就是得出一个新的基本可行解 算法步骤: 步骤1给定一个初始基本可行解,记迭代次数 k 1 ; 步骤2 :计算单纯形乘子y k B k T c B k)和简约价值系数向量C N k) c N k) N T y k ; 步骤3 :最优性检验,计算C?k) min{C (k)|j 2},如果C?k) 0,则x (k)为最优解, 停止迭代;否则有x p 0,选x p 为入基变量; 步骤4:确定出基变量,计算g k) B k 1a p ,如果对所有j B k ,有器)0,则问题 无有界的最优解,停止迭代;否则确定出基变量指标 步骤5:交换B k 的列a q 与N k 的列a p 得到新的基矩阵 盼和山+1,计算新的基本可 行解 x (k1),置k:k 1后转步骤 2; 在上述算法中,当存在不止一个简约价值系数 C j k) 0时,选取最负的?“的 指标为p ,并以X p 作为入基变量。 Matlab 计算程序: Function] x,f]=zuiyouhua(A,b,c) Size(A)=[m, n]; i=n+1: n+m; N=1: n; B=eye(m,m); xb=b '; xn=zeros(m,1); f1=0; w=zeros(1,m); z=-c; flag=1; while(1) [a,k]=max(z); If a<=0 flag=0; break else y=i nv(B)*A(:,k) b (k) B k }; min{ _(k )殆 0, j

C语言程序设计--形考任务2017全部答案

C语言程序设计形考任务1 题目1 在每个C语言程序中都必须包含有这样一个函数,该函数的函数名为()。选择一项: A. main B. MAIN C. name D. function 题目2 C语言源程序文件的缺省扩展名为()。 选择一项: A. cpp B. exe C. obj D. c 题目3 由C语言目标文件连接而成的可执行文件的缺省扩展名为()。 选择一项: A. cpp B. exe C. obj D. c

题目4 程序运行中需要从键盘上输入多于一个数据时,各数据之间应使用的分隔符为()。选择一项: A. 空格或逗号 B. 逗号或回车 C. 逗号或分号 D. 空格或回车 题目5 每个C语言程序文件的编译错误被分为()。 选择一项: A. 1类 B. 2类 C. 3类 D. 4类 题目6 在·()。 选择一项: A. {} B. {;} C. {x=0;} D. {y=10} 题目7

C语言程序中的基本功能模块为()。 选择一项: A. 表达式 B. 标识符 C. 语句 D. 函数 题目8 在一个函数定义中,函数头包括的3个部分依次为函数类型、函数名和()。 选择一项: A. 表达式 B. 语句 C. 参数表 D. 函数体 题目9 在一个程序文件中,若要使用#include命令包含一个用户定义的头文件,则此头文件所使用的起止定界符为一对()。 选择一项: A. 尖括号 B. 双引号 C. 单引号 D. 花括号 题目10

在C语言程序中,多行注释语句使用的开始标记符为()。 选择一项: A. // B. /* C. */ D. ** 题目11 在printf()函数调用的格式字符串中,若使用格式符为“%c”,则对应输出的数据类型为()。 选择一项: A. char B. int C. float D. double 题目12 在printf()函数调用的格式字符串中,若使用格式符为“%5d”,则规定对应输出的数据占用的字符位置个数为()。 选择一项: A. 5 B. 4 C. 3 D. 6

单纯形法matlab程序

function Z=dcxf(c,A,N) %定义函数名称为dcxf。 l=length(N); CB=c(N(1):N(l)) [m,n]=size(A); b=A(:,n); A=A(:,1:n-1); %参数包括目标函数系数(C),约束条件的系数矩阵(A), %其中A的最后一列为约束条件的右端值b,初始基向量的位置(N)。 sigma=c-CB*A;%计算检验数sigma。 display('初始单纯形表为:');%输出初始的单纯形表table=[nan,nan,nan,c;CB',N',b,A;nan,nan,nan,si gma] opt=1;step=0; while opt step=step+1;%定义循环,直到第“step”步找到最优解(opt=0)。 if sum(sigma>0)==0 %利用检验数判断是否得到最优解,并给出提示。 display('没有得到最优解,继续迭代.'); opt=0;

else inb=find(sigma==max(sigma)); %利用单纯形方法找到入基变量的位置 num=length(inb); Inb=inb(num) flag=0; for i=1:m %利用单纯形方法找出出基变量的位置 if A(i,inb)>0 theta(i)=b(i)/A(i,inb); else theta(i)=inf; end end outb=find(theta==min(theta)); num=length(outb); %判断足否出现退化现象,如出现退化,给il{语言提示,并取最后出现的符合出基条件的变量为出基变量。 if num~=1 display('出现退化情况.'); end outb=outb(num);

C语言程序设计形考任务

C语言程序设计形考任务Prepared on 21 November 2021

C语言程序设计形考任务1 题目1 在每个C语言程序中都必须包含有这样一个函数,该函数的函数名为 ()。 选择一项: A. main B. MAIN C. name D. function 题目2 C语言源程序文件的缺省扩展名为()。 选择一项: A. cpp B. exe C. obj D. c 题目3 由C语言目标文件连接而成的可执行文件的缺省扩展名为()。 选择一项: A. cpp B. exe C. obj D. c 题目4 程序运行中需要从键盘上输入多于一个数据时,各数据之间应使用的分隔符为()。 选择一项: A. 空格或逗号 B. 逗号或回车

C. 逗号或分号 D. 空格或回车 题目5 每个C语言程序文件的编译错误被分为()。 选择一项: A. 1类 B. 2类 C. 3类 D. 4类 题目6 不符合C语言规定的复合语句是()。 选择一项: A. {} B. {;} C. {x=0;} D. {y=10} 题目7 C语言程序中的基本功能模块为()。 选择一项: A. 表达式 B. 标识符 C. 语句 D. 函数 题目8 在一个函数定义中,函数头包括的3个部分依次为函数类型、函数名和()。 选择一项: A. 表达式 B. 语句

C. 参数表 D. 函数体 题目9 在一个程序文件中,若要使用#include命令包含一个用户定义的头文件,则此头文件所使用的起止定界符为一对()。 选择一项: A. 尖括号 B. 双引号 C. 单引号 D. 花括号 题目10 在C语言程序中,多行注释语句使用的开始标记符为()。 选择一项: A. /* C. */ D. ** 题目11 在printf()函数调用的格式字符串中,若使用格式符为“%c”,则对应输出的数据类型为()。 选择一项: A. char B. int C. float D. double 题目12 在printf()函数调用的格式字符串中,若使用格式符为“%5d”,则规定对应输出的数据占用的字符位置个数为()。 选择一项: A. 5 B. 4

单纯形法MATLAB程序

单纯形法(Mat lab程序) %%单纯形法(Mat lab程序)a= input (' input the major matrix A '); b=input (' input the matrix b '); n=input C input the judgement '); %%为计数器(确定循环次数) 萨0; while g<40 %%确定非负 alength=max(size(n)); blength二max(size(b)); m=0; for i=l:alength 辻n(i)〉=0 m二m+1; end end; if m==alength x=b; break end; %%找K s二min(n); for i=l:alength if n(i) ==s k二i; break end; end; %%a[i,k]的非负性 m=0; for i=l:blength if a(i, k)<0 m二m+1; end; end;

if m==blength

disp('x does not exit'); judge二1; break end; %%找L确定主元cc=100000; for i=l:blength if a (i, k) >0 if (b(i)/a(i, k))< cc cc=b(i)/a(i, k); end end end; for i=l:blength if a(i, k)~=0 if (b(i)/a(i, k))==cc 1二i; break end end end; %%计算,a 标准化zu=a(l, k); aa=a; for i=l:1-1 for j=l:alength aa(i, j)=a(i, j)- a(l, j)*a(i, k)/a(l, k); end end; for i=l+l:blength for j=l :alength aa(i, j)=a(i, j)- a(l, j)*a(i, k)/a(l, k); end end; for j=l:alength aa(l, j)=a(l, j)/zu; end; %%b 勺判别bb=b; bb(l)=b(l)/zu; for i=l: 1~1 bb(i)=b(i)~ b⑴*a(i, k)/a(l, k); end; for i=l+l:blength bb(i)二b(i)- b(l)*a(i, k)/a(l, k); end; b二bb; %%确定判别数

相关主题
相关文档 最新文档