線性規(guī)劃(運籌學(xué)-京航空航天大學(xué),黨耀國)(研究生)

1、運運 籌籌 學(xué)學(xué) 南京航空航天大學(xué)經(jīng)濟與管理學(xué)院南京航空航天大學(xué)經(jīng)濟與管理學(xué)院 黨黨 耀耀 國國 二二00五年九月五年九月 緒緒 論論 一一 運籌學(xué)發(fā)展簡史運籌學(xué)發(fā)展簡史 中國古代的“齊王賽馬”就是對策論的一個典型實例。作為運籌學(xué)的早期工作其歷史可追溯到1914年： 1914年英國人蘭徹斯特(F.W.Lanchester)呈發(fā)表過關(guān)于人與火力的優(yōu)勢與勝利之間的理論文章，這就是軍事運籌學(xué)中著名的“蘭徹斯特戰(zhàn)斗方程”。 排隊論的先驅(qū)者丹麥工程師愛爾朗(A.K.Erlang)1917年在哥本哈根電話公司研究電話通信系統(tǒng)時，提出了排隊論的一些著名公式。 20世紀30年代，荷蘭人荷雷斯列文生(Horac

2、e.C.Le venson)用運籌學(xué)思想分析商業(yè)廣告和顧客心理，由此提出了存儲論中著名的“經(jīng)濟批量公式”。 1947年，美國數(shù)學(xué)家丹捷格(G.B.Dantizg)發(fā)表了關(guān)于線性規(guī)劃的研究成果，所解決的問題是美國空軍軍事規(guī)劃時提出的，并給出了求解線性規(guī)劃問題的單純形算法。事實上，早在1939年蘇聯(lián)學(xué)者康托洛維奇(.)在解決工業(yè)生產(chǎn)組織和計劃問題時，已提出了類似線性規(guī)劃的模型，并給出了“解乘數(shù)法”的求解方法。由于當(dāng)時未被重視，直到1960年康托洛維奇再次發(fā)表了最佳資源利用的經(jīng)濟計算一書后，才受到國內(nèi)外的一致重視。為此康托洛維奇獲得了諾貝爾經(jīng)濟學(xué)獎。 因為它與研究技術(shù)問題不同，就稱之為“運用研究”或

3、“操作研究”(Operational Research)。研究內(nèi)容是： 1.研究護航艦隊保護商船隊的編隊問題，即當(dāng)船隊遭受德國潛艇攻擊時，如何使船隊損失最??； 2. 研究反潛深水炸彈的合理爆炸深度，這使得德國潛艇被摧毀數(shù)增加了400%；3. 研究船隊在遭受敵機攻擊時，大船應(yīng)急轉(zhuǎn)向而小船應(yīng)緩慢轉(zhuǎn)向的逃避方法，其結(jié)果，使船只在受敵機攻擊時，中彈船只數(shù)由47%降到29%。 在20世紀50年代中期，我國科學(xué)家錢學(xué)森、許國志等人將運籌學(xué)由西方引入我國，并結(jié)合了我國的特點在國內(nèi)推廣應(yīng)用。在經(jīng)濟數(shù)學(xué)方面，特別是投入產(chǎn)出表的研究和應(yīng)用開展得較早。質(zhì)量控制(后改為質(zhì)量管理)的應(yīng)用也有特色。在此期間，以華羅庚敎授

4、為首的一大批數(shù)學(xué)家加入到運籌學(xué)的研究隊伍，使運籌學(xué)的很多分支很快跟上當(dāng)時的國際水平。 我國第一個運籌學(xué)小組于1956年在中國科學(xué)院力學(xué)研究所成立，1960年在山東濟南召開全國應(yīng)用運籌學(xué)的經(jīng)驗交流和推廣會議，1962年在北京召開了全國運籌學(xué)專業(yè)學(xué)術(shù)會議，1980年4月成立中國運籌學(xué)學(xué)會。上世紀50年代中期，以華羅庚為首的一大批科學(xué)家加入到運籌學(xué)的研究中，首先在一些企業(yè)、事業(yè)單位積極推廣優(yōu)選法、統(tǒng)籌法等運籌學(xué)方法，取得顯著成果；并成立了優(yōu)選法、統(tǒng)籌法與經(jīng)濟數(shù)學(xué)研究會。學(xué)會主要研究運籌學(xué)，但沒有稱為運籌學(xué)。如今，運籌學(xué)已經(jīng)成為所有大學(xué)的經(jīng)濟與管理學(xué)院、工學(xué)院與計算機專業(yè)、應(yīng)用數(shù)學(xué)專業(yè)的基礎(chǔ)課程。 二

5、、二、 運籌學(xué)的工作步驟運籌學(xué)的工作步驟 運籌學(xué)在解決大量實際問題的過程中形成了自己的工作步驟：1.提出和形成問題：提出和形成問題：即要弄清問題的目標，可能的約束，問題的可控變量以及有關(guān)參數(shù)及有關(guān)資料。2.建立模型：建立模型：即把問題中可控變量、參數(shù)和目標與約束之間的關(guān)系用一定的模型表示出來。3.求解：求解：用各種手段(主要是數(shù)學(xué)方法，也可用其它方法)將模型求解。解可以是最優(yōu)解、次優(yōu)解、滿意解.復(fù)雜模型的求解需用計算機,解的精度要求由決策者提出4.解的檢驗：解的檢驗：首先檢驗求解步驟和程序有無錯誤，然后檢查解是否反映現(xiàn)實問題。5.解的控制：解的控制：通過控制解的變化過程決定對解是否要作一定的修

6、改。6.解的實施：解的實施：是指將解用到實際中去，必須考慮到實際的問題，如向?qū)嶋H部門講清楚解的用法，在實施中可能產(chǎn)生的問題等。 以上過程應(yīng)反復(fù)進行。 三、三、 運籌學(xué)的應(yīng)用與展望運籌學(xué)的應(yīng)用與展望 在運籌學(xué)的發(fā)展簡史中，已提到了運籌學(xué)在早期的應(yīng)用，主要在軍事領(lǐng)域。二次大戰(zhàn)后運籌學(xué)的應(yīng)用轉(zhuǎn)向民用，主要應(yīng)用于：(1)市場銷售：在廣告預(yù)算和媒介的選擇、競爭性定價新產(chǎn)品開發(fā)、銷售計劃的制定等方面。(2)生產(chǎn)計劃：在總體計劃方面主要是從總體確定生產(chǎn)、存儲和勞動力的配合等計劃以適應(yīng)波動的需求計劃,主要用線性規(guī)劃和模擬的方法等。(3)庫存管理:主要應(yīng)用于多種物資庫存的管理,以確定合理的庫存量。(4)運輸問題

