最優(yōu)化實(shí)例和matlab源程序

1、最優(yōu)化平時(shí)作業(yè)一、目標(biāo)規(guī)劃1、題目：見(jiàn)書(shū)中例題P110例42、解題方法：利用Lingo求解3、具體步驟（1）.對(duì)應(yīng)于第一優(yōu)先等級(jí)，建立線性規(guī)劃問(wèn)題：model:min=-d1;5*x1+10*x2<=60;x1-2*x2+d1_-d1=0; end運(yùn)行結(jié)果： -d1=0（2）對(duì)應(yīng)于第二優(yōu)先等級(jí)，將-d1=0作為約束條件，建立線性規(guī)劃問(wèn)題：min=d2_;5*x1+10*x2<=60;x1-2*x2+d1_-d1=0; 4*x1+4*x2+d2_-d2=36; -d1=0;end 運(yùn)行結(jié)果：d2=0;（3）.對(duì)應(yīng)于第三優(yōu)先等級(jí)，將-d1=0, -d1=0作為約束條件，建立線性規(guī)劃問(wèn)題

2、：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運(yùn)行結(jié)果： d3=0;X1 4.800000 X2 2.400000 二、動(dòng)態(tài)規(guī)劃之0-1背包問(wèn)題1、題目：給定n種物品和一背包。物品i的重量是Wi，其價(jià)值為Vi，背包的容量是c，問(wèn)應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品的總價(jià)值最大。2、解題方法與思路：利用java求解，.思想方法是回溯思想3、需求分析對(duì)于給定n種物品和一背包。在容量最大值固定的情況下，要求裝入的物品價(jià)值最大化4、java

3、源程序及運(yùn)行結(jié)果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;knaps

4、ack(v,w,c);System.out.println(bestp); /比較兩個(gè)元素大小的類(lèi)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

5、 d=(Element)x).d;static double c; /背包容量static int n;/物品數(shù)static doublew;/物品重量數(shù)組static doublep; /物品價(jià)值數(shù)組static double cw;/當(dāng)前重量static double cp;/當(dāng)前價(jià)值static double bestp; /當(dāng)前最優(yōu)值static int x;/解static int sortX;/排好序之后的解static int bestX;/最有解 static Date date = null; / jve:decl-index=0:public static double k

6、napsack(doublepp,doubleww,double cc)c=cc;n=pp.length-1;cw=0.0;cp=0.0;bestp=0.0;Elementq=new Elementn; /q為單位重量?jī)r(jià)值數(shù)組for(int i=1;i<=n;i+)qi-1=new Element(i,ppi/wwi);MergeSort.mergeSort(q);p=new doublen+1;w=new doublen+1;x=new intn+1;sortX=new intn+1;bestX=new intn+1;for(int i=1;i<=n;i+)pi=ppqn-i.i

7、d;wi=wwqn-i.id;sortXi=qn-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+)bestXj=xj;return; /搜索子樹(shù)if(cw+wi<=c) /進(jìn)入左子樹(shù)xsortXi=1;cw+=wi;cp+=pi;backtrack(i+1);cw-=wi;cp-=pi;if(bound(i+1)>bestp)xsortXi=0;backtrack(i+

8、1);/進(jìn)入右子樹(shù)/計(jì)算上界private static double bound(int i)double cleft=c-cw;double bound=cp; /以物品重量?jī)r(jià)值遞減順序裝入物品while(i<=n&&wi<=cleft)cleft-=wi;bound+=pi;i+; /裝滿背包if(i<=n)bound+=pi/wi*cleft;return bound;public static String getX()String solution=String.valueOf(bestX1);for(int i=2;i<bestX.leng

9、th;i+)solution+=","solution+=String.valueOf(bestXi);return solution;public static double getBestValue()return bestp;三、最短路徑問(wèn)題：給定距離矩陣，求第一點(diǎn)到其它點(diǎn)的最短距離1、題目：給定下列矩陣，求第一點(diǎn)到其余各點(diǎn)的最短路徑2、解題方法：利用matlab求解3、具體步驟：源程序及運(yùn)行結(jié)果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、,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運(yùn)行輸出，第一個(gè)點(diǎn)到其它各點(diǎn)的最短路徑長(zhǎng)度，即： d

