緒論及線性規(guī)劃

1、西安財(cái)經(jīng)學(xué)院精品課程運(yùn)籌學(xué)授課教案劉小冬，雷福民王命宇，許格妮西安財(cái)經(jīng)學(xué)院 信息學(xué)院2005年12月緒論運(yùn)籌學(xué)概況一種科學(xué)只有在成功地運(yùn)用數(shù)學(xué)時(shí)，才算達(dá)到完善的地步。Karl Marx【教學(xué)內(nèi)容】運(yùn)籌學(xué)的由來和發(fā)展，運(yùn)籌學(xué)研究的性質(zhì)與特點(diǎn)，運(yùn)籌學(xué)的主要內(nèi)容，運(yùn)籌學(xué)的方法論，運(yùn)籌學(xué)的發(fā)展趨勢?！窘虒W(xué)要求】要求學(xué)生了解運(yùn)籌學(xué)是逐步發(fā)展起來的，今后還將繼續(xù)發(fā)展；理解運(yùn)籌學(xué)整個(gè)過程的各個(gè)步驟；初步理解數(shù)學(xué)模型的建立過程。【教學(xué)重點(diǎn)】運(yùn)籌學(xué)的由來和發(fā)展，運(yùn)籌學(xué)的主要內(nèi)容，運(yùn)籌學(xué)的方法論。【教材內(nèi)容及教學(xué)過程】運(yùn)籌一詞出自中國古代史書史記·高祖本紀(jì)“夫運(yùn)籌帷幄之中，決勝于千里之外?！边\(yùn)籌學(xué)把科學(xué)

2、的方法、技術(shù)和工具應(yīng)用到包括系統(tǒng)管理在內(nèi)的各種問題上，以便為那些掌管系統(tǒng)的人們提供最佳的解決問題的方法。本章介紹運(yùn)籌學(xué)的概況，包括運(yùn)籌學(xué)的由來和發(fā)展、運(yùn)籌學(xué)的性質(zhì)與特點(diǎn)、運(yùn)籌學(xué)的主要內(nèi)容和運(yùn)籌學(xué)的發(fā)展趨勢。1、運(yùn)籌學(xué)的由來和發(fā)展運(yùn)籌學(xué)是本世紀(jì)新興的學(xué)科之一，它能幫助決策人解決那些可以用定量方法和有關(guān)理論來處理的問題。它在工業(yè)、商業(yè)、農(nóng)業(yè)、交通運(yùn)輸、政府部門和其它方面都有重要的應(yīng)用?，F(xiàn)在它已經(jīng)成為經(jīng)濟(jì)計(jì)劃、系統(tǒng)工程、現(xiàn)代管理等領(lǐng)域的強(qiáng)有力的工具。自從人類社會(huì)誕生以來，人們都一直在經(jīng)歷著運(yùn)用和籌劃的決策過程。而運(yùn)籌學(xué)的一些樸素思想可以追溯到很久以前。歷史上曾經(jīng)記載著很多巧妙的運(yùn)用事例。例如，廣為人

3、知的我國戰(zhàn)國時(shí)期齊王和大臣田忌賽馬的故事：在謀士孫臏的策劃下，田忌竟以遜色于齊王馬匹的劣勢獲得比賽的勝利，贏得千金。又如，北宋真宗年間，皇城失火，皇宮被毀，朝廷決定重建皇宮，當(dāng)時(shí)亟待解決“取土”，“外地材料的儲(chǔ)運(yùn)”和“處理瓦礫”等三項(xiàng)任務(wù)，在修建皇宮負(fù)責(zé)人丁渭的精心策劃下，巧妙的解決了上述三項(xiàng)任務(wù)。三國時(shí)期的運(yùn)籌大師諸葛亮，更是眾所周知的風(fēng)云人物。在國外人們常推崇阿基米德為運(yùn)籌學(xué)的先驅(qū)人物，因?yàn)樗I劃有方，在保衛(wèi)敘拉古、抵抗羅馬帝國的侵略中做出了突出貢獻(xiàn)。但運(yùn)籌學(xué)作為科學(xué)名詞出現(xiàn)是在20世紀(jì)30年代末（第二次世界大戰(zhàn)）。當(dāng)時(shí)英、美對(duì)付德國的空襲，雷達(dá)作為防空系統(tǒng)的一部分，從技術(shù)上是可行的，但實(shí)

4、際運(yùn)用時(shí)卻并不好用。為此一些科學(xué)家研究如何合理運(yùn)用雷達(dá)開始進(jìn)行一類新問題的研究。因?yàn)樗c研究技術(shù)問題不同，就稱之為“運(yùn)用研究”(Operational Research)。為了進(jìn)行運(yùn)籌學(xué)研究，在英、美的軍隊(duì)中成立了一些專門小組。開展了護(hù)航艦隊(duì)保護(hù)商船隊(duì)的編隊(duì)問題和當(dāng)船隊(duì)遭受德國潛艇攻擊時(shí)，如何使船隊(duì)損失最少的問題的研究。在研究了反潛深水炸彈的合理爆炸深度后，使德國潛艇被摧毀數(shù)增加到400%；研究了船只在受敵機(jī)攻擊時(shí)，提出了大船應(yīng)急轉(zhuǎn)向和小船應(yīng)緩慢轉(zhuǎn)向的逃避方法。研究結(jié)果使船只在受到敵機(jī)攻擊時(shí)，中彈數(shù)由47%降到29%。雖然運(yùn)籌學(xué)這一科學(xué)名詞出現(xiàn)于二戰(zhàn)中，但在這之前已有許多蘊(yùn)含運(yùn)籌學(xué)思想和方法的

5、書籍和論文出現(xiàn)。原蘇聯(lián)數(shù)學(xué)家康托洛維奇的生產(chǎn)組織與管理中的數(shù)學(xué)方法（屬于規(guī)劃論的內(nèi)容）出版于1939年。但是當(dāng)時(shí)未得到重視，直到1960年康托洛維奇再次發(fā)表了最佳資源利用的經(jīng)濟(jì)計(jì)算一書后，才受到國內(nèi)外的一致重視。為此康托洛維奇于1975年得到了諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。馮·諾伊曼等所著對(duì)策論與經(jīng)濟(jì)行為一書（運(yùn)籌學(xué)中對(duì)策論的創(chuàng)始作）成書前所發(fā)表的一系列論文在1928年就開始刊出。排對(duì)論的先驅(qū)者丹麥工程師艾爾朗1917年在哥本哈根電話公司研究電話通訊系統(tǒng)時(shí)，提出了排對(duì)論的一些著名公式。二戰(zhàn)后，美國等國家的軍方仍保留一些運(yùn)籌研究小組，其他多數(shù)人轉(zhuǎn)向把運(yùn)籌學(xué)研究用于和平時(shí)期的工商業(yè)。美、德等國家的運(yùn)籌