7、：各種運輸?shù)恼{(diào)度與計劃安排。(5)財政和會計：這里主要涉及預(yù)算、貸款、成本分析、定價、投資、證券管理、現(xiàn)金管理等。用得較多的方法是：統(tǒng)計分析、數(shù)學(xué)規(guī)劃、決策分析。(6)人事管理：一是人員的獲得和需求估計；二是人才的開發(fā)，即進行教育和培訓(xùn)；三是人員的分配；四是各類人員的合理利用問題；五是人才的評價，其中有如何測定一個人對組織、社會的貢獻;六是工資和津貼的確定等。(7)設(shè)備維修、更新和可靠性、項目選擇和評價。(8)工程的優(yōu)化設(shè)計：這在建筑、電子、光學(xué)、機械和化工等領(lǐng)域都有應(yīng)用。(9)計算機和信息系統(tǒng)：(10)城市管理：包含了各種緊急服務(wù)系統(tǒng)的設(shè)計和運用四、最優(yōu)化問題舉例1、多參數(shù)的曲線擬合問題 已

8、知熱敏電阻R依賴于溫度t的函數(shù)關(guān)系題。這就是一個最小二乘問平方和誤差”來度量。通常使用“最小一定正好通過測量點，關(guān)系式，但這條曲線不的一個函數(shù)關(guān)于以確定）一組數(shù)值，由上式可給定（？參數(shù)問題是如何確定（據(jù)通過實驗，測得一組數(shù)為待定參數(shù)。其中213213213213211)(),(min , 2 , 1),)( 32niiiiixtxtRRxxxftRxxxxxxniRtxxxextR2、生成成本問題介紹Cobb-Douglas生成函數(shù)。0, 0. min ),( .210212102121212xxQxAxtsxrxCQxrxcrAxAxxxQQxx生產(chǎn)成本最小化。的條件下，使不低于某水平生產(chǎn)成

9、本問題是在產(chǎn)量生產(chǎn)成本，則，資本報酬率為已知工資率為為參數(shù)。，為生產(chǎn)技術(shù)水平，則為產(chǎn)出產(chǎn)量為勞動力，為資本的貨物，設(shè) 3、資源分配問題、資源分配問題考慮將m種資源安排給n種活動，問應(yīng)如何分配資源，才能使收益最大？這是線性規(guī)劃模型。為則，對應(yīng)的最優(yōu)化模型的單位利潤。表示活動其中的單位消耗量；相對于活動表示資源（種資源的擁有量；表示第其中的水平，已知的數(shù)據(jù)有表示選用活動設(shè)決策變量0. max ,),(a,)a,),(), 2 , 1(21ijnmij21XbAXtsXCZjcccccjiAibbbbbjnjxTjTniTmj在某些實際應(yīng)用中，有時考慮的利潤c1,c2,cn并不是固定的數(shù)值，而是隨機

10、變量，假定C是一個均值為TncccC),(21線性規(guī)劃模型的希望最大，則可考慮）如果希望（的隨機變量。，方差為均值為就是一個題的目標函數(shù)的隨機變量。則上述問協(xié)方差矩陣為ZAXXXCZVTT1二次規(guī)劃問題。非線性規(guī)劃問題，稱為，它是一類比較特殊的函數(shù)，約束為線性約束這時目標函數(shù)就是二次模型的方差最小，則有如下如果希望0. min )2(0. max XbAXtsVXXZZXbAXtsXCZTT差最小，則如果希望期望最大，方)3(這仍是二次規(guī)劃問題。則求一種自然的考慮就是要愿望水平或滿意水平。常常被認為是這個值證期望達到至少某一值假定人們的興趣在于保者綜合加以考慮）如果對期望、方差兩（題。這是一個

11、多目標規(guī)劃問0. min ,40. min max XZXCbAXtsVXXZZXCZZXbAXtsVXXZXCZTTTTTxpxdZxpxdZyPZxypxdPZXCPynpdypdcZZXCPTTTTTTTTmin ), ,),相應(yīng)的模型為：（是一維隨機變量，則維固定向量，是設(shè)為確定性問題，為把不確定性問題轉(zhuǎn)化。當(dāng)然人們喜歡極大化的概率，是獲得滿意水平（另一種方法是令0.XbAXts這是線性分式規(guī)劃。題。是常數(shù)，它就是運輸問的，則如果倉庫的位置是固定為變量的非線性規(guī)劃。這時模型就是以的度量，可采用：關(guān)于則問題的模型為：的貨物單位數(shù)量。場到市為倉庫的距離，到市場為倉庫的位置，為倉庫設(shè)距離最小

