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

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

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

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

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

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

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

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

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

9、,i)0); % 再進(jìn)行查找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); % 存放的是人工變量的行數(shù) text=find(A(x1,1:n)=0); % 該行的所有元素都不為零的列坐標(biāo) if isempty(text) %如果tex

10、t為空 decide(1)=; A1(x1,:)=; A(x1,:)=; m=m-1; else i=text(1); % i保存列數(shù) A(x1,:)=A(x1,:)/A(x1,i);%進(jìn)行單位化 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,:);%進(jìn)行換基迭代 end end decide(1)=;%賦值為空 text(1)=; end end end decide=find(c(1,1:n)0); %decide存放c中該行中所有數(shù)值大于

11、零的列數(shù) while isempty(decide) i=decide(1); % 將列數(shù)賦給i text=find(A(:,i)0); % 保存大于零的項(xiàng)的行數(shù) if isempty(text) % 為空的時(shí)候，則無解 flag=0; %有可行解但無最優(yōu)值，flag記為0 c=c;A; %將c添加到A矩陣上方的到對(duì)應(yīng)解的單純形表 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); % 再進(jìn)行查找 end c=c;A;%得到對(duì)應(yīng)解的單純形表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七結(jié)果運(yùn)行測(cè)試：輸入測(cè)試數(shù)據(jù)： 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ùn)行結(jié)果為：該問題存在最優(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八心得與感悟：通過本學(xué)期學(xué)習(xí)MALTAB軟件，初步了解并掌握了MATLAB軟件中的線性規(guī)劃問題的編程求解的