6、學(xué)得以蓬勃發(fā)展，出現(xiàn)了應(yīng)用研究和理論研究相互促進(jìn)的局面。運(yùn)籌學(xué)得到了很快的發(fā)展。50年代中期，錢學(xué)森、許國志等教授將運(yùn)籌學(xué)由西方引入我國。在1956年曾用過運(yùn)用學(xué)的名字，1957年正式更名為運(yùn)籌學(xué)。他們把運(yùn)籌學(xué)結(jié)合我國的特點(diǎn)在國內(nèi)推廣應(yīng)用。在經(jīng)濟(jì)數(shù)學(xué)方面，特別是投入產(chǎn)出表的研究和應(yīng)用開展較早，質(zhì)量管理的應(yīng)用也有特色。在此期間以華羅庚教授為首的一大批數(shù)學(xué)家加入到運(yùn)籌學(xué)的研究隊(duì)伍，使運(yùn)籌數(shù)學(xué)的許多分支很快跟上了當(dāng)時(shí)的國際水平。1980年我國的運(yùn)籌學(xué)會(huì)成立，運(yùn)籌學(xué)雜志創(chuàng)始于1982年，1997年改為運(yùn)籌學(xué)學(xué)報(bào)。2、運(yùn)籌學(xué)的性質(zhì)與特點(diǎn)運(yùn)籌學(xué)是多種學(xué)科的綜合性科學(xué)，也是最早形成的一門軟科學(xué)。當(dāng)人們把戰(zhàn)時(shí)

7、的運(yùn)籌研究取得成功的經(jīng)驗(yàn)在和平時(shí)期加以推廣應(yīng)用時(shí)，面臨著一個(gè)廣闊的研究領(lǐng)域。在這一領(lǐng)域中，對(duì)于運(yùn)籌學(xué)主要研究和解決什么問題有許多說法，至今爭論不休，實(shí)際上形成了一個(gè)在爭論中發(fā)展運(yùn)籌學(xué)的局面。在這四五十年中，我們能從它的爭論中看出運(yùn)籌學(xué)所具有的一些特點(diǎn)。.引進(jìn)數(shù)學(xué)研究方法。運(yùn)籌學(xué)是一門以數(shù)學(xué)為主要工具，尋求各種問題最優(yōu)方案的學(xué)科，所以是一門優(yōu)化科學(xué)。隨著生產(chǎn)與管理的規(guī)模日益擴(kuò)大，其間的數(shù)量關(guān)系也就更加復(fù)雜，從其間的數(shù)量關(guān)系來研究這些問題，即引進(jìn)數(shù)學(xué)研究方法，是運(yùn)籌學(xué)的一大特點(diǎn)。.系統(tǒng)性。運(yùn)籌學(xué)研究問題是從系統(tǒng)的觀點(diǎn)出發(fā)，研究全局性的問題，研究綜合優(yōu)化的規(guī)律，它是系統(tǒng)工程的主要理論基礎(chǔ)。.著重實(shí)際

8、應(yīng)用。在運(yùn)籌學(xué)術(shù)界，有許多人強(qiáng)調(diào)運(yùn)籌學(xué)的實(shí)用性和對(duì)研究結(jié)果的“執(zhí)行”，把“執(zhí)行”看作運(yùn)籌工作中的一個(gè)重要組成部分。有的運(yùn)籌學(xué)教科書中，在講述從理論上求得最優(yōu)解之后，還要講述根據(jù)實(shí)際情況對(duì)所得解進(jìn)行進(jìn)一步的考察，講述對(duì)所得最優(yōu)解如何進(jìn)行靈敏度分析等。.跨學(xué)科性。由有關(guān)的各種專家組成的進(jìn)行集體研究的運(yùn)籌小組總和應(yīng)用多種學(xué)科的只是來解決實(shí)際問題是早期軍事運(yùn)籌研究的一個(gè)重要特點(diǎn)。如二戰(zhàn)時(shí)英國在空軍部門成立的防空運(yùn)籌小組其成員包括數(shù)學(xué)家、物理學(xué)家、天文學(xué)家、生理學(xué)家和軍事專家多人，任務(wù)時(shí)探討如何抵御敵人的空襲和潛艇。這種組織和這種特點(diǎn)一直在一些地方和一些部門以不同的形式保留下來，這往往是研究和解決實(shí)際問

9、題的需要。從世界范圍來看，運(yùn)籌學(xué)的成敗以及應(yīng)用的廣泛程度，無不與有這樣的研究組織和這種組織的工作水平有關(guān)。.理論和應(yīng)用的發(fā)展相互促進(jìn)。運(yùn)籌學(xué)的各個(gè)分支學(xué)科，都是由于實(shí)際問題的需要或以一定的實(shí)際問題為背景逐漸發(fā)展起來的。初期一些老的學(xué)科方面的專家對(duì)運(yùn)籌學(xué)做出了貢獻(xiàn)。隨后新的人才也逐漸涌現(xiàn)，新的理論相繼出現(xiàn)，這往往就開拓出新的領(lǐng)域。例如，繼Dantzig發(fā)明了求解線性規(guī)劃的單純形方法之后，又相繼出現(xiàn)了一批職業(yè)的線性規(guī)劃工作者，由于他們從事了大量的實(shí)踐活動(dòng)，反過來又進(jìn)一步促進(jìn)了線性規(guī)劃方法的進(jìn)一步發(fā)展，從而又出現(xiàn)了橢球法，內(nèi)點(diǎn)法等新的解線性規(guī)劃的方法。目前運(yùn)籌學(xué)家們?nèi)栽谧巫尾痪氲难芯啃录夹g(shù)、新方法，

10、使運(yùn)籌學(xué)這門年輕的學(xué)科不斷向前發(fā)展。3、運(yùn)籌學(xué)的主要內(nèi)容運(yùn)籌學(xué)發(fā)展到現(xiàn)在雖然只有四五十年的歷史，但是內(nèi)容豐富，涉及面廣，應(yīng)用范圍大，已形成了一個(gè)相當(dāng)龐大的學(xué)科。它的主要內(nèi)容一般應(yīng)包括線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃、多目標(biāo)規(guī)劃、網(wǎng)絡(luò)分析、排隊(duì)論、對(duì)策論、決策論、存儲(chǔ)論、可靠性理論、模型論、投入產(chǎn)出分析等等。它們中的每一個(gè)部分都可以獨(dú)立成冊(cè)，都有豐富的內(nèi)容。線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃、多目標(biāo)規(guī)劃這五個(gè)部分統(tǒng)稱為規(guī)劃論，它們主要是解決兩個(gè)方面的問題。一個(gè)方面的問題是對(duì)于給定的人力、物力和財(cái)力，怎樣才能發(fā)揮它們的最大效益；另一個(gè)方面的問題是對(duì)于給定的任務(wù)，怎樣才能用最少的人力、

11、物力和財(cái)力去完成它。網(wǎng)絡(luò)分析主要是研究解決生產(chǎn)組織、計(jì)劃管理中諸如最短路徑問題、最小連接問題、最小費(fèi)用流問題、以及最優(yōu)分派問題等。特別在設(shè)計(jì)和安排大型復(fù)雜工程時(shí)，網(wǎng)絡(luò)技術(shù)時(shí)重要的工具。排隊(duì)現(xiàn)象在日常生活中屢見不鮮，如機(jī)器等待修理，船舶等待裝卸，顧客等待服務(wù)等。它們有一個(gè)共同的問題，就是等待時(shí)間長了，會(huì)影響生產(chǎn)任務(wù)的完成，或者顧客會(huì)自動(dòng)離去而影響經(jīng)濟(jì)效益；如果增加修理工、裝卸碼頭和服務(wù)臺(tái)，固然能解決等待時(shí)間過長的問題，但又會(huì)蒙受修理工、碼頭和服務(wù)臺(tái)空閑的損失。這類問題的妥善解決是排對(duì)論的任務(wù)。對(duì)策論是研究具有厲害沖突的各方，如何制定出對(duì)自己有利從而戰(zhàn)勝對(duì)手的斗爭策略。例如，戰(zhàn)國時(shí)代田忌賽馬的故事

