用單純形法求解線性規(guī)劃問題

1、目錄一摘要 2二實驗目的 2三實驗內容 2四建立數學模型 3五實驗原理 5六MALTAB程序代碼及注釋 7七結果運行測試 13八心得與感悟 15 一摘要：線性規(guī)劃是運籌學中研究較早、發(fā)展較快、應用廣泛、方法較成熟的一個重要分支,它是輔助人們進行科學管理的一種數學方法.研究線性約束條件下線性目標函數的極值問題的數學理論和方法,英文縮寫LP。自1946年G.B.Dantizig提出單純形法以來，它一直是求解線性規(guī)劃問題的最有效的數學方法之一。單純形法的理論根據是：線性規(guī)劃問題的可行域是 n維向量空間Rn中的多面凸集,其最優(yōu)值如果存在必在該凸集的某頂點處達到。頂點所對應的可行解稱為基本可行解。通過引

2、入普通單純形法，依次迭代并判斷，逐步逼近，最后得到最優(yōu)解。若不是，則按照一定法則轉換到另一改進的基本可行解，再鑒別；若仍不是，則再轉換，按此重復進行。因基本可行解的個數有限，故經有限次轉換必能得出問題的最優(yōu)解。如果問題無最優(yōu)解也可用此法判別。關鍵字：線性規(guī)劃，單純形法，最優(yōu)值，最優(yōu)解二實驗目的：1.加強學生分析問題能力，鍛煉數學建模能力。2.了解并掌握MATLAB軟件中的線性規(guī)劃問題的編程、求解和分析。3.利用所學的MALTAB語言，完成對單純形法問題的編程設計。三實驗內容：某商場決定，營業(yè)員每周連續(xù)工作5天后連續(xù)休息2天，輪流休息，據統(tǒng)計，商場每天需要營業(yè)員如下：星期一：300，二：300；

3、三：350，四：400，五：480，六：600；日：500；（1）商場人力資源部應如何安排每天上班的人數才能使商場總的營業(yè)員最少（2）若商場可以雇傭臨時工，上班時間同正式工，若正式工每天工資80，臨時工每天100，問商場是否應雇傭臨時工及雇傭多少名？四建立數學模型：從實際問題中建立數學模型一般有以下三個步驟： 1.根據影響所要達到目的的因素找到決策變量； 2.由決策變量和所在達到目的之間的函數關系確定目標函數； 3.由決策變量所受的限制條件確定決策變量所要滿足的約束條件。 當我們得到的數學模型的目標函數為線性函數，約束條件為線性等式或不等式時稱此數學模型為線性規(guī)劃模型。 線性規(guī)劃問題的標準形式

4、：由題可知，可設每天上班人數分別應為x1,x2,x3,x4,x5,x6,x7;建立下列數學模型將其轉化為標準形式為：即價值向量約束矩陣右端向量五實驗原理：根據單純形法的原理，在線性規(guī)劃問題中，決策變量（控制變量）x1，x2，x n的值稱為一個解,滿足所有的約束條件的解稱為可行解。使目標函數達到最大值（或最小值）的可行解稱為最優(yōu)解。這樣，一個或多個最優(yōu)解能在整個由約束條件所確定的可行區(qū)域內使目標函數達到最大值（或最小值）。求解線性規(guī)劃問題的目的就是要找出最優(yōu)解。最優(yōu)解可能出現下列情況之一：存在著一個最優(yōu)解；存在著無窮多個最優(yōu)解；不存在最優(yōu)解，這只在三種情況下發(fā)生，即沒有可行解或各項約束條件不阻止

5、目標函數的值無限增大（或向負的方向無限增大）。單純形法的一般解題步驟可歸納如下： 把線性規(guī)劃問題的約束方程組表達成典范型方程組，找出基本可行解作為初始基本可行解。 若基本可行解不存在，即約束條件有矛盾，則問題無解。 若基本可行解存在，從初始基本可行解作為起點，根據最優(yōu)性條件和可行性條件，引入非基變量取代某一基變量，找出目標函數值更優(yōu)的另一基本可行解。 按步驟3進行迭代,直到對應檢驗數滿足最優(yōu)性條件（這時目標函數值不能再改善），即得到問題的最優(yōu)解。 若迭代過程中發(fā)現問題的目標函數值無界，則終止迭代。流程圖如下：対原問題增加m個人工變量構造輔助問題判斷輔助問題最優(yōu)值g=0無解，停止人工變量xj是否

6、為非基變量把人工變量對應的列從單純形表中去掉進行換基迭代得到新矩陣BB中是否有人工變量得到初始可行基B求對應典式和檢驗數判斷k0得到最優(yōu)解進行換基迭代得到新基判斷Ak0問題無界否是否否是是否是六MALTAB程序代碼及注釋：function x,minf,flag,cpt=dcxsf(A,b,c)format rat %使數據可以以分數形式輸出c=-c; %將目標函數系數向量加負號得到單純形表第0行m,n=size(A); %求約束矩陣的行數和列數m1=m; %保存下原來的行數s=eye(m); %生成秩為m的單位矩陣A=A s; %將s矩陣添加到A矩陣右側A=A b; %將b向量添加到A矩陣右

7、側g1=zeros(1,n); %生成一個1行n列的零矩陣g1x=ones(1,m); %生成一個1行m列元素全為1的矩陣g1=g1 -x; %將g1和-x合并，產生一個新的前n列為0后m列為-1的單行矩陣g=0; %初始化一個單元素零矩陣g1=g1 g;%將單元素零矩陣添加到g1右側，生成人工向量的檢驗向量g1s1=n+m+1; %記錄目前列數之和s2=zeros(1,m+1);%生成1行m+1列的零矩陣s2c=c s2;%將s2添加到c右側A1=zeros(m,1);%生成一個m行1列的零矩陣A1for i1=1:m A1(i1,1)=i1+n;%基變量的數值存儲區(qū)endfor i=1:m