12、。各倉庫到市場的總加權(quán)試確定倉庫的位置，使個倉庫的容量為個倉庫，第現(xiàn)規(guī)劃對某種貨物的需求量為）個市場的位置為（個市場，第設(shè)有選址問題dijwwyyxxbyaxddwmiqwmicwtsdwjiwjidiyxCimqbajnmnmmjijiijijijjnjijinjijminjijijijijiiijjj,;,;,)()(0, 2 , 1 , 2 , 1 . min ),(.,)4(1111221111參考書 1、盧向華，等著運籌學(xué)教程，高等教育出版社 2、錢頌迪，運籌學(xué)，清華大學(xué)出版社 3、林同曾，運籌學(xué)，機械工業(yè)出版社 4、胡運權(quán)， 運籌學(xué)教程，清華大學(xué)出版社 第 一章 線 性 規(guī) 劃 第

13、 一 節(jié) 線性規(guī)劃模型及其圖解法 線性規(guī)劃是運籌學(xué)的一個重要分枝。自1947年美國數(shù)學(xué)家丹捷格（G.B.Dantzig）提出了求解線性規(guī)劃問題的方法單純形法之后，線性規(guī)劃在理論上趨于成熟，在實際中的應(yīng)用日益廣泛與深入。特別是在能用計算機來處理成千上萬個約束條件和變量的大規(guī)模線性規(guī)劃問題之后，它的適用領(lǐng)域更廣泛了。從解決技術(shù)問題中的最優(yōu)化設(shè)計到工業(yè)、農(nóng)業(yè)、商業(yè)、交通輸業(yè)、軍事、經(jīng)濟計劃與管理、決策等各個領(lǐng)域均可發(fā)揮作用；從范圍來看，小到一個小組的日常工作和計劃安排，大至整個部門以致國民經(jīng)濟計劃的最優(yōu)方案的提出，都有用武之地。它具有適應(yīng)性強、應(yīng)用廣泛、計算技術(shù)比較簡單的特點，是現(xiàn)代管理科學(xué)的重要基

14、礎(chǔ)和手段之一。一、線性規(guī)劃模型線性規(guī)劃：就是一個線性函數(shù)在線性等式或不等式約束條件下的極值問題。線性規(guī)劃研究的問題主要有兩類： 1、任務(wù)確定后，如何統(tǒng)籌安排，盡量做到用盡量少的人力和物力資源來完成任務(wù)； 2、有一定量的人力、物力資源，如何安排使用他們，使完成的任務(wù)（創(chuàng)造的利潤）最多。 在生產(chǎn)管理和經(jīng)濟活動中經(jīng)常提出這樣一類問題， 即如何合理地利用有限的人力、物力、財力等資源，以便得到最好的經(jīng)濟效果。例例1：某工廠在計劃期內(nèi)安排生產(chǎn)、兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時、A、B兩種原材料的消耗及兩種產(chǎn)品每件可獲利潤見如下表所示：問如何安排計劃使該工廠獲利最多？ I II 資源總量 設(shè) 備A

15、1臺時 2臺時 8 臺時 設(shè) 備B 2臺時 2臺時 12 臺時 原材料A 4公斤 0公斤 16公斤 原材料B 0公斤 4公斤 12公斤 利 潤 2元/件 3元/件解：解：假設(shè) x1、x2分別表示在計劃期內(nèi)生產(chǎn)產(chǎn)品I、II的數(shù)量，則該計劃問題可用如下數(shù)學(xué)模型表示為： 目標函數(shù) Max Z = 2x1 +3x2 約束條件0,12416482122221212121xxxxxxxx例例2 某汽車廠生產(chǎn)大轎車和載重汽車，所需資源、某汽車廠生產(chǎn)大轎車和載重汽車，所需資源、資源可用量和產(chǎn)品價格如下表所示資源可用量和產(chǎn)品價格如下表所示: 大轎車大轎車 載重汽車載重汽車 可用量可用量鋼材（噸）鋼材（噸） 2

16、2 1600工時工時(小時小時) 5 2.5 2500大轎車座椅大轎車座椅 400（輛）（輛）獲利獲利(千元千元/輛輛) 4 3問應(yīng)如何組織生產(chǎn)才能使工廠活力最大？問應(yīng)如何組織生產(chǎn)才能使工廠活力最大？ 例2的數(shù)學(xué)模型2134maxxxz16002221 xx25005 . 2521xx1x02xs.t.,4001x例3 下料問題 某工廠要做100套鋼架，每套有長2.9米、2.1米和1.5米的圓鋼組成，已知原料長7.4米，問應(yīng)如何下料使需用的原材料最省。 解：如果從每根7.4米長的原料上各截一根2.9米、2.1米和1.5米長的圓鋼，則還余0.9米，用100根原料，浪費預(yù)料共90米?，F(xiàn)采用套裁的辦

17、法，設(shè)計五種方案，如表1.2所示。表 圓鋼套裁方案 方案長度一二三四五2.92.11.513210221213合計（米）料頭（米）7.407.30.17.20.27.10.36.60.8例3 數(shù)學(xué)模型 設(shè)個方案各下料 根，則有5 , 4 , 3 , 2 , 1, ixi0,100323100221002. .8 . 03 . 02 . 01 . 00 . 0min54321532154342154321xxxxxxxxxxxxxxxtsxxxxxz（1-5）以上三個例子,從數(shù)學(xué)上來講,它們的共同特征是:(1)每個問題都用一組決策變量(x1 , x2 , , xn)表示某一方案 ,這組未知數(shù)的值

18、就代表一個具體的方案,通常要求這些未知數(shù)取值是非負的。(2) 存在一定的限制條件(稱為約束條件),這些條件都可以用關(guān)于決策變量的一組線性等式或不等式來表示。(3) 都有一個目標要求,并且這個目標可表示為這組決策 變量的線性函數(shù)(稱為目標函數(shù)),按研究問題的不同,要求目標函數(shù)實現(xiàn)最大化或最小化。 滿足以上三個條件的數(shù)學(xué)模型稱為線性規(guī)劃數(shù)學(xué)模型。0,),()2 .1 (),(),()1 .1 ()(21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcZMaxMin其一般形式為(1.1)和(1.2)形式。 在該模型

19、中,方程(1.1)稱為目標函數(shù);(1.2)稱為約束條件。二、圖解法二、圖解法對于簡單的線性規(guī)劃問題(只有兩個決策變量的線性規(guī)劃問題),我們通過圖解法可以對它進行求解。我們可以由例1具體給出求解的方法。例1：用圖解法求解線性規(guī)劃問題。 MAX Z=2x1+3x2 s.t. 2x1+2x2 12 x1+2x2 8 4x1 16 4x2 12 x1，x20 x1+2x2=8 解得：x1=4 4x1=16 x2=2這就是本線性規(guī)劃問題的最優(yōu)解。此時相應(yīng)的目標函數(shù)的最大值為： Z=24+321=164x2=12X1+2x2=82x1+2x2=12ABCDX2解：對于上述具有兩個

20、變量的線性規(guī)劃問題，下圖的陰影部分描述了滿足約束條件的區(qū)域，為OABCD;紅虛線為目標函數(shù)Z=2x1+3x2的等值線。等值線。沿箭頭方向移動目標函數(shù)的等值線，平移等值線直至與可行域OABCD相切或融合為一條直線，此時就得到最優(yōu)解為C 點，其坐標可通過解方程組得到：例2：用圖解法求解線性規(guī)劃問題。 MAX Z=4x1+3x2 s.t. 2x1+2x2 1600 5 x1+2.5x2 2500 x1 400 x1,x20由約束條件得到可行域OABCD。由等值線Z=4x1+3x2沿箭頭方向向上平移與可行域交于B點，則B點就是最優(yōu)點。最優(yōu)值等于26000Z= 40 X1 + 80X2 =0 X1 +

21、2X2 =30DABCX2X1求解最優(yōu)解：求解最優(yōu)解：BC線段線段B點點 C點點X(1)=(6,12) X(2)=(15,7.5)X= X(1)+(1- ) X(2) (0 1)例例3、 maxZ=40X1+ 80X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0 0X1 =6 + +(1- )15X2=12 + +(1- )7.5X1 =15-9 X2 =7.5+4.5 (0 1)X= = +(1- )maxZ=1200 X1 6 15 X2 12 7.5無界無有限最優(yōu)解若目標函數(shù)由 Max Z = 2x1 + 4x2 改為 Min Z =2 x1 +4 x2 ,

22、則可行解所在的范圍雖然無界,但有最優(yōu)解 x1 = 4，x2 = 0 ,即 (4,0)點.例例4、 maxZ=2X1+ 4X2 2X1+X2 8 8-2X1+X2 2X1 , X2 0 0Z=02X1+ X2=8-2X1+ X2=28246X240X1例例5、 maxZ=3X1+2X2 -X1 -X2 1 1X1 , X2 0 0無解無解無可行解無可行解-1X2-1X10通過圖解法可以看出： （1）線性規(guī)劃的所有可行解構(gòu)成的可行域一般是凸多邊形，有些可行域是無界的； （2）若存在最優(yōu)解，則一定在可行域的某頂點得到； （3）若在兩個頂點上同時得到最優(yōu)解，則在這兩點的連線上的任一點都是最優(yōu)解。 （4

23、）若可行域無界，則可能發(fā)生最優(yōu)解無界的情況； （5）若可行域是空集，此時無最優(yōu)解。上述理論具有普遍意義，對于兩個以上變量的線性規(guī)劃問題都成立。 圖解法雖然直觀、簡便等優(yōu)點，在變量多的情況下，即在多維的情況下，它就無能為力了。因此，需要介紹一種代數(shù)方法單純型法，為了以后介紹方便討論，需要研究一下線性規(guī)劃數(shù)學(xué)模型的標準化問題。三、線性規(guī)劃問題的標準型三、線性規(guī)劃問題的標準型 由前面所舉的例子可知,線性規(guī)劃問題可能有各種不同的形式。目標函數(shù)有實現(xiàn)最大化也有實現(xiàn)最小化的;約束條件可以是“ ”形式、“”形式不等式,有的是等式。決策變量有時有非負限制有時沒有。這種多樣性給討論問題代來了不便。為了便于今后討

24、論，我們規(guī)定線性規(guī)劃問題的標準型為： 0,)4 .1 (21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcZMax 這里我們假設(shè) bi 0 ( i = 1,2,m),否則兩端同時乘以“-1”。用矩陣向量描述就是：0)5.1(XbAXXCZMaxT 其中：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

25、, , 0 )T , ( j = 1, 2, , n ) 。 我們稱 A 為約束方程組的系數(shù)矩陣( mn階),一般情況下 m n , m , n 為正整數(shù),分別表示約束條件的個數(shù)和決策變量的個數(shù), C 為價值向量, X 為決策向量, 通常aij , bi , cj ( i = 1, 2, , m , j = 1, 2, , n ) 為已知常數(shù)。 實際上，具體問題的線性規(guī)劃數(shù)學(xué)模型是各式各樣的,需要把它們化成標準型,并借助于標準型的求解方法進行求解.以下就具體討論如何把一般的線性規(guī)劃模型化成標準型。1. 若要求目標函數(shù)實現(xiàn)最小化時. 即此時的目標函數(shù)是: Min Z = CTX , 這時只需要將