12、便是對(duì)策論的一個(gè)絕妙的例子。決策問題是普遍存在的，凡屬“舉棋不定”的事情都必須做出決策。人們之所以舉棋不定，是因?yàn)槿藗冊(cè)谥謱?shí)現(xiàn)某個(gè)預(yù)期目標(biāo)時(shí)，面前出現(xiàn)了多種情況，又有多種行動(dòng)方案可供選擇。決策者如何從中選擇一個(gè)最優(yōu)方案，才能達(dá)到他的預(yù)期目標(biāo)，這是決策論的研究任務(wù)。人們?cè)谏a(chǎn)和消費(fèi)過程中，都必須儲(chǔ)備一定數(shù)量的原材料、半成品或商品。存儲(chǔ)少了會(huì)因停工待料或失去銷售機(jī)會(huì)而遭受損失，存儲(chǔ)多了又會(huì)造成資金積壓、原材料及商品的損耗。因此，如何確定合理的存儲(chǔ)量、購貨批量和購貨周期至關(guān)重要，這便是存儲(chǔ)論要解決的問題。對(duì)于一個(gè)復(fù)雜的系統(tǒng)和設(shè)備，往往是由成千上萬個(gè)工作單元或零件組成的，這些單元或零件的質(zhì)量如何，將

13、直接影響到系統(tǒng)或設(shè)備的工作性能是否穩(wěn)定可靠。研究如何保證系統(tǒng)或設(shè)備的工作可靠性，這便是可靠性理論的任務(wù)。人們?cè)谏a(chǎn)實(shí)踐和社會(huì)實(shí)踐中遇到的事物往往是很復(fù)雜的，要想了解這些事物的變化規(guī)律，首先必須對(duì)這些事情的變化過程進(jìn)行適當(dāng)?shù)拿枋?，即所謂建立模型，然后就可通過對(duì)模型的研究來了解事物的變化規(guī)律。模型論就是從理論上和方法上來研究建立模型的基本技能。投入產(chǎn)出分析是通過研究多個(gè)部門的投入產(chǎn)出所必須遵守的綜合平衡原則來制定各個(gè)部門的發(fā)展計(jì)劃，借以從宏觀上控制、調(diào)整國民經(jīng)濟(jì)，以求得國民經(jīng)濟(jì)協(xié)調(diào)合理的發(fā)展。4、運(yùn)籌學(xué)的方法論 運(yùn)籌學(xué)的方法論包括以下幾個(gè)部分：(1) 提出需要解決的問題：提出需要解決的問題，確定目

14、標(biāo)，并分析問題所處的環(huán)境和約束條件。抓住主要矛盾，舍棄次要因素。(2) 建立模型：選用合適的數(shù)學(xué)模型來描述問題，確定決策變量，建立目標(biāo)函數(shù)、約束條件等，并據(jù)此建立相應(yīng)的運(yùn)籌學(xué)模型。(3) 求解模型：確定與數(shù)學(xué)模型有關(guān)的各種參數(shù)，選擇求解方法，求出解。解可以是最優(yōu)解、次優(yōu)解、滿意解。(4) 解的檢驗(yàn)：首先檢查求解步驟和程序有無錯(cuò)誤，然后檢查解是否反映現(xiàn)實(shí)問題。(5) 解的控制：通過靈敏度分析等方法，對(duì)所求的解進(jìn)行分析和評(píng)價(jià)，并據(jù)此對(duì)問題的提出和建模階段進(jìn)行修正。(6) 解的實(shí)施：提供決策所需的依據(jù)、信息和方案，幫助決策者決定處理問題的方針和行動(dòng)。另外，這六部分之間存在下圖所示關(guān)系：提出問題建立模

15、型求解模型解的檢驗(yàn)解的控制解的實(shí)施5、運(yùn)籌學(xué)的發(fā)展趨勢運(yùn)籌學(xué)作為一門學(xué)科，在理論和應(yīng)用方面，無論就廣度和深度來說都有著無限廣闊的前景。它不是一門衰老過時(shí)的學(xué)科，而使一門處于年輕發(fā)展時(shí)期的學(xué)科，這從運(yùn)籌學(xué)目前的發(fā)展趨勢便可看出。.運(yùn)籌學(xué)的理論研究將會(huì)得到進(jìn)一步系統(tǒng)的、深入的發(fā)展。數(shù)學(xué)規(guī)劃是20世紀(jì)40年代末期才開始出現(xiàn)的。經(jīng)過十多年的時(shí)間，到了20世紀(jì)60年代，它已形成了應(yīng)用數(shù)學(xué)中一個(gè)重要的分支，各種方法和各種理論紛紛出現(xiàn)，蔚為壯觀。但是，數(shù)學(xué)規(guī)劃也和別的學(xué)科一樣，在各種方法和理論出現(xiàn)以后，自然要走上統(tǒng)一的途徑。也就是說，用一種或幾種方法和理論把現(xiàn)存的東西統(tǒng)一在某些系統(tǒng)之下來進(jìn)行研究。而目前這種

16、由分散到統(tǒng)一、由具體到抽象的過程正在形成，而且將得到進(jìn)一步的發(fā)展。.運(yùn)籌學(xué)向一些新的研究領(lǐng)域發(fā)展。運(yùn)籌學(xué)的一個(gè)重要特點(diǎn)是應(yīng)用十分廣泛，近年來它正迅速的向一些新的研究領(lǐng)域或原來研究較少的領(lǐng)域發(fā)展，如研究世界性的問題，研究國家決策，或研究系統(tǒng)工程等。.運(yùn)籌學(xué)分散融化于其它學(xué)科，并結(jié)合其他學(xué)科一起發(fā)展。如數(shù)學(xué)規(guī)劃方法用于工程設(shè)計(jì)，常常叫做“最優(yōu)化方法”，已稱為工程技術(shù)中的一個(gè)有力研究工具；數(shù)學(xué)規(guī)劃用于Leontief的投入產(chǎn)出模型，也稱為西方計(jì)量經(jīng)濟(jì)學(xué)派常用的數(shù)學(xué)工具等等。.運(yùn)籌學(xué)沿原有的各學(xué)科分支向前發(fā)展，這仍是目前發(fā)展的一個(gè)重要方面。如規(guī)劃論，從研究當(dāng)目標(biāo)規(guī)劃進(jìn)而研究多目標(biāo)規(guī)劃，這當(dāng)然可以看成是

