線性規(guī)劃研究生演示文稿

線性規(guī)劃研究生演示文稿目前一頁\總數(shù)一百五十頁\編于十八點(diǎn)（優(yōu)選）線性規(guī)劃研究生目前二頁\總數(shù)一百五十頁\編于十八點(diǎn)venson)用運(yùn)籌學(xué)思想分析商業(yè)廣告和顧客心理，由此提出了存儲(chǔ)論中著名的“經(jīng)濟(jì)批量公式”。1947年，美國數(shù)學(xué)家丹捷格(G.B.Dantizg)發(fā)表了關(guān)于線性規(guī)劃的研究成果，所解決的問題是美國空軍軍事規(guī)劃時(shí)提出的，并給出了求解線性規(guī)劃問題的單純形算法。事實(shí)上，早在1939年蘇聯(lián)學(xué)者康托洛維奇(Л.В.Канторович)在解決工業(yè)生產(chǎn)組織和計(jì)劃問題時(shí)，已提出了類似線性規(guī)劃的模型，并給出了“解乘數(shù)法”的求解方法。由于當(dāng)時(shí)未被重視，直到1960年康目前三頁\總數(shù)一百五十頁\編于十八點(diǎn)托洛維奇再次發(fā)表了《最佳資源利用的經(jīng)濟(jì)計(jì)算》一書后，才受到國內(nèi)外的一致重視。為此康托洛維奇獲得了諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。因?yàn)樗c研究技術(shù)問題不同，就稱之為“運(yùn)用研究”或“操作研究”(OperationalResearch)。研究?jī)?nèi)容是：1.研究護(hù)航艦隊(duì)保護(hù)商船隊(duì)的編隊(duì)問題，即當(dāng)船隊(duì)遭受德國潛艇攻擊時(shí)，如何使船隊(duì)損失最??；2.研究反潛深水炸彈的合理爆炸深度，這使得德國潛艇被摧毀數(shù)增加了400%；3.研究船隊(duì)在遭受敵機(jī)攻擊時(shí)，大船應(yīng)急轉(zhuǎn)向而小船應(yīng)緩慢轉(zhuǎn)向的逃避方法，其結(jié)果，使船只在受敵機(jī)攻擊時(shí)，中彈船只數(shù)由47%降到29%。目前四頁\總數(shù)一百五十頁\編于十八點(diǎn)

在20世紀(jì)50年代中期，我國科學(xué)家錢學(xué)森、許國志等人將運(yùn)籌學(xué)由西方引入我國，并結(jié)合了我國的特點(diǎn)在國內(nèi)推廣應(yīng)用。在經(jīng)濟(jì)數(shù)學(xué)方面，特別是投入產(chǎn)出表的研究和應(yīng)用開展得較早。質(zhì)量控制(后改為質(zhì)量管理)的應(yīng)用也有特色。在此期間，以華羅庚敎?zhǔn)跒槭椎囊淮笈鷶?shù)學(xué)家加入到運(yùn)籌學(xué)的研究隊(duì)伍，使運(yùn)籌學(xué)的很多分支很快跟上當(dāng)時(shí)的國際水平。我國第一個(gè)運(yùn)籌學(xué)小組于1956年在中國科學(xué)院力學(xué)研究所成立，1960年在山東濟(jì)南召開全國應(yīng)用運(yùn)籌學(xué)的經(jīng)驗(yàn)交流和推廣會(huì)議，1962年在北京召開了全國運(yùn)籌學(xué)專業(yè)學(xué)術(shù)會(huì)議，1980年4月成立中國運(yùn)籌學(xué)學(xué)會(huì)。上世紀(jì)50年代中期，以華羅庚為首的一大批科學(xué)家加入到運(yùn)籌學(xué)的研究中，首先在一些企業(yè)、事業(yè)單位積極推廣優(yōu)選法、統(tǒng)籌法等運(yùn)籌學(xué)方法，取得顯著成果；并成立了優(yōu)選法、統(tǒng)籌法與經(jīng)濟(jì)數(shù)學(xué)研究會(huì)。學(xué)會(huì)主要研究運(yùn)籌學(xué)，但沒有稱為運(yùn)籌學(xué)。如今，運(yùn)籌學(xué)已經(jīng)成為所有大學(xué)的經(jīng)濟(jì)與管理學(xué)院、工學(xué)院與計(jì)算機(jī)專業(yè)、應(yīng)用數(shù)學(xué)專業(yè)的基礎(chǔ)課程。

目前五頁\總數(shù)一百五十頁\編于十八點(diǎn)二、運(yùn)籌學(xué)的工作步驟

運(yùn)籌學(xué)在解決大量實(shí)際問題的過程中形成了自己的工作步驟：1.提出和形成問題：即要弄清問題的目標(biāo)，可能的約束，問題的可控變量以及有關(guān)參數(shù)及有關(guān)資料。2.建立模型：即把問題中可控變量、參數(shù)和目標(biāo)與約束之間的關(guān)系用一定的模型表示出來。3.求解：用各種手段(主要是數(shù)學(xué)方法，也可用其它方法)將模型求解。解可以是最優(yōu)解、次優(yōu)解、滿意解.復(fù)雜模型的求解需用計(jì)算機(jī),解的精度要求由決策者提出目前六頁\總數(shù)一百五十頁\編于十八點(diǎn)4.解的檢驗(yàn)：首先檢驗(yàn)求解步驟和程序有無錯(cuò)誤，然后檢查解是否反映現(xiàn)實(shí)問題。5.解的控制：通過控制解的變化過程決定對(duì)解是否要作一定的修改。6.解的實(shí)施：是指將解用到實(shí)際中去，必須考慮到實(shí)際的問題，如向?qū)嶋H部門講清楚解的用法，在實(shí)施中可能產(chǎn)生的問題等。以上過程應(yīng)反復(fù)進(jìn)行。

