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

《用單純形法求解線性規(guī)劃問題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、目錄一．摘要…………………………………………………………2二．實(shí)驗(yàn)?zāi)康摹?三．實(shí)驗(yàn)內(nèi)容……………………………………………………2四．建立數(shù)學(xué)模型………………………………………………3五．實(shí)驗(yàn)原理……………………………………………………5六．MALTAB程序代碼及注釋……………………………………7七．結(jié)果運(yùn)行測(cè)試…………………………………………………13八．心得與感悟…………………………………………………1513一．摘要：線性規(guī)劃是運(yùn)籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、方法較成熟的一個(gè)重要分支,它是輔助人們進(jìn)行

2、科學(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)的可行解稱為基本可行解。通過引入普通單純形法，依次迭代并判斷，逐步逼近，最后得到最優(yōu)解。若不是，則按照一定法則轉(zhuǎn)換到另一改進(jìn)的基本可行解，再鑒別；若仍不是，則再轉(zhuǎn)換，按此重復(fù)進(jìn)行。因基本可行解的個(gè)數(shù)有限，故經(jīng)有限次轉(zhuǎn)換必能得出問

3、題的最優(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；三：350，四：400，五：480，六：600；日：500；（1）商場(chǎng)人力資源部應(yīng)如何安排每天上班的人數(shù)才能使商場(chǎng)總的營(yíng)業(yè)員最少（2）若商場(chǎng)可以雇

4、傭臨時(shí)工，上班時(shí)間同正式工，若正式工每天工資80，臨時(shí)工每天100，問商場(chǎng)是否應(yīng)雇傭臨時(shí)工及雇傭多少名？13四．建立數(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)形式：由題可知，可設(shè)每天上班人數(shù)分別應(yīng)為x1,x2,x3,x4,x5,x6,x7;建立下列數(shù)學(xué)模型13將其

5、轉(zhuǎn)化為標(biāo)準(zhǔn)形式為：即價(jià)值向量約束矩陣右端向量13五．實(shí)驗(yàn)原理：根據(jù)單純形法的原理，在線性規(guī)劃問題中，決策變量（控制變量）x1，x2，…xn的值稱為一個(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)約束條件不阻止目標(biāo)函數(shù)的值無限增大（或向負(fù)的方向無限

6、增大）。單純形法的一般解題步驟可歸納如下：①把線性規(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ù)值無界，則終止迭代。13流程圖如下：対原問題增加m個(gè)人工變量構(gòu)造輔助問題判斷輔助問題最優(yōu)值g=0無解，停止人

7、工變量xj是否為非基變量把人工變量對(duì)應(yīng)的列從單純形表中去掉進(jìn)行換基迭代得到新矩陣BB中是否有人工變量得到初始可行基B求對(duì)應(yīng)典式和檢驗(yàn)數(shù)ξ判斷ξk≤0得到最優(yōu)解進(jìn)行換基迭代得到新基判斷Ak≤0問題無界否是否否是是否是13六．MALTAB程序代碼及注釋：function[x,minf,flag,cpt]=dcxsf(A,b,c)formatrat%使數(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

8、s];%將s矩陣添加到A矩陣右側(cè)A=[Ab];%將b向量添加到A矩陣右側(cè)g1=zeros(1,n);%生成一個(gè)1行n列的零矩陣g1x=o