17、對(duì)事物進(jìn)行深入研究的自然延伸。事實(shí)上，在實(shí)際問題中想達(dá)到的目標(biāo)往往由多個(gè)，而且有些還是互相矛盾的。再如，從研究短期規(guī)劃到研究長期規(guī)劃，這種深入研究也是很自然的，因?yàn)閷?duì)于不少實(shí)際問題，人們主要關(guān)心的是未來的結(jié)果。.運(yùn)籌學(xué)中建立模型的問題將日益受到重視。從事實(shí)際問題研究的運(yùn)籌學(xué)工作者，常常感到他們所遇到的困難是如何把一個(gè)實(shí)際問題變成一個(gè)可以用數(shù)學(xué)方法或別的方法來處理的問題。就目前來說，關(guān)于運(yùn)籌學(xué)理論和方法的研究，遠(yuǎn)遠(yuǎn)超過了對(duì)上述困難的研究，要使運(yùn)籌學(xué)能保持它的生命力，這種研究非常必要。.運(yùn)籌學(xué)的發(fā)展將進(jìn)一步依賴于計(jì)算機(jī)的應(yīng)用和發(fā)展。電子計(jì)算機(jī)的問世與廣泛的應(yīng)用是運(yùn)籌學(xué)得以迅速發(fā)展的重要原因。實(shí)際問

18、題中的運(yùn)籌學(xué)問題，計(jì)算量一般都是很大的。只是有了存儲(chǔ)量大、計(jì)算速度快的計(jì)算機(jī)，才使得運(yùn)籌學(xué)得應(yīng)用成為可能，并反過來推動(dòng)了運(yùn)籌學(xué)的進(jìn)一步發(fā)展。如算法復(fù)雜性這個(gè)學(xué)科就是運(yùn)籌學(xué)與計(jì)算機(jī)相結(jié)合的產(chǎn)物?？傊\(yùn)籌學(xué)雖然只有四五十年的歷史，但發(fā)展如此之快，運(yùn)籌學(xué)工作者如此之多，都是前所未有的。運(yùn)籌學(xué)作為一門學(xué)科，在理論及應(yīng)用方面，無論就其廣度還是深度來說，都有著無限廣闊的前景。它對(duì)于加速我國的四個(gè)現(xiàn)代化建設(shè)必將起到十分重要的作用。參考文獻(xiàn)1 刁在筠，鄭漢鼎，劉家壯，劉桂真運(yùn)籌學(xué)北京：高等教育出版社，2001年9月第二版。- 42 -第一章 線性規(guī)劃【教學(xué)內(nèi)容】線性規(guī)劃模型，圖解法，可行區(qū)域的幾何結(jié)構(gòu)，基本

19、可行解及線性規(guī)劃的基本定理，單純形方法，單純形表，兩階段法，關(guān)于單純形方法的幾點(diǎn)說明，對(duì)偶線性規(guī)劃，對(duì)偶理論，對(duì)偶單純形法，求解線性規(guī)劃問題的幾個(gè)常用軟件?！窘虒W(xué)要求】要求學(xué)生理解線性規(guī)劃的標(biāo)準(zhǔn)形式，能熟練的將一般的線性規(guī)劃問題化為標(biāo)準(zhǔn)形式；掌握?qǐng)D解法，能用單純形法求解線性規(guī)劃問題；掌握靈敏度分析方法，能夠建立線性規(guī)劃模型及用常用軟件求解線性規(guī)劃問題?！窘虒W(xué)重點(diǎn)】線性規(guī)劃模型，圖解法，單純形方法，單純形表，兩階段法，對(duì)偶線性規(guī)劃，對(duì)偶單純形法，靈敏度分析。【教學(xué)難點(diǎn)】基本可行解及線性規(guī)劃的基本定理，單純形方法，對(duì)偶線性規(guī)劃，對(duì)偶理論，對(duì)偶單純形法?！窘滩膬?nèi)容及教學(xué)過程】線性規(guī)劃是運(yùn)籌學(xué)中應(yīng)用最

20、廣泛的方法之一，也是運(yùn)籌學(xué)的最基本的方法之一，網(wǎng)絡(luò)規(guī)劃，整數(shù)規(guī)劃，目標(biāo)規(guī)劃和多目標(biāo)規(guī)劃都是以線性規(guī)劃為基礎(chǔ)的。它是解決稀缺資源最優(yōu)分配的有效方法，使付出的費(fèi)用最小或獲得的收益最大。線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)基本分支，其應(yīng)用極其廣泛，其作用已為越來越多的人所重視。從線性規(guī)劃誕生至今的幾十年中，隨著計(jì)算機(jī)的逐漸普及，它越來越急速的滲透于工農(nóng)業(yè)生產(chǎn)、商業(yè)活動(dòng)、軍事行動(dòng)和科學(xué)研究的各個(gè)方面，為社會(huì)節(jié)省的財(cái)富、創(chuàng)造的價(jià)值無法估量。最近十多年來，線性規(guī)劃無論是在深度還是在廣度方面又都取得了重大進(jìn)展。本章先通過例子歸納線性規(guī)劃數(shù)學(xué)模型的一般形式，然后著重介紹有關(guān)線性規(guī)劃的一些基本概念、基本理論及解線性規(guī)劃問題的

21、若干方法。數(shù)學(xué)規(guī)劃的研究對(duì)象是計(jì)劃管理工作中有關(guān)安排和估值的問題，解決的主要問題是在給定條件下，按某一衡量指標(biāo)來尋找安排的最優(yōu)方案。它可以表示成求函數(shù)在滿足約束條件下的極大極小值問題。第一節(jié) 線性規(guī)劃模型線性規(guī)劃(Linear Programming，簡記為LP)問題研究的是在一組線性約束條件下一個(gè)線性函數(shù)最優(yōu)問題。§11 線性規(guī)劃問題舉例例1.1.1 某工廠用3種原料生產(chǎn)3種產(chǎn)品。已知單位產(chǎn)品所需原料數(shù)量如表1.1.1所示，試制訂出利潤最大的生產(chǎn)計(jì)劃。4 53單位產(chǎn)品的利潤（千元）200052800420P21500032P1原料可用量Q3Q2Q1單位產(chǎn)品所需 產(chǎn)品 原料數(shù)量(kg

22、) 原料3P3表1.1.1分析 設(shè)產(chǎn)品的產(chǎn)量為個(gè)單位，它們受到一些條件的限制。首先，它們不能取負(fù)值，即必須有；其次，根據(jù)題設(shè)，三種原料的消耗量分別不能超過它們的可用量，即它們又必須滿足：我們希望在以上約束條件下，求出，使總利潤達(dá)到最大，故求解該問題的數(shù)學(xué)模型為：類似這樣的問題非常多。§12 線性規(guī)劃模型以上例子具有這樣的特征：（1） 問題中要求有一組變量（決策變量），這組變量的一組定值就代表一個(gè)問題中的具體方案；（2） 存在一定的限制條件（約束條件），這些限制條件可以用一組線性等式或不等式來表示；（3） 有一個(gè)目標(biāo)要求（目標(biāo)函數(shù)），可以表示為決策變量的線性函數(shù)，并且要求這個(gè)目標(biāo)函數(shù)達(dá)

23、到最優(yōu)（最大或最小）。將這三個(gè)條件歸結(jié)在一起，就得到線性規(guī)劃問題。線性規(guī)劃問題的標(biāo)準(zhǔn)形式是具有如下形式的問題： (1.1.1)如果令，以及，則上述標(biāo)準(zhǔn)線性規(guī)劃問題可以用矩陣形式表示， (1.1.2)或 (1.1.3)除了線性規(guī)劃問題的標(biāo)準(zhǔn)形式之外，還有其它形式的線性規(guī)劃問題，但這些問題都可以通過一些簡單代換化為標(biāo)準(zhǔn)線性規(guī)劃問題。（1） 極大化問題對(duì)于目標(biāo)函數(shù)為極大化問題，如，可以等價(jià)地化為極小化問題，因?yàn)?。?） 不等式約束問題對(duì)于形如的不等式約束，可以通過引入所謂“松弛變量”化為等式約束（其中）；而對(duì)于形如的不等式約束，可以通過引入所謂“剩余變量”化為等式約束（其中）。（3） 無非負(fù)條件問題