目前七頁\總數(shù)一百五十頁\編于十八點(diǎn)三、運(yùn)籌學(xué)的應(yīng)用與展望在運(yùn)籌學(xué)的發(fā)展簡(jiǎn)史中，已提到了運(yùn)籌學(xué)在早期的應(yīng)用，主要在軍事領(lǐng)域。二次大戰(zhàn)后運(yùn)籌學(xué)的應(yīng)用轉(zhuǎn)向民用，主要應(yīng)用于：市場(chǎng)銷售：在廣告預(yù)算和媒介的選擇、競(jìng)爭(zhēng)性定價(jià)新產(chǎn)品開發(fā)、銷售計(jì)劃的制定等方面。(2)生產(chǎn)計(jì)劃：在總體計(jì)劃方面主要是從總體確定生產(chǎn)、存儲(chǔ)和勞動(dòng)力的配合等計(jì)劃以適應(yīng)波動(dòng)的需求計(jì)劃,主要用線性規(guī)劃和模擬的方法等。(3)庫存管理:主要應(yīng)用于多種物資庫存的管理,以確定合理的庫存量。(4)運(yùn)輸問題：各種運(yùn)輸?shù)恼{(diào)度與計(jì)劃安排。(5)財(cái)政和會(huì)計(jì)：這里主要涉及預(yù)算、貸款、成本分析、定價(jià)、投資、證券管理、現(xiàn)金管理等。用得較多的方法是：統(tǒng)計(jì)分析、數(shù)學(xué)規(guī)劃、決策分析。目前八頁\總數(shù)一百五十頁\編于十八點(diǎn)(6)人事管理：一是人員的獲得和需求估計(jì)；二是人才的開發(fā)，即進(jìn)行教育和培訓(xùn)；三是人員的分配；四是各類人員的合理利用問題；五是人才的評(píng)價(jià)，其中有如何測(cè)定一個(gè)人對(duì)組織、社會(huì)的貢獻(xiàn);六是工資和津貼的確定等。(7)設(shè)備維修、更新和可靠性、項(xiàng)目選擇和評(píng)價(jià)。(8)工程的優(yōu)化設(shè)計(jì)：這在建筑、電子、光學(xué)、機(jī)械和化工等領(lǐng)域都有應(yīng)用。(9)計(jì)算機(jī)和信息系統(tǒng)：(10)城市管理：包含了各種緊急服務(wù)系統(tǒng)的設(shè)計(jì)和運(yùn)用目前九頁\總數(shù)一百五十頁\編于十八點(diǎn)四、最優(yōu)化問題舉例1、多參數(shù)的曲線擬合問題已知熱敏電阻R依賴于溫度t的函數(shù)關(guān)系目前十頁\總數(shù)一百五十頁\編于十八點(diǎn)2、生成成本問題介紹Cobb-Douglas生產(chǎn)函數(shù)。目前十一頁\總數(shù)一百五十頁\編于十八點(diǎn)3、資源分配問題考慮將m種資源安排給n種活動(dòng)，問應(yīng)如何分配資源，才能使收益最大？目前十二頁\總數(shù)一百五十頁\編于十八點(diǎn)在某些實(shí)際應(yīng)用中，有時(shí)考慮的利潤(rùn)c1,c2,…cn并不是固定的數(shù)值，而是隨機(jī)變量，假定C是一個(gè)均值為目前十三頁\總數(shù)一百五十頁\編于十八點(diǎn)目前十四頁\總數(shù)一百五十頁\編于十八點(diǎn)這是線性分式規(guī)劃。目前十五頁\總數(shù)一百五十頁\編于十八點(diǎn)目前十六頁\總數(shù)一百五十頁\編于十八點(diǎn)最優(yōu)化的分類圖離散規(guī)劃整數(shù)規(guī)劃非線性最小二乘球面規(guī)劃非線性等式最優(yōu)化連續(xù)優(yōu)化離散優(yōu)化有約束無約束線性規(guī)劃不可微分規(guī)劃非線性規(guī)劃網(wǎng)絡(luò)規(guī)劃隨機(jī)規(guī)劃目前十七頁\總數(shù)一百五十頁\編于十八點(diǎn)參考書

1、盧向華，等著《運(yùn)籌學(xué)教程》，高等教育出版社2、錢頌迪，《運(yùn)籌學(xué)》，清華大學(xué)出版社3、林同曾，《運(yùn)籌學(xué)》，機(jī)械工業(yè)出版社

4、胡運(yùn)權(quán)，《運(yùn)籌學(xué)教程》，清華大學(xué)出版社目前十八頁\總數(shù)一百五十頁\編于十八點(diǎn)第一章線性規(guī)劃第一節(jié)線性規(guī)劃模型及其圖解法線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分枝。自1947年美國數(shù)學(xué)家丹捷格（G.B.Dantzig）提出了求解線性規(guī)劃問題的方法——單純形法之后，線性規(guī)劃在理論上趨于成熟，在實(shí)際中的應(yīng)用日益廣泛與深入。特別是在能用計(jì)算機(jī)來處理成千上萬個(gè)約束條件和變量的大規(guī)模線性規(guī)劃問題之后，它的適用領(lǐng)域更廣泛了。從解決技術(shù)問題中的最優(yōu)化設(shè)計(jì)到工業(yè)、農(nóng)業(yè)、商業(yè)、交通輸業(yè)、軍事、經(jīng)濟(jì)計(jì)劃與管理、決策等各個(gè)領(lǐng)域均可發(fā)揮作用；從范圍來看，小到一個(gè)小組的日常工作和計(jì)劃安排，大至整個(gè)部門以致國民經(jīng)濟(jì)計(jì)劃的最優(yōu)方案的提出，都有用武之地。它具有適應(yīng)性強(qiáng)、應(yīng)用廣泛、計(jì)算技術(shù)比較簡(jiǎn)單的特點(diǎn)，是現(xiàn)代管理科學(xué)的重要基礎(chǔ)和手段之一。目前十九頁\總數(shù)一百五十頁\編于十八點(diǎn)一、線性規(guī)劃模型線性規(guī)劃：就是一個(gè)線性函數(shù)在線性等式或不等式約束條件下的極值問題。線性規(guī)劃研究的問題主要有兩類：1、任務(wù)確定后，如何統(tǒng)籌安排，盡量做到用盡量少的人力和物力資源來完成任務(wù)；2、有一定量的人力、物力資源，如何安排使用他們，使完成的任務(wù)（創(chuàng)造的利潤(rùn)）最多。在生產(chǎn)管理和經(jīng)濟(jì)活動(dòng)中經(jīng)常提出這樣一類問題，即如何合理地利用有限的人力、物力、財(cái)力等資源，以便得到最好的經(jīng)濟(jì)效果。目前二十頁\總數(shù)一百五十頁\編于十八點(diǎn)例1：某工廠在計(jì)劃期內(nèi)安排生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)、A、B兩種原材料的消耗及兩種產(chǎn)品每件可獲利潤(rùn)見如下表所示：?jiǎn)柸绾伟才庞?jì)劃使該工廠獲利最多？III資源總量設(shè)備A1臺(tái)時(shí)2臺(tái)時(shí)8臺(tái)時(shí)設(shè)備B2臺(tái)時(shí)2臺(tái)時(shí)12臺(tái)時(shí)原材料A4公斤0公斤16公斤原材料B0公斤4公斤12公斤利潤(rùn)2元/件3元/件目前二十一頁\總數(shù)一百五十頁\編于十八點(diǎn)解：假設(shè)x1、x2分別表示在計(jì)劃期內(nèi)生產(chǎn)產(chǎn)品I、II的數(shù)量，則該計(jì)劃問題可用如下數(shù)學(xué)模型表示為：目標(biāo)函數(shù)Max

Z=2x1+3x2

