2023-2023〔1〕專業課程實踐論文對偶單純形法范俊，0818180124，R數學08-1班陳泊宇，0818180116，R數學08-1班侯建成，0818180128，R數學08-1班算法理論對偶單純形法是解決線性規劃問題的一種方法。當一個線性規劃問題具有中心部位具有單位子塊，底行相應于單位子塊位置元素為0，底行其他元素非負等三個特點而同時又不具有右行列元素非負特點，即滿足特點1、3、4時可使用此方法求出最優解。此方法運用所允許的運算，始終不破壞第1、3、4三個特點，而逐步調出第2個特點的方法，以解出最優解。其具體的步驟為：1.從右列負元素中任選一個。2.從所選行位于中心部位的負元素中確定一個，由于要保持第3、4的特點不被破壞，理應取相應底行的元素與該負元素之比中最大者。3.進行旋轉運算。如此往復直至第2個特點也被滿足，并得到最優解。該matlab程序可以解決在標準形下滿足第1、3、4特點的線性規劃問題。二、算法框圖三、算法程序建立函數functionx=lindual(c,A,b)[n1,n2]=size(A);A=[-A,eye(n1)];c=[-c,zeros(1,n1)];x1=[zeros(1,n2),b'];lk=[n2+1:n1+n2];b=-b;while(1)x=x1(1:n2);s1=[lk',b,A];c;x1;cc=[];ci=[];fori=1:n1ifb(i)<0cc=[cc,b(i)];ci=[ci,i];endendnc=length(cc);ifnc==0fprintf('到達最優解');breakendcliu=cc(1);cl=ci(1);forj=1:ncifabs(cc(j))>abs(cliu)cliu=cc(j);cl=j;endendcc1=[];ci1=[];fori=1:n1+n2ifA(cl,i)<0cc1=[cc1,A(cl,i)];ci1=[ci1,i];endendnc1=length(cc1);ifnc1==0fprintf('無可行解');breakendcliu=c(ci1(1))/cc1(1);cl1=ci1(1);forj=1:nc1ifc(ci1(j))/cc1(j)<cliucliu=c(ci1(j))/cc1(j);cl1=ci1(j);endendb(cl)=b(cl)/A(cl,cl1);A(cl,:)=A(cl,:)/A(cl,cl1);fork=1:n1ifk~=clb(k)=b(k)-b(cl)*A(k,cl1);A(k,:)=A(k,:)-A(cl,:).*A(k,cl1);endendc=c-c(cl1).*A(cl,:);x1(lk(cl))=0;lk(cl)=cl1;forkk=1:n1x1(lk(kk))=b(kk);endx=x1(1:n2);end四、算法實現例1.用對偶單純形法解以下線性規劃mins.t.65x解：利用matlab數學軟件的解答方法為：〔1〕輸入題中條件：>>c=[15245];A=[061;521];b=[2;1];〔2〕調用函數求出最優解：>>x=lindual(c,A,b)〔3〕求最優值：>>z=c*x’運行結果如下：例2.用對偶單純形法解以下線性規劃mins.t.2xx解：利用matlab數學軟件的解答方法為：〔1〕輸入題中條件：>>c=[11];A=[21;1