單純形算法MATLAB編程報(bào)告

1、機(jī)械優(yōu)化設(shè)計(jì)課程作業(yè) 題 目： 單純形程序算法 學(xué) 院： 機(jī)電工程學(xué)院 專 業(yè)： 機(jī)械工程 姓 名： 璐穎 學(xué) 號(hào)： 2015020287 指導(dǎo)老師： 王 2016年 4 月 24 日基于MATLAB的單純形算法實(shí)現(xiàn)1. 算法簡述為求解下面線性規(guī)劃問題：其中初始可行基為松弛變量對(duì)應(yīng)的列組成. 對(duì)于一般標(biāo)準(zhǔn)線性規(guī)劃問題:求解上述一般標(biāo)準(zhǔn)線性規(guī)劃的單純形算法步驟如下：對(duì)于一般的標(biāo)準(zhǔn)形式線性規(guī)劃問題(求極小問題),首先給定一個(gè)初始基本可行解。設(shè)初始基為B,然后執(zhí)行如下步驟： (1).解,求得，(2).計(jì)算單純形乘子w, ,得到,對(duì)于非基變量，計(jì)算判別數(shù),可直接計(jì)算令 ,R為非基變量集合若判別數(shù) ,則

2、得到一個(gè)最優(yōu)基本可行解，運(yùn)算結(jié)束；否則，轉(zhuǎn)到下一步(3).解,得到；若,即的每個(gè)分量均非正數(shù)，則停止計(jì)算，問題不存在有限最優(yōu)解，否則，進(jìn)行步驟(4).確定下標(biāo)r,使2. 算法框圖初始化 初始可行基B 是 否 輸出結(jié)果，得到最優(yōu)解結(jié)束是否 不存在有限最優(yōu)解確定下標(biāo)r,使得 高斯迭代 3 計(jì)算程序Clear %清空工作區(qū)Clc %清空命令輸入框A=input('A=');b=input('b=');c=input('c=');format rat %可以讓結(jié)果用分?jǐn)?shù)輸出m,n=size(A); %取維數(shù) E=1:m;E=E' F=n-m+1:

3、n;F=F'D=E,F; %創(chuàng)建一個(gè)一一映射，為了結(jié)果能夠標(biāo)準(zhǔn)輸出X=zeros(1,n); %初始化Xif(n<m) %判斷是否為標(biāo)準(zhǔn)型 fprintf('不符合標(biāo)準(zhǔn)形式需引入松弛變量') flag=0;else flag=1; B=A(:,n-m+1:n); %找基矩陣 cB=c(n-m+1:n); %基矩陣對(duì)應(yīng)目標(biāo)值的c while flag w=cB/B %計(jì)算單純形乘子，cB/B=cB*inv(B),左除相當(dāng)于求逆 panbieshu=w*A-c %計(jì)算判別數(shù),后面沒有加分號(hào)，就是為了計(jì)算后能夠顯示出來 z,k=max(panbieshu) % k作為進(jìn)

4、基變量下標(biāo) fprintf('確定下標(biāo)并選擇進(jìn)基變量和離基變量為n',k); b'./(BA(:,k) %這個(gè)式子是為了確定進(jìn)基變量和離基變量的下標(biāo) if(z<0.) %為了使判別數(shù)盡可能趨近于零 flag=0; %所有判別數(shù)都小于0時(shí)達(dá)到最優(yōu)解 fprintf(' 已找到最優(yōu)解!n'); xB=(Bb')' f=cB*xB' for i=1:n mark=0; for j=1:m if (D(j,2)=i) mark=1; X(i)=xB(D(j,1) %利用D找出xB與X之間的關(guān)系 end end if mark=0 X

5、(i)=0; %如果D中沒有X(i),則X(i)為非基變量，所以X(i)0 end end fprintf('基向量為:'); X fprintf('目標(biāo)函數(shù)值為:') ; f else if(BA(:,k)<=0) % 如果BA(;,k)中的每一個(gè)分量都小于零 flag=0; fprintf(' n 此問題不存在最優(yōu)解!n'); %若BA(:,k)的第k列均不大于0，則該問題不存在最優(yōu)解 else b1=Bb' temp=inf; for i=1:m if (A(i,k)>0) && (b1(i)/(A(i,

6、k)+eps)<temp ) temp=b1(i)/A(i,k); %找離基變量 r=i; end end fprintf('x(%d)進(jìn)基，x(%d)離基n',k,D(r,2); %顯示進(jìn)基變量和離基變量 B(:,r)=A(:,k) cB(r)=c(k) %確定進(jìn)基離基變量后，相應(yīng)的基矩陣及新基對(duì)應(yīng)的目標(biāo)值的c也相應(yīng)改變 D(r,2)=k; %改變D中的映射關(guān)系 end end endend【備注：文件名字為danchunxing11zly.m】4. 使用方法以及運(yùn)算實(shí)例在命令窗口中輸入 run danchunxing11zly，然后依次按照提示完成約束以及目標(biāo)函數(shù)的矩

7、陣。例1：min S.t 窗口輸入 run danchunxing11zly A=1 1 -2 1 0 0;2 -1 4 0 1 0;-1 2 -4 0 0 1; b=10 8 4; c=1 -2 1 0 0 0運(yùn)行結(jié)果為：w = 0 0 0 panbieshu = -1 2 -1 0 0 0 z = 2 k = 2 確定下標(biāo)并選擇進(jìn)基變量和離基變量為ans = 10 -8 2 x(2)進(jìn)基，x(6)離基B = 1 0 1 0 1 -1 0 0 2 cB = 0 0 -2 w = 0 0 -1 panbieshu = 0 0 3 0 0 -1 z = 3 k = 3 確定下標(biāo)并選擇進(jìn)基變量和離

8、基變量為ans = 1/0 4 -2 x(3)進(jìn)基，x(5)離基B = 1 -2 1 0 4 -1 0 -4 2 cB = 0 1 -2 w = 0 -3/2 -7/4 panbieshu = -9/4 0 0 0 -3/2 -7/4 z = 0 k = 2 確定下標(biāo)并選擇進(jìn)基變量和離基變量為ans = 1/0 1/0 4 已找到最優(yōu)解!xB = 8 5 12 f = -19 X = 0 12 0 0 0 0 X = 0 12 5 0 0 0 X = 0 12 5 8 0 0 基向量為:X = 0 12 5 8 0 0 目標(biāo)函數(shù)值為:f = -19 例2： max S.t 命令窗口中輸入: r

9、un danchunxing11zlyA=1 1 2 1 0;1 4 -1 0 1b=6 4c=-2 -1 1 0 0運(yùn)行結(jié)果為：w = 0 0 panbieshu = 2 1 -1 0 0 z = 2 k = 1 確定下標(biāo)并選擇進(jìn)基變量和離基變量為ans = 6 4 x(1)進(jìn)基，x(5)離基B = 1 1 0 1 cB = 0 -2 w = 0 -2 panbieshu = 0 -7 1 0 -2 z = 1 k = 3 確定下標(biāo)并選擇進(jìn)基變量和離基變量為ans = 2 -4 x(3)進(jìn)基，x(4)離基B = 2 1 -1 1 cB = 1 -2 w = -1/3 -5/3 panbieshu =