約束條件目前二十二頁\總數(shù)一百五十頁\編于十八點(diǎn)例2某汽車廠生產(chǎn)大轎車和載重汽車，所需資源、資源可用量和產(chǎn)品價(jià)格如下表所示:大轎車載重汽車可用量鋼材（噸）221600工時(shí)(小時(shí))52.52500大轎車座椅400（輛）獲利(千元/輛)43問應(yīng)如何組織生產(chǎn)才能使工廠獲利最大？目前二十三頁\總數(shù)一百五十頁\編于十八點(diǎn)例2的數(shù)學(xué)模型s.t.,目前二十四頁\總數(shù)一百五十頁\編于十八點(diǎn)例3下料問題某工廠要做100套鋼架，每套有長(zhǎng)2.9米、2.1米和1.5米的圓鋼組成，已知原料長(zhǎng)7.4米，問應(yīng)如何下料使需用的原材料最省。解：如果從每根7.4米長(zhǎng)的原料上各截一根2.9米、2.1米和1.5米長(zhǎng)的圓鋼，則還余0.9米，用100根原料，浪費(fèi)預(yù)料共90米?，F(xiàn)采用套裁的辦法，設(shè)計(jì)五種方案，如表1.2所示。目前二十五頁\總數(shù)一百五十頁\編于十八點(diǎn)表圓鋼套裁方案方案長(zhǎng)度一二三四五2.92.11.513210221213合計(jì)（米）料頭（米）7.407.30.17.20.27.10.36.60.8目前二十六頁\總數(shù)一百五十頁\編于十八點(diǎn)例3數(shù)學(xué)模型設(shè)個(gè)方案各下料根，則有（1-5）目前二十七頁\總數(shù)一百五十頁\編于十八點(diǎn)以上三個(gè)例子,從數(shù)學(xué)上來講,它們的共同特征是:每個(gè)問題都用一組決策變量(x1,x2,···,xn)表示某一方案,這組未知數(shù)的值就代表一個(gè)具體的方案,通常要求這些未知數(shù)取值是非負(fù)的。(2)存在一定的限制條件(稱為約束條件),這些條件都可以用關(guān)于決策變量的一組線性等式或不等式來表示。(3)都有一個(gè)目標(biāo)要求,并且這個(gè)目標(biāo)可表示為這組決策變量的線性函數(shù)(稱為目標(biāo)函數(shù)),按研究問題的不同,要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。滿足以上三個(gè)條件的數(shù)學(xué)模型稱為線性規(guī)劃數(shù)學(xué)模型。目前二十八頁\總數(shù)一百五十頁\編于十八點(diǎn)其一般形式為(1.1)和(1.2)形式。在該模型中,方程(1.1)稱為目標(biāo)函數(shù);(1.2)稱為約束條件。目前二十九頁\總數(shù)一百五十頁\編于十八點(diǎn)二、圖解法對(duì)于簡(jiǎn)單的線性規(guī)劃問題(只有兩個(gè)決策變量的線性規(guī)劃問題),我們通過圖解法可以對(duì)它進(jìn)行求解。我們可以由例1具體給出求解的方法。例1：用圖解法求解線性規(guī)劃問題。MAXZ=2x1+3x2s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12x1，x2≥0目前三十頁\總數(shù)一百五十頁\編于十八點(diǎn)

x1+2x2=8解得：x1=44x1=16x2=2這就是本線性規(guī)劃問題的最優(yōu)解。此時(shí)相應(yīng)的目標(biāo)函數(shù)的最大值為：Z=24+321=164x2=12X1+2x2=82x1+2x2=12ABCDX2解：對(duì)于上述具有兩個(gè)變量的線性規(guī)劃問題，下圖的陰影部分描述了滿足約束條件的區(qū)域，為OABCD;紅虛線為目標(biāo)函數(shù)Z=2x1+3x2的等值線。沿箭頭方向移動(dòng)目標(biāo)函數(shù)的等值線，平移等值線直至與可行域OABCD相切或融合為一條直線，此時(shí)就得到最優(yōu)解為C點(diǎn)，其坐標(biāo)可通過解方程組得到：目前三十一頁\總數(shù)一百五十頁\編于十八點(diǎn)例2：用圖解法求解線性規(guī)劃問題。MAXZ=4x1+3x2s.t.2x1+2x2≤16005x1+2.5x2≤2500x1≤400x1,x2≥0由約束條件得到可行域OABCD。由等值線Z=4x1+3x2沿箭頭方向向上平移與可行域交于B點(diǎn)，則B點(diǎn)就是最優(yōu)點(diǎn)。最優(yōu)值等于2600目前三十二頁\總數(shù)一百五十頁\編于十八點(diǎn)0Z=40X1+80X2=0

X1+2X2=30DABCX2X1求解最優(yōu)解：BC線段B點(diǎn)C點(diǎn)X(1)=(6,12)X(2)=(15,7.5)X=X(1)+(1-)X(2)(01)例3、maxZ=40X1+80X2X1+2X2303X1+2X2602X224

X1,X20目前三十三頁\總數(shù)一百五十頁\編于十八點(diǎn)X1=6++(1-)·15X2=12++(1-)·7.5X1=15-9X2=7.5+4.5(01)X==+(1-)maxZ=1200

X1615

X2127.5目前三十四頁\總數(shù)一百五十頁\編于十八點(diǎn)無界無有限最優(yōu)解若目標(biāo)函數(shù)由MaxZ=2x1+4x2改為MinZ=2x1+4x2,則可行解所在的范圍雖然無界,但有最優(yōu)解x1=4，x2=0,即(4,0)點(diǎn).例4、maxZ=2X1+4X22X1+X28-2X1+X22X1,X20Z=02X1+X2=8-2X1+X2=28246X240X1目前三十五頁\總數(shù)一百五十頁\編于十八點(diǎn)例5、maxZ=3X1+2X2-X1-X21X1,X20無解無可行解-1X2-1X10目前三十六頁\總數(shù)一百五十頁\編于十八點(diǎn)通過圖解法可以看出：（1）線性規(guī)劃的所有可行解構(gòu)成的可行域一般是凸多邊形，有些可行域是無界的；（2）若存在最優(yōu)解，則一定在可行域的某頂點(diǎn)得到；（3）若在兩個(gè)頂點(diǎn)上同時(shí)得到最優(yōu)解，則在這兩點(diǎn)的連線上的任一點(diǎn)都是最優(yōu)解。（4）若可行域無界，則可能發(fā)生最優(yōu)解無界的情況；（5）若可行域是空集，此時(shí)無最優(yōu)解。目前三十七頁\總數(shù)一百五十頁\編于十八點(diǎn)上述理論具有普遍意義，對(duì)于兩個(gè)以上變量的線性規(guī)劃問題都成立。圖解法雖然直觀、簡(jiǎn)便等優(yōu)點(diǎn)，在變量多的情況下，即在多維的情況下，它就無能為力了。因此，需要介紹一種代數(shù)方法——單純型法，為了以后介紹方便討論，需要研究一下線性規(guī)劃數(shù)學(xué)模型的標(biāo)準(zhǔn)化問題。目前三十八頁\總數(shù)一百五十頁\編于十八點(diǎn)三、線性規(guī)劃問題的標(biāo)準(zhǔn)型由前面所舉的例子可知,線性規(guī)劃問題可能有各種不同的形式。目標(biāo)函數(shù)有實(shí)現(xiàn)最大化也有實(shí)現(xiàn)最小化的;約束條件可以是“”形式、“”形式不等式,有的是等式。決策變量有時(shí)有非負(fù)限制有時(shí)沒有。這種多樣性給討論問題代來了不便。為了便于今后討論，我們規(guī)定線性規(guī)劃問題的標(biāo)準(zhǔn)型為：

目前三十九頁\總數(shù)一百五十頁\編于十八點(diǎn)這里我們假設(shè)bi

