線性規(guī)劃模型的應(yīng)用及靈敏度分析范文

./摘要線性規(guī)劃是解決稀缺資源最優(yōu)分配的有效方法,使付出的費(fèi)用最少或獲得的利益最大。它的研究對(duì)象是有一定的人力、財(cái)力、資源條件下,如何合理安排使用,效益最高；某項(xiàng)任務(wù)確定后,如何安排人、財(cái)、物,使之最省。它要解決的問(wèn)題的目標(biāo)可以用數(shù)值指標(biāo)反映,對(duì)于要實(shí)現(xiàn)的目標(biāo)有多種方案可以選擇,有影響決策的若干約束條件。本文主要介紹了線性規(guī)劃模型在實(shí)際生活中的應(yīng)用,其中包括解線性方程組的各種方法,如圖解法、單純形法、以及對(duì)偶單純形法等等,以及簡(jiǎn)單介紹了有關(guān)靈敏度分析的方法。由于許多問(wèn)題僅僅利用線性規(guī)劃的方法還不足以解決,因此用到了對(duì)偶理論,也因此引出了對(duì)偶單純形法。對(duì)偶規(guī)劃是線性規(guī)劃問(wèn)題從另一個(gè)角度進(jìn)行研究,是線性規(guī)劃理論的進(jìn)一步深化,也是線性規(guī)劃理論整體的一個(gè)不可分割的組成部分。靈敏度分析是對(duì)線性規(guī)劃結(jié)果的再發(fā)掘,是對(duì)線性規(guī)劃理論的充要應(yīng)用,本文以實(shí)例驗(yàn)證靈敏度分析的實(shí)際應(yīng)用。關(guān)鍵詞：線性規(guī)劃；單純形法；對(duì)偶單純形法.ABSTRCTLinearprogrammingisaneffectivemethodtosolvetheoptimalallocationofscarceresources,makethecostofpayorreceiveatleasttheinterestsofthelargest.Itsobjectofstudyisthehumanandfinancialresources,resourceconditions,howtoreasonablyarrangetouse,benefitissupreme;Ataskisdetermined,howtoarrangepeople,goods,andmakeitthemostprovinces.Ittothetargetcanbeusedtosolvetheproblemofthenumericalindicators,toachieveavarietyofsolutionstochoosefrom,haveanimpactonthedecisionofsomeconstraintconditions.Throughthesubjectdesign,candeepentheoperationsresearch,optimizationmethod,linearprogramming,nonlinearprogramming,toimprovetheintegrateduseofknowledge,improvetheabilityofusingthesensitivityanalysistosolvevariouspracticalproblems.Thisarticlemainlyintroducestheapplicationoflinearprogrammingmodelinreallife,includingthevariousmethodsofsolvinglinearequations,asshowninfiguremethod,simplexmethodanddualsimplexmethod,etc.,andsimplyintroducesthemethodofsensitivityanalysis.Duetomanyproblemsjustbyusingthemethodoflinearprogrammingisnotenoughtosolve,sousethedualitytheory,thusraisesthedualsimplexmethod.ThedualprogrammingislinearprogrammingproblemfromanotherAngle,isthefurtherdeepeningoflinearprogrammingtheory,linearplanningtheoryasawholeisalsoanintegralpartof.Sensitivityanalysisistodiscover,theresultofthelinearprogrammingisthechargetoapplicationoflinearprogrammingtheory.Keywords:linearprogramming；Simplexmethod；Thedualsimplexmethod.目錄TOC\o"1-3"\h\u202前言1034線性規(guī)劃模型的應(yīng)用與靈敏度分析………………12000第一章線性規(guī)劃問(wèn)題……………175801.線性規(guī)劃及靈敏度分析簡(jiǎn)介…………………1235072.線性規(guī)劃模型應(yīng)用的發(fā)展……………………1147293.線性規(guī)劃模型研究的問(wèn)題……………………2209324.線性規(guī)劃模型的應(yīng)用…………2178394.1問(wèn)題………………25254.2線性規(guī)劃方法的特點(diǎn)及局限性………………2232344.3線性規(guī)劃模型的基本結(jié)構(gòu)……………………3257624.4線性規(guī)劃模型的一般形式……………………347914.4線性規(guī)劃的性質(zhì)…………………520039第二章求解線性規(guī)劃的方法………………………639291.圖解法……………6249122.單純行法…………………………768072.1單純行法的基本思路…………7218052.2單純形法的求解步驟………………………11221062.3單純形法的求解過(guò)程小結(jié)…………………12213692.3.1人造基、初始基本可行解…………………12245382.3.2最優(yōu)解判別定理：…………14241722.3.3單純行過(guò)程的兩種方法…………………14109563.單純行法…………………………1450773.1對(duì)偶問(wèn)題的提出………………14150803.2線性規(guī)劃的對(duì)偶理論…………15309983.3對(duì)偶單純形法的步驟…………15221544.單純行表…………………………158107第三章靈敏度分析…………………17254721.邊際值<影子價(jià)>……………17121032.價(jià)值向量的靈敏度分析………………………18264463.靈敏度的應(yīng)用…………………192452第四章應(yīng)用設(shè)計(jì)實(shí)例………………19118741.目標(biāo)函數(shù)系數(shù)靈敏度分析……………………1974332.右邊值敏感性分析……………1931247結(jié)論………………2226497參考文獻(xiàn)………………2321324致謝………………24.前言線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支。1947年,當(dāng)時(shí)正在美國(guó)空軍擔(dān)任數(shù)學(xué)顧問(wèn)的Dantzig在《最優(yōu)規(guī)劃的科學(xué)計(jì)算》中提出"如何使規(guī)劃過(guò)程機(jī)械化"問(wèn)題,并著手建立數(shù)學(xué)模型。他從改造投入產(chǎn)出模型入手,逐步研究,形成了"單純形法",并于1953年提出"改進(jìn)單純形法",以解決計(jì)算機(jī)求解過(guò)程中的舍入誤差問(wèn)題。之后,線性規(guī)劃理論逐步趨于成熟,在實(shí)用中日益廣泛和深入。通過(guò)設(shè)計(jì)該課題,可以加深對(duì)運(yùn)籌學(xué)、最優(yōu)化、線性規(guī)劃、非線性規(guī)劃以及MATLAB的認(rèn)識(shí),提高對(duì)這些知識(shí)的綜合應(yīng)用水平,提高利用靈敏度分析解決各種線性規(guī)劃問(wèn)題的能力。本文章主要介紹了線性規(guī)劃在實(shí)際生活中的應(yīng)用,包括解線性方程組的各種方法,包括圖解法,單純形法,大M法,二階段法以及對(duì)偶單純形法,以及簡(jiǎn)要介紹了有關(guān)靈敏度分析的方法。由于線性方程組是解決各種應(yīng)用問(wèn)題的主要工具,而有許多問(wèn)題僅僅利用線性規(guī)劃的解決方法還不足以解決問(wèn)題,還用到了對(duì)偶理論,也因此引出了對(duì)偶單純形法。本課題當(dāng)前的研究方向有：LP的內(nèi)點(diǎn)算法,它通過(guò)非線性規(guī)劃解決線性問(wèn)題,其成功是對(duì)數(shù)學(xué)思想的革新；算法復(fù)雜度,評(píng)價(jià)算法好壞應(yīng)從平均工作量出發(fā)；大型問(wèn)題的分解算法、近似算法。線性規(guī)劃的應(yīng)用正在不斷擴(kuò)大,企業(yè)成功確實(shí)通過(guò)提高生產(chǎn)和有效使用資源的競(jìng)爭(zhēng)過(guò)程來(lái)達(dá)到。.線性規(guī)劃模型的應(yīng)用與靈敏度分析第一章線性規(guī)劃問(wèn)題線性規(guī)劃及靈敏度分析簡(jiǎn)介線性規(guī)劃<LinearProgramming>問(wèn)題,簡(jiǎn)稱(chēng)LP問(wèn)題,是運(yùn)籌學(xué)中最基本,也是最重要的內(nèi)容,被廣泛地應(yīng)用于軍事決策、企業(yè)管理、工程設(shè)計(jì)、交通運(yùn)輸?shù)阮I(lǐng)域.特別是經(jīng)濟(jì)領(lǐng)域應(yīng)用更為廣泛,有資料稱(chēng),在對(duì)500家有相當(dāng)效益的公司所作的評(píng)述中,有85%的公司都曾應(yīng)用了線性規(guī)劃。靈敏度分析對(duì)于決策者的重要性不言而喻,在真實(shí)世界里,周?chē)沫h(huán)境、條件是在不斷變化的。2.線性規(guī)劃模型應(yīng)用的發(fā)展線性規(guī)劃及其通用解法——單純形法是由美國(guó)在1947年研究空軍軍事規(guī)劃提出來(lái)的。法國(guó)數(shù)學(xué)家傅里葉和瓦萊－普森分別于1832和1911年獨(dú)立地提出線性規(guī)劃的想法,但未引起注意。1939年蘇聯(lián)數(shù)學(xué)家康托羅維奇在《生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法》一書(shū)中提出線性規(guī)劃問(wèn)題,也未引起重視[1]。1947年美國(guó)數(shù)學(xué)家丹齊克提出線性規(guī)劃的一般數(shù)學(xué)模型和求解線性規(guī)劃問(wèn)題的通用方法──單純形法,為這門(mén)學(xué)科奠定了基礎(chǔ)。1947年美國(guó)數(shù)學(xué)家諾伊曼提出對(duì)偶理論,開(kāi)創(chuàng)了線性規(guī)劃的許多新的研究領(lǐng)域,擴(kuò)大了它的應(yīng)用范圍和解題能力[2]。1951年美國(guó)經(jīng)濟(jì)學(xué)家?guī)炱章拱丫€性規(guī)劃應(yīng)用到經(jīng)濟(jì)領(lǐng)域,為此與康托羅維奇一起獲1975年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。50年代后對(duì)線性規(guī)劃進(jìn)行大量的理論研究,并涌現(xiàn)出一大批新的算法。例如,1954年萊姆基提出對(duì)偶單純形法,1954年加斯和薩迪等人解決了線性規(guī)劃的靈敏度分析和參數(shù)規(guī)劃問(wèn)題,1956年塔克提出互補(bǔ)松弛定理,1960年丹齊克和沃爾夫提出分解算法等。線性規(guī)劃的研究成果還直接推動(dòng)了其他數(shù)學(xué)規(guī)劃問(wèn)題包括整數(shù)規(guī)劃、隨機(jī)規(guī)劃和非線性規(guī)劃的算法研究[3]。1984年美國(guó)貝爾電話實(shí)驗(yàn)室的印度數(shù)學(xué)家N.卡馬卡提出解線性規(guī)劃問(wèn)題的新的多項(xiàng)式時(shí)間算法。用這種方法求解線性規(guī)劃問(wèn)題在變量個(gè)數(shù)為5000時(shí)只要單純形法所用時(shí)間的1/50?，F(xiàn)已形成線性規(guī)劃多項(xiàng)式算法理論。50年代后線性規(guī)劃的應(yīng)用范圍不斷擴(kuò)大[4]。3.線性規(guī)劃模型研究的問(wèn)題建立線性規(guī)劃模型線性規(guī)劃研究的問(wèn)題主要有兩類(lèi):一類(lèi)是當(dāng)一項(xiàng)任務(wù)確定后,如何統(tǒng)籌安排,盡量做到以最少的人力、物力等資源去完成；另一類(lèi)是在人力、物力等資源確定的情況下,如何安排使用這些資源,使創(chuàng)造的價(jià)值最多,其實(shí)質(zhì)是解決稀缺資源在有競(jìng)爭(zhēng)環(huán)境中如何進(jìn)行最優(yōu)分配的問(wèn)題,即尋求整個(gè)問(wèn)題的某個(gè)整體指標(biāo)最優(yōu)的問(wèn)題[4]。線性規(guī)劃模型的應(yīng)用4.1問(wèn)題a.目標(biāo)函數(shù)最優(yōu)化——單一目標(biāo),多重目標(biāo)問(wèn)題如何處理？b.實(shí)現(xiàn)目標(biāo)的多種方法,若實(shí)現(xiàn)目標(biāo)只有一種方法不存在規(guī)劃問(wèn)題。c.生產(chǎn)條件的約束——資源是有限的,資源無(wú)限不存在規(guī)劃問(wèn)題。4.2線性規(guī)劃方法的特點(diǎn)及局限性特點(diǎn)：a.可以使研究對(duì)象具體化、數(shù)量化。可以對(duì)所研究的技術(shù)經(jīng)濟(jì)問(wèn)題做出明確的結(jié)論；b.線性；c.允許出現(xiàn)生產(chǎn)要素的剩余量；d.有一套完整的運(yùn)算程序；局限性：a.線性規(guī)劃它是以?xún)r(jià)格不變和技術(shù)不變?yōu)榍疤釛l件的,不能處理涉及到時(shí)間因素的問(wèn)題。因此,線性規(guī)劃只能以短期計(jì)劃為基礎(chǔ)。b.在生產(chǎn)活動(dòng)中,投入產(chǎn)出的關(guān)系不完全是線性關(guān)系,由于在一定的技術(shù)條件下,報(bào)酬遞減規(guī)律起作用,所以要滿足線性假定是不可能的。在線性規(guī)劃解題中,常常把投入產(chǎn)出的非線性關(guān)系轉(zhuǎn)化為線性關(guān)系來(lái)處理,以滿足線性的假定性,客觀上產(chǎn)生誤差。c.線性規(guī)劃本身只是一組方程式,并不提供經(jīng)濟(jì)概念,它不能代替人們對(duì)現(xiàn)實(shí)經(jīng)濟(jì)問(wèn)題的判斷。4.3線性規(guī)劃模型的基本結(jié)構(gòu)<1>決策變量——未知數(shù)。它是通過(guò)模型計(jì)算來(lái)確定的決策因素。又分為實(shí)際變量——求解的變量和計(jì)算變量,計(jì)算變量又分松弛變量〔上限和人工變量〔下限。<2>目標(biāo)函數(shù)——經(jīng)濟(jì)目標(biāo)的數(shù)學(xué)表達(dá)式。目標(biāo)函數(shù)是求變量的線性函數(shù)的極大值和極小值這樣一個(gè)極值問(wèn)題。<3>約束條件——實(shí)現(xiàn)經(jīng)濟(jì)目標(biāo)的制約因素。它包括：生產(chǎn)資源的限制〔客觀約束條件、生產(chǎn)數(shù)量、質(zhì)量要求的限制〔主觀約束條件、特定技術(shù)要求和非負(fù)限制。4.4線性規(guī)劃模型的一般形式極大值模型<1-1><1-2><1-3>其簡(jiǎn)縮形式為極小值模型<1-4><1-5><1-6>其簡(jiǎn)縮形式為模型的簡(jiǎn)縮形式可用向量表示例1生產(chǎn)安排模型,某工廠生產(chǎn)I、II兩種產(chǎn)品,已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗,如表所示。III資源總量設(shè)備128/臺(tái)時(shí)原材料A4016/千克原材料B0412/千克該工廠生產(chǎn)一單位產(chǎn)品I可獲利2元,生產(chǎn)產(chǎn)品II可獲利3元,問(wèn)如何安排生產(chǎn)獲利最大？解： 本問(wèn)題是目標(biāo)最大化問(wèn)題： <1>決策變量,設(shè)x1,x2為產(chǎn)品I、II的生產(chǎn)數(shù)量；<2>目標(biāo)函數(shù),2x1+3x2；<3>約束條件,設(shè)備限制：x1+2x2≤8原材料A限制：4x1≤16原材料B限制：4x2≤12基本要求：x10,x20該模型記為如下形式maxZ=2x1+3x2s.t. x1+2x2≤8 4x1≤16 4x2≤12x1,x20其中max表示本問(wèn)題是最大值問(wèn)題〔用min表示最小值問(wèn)題,s.t.<subjectto的縮寫(xiě)>表示約束條件。這就是一個(gè)線性規(guī)劃模型[5]。4.4線性規(guī)劃的性質(zhì)定理1線性規(guī)劃問(wèn)題的可行解X是基可行解的充要條件是X的非零分量對(duì)應(yīng)的系數(shù)矩陣A的列向量線性無(wú)關(guān)[6]。定理2若一個(gè)線性規(guī)劃問(wèn)題有可行解,則它必有基本可行解[7]。定理3若可行域有界,線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)一定可以在其可行域的頂點(diǎn)達(dá)到最優(yōu)。求解線性規(guī)劃的方法1.圖解法圖解法是求解線性規(guī)劃模型的一種重要方法,線性規(guī)劃中一些重要的性質(zhì)、概念和求解思想都來(lái)源于此。當(dāng)只有兩個(gè)決策變量時(shí),可以用圖解法求解。它具有簡(jiǎn)單直觀的特點(diǎn)。為了給后面的線性問(wèn)題的基本理論提供較直觀的幾何說(shuō)明,先介紹線性規(guī)劃問(wèn)題的圖解法[8]。圖解法的求解步驟如下：第一步,根據(jù)約束畫(huà)出可行域,先以決策變量為坐標(biāo),建立直角坐標(biāo)系,再根據(jù)各約束條件,作出可行域。第二步,作出一條目標(biāo)函數(shù)等值線,并確定增值方法。第三步,沿等值線的法線方向值增大方向移動(dòng),從而找到最大值。圖解法得出線性規(guī)劃的幾種情況：表2-1解旳幾種情況解旳幾種情況約束條件圖形特點(diǎn)方程特點(diǎn)唯一解一般圍成有限區(qū)域,最優(yōu)值只在一個(gè)頂點(diǎn)達(dá)到無(wú)窮多解在圍成的的區(qū)域邊界上,至少有兩個(gè)頂點(diǎn)處達(dá)到優(yōu)解目標(biāo)和某一約束方程成比例無(wú)可行解〔無(wú)解圍不成區(qū)域有矛盾方程無(wú)界解<無(wú)解圍成無(wú)界區(qū)域,且無(wú)有限最優(yōu)解缺少一必要條件的方程例：MinZ=10x1+20x22.單純形法單純形法是美國(guó)數(shù)學(xué)家于1947年首先提出的。它的理論根據(jù)是：線性規(guī)劃問(wèn)題的可行域是n維向量空間nR中的多面凸集,其最優(yōu)值如果存在必在該凸集的某頂點(diǎn)處達(dá)到[9]。它的原理涉及到較多的數(shù)學(xué)理論上的推導(dǎo)和證明,我們?cè)诖藘H介紹這種方法的具體操作步驟及每一步的經(jīng)濟(jì)上的含義。為更好地說(shuō)明問(wèn)題,我們?nèi)越Y(jié)合實(shí)例介紹這種方法。單純形法〔simplexmethods,求解線性規(guī)劃的通用方法。2.1單純形法的基本思路單純形法的基本思路是：根據(jù)線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型,從可行域中某個(gè)基本可行解〔一個(gè)頂點(diǎn)開(kāi)始,轉(zhuǎn)換到另一個(gè)基本可行解〔頂點(diǎn),并且當(dāng)目標(biāo)函數(shù)達(dá)到最大值時(shí),問(wèn)題就得到了解決,其基本思路的框架圖如下圖2-1。圖2-1.單純行法的基本思路用單純行法討論例1的求解解：已知例1的標(biāo)準(zhǔn)型為〔2-1〔2-2約束條件〔2-2的系數(shù)矩陣顯然,x3,x4,x5的系數(shù)列向量〔2-3是線性獨(dú)立的,因而這些向量構(gòu)成一個(gè)基<2-4>對(duì)應(yīng)于B的基變量為x3,x4,x5,從約束條件〔2-2中可以看到〔2-5當(dāng)令非基變量這時(shí)得到一個(gè)基本可行解X〔0〔2-6將式<2-3>代入目標(biāo)函數(shù)<2-1>得到〔2-7這個(gè)基本可行解表示：工廠沒(méi)有安排生產(chǎn)ⅠⅡ產(chǎn)品；資源都沒(méi)有被利用,所以工廠的利潤(rùn)Z=0。分析目標(biāo)函數(shù)的表達(dá)式<2-7>可以看到：非基變量x1,x2的系數(shù)都是正數(shù),因此將非基變量變?yōu)榛兞?目標(biāo)函數(shù)的值就可能增大,從經(jīng)濟(jì)意義上講,安排生產(chǎn)產(chǎn)品Ⅰ或Ⅱ,就可以使工廠的利潤(rùn)指標(biāo)增加,所以只要在目標(biāo)函數(shù)<2-7>的表達(dá)式中還存在有正系數(shù)的非基變量,這表示目標(biāo)函數(shù)值還有增加的可能,就需要將非基變量與某個(gè)基變量進(jìn)行對(duì)換,一般選擇正系數(shù)最大的那個(gè)非基變量x2為換入變量,將它換入到基變量中區(qū),同時(shí)還有確定基變量中有一個(gè)要換出來(lái)成為非基變量,可按以下方法來(lái)確定換出變量?，F(xiàn)分析式<2-5>,當(dāng)將x2定為換入變量后,必須從x3,x4,x5中換出一個(gè),并保證其余的都是非負(fù),即x3,x4,x5。當(dāng)x1=0,由式<2-5>得到〔2-8可以看出,只有選擇〔2-9時(shí),才能使式<2-8>成立。以上數(shù)學(xué)模型說(shuō)明了每生產(chǎn)一件產(chǎn)品Ⅱ,需要用掉的各種資源數(shù)為<2,0,4>。這些資源中的薄弱環(huán)節(jié)確定了產(chǎn)品Ⅱ的產(chǎn)量。原材料B的數(shù)量決定產(chǎn)品Ⅱ的產(chǎn)量只能是x2=12/4=3件。為了求得以x3,x4,x2為基變量的一個(gè)基本可行解和進(jìn)一步分析問(wèn)題,需將方程<2-5>中x2的位置對(duì)換。得到〔2-10用高斯消去法求解,得到以非基變量表示的基變量〔2-11代入目標(biāo)函數(shù)得到<2-12>令非基變量得到并得另一個(gè)基本可行解。從目標(biāo)函數(shù)的表達(dá)式<2-12>中可以看到,非基變量的系數(shù)是正的,說(shuō)明目標(biāo)函數(shù)的值還可以增大,還不是最優(yōu)解。于是用上述方法,確定換入、換出變量,繼續(xù)迭代,再得到另外一個(gè)基本可行解。再經(jīng)過(guò)一次迭代,得到一個(gè)基本可行解。而這時(shí)得到的目標(biāo)函數(shù)的表達(dá)式是〔2-13再分析目標(biāo)函數(shù)<2-13>,可知所有非基變量的系數(shù)都是負(fù)數(shù),這說(shuō)明若要用剩余資源就必須支付附加費(fèi)用。所以當(dāng)時(shí),即不再利用這些資源時(shí),目標(biāo)函數(shù)達(dá)到最大值,那么是最優(yōu)解。這說(shuō)明當(dāng)產(chǎn)品Ⅰ生產(chǎn)4件,產(chǎn)品Ⅱ生產(chǎn)2件,工廠才能得到最大利潤(rùn)。通過(guò)上例,可以了解利用單純形法求解線性規(guī)劃問(wèn)題的思路。2.2單純形法的求解步驟線性規(guī)劃問(wèn)題的求解有以下幾個(gè)步驟：<1>確定初始基本可行解。為了確定初始基本可行解,首先要找出初始可行解。設(shè)一線性規(guī)劃問(wèn)題為〔2-14可分為兩種情況討論。①若中存在一個(gè)單位基,則將其作為初始可行基〔2-15②若中不存在一個(gè)單位基,則人為地構(gòu)造一個(gè)單位初始基。<2>檢驗(yàn)最優(yōu)解。得到初始基本可行解后,要檢驗(yàn)該解是否為最優(yōu)解。如果是最優(yōu)解,則停止運(yùn)算；否則轉(zhuǎn)入〔3基變換。下面給出最優(yōu)性判別定理。一般情況下,經(jīng)過(guò)迭代后可以得到以非基變量表示基變量的表達(dá)式〔〔2-16將式<2-11>代入式<2-10>的目標(biāo)函數(shù),整理后得〔2-17令〔〔2-18于是〔2-19再令〔2-20則得到以非基變量表示目標(biāo)函數(shù)的表達(dá)式〔2-21<3>基變換。若初始基本可行解不是最優(yōu)解,又不能判別無(wú)界時(shí),由目標(biāo)函數(shù)<2-10>的約束條件可看到,當(dāng)某些增加則目標(biāo)函數(shù)值還可能增加這時(shí)就要將其中某個(gè)非基變量換到基變量中去〔稱(chēng)為換入變量,同時(shí),某個(gè)基變量要換成非基變量〔稱(chēng)為換出變量,隨之會(huì)得到一個(gè)新的基本可行解。從一個(gè)基本可行解到另一個(gè)基本可行解的變換,就是進(jìn)行一次基變換。從幾何意義上就是從可行域的一個(gè)頂點(diǎn)轉(zhuǎn)向另一個(gè)頂點(diǎn)。<4>迭代。在確定了換入變量和換出變量后,要把和的位置進(jìn)行對(duì)換,就是說(shuō)要把對(duì)應(yīng)的系數(shù)列向量變成單位列向量。這可以通過(guò)對(duì)約束方程組的增廣矩陣進(jìn)行初等行變換來(lái)實(shí)現(xiàn),變換結(jié)果得一新的基本可行解。2.3單純形法的求解過(guò)程小結(jié)2.3.1人造基、初始基本可行解<1>若從線性規(guī)劃問(wèn)題的Pj中能直接觀察到存在m個(gè)線性獨(dú)立的單位向量,經(jīng)過(guò)重新安排次序便得到一個(gè)可行基。<2>"≤"標(biāo)準(zhǔn)化的方法,引入非負(fù)的松弛變量重新對(duì)及編號(hào),經(jīng)整理則可得到下列方程顯然得到一個(gè)單位陣我們就將B作為可行基。我們就將B作為可行基。將每個(gè)等式進(jìn)行移項(xiàng)得令由等式可得得到一個(gè)初始基本可行解2.3.2最優(yōu)性檢驗(yàn)得到初始可行解后,要檢驗(yàn)一下是否是最優(yōu)解,如果是則停止迭代,如果不是,則繼續(xù)迭代。但每次迭代后都要檢驗(yàn)是否是最優(yōu)解,為此需要建立一個(gè)判別準(zhǔn)則。一般情況下,經(jīng)過(guò)迭代后式變成將上式代入目標(biāo)函數(shù),整理后得2.3.3最優(yōu)解判別定理：若為對(duì)應(yīng)于B的基本可行解,且對(duì)于一切有X〔0為最優(yōu)解。無(wú)有限最優(yōu)解判別定理：若為對(duì)應(yīng)于B的基本可行解,有一個(gè)并且對(duì)于一切i=1,2,3,……,m有那么該線性規(guī)劃沒(méi)有有限最優(yōu)解。a.換入變量的確定則對(duì)應(yīng)的為換入變量b.換出變量的確定為換入變量。2.3.4單純形法過(guò)程的兩種方法在單純形迭代過(guò)程中,要求人工變量逐步從基變量被替換出,變?yōu)榉腔兞?這有兩種方法：大M法和兩階段法[10]。3.對(duì)偶單純形法對(duì)偶規(guī)劃是線性規(guī)劃問(wèn)題從另一個(gè)角度進(jìn)行研究,是線性規(guī)劃理論的進(jìn)一步深化,也是線性規(guī)劃理論的進(jìn)一步深化,也是線性規(guī)劃理論整體的一個(gè)不可分割.3.1對(duì)偶問(wèn)題的提出每個(gè)線性規(guī)劃都有另一個(gè)線性規(guī)劃〔對(duì)偶問(wèn)題與它密切相關(guān),對(duì)偶理論揭示了原問(wèn)題與對(duì)偶問(wèn)題的內(nèi)在聯(lián)系[11]?？紤]到對(duì)偶模型的約束與原問(wèn)題模型的變量相對(duì)應(yīng),變量則是與原問(wèn)題模型的約束相對(duì)應(yīng)。原問(wèn)題是最小化,則可將對(duì)偶問(wèn)題看做原問(wèn)題[12]。3.2線性規(guī)劃的對(duì)偶理論定理2-1<對(duì)稱(chēng)性定理>對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。定理2-2<弱對(duì)偶定理>設(shè)X和Y分別是原問(wèn)題P和對(duì)偶問(wèn)題D的可行解,則有[13]。定理2-3<對(duì)偶原理>定理2-4<互補(bǔ)松弛定理>如果X和Y分別為P和D的可行解,它們分別為P和D的最優(yōu)解的充要條件是3.3對(duì)偶單純形法的步驟對(duì)偶單純形法是用對(duì)偶理論求解原問(wèn)題的一種方法,而不是求解對(duì)偶問(wèn)題解的單純形法。與對(duì)偶單純形法相對(duì)應(yīng),已有的單純形法稱(chēng)原始單純形法[14]。建立初始單純形表,計(jì)算檢驗(yàn)數(shù)行先確定換出變量--解答列中的負(fù)元素一般選最小的負(fù)元素對(duì)應(yīng)的基變量出基；將主元素進(jìn)行換基迭代〔旋轉(zhuǎn)運(yùn)算、樞運(yùn)算>,將主元素變成1,主元列變成單位向量,得到新的單純形表。繼續(xù)以上步驟,直至求出最優(yōu)解[15]。單純形表表2-2單純形表也可以反映線性規(guī)劃在現(xiàn)實(shí)生活中的運(yùn)用初單純形表實(shí)際活動(dòng)松弛活動(dòng)比值x1x2x3x4x5R0x382300060x4161210040x51240010-目標(biāo)系數(shù)行23000檢驗(yàn)數(shù)行023000第二單純形表實(shí)際活動(dòng)松弛活動(dòng)比值x1x2x3x4x5R0x362010030x421210020x5164001043x2304001-檢驗(yàn)數(shù)行20000903000第三單純形表實(shí)際活動(dòng)松弛活動(dòng)比值x1x2x3x4x5R0x32001-2042x1212010-0x58000-4143x230100012檢驗(yàn)數(shù)行000-201323020第三章靈敏度分析靈敏度分析是研究與分析一個(gè)系統(tǒng)<或模型>的狀態(tài)或輸出變化對(duì)系統(tǒng)參數(shù)或周?chē)鷹l件變化的敏感程度的方法。在最優(yōu)化方法中經(jīng)常利用靈敏度分析來(lái)研究原始數(shù)據(jù)不準(zhǔn)確或發(fā)生變化時(shí)最優(yōu)解的穩(wěn)定性。通過(guò)靈敏度分析還可以決定哪些參數(shù)對(duì)系統(tǒng)或模型有較大的影響。因此,靈敏度分析幾乎在所有的運(yùn)籌學(xué)方法中以及在各種方案進(jìn)行評(píng)價(jià)時(shí)都是很重要的[16]。1.邊際值<影子價(jià)>是指在最優(yōu)解的基礎(chǔ)上,當(dāng)?shù)趇個(gè)約束行的右端項(xiàng)減少一個(gè)單位時(shí),目標(biāo)函數(shù)的變化量機(jī)會(huì)成本因此機(jī)會(huì)成本的另外表達(dá)形式關(guān)于影子價(jià)的一些說(shuō)明①影子價(jià)是資源最優(yōu)配置下資源的理想價(jià)格,資源的影子價(jià)與資源的緊缺度有關(guān)；②松弛變量增加一個(gè)單位等于資源減少一個(gè)單位；③剩余變量增加一個(gè)單位等于資源增加一個(gè)單位；④資源有剩余,在最優(yōu)解中就有對(duì)應(yīng)松弛變量存在,且其影子價(jià)為0；⑤影子價(jià)為0,資源并不一定有剩余。2.價(jià)值向量的靈敏度分析價(jià)值向量<即目標(biāo)函數(shù)系數(shù)>的靈敏度分析分為原最終單純形表中jc與非基變量和基變量對(duì)應(yīng)兩種情況來(lái)討論[17]。若是非基變的系數(shù),則其對(duì)應(yīng)的最終單純形表中的檢驗(yàn)數(shù)為當(dāng)變化,要保證最終單純形表的最優(yōu)解不變,必有保證最終單純形表最優(yōu)解不變,可得的允許變化值〔2若是基變量的系數(shù),應(yīng)有,當(dāng)變化時(shí),就引起的變化這時(shí)若要求原最優(yōu)解不變,必須滿足。于是得到可變化的范圍是3.靈敏度的應(yīng)用<1>投入產(chǎn)出法中靈敏度分析可以用來(lái)研究采取某一項(xiàng)重大經(jīng)濟(jì)政策后將會(huì)對(duì)國(guó)民經(jīng)濟(jì)的各個(gè)部門(mén)產(chǎn)生怎樣的影響。<2>方案評(píng)價(jià)中靈敏度分析可以用來(lái)確定評(píng)價(jià)條件發(fā)生變化時(shí)備選方案的價(jià)值是否會(huì)發(fā)生變化或變化多少。應(yīng)用設(shè)計(jì)實(shí)例某農(nóng)戶計(jì)劃用12公頃耕地生產(chǎn)玉米,大豆和地瓜,可投入48個(gè)勞動(dòng)日,資金360元。生產(chǎn)玉米1公頃,需6個(gè)勞動(dòng)日,資金36元,可獲凈收入200元；生產(chǎn)1公頃大豆,需6個(gè)勞動(dòng)日,資金24元,可獲凈收入150元；生產(chǎn)1公頃地瓜需2個(gè)勞動(dòng)日,資金18元,可獲凈收入1200元,問(wèn)怎樣安排才能使總的凈收入最高。設(shè)種玉米,大豆和地瓜的數(shù)量分別為x1、x2和x3公頃,根據(jù)問(wèn)題建立線性規(guī)劃問(wèn)題模型如下：MaxZ=200x1+150x2+100x3x1+x2+x3≤126x1+6x2+2x3≤48 <4-1>36x1+24x2+183≤360 <4-2>x1≥0,x2≥0,x3≥01.目標(biāo)函數(shù)系數(shù)靈敏度分析表4-1目標(biāo)系數(shù)的允許變動(dòng)范圍活動(dòng)目標(biāo)系數(shù)可減上限可增上限可變范圍玉米種植x1大豆種植x2地瓜種植x320015010050無(wú)窮大100/310050100150~300-~200200/3~200當(dāng)僅有一種目標(biāo)系數(shù)在允許范圍內(nèi)變動(dòng)時(shí),最優(yōu)方案不會(huì)變動(dòng),但最優(yōu)目標(biāo)值會(huì)隨之變化。2.右邊值敏感性分析由線性規(guī)劃的原理可知,影子價(jià)格不變的條件是最優(yōu)解的松弛變量矩陣與右邊值矩陣的乘積大于和等于0,即：當(dāng)右邊值發(fā)生變化時(shí),如耕地變化△,此時(shí),影子價(jià)格不變的條件是得到6+3/2△1≥06-1/2△1≥0-4≤△1≤436-9△1≥0因此耕地影子價(jià)格不變的耕地?cái)?shù)量范圍為：[8,16]得到6－1/4△2≥06+1/4△2≥0-24≤△2≤836-9/2△2≥0因此勞動(dòng)力影子價(jià)格不變的勞動(dòng)力數(shù)量范圍為：[24,56]得到6≥0△3≥－3636＋△3≥0因此資金影子價(jià)格不變的資金數(shù)量范圍為：[324,-]表4-2常數(shù)項(xiàng)的允許變動(dòng)范圍資源現(xiàn)有數(shù)量可減上限可增上限可變范圍影子價(jià)格耕地12448～165