最优化实例和matlab源程序.doc

最优化实例和matlab源程序
最优化平时作业

一、目标规划
1、题目：见书中例题P110例4
2、解题方法:利用Lingo求解
3、具体步骤
(1）.对应于第一优先等级，建立线性规划问题：
model:
min=-d1;
5*x1+10＊x2〈=60；
x1—2*x2+d1_-d1=0；
end
运行结果： —d1=0
（2）对应于第二优先等级,将—d1=0作为约束条件，建立线性规划问题：
min=d2_；
5＊x1+10*x2〈=60；
x1-2*x2+d1_—d1=0；
4＊x1+4＊x2+d2_-d2=36；
—d1=0;
end

运行结果：d2=0；
（3)。对应于第三优先等级,将-d1=0, -d1=0作为约束条件,建立线性规划问题:
min=d3_;
5＊x1+10*x2<=60;
x1—2*x2+d1_-d1=0;
4＊x1+4*x2+d2_—d2=36；
6x1+8＊x2+d3_-d3=48；
-d1=0；
d2=0；
end

运行结果： d3=0;
X1 4。800000
X2 2。400000

二、动态规划之0-1背包问题
1、题目：给定n种物品和一背包.物品i的重量是Wi，其价值为Vi，背包的容量是c，问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大.
2、解题方法与思路：利用java求解,.思想方法是回溯思想
3、需求分析
对于给定n种物品和一背包.在容量最大值固定的情况下，要求装入的物品价值最大化
4、java源程序及运行结果
BackTrace。java

＊ To change this template， choose Tools | Template Manager
＊ and open the template in the editor。
*/

package sunfa;

import java。util。Date；

public class BackTrace ｛

/*＊
* @param args
*/
public static void main(String［］ args) ｛
double w[]=｛2，2，6，5，4};
double v［]=｛6,3,5，4,6｝;
int n=5;
double c=10；
knapsack（v，w,c);
System。out。println(bestp)；

}
//比较两个元素大小的类
private static class Element implements Comparable{
int id;
double d;

private Element(int idd，double dd)｛
id=idd;
d=dd；
}

public int compareTo（Object x）{
double xd=((Element）x).d;
if(d〈xd)return -1;
if（d==xd)return 0；
return 1;
｝
public boolean equals（Object x）{
return d==（(Element）x)。d；
｝
｝

static double c； //背包容量
static int n;//物品数
static double[]w;//物品重量数组
static double［］p； //物品价值数组
static double cw;//当前重量
static double cp;//当前价值
static double bestp; //当前最优值
static int ［] x;//解
static int [］ sortX；//排好序之后的解
static int ［］ bestX;//最有解

static Date date = null; // ＠jve:decl-index=0:

public static double knapsack（double［]pp，double［]ww，double cc）｛

c=cc；
n=pp.length—1；
cw=0.0；
cp=0。0;
bestp=0.0；

Element[]q=new Element［n];
//q为单位重量价值数组
for(int i=1;i<=n;i++）
q[i—1］=new Element(i，pp[i]/ww［i］);

MergeSort.mergeSort(q）;

p=new double[n+1］;
w=new double［n+1];
x=new int［n+1]；
sortX=new int[n+1］;
bestX=new int［n+1］；
for(int i=1;i〈=n；i++){
p[i］=pp[q[n—i].id］;
w［i]=ww[q［n-i]。id]；
sortX［i］=q[n—i］。id;
}

backtrack(1);//回溯搜索

return bestp；
｝

private static void backtrack(int i)｛
if（i>=n){
if（cp>bestp)｛
bestp=cp;

for（int j=1；j〈=n；j++)｛
bestX［j]=x［j]；
｝
｝
return;
｝
//搜索子树
if(cw+w［i]<=c）{
//进入左子树
x[sortX［i］]=1;
cw+=w［i］；
cp+=p[i];
backtrack（i+1)；
cw-=w[i];
cp—=p［i］；

}
if（bound（i+1）〉bestp)
x［sortX[i］］=0；
backtrack（i+1)；//进入右子树
｝
//计算上界
private static double bound（int i)｛
double cleft=c—cw;
double bound=cp；
//以物品重量价值递减顺序装入物品
while(i〈=n＆＆w［i］〈=cleft){
cleft—=w［i];
bound+=p［i］;i++;

}
//装满背包
if（i〈=n）
bound+=p［i]/w[i]*cleft;
return bound；
｝
public static String getX（）｛
String solution=String.valueOf（bestX[1］）；
for(int i=2;i〈bestX.length;i++）｛
solution+=”,”；
solution+=String。valueOf（bestX［i])；
｝
return solution;
}
public static double getBestValue()｛