26、目標函數(shù)的最小值變換為求目標函數(shù)的最大值,即 Min Z = Max (- Z) 。令Z= -Z，于是就得到： Max Z= - CTX 。2. 若約束方程組為不等式。這時有兩種情況:一是約束條件為“ ”形式的不等式,則在“ ” 號的左邊加入非負的松弛變量;把原“ ” 形的不等式變?yōu)榈仁?另一種是約束條件為“ ”形式的不等式,則可在“ ”號的左端減去一個非負的剩余變量。相應(yīng)的松弛變量或剩余變量在目標函數(shù)中的價值系數(shù)取值為0。3. 若存在無非負要求的變量. 即有某一個變量 xj 取正值或負值都可以. 這時為了滿足標準型對變量的非負要求,可令 xj = xj- xj, 其中: xj、 xj 0 ，

27、由于xj可能大于也可能小于xj，故 xj 可以為正或為負。上述的標準型具有如下特點： （1）目標函數(shù)求最大值； （2）所求的變量都要求是非負的； （3）所有的約束條件都是等式； （4）常數(shù)項非負 綜合以上的討論可以說明任何形式的線性規(guī)劃問題都可以通過上述手續(xù)把非標準型式的線性規(guī)劃問題化成標準型。現(xiàn)舉例如下：例：將例1的數(shù)學(xué)模型化為標準型。 max Z=2x1+3x2 2x1+2x2 12 x1+2x28 4x212 4x1 16 x1, x20 解：引進4個新的非負變量x3,x4,x5,x6使不等式變?yōu)榈仁?，標準型為?Max Z=2x1+3x2+0 x3+0 x4+0 x5+0 x6 2x1