24、對(duì)于變量無非負(fù)約束條件問題，可以定義，從而化為非負(fù)約束。因此，本章主要討論標(biāo)準(zhǔn)形式的線性規(guī)劃問題（1.1.1）的性質(zhì)和求解方法。第二節(jié) 線性規(guī)劃問題的可行域及最優(yōu)性條件§21 線性規(guī)劃問題的可行域（1） 凸組合與凸集定義1.2.1 設(shè)是維歐氏空間中的一個(gè)點(diǎn)集，稱為和的凸組合。定義1.2.2 設(shè)是維歐氏空間中的一個(gè)點(diǎn)集，若對(duì)任何與任何，都有就稱是一個(gè)凸集。圖1.2.1 凸集與非凸集凸集非凸集凸集與非凸集如圖1.2.1所示。（2） 線性規(guī)劃問題的可行域與凸集對(duì)于標(biāo)準(zhǔn)線性規(guī)劃問題（1.1.1），令表示它的可行域。定理1.2.1 線性規(guī)劃問題（1.1.1）的可行域是凸集。定義1.2.3 給定

25、及非零向量，稱集合是中的一個(gè)超平面。定理1.2.2 由超平面產(chǎn)生了兩個(gè)閉半空間、都是凸集。定義1.2.4 稱集合為多面凸集。非空有界的多面凸集稱為凸多面體。因此，線性規(guī)劃問題（1.1.1）的可行域是多面凸集。（3） 極點(diǎn)和極方向定義1.2.5 設(shè)為凸集，。若對(duì)任何，以及任何，都有則稱為凸集的一個(gè)極點(diǎn)。按此定義，平面上長方形的四個(gè)角點(diǎn)就是長方形區(qū)域的全部極點(diǎn)。平面圖形中每個(gè)頂點(diǎn)至少是兩條線的交點(diǎn)。一般對(duì)標(biāo)準(zhǔn)形式線性規(guī)劃問題（1.1.1），當(dāng)可行區(qū)域非空時(shí)，可以證明其可行域D一定有極點(diǎn)，每個(gè)極點(diǎn)至少是個(gè)超平面的交點(diǎn)（參見定理1.3.2）。至于多面凸集D的極點(diǎn)個(gè)數(shù)的有限性，在下一段我們給出了頂點(diǎn)的代

26、數(shù)結(jié)構(gòu)后，結(jié)論將會(huì)更清楚。定義1.2.6 設(shè)為凸集，。若存在以及所有，都有則稱為凸集的一個(gè)方向。定義1.2.7 設(shè)為凸集，是凸集的一個(gè)方向。若對(duì)凸集的任何方向，以及任何，當(dāng)時(shí)，必有 ，則稱為凸集的一個(gè)極方向。極點(diǎn)、方向和極方向如圖1.2.2所示。d1d2d圖1.2.2 極點(diǎn)（A、B）、方向（d、d1、d2）和極方向（d1、d2）定理1.2.3 設(shè)為的所有極點(diǎn)，為極方向，則當(dāng)且僅當(dāng)滿足 (1.2.1)即的充分必要條件為可以表示為的極點(diǎn)的凸組合與極方向的非負(fù)線性組合。注：這種表示方法不一定唯一。圖1.2.3 多面凸集中點(diǎn)的表示圖示d1d2dxx3x1x2x4多面凸集中點(diǎn)的表示如圖1.2.3所示。&

27、#167;22 線性規(guī)劃問題的最優(yōu)解（1） 兩個(gè)變量線性規(guī)劃問題的圖解法如果一個(gè)線性規(guī)劃問題只有兩個(gè)變量，我們可以直觀了解可行區(qū)域D的結(jié)構(gòu)，同時(shí)還可利用目標(biāo)函數(shù)與可行區(qū)域的關(guān)系利用圖解法求解該問題。例1.2.1 求解線性規(guī)劃解：可行區(qū)域D如圖1.2.4所示。在區(qū)域的內(nèi)部及邊界上的每一個(gè)點(diǎn)都是可行點(diǎn)，目標(biāo)函數(shù)的等直線(取定某一個(gè)常值)的法線方向（梯度方向）是函數(shù)值增加最快的方向（負(fù)梯度方向是函數(shù)值減小最快的方向）。沿著函數(shù)的負(fù)梯度方向移動(dòng)，函數(shù)值會(huì)減小，當(dāng)移動(dòng)到點(diǎn)時(shí)，再繼續(xù)移動(dòng)就離開區(qū)域D了。于是點(diǎn)就是最優(yōu)解，而最優(yōu)值為。圖1.2.4可以看出，點(diǎn)都是該線性規(guī)劃問題可行域的極點(diǎn)。如果將例1.2.1

28、中的目標(biāo)函數(shù)改為，可行區(qū)域不變，用圖解法求解的過程如圖1.2.5所示。圖1.2.5由于目標(biāo)函數(shù)的等值線與直線平行，當(dāng)目標(biāo)函數(shù)的等值線與直線重合(此時(shí))時(shí)，目標(biāo)函數(shù)達(dá)到最小值4，于是，線段上的每一個(gè)點(diǎn)均為該問題的最優(yōu)解。.特別地，線段的兩個(gè)端點(diǎn)，即可行區(qū)域D的兩個(gè)頂點(diǎn)，均是該線性規(guī)劃問題的最優(yōu)解。此時(shí)，最優(yōu)解不唯一。例1.2.2 用圖解法解線性規(guī)劃圖1.2.6解：該問題的可行區(qū)域如圖1.2.6所示。與上例求解方法類似，目標(biāo)函數(shù)沿著它的負(fù)法線方向移動(dòng)，由于可行域D無界，因此，移動(dòng)可以無限制下去，而目標(biāo)函數(shù)值一直減小，所以該線性規(guī)劃問題無有限最優(yōu)解，即該問題無界。從圖解法的幾何直觀容易得到下面幾個(gè)重

29、要結(jié)論：線性規(guī)劃的可行區(qū)域D是若干個(gè)半平面的交集，它形成了一個(gè)多面凸集（也可能是空集）。對(duì)于給定的線性規(guī)劃問題，如果它有最優(yōu)解，最優(yōu)解總可以在可行域D的某個(gè)頂點(diǎn)上達(dá)到。在這種情況下還包含兩種情況：有唯一解和有無窮多解。如果可行域無界，線性規(guī)劃問題的目標(biāo)函數(shù)可能有無界的情況。（2） 線性規(guī)劃問題的最優(yōu)解對(duì)于具有個(gè)變量的一般的線性規(guī)劃問題也有類似的結(jié)論。這可以通過多面凸集的表示定理（定理1.2.3）得到。定理1.2.4 如果標(biāo)準(zhǔn)線性規(guī)劃問題（1.1.1）的可行域非空，為的所有極點(diǎn)，為的所有極方向，則有： 如果（），則問題（1.1.1）有有限最優(yōu)解，并且若，且滿足上面條件的極點(diǎn)唯一，則為問題（1.1