return bestp;
}

｝

三、最短路径问题：给定距离矩阵，求第一点到其它点的最短距离
1、题目：给定下列矩阵，求第一点到其余各点的最短路径

2、解题方法:利用matlab求解
3、具体步骤：源程序及运行结果
clear;
clc;
M=10000;
a(1，：）=[0，50,M，40,25，10];
a（2，:）=［zeros（1，2），15，20，M,25］；
a（3,:)=［zeros(1,3），10，20，M]；
a(4,:）=［zeros（1，4)，10,25］;
a（5，：)=[zeros(1，5）,55];
a(6，:)=zeros(1，6）;
a=a+a'；
pb(1:length(a)）=0；pb（1)=1;d(1:length(a))=M；d(1）=0;temp=1;
while sum（pb)<length（a)
tb=find（pb==0)；
d（tb）=min(d（tb）,d(temp)+a(temp，tb));
tmpb=find（d(tb）==min（d(tb))）；
temp=tb(tmpb（1)）；
pb(temp)=1;
end
运行输出，第一个点到其它各点的最短路径长度，即：
d = 0 35 45 35 25 10
四、关键路径问题
1。题目要求：
某工程由下表作业组成，计算出其关键路径。
作业
计划完成时间
紧前工作
A
5
/
B
10
/
C
11
/
D
4
B
E
4
A
F
15
CD
G
21
BE
H
35
BE
I
25
BE
J
15
F，G，I
K
20
FG
2。解题方法：用lingo求解
3。LINGO源程序
sets:
event/1。。8/: et， lt；
active（event， event）/
！ A B C D E 0 F G H I 0 J K;
1,2 1，3 1,4 3,4 2,5 3，5 4,6 5，6 5,8 5,7 6,7 7，8 6,8
/: d, tf， ff;
endsets
data：
d = 5 10 11 4 4 0 15 21 35 25 0 15 20;
enddata