8、 g1(1,:)= g1(1,:)+A(i,:); end decide=find(g1(1,1:m+n)0); %尋找g1中大于零的數值列數存于decide數組中while isempty(decide) %當decide不為空 i=decide(1); %將列數賦給i text=find(A(1:m,i)0); %text存放該列中所有數值大于零的行數 if isempty(text) %如果text為空則無解 flag=0; break; end min=inf;%min初始化為無窮大 for i1=1:m % 當該列存在大于零的數值時 if A(i1,i)0&A(i1,s1)/A(i1

9、,i)0); % 再進行查找endif g1(1,s1)0 % 無解情況 flag=-1; endif g1(1,s1)=0 %置空矩陣 g1(1,:)=; for i6=1:m A(:,n+1)=; end for i6=1:m c(n+1)=; end decide=find(A1(1:m,1)n); % 查找是否有人工變量 if isempty(decide) while isempty(decide) x1=decide(1); % 存放的是人工變量的行數 text=find(A(x1,1:n)=0); % 該行的所有元素都不為零的列坐標 if isempty(text) %如果tex

10、t為空 decide(1)=; A1(x1,:)=; A(x1,:)=; m=m-1; else i=text(1); % i保存列數 A(x1,:)=A(x1,:)/A(x1,i);%進行單位化 A1(x1,1)=i; c(1,:)=c(1,:)+(-1*c(1,i)*A(x1,:); for i1=1:m if i1=x1 A(i1,:)=A(i1,:)+(-1*A(i1,i)*A(x1,:);%進行換基迭代 end end decide(1)=;%賦值為空 text(1)=; end end end decide=find(c(1,1:n)0); %decide存放c中該行中所有數值大于

11、零的列數 while isempty(decide) i=decide(1); % 將列數賦給i text=find(A(:,i)0); % 保存大于零的項的行數 if isempty(text) % 為空的時候，則無解 flag=0; %有可行解但無最優(yōu)值，flag記為0 c=c;A; %將c添加到A矩陣上方的到對應解的單純形表 cpt=c; x=zeros(n,1); for o=1:n for o1=1:m if o=A1(o1,1) x(o,1)=A(o1,n+1); end end end disp(該問題有可行解但沒有最優(yōu)解!) minf=-inf;%無最優(yōu)值，將minf賦值為無窮

12、小 x=;%解向量為空 return; end min=inf; %min初始化為無窮大 for i1=1:m if A(i1,i)0&A(i1,n+1)/A(i1,i)0); % 再進行查找 end c=c;A;%得到對應解的單純形表cpt=c;x=zeros(n,1); for o=1:n for o1=1:m if o=A1(o1,1) x(o,1)=A(o1,n+1); end endendminf=c(1,n+1);%得到最優(yōu)值flag=1 ; %有最優(yōu)值 記錄flag為1end if flag=0 %有可行解但沒有最優(yōu)值情況 disp(該問題有可行解但沒有最優(yōu)解!) x=; %賦值

13、為空 minf=-inf;%最優(yōu)值輸出為無窮小 end if flag=1 %有可行解有最優(yōu)值情況 disp(該問題存在最優(yōu)解!) x=x; minf=minf; end; if flag=-1 %沒有可行解情況 disp(該問題沒有可行解!) x=;%賦值為空 cpt=; minf=; endend七結果運行測試：輸入測試數據： A=1 1 1 1 1 0 0 -1 0 0 0 0 0 0;0 1 1 1 1 1 0 0 -1 0 0 0 0 0;0 0 1 1 1 1 1 0 0 -1 0 0 0 0;1 0 0 1 1 1 1 0 0 0 -1 0 0 0;1 1 0 0 1 1 1 0

14、 0 0 0 -1 0 0;1 1 1 0 0 1 1 0 0 0 0 0 -1 0;1 1 1 1 0 0 1 0 0 0 0 0 0 -1; b=300 300 350 400 480 600 550; c=1 1 1 1 1 1 1 0 0 0 0 0 0 0; x,minf,flag,cpt=dcxsf(A,b,c)運行結果為：該問題存在最優(yōu)解!x = 170 290/3 120 50/3 0 200/3 440/3 310/3 0 0 0 0 0 0 minf = 1850/3 flag = 1 cpt = Columns 1 through 6 0 0 0 0 -1/3 0 1 0

15、 0 0 -1 0 0 0 1 0 -1 0 0 0 0 0 2/3 0 0 0 0 0 2/3 1 0 1 0 0 2/3 0 0 0 0 0 -5/3 0 0 0 0 1 2/3 0 Columns 7 through 12 0 0 -1/3 0 -1/3 0 0 0 0 1 -1 1 0 0 0 0 0 1 1 0 2/3 -1 2/3 -1 0 0 -1/3 0 -1/3 0 0 0 -1/3 0 2/3 -1 0 1 -2/3 1 -2/3 1 0 0 -1/3 0 -1/3 0 Columns 13 through 15 -1/3 -1/3 1850/3 -1 0 170 -1 0 120 2/3 -1/3 440/3 -1/3 2/3 200/3 2/3 -1/3 290/3 -2/3 -2/3 310/3 2/3 -1/3 50/3 解得最優(yōu)解為(170 97 120 17 0 67 146)最優(yōu)值為617八心得與感悟：通過本學期學習MALTAB軟件，初步了解并掌握了MATLAB軟件中的線性規(guī)劃問題的編程求解的