0(i=1,2,···,m),否則兩端同時(shí)乘以“-1”。用矩陣向量描述就是：目前四十頁\總數(shù)一百五十頁\編于十八點(diǎn)其中：C=(c1,c2,···,cn)T，X=(x1,x2,···,xn)T，b=(b1,b2,···,bm)T,A=(P1,P2,···,Pn)，Pj=(a1j,a2j,···,amj)T，0=(0,0,···,0)T,(j=1,2,···,n)。

我們稱A為約束方程組的系數(shù)矩陣(m×n階),一般情況下m<n,m,n為正整數(shù),分別表示約束條件的個(gè)數(shù)和決策變量的個(gè)數(shù),C為價(jià)值向量,X為決策向量,通常aij

,bi

,cj

(i=1,2,···,m,j=1,2,···,n)為已知常數(shù)。實(shí)際上，具體問題的線性規(guī)劃數(shù)學(xué)模型是各式各樣的,需要把它們化成標(biāo)準(zhǔn)型,并借助于標(biāo)準(zhǔn)型的求解方法進(jìn)行求解.目前四十一頁\總數(shù)一百五十頁\編于十八點(diǎn)以下就具體討論如何把一般的線性規(guī)劃模型化成標(biāo)準(zhǔn)型。若要求目標(biāo)函數(shù)實(shí)現(xiàn)最小化時(shí).即此時(shí)的目標(biāo)函數(shù)是:MinZ=CTX,這時(shí)只需要將目標(biāo)函數(shù)的最小值變換為求目標(biāo)函數(shù)的最大值,即MinZ=Max

(-Z)。令Zˊ=-Z，于是就得到：Max

Zˊ=-CTX。2.若約束方程組為不等式。這時(shí)有兩種情況:一是約束條件為“”形式的不等式,則在“”號(hào)的左邊加入非負(fù)的松弛變量;把原“”形的不等式變?yōu)榈仁?另一種是約束條件為“”形式的不等式,則可在“”號(hào)的左端減去一個(gè)非負(fù)的剩余變量。相應(yīng)的松弛變量或剩余變量在目標(biāo)函數(shù)中的價(jià)值系數(shù)取值為0。目前四十二頁\總數(shù)一百五十頁\編于十八點(diǎn)3.若存在無非負(fù)要求的變量.即有某一個(gè)變量xj取正值或負(fù)值都可以.這時(shí)為了滿足標(biāo)準(zhǔn)型對(duì)變量的非負(fù)要求,可令xj=xjˊ-xj〞,其中:xjˊ、xj〞0，由于xjˊ可能大于也可能小于xj〞，故xj可以為正或?yàn)樨?fù)。上述的標(biāo)準(zhǔn)型具有如下特點(diǎn)：（1）目標(biāo)函數(shù)求最大值；（2）所求的變量都要求是非負(fù)的；（3）所有的約束條件都是等式；（4）常數(shù)項(xiàng)非負(fù)綜合以上的討論可以說明任何形式的線性規(guī)劃問題都可以通過上述手續(xù)把非標(biāo)準(zhǔn)型式的線性規(guī)劃問題化成標(biāo)準(zhǔn)型。現(xiàn)舉例如下：目前四十三頁\總數(shù)一百五十頁\編于十八點(diǎn)例：將例1的數(shù)學(xué)模型化為標(biāo)準(zhǔn)型。maxZ=2x1+3x22x1+2x2≤12

x1+2x2≤84x2≤124x1≤16

x1,x2≥0

解：引進(jìn)4個(gè)新的非負(fù)變量x3,x4,x5,x6使不等式變?yōu)榈仁?，?biāo)準(zhǔn)型為：MaxZ=2x1+3x2+0·x3+0·x4+0·x5+0·x6

2x1+2x2+x3=12

x1+2x2+x4=184x1+x5=164x2+x6=12

x1,x2,x3,x4,x5,x6≥0

目前四十四頁\總數(shù)一百五十頁\編于十八點(diǎn)例4:試將如下線性規(guī)劃問題化成標(biāo)準(zhǔn)型解：令x3=x4-x5,x4,x5

0,(1)式左端加上非負(fù)松弛變量x6,(2)式左端減去非負(fù)剩余變量x7,則可將上述線性規(guī)劃問題化成如下的標(biāo)準(zhǔn)型:目前四十五頁\總數(shù)一百五十頁\編于十八點(diǎn)目前四十六頁\總數(shù)一百五十頁\編于十八點(diǎn)可行解:滿足約束條件(1.7),(1.8)的解X=(x1,x2,···,xn)T

稱為線性規(guī)劃問題的可行解;所有可行解的集合稱為可行解集或可行域。最優(yōu)解:滿足約束條件及目標(biāo)函數(shù)(1.6)的可行解稱為線性規(guī)劃問題的最優(yōu)解。四、線性規(guī)劃問題的解的概念在討論線性規(guī)劃問題的求解之前,先要了解線性規(guī)劃問題的解的概念。由前面討論可知線性規(guī)劃問題的標(biāo)準(zhǔn)型為(1.6)、(1.7)、(1.8)，即如下式子：目前四十七頁\總數(shù)一百五十頁\編于十八點(diǎn)基:假設(shè)A是約束方程組的系數(shù)矩陣,其秩數(shù)為m,B是矩陣A中由m列構(gòu)成的非奇異子矩陣(B的行列式的值不為0），則稱B是線性規(guī)劃問題的一個(gè)基。這就是說,矩陣B是由m個(gè)線性無關(guān)的列向量組成,不失一般性,可假設(shè):稱Pj(j=1,2,···,m)為基向量,與基向量Pj相對(duì)應(yīng)的變量xj(j=1,2,···,m)為基變量,否則稱為非基變量。為了進(jìn)一步討論線性規(guī)劃問題的解,下面研究約束方程組(1.7)的求解問題。假設(shè)該方程組系數(shù)矩陣A的秩為m,因m<n,所以它有無窮多個(gè)解。假設(shè)前m個(gè)變量的系數(shù)列向量是線性無關(guān)的，這時(shí)(1.7)式可改寫為：目前四十八頁\總數(shù)一百五十頁\編于十八點(diǎn)方程組(1.9)的一個(gè)基是B=(P1,P2,···,Pm),Pj=(a1j,···,amj)T,(j=1,2,···,m),設(shè)XB是對(duì)應(yīng)于這個(gè)基的基向量,即：

XB=(x1,x2,···,xm)T

現(xiàn)若令(1.9)式中的非基變量xm+1=···=xn=0,并用高斯消去法求出一個(gè)解X=(x1,x2,···,xm,0,···,0)T,這個(gè)解的非0分量的數(shù)目不大于方程個(gè)數(shù)m,稱X為基本解.目前四十九頁\總數(shù)一百五十頁\編于十八點(diǎn)基本可行解:滿足非負(fù)條件(1.8)的基本解稱為基本可行解.由此可見,基本可行解的非0分量的數(shù)目不大于m,并且都是非負(fù)的?？尚谢?對(duì)應(yīng)于基本可行解的基稱為可行基.由此可見,約束方程組(1.7)基本解的數(shù)目至多是Cnm個(gè).一般地講,基本可行解的數(shù)目要小于基本解的數(shù)目,至多相等.以上提到的幾種解的概念,可用如下圖來表示:基解可行解基本可行解目前五十頁\總數(shù)一百五十頁\編于十八點(diǎn)第二節(jié)線性規(guī)劃問題的幾何意義

在上一節(jié)的圖解法中,我們已經(jīng)直觀地看到了可行和最優(yōu)解的幾何意義,這一節(jié)從理論上進(jìn)一步討論。一、基本概念：1.凸集:假設(shè)K是n維歐氏空間的一個(gè)點(diǎn)集,若對(duì)于K中的任意兩點(diǎn)X1、X2,其連線上的所有點(diǎn)X1+(1-)X2(01)都在集合K中,即:X1+(1-)X2K(01)則稱K為凸集。從直觀上講，凸集無凹入部分，其內(nèi)部沒有洞。實(shí)心圓、實(shí)心球、實(shí)心立方體等都是凸集，圓周不是凸集。目前五十一頁\總數(shù)一百五十頁\編于十八點(diǎn)圖（a)、(b)、為凸集，而圖（c)、(d)不是凸集。目前五十二頁\總數(shù)一百五十頁\編于十八點(diǎn)容易驗(yàn)證以下結(jié)論是正確的：目前五十三頁\總數(shù)一百五十頁\編于十八點(diǎn)2.凸組合:設(shè)X1、X2、···、Xk是n維歐氏空間En中的k個(gè)點(diǎn)，若存在1、2、···、k，且0i