n=＠size（event）；
et(1)=0;
@for(event（k) | k #gt# 1：
et（k）=@max（active(i,k）： et（i）+d(i，k）);
)；
lt（n）=et(n);
＠for（event（k) ｜ k ＃lt＃ n:
lt(k)=＠min（active（k，j): et(j）—d（k，j））;
)；
＠for（active（i，j）:
tf(i，j）=lt(j）-et(i)-d（i,j）;
ff（i，j)=et（j）—et(i)—d(i,j)；
）；

即项目的总工期为51天，作业在(1，3)，（3，5），（5,6）和（6,8）位于关键路径上。

五、存储问题
1．题目要求：
某电器公司的生产流水线需要某种零件，该零件需要靠订货得到．为此，该公司考虑到了如下费用结构：
（1） 批量订货的订货费12000 元／次;
(2） 每个零件的单位成本为 10 元／件；
（3) 每个零件的存贮费用为 0。3元／(件 · 月)；
（4) 每个零件的缺货损失为 1。1 元／（件 · 月）。
公司应如何安排这些零件的订货时间与订货规模，使得全部费用最少？
设该零件的每月需求量为800件．
（1）试求今年该公司对零件的最佳订货存贮策略及费用；
(2）若明年对该零件的需求将提高一倍，则需零件的订货批量应比今年增加多少?订货次数以为多少?
解：取一年为单位时间，由假设,订货费 CD ＝ 12000元／次,存贮费 Cp= 3。6 元／(件 · 年)，需求率 D = 96000件／年，代入相关的公式得到：

2。LINGO源程序
（1）MODEL:
C_D = 12000;
D = 96000;
C_P = 3.6；
Q = (2＊C_D＊D/C_P)^0。5;
T = Q/D；
n = 1/T;
TC = 0。5＊C_P＊Q+C_D＊D/Q;
END
全年的订货次数为次
(2)
sets：
times/1.。2/: n, Q, TC;
endsets
data:
n = 3， 4;
C_D = 12000;
D = 96000；
C_P = 3.6；
enddata
＠for（times:
n = D/Q；
TC=0.5＊C_P*Q+C_D＊D/Q；
）；
END
结果输出：全年组织 4 次订货更好一些，每季度订货一次，每次订货 24000件。
程序：
(3)
MODEL:
sets:
order/1.。99/: TC, EOQ；
endsets
＠for(order(i):
EOQ(i）=D/i;
TC(i）=0.5＊C_P*EOQ(i)+C_D＊D/EOQ(i）；
）;
TC_min=@min（order: TC);
Q=＠sum（order（i）: EOQ(i）*（TC_min #eq＃ TC（i））)；
N=D/Q;
data:
C_D = 12000；
D = 96000;
C_P = 3。6;
enddata
END
结果显示：一年组织 4 次订货（每季度 1 次），每次的订货量为 24 000件，最优费用为 91200 元

六、矩阵对策给定下列矩阵，求最优决策
1、题目：见书中P337例7
2、解题方法与思路:转化为线性规划问题，再用lingo求解
3、具体步骤：源程序及运行结果
（1）求X（lingo源程序)
min=x5;
9＊x1+2＊x2+5*x3+10*x4—x5>=0;
8＊x1+4＊x2+8＊x3+7*x4-x5>=0;
11*x1+6*x2+7*x3+9＊x4—x5〉=0;
8＊x1+3＊x2+8*x3+6*x4- x5>=0；
x1+x2+x3+x4=0；
end
（2）求Y（lingo源程序）
max=x5；
9*x1+8*x2+11＊x3+8*x4—x5>=0；
2*x1+4*x2+6*x3+3*x4—x5〉=0;
5＊x1+8＊x2+7*x3+8*x4—x5〉=0；
10＊x1+7＊x2+9*x3+6*x4- x5>=0;
x1+x2+x3+x4=0；
end
运行输出:对策值V=8
七、排队论
1、解题步骤：
第1步 调查并收集和处理数据，记录客户到达时刻、等待时间和服务时间．假定客户到达的间隔时间服从指数分布（均值为10分钟）；每个客户的服务时间服从均匀分布U[10,15]。
第2步 构造模拟模型．输人因素：客户的到达间隔时间和服务时间；排队规则:先到先服务;一个服务机构。
第3步 模拟实验。设置模拟时钟及总的运行时间T,如8小时等。推进原则按下次事件推进或均匀间隔推进。

2、用MATLAB编制程序如下：
for n=1：10
arrive=zeros(1,n）；
for i=2:n
arrive(i）=arrive（i—1)+exprnd(0.1）；
end
wait=zeros（1,n)；
for i=1：n
if (i==1)
wait（i)=0;
else
servetime=unifrnd（10，15）；
if (arrive(i—1)+servetime+wait（i—1)〉arrive（i)）
wait（i)=arrive（i—1）+servetime+wait(i-1)-arrive（i）；
else
wait(i）=0；
end
end
end
meantime=mean(wait)
end

运行结果
meantime =
0
meantime =
7。2542
meantime =
12.1298
meantime =
20.0985
meantime =
26。8833
meantime =

32.5758
meantime =

37。2478
meantime =

43.6372
meantime =

51.4519
meantime =

59.4032

〉>计算的一组结果如下表:

客户数目
0
1
2
3
4
平均等待时间
0
5.5753
14.1838
18。9329
28.0946
客户数目
5
6
7
8
9
平均等待时间
28.1320
38.2700
40。8833
50。5942
59。3735