30、.1）的唯一最優(yōu)解；若，則最優(yōu)解不唯一，都是問題（1.1.1）的最優(yōu)解，另外，所有的凸組合都是問題（1.1.1）的最優(yōu)解； 如果存在滿足，則問題（1.1.1）無有限最優(yōu)解； 如果對(duì)所有（）都有，且存在滿足，則問題（1.1.1）的最優(yōu)解不唯一，都是其最優(yōu)解，其中。定理1.2.4從代數(shù)角度給出了一般標(biāo)準(zhǔn)線性規(guī)劃問題（1.1.1）所有解的組成情況：當(dāng)目標(biāo)函數(shù)的梯度與可行域的所有極方向夾角小于900時(shí)，則問題有最優(yōu)解；另外，在這種情況下，當(dāng)目標(biāo)函數(shù)只在一個(gè)極點(diǎn)上達(dá)到最小，則問題有唯一最優(yōu)解；當(dāng)目標(biāo)函數(shù)在多于一個(gè)極點(diǎn)上同時(shí)達(dá)到最小，則問題有無窮多最優(yōu)解。當(dāng)目標(biāo)函數(shù)的梯度與可行域的某一極方向夾角大于900

31、時(shí)，則問題無有限最優(yōu)解。當(dāng)目標(biāo)函數(shù)的梯度與可行域的所有極方向夾角都不大于900時(shí)，并且與某一個(gè)極方向的夾角恰好為900，同時(shí)，目標(biāo)函數(shù)至少在一個(gè)極點(diǎn)上達(dá)到最小，則問題有無窮多最優(yōu)解。下面要講到的單純形方法正是通過一種算法來實(shí)現(xiàn)和檢驗(yàn)上面的各種情況。（3） 線性規(guī)劃問題的最優(yōu)性條件Kuhn和Tucker從理論上給出了線性規(guī)劃問題的最優(yōu)性條件，從理論上圓滿解決了線性規(guī)劃問題最優(yōu)解所滿足的條件。定理1.2.55 對(duì)于標(biāo)準(zhǔn)線性規(guī)劃問題（LP）：，是其最優(yōu)解的充分必要條件為存在，使得下式成立： (1.2.2) 但是，僅僅從這個(gè)定理出發(fā)，很難直接來求解線性規(guī)劃問題，因此，下面我們將介紹用于求解線性規(guī)劃問題

32、的一種迭代方法單純形方法。第三節(jié) 求解線性規(guī)劃問題的單純形方法§31 基本可行解及線性規(guī)劃問題的基本定理考慮標(biāo)準(zhǔn)形式的線性規(guī)劃問題（LP）：，假設(shè)秩，故中必有個(gè)線性無關(guān)的列向量，它們構(gòu)成滿秩方陣（為敘述方便，假定），把中其余各列組成的子陣記為，即，再把的分量也相應(yīng)地分為兩部分，記為和，則可記作即給任意一組值，則可得到對(duì)應(yīng)的的一組值，于是便是約束方程組的一個(gè)解。若令，就得到約束方程組的一種特殊形式的解。定義1.3.1 設(shè)是秩為的約束矩陣中的一個(gè)階滿秩子方陣，則稱為一個(gè)基(或基陣)。中個(gè)線性無關(guān)的列向量稱為基向量，變量中與之對(duì)應(yīng)的個(gè)分量稱為基變量，其余的分量稱為非基變量。令所有的非基變量

33、取值為零，得到的解，稱為相應(yīng)于的基本解。當(dāng)時(shí)，稱基本解為基本可行解，這時(shí)對(duì)應(yīng)的基稱為可行基。定理1.3.1 可行解是基本可行解的充要條件是它的正分量所對(duì)應(yīng)的中列向量線性無關(guān)。由定義知，基本可行解至少有個(gè)分量為零，從幾何上看它至少屬于個(gè)超平面的交集。定理1.3.2 是基本可行解的充要條件是是可行域D的極點(diǎn)。定理1.3.2是一個(gè)非常重要的定理，它將線性規(guī)劃問題可行域的極點(diǎn)與線性規(guī)劃問題的基本可行解一一對(duì)應(yīng)起來，因此，我們前面討論的線性規(guī)劃問題的最優(yōu)解（如果有的話）是在其可行域的極點(diǎn)上達(dá)到，對(duì)應(yīng)的就是在基本可行解上達(dá)到。所以，我們以后只需要討論基本可行解。定理1.3.3 一個(gè)標(biāo)準(zhǔn)形式的線性規(guī)劃問題（

34、1.1.1）：，若可行域非空，則至少有一個(gè)基本可行解。定理1.3.3給出了基本可行解的存在性。定理1.3.4 若標(biāo)準(zhǔn)形式的線性規(guī)劃問題（1.1.1）：有有限的最優(yōu)值，則一定存在一個(gè)基本可行解是最優(yōu)解。由基本可行解與可行基的這種對(duì)應(yīng)關(guān)系，我們知道給定一個(gè)標(biāo)準(zhǔn)形式的線性規(guī)劃問題，它最多有個(gè)可行基，因而基本可行解的個(gè)數(shù)不會(huì)超過，從而多面凸集D的頂點(diǎn)個(gè)數(shù)不會(huì)超過個(gè)。由定理1.3.4可知，線性規(guī)劃問題實(shí)際上是一個(gè)組合問題：即在有限個(gè)可行解中找出最優(yōu)解。一個(gè)基本可行解，如果它的所有的基變量都取正值，稱它是非退化的；如果有的基變量也取零值，稱它為退化的。一個(gè)線性規(guī)劃問題，如果它的所有基本可行解都是非退化的，

35、就說該問題是非退化的，否則說它是退化的。§32 求解線性規(guī)劃問題的單純形方法考慮標(biāo)準(zhǔn)線性規(guī)劃問題（LP）：解線性規(guī)劃問題著名的單純形方法(Simplex Method)是G.B.Dantzig在1947年提出的。本節(jié)我們介紹單純形方法的理論、基本計(jì)算步驟及具體實(shí)施運(yùn)算的單純形表。（1） 假設(shè)假設(shè)1.3.1 ；假設(shè)1.3.2 秩；假設(shè)1.3.3 中存在滿秩矩陣滿足；假設(shè)1.3.4 所考慮的（LP）問題是非退化的。上面四個(gè)基本假設(shè)是為了方便討論單純形方法而做的，實(shí)際上，在我們學(xué)完單純形方法后會(huì)發(fā)現(xiàn)，這四個(gè)假設(shè)都不是必須的。我們已經(jīng)知道，對(duì)于一個(gè)標(biāo)準(zhǔn)線性規(guī)劃問題（LP），如果它有最優(yōu)解，則

36、必可在某一基本可行解處達(dá)到，因而只需在基本可行解集合中尋求即可。單純形方法的主要思想就是先找出一個(gè)基本可行解，判別它是否為最優(yōu)解，如不是，就找一個(gè)更好的基本可行解，再進(jìn)行判別，如此迭代進(jìn)行，直至找到最優(yōu)解，或者判定該問題無有限最優(yōu)解。（2） 基本可行解的一些性質(zhì)由假定1.3.3和1.3.4，已找到了一個(gè)可行基，對(duì)應(yīng)一個(gè)非退化的基本可行解，此時(shí)可將方程組化成與之等價(jià)的方程組 (1.3.1)為敘述方便，這里假定，且有。記向量則(1.3.1)式可寫成或 (1.3.2)對(duì)目標(biāo)函數(shù)作相應(yīng)的變換，記為，其中是基變量對(duì)應(yīng)的系數(shù)，是非基變量對(duì)應(yīng)的系數(shù)，則 (1.3.3)對(duì)應(yīng)的目標(biāo)函數(shù)值用表示，則。由于，故當(dāng)時(shí)