1,i=1,2,···,k,i=1,使X=1X1+2X2+···+kXk,則稱X為由X1、X2、···、Xk所構(gòu)成的凸組合。按照定義，凡是由x,y的凸組合表示的點(diǎn)都在x,y的連線上，而且反之亦然。3.頂點(diǎn):假設(shè)K是凸集,XK;若不能用不同的兩個(gè)點(diǎn)X1、X2K的線性組合表示為:

X=X1+(1-)X2，(0<<1)則稱X為凸集K的一個(gè)頂點(diǎn)（或稱為極點(diǎn)）。頂點(diǎn)不位于凸集K中的任意不同兩點(diǎn)的連線內(nèi)。目前五十四頁\總數(shù)一百五十頁\編于十八點(diǎn)二、基本定理定理1：若線性規(guī)劃問題存在可行域，則其可行域：D={X

?AX=b,X

0}，是凸集。引理1：線性規(guī)劃問題的可行解X為基本可行解的充要條件是X的正分量所對(duì)應(yīng)的系數(shù)列向量是線性無關(guān)的。證明:(1)必要性:由基本可行解的定義便可知。（2）充分性：若向量

P1,P2,···,Pk

線性無關(guān)，則必有km;當(dāng)k=m時(shí)，它們恰好構(gòu)成一個(gè)基，從而X=(x1,x2,···,xm,0,···,0)T

為相應(yīng)的基本可行解,當(dāng)k<m時(shí)，則一定可以從其余的列向量中取出m–k個(gè)與P1,P2,···,Pk

構(gòu)成最大的線性無關(guān)向量組,其對(duì)應(yīng)的解恰為X,所以根據(jù)定義是基本可行解(此時(shí)為退化的基本可行解)。目前五十五頁\總數(shù)一百五十頁\編于十八點(diǎn)定理2:線性規(guī)劃問題的基本可行解對(duì)應(yīng)于可行域的頂點(diǎn).引理2：若K是有界凸集，則任何一點(diǎn)Z

K可表示為K的頂點(diǎn)的凸組合。定理3:若可行域有界,則線性規(guī)劃問題的目標(biāo)函數(shù)一定可以在其可行域的頂點(diǎn)上達(dá)到最優(yōu)解。定理4(線性規(guī)劃問題的基本定理)若線性規(guī)劃問題存在可行解,則一定存在基本可行解;(2)若線性規(guī)劃問題存在最優(yōu)解,則一定存在最優(yōu)的基本可行解。目前五十六頁\總數(shù)一百五十頁\編于十八點(diǎn)根據(jù)以上討論得到如下的結(jié)論：（1）線性規(guī)劃問題的所有可行解的集合一般是凸集，它可以是有界的，也可以是無界的區(qū)域；僅有有限個(gè)頂點(diǎn)。(2)線性規(guī)劃問題的每一個(gè)基本可行解對(duì)應(yīng)于可行域的一個(gè)頂點(diǎn)。若線性規(guī)劃問題有最優(yōu)解，必定可在某頂點(diǎn)處取到。(3)如果一個(gè)線性規(guī)劃問題存在多個(gè)最優(yōu)解，那么至少有兩個(gè)相鄰的頂點(diǎn)處是線性規(guī)劃的可行解。（4）如果有一個(gè)頂點(diǎn)處可行解的目標(biāo)值比其它相鄰頂點(diǎn)可行解的目標(biāo)值優(yōu)的話，那么它就比其它所有頂點(diǎn)的可行解的目標(biāo)值優(yōu)。或者說，它就是最優(yōu)解。

目前五十七頁\總數(shù)一百五十頁\編于十八點(diǎn)

雖然可行域的頂點(diǎn)個(gè)數(shù)是有限的(它們不超過Cnm

個(gè))，采用“枚舉法”找出所有基本可行解，然后一一比較它們的目標(biāo)函數(shù)值的大小，最終可以找到最優(yōu)解。但當(dāng)m、n的數(shù)目相當(dāng)大時(shí)，這種辦法實(shí)際上是行不通的。因此，我們還要繼續(xù)討論一種方法，通過逐步迭代保證能逐步改進(jìn)并最終求出最優(yōu)解。目前五十八頁\總數(shù)一百五十頁\編于十八點(diǎn)

第三節(jié)單純形算法單純形算法的基本思路是:根據(jù)問題的標(biāo)準(zhǔn)型,從可行域中某個(gè)基本可行解(頂點(diǎn))開始,轉(zhuǎn)換到另一個(gè)基本可行解(頂點(diǎn)),并使得每次的轉(zhuǎn)換,目標(biāo)函數(shù)值均有所改善,最終達(dá)到最大值時(shí)就得到最優(yōu)解。對(duì)于標(biāo)準(zhǔn)線性規(guī)劃問題(簡(jiǎn)寫為L(zhǎng)P):這里A=(aij)mn,秩A=m。首先假定已求得(LP)的一個(gè)基本可行解X(0),為敘述方便,不失一般性,假設(shè):目前五十九頁\總數(shù)一百五十頁\編于十八點(diǎn)X(0)=(x1(0),x2(0),···,xm(0),0,···,0)T

(XB(0),XN(0))T,其對(duì)應(yīng)的基為:B=(P1,···,Pm),其中Pj=(a1j,···,amj)T,

j=1,2,···,m,對(duì)應(yīng)的價(jià)值系數(shù)分別記為CB=(c1,···,cm)T,CN

=(cm+1,···,cn

)T,又記N=(Pm+1,···,Pn),由約束條件AX=b,可以得到:BXB(0)+NXN(0)=b即:

XB(0)=B-1b–B-1NXN(0)(1.21)上式就是基變量用非基變量表示的形式。由于X(0)是基本可行解,且XN(0)=0,所以XB(0)=B-1b0;引入記號(hào)b*

