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

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

2、x1+10*x2<=60;x1-2*x2+d1_-d 仁0;4*x1+4*x2+d2_-d2=36;6x1+8*x2+d3_-d3=48;-d 1=0;d2=0;end運(yùn)行結(jié)果：d3=0;X1X24.8000002.400000二、動(dòng)態(tài)規(guī)劃之0-1背包問題1、 題目：給定n種物品和一背包。物品i的重量是 Wi，其價(jià)值為 Vi，背包的容量是 c，問應(yīng) 如何選擇裝入背包中的物品，使得裝入背包中物品的總價(jià)值最大。2、 解題方法與思路：利用java求解，.思想方法是回溯思想3、需求分析對(duì)于給定n種物品和一背包。在容量最大值固定的情況下，要求裝入的物品價(jià)值最大化4、java源程序與運(yùn)行結(jié)果Back

3、Trace.java* To cha nge this template, choose Tools | Template Man ager* and ope n 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;kn apsack(v,w,c);Sys

4、tem.out.pri ntln( bestp);/ 比擬兩個(gè)元素大小的類private static class Eleme nt impleme nts Comparable int id;double d;private Eleme nt(i nt idd,double dd) id=idd;d=dd;public int compareTo(Object x) double xd=(Eleme nt)x).d; if(d<xd)retur n -1; if(d=xd)retur n 0;return 1;public boolea n equals(Object x) retur

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

6、double kn apsack(doublepp,doubleww,double cc) c=cc;n=ppen gth-1;cw=0.0;cp=0.0;bestp=0.0;Eleme ntq=new Eleme nt n;/q為單位重量?jī)r(jià)值數(shù)組for(i nt i=1;i<=n ;i+)qi-1=new Eleme nt(i,ppi/wwi);MergeSort.mergeSort(q);p=new double n+1; w=new double n+1;x=new intn+1;sortX=new in t n+1;bestX=new intn +1;for(i nt i=1;i

7、<=n ;i+)pi=ppq n-i.id;wi=wwq n-i.id; sortXi=q n-i.id;backtrack(1);/回溯搜索return bestp;private static void backtrack(i nt i)if(i>=n)if(cp>bestp) bestp=cp;for(i nt j=1;j<=n ;j+) bestXj=xj; return;/搜索子樹if(cw+wi<=c)/進(jìn)入左子樹xsortXi=1;cw+=wi;cp+=pi;backtrack(i+1);cw-=wi;cp-=pi;if(bou nd(i+1)>

8、;bestp)xsortXi=0;backtrack(i+1);/進(jìn)入右子樹/計(jì)算上界private static double boun d(i nt i)double cleft=c-cw;double boun d=cp;/以物品重量?jī)r(jià)值遞減順序裝入物品while(i<=n&&wi<=cleft)cleft-=wi; boun d+=pi;i+;/裝滿背包if(i<=n)bou nd+=pi/wi*cleft;retur n bound;public static Stri ng getX()Stri ng solutio n=Stri ng.value

9、Of(bestX1);for(i nt i=2;i<bestX.le ngth;i+)soluti on+=","solutio n+=Stri ng.valueOf(bestXi);retur n soluti on;public static double getBestValue()return bestp;三、最短路徑問題：給定距離矩陣，求第一點(diǎn)到其它點(diǎn)的最短距離1題目：給定以下矩陣，求第一點(diǎn)到其余各點(diǎn)的最短路徑0504025105001520251501020402010010252520100551025255502、解題方法:利用matlab求解3、具體