11、 = 0 35 45 35 25 10四、關(guān)鍵路徑問(wèn)題1.題目要求：某工程由下表作業(yè)組成，計(jì)算出其關(guān)鍵路徑。作業(yè)計(jì)劃完成時(shí)間緊前工作A5/B10/C11/D4BE4AF15CDG21BEH35BEI25BEJ15F,G,IK20FG2.解題方法：用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;endsetsdata: d =

12、5 10 11 4 4 0 15 21 35 25 0 15 20;enddatan=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););即項(xiàng)目的總工期為51天，作業(yè)在（1，3），（3,

13、5），（5,6）和（6,8）位于關(guān)鍵路徑上。五、存儲(chǔ)問(wèn)題1題目要求：某電器公司的生產(chǎn)流水線需要某種零件，該零件需要靠訂貨得到為此，該公司考慮到了如下費(fèi)用結(jié)構(gòu)：(1) 批量訂貨的訂貨費(fèi)12000 元次；(2) 每個(gè)零件的單位成本為 10 元件；(3) 每個(gè)零件的存貯費(fèi)用為 0.3元(件 · 月)；(4) 每個(gè)零件的缺貨損失為 1.1 元(件 · 月)。公司應(yīng)如何安排這些零件的訂貨時(shí)間與訂貨規(guī)模，使得全部費(fèi)用最少？設(shè)該零件的每月需求量為800件（1）試求今年該公司對(duì)零件的最佳訂貨存貯策略及費(fèi)用；（2）若明年對(duì)該零件的需求將提高一倍，則需零件的訂貨批量應(yīng)比今年增加多少？訂貨次數(shù)以

14、為多少？解：取一年為單位時(shí)間，由假設(shè)，訂貨費(fèi) CD 12000元次，存貯費(fèi) Cp= 3.6 元(件 · 年)，需求率 D = 96000件年，代入相關(guān)的公式得到：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全年的訂貨次數(shù)為次(2)sets:times/1.2/: n, Q, TC;endsetsdata: n = 3, 4; C_D = 12000; D = 96000; C_P = 3.

15、6; enddata for(times: n = D/Q; TC=0.5*C_P*Q+C_D*D/Q; );END結(jié)果輸出：全年組織 4 次訂貨更好一些，每季度訂貨一次，每次訂貨 24000件。程序：(3)MODEL:sets: order/1.99/: TC, EOQ; endsetsfor(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;

16、D = 96000; C_P = 3.6; enddataEND結(jié)果顯示：一年組織 4 次訂貨（每季度 1 次），每次的訂貨量為 24 000件，最優(yōu)費(fèi)用為 91200 元六、矩陣對(duì)策給定下列矩陣，求最優(yōu)決策1、題目：見(jiàn)書(shū)中P337例72、解題方法與思路：轉(zhuǎn)化為線性規(guī)劃問(wèn)題，再用lingo求解3、具體步驟：源程序及運(yùn)行結(jié)果（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&

17、gt;=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運(yùn)行輸出：對(duì)策值V=8七、排隊(duì)論1、解題步驟：第1步 調(diào)查并收集和處理數(shù)據(jù)，記錄客戶到達(dá)時(shí)刻、等待時(shí)間和服務(wù)時(shí)間假定客戶到達(dá)的間隔時(shí)間服從指數(shù)分布（均值為10分鐘）；每個(gè)客戶的服務(wù)時(shí)間服從均勻分布U10，15。第2步 構(gòu)造模擬模

18、型輸人因素：客戶的到達(dá)間隔時(shí)間和服務(wù)時(shí)間；排隊(duì)規(guī)則：先到先服務(wù)；一個(gè)服務(wù)機(jī)構(gòu)。第3步 模擬實(shí)驗(yàn)。設(shè)置模擬時(shí)鐘及總的運(yùn)行時(shí)間T，如8小時(shí)等。推進(jìn)原則按下次事件推進(jìn)或均勻間隔推進(jìn)。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;endendend meantime=mean(wait)end