=B-1b=(b1*,b2*,···,bm*)T,將(1.21)式代入目標(biāo)函數(shù)整理得:Z=CBTB-1b+(CNT–CBTB-1N)XN(0)(1.22)上式就是目標(biāo)函數(shù)用非基變量表示的形式。目前六十頁\總數(shù)一百五十頁\編于十八點(diǎn)記Z0

=CBTB-1b,令j=cj–CBTB-1Pj

,則顯然當(dāng)j∈IB={1,···,m}(IB稱為基變量指標(biāo)集)時(shí),j=0;當(dāng)j∈IN={m+1,···,n}(IN稱為非基變量指標(biāo)集)時(shí),j則不一定等于0。j稱為檢驗(yàn)數(shù)，又令yj=B-1Pj

(y1j,···,ymj)T,j∈IN

,則可得出如下的初始單純形表1—3。目前六十一頁\總數(shù)一百五十頁\編于十八點(diǎn)cj→c1…ck…cmcm+1…cj…cnCBXBb*x1…xk…xmxm+1…xj…xnc1x1b1*1…0…0y1m+1…y1j…y1n

…

…

…

…

…

…

…

…

…ckxkbk*0…1…0ykm+1…ykj…ykn

…

…

……

…

…

……

…cmxmbm*0…0…1ymm+1…ymj…ymnC-CBTB-1A0…0…0m+1…j…n

表1—3初始單純形表目前六十二頁\總數(shù)一百五十頁\編于十八點(diǎn)

由于xj

0,j

0,j∈IN,所以由(1.23)式可知:CTXCTX(0)命題得證。2.無有限最優(yōu)解判別定理:若X(0)=(XB(0),XN(0))T為一基本可行解,且有一個(gè)j0∈IN,j0

>0,而yj00,則(LP)無有限最優(yōu)解(也稱為無界解)。一、最優(yōu)性檢驗(yàn)與解的判別最優(yōu)解判別定理:若X(0)=(XB(0),XN(0))T,其中XB(0)=B-1b,XN(0)=0為對(duì)應(yīng)于基B的基本可行解,且對(duì)于一切j∈IN,有j0,則X(0)已為(LP)的最優(yōu)解。證明:設(shè)X為(LP)的一個(gè)可行解,令X=(XB,XN)T,代入目標(biāo)函數(shù)值整理得到:目前六十三頁\總數(shù)一百五十頁\編于十八點(diǎn)3.基變換:若非上述兩種情形,則由式(1.23)可見,當(dāng)某些j

>0,xj>0,j∈IN,則目標(biāo)函數(shù)值還可以增加。為使目標(biāo)函數(shù)值增加最快，我們選擇：j

=max{l∣l

>0,l∈IN}j所對(duì)應(yīng)的變量xj為換入變量(就是下一個(gè)基的基變量).因?yàn)榛兞總€(gè)數(shù)總是為m,所以換入一個(gè)之后還必須換出一個(gè)。下面我們來考慮如何選擇換出變量。若初始基本可行解X(0)不是最優(yōu)解，那么就還要找一個(gè)新的基本可行解。其作法如下：從原可行基中換出一個(gè)列向量，再投入一個(gè)新的列向量，（要保證線性無關(guān)），從而得到一個(gè)新的可行基，這就是基變換。目前六十四頁\總數(shù)一百五十頁\編于十八點(diǎn)

要做基變換。首先確定換入變量（已講過），即選擇最大的檢驗(yàn)數(shù)j所對(duì)應(yīng)的非基變量作為換入變量xj(進(jìn)基變量)。下面再確定換出變量。確定換出變量的原則是保持解的可行性。這就說，要使原基本可行解的某一個(gè)正分量xj變?yōu)?，同時(shí)保持其余分量均非負(fù)。具體實(shí)現(xiàn)是按“最小比例原則”進(jìn)行，也稱原則。若則選基變量Xl為換出變量。4.旋轉(zhuǎn)運(yùn)算（迭代）（樞運(yùn)算）在確定了換入變量Xk與換出變量Xl之后，要把xk和xl的位置對(duì)換，就是說，要把xk所對(duì)應(yīng)的列向量pk變成單位向量。這只對(duì)系數(shù)矩陣的增廣矩陣進(jìn)行變換即可，稱ylk為旋轉(zhuǎn)元。目前六十五頁\總數(shù)一百五十頁\編于十八點(diǎn)以表1—3中的元素ykl

(稱為主元素或旋轉(zhuǎn)元素)進(jìn)行基變換:將第k行每個(gè)元素除以ykl

,將第k行每個(gè)元素乘以–yij/ykj

加到第i行(i=1,2,···,m,

i≠k,j=1,2,···,k),將第k行每個(gè)元素乘以–j/ykj

加到檢驗(yàn)數(shù)行,對(duì)應(yīng)的新的目標(biāo)函數(shù)值即為：目前六十六頁\總數(shù)一百五十頁\編于十八點(diǎn)經(jīng)過基變換之后，針對(duì)于新基B1的基本可行解為：目前六十七頁\總數(shù)一百五十頁\編于十八點(diǎn)綜合以上的討論,單純形算法的計(jì)算步驟可歸結(jié)如下：第一步：找出初始可行基，確定初始基本可行解，建立初始單純形表；第二步：檢查對(duì)應(yīng)于非基變量的檢驗(yàn)數(shù)l，l∈IN，若所有l(wèi)0，l∈IN，則已得到最優(yōu)解，停止計(jì)算，否則轉(zhuǎn)入下一步；第三步：在所有l(wèi)>0，l∈IN中，若有一個(gè)j對(duì)應(yīng)的系數(shù)列向量yj0，則此問題沒有有限最優(yōu)解，停止計(jì)算，否則轉(zhuǎn)入下一步；第四步：根據(jù)max{l∣l>0，l∈IN}=j,確定xj

為目前六十八頁\總數(shù)一百五十頁\編于十八點(diǎn)換入變量(即為新基的基變量),再根據(jù):確定xk為換出變量(即為新基的非基變量),轉(zhuǎn)下一步；第五步：以ykj為主元素進(jìn)行基變換，轉(zhuǎn)回第二步。例5.利用單純形算法求解例1的線性規(guī)劃問題。

MaxZ=2x1+3x2+0·x3+0·x4+0·x5+0·x62x1+2x2+x3=12x1+2x2+x4=84x2+x5=124x1+x6=16

x1,x2,x3,x4,x5,x6≥0

解：（1）由標(biāo)準(zhǔn)型得到：目前六十九頁\總數(shù)一百五十頁\編于十八點(diǎn)cj230000XBbx1x2x3x4x5x6221000120100400010040001x3x4x5x6128161264-3-Z0230000（2）max{1,

2}=3=

2,所以x2為換入變量.(3)因?yàn)?=2,

2=3都大于0，且p1,p2的坐標(biāo)有正分量存在，因?yàn)棣龋?與x6那一行相對(duì)應(yīng)，所以x6為換出變量；目前七十頁\總數(shù)一百五十頁\編于十八點(diǎn)cj230000XBbx1x2x3x4x5x60100-1/210010-1/2400010010001/4x3x4x5x262163324--Z-920000-3/4

