1緒論及線性規(guī)劃

西安財(cái)經(jīng)學(xué)院精品課程運(yùn)籌學(xué)授課教案劉小冬，雷福民王命宇，許格妮西安財(cái)經(jīng)學(xué)院信息學(xué)院2005年12月-PAGE1-緒論——運(yùn)籌學(xué)概況一種科學(xué)只有在成功地運(yùn)用數(shù)學(xué)時(shí)，才算達(dá)到完善的地步。――――――————KarlMarx【教學(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ā)展趨勢(shì)?！窘虒W(xué)要求】要求學(xué)生了解運(yùn)籌學(xué)是逐步發(fā)展起來的，今后還將繼續(xù)發(fā)展；理解運(yùn)籌學(xué)整個(gè)過程的各個(gè)步驟；初步理解數(shù)學(xué)模型的建立過程?！窘虒W(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é)的方法、技術(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ā)展趨勢(shì)。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)用事例。例如，廣為人知的我國戰(zhàn)國時(shí)期齊王和大臣田忌賽馬的故事：在謀士孫臏的策劃下，田忌竟以遜色于齊王馬匹的劣勢(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í)際運(yùn)用時(shí)卻并不好用。為此一些科學(xué)家研究如何合理運(yùn)用雷達(dá)開始進(jìn)行一類新問題的研究。因?yàn)樗c研究技術(shù)問題不同，就稱之為“運(yùn)用研究”(OperationalResearch)。為了進(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é)思想和方法的書籍和論文出現(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)籌學(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í)的運(yùn)籌研究取得成功的經(jīng)驗(yàn)在和平時(shí)期加以推廣應(yīng)用時(shí)，面臨著一個(gè)廣闊的研究領(lǐng)域。在這一領(lǐng)域中，對(duì)于運(yùn)籌學(xué)主要研究和解決什么問題有許多說法，至今爭(zhēng)論不休，實(shí)際上形成了一個(gè)在爭(zhēng)論中發(fā)展運(yùn)籌學(xué)的局面。在這四五十年中，我們能從它的爭(zhēng)論中看出運(yùn)籌學(xué)所具有的一些特點(diǎn)。=1\*GB2⑴.引進(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)。=2\*GB2⑵.系統(tǒng)性。運(yùn)籌學(xué)研究問題是從系統(tǒng)的觀點(diǎn)出發(fā)，研究全局性的問題，研究綜合優(yōu)化的規(guī)律，它是系統(tǒng)工程的主要理論基礎(chǔ)。=3\*GB2⑶.著重實(shí)際應(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)行靈敏度分析等。=4\*GB2⑷.跨學(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í)際問題的需要。從世界范圍來看，運(yùn)籌學(xué)的成敗以及應(yīng)用的廣泛程度，無不與有這樣的研究組織和這種組織的工作水平有關(guān)。=5\*GB2⑸.理論和應(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ù)、新方法，使運(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ù)，怎樣才能用最少的人力、物力和財(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ēng)策略。例如，戰(zhàn)國時(shí)代田忌賽馬的故事便是對(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ì)量如何，將直接影響到系統(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)提出需要解決的問題：提出需要解決的問題，確定目標(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)系：