28、+2x2+x3 =12 x1+2x2+ x4 =18 4x2+ x5 =12 4x1+ x6=16 x1, x2,x3,x4,x5,x60例例4: 試將如下線性規(guī)劃問題化成標準型無限制321321321321321,0,)3(523)2(2)1(732xxxxxxxxxxxxxxxZMin解：解：令 x3 = x4 - x5 , x4 , x5 0 , (1)式左端加上非負松弛變量 x6 , (2)式左端減去非負剩余變量 x7 , 則可將上述線性規(guī)劃問題化成如下的標準型:0,5223270033272154217542165421765421xxxxxxxxxxxxxxxxxxxxxxxZMa

29、x)8 . 1 (), 2 , 1(0)7 . 1 (), 2 , 1(1njxnjbxajnjjjij1. 可行解可行解: 滿足約束條件(1.7),(1.8)的解 X = ( x1, x2, , xn)T 稱為線性規(guī)劃問題的可行解;所有可行解的集合稱為可行解集或可行域。2. 最優(yōu)解最優(yōu)解: 滿足約束條件及目標函數(shù)(1.6)的可行解稱為線性規(guī)劃問題的最優(yōu)解。四、線性規(guī)劃問題的解的概念四、線性規(guī)劃問題的解的概念 在討論線性規(guī)劃問題的求解之前,先要了解線性規(guī)劃問題的解的概念。由前面討論可知線性規(guī)劃問題的標準型為 (1.6)、(1.7)、(1.8)，即如下式子：)6.1(1njjjxcZMax3.

30、基基: 假設(shè) A 是約束方程組的系數(shù)矩陣,其秩數(shù)為 m ,B是矩陣 A 中由 m 列構(gòu)成的非奇異子矩陣(B的行列式的值不為0），則稱 B 是 線性規(guī)劃問題的一個基。這就是說,矩陣 B 是由 m 個線性無關(guān)的列向量組成,不失一般性,可假設(shè):),(212111211mmmmmmPPPaaaaaaB稱 Pj ( j = 1,2,m )為基向量,與基向量 Pj 相對應(yīng)的變量xj ( j = 1,2,m )為基變量,否則稱為非基變量。 為了進一步討論線性規(guī)劃問題的解,下面研究約束方程組(1.7)的求解問題。假設(shè)該方程組系數(shù)矩陣 A 的秩為 m ,因 m n,所以它有無窮多個解。假設(shè)前 m 個變量的系數(shù)列

31、向量是線性無關(guān)的，這時(1.7)式可改寫為：)9 . 1 (:111111111111nmjjjjmjjnmnnmmmmmmmmmxPbxPxaaxaabxaaxaa或方程組(1.9)的一個基是B=(P1, P2, ,Pm), Pj=(a1j, ,amj)T, (j = 1,2, , m ),設(shè) XB 是對應(yīng)于這個基的基向量,即： XB = ( x1, x2, , xm )T 現(xiàn)若令(1.9)式中的非基變量 xm+1 = = xn = 0 ,并用高斯消去法求出一個解 X = ( x1, x2, , xm , 0, , 0 )T ,這個解的非0分量的數(shù)目不大于方程個數(shù) m ,稱 X 為基本解.4

32、. 基本可行解基本可行解 : 滿足非負條件(1.8)的基本解稱為基本可行解.由此可見,基本可行解的非0分量的數(shù)目不大于 m ,并且都是非負的。5. 可行基可行基: 對應(yīng)于基本可行解的基稱為可行基.由此可見,約束方程組(1.7)基本解的數(shù)目至多是 Cnm 個.一般地講,基本可行解的數(shù)目要小于基本解的數(shù)目,至多相等. 以上提到的幾種解的概念,可用如下圖來表示:基解可行解基本可行解 第二節(jié)第二節(jié) 線性規(guī)劃問題的幾何意義線性規(guī)劃問題的幾何意義 在上一節(jié)的圖解法中,我們已經(jīng)直觀地看到了可行和最優(yōu)解的幾何意義,這一節(jié)從理論上進一步討論。一、基本概念：一、基本概念：1.凸集: 假設(shè) K 是 n 維歐氏空間的

33、一個點集,若對于K 中的任意兩點 X1、X2 ,其連線上的所有點 X1+(1-)X2 ( 0 1)都在集合 K 中,即: X1+(1-)X2 K ( 0 1)則稱 K 為凸集。從直觀上講，凸集無凹入部分，其內(nèi)部沒有洞。 實心圓、實心球、實心立方體等都是凸集，圓周不是凸集。圖（a)、(b)、為凸集，而圖（c)、(d)不是凸集。容易驗證以下結(jié)論是正確的：交集仍是凸集。定理：任意多個凸集的都是凸集。半空間半空間線。為一維向量時，就是直當(dāng)是凸集。（超平面）則且）（）設(shè)（都是凸集。和全集空集bxRxHbxRxHbxRxHRbRRTnTnTnnn, 0,2) 1 (212. 凸組合: 設(shè) X1、 X2、

34、Xk 是 n 維歐氏空間 En 中的k 個點，若存在 1、 2、 、 k，且 0 i 1 ,i = 1,2, , k, i = 1 , 使 X = 1X1 + 2X2 + + kXk , 則稱X 為由 X1、 X2、 Xk 所構(gòu)成的凸組合。 按照定義，凡是由x,y的凸組合表示的點都在x,y的連線上，而且反之亦然。3. 頂點: 假設(shè) K 是凸集, X K ; 若不能用不同的兩個點X1、 X2 K 的線性組合表示為: X = X1+(1-)X2 ， ( 0 1) 則稱 X 為凸集 K 的一個頂點（或稱為極點）。 頂點不位于凸集 K中的任意不同兩點的連線內(nèi)。二、基本定理二、基本定理定理定理1：若線性

35、規(guī)劃問題存在可行域，則其可行域： D = X AX = b , X 0 ，是凸集。引理引理1：線性規(guī)劃問題的可行解 X 為基本可行解的充要條件是 X 的正分量所對應(yīng)的系數(shù)列向量是線性無關(guān)的。證明證明 : (1) 必要性: 由基本可行解的定義便可知。（2）充分性：若向量 P1, P2, ,Pk 線性無關(guān)，則必有 km ; 當(dāng) k = m 時，它們恰好構(gòu)成一個基，從而 X = ( x1, x2, , xm , 0, , 0 )T 為相應(yīng)的基本可行解,當(dāng) k 0, 而 yj0 0 , 則(LP)無有限最優(yōu)解(也稱為無界解)。一、最優(yōu)性檢驗與解的判別一、最優(yōu)性檢驗與解的判別1. 最優(yōu)解判別定理最優(yōu)解判

36、別定理: 若 X(0) = ( XB(0), XN(0) )T , 其中XB(0)=B-1b , XN(0) =0 為對應(yīng)于基 B 的基本可行解 , 且對于一切jIN ,有 j 0 , 則 X(0) 已為( LP )的最優(yōu)解。證明證明:設(shè) X 為(LP)的一個可行解,令 X = ( XB, XN )T, 代入目標函數(shù)值整理得到:3. 基變換基變換: 若非上述兩種情形,則由式(1.23)可見,當(dāng)某些j 0, xj 0, jIN , 則目標函數(shù)值還可以增加。為使目標函數(shù)值增加最快，我們選擇： j = max ll 0 , l IN j所對應(yīng)的變量xj為換入變量(就是下一個基的基變量). 因為基變量

37、個數(shù)總是為 m , 所以換入一個之后還必須換出一個。下面我們來考慮如何選擇換出變量。 若初始基本可行解X(0)不是最優(yōu)解，那么就還要找一個新的基本可行解。其作法如下： 從原可行基中換出一個列向量，再投入一個新的列向量，（要保證線性無關(guān)），從而得到一個新的可行基，這就是基變換。 要做基變換要做基變換。首先確定換入變量（已講過），即選擇最大的檢驗數(shù)j所對應(yīng)的非基變量作為換入變量xj(進基變量)。 下面再確定換出變量再確定換出變量。確定換出變量的原則是保持解的可行性。這就說，要使原基本可行解的某一個正分量xj變?yōu)?，同時保持其余分量均非負。具體實現(xiàn)是按“最小比例原則”進行，也稱原則。 若則選基變量X