故x2對(duì)應(yīng)列與x6對(duì)應(yīng)行的相交處的4為主元素；（4）以“4”為主元素進(jìn)行旋轉(zhuǎn)計(jì)算，進(jìn)行行初等變換，得下表：目前七十一頁\總數(shù)一百五十頁\編于十八點(diǎn)cj230000XBbx1x2x3x4x5x6001-201/20010-1/2000-412

010001/4x3x1x5x222834-412-Z-13000-201/4

這時(shí)出現(xiàn)了退化問題。即有兩個(gè)或更多的相同時(shí)，在相同對(duì)應(yīng)的變量中選擇下標(biāo)最大的那個(gè)基變量為換出變量；同時(shí)如果出現(xiàn)有兩個(gè)或更多的檢驗(yàn)數(shù)σ相同時(shí)，在相同σ對(duì)應(yīng)的變量中選擇下標(biāo)最小的那個(gè)基變量為進(jìn)入變量，這樣會(huì)避免出現(xiàn)“死循環(huán)”的現(xiàn)象。目前七十二頁\總數(shù)一百五十頁\編于十八點(diǎn)cj230000XBbx1x2x3x4x5x6001-1-1/400011/40000-21/2

1010?-1/80x3x1x6x20442-Z-14000-3/2-1/80

這時(shí)，檢驗(yàn)數(shù)全部小于等于0，即目標(biāo)函數(shù)已不可能再增大，于是得到最優(yōu)解：X=(4,2,0,0,0,4)T目標(biāo)函數(shù)的最大值為：Z=14目前七十三頁\總數(shù)一百五十頁\編于十八點(diǎn)

第四節(jié)單純形算法的進(jìn)一步討論一、初始基本可行解的確定利用單純形算法的一個(gè)根本前提是要有一個(gè)初始的基本可行解.這對(duì)于一些簡(jiǎn)單問題,利用觀察或其它手段是容易得到的;但對(duì)于較復(fù)雜的問題,則利用這種方法幾乎是不可行的.這就引起了人們對(duì)求初始基本可行解的思考.以下我們分幾種情形加以討論。對(duì)于AX=b,人們一下就可以從其中求得一個(gè)單位矩陣.這時(shí)取初始基B就是單位矩陣,對(duì)應(yīng)的基變量為XB,非基變量為XN

。這時(shí)目前七十四頁\總數(shù)一百五十頁\編于十八點(diǎn),然后按單純形算法計(jì)算步驟便可得到。這種情況包含了AX

b的情形。人工變量法(大M法)

設(shè)有一個(gè)線性規(guī)劃的約束條件是等式約束，這時(shí)分別給每一個(gè)約束條件加入人工變量xn+1,…,xn+m,得:目前七十五頁\總數(shù)一百五十頁\編于十八點(diǎn)由此得到一個(gè)m階單位矩陣.以xn+1,…,xn+m為基變量,令非基變量x1,…,xn為0,便可得到一個(gè)初始基本可行解X(0);X(0)=(0,,0,b1,,bm)T。因?yàn)槿斯ぷ兞渴呛蠹尤氲皆s束方程組中的虛擬變量,我們要求將它們從基變量中逐漸替換掉.若經(jīng)過基的變換,基變量中不再包含有人工變量,這就表示原問題有解;若經(jīng)過基變換,最后在基中至少還有一個(gè)人工變量,這就意味著原問題無可行解.具體處理方法如下:對(duì)于加入人工變量的線性規(guī)劃問題的目標(biāo)函數(shù)如何處理?我們希望人工變量對(duì)目標(biāo)函數(shù)取值不受影響.因此目前七十六頁\總數(shù)一百五十頁\編于十八點(diǎn)只有在迭代過程中,把人工變量從基變量中換出,讓它成為非基變量.為此,就必須假定人工變量在目標(biāo)函數(shù)中的價(jià)值系數(shù)為(-M)(對(duì)于極大化目標(biāo)),M為充分大的正數(shù).這樣,對(duì)于要求實(shí)現(xiàn)目標(biāo)函數(shù)最大化的問題來講,只要在基變量中還存在人工變量,目標(biāo)函數(shù)就不可能實(shí)現(xiàn)最大化.這就是大M法。以下舉例加以說明。例6.試用大M法求解如下線性規(guī)劃問題的最優(yōu)解。目前七十七頁\總數(shù)一百五十頁\編于十八點(diǎn)解:在上述問題中加入松弛變量,剩余變量和人工變量得:這里M是一個(gè)充分大的正數(shù),取基變量為x4,x6,x7,可得如下的表1—8。利用表1—8得初始單純形表，單純形算法得表1—9～表1—11。目前七十八頁\總數(shù)一百五十頁\編于十八點(diǎn)表1—8cj3-1-100-M-MCBXBb*x1x2x3x4x5x6x70x4111-211000-Mx63-4120-110-Mx71-20[1]0001-Z03-1-100-M-M目前七十九頁\總數(shù)一百五十頁\編于十八點(diǎn)cj3-1-100-M-MθCBXBb*x1x2x3x4x5x6x70x4111-21100011-Mx63-4120-1101.5-Mx71-20[1]00011-Z4M3-6MM-13M-10-M00初始單純形表目前八十頁\總數(shù)一百五十頁\編于十八點(diǎn)表1—9cj3-1-100-M-MθCBXBb*x1x2x3x4x5x6x70x4103-20100-1－-Mx610[1]00-11-21-1x31-2010001－-ZM+11M-100-M01-3M目前八十一頁\總數(shù)一百五十頁\編于十八點(diǎn)cj3-1-100-M-MθCBXBb*x1x2x3x4x5x6x70x412[3]001-22-54-1x210100-11-2－-1x31-2010001－-Z21000-11-M-1-M

表1—10目前八十二頁\總數(shù)一百五十頁\編于十八點(diǎn)cj3-1-100-M-MθCBXBb*x1x2x3x4x5x6x73x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3-Z-2000-1/3-1/31/3-M2/3-M

表1—11在表1—11中，所有的j0，故得到最優(yōu)解：

X*=(4,1,9,0,0,0,0)T

目標(biāo)函數(shù)值Z′=2,原問題的最優(yōu)目標(biāo)值為:Z*=-2。目前八十三頁\總數(shù)一百五十頁\編于十八點(diǎn)3.