37、，是一個(gè)第個(gè)分量為1，其余分量為0的維向量。故有令則從而(1.3.3)式可記為經(jīng)過變換后與原問題等價(jià)的問題是（對(duì)應(yīng)于基本可行解，（） (1.3.4) (1.3.5)它充分反映了基本可行解的特征。 最優(yōu)性準(zhǔn)則定理1.3.5 如果(1.3.4)式中，則為原問題的最優(yōu)解。另外，如果對(duì)應(yīng)于非基變量的每個(gè)，則為原問題的唯一最優(yōu)解；如果對(duì)應(yīng)于非基變量的某個(gè)，則雖然為原問題的最優(yōu)解，但此時(shí)最優(yōu)解不唯一。 無有限最優(yōu)解情況定理1.3.6 如果(1.3.4)中的向量的第個(gè)分量，而向量，則原問題無有限最優(yōu)解。另外，是（LP）問題的一個(gè)極方向。 基可行解可以改進(jìn)的條件|定理1.3.7 如果(1.3.4)中的向量的第

38、個(gè)分量，且同時(shí)向量，則原問題存在另一個(gè)基可行解，滿足。（3） 基可行解的改進(jìn)基可行解的改進(jìn)的思想是：從原來的非基變量中選一個(gè)變量讓它變?yōu)榛兞浚瑸楸ＷC新得到的解仍是基本可行解，必須從原來的基變量中選一個(gè)讓它變?yōu)榉腔兞俊Ｒ簿褪钦f新基與原有的基有個(gè)相同的列向量，僅有一列向量不同。應(yīng)該選擇哪一個(gè)非基變量變?yōu)榛兞磕?？若已知，因?yàn)?，與相對(duì)應(yīng)的是非基變量，因此當(dāng)變?yōu)榛兞繒r(shí)，它的值由零變?yōu)檎龜?shù)，比如說，其余的非基變量仍取值為零。由(1.3.4)式知對(duì)應(yīng)新解的目標(biāo)函數(shù)值為。至于的取值大小應(yīng)以保證新解是基本可行解為原則。尋找的具體方法如下，取有令顯然為使，只要即可，所以令 (1.3.6)從而保證了。因而是

39、可行解。由于向量組線性無關(guān)，則是基本可行解。的各分量為： (1.3.7)由，得，因此有由于相應(yīng)于基本可行解的向量有重要的作用，我們稱它為基本可行解的檢驗(yàn)數(shù)向量，它的各個(gè)分量稱為檢驗(yàn)數(shù)。注意，由假設(shè)1.3.4，在(1.3.6)式中最小比值是唯一的。如果檢驗(yàn)數(shù)向量有不止一個(gè)正分量，可以任意選取一個(gè)正分量作為定理中的。而選擇正值的最好策略是什么？這個(gè)問題至今尚未解決。一般常取最大的那個(gè)，所對(duì)應(yīng)的“入基”，而(1.3.6)算出的所對(duì)應(yīng)的“出基”，這就是從一個(gè)基本可行解移動(dòng)到另一個(gè)“更好”的基本可行解的過程。新舊基本可行解與的差別在于以原來的非基變量代替原來的基變量，而成為第個(gè)基變量，而變?yōu)榉腔兞?。?/p>

40、個(gè)過程稱為換基，或說進(jìn)行了一次迭代，稱為退出基列，為進(jìn)入基列，為離基變量，為進(jìn)基變量。（4） 單純形方法上面三個(gè)定理給出了單純形法的迭代步驟，給定一個(gè)基本可行解，計(jì)算與其對(duì)應(yīng)的檢驗(yàn)數(shù)向量。若，則就是最優(yōu)解；如果的某個(gè)分量，而，則原問題無界；如果且含有正分量，那么按照公式(1.3.6)和(1.3.7)式求出另一個(gè)基本可行解，使目標(biāo)函數(shù)值減少個(gè)單位。得到新的基本可行解后，再按以上程序進(jìn)行，這樣便可得到一個(gè)基本可行解的序列。在假設(shè)1.3.4的前提下，每迭代一次目標(biāo)函數(shù)值嚴(yán)格減少，因而序列中的基本可行解不可能重復(fù)出現(xiàn)。由于基本可行解的個(gè)數(shù)是有限的，故最終一定能找到最優(yōu)解或者判定問題無界，所以得到如下定

41、理。定理1.3.8 對(duì)于任何非退化的線性規(guī)劃問題，從任何基本可行解開始，經(jīng)過有限多次迭代，或得到一個(gè)基本可行的最優(yōu)解，或做出該線性規(guī)劃問題無界的判斷。在單純形方法的一次迭代過程中，迭代前后的兩個(gè)基有個(gè)相同的列向量，這樣的基稱為相鄰基。在幾何上，可以嚴(yán)格證明相鄰基所對(duì)應(yīng)的是可行域多面凸集的相鄰頂點(diǎn)。因此直觀的說，單純形方法就是從可行域多面凸集的一個(gè)頂點(diǎn)迭代到與其相鄰的另一個(gè)頂點(diǎn)，直至找到最優(yōu)解或判定問題無界。下面給出具體的計(jì)算步驟。單純形方法步驟第1步 找一個(gè)初始的可行基；第2步 求出對(duì)應(yīng)的典式及檢驗(yàn)數(shù)向量；第3步 求；第4步 若，停止。已找到最優(yōu)解及最優(yōu)值；第5步 若，停止.原問題無界；第6步

42、 求；第7步 以代替得到新的基，轉(zhuǎn)第2步。直接用公式進(jìn)行單純形法的迭代計(jì)算，對(duì)于用筆計(jì)算是很不方便的，其中最復(fù)雜的是進(jìn)行基變換，但實(shí)施基變換所用的實(shí)際上是消元法。因此，可以將單純形法的全部計(jì)算過程在一個(gè)類似增廣矩陣的數(shù)表上進(jìn)行，這種表格稱為單純形表3。第四節(jié) 解線性規(guī)劃問題的進(jìn)一步討論及例§41 兩階段法及關(guān)于單純形方法的幾點(diǎn)說明（1） 兩階段方法求初始可行解設(shè)原問題為 (1.4.1)所謂兩階段法，就是將線性規(guī)劃問題的求解過程分成兩個(gè)階段，第一個(gè)階段是判斷線性規(guī)劃是否有可行解，如果沒有可行解，計(jì)算停止；如果有可行解，按第一階段的方法可以求得一個(gè)初始基本可行解，使運(yùn)算進(jìn)入第二階段。第二