38、l為換出變量。4.旋轉(zhuǎn)運算（迭代）（樞運算） 在確定了換入變量Xk與換出變量Xl之后，要把xk和xl的位置對換，就是說，要把xk 所對應(yīng)的列向量pk變成單位向量。這只對系數(shù)矩陣的增廣矩陣進行變換即可，稱ylk為旋轉(zhuǎn)元。lillikikijybyyb0|min以表13中的元素 ykl (稱為主元素或旋轉(zhuǎn)元素)進行基變換: 將第 k 行每個元素除以 ykl , 將第 k 行每個元素乘以 yij / ykj 加到第 i 行( i = 1,2, ,m , i k , j = 1,2, , k ),將第 k 行每個元素乘以 j / ykj 加到檢驗數(shù)行, 對應(yīng)的新的目標函數(shù)值即為：)33.1(*01kj

39、kjybZZ經(jīng)過基變換之后，針對于新基 B1 的基本可行解 為：mkkijikjibybkimibybbxjkjkikjkji, 1, 1, 1,0)34. 1 ()(, 2 , 1*) 1 (的位置即為原來的綜合以上的討論,單純形算法的計算步驟可歸結(jié)如下：第一步：找出初始可行基，確定初始基本可行解 ，建立初始單純形表；第二步：檢查對應(yīng)于非基變量的檢驗數(shù) l ，lIN ，若所有 l 0 ，lIN ，則已得到最優(yōu)解，停止計算，否則轉(zhuǎn)入下一步；第三步：在所有l(wèi) 0，lIN 中，若有一個j 對應(yīng)的系數(shù)列向量 yj 0，則此問題沒有有限最優(yōu)解，停止計算，否則轉(zhuǎn)入下一步；第四步：根據(jù) max l l 0

40、，lIN = j ,確定 xj 為換入變量(即為新基的基變量),再根據(jù):miyybybijijikjk1, 0,min*確定 xk 為換出變量(即為新基的非基變量), 轉(zhuǎn)下一步；第五步：以 ykj 為主元素進行基變換，轉(zhuǎn)回第二步。 例例5. 利用單純形算法求解例1的線性規(guī)劃問題。 Max Z=2x1+3x2+0 x3+0 x4+0 x5+0 x6 2x1+2x2+x3 =12 x1+2x2+ x4 =8 4x2+ x5 =12 4x1+ x6=16 x1,x2,x3,x4,x5,x60 解： （1）由標準型得到：cj2 3 0 0 0 0XBbx1 x2 x3 x4 x5 x6 i2 2 1

41、0 0 01 2 0 1 0 04 0 0 0 1 0 0 4 0 0 0 1x3x4x5x6128161264-3-Z0 2 3 0 0 0 0 （2）max1, 2=3= 2,所以x2為換入變量. (3)因為1=2, 2=3都大于0，且p1,p2的坐標有正分量存在，33 , 4 , 6min0|minlklikikiiabaab因為3與x6那一行相對應(yīng)，所以x6為換出變量；cj2 3 0 0 0 0XBbx1 x2 x3 x4 x5 x6 i2 0 1 0 0 -1/21 0 0 1 0 -1/24 0 0 0 1 0 0 1 0 0 0 1/4x3x4x5x262163324-Z-9 2

42、 0 0 0 0 -3/4 故x2對應(yīng)列與x6對應(yīng)行的相交處的4為主元素；（4）以“4”為主元素進行旋轉(zhuǎn)計算，進行行初等變換，得下表：cj2 3 0 0 0 0XBbx1 x2 x3 x4 x5 x6 i0 0 1 -2 0 1/21 0 0 1 0 -1/20 0 0 -4 1 2 0 1 0 0 0 1/4x3x1x5x222834-412-Z-13 0 0 0 -2 0 1/4 這時出現(xiàn)了退化問題。即有兩個或更多的相同時，在相同 對應(yīng)的變量中選擇下標最大的那個基變量為換出變量；同時如果出現(xiàn)有兩個或更多的檢驗數(shù)相同時，在相同 對應(yīng)的變量中選擇下標最小的那個基變量為進入變量，這樣會避免出現(xiàn)“

43、死循環(huán)”的現(xiàn)象。cj2 3 0 0 0 0XBbx1 x2 x3 x4 x5 x6 i0 0 1 -1 -1/4 01 0 0 1 1/4 00 0 0 -2 1/2 1 0 1 0 -1/8 0 x3x1x6x20442-Z-14 0 0 0 -3/2 -1/8 0 這時，檢驗數(shù)全部小于等于0，即目標函數(shù)已不可能再增大，于是得到最優(yōu)解： X=(4,2,0,0,0,4)T目標函數(shù)的最大值為： Z=14 第四節(jié)第四節(jié) 單純形算法的進一步討論單純形算法的進一步討論一、初始基本可行解一、初始基本可行解 的確定的確定 利用單純形算法的一個根本前提是要有一個初始的基本可行解 .這對于一些簡單問題, 利用

44、觀察或其它手段是容易得到的;但對于較復(fù)雜的問題, 則利用這種方法幾乎是不可行的. 這就引起了人們對求初始基本可行解 的思考.以下我們分幾種情形加以討論。1. 對于 AX = b , 人們一下就可以從其中求得一個單位矩陣.這時取初始基 B 就是單位矩陣,對應(yīng)的基變量為 XB, 非基變量為 XN 。這時)0,(0bbXXNB這里假設(shè)當(dāng)然, 然后按單純形算法計算步驟便可得到。這種情況包含了 AX b 的情形。2. 人工變量法人工變量法(大大 M 法法) 設(shè)有一個線性規(guī)劃的約束條件是等式約束，這時分別給每一個約束條件加入人工變量 xn+1, , xn+m , 得:0,)35. 1 (111122212

45、1111111mnnnmmnnmnmnnnnnnxxxxbxxaxabxxaxabxxaxa由此得到一個 m 階單位矩陣. 以 xn+1, , xn+m 為基變量, 令非基變量 x1, , xn 為 0, 便可得到一個初始基本可行解 X(0) ; X(0) = ( 0, , 0, b1 , , bm )T 。 因為人工變量是后加入到原約束方程組中的虛擬變量, 我們要求將它們從基變量中逐漸替換掉.若經(jīng)過基的變換, 基變量中不再包含有人工變量, 這就表示原問題有解; 若經(jīng)過基變換,最后在基中至少還有一個人工變量, 這就意味著原問題無可行解. 具體處理方法如下: 對于加入人工變量的線性規(guī)劃問題的目標

46、函數(shù)如何處理?我們希望人工變量對目標函數(shù)取值不受影響.因此只有在迭代過程中, 把人工變量從基變量中換出,讓它成為非基變量.為此, 就必須假定人工變量在目標函數(shù)中的價值系數(shù)為(-M)(對于極大化目標), M為充分大的正數(shù).這樣, 對于要求實現(xiàn)目標函數(shù)最大化的問題來講,只要在基變量中還存在人工變量, 目標函數(shù)就不可能實現(xiàn)最大化. 這就是大M法。以下舉例加以說明。例例6. 試用大M法求解如下線性規(guī)劃問題的最優(yōu)解。0,12324112332131321321321xxxxxxxxxxxxxxZMin解解:在上述問題中加入松弛變量,剩余變量和人工變量得:0,12324112371731653214321

47、76321xxxxxxxxxxxxxxMxMxxxxZMax這里M是一個充分大的正數(shù), 取基變量為 x4 , x6 , x7 , 可得如下的表18。利用表18得初始單純形表，單純形算法得表19 表111。表表18cj3-1-100-M -MCBXBb*x1x2x3x4x5x6x70 x4111-211000-Mx63-4120-110-Mx71-2010001-Z03-1-100-M -Mcj3-1-100-M -MCBXBb*x1x2x3x4x5x6x70 x4111-21100011-Mx63-4120-1101.5-Mx71-20100011-Z4M 3-6M M-13M-10-M00初

48、始單純形表表表19cj3-1-100-M-MCBXBb*x1x2x3x4x5x6x70 x4103-20100-1-Mx610100-11-21-1x31-2010001- ZM+11M-100-M01-3Mcj3-1-100-M-MCBXBb*x1x2x3x4x5x6x70 x4123001-22-54-1x210100-11-2-1x31-2010001- Z21000-11-M-1-M 表表110cj3-1-100-M-MCBXBb*x1x2x3x4x5x6x73x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3- Z-200

49、0-1/3 -1/31/3-M2/3-M 表表111在表111中，所有的 j 0，故得到最優(yōu)解： X* = ( 4, 1, 9, 0, 0, 0, 0 )T 目標函數(shù)值 Z= 2 , 原問題的最優(yōu)目標值為: Z* = -2 。3. 兩階段法兩階段法: 這種方法是在約束條件中加入人工變量,將線性規(guī)劃問題分為兩階段進行求解. 第一階段是先求出基本可行解 (或判斷出原線性規(guī)劃問題無解), 第二階段利用已求出的初始基本可行解 來求最優(yōu)解。具體由如下定理5給出。定理定理5 設(shè)原線性規(guī)劃問題記成(LP), 由它而引入的新的線性規(guī)劃問題記成(LP)*。分別表示如下：個mTTmnnTTexxXXXbIXAXX

50、bAXXeWMinLPXCZMaxLP)1 , 1 (,),(0,00:)*(:)(1*1) 若(LP)*具有最優(yōu)基本可行解 ,0,*XXX且則(LP)是可行的,而 .)(的一個基可行解即為 LPX2) 若(LP)*的最優(yōu)基本可行解 ,0,*XXX使得則(LP)必不可行。 定理5的具體應(yīng)用過程是: (LP)*判斷原線性規(guī)劃問題是否存在基本可行解 , 利用單純形算法, 若得到 W = 0 , 即所有人工變量為非基變量, 這表示原問題已得到了一個基本可行解 .于是只需要將第一階段最終計算表中的目標函數(shù)行的數(shù)字換成原問題的目標函數(shù)的數(shù)字, 就得到了求解原問題的初始計算表, 再進行第二階段的求解。若第