兩階段法:這種方法是在約束條件中加入人工變量,將線性規(guī)劃問題分為兩階段進(jìn)行求解.第一階段是先求出基本可行解(或判斷出原線性規(guī)劃問題無解),第二階段利用已求出的初始基本可行解來求最優(yōu)解。具體由如下定理5給出。定理5設(shè)原線性規(guī)劃問題記成(LP),由它而引入的新的線性規(guī)劃問題記成(LP)*。分別表示如下：目前八十四頁\總數(shù)一百五十頁\編于十八點(diǎn)1)若(LP)*具有最優(yōu)基本可行解則(LP)是可行的,而2)若(LP)*的最優(yōu)基本可行解則(LP)必不可行。定理5的具體應(yīng)用過程是:(LP)*判斷原線性規(guī)劃問題是否存在基本可行解,利用單純形算法,若得到W=0,即所有人工變量為非基變量,這表示原問題已得到了一個(gè)基本可行解.于是只需要將第一階段最終計(jì)算表中的目標(biāo)函數(shù)行的數(shù)字換成原問題的目標(biāo)函數(shù)的數(shù)字,就得到了求解原問題的初始計(jì)算表,再進(jìn)行第二階段的求解。若第一階段的最終計(jì)算表出現(xiàn)W>0,這就表明原問題無可行解，應(yīng)停止計(jì)算。目前八十五頁\總數(shù)一百五十頁\編于十八點(diǎn)解：先在以上問題的約束條件中加入松弛變量、剩余變量、人工變量，給出第一階段的線性規(guī)劃問題：各階段的計(jì)算方法及步驟與前述單純形法完全相同，下面用例子說明該方法的應(yīng)用。例7：試用兩階段法求解如下線性規(guī)劃問題目前八十六頁\總數(shù)一百五十頁\編于十八點(diǎn)以x4、x6、x7為基變量得如下初始計(jì)算表cj00000-1-1CBXBb*x1x2x3x4x5x6x70x4111-211000-1x63-4120-110-1x71-20[1]0001-W'000000-1-1目前八十七頁\總數(shù)一百五十頁\編于十八點(diǎn)cj00000-1-1θCBXBb*x1x2x3x4x5x6x70x4111-21100011-1x63-4120-1101.5-1x71-20[1]00011-W'4-6130-100初始單純形表1—12目前八十八頁\總數(shù)一百五十頁\編于十八點(diǎn)表1—13cj00000-1-1θCBXBb*x1x2x3x4x5x6x70x4103-20100-1－-1x610[1]00-11-21-1x31-2010001－-W'10100-10-3目前八十九頁\總數(shù)一百五十頁\編于十八點(diǎn)表1—14cj00000-1-1θCBXBb*x1x2x3x4x5x6x70x4123001-22-50x210100-11-20x31-2010001-W'000000-1-1目前九十頁\總數(shù)一百五十頁\編于十八點(diǎn)這里x6、x7是人工變量。第一階段我們已求得W′=0，最優(yōu)解x5=0，x6=0，x7=0。因人工變量x6=x7=0,所以(0,1,1,12,0)T是原問題的基本可行解。于是可以開始第二階段的計(jì)算。將第一階段的最終計(jì)算表1—14中的人工變量列取消,并將目標(biāo)函數(shù)系數(shù)換成原問題的目標(biāo)函數(shù)系數(shù),重新計(jì)算檢驗(yàn)數(shù)行,可得如下第二階段的初始單純形表1—15；應(yīng)用單純形算法求解得最終表1—16。目前九十一頁\總數(shù)一百五十頁\編于十八點(diǎn)表1—15cj3-1-100CBXBb*x1x2x3x4x50x412[3]001-212/3=4-1x210100-1—-1x31-20100—-Z'21000-1目前九十二頁\總數(shù)一百五十頁\編于十八點(diǎn)表1—16cj3-1-100CBXBb*x1x2x3x4x53x141001/3-2/3-1x210100-1-1x390012/3-4/3-Z'-2000-1/3-1/3表1—16中所有檢驗(yàn)數(shù)j

0，所以x1=4，x2=1,x3=9是原線性規(guī)劃問題的最優(yōu)解。目標(biāo)函數(shù)值：Z*=2。目前九十三頁\總數(shù)一百五十頁\編于十八點(diǎn)第五節(jié)LP的對(duì)偶理論

對(duì)偶問題例12加工能力(小時(shí)/天)

A2212B128C4016D041223銷售收入產(chǎn)品設(shè)備目前九十四頁\總數(shù)一百五十頁\編于十八點(diǎn)設(shè)X1，

X2為產(chǎn)品1，2的產(chǎn)量2X1+2X2

12X1+2X2

84X1

164X2

12X1X2

0maxZ=2X1+3X2221212X1840X21604

12(23)

X1X2目前九十五頁\總數(shù)一百五十頁\編于十八點(diǎn)設(shè)y1,

y2,

y3,

y4分別為出租每臺(tái)設(shè)備臺(tái)時(shí)的租金和出讓單位原材料A,B的附加額。2y1+y2+4y322y1+2y2+443y1…y4

021402204y1y2y3y423目前九十六頁\總數(shù)一百五十頁\編于十八點(diǎn)(y1y2y3y4)22124004(2,3)minW=12y1+8y2+16y3+12y4y1,

y2,

y3,

y4

“影子價(jià)格”目前九十七頁\總數(shù)一百五十頁\編于十八點(diǎn)定義：對(duì)偶問題minW=yb

yA

Cy0minW=bTyATy

CTy0maxZ=CX

AX

bX0原問題目前九十八頁\總數(shù)一百五十頁\編于十八點(diǎn)對(duì)偶關(guān)系對(duì)應(yīng)表

原問題對(duì)偶問題目標(biāo)函數(shù)類型maxmin目標(biāo)函數(shù)系數(shù)目標(biāo)函數(shù)系數(shù)右邊項(xiàng)系數(shù)與右邊項(xiàng)的對(duì)應(yīng)關(guān)系右邊項(xiàng)系數(shù)目標(biāo)函數(shù)系數(shù)變量數(shù)與約束數(shù)變量數(shù)n約束數(shù)n的對(duì)應(yīng)關(guān)系約束數(shù)m變量數(shù)m原問題變量類型與

0

對(duì)偶問題約束類型變量

0約束

的對(duì)應(yīng)關(guān)系無限制＝原問題約束類型與

0對(duì)偶問題變量類型約束

變量

0的對(duì)應(yīng)關(guān)系＝無限制目前九十九頁\總數(shù)一百五十頁\編于十八點(diǎn)例1、寫出下面問題的對(duì)偶規(guī)劃maxZ=5X1+6X23X1-2X2=74X1+X2

9X1,X2

0minW=7y1+9y23y1+4y25

-2y1+y2

6y1自由

,y2

0解：對(duì)偶問題目前一百頁\總數(shù)一百五十頁\編于十八點(diǎn)例2、寫對(duì)偶規(guī)劃minZ=4X1+2X2-3X3-X1+2X2

62X1+3X3

9X1+5X2-2X3=

4X2,X30maxW=6y1+9y2+4y3-y1+2y2+y3=

42y1+5y323y2-2y3

-3y10,y20,y3自由目前一百零一頁\總數(shù)一百五十頁\編于十八點(diǎn)minZ=4X1+2X2-3X3X1-2X2

-

62X1+3X3

9X1+5X2-2X3=

4X2,X30或?qū)⒃瓎栴}變形為目前一百零二頁\總數(shù)一百五十頁\編于十八點(diǎn)maxW=-6y1+9y2+4y3y1+2y2+y3=

4-2y1+5y323y2-2y3

-3y1,y20,y3自由對(duì)偶規(guī)劃目前一百零三頁\總數(shù)一百五十頁\編于十八點(diǎn)產(chǎn)品A，B產(chǎn)量為X1，X2，Z為利潤(rùn)例1、3X1+X2+X3=483X1+4X2+X4=120X1…X40maxZ=5X1+6X23X1+X2483X1+4X2120X1,X2

0機(jī)器臺(tái)時(shí)勞動(dòng)工時(shí)目前一百零四頁\總數(shù)一百五十頁\編于十八點(diǎn)X=(8,24)TZ=184

560