10、步驟：源程序與運(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,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:le ngth(a)=0;pb(1)=1;d(1:le ngth (a) )=M;d(1)=0;temp=1;while sum(pb)<le ngth(a)tb=fi nd(pb=O);d(tb)=mi n(d(tb),d

11、(temp)+a(temp,tb);tmpb=fi nd(d(tb)=mi n(d(tb);temp=tb(tmpb(1);pb(temp)=1;end運(yùn)行輸出，第一個(gè)點(diǎn)到其它各點(diǎn)的最短路徑長(zhǎng)度，即:d = 035 45352510四、關(guān)鍵路徑問題1.題目要求：某工程由下表作業(yè)組成，計(jì)算出其關(guān)鍵路徑。作業(yè)方案完成時(shí)間緊前工作A5/B10/C11/D4BE4AF15CDG21BEH35BEI25BEJ15F,G,IK20FG2. 解題方法：用lingo求解3. LINGO源程序sets :eve nt/1.8/: et, lt;active(eve nt, eve nt)/! A B C D E

12、 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;en dsetsdata :d = 5 10 11 4 4 0 15 21 35 25 0 15 20; en ddatan=size (event);et=0;for (event(k) | k #gt# 1:et(k)= maXactive(i,k): et(i)+d(i,k);)；lt( n)=et( n);for (event(k) | k #lt# n:lt(k)= mi n(active(k,j): et(j)-d(k,j

13、););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天，作業(yè)在(1, 3), (3,5 ) , (5,6 )和(6,8 )位于關(guān)鍵路徑上。五、存儲(chǔ)問題1. 題目要求：某電器公司的生產(chǎn)流水線需要某種零件，該零件需要靠訂貨得到為此，該公司考慮到了如 下費(fèi)用結(jié)構(gòu)：(1) 批量訂貨的訂貨費(fèi)12000元/次；(2) 每個(gè)零件的單位本錢為10元/件； 每個(gè)零件的存貯費(fèi)用為 0.3元/ (件月); 每個(gè)零件的缺貨損失為1.1元/ (件月)。公司應(yīng)如何安排這些零件的訂貨時(shí)間與訂貨規(guī)模，使得

14、全部費(fèi)用最少？ 設(shè)該零件的每月需求量為800件.(1) 試求今年該公司對(duì)零件的最正確訂貨存貯策略與費(fèi)用；(2) 假設(shè)明年對(duì)該零件的需求將提高一倍，那么需零件的訂貨批量應(yīng)比今年增加多少？訂貨次 數(shù)以為多少？解：取一年為單位時(shí)間，由假設(shè)，訂貨費(fèi) CD = 12000元/次，存貯費(fèi) Cp= 3.6 (件年)，需求率D = 96000件/年，代入相關(guān)的公式得到：tc2CdD25298960002 1200 96000I360.2635252982CdCpD 2 3.6 12000 96000910732. LINGO源程序(1)MODEL:C_D = 12000;D = 96000;C_P = 3.6

15、;Q = (2*C_D*D/C_P)a0.5;T = Q/D;n = 1/T;TC = 0.5*C_P*Q+C_D*D/Q;END1 n = 3.7947全年的訂貨次數(shù)為T次sets:times/1.2/: n, Q, TC;en dsetsdata:n = 3, 4;C_D = 12000;D = 96000;C_P = 3.6;en ddatafor(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;en dse

16、tsfor(order(i):EOQ(i)=D/i;TC(i)=0.5*C_P*EOQ(i)+C_D*D/EOQ(i););TC_mi n=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;en ddataEND結(jié)果顯示：一年組織4次訂貨(每季度1次)，每次的訂貨量為 24 000件，最優(yōu)費(fèi)用為91200 元六、矩陣對(duì)策給定以下矩陣，求最優(yōu)決策1、題目：見書中 P337例72、 解題方法與思路：轉(zhuǎn)化為線性規(guī)劃問題，再用lin go求解3、具體步

17、驟：源程序與運(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>=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

18、*x4- x5>=0;x1+x2+x3+x4=0;end運(yùn)行輸出：對(duì)策值V=8七、排隊(duì)論1、解題步驟：第1步調(diào)查并收集和處理數(shù)據(jù)，記錄客戶到達(dá)時(shí)刻、等待時(shí)間和效勞時(shí)間假 定客戶到達(dá)的間隔時(shí)間服從指數(shù)分布(均值為10分鐘)；每個(gè)客戶的效勞時(shí)間服從均勻分布U10, 15。第2步構(gòu)造模擬模型輸人因素：客戶的到達(dá)間隔時(shí)間和效勞時(shí)間；排隊(duì)規(guī)那么： 先到先效勞；一個(gè)效勞機(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:10arrive=zeros(1, n);for i=2:narrive(i)=arrive(i-1)+exprnd(0.1);endwait=zeros(1, n);for i=1:nif (i=1)wait(i)=0;elseservetime=u nifrn d(10,15);if (arrive(i-1)+servetime+wait(i-1)>arrive(i)wait(i)=arrive(i-1)+servetime+wait(i-1)-arrive(i);elsewait(i)=0;endendendmean time=mea n( wait) end運(yùn)行結(jié)果