51、一階段的最終計算表出現(xiàn) W 0 , 這就表明原問題無可行解，應(yīng)停止計算。0,12324112332131321321321xxxxxxxxxxxxxxZMax解：解：先在以上問題的約束條件中加入松弛變量、剩余變量、人工變量，給出第一階段的線性規(guī)劃問題：0,12324112717316532143217676xxxxxxxxxxxxxxxxWMaxxxZMin各階段的計算方法及步驟與前述單純形法完全相同，下面用例子說明該方法的應(yīng)用。 例例7：試用兩階段法求解如下線性規(guī)劃問題以 x4、x6、x7 為基變量得如下初始計算表cj00000-1-1CBXBb*x1x2x3x4x5x6x70 x4111-

52、211000-1x63-4120-110-1x71-2010001-W000000-1-1cj00000-1-1CBXBb*x1x2x3x4x5x6x70 x4111-21100011-1x63-4120-1101.5-1x71-20100011-W4-6130-100初始單純形表112表表113cj00000-1-1CBXBb*x1x2x3x4x5x6x70 x4103-20100-1-1x610100-11-21-1x31-2010001-W10100-10-3表表114cj00000-1-1CBXBb*x1x2x3x4x5x6x70 x4123001-22-50 x210100-11-2

53、0 x31-2010001-W000000-1-1 這里 x6、x7 是人工變量。第一階段我們已求得 W = 0 ，最優(yōu)解 x5 = 0， x6 = 0， x7 = 0。因人工變量 x6 = x7 = 0, 所以( 0, 1, 1 ,12, 0 )T 是原問題的基本可行解 。于是可以開始第二階段的計算。將第一階段的最終計算表114中的人工變量列取消, 并將目標函數(shù)系數(shù)換成原問題的目標函數(shù)系數(shù), 重新計算檢驗數(shù)行, 可得如下第二階段的初始單純形表115；應(yīng)用單純形算法求解得最終表116。 表表115cj3-1-100CBXBb*x1x2x3x4x50 x4123001-212/3=4-1x210