43、階段使從這個(gè)初始的基本可行解開始，使用單純形方法或者判定線性規(guī)劃問題無界，或者求得一個(gè)最優(yōu)解。第一階段：給問題(1.4.1)增加個(gè)人工變量，用單純形法解如下的輔助問題 (1.4.2)并且，問題（1.4.2）滿足假設(shè)1.3.1、1.3.2和1.3.3，是一個(gè)有個(gè)變量的標(biāo)準(zhǔn)形式線性規(guī)劃問題，且人工變量對(duì)應(yīng)的列構(gòu)成了一個(gè)階單位矩陣，基本可行解，所對(duì)應(yīng)的目標(biāo)函數(shù)值為，可以用單純形方法求解。問題(2.4.1)與其輔助問題(2.4.2)有如下關(guān)系：若原問題(2.4.1)的可行區(qū)域，輔助問題(2.4.2)的可行區(qū)域?yàn)?，則和是等價(jià)的。而(2.4.2)的當(dāng)?shù)慕猓?dāng)且僅當(dāng)有。由于，故輔助問題(2.4.2)的目標(biāo)函

44、數(shù)有下界，從而問題(2.4.2)必有最優(yōu)解。計(jì)算結(jié)果有如下三種可能情況：情形1 問題(2.4.2)的最優(yōu)值，且人工變量，皆為非基變量，此時(shí)我們已得到原問題(2.4.1)的一個(gè)基本可行解。情形2 問題(2.4.2)的最優(yōu)值，說明原問題沒有可行解。這時(shí)或者原問題的約束方程組不相容，即有秩秩；或者方程組雖相容，但沒有非負(fù)解?？傊?，運(yùn)算結(jié)束。情形3 問題(2.4.2)的最優(yōu)值，而某些人工變量雖然取值為零，但仍是基變量。當(dāng)情形1出現(xiàn)時(shí)，把人工變量對(duì)應(yīng)的列從單純形表中去掉，得到原問題的一個(gè)初始可行解，直接轉(zhuǎn)入第二階段：即對(duì)原目標(biāo)函數(shù)應(yīng)用通常的單純形法求解。當(dāng)情形3出現(xiàn)時(shí)，設(shè)基變量為，為一人工變量，顯然有。

45、我們觀察表中第行中非基變量的系數(shù)，即考察，如果它們不全為零，設(shè)，以為轉(zhuǎn)軸元進(jìn)行一次旋轉(zhuǎn)變換(注意，此時(shí)不要求)后，由于，所以，故值不變，最優(yōu)解也不變，只是將零值的變成了基變量，代替了取零值的人工變量，這樣使基變量中減少了一個(gè)人工變量（這種情況是退化情況）。如果非基變量的系數(shù)都為零，則這時(shí)有秩秩，這表明第個(gè)約束方程是多余的，將它刪去就可以了。如果基變量中還有其他人工變量，重復(fù)剛才的過程，直至基變量中沒有人工變量。事實(shí)上，通過兩階段方法我們已經(jīng)解決了開始介紹單純形方法的四個(gè)假設(shè)中的三個(gè)。同樣是使用單純形方法從算法角度已經(jīng)解決了：（1）什么條件下；（2）什么條件下秩；以及（3）什么條件下的問題。更重

46、要的是，解決這些假設(shè)并沒有用到其它工具，仍然是單純形方法。因此，單純形方法在求解線性規(guī)劃問題時(shí)是封閉的。（2） 關(guān)于退化問題5設(shè)給定了線性規(guī)劃 (1.4.3)的一個(gè)可行基，它對(duì)應(yīng)的基本可行解是，對(duì)應(yīng)的基陣是，應(yīng)該滿足約束條件，所以。如果是退化的基本可行解，它的基變量中就有一部分等于零，或者說向量被向量組用非負(fù)系數(shù)線性表示時(shí)，有的系數(shù)等于零。如果能夠?qū)ψ饕粋€(gè)微小的變動(dòng),使被用非負(fù)系數(shù)線性表示時(shí),系數(shù)全部是正的,那么就變成非退化的了。進(jìn)一步,如果變動(dòng)使得所有的基陣都有上述性質(zhì),那么這個(gè)變動(dòng)以后的線性規(guī)劃問題就是非退化的。給(1.4.1)的常數(shù)項(xiàng)后面加上，得到下列線性規(guī)劃問題: (1.4.4)稱(1

47、.4.4)為(1.4.3)的攝動(dòng)問題。這里是一個(gè)充分小的正數(shù),表示的次方。定理1.4.1 對(duì)于線性規(guī)劃問題(1.4.4),存在,使得對(duì)于任何滿足的,都有(1.4.4)是非退化的。定理1.4.2 在充分小時(shí),讓(1.4.4)中任一基本可行解中的等于零,就得到(1.4.3)的一個(gè)基本可行解。因此，只需要求解(1.4.4)即可。在求解(1.4.4)時(shí)，還需要解決如下三個(gè)問題：1、 在迭代過程中如何尋找的多項(xiàng)式；2、 在迭代過程中如何比較多項(xiàng)式的大??；3、 如何尋找(1.4.4)的初始可行解。對(duì)于第一個(gè)問題，由于的系數(shù)與的系數(shù)相同，所以多項(xiàng)式的系數(shù)就是對(duì)應(yīng)的系數(shù)。對(duì)于第二個(gè)問題，可以通過比較多項(xiàng)式的系

48、數(shù)來得到。對(duì)于第三個(gè)問題，可以通過(1.4.3)的基本可行解來尋找(1.4.4)的基本可行解。注意，在找到(1.4.3)的基本可行解后，將變量的下標(biāo)調(diào)換一下，讓基變量是就行。事實(shí)上，攝動(dòng)法的思想是這樣的：在維空間，個(gè)平面可以交到一個(gè)點(diǎn)，但是，有時(shí)候一個(gè)點(diǎn)不是個(gè)平面的交點(diǎn)，這個(gè)點(diǎn)是多于個(gè)平面相交得到的點(diǎn)。例如，金字塔的頂點(diǎn)，就是由四個(gè)平面相交而成的。對(duì)于這樣的點(diǎn)，從中任意找出個(gè)平面就可以得到這個(gè)點(diǎn)，因此，這樣的點(diǎn)的表示方法是不唯一的，正是這樣才有可能產(chǎn)生了循環(huán)。攝動(dòng)法的思想非常好，它將平面的常數(shù)項(xiàng)做適當(dāng)?shù)臄_動(dòng)，使這些平面產(chǎn)生一些微小的移動(dòng)，保證每個(gè)點(diǎn)恰好是個(gè)平面的交點(diǎn)。1955年，E. Beale找出一個(gè)很有趣的例子5,是一個(gè)退化的線性規(guī)劃問題，在用單純形方法求解時(shí)，產(chǎn)生了循環(huán)。用簡單的單純形方法得不到任何結(jié)論。攝動(dòng)法正是為了解決這個(gè)問題而出現(xiàn)的。§42 線性規(guī)劃問題的對(duì)偶及對(duì)偶單純形方法本節(jié)主要涉及三個(gè)問題：一是給定了標(biāo)準(zhǔn)線性規(guī)劃問題后，如何寫出它的對(duì)偶問題；二是研究線性規(guī)劃問題與其對(duì)偶問題之間的關(guān)系；最后，給出解線性規(guī)劃問題的對(duì)偶單純形算法。（1） 線性規(guī)劃問題的對(duì)偶在例1.1.1中討論了某工廠用3種原料生產(chǎn)3種產(chǎn)品，制訂最大生產(chǎn)計(jì)劃的問