提出問題提出問題建立模型求解模型解的檢驗(yàn)解的控制解的實(shí)施5、運(yùn)籌學(xué)的發(fā)展趨勢(shì)運(yùn)籌學(xué)作為一門學(xué)科，在理論和應(yīng)用方面，無論就廣度和深度來說都有著無限廣闊的前景。它不是一門衰老過時(shí)的學(xué)科，而使一門處于年輕發(fā)展時(shí)期的學(xué)科，這從運(yùn)籌學(xué)目前的發(fā)展趨勢(shì)便可看出。=1\*GB2⑴.運(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)行研究。而目前這種由分散到統(tǒng)一、由具體到抽象的過程正在形成，而且將得到進(jìn)一步的發(fā)展。=2\*GB2⑵.運(yùn)籌學(xué)向一些新的研究領(lǐng)域發(fā)展。運(yùn)籌學(xué)的一個(gè)重要特點(diǎn)是應(yīng)用十分廣泛，近年來它正迅速的向一些新的研究領(lǐng)域或原來研究較少的領(lǐng)域發(fā)展，如研究世界性的問題，研究國家決策，或研究系統(tǒng)工程等。=3\*GB2⑶.運(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é)工具等等。=4\*GB2⑷.運(yùn)籌學(xué)沿原有的各學(xué)科分支向前發(fā)展，這仍是目前發(fā)展的一個(gè)重要方面。如規(guī)劃論，從研究當(dāng)目標(biāo)規(guī)劃進(jìn)而研究多目標(biāo)規(guī)劃，這當(dāng)然可以看成是對(duì)事物進(jìn)行深入研究的自然延伸。事實(shí)上，在實(shí)際問題中想達(dá)到的目標(biāo)往往由多個(gè)，而且有些還是互相矛盾的。再如，從研究短期規(guī)劃到研究長期規(guī)劃，這種深入研究也是很自然的，因?yàn)閷?duì)于不少實(shí)際問題，人們主要關(guān)心的是未來的結(jié)果。=5\*GB2⑸.運(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é)能保持它的生命力，這種研究非常必要。=6\*GB2⑹.運(yùn)籌學(xué)的發(fā)展將進(jìn)一步依賴于計(jì)算機(jī)的應(yīng)用和發(fā)展。電子計(jì)算機(jī)的問世與廣泛的應(yīng)用是運(yùn)籌學(xué)得以迅速發(fā)展的重要原因。實(shí)際問題中的運(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)刁在筠，鄭漢鼎，劉家壯，劉桂真．運(yùn)籌學(xué)．北京：高等教育出版社，2001年9月第二版。第一章線性規(guī)劃【教學(xué)內(nèi)容】線性規(guī)劃模型，圖解法，可行區(qū)域的幾何結(jié)構(gòu)，基本可行解及線性規(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ì)偶單純形法，靈敏度分析?！窘虒W(xué)難點(diǎn)】基本可行解及線性規(guī)劃的基本定理，單純形方法，對(duì)偶線性規(guī)劃，對(duì)偶理論，對(duì)偶單純形法?！窘滩膬?nèi)容及教學(xué)過程】線性規(guī)劃是運(yùn)籌學(xué)中應(yīng)用最廣泛的方法之一，也是運(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ī)劃問題的若干方法。數(shù)學(xué)規(guī)劃的研究對(duì)象是計(jì)劃管理工作中有關(guān)安排和估值的問題，解決的主要問題是在給定條件下，按某一衡量指標(biāo)來尋找安排的最優(yōu)方案。它可以表示成求函數(shù)在滿足約束條件下的極大極小值問題。第一節(jié)線性規(guī)劃模型線性規(guī)劃(LinearProgramming，簡(jiǎn)記為LP)問題研究的是在一組線性約束條件下一個(gè)線性函數(shù)最優(yōu)問題?！?．1線性規(guī)劃問題舉例例1.1.1某工廠用3種原料生產(chǎn)3種產(chǎn)品。已知單位產(chǎn)品所需原料數(shù)量如表1.1.1所示，試制訂出利潤最大的生產(chǎn)計(jì)劃。4453單位產(chǎn)品的利潤（千元）200052800420P21500032P1原料可用量Q3Q2Q1單位產(chǎn)品所需產(chǎn)品原料數(shù)量(kg)原料3P3表1.1.1分析設(shè)產(chǎn)品的產(chǎn)量為個(gè)單位，，它們受到一些條件的限制。首先，它們不能取負(fù)值，即必須有；其次，根據(jù)題設(shè)，三種原料的消耗量分別不能超過它們的可用量，即它們又必須滿足：我們希望在以上約束條件下，求出，使總利潤達(dá)到最大，故求解該問題的數(shù)學(xué)模型為：類似這樣的問題非常多?！?．2線性規(guī)劃模型以上例子具有這樣的特征：?jiǎn)栴}中要求有一組變量（決策變量），這組變量的一組定值就代表一個(gè)問題中的具體方案；存在一定的限制條件（約束條件），這些限制條件可以用一組線性等式或不等式來表示；有一個(gè)目標(biāo)要求（目標(biāo)函數(shù)），可以表示為決策變量的線性函數(shù)，并且要求這個(gè)目標(biāo)函數(shù)達(dá)到最優(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ī)劃問題，但這些問題都可以通過一些簡(jiǎn)單代換化為標(biāo)準(zhǔn)線性規(guī)劃問題。極大化問題對(duì)于目標(biāo)函數(shù)為極大化問題，如，可以等價(jià)地化為極小化問題，因?yàn)?。不等式約束問題對(duì)于形如的不等式約束，可以通過引入所謂“松弛變量”化為等式約束（其中）；而對(duì)于形如的不等式約束，可以通過引入所謂“剩余變量”化為等式約束（其中）。無非負(fù)條件問題對(duì)于變量無非負(fù)約束條件問題，可以定義，從而化為非負(fù)約束。因此，本章主要討論標(biāo)準(zhǔn)形式的線性規(guī)劃問題（1.1.1）的性質(zhì)和求解方法。第二節(jié)線性規(guī)劃問題的可行域及最優(yōu)性條件§2．1線性規(guī)劃問題的可行域凸組合與凸集定義1.2.1設(shè)是維歐氏空間中的一個(gè)點(diǎn)集，，，，稱為和的凸組合。定義1.2.2設(shè)是維歐氏空間中的一個(gè)點(diǎn)集，若對(duì)任何與任何，都有就稱是一個(gè)凸集。圖1.2.1凸集與非凸集圖1.2.1凸集與非凸集凸集非凸集線性規(guī)劃問題的可行域與凸集對(duì)于標(biāo)準(zhǔn)線性規(guī)劃問題（1.1.1），令表示它的可行域。定理1.2.1線性規(guī)劃問題（1.1.1）的可行域是凸集。定義1.2.3給定及非零向量，稱集合是中的一個(gè)超平面。定理1.2.2由超平面產(chǎn)生了兩個(gè)閉半空間、都是凸集。定義1.2.4為多面凸集。非空有界的多面凸集稱為凸多面體。因此，線性規(guī)劃問題（1.1.1）的可行域是多面凸集。極點(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)的代數(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所示。dd1d2d圖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)的表示圖示圖1.2.3多面凸集中點(diǎn)的表示圖示d1d2dxx3x1x2x4§2．2線性規(guī)劃問題的最優(yōu)解兩個(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中的目標(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圖1.2.6解：該問題的可行區(qū)域如圖1.2.6圖1.2.6與上例求解方法類似，目標(biāo)函數(shù)沿著它的負(fù)法線方向移動(dòng)，由于可行域D無界，因此，移動(dòng)可以無限制下去，而目標(biāo)函數(shù)值一直減小，所以該線性規(guī)劃問題無有限最優(yōu)解，即該問題無界。從圖解法的幾何直觀容易得到下面幾個(gè)重要結(jié)論：=1\*GB2⑴．線性規(guī)劃的可行區(qū)域D是若干個(gè)半平面的交集，它形成了一個(gè)多面凸集（也可能是空集）。=2\*GB2⑵．對(duì)于給定的線性規(guī)劃問題，如果它有最優(yōu)解，最優(yōu)解總可以在可行域D的某個(gè)頂點(diǎn)上達(dá)到。在這種情況下還包含兩種情況：有唯一解和有無窮多解。=3\*GB2⑶．如果可行域無界，線性規(guī)劃問題的目標(biāo)函數(shù)可能有無界的情況。線性規(guī)劃問題的最優(yōu)解對(duì)于具有個(gè)變量的一般的線性規(guī)劃問題也有類似的結(jié)論。這可以通過多面凸集的表示定理（定理1.2.3）得到。定理1.2.4如果標(biāo)準(zhǔn)線性規(guī)劃問題（1.1.1）的可行域非空，為的所有極點(diǎn)，為的所有極方向，則有：=1\*GB2⑴如果（），則問題（1.1.1）有有限最優(yōu)解，并且若，且滿足上面條件的極點(diǎn)唯一，則為問題（1.1.1）的唯一最優(yōu)解；若，則最優(yōu)解不唯一，都是問題（1.1.1）的最優(yōu)解，另外，所有的凸組合都是問題（1.1.1）的最優(yōu)解；=2\*GB2⑵如果存在滿足，則問題（1.1.1）無有限最優(yōu)解；=3\*GB2⑶如果對(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時(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)上面的各種情況。線性規(guī)劃問題的最優(yōu)性條件Kuhn和Tucker從理論上給出了線性規(guī)劃問題的最優(yōu)性條件，從理論上圓滿解決了線性規(guī)劃問題最優(yōu)解所滿足的條件。定理1.2.5[5]對(duì)于標(biāo)準(zhǔn)線性規(guī)劃問題（LP）：，是其最優(yōu)解的充分必要條件為存在，使得下式成立：(1.2.2)但是，僅僅從這個(gè)定理出發(fā)，很難直接來求解線性規(guī)劃問題，因此，下面我們將介紹用于求解線性規(guī)劃問題的一種迭代方法——單純形方法。第三節(jié)求解線性規(guī)劃問題的單純形方法§3．1基本可行解及線性規(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è)分量稱為基變量，其余的分量稱為非基變量。令所有的非基變量取值為零，得到的解，稱為相應(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ī)劃問題（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ī)劃問題，如果它的所有基本可行解都是非退化的，就說該問題是非退化的，否則說它是退化的?！?．2求解線性規(guī)劃問題的單純形方法考慮標(biāo)準(zhǔn)線性規(guī)劃問題（LP）：解線性規(guī)劃問題著名的單純形方法(SimplexMethod)是G.B.Dantzig在1947年提出的。本節(jié)我們介紹單純形方法的理論、基本計(jì)算步驟及具體實(shí)施運(yùn)算的單純形表。假設(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)解，則必可在某一基本可行解處達(dá)到，因而只需在基本可行解集合中尋求即可。單純形方法的主要思想就是先找出一個(gè)基本可行解，判別它是否為最優(yōu)解，如不是，就找一個(gè)更好的基本可行解，再進(jìn)行判別，如此迭代進(jìn)行，直至找到最優(yōu)解，或者判定該問題無有限最優(yōu)解。基本可行解的一些性質(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í)，是一個(gè)第個(gè)分量為1，其余分量為0的維向量。故有令則從而(1.3.3)式可記為經(jīng)過變換后與原問題等價(jià)的問題是（對(duì)應(yīng)于基本可行解，（））(1.3.4)(1.3.5)它充分反映了基本可行解的特征。=1\*GB3①最優(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)解不唯一。=2\*GB3②無有限最優(yōu)解情況定理1.3.6如果(1.3.4)中的向量的第個(gè)分量，而向量，則原問題無有限最優(yōu)解。另外，是（LP）問題的一個(gè)極方向。=3\*GB3③基可行解可以改進(jìn)的條件|定理1.3.7如果(1.3.4)中的向量的第個(gè)分量，且同時(shí)向量，則原問題存在另一個(gè)基可行解，滿足。|基可行解的改進(jìn)基可行解的改進(jìn)的思想是：從原來的非基變量中選一個(gè)變量讓它變?yōu)榛兞?，為保證新得到的解仍是基本可行解，必須從原來的基變量中選一個(gè)讓它變?yōu)榉腔兞?。也就是說新基與原有的基有個(gè)相同的列向量，僅有一列向量不同。應(yīng)該選擇哪一個(gè)非基變量變?yōu)榛兞磕兀咳粢阎?，因?yàn)椋c相對(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)從而保證了。因而是可行解。由于向量組線性無關(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)榉腔兞?。整個(gè)過程稱為換基，或說進(jìn)行了一次迭代，稱為退出基列，為進(jìn)入基列，為離基變量，為進(jìn)基變量。單純形方法上面三個(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)解或者判定問題無界，所以得到如下定理。定理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步求；第7步以代替得到新的基，轉(zhuǎn)第2步。直接用公式進(jìn)行單純形法的迭代計(jì)算，對(duì)于用筆計(jì)算是很不方便的，其中最復(fù)雜的是進(jìn)行基變換，但實(shí)施基變換所用的實(shí)際上是消元法。因此，可以將單純形法的全部計(jì)算過程在一個(gè)類似增廣矩陣的數(shù)表上進(jìn)行，這種表格稱為單純形表[3]。第四節(jié)解線性規(guī)劃問題的進(jìn)一步討論及例§4．1兩階段法及關(guān)于單純形方法的幾點(diǎn)說明兩階段方法求初始可行解設(shè)原問題為(1.4.1)所謂兩階段法，就是將線性規(guī)劃問題的求解過程分成兩個(gè)階段，第一個(gè)階段是判斷線性規(guī)劃是否有可行解，如果沒有可行解，計(jì)算停止；如果有可行解，按第一階段的方法可以求得一個(gè)初始基本可行解，使運(yùn)算進(jìn)入第二階段。第二階段使從這個(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)函數(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è)基變量為，為一人工變量，顯然有。我們觀察表中第行中非基變量的系數(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）什么條件下的問題。更重要的是，解決這些假設(shè)并沒有用到其它工具，仍然是單純形方法。因此，單純形方法在求解線性規(guī)劃問題時(shí)是封閉的。關(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.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在迭代過程中如何尋找的多項(xiàng)式；在迭代過程中如何比較多項(xiàng)式的大??；如何尋找(1.4.4對(duì)于第一個(gè)問題，由于的系數(shù)與的系數(shù)相同，所以多項(xiàng)式的系數(shù)就是對(duì)應(yīng)的系數(shù)。對(duì)于第二個(gè)問題，可以通過比較多項(xiàng)式的系數(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ǎn)單的單純形方法得不到任何結(jié)論。攝動(dòng)法正是為了解決這個(gè)問題而出現(xiàn)的?！?．2線性規(guī)劃問題的對(duì)偶及對(duì)偶單純形方法本節(jié)主要涉及三個(gè)問題：一是給定了標(biāo)準(zhǔn)線性規(guī)劃問題后，如何寫出它的對(duì)偶問題；二是研究線性規(guī)劃問題與其對(duì)偶問題之間的關(guān)系；最后，給出解線性規(guī)劃問題的對(duì)偶單純形算法。線性規(guī)劃問題的對(duì)偶在例1.1.1中討論了某工廠用3種原料生產(chǎn)3種產(chǎn)品，制訂最大生產(chǎn)計(jì)劃的問題，構(gòu)造了一個(gè)線性規(guī)劃問題?，F(xiàn)從另外一個(gè)角度來討論這個(gè)問題。假設(shè)該廠的決策者決定不生產(chǎn)產(chǎn)品，而將其所有3種原料外售。這時(shí)工廠的決策者就要考慮給每種資源如何定價(jià)的問題。設(shè)用分別表示出讓單位原料的單價(jià)。在作決策時(shí)，作如下比較：若用2個(gè)單位原料和3個(gè)單位原料可生產(chǎn)1件產(chǎn)品，獲利3千元，那么生產(chǎn)1件產(chǎn)品的原料出售的所有收入不應(yīng)低于生產(chǎn)1件產(chǎn)品的利潤，因此就有同理，有把工廠所有原料都出售，其收入為從工廠的決策者來看，越大越好，但從接受者來看，他的支付越少越好，所以工廠的決策者只能在滿足不小于所有產(chǎn)品利潤的條件下，使其總收入盡可能的小，他才能實(shí)現(xiàn)其意愿，所以得到另一個(gè)規(guī)劃問題：這個(gè)線性規(guī)劃問題稱為例1.1.1一般，對(duì)于標(biāo)準(zhǔn)線性規(guī)劃問題(1.4.定義其對(duì)偶問題為(1.4.對(duì)偶理論線性規(guī)劃問題及其對(duì)偶問題之間的有如下關(guān)系。定理1.4.3如果一個(gè)線性規(guī)劃問題有最優(yōu)解，則它的對(duì)偶問題也有最優(yōu)解，且它們的最優(yōu)值相等。定理1.4.4若分別是原始問題及其對(duì)偶問題的可行解，則分別是原始、對(duì)偶問題最優(yōu)解的充要條件是。事實(shí)上，在用單純形方法求解標(biāo)準(zhǔn)線性規(guī)劃問題時(shí)，一旦找到了一個(gè)基，令，則就是對(duì)偶問題的一組解；另外，如果是最優(yōu)基，則就是對(duì)偶問題的最優(yōu)解。對(duì)偶單純形方法根據(jù)對(duì)偶性，我們還可以給出解標(biāo)準(zhǔn)線性規(guī)劃問題的另一種方法——對(duì)偶單純形法。單純形方法的最優(yōu)性準(zhǔn)則是：當(dāng)基本可行解對(duì)應(yīng)的檢驗(yàn)數(shù)向量有(1.4.7)時(shí)，為最優(yōu)解。其中為對(duì)應(yīng)的可行基，?？梢哉J(rèn)為(1.4.7)式是對(duì)偶變量的可行性表示。因此單純形方法可以解釋為它是在保持一個(gè)原始問題可行解的前提下，向?qū)ε伎尚薪獾姆较虻?，這樣的算法稱為原始算法。同樣，我們可以從一個(gè)對(duì)偶可行解開始，保持對(duì)偶問題的可行性，向原始可行解的方向迭代，這樣的算法稱為對(duì)偶單純形法。假設(shè)已有原始問題的一個(gè)基本解（但不是可行解）和一個(gè)對(duì)偶問題的可行解（即原問題的檢驗(yàn)數(shù)向量），那么，為減少原始問題的不可行性，我們選擇這樣一個(gè)行，作為旋轉(zhuǎn)行，它對(duì)應(yīng)于原始不可行解的分量。通過旋轉(zhuǎn)變換，我們希望增加當(dāng)前的目標(biāo)函數(shù)值，且保持對(duì)偶解的可行性。假設(shè)以為轉(zhuǎn)軸元作旋轉(zhuǎn)變換，目標(biāo)函數(shù)值變?yōu)?，新的檢驗(yàn)數(shù)為。因?yàn)橐延?，，要增加值，則要求轉(zhuǎn)軸元；要保持對(duì)偶的可行性，則要求(1.4.8)已有，，，故僅需對(duì)于的元素必須有(1.4.9)因此旋轉(zhuǎn)列的選取由下式確定(1.4.10)由此可以得到對(duì)偶單純形法的計(jì)算步驟。對(duì)偶單純形方法步驟第1步列出初始單純形表（它含有原始問題的一個(gè)基本解和對(duì)偶問題的一個(gè)可行解）。第2步求。第3步若，停止。已找到原問題的最優(yōu)解及最優(yōu)值。第4步若，則原始問題無可行解，停止。第5步求。第6步以為轉(zhuǎn)軸元作一次旋轉(zhuǎn)變換，轉(zhuǎn)第2步。對(duì)于如下線性規(guī)劃問題(1.4.11)使用對(duì)偶單純形法比用原始單純形法更具有優(yōu)越性。因?yàn)槿绻褂脝渭冃畏椒?，首先，需要給問題(1.4.11)增加個(gè)剩余變量，再增加個(gè)人工變量，用兩階段方法來求解。這使問題的規(guī)模增加了很多。但是，如果使用對(duì)偶單純形方法，直接給問題(1.4.11)增加個(gè)剩余變量，就已經(jīng)得到了原問題的滿足最優(yōu)性條件的不可行解，可以直接使用對(duì)偶單純形方法來求解。事實(shí)上，定理1.2.5給出的就是關(guān)于標(biāo)準(zhǔn)線性規(guī)劃問題和其對(duì)偶問題解的一些性質(zhì)。式(1.2.2)的第一個(gè)條件，就是原問題的約束條件；第二個(gè)條件，即就是其對(duì)偶的約束條件；第三個(gè)條件，即稱為互補(bǔ)松弛條件。詳細(xì)討論參見[5]?！?．3線性規(guī)劃問題的靈敏度分析再考慮例1.2.1中的解線性規(guī)劃其可行區(qū)域D如圖1.4.1所示，點(diǎn)是最優(yōu)解。事實(shí)上，只要目標(biāo)函數(shù)的負(fù)梯度方向在和，點(diǎn)都是最優(yōu)解。對(duì)于一個(gè)線性規(guī)劃問題，研究當(dāng)數(shù)據(jù)變動(dòng)時(shí)解的變化情況是很重要的。在本節(jié)內(nèi)，我們僅研究個(gè)別數(shù)據(jù)變化時(shí)導(dǎo)致解變化的情況，這就是靈敏度分析問題。改變價(jià)值向量考慮如下的LP問題(1.4.12)假定已得到它的最優(yōu)解，最優(yōu)基本可行解，對(duì)應(yīng)的可行基為，(1.4.12)等價(jià)于：(1.4.13)圖1.4.1(1.4.14圖1.4.1讓我們來考慮(1.4.12)中的數(shù)據(jù)在什么范圍內(nèi)變化時(shí)，最優(yōu)解不會(huì)變化（雖然值可能會(huì)改變）。在實(shí)際問題中，改變價(jià)值向量或改變右端向量是經(jīng)常發(fā)生的。下面我們先討論改變價(jià)值向量的情況。當(dāng)問題(1.4.12)中的價(jià)值向量變?yōu)?，而約束系數(shù)矩陣和右端向量不變時(shí)，可行區(qū)域沒有變，因此原來的最優(yōu)基本可行解還是新問題的基本可行解，但對(duì)新問題來說，所對(duì)應(yīng)的檢驗(yàn)數(shù)向量和目標(biāo)函數(shù)值應(yīng)作相應(yīng)變動(dòng)，按公式我們有故只需計(jì)算(1.4.13)中的系數(shù)。當(dāng)時(shí)，仍為新問題的最優(yōu)解。當(dāng)價(jià)值向量只有一個(gè)分量變成，并且是非基變量時(shí)，情況很簡(jiǎn)單。由單純形法的計(jì)算公式知，只有起變化，新的檢驗(yàn)數(shù)應(yīng)為(1.4.15)若，即時(shí)，還是新問題的最優(yōu)解。改變右端向量設(shè)右端向量變成，(1.4.13)中的檢驗(yàn)數(shù)向量不變，仍有，只需計(jì)算，如果只改變右端向量中的一個(gè)分量，則計(jì)算還可簡(jiǎn)化為(1.4.16)這里表示矩陣的第列向量。顯然，如果，即時(shí)，最優(yōu)解不變（值可能發(fā)生了變化）。關(guān)于靈敏度問題的詳細(xì)討論，參見[5]?！?．4線性規(guī)劃問題的一些例子示例例1.4.1(1.4.解增加人工變量得到輔助問題(1.4.用單純形方法求解(1.4.18)，得到輔助問題的一個(gè)最優(yōu)解，第一階段結(jié)束，同時(shí)得到原問題的第一個(gè)基本可行解，對(duì)應(yīng)的(1.4.17)(1.4.直接開始第二階段運(yùn)算，用單純形方法求解得原問題的最優(yōu)解，其最優(yōu)值為，對(duì)應(yīng)的(1.4.17)(1.4.注：這里給出了求解過程，但是沒有詳細(xì)的求解步驟。我們的目的是讓學(xué)生了解單純形方法的求解過程，但是，又不希望學(xué)生用手工來完成這些運(yùn)算。線性規(guī)劃問題發(fā)展到現(xiàn)在，已經(jīng)有很完善的程序包和軟件包，學(xué)生只需要了解線性規(guī)劃單純形方法的原理，至于計(jì)算，可以通過程序包或軟件包來完成。參見本章第五節(jié)關(guān)于軟件的介紹?？梢詺w結(jié)為線性規(guī)劃問題的一些常見的實(shí)際問題例1.4.2（運(yùn)輸問題）要把某種物資從個(gè)發(fā)點(diǎn)，調(diào)運(yùn)給需要這種物資的個(gè)收點(diǎn)。已知，從運(yùn)一個(gè)單位的產(chǎn)品到的運(yùn)價(jià)為?，F(xiàn)在需要確定一個(gè)調(diào)運(yùn)方案，即確定由到的運(yùn)輸量，在滿足供需要求的條件下，使總運(yùn)輸費(fèi)用最省。建立的數(shù)學(xué)模型是：例1.4.3（營養(yǎng)問題）某飼養(yǎng)場(chǎng)所用混合飼料由種配料組成，要求這種混合飼料含有種不同的營養(yǎng)成分，并且每一份混合飼料中第種營養(yǎng)成分的含量不低于。已知每單位的第種配料中所含第種營養(yǎng)成分的量為，每單位的第種配料的價(jià)格為。在保證營養(yǎng)的條件下，應(yīng)如何配方，使混合飼料的費(fèi)用最省。設(shè)混合飼料中第種配料所用量為，建立的數(shù)學(xué)模型是例1.4.4（作物布局問題）設(shè)要在塊土地上，種植種不同的作物，第塊土地的面積為，第種作物的計(jì)劃種植面積為（假設(shè)），第種作物在第塊土地上的單位產(chǎn)量為，問應(yīng)如何合理安排種植計(jì)劃，才能使總產(chǎn)量最高。設(shè)為在第塊土地上種植第種作物的面積，建立的數(shù)學(xué)模型是：這樣的例子不勝枚舉。這些例子的具體內(nèi)容各不相同，但歸結(jié)出的數(shù)學(xué)模型都屬于同一類問題——線性規(guī)劃問題。第五節(jié)求解線性規(guī)劃問題的一些軟件§5．1求解線性規(guī)劃問題的Fortran語言程序文獻(xiàn)[6]中給出了求解線性規(guī)劃問題的多功能程序，包括單純形算法、對(duì)偶單純形算法、對(duì)偶單純形交叉算法和靈敏度分析。用Fortran-IV算法語言編寫，有一定的靈活性，適合于二次再開發(fā)。該軟件的程序、說明見該書所配光盤?！?．2求解線性規(guī)劃問題的LINDO軟件包[7,8,9,10]LINDO軟件介紹LINDO(LinearINteractiveandDiscreteOptimizer)可以用于求解線性規(guī)劃（LP）、整數(shù)規(guī)劃（IP）和二次規(guī)劃（QP）。LINDO求解線性規(guī)劃問題（LP）采用的方法是單純形法。先尋找一個(gè)可行解，然后在此可行解的基礎(chǔ)上尋求最優(yōu)解。LINDO求解LP問題的結(jié)果分為：不可行解（NoFeasibleSolution）和可行解（FeasibleSolution）；可行解又分為：有最優(yōu)解（OptimalSolution）和無有限最優(yōu)解（UnboundedSolution）兩種情況。LINDO的主要設(shè)計(jì)原則是，如果一個(gè)用戶只是想解決一個(gè)簡(jiǎn)單的問題，就不應(yīng)該在學(xué)習(xí)LINDO的基本特性上花費(fèi)太多的準(zhǔn)備成本。示例例如，用LINDO求解這樣一個(gè)線性規(guī)劃問題：那么，只需要打開LINDO，然后按照下面的操作進(jìn)行即可。模型的輸入當(dāng)打開LINDO后，屏幕將出現(xiàn)如圖1.5.1所示的窗口。圖圖1.5.1標(biāo)題為“LINDO”的窗口是主窗口，它包含所有的其他窗口以及所有命令菜單和工具欄。里面的空白模型窗口用于輸入LINDO的程序代碼，代碼格式如下：max10x+15ysubjecttox<=10y<=12x+y<=16end輸入的結(jié)果如圖1.5.2所示。圖圖1.5.2注：LINDO中已假設(shè)所有的變量都是非負(fù)的，所以非負(fù)約束不必再輸入；另外，LINDO也不區(qū)分變量中的大小字符（均轉(zhuǎn)換為大寫）；約束條件中的“<=”及“>=”可用“>”及“<”代替，表示不等式“≥”和“≤”。約束條件在“SUBJECTTO”（或者只輸入ST）之后。執(zhí)行從Solve菜單選擇Solve命令，或者在窗口頂部的工具欄里按Solve按鈕，LINDO就會(huì)先對(duì)模型進(jìn)行編譯。首先，LINDO會(huì)檢查模型是否具有數(shù)學(xué)意義以及是否符合語法要求。如果模型不能通過這一步檢查，會(huì)看到以下報(bào)錯(cuò)信息：Anerroroccurredduringcompilationonline:n（產(chǎn)生錯(cuò)誤的行數(shù)），LINDO會(huì)自動(dòng)跳轉(zhuǎn)到發(fā)生錯(cuò)誤的行。檢查通過后，LINDO開始正式求解，這由一個(gè)叫LINDOsolver的處理器完成。當(dāng)solver初始化時(shí)，會(huì)在屏幕上顯示一個(gè)狀態(tài)窗口，如圖1.5.3所示。圖圖1.5.3這個(gè)狀態(tài)窗口可以顯示solver的進(jìn)度，下表是對(duì)各項(xiàng)數(shù)據(jù)/控制按鈕的說明：數(shù)據(jù)項(xiàng)/控制說明Status給出當(dāng)前解決方案的狀態(tài)，可能的值包括：Optimal（最優(yōu)的），F(xiàn)easible（可行的），Infeasible（不可行的）和Unbounded（無界的）Iterationssolver的迭代次數(shù)Infeasibility多余或錯(cuò)誤約束條件數(shù)量Objective目標(biāo)函數(shù)的當(dāng)前值BestIP標(biāo)示得到最優(yōu)整數(shù)解決方案值，該項(xiàng)只出現(xiàn)在IP（整數(shù)規(guī)劃）模型IPBoundIP模型中目標(biāo)的理論范圍Branches由LINDOIPsolver分生出來的整型變量個(gè)數(shù)ElapsedTimesolver啟動(dòng)后所經(jīng)過時(shí)間UpdateInterval狀態(tài)窗口更新周期（秒）。你可以把這個(gè)值設(shè)成任何一個(gè)非負(fù)數(shù)，如果把它設(shè)成零的話很可能會(huì)增加求解時(shí)間InterruptSolver按下該按鈕，solver將立刻停止并返回當(dāng)前得到的最優(yōu)解Close按下該按鈕關(guān)閉狀態(tài)窗口，solver繼續(xù)運(yùn)行。狀態(tài)窗口可以通過選取相應(yīng)命令重新打開當(dāng)solver完成優(yōu)化過程后將會(huì)提示你是否要進(jìn)行靈敏度和范圍分析。若不需要靈敏度和范圍分析，按下“No”按鈕即可關(guān)閉狀態(tài)窗口。此時(shí)，屏幕將會(huì)出現(xiàn)一個(gè)名為“ReportsWindow”的窗口。這個(gè)窗口里顯示的就是LINDO的輸出結(jié)果報(bào)告。如果需要存儲(chǔ)解決方案報(bào)告的話，可以把這些信息從ReportsWindow寫到另外一個(gè)磁盤文件里，方法是選取File|LogOutput命令。對(duì)于上述的例子，ReportsWindow里顯示的是模型的最優(yōu)解決方案，如圖1.5.4所示。按照順序，顯示LINDO求解問題的迭代次數(shù)、最優(yōu)目標(biāo)函數(shù)值、最優(yōu)變量值、松弛或剩余變量的取值，對(duì)偶變量的取值。本例中得到的最大值是145，這時(shí)x和y分別取值10和3。LINDO的進(jìn)一步說明LINDO也可以用來解決一些復(fù)雜的二次規(guī)劃和整數(shù)規(guī)劃問題。LINDO主要有三個(gè)基本使用模式。對(duì)于一些中小規(guī)模的問題，LINDO只要通過鍵盤輸入就可以方便地實(shí)現(xiàn)交互性良好的操作與使用。另外，LINDO也可以對(duì)外建文件進(jìn)行處理，只要這些文件里包含有必要的命令代碼和輸入數(shù)據(jù)，處理后就可以生成用于報(bào)告目的的文檔。最后，還可以自建子程序，然后直接與LINDO相結(jié)合形成一個(gè)包括你自己的代碼和LINDO本身的優(yōu)化庫的綜合程序。圖圖1.5.4§5．3求解線性規(guī)劃問題的LINGO軟件包LINGO軟件介紹LINGO是一種專門用于求解數(shù)學(xué)規(guī)劃問題的軟件包。LINGO主要用于求解線性規(guī)劃、非線性規(guī)劃、二次規(guī)劃、動(dòng)態(tài)規(guī)劃和整數(shù)規(guī)劃等問題，也可以用于求解一些線性和非線性方程組及代數(shù)方程求根等。LINGO中包含了一種建模語言和大量的常用函數(shù)，可供使用者在建立數(shù)學(xué)規(guī)劃問題的模型時(shí)調(diào)用。示例例如，用LINGO求解線性規(guī)劃問題：最基本的用法與LINDO類似，只需要打開LINGO，然后按照下面的操作進(jìn)行即可。模型的輸入當(dāng)打開LINGO后，屏幕將出現(xiàn)如圖1.5.5所示的窗口。圖圖1.5.5標(biāo)題為“LINGO”的窗口是主窗口，它包含所有的其他窗口以及所有命令菜單和工具欄。里面的空白窗口用于輸入LINGO的程序代碼，代碼格式如下：MODEL:min=21*x11+25*x12+7*x13+15*x14+51*x21+51*x22+37*x23+15*x24;x11+x12+x13+x14>=2000;x21+x22+x23+x24>=1000;x11+x21>=1700;x12+x22>=1100;x13+x23>=200;x14+x24>=100;END執(zhí)行從Solve菜單選擇Solve命令，或者在窗口頂部的工具欄里按Solve按鈕，LINGO就會(huì)先對(duì)模型進(jìn)行編譯，檢查模型是否具有數(shù)學(xué)意義以及是否符合語法要求。如果模型不能通過這一步檢查，會(huì)看到報(bào)錯(cuò)信息，并指出出錯(cuò)的語句。檢查通過后，LINGO開始正式求解。求解結(jié)果如圖1.5.6所示。此問題的解為：，，，，，，，，最優(yōu)值為：79600。LINGO程序注解MODEL：LINGO模型程序的開始標(biāo)志。END：LINGO模型程序的結(jié)束標(biāo)志。min=21*x11+25*x12+7*x13+15*x14+51*x21+51*x22+37*x23+15*x24：表明目標(biāo)函數(shù)是求的最小值。x11+x12+x13+x14>=2000：對(duì)應(yīng)約束條件。圖1.5.6由于LINGO默認(rèn)各變量非負(fù)，所以在程序中不需要專門的語句對(duì)應(yīng)于約束條件中的。圖1.5.6當(dāng)運(yùn)用LINGO求解此問題后，系統(tǒng)會(huì)彈出一個(gè)名為SolutionReport的文本框，其文本框中包含了求解的詳細(xì)信息，如下：Rows=7Vars=8Negervars=0(allarelinear)Nonzeros=30Constraintnonz=16(16are+-1)Density=0.476Smallestandlargestelementsinabsvalue=1.000002000.00No.<:0No.=:0No.>:6,Obj=MIN,GUBs<=4Singlecols=0Globaloptimalsolutionfoundatstep:9Objectivevalue:79600.00VariableValueReducedCostX111700.0000.0000000X121100.0000.0000000X13200.00000.0000000X140.000000015.00000X210.000000015.00000X220.000000011.00000X230.000000015.00000X241000.0000.0000000