54、100-1-1x31-20100-Z21000-1表表116cj3-1-100CBXBb*x1x2x3x4x53x141001/3-2/3-1x210100-1-1x390012/3-4/3-Z-2000-1/3-1/3表116中所有檢驗數(shù) j 0，所以 x1 = 4，x2 = 1 , x3 = 9 是原線性規(guī)劃問題的最優(yōu)解。目標函數(shù)值： Z* = 2 。第五節(jié)第五節(jié) LP的對偶理論的對偶理論1.5.1 對偶問題對偶問題例例 1 2 加工能力加工能力(小時小時/天天) A 2 2 12 B 1 2 8 C 4 0 16 D 0 4 12 2 3銷售收入銷售收入產(chǎn)品產(chǎn)品設(shè)備設(shè)備設(shè)設(shè)X1 ， X2

55、 為產(chǎn)品為產(chǎn)品1，2的產(chǎn)量的產(chǎn)量2X1 +2X2 12 X1 +2X2 84X1 16 4X2 12X1 X2 0maxZ= 2X1 +3X2 2 2 12 1 2 X1 84 0 X2 160 4 12 (2 3) X1X2設(shè)設(shè) y1 , y2 , y3 , y4分別為出租每臺設(shè)備臺時的租分別為出租每臺設(shè)備臺時的租金和出讓單位原材料金和出讓單位原材料A, B的附加額。的附加額。2y1 +y2 +4y3 22y1 +2y2 +44 3y1 y4 02 1 4 02 2 0 4y1 y2 y3 y4 23(y1 y2 y3 y4)2 21 24 00 4 (2,3)minW=12y1+8y2 +

56、16y3+12y4y1 , y2 , y3 , y4 “影子價格影子價格”定義：定義：對偶問題對偶問題 minW=yb yA Cy 0minW=bTyATy CTy 0maxZ=CX AX bX 0原問題原問題對偶關(guān)系對應(yīng)表對偶關(guān)系對應(yīng)表 原問題原問題 對偶問題對偶問題目標函數(shù)類型目標函數(shù)類型 max min目標函數(shù)系數(shù)目標函數(shù)系數(shù) 目標函數(shù)系數(shù)目標函數(shù)系數(shù) 右邊項系數(shù)右邊項系數(shù)與右邊項的對應(yīng)關(guān)系與右邊項的對應(yīng)關(guān)系 右邊項系數(shù)右邊項系數(shù) 目標函數(shù)系數(shù)目標函數(shù)系數(shù)變量數(shù)與約束數(shù)變量數(shù)與約束數(shù) 變量數(shù)變量數(shù)n 約束數(shù)約束數(shù) n的對應(yīng)關(guān)系的對應(yīng)關(guān)系 約束數(shù)約束數(shù)m 變量數(shù)變量數(shù)m原問題變量類型與原問

57、題變量類型與 0 對偶問題約束類型對偶問題約束類型 變量變量 0 約束約束 的對應(yīng)關(guān)系的對應(yīng)關(guān)系 無限制無限制 原問題約束類型與原問題約束類型與 0 對偶問題變量類型對偶問題變量類型 約束約束 變量變量 0 的對應(yīng)關(guān)系的對應(yīng)關(guān)系 無限制無限制例例1、寫出下面問題的對偶規(guī)劃、寫出下面問題的對偶規(guī)劃maxZ= 5X1 +6X2 3X1 -2X2 =74X1 +X2 9X1 , X2 0minW=7y1 +9y23y1+4y2 5 -2y1 +y2 6y1自由自由 , y2 0解：對偶問題解：對偶問題例例2 2、寫對偶規(guī)劃、寫對偶規(guī)劃minZ= 4X1 +2X2 -3X3 -X1+2X2 62X1

58、+3X3 9 X1 +5X2 -2X3 = = 4X2 , X3 0maxW= 6y1 +9y2 +4y3 -y1+2y2 + y3 = = 42y1 +5y3 2 3y2 -2y3 -3y1 0 , y2 0 , y3自由自由minZ= 4X1 +2X2 -3X3 X1 -2X2 - 62X1 +3X3 9 X1 +5X2 -2X3 = = 4X2 , X3 0或?qū)⒃瓎栴}變形為或?qū)⒃瓎栴}變形為maxW= -6y1 +9y2 +4y3 y1+2y2 + y3 = = 4-2y1 +5y3 2 3y2 -2y3 -3y1 , y2 0 , y3自由自由對偶規(guī)劃對偶規(guī)劃產(chǎn)品產(chǎn)品A，B產(chǎn)量為產(chǎn)量為X

59、1，X2，Z為利潤為利潤例例1、3X1 +X2 +X3=483X1 +4X2 +X4=120X1 X4 0maxZ= 5X1 +6X2 3X1 +X2 483X1 +4X2 120X1 , X2 0機器臺時機器臺時勞動工時勞動工時X=(8,24)T Z =184 5 6 0 0 X1 X2 X3 X40 X3 48 3 1 1 00 X4 120 3 (4) 0 1 0 5 6 0 0 0 X3 18 (9/4) 0 1 -1/46 X2 30 3/4 1 0 1/4 180 1/2 0 0 -3/2 5 X1 8 1 0 4/9 -1/96 X2 24 0 1 -1/3 1/3 184 0

60、0 -2/9 -13/93y1+3y2 5 y1 +4y2 6minW=48y1+120y23y1+3y2 -y3+y5 =5 y1 +4y2 -y4+y6= 6minW=48y1+120y2 +My5 +My6y=(2/9,13/9), Z=184 48 120 0 0 48 120 0 0 M M y1 y2 y3 y4 y5 y6M y5 5 3 3 -1 0 1 0 5 3 3 -1 0 1 0 M y6 6 1 6 1 4 0 -1 0 1 4 0 -1 0 1 yB 1111M 48-4 48-4M 120-7M M M 0 0 0 0M y5 1/2 9/4 0 -1 3/4 1