線性規(guī)劃及單純形法演示文稿

線性規(guī)劃及單純形法演示文稿目前一頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)緒論一、運(yùn)籌學(xué)發(fā)展簡(jiǎn)介二、運(yùn)籌學(xué)的特點(diǎn)及研究對(duì)象三、運(yùn)籌學(xué)的工作步驟四、運(yùn)籌學(xué)內(nèi)容介紹目前二頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)2一、運(yùn)籌學(xué)（OR）發(fā)展簡(jiǎn)介運(yùn)籌學(xué)在國(guó)外英國(guó)稱(chēng)為OperationalResearch美國(guó)稱(chēng)為OperationsResearch起源于二戰(zhàn)期間的軍事問(wèn)題，如雷達(dá)的設(shè)置、運(yùn)輸船隊(duì)的護(hù)航艦隊(duì)的規(guī)模、反潛作戰(zhàn)中深水炸彈的深度、飛機(jī)出擊隊(duì)型、軍事物資的存儲(chǔ)等。二戰(zhàn)以后運(yùn)籌學(xué)應(yīng)用于經(jīng)濟(jì)管理領(lǐng)域（LP、計(jì)算機(jī)）1948年英國(guó)首先成立運(yùn)籌學(xué)會(huì)；1952年美國(guó)成立運(yùn)籌學(xué)會(huì)。1952年，Morse和Kimball出版《運(yùn)籌學(xué)方法》1959年成立國(guó)際運(yùn)籌學(xué)聯(lián)合會(huì)目前三頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)3

運(yùn)籌學(xué)在國(guó)內(nèi)中國(guó)古代樸素的運(yùn)籌學(xué)思想（田忌賽馬、都江堰工程、丁渭修復(fù)皇宮）1956年中科院成立運(yùn)籌學(xué)小組1957年正式將OperationsResearch命名為“運(yùn)籌學(xué)”1958年提出運(yùn)輸問(wèn)題的圖上作業(yè)法（解決糧食合理運(yùn)輸問(wèn)題）1962年提出中國(guó)郵路問(wèn)題（管梅谷）1964年華羅庚推廣統(tǒng)籌方法1980年中國(guó)運(yùn)籌學(xué)學(xué)會(huì)正式成立1982年中國(guó)加入國(guó)際運(yùn)籌學(xué)聯(lián)合會(huì)1999年8月我國(guó)組織了第15屆大會(huì)目前四頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)4＊齊王賽馬（齊王和田忌）戰(zhàn)國(guó)時(shí)期，齊威王與田忌賽馬，規(guī)定雙方各出上中下三個(gè)等級(jí)的馬各一匹。如果按同等級(jí)的馬比賽，齊王可獲全勝。田忌的謀士孫臏提出的以下、上、中對(duì)齊王的上、中、下對(duì)策，使處于劣勢(shì)的田忌戰(zhàn)勝齊王，這是從總體出發(fā)制定對(duì)抗策略的一個(gè)著名事例。目前五頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)5丁渭主持皇宮的修復(fù)（北宋，皇宮因火焚毀）北宋真宗年間，皇城失火，宮殿燒毀，大臣丁謂主持了皇宮修復(fù)工程。他采用了一套綜合施工方案:①先在需要重建的大道上就近取土燒磚；②在取土后的深溝中引水，形成人工河，再由此水路運(yùn)入建筑材料，從而加快了工程進(jìn)度；③皇宮修復(fù)后，又將碎磚廢土填入溝中，重修大道。使燒磚、運(yùn)輸建筑材料和處理廢墟三項(xiàng)繁重工程任務(wù)協(xié)調(diào)起來(lái)，從而在總體上得到了最佳解決，一舉三得，節(jié)省了大量勞力、費(fèi)用和時(shí)間。目前六頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)6運(yùn)籌學(xué)為決策機(jī)構(gòu)對(duì)所控制的業(yè)務(wù)活動(dòng)作決策時(shí)，提供以數(shù)量為基礎(chǔ)的科學(xué)方法——Morse和Kimball運(yùn)籌學(xué)是把科學(xué)方法應(yīng)用在指導(dǎo)人員、工商企業(yè)、政府和國(guó)防等方面解決發(fā)生的各種問(wèn)題，其方法是發(fā)展一個(gè)科學(xué)的系統(tǒng)模式，并運(yùn)用這種模式預(yù)測(cè)、比較各種決策及其產(chǎn)生的后果，以幫助主管人員科學(xué)地決定工作方針和政策——英國(guó)運(yùn)籌學(xué)會(huì)運(yùn)籌學(xué)是應(yīng)用分析、試驗(yàn)、量化的方法對(duì)經(jīng)濟(jì)管理系統(tǒng)中人力、物力、財(cái)力等資源進(jìn)行統(tǒng)籌安排，為決策者提供有根據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理——中國(guó)百科全書(shū)現(xiàn)代運(yùn)籌學(xué)涵蓋了一切領(lǐng)域的管理與優(yōu)化問(wèn)題，稱(chēng)為ManagementScience運(yùn)籌學(xué)的定義二、運(yùn)籌學(xué)的特點(diǎn)及研究對(duì)象目前七頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)7運(yùn)籌學(xué)的特點(diǎn)：優(yōu)化：從全局觀點(diǎn)看問(wèn)題，追求總體效果最優(yōu)量化：通過(guò)建立和求解模型使問(wèn)題在量化的基礎(chǔ)上得到合理決策綜合：多學(xué)科交叉運(yùn)籌學(xué)的研究對(duì)象：生產(chǎn)與經(jīng)濟(jì)等各種實(shí)踐活動(dòng)中提出來(lái)的實(shí)際問(wèn)題二、運(yùn)籌學(xué)的特點(diǎn)及研究對(duì)象目前八頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)8三、運(yùn)籌學(xué)的工作步驟明確問(wèn)題建立模型設(shè)計(jì)算法整理數(shù)據(jù)求解模型評(píng)價(jià)結(jié)果簡(jiǎn)化？滿(mǎn)意？YesNoNo明確問(wèn)題建立模型設(shè)計(jì)算法整理數(shù)據(jù)求解模型評(píng)價(jià)結(jié)果目前九頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)9四、運(yùn)籌學(xué)內(nèi)容介紹線性規(guī)劃及單純形法對(duì)偶理論及靈敏度分析運(yùn)輸問(wèn)題整數(shù)規(guī)劃動(dòng)態(tài)規(guī)劃圖與網(wǎng)絡(luò)分析

目前十頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)10第一章線性規(guī)劃及單純形法1939年蘇康托洛維奇發(fā)表“生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法”，1960年出版“最佳資源利用的經(jīng)濟(jì)計(jì)算”獲諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)1941年美Hichcock提出運(yùn)輸問(wèn)題1947年美丹捷格（）提出單純形法，1963年出版“線性規(guī)劃及其擴(kuò)展”

在生產(chǎn)管理中如何有效地利用現(xiàn)有人力、物力完成更多的任務(wù)，或在預(yù)定的任務(wù)目標(biāo)下，如何耗用最少的人力、物力去實(shí)現(xiàn)目標(biāo)。目前十一頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)11第一節(jié)線性規(guī)劃問(wèn)題及數(shù)學(xué)模型例1生產(chǎn)計(jì)劃問(wèn)題(P4)

III資源限量設(shè)備128臺(tái)時(shí)原材料A4016公斤原材料B0412公斤單位利潤(rùn)23設(shè)I、II兩種產(chǎn)品的產(chǎn)量分別為x1,x2。建立該問(wèn)題的數(shù)學(xué)模型為：目標(biāo)函數(shù)約束條件決策變量一、實(shí)例目前十二頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)12例2合理下料問(wèn)題

現(xiàn)要做100套鋼架，每套需2.9米、2.1米和1.5米的圓鋼各一根。已知原料長(zhǎng)7.4米，問(wèn)如何下料，使用的原料最少（余料最少或根數(shù)最少）？解：設(shè)x1,x2,

x3,x4,x5分別代表五種不同的原料用量方案（余料最少）目前十三頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)13方案2.9米2.1米1.5米合計(jì)余料x(chóng)11037.40x22017.30.1x30227.20.2x41207.10.3x50136.60.8決策變量？目標(biāo)函數(shù)？特點(diǎn)？約束條件？決策方案？最優(yōu)方案？最優(yōu)值？目前十四頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)14二、總結(jié)目標(biāo)函數(shù)用決策變量的線性函數(shù)來(lái)表示。按問(wèn)題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化和最小化。線性規(guī)劃問(wèn)題（LP問(wèn)題）的共同特征：每一個(gè)問(wèn)題變量都用一組決策變量（x1,x2,…,xn）表示某一方案，這組決策變量的值代表一個(gè)具體方案，這些變量是非負(fù)的。存在一定的約束條件，這些約束條件可以用一組線性等式或線性不等式來(lái)表示。線性規(guī)劃模型的一般形式與標(biāo)準(zhǔn)形式（P7稍后講）目前十五頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)15三、兩變量線性規(guī)劃問(wèn)題的圖解法1.線性不等式的幾何意義—

半平面作出LP問(wèn)題的可行域作出目標(biāo)函數(shù)的等值線移動(dòng)等值線到可行域邊界得到最優(yōu)點(diǎn)2.圖解法步驟目前十六頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)164x1=164x2=12x1+2x2=8x1x248430例1（書(shū)P4）：Q(4,2)Z=2x1+3x2做目標(biāo)函數(shù)2x1+3x2的等值線，與陰影部分的邊界相交于Q(4,2)點(diǎn)，表明最優(yōu)生產(chǎn)計(jì)劃為：生產(chǎn)I產(chǎn)品4件，生產(chǎn)II產(chǎn)品2件。最大利潤(rùn)：14.基本概念：可行解、可行域、最優(yōu)解？目前十七頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)17例2Z=36目前十八頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)183.圖解法的作用能解決少量問(wèn)題LP問(wèn)題有可行解有最優(yōu)解唯一解無(wú)窮多解無(wú)最優(yōu)解（可行域?yàn)闊o(wú)界）無(wú)可行解（無(wú)解）規(guī)律1：揭示了線性規(guī)劃問(wèn)題的若干規(guī)律見(jiàn)P9-10例題目前十九頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)19結(jié)論：若LP問(wèn)題有最優(yōu)解，則要么最優(yōu)解唯一，要么有無(wú)窮多最優(yōu)解?！锬壳岸?yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)20

規(guī)律2：線性規(guī)劃問(wèn)題的可行域?yàn)橐煌辜€性規(guī)劃問(wèn)題凸集的頂點(diǎn)個(gè)數(shù)是有限的最優(yōu)解肯定可在凸集的某頂點(diǎn)處達(dá)到目前二十一頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)21四、線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型1.一般形式目前二十二頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)222.標(biāo)準(zhǔn)型LP模型的各種表示法見(jiàn)P7目前二十三頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)233.所有LP問(wèn)題均可化為標(biāo)準(zhǔn)型1.目標(biāo)函數(shù)最大化2.約束條件為等式3.變量約束為非負(fù)4.約束右端項(xiàng)非負(fù)目前二十四頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)24例1可化為目前二十五頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)25例2化標(biāo)準(zhǔn)型目前二十六頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)26課堂作業(yè)目前二十七頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)27五、標(biāo)準(zhǔn)型LP問(wèn)題的解LP模型向量表示法見(jiàn)P7目前二十八頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)28目前二十九頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)29令B==(P1,P2,…,Pm)且|B|0，稱(chēng)A中基B對(duì)應(yīng)的列向量Pj(j=1,2,…,m)

為基向量。與基向量Pj對(duì)應(yīng)的變量xj稱(chēng)為基變量，記為XB=(x1,x2,…,xm)T，其余的變量稱(chēng)為非基變量，記為XN=(xm+1,xm+2,…,xm+n)T?；兞浚耗壳叭?yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)30基本解令非基變量XN=0，求得的一組基變量XB的值稱(chēng)為基本解。基可行解（頂點(diǎn)）既是基本解，又是可行解?；顑?yōu)點(diǎn)既是基本解，又是使目標(biāo)函數(shù)值達(dá)到最優(yōu)的解目前三十一頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)31如引例中：基基變量非基變量基本解是否可行目標(biāo)函數(shù)值ZB1x1,x2x3,x4（-2，3，0，0）否B2x1,x3x2,x4（3，0，1，0）是Z=3B3x1,x4x2,x3（4，0，0，-3）否B4x2,x3x1,x4

（0，9/5，2/5，0）是Z=9/5B5x1,x4x2,x3（2，0，0，-1）

否B3x3,x4x1,x2（0，0，4，9）是Z=0目前三十二頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)32

線性規(guī)劃標(biāo)準(zhǔn)型問(wèn)題解的關(guān)系約束方程的解空間基解可行解非可行解基可行解LP解的基本定理見(jiàn)P12目前三十三頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)33第二節(jié)單純型法

一、基本思想化LP問(wèn)題為標(biāo)準(zhǔn)型，確定一個(gè)初始基本可行解檢驗(yàn)解的最優(yōu)性結(jié)束Y樞軸運(yùn)算（旋轉(zhuǎn)運(yùn)算）確定另一個(gè)基本可行解N目前三十四頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)34二、樞軸運(yùn)算目前三十五頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)35又如：目前三十六頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)36三、檢驗(yàn)數(shù)的意義P17目前三十七頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)37四、單純形表基變量非基變量常數(shù)項(xiàng)約束方程增廣矩陣檢驗(yàn)數(shù)+目標(biāo)函數(shù)值P17目前三十八頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)38第三節(jié)單純型法的步驟一、步驟化LP問(wèn)題為標(biāo)準(zhǔn)型,建立初始單純型表;直接求最小化問(wèn)題，P23說(shuō)明目前三十九頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)39二、用單純形表求解LP問(wèn)題實(shí)例化為標(biāo)準(zhǔn)型例1.目前四十頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)40單純型表

算法步驟：Cj23000

CBXBbX1X2X3X4X50X30X40X58161212100440010-0[4]0013023000以[4]為樞軸元素進(jìn)行旋轉(zhuǎn)運(yùn)算，x2為換入變量，x5為換出變量Cj23000

CBXBbX1X2X3X4X50X30X43X22163[1]010-1/2240010401001/4--92000-3/4以[1]為樞軸元素進(jìn)行運(yùn)算，x1為換入變量，x3為換出變量（1）建立初始單純形表；（2）求檢驗(yàn)數(shù)并判斷最優(yōu)性，若最優(yōu)，終止，否則轉(zhuǎn)下一步；（3）確定出基與進(jìn)基變量；（4）換基迭代，轉(zhuǎn)入（2）。目前四十一頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)41Cj23000

CBXBbX1X2X3X4X52X10X43X22831010-1/2-00-41[2]401001/412-1300-201/4以[2]為樞軸元素進(jìn)行運(yùn)算，x5為換入變量，x4為換出變量Cj23000

CBXBbX1X2X3X4X52X10X53X24421001/4000-21/21011/2-1/80-1400-3/2-1/80此時(shí)達(dá)到最優(yōu)解。X*=(4,2),MaxZ=14。目前四十二頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)42例2目前四十三頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)43解:化標(biāo)準(zhǔn)型目前四十四頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)44

21000

01505100

0

24620100511001

21000

—24/65/1主元化為1主列單位向量換出換入表1：列初始單純形表（單位矩陣對(duì)應(yīng)的變量為基變量）正檢驗(yàn)數(shù)中最大者對(duì)應(yīng)的列為主列最小的值對(duì)應(yīng)的行為主行目前四十五頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)45

21000

01505100

2

412/601/600104/60-1/6101/30-1/30

15/524/26/4

0*52*2/6+0*4/61-2/3=表2：換基

（初等行變換，主列化為單位向量，主元為1）檢驗(yàn)數(shù)>0確定主列最小確定主列主元目前四十六頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)46

21000

015/20015/4-15/2

2

7/21001/4-1/213/2010-1/43/2000-1/4-1/2

檢驗(yàn)數(shù)<=0最優(yōu)解為X=(7/2,3/2,15/2,0,0)目標(biāo)函數(shù)值Z=8.5

2*7/21*3/2+0*15/28.5表3：換基

（初等行變換，主列化為單位向量，主元為1）目前四十七頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)47

21000

01505100

0

24620100511001

21000練習(xí):一般主列選擇正檢驗(yàn)數(shù)中最大者對(duì)應(yīng)的列,也可選擇其它正檢驗(yàn)數(shù)的列.以第2列為主列,用單純形法求解。正檢驗(yàn)數(shù)對(duì)應(yīng)的列為主列注：1.幾種特殊情形P20-23；2.對(duì)于極小化的LP問(wèn)題，只須改成檢驗(yàn)數(shù)≥0為最優(yōu)。目前四十八頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)48第四節(jié)LP問(wèn)題的進(jìn)一步討論一、人工變量法目前四十九頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)491.大M法(M為任意大的正數(shù))加入松弛變量x4;剩余變量x5;人工變量x6,x7目前五十頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)501)人工變量的識(shí)別2)目標(biāo)函數(shù)的處理3)計(jì)算(單純型法)目前五十一頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)51Cj-31100MMCBXBbx1x2x3x4x5x6x70x4111-21100011Mx63-4120-1103/2Mx71-20100011-3+6M1-M1-3M0M000x4103-20100-1-Mx610100-11-211x31-2010001--11-M00M03M-1注意：本例是求最小值，所以用所有來(lái)判別目標(biāo)函數(shù)是否實(shí)現(xiàn)了最小化。因而換入變量xk的選取標(biāo)準(zhǔn)為目前五十二頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)52結(jié)果得:X*=(4,1,9,0,0,0,0)Z*=2Cj-31100MMCBXBbx1x2x3x4x5x6x70x4123001-22-541x210100-11-2-1x31-2010001--10001M-1M+1-3x141001/3-2/32/3-5/31x210100-11-21x390012/3-4/34/3-7/30001/31/3M-1/3M-2/3（接上表）目前五十三頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)53兩階段法(將LP問(wèn)題分成兩個(gè)階段來(lái)考慮)第I階段:求解模型（1）得到原問(wèn)題的一個(gè)基本可行解。做法是：先不考慮原問(wèn)題是否存在可行解，給原LP問(wèn)題加入人工變量，并構(gòu)造僅含人工變量之和的目標(biāo)函數(shù)w并要求最小化；然后用單純型法求解，若得w=0，則求得原問(wèn)題的一個(gè)基本可行解，進(jìn)行第二階段計(jì)算，否則無(wú)可行解。目前五十四頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)54第II階段：求解模型（2）得到原LP問(wèn)題的最優(yōu)解。做法是：將第一階段得到的最終表除去人工變量，將目標(biāo)函數(shù)行的系數(shù)換為原問(wèn)題的系數(shù)，作為第二階段的初始表。目前五十五頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)55加入松弛變量x4;剩余變量x5;人工變量x6,x7用單純形法求解第一階段的結(jié)果得：目前五十六頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)56Cj0000011CBXBbx1x2x3x4x5x6x70x4111-211000111x63-4120-1103/21x71-201000116-1-301000x4103-20100-1-1x610100-11-210x31-2010001-0-1001030x4123001-22-540x210100-11-2-0x31-2010000-0000011此時(shí)，達(dá)到第一階段的最優(yōu)解，W=0目前五十七頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)57Cj-31100CBXBbx1x2x3x4x50x4123001-241x210100-1-1x31-20100--10001-3x141001/3-2/31x210100-11x390012/3-4/30001/31/3由于人工變量x6=x7=0,所以（0,1,1,12,0）T是該線性規(guī)劃問(wèn)題的基可行解。于是轉(zhuǎn)入第二階段運(yùn)算：此時(shí)達(dá)到該LP問(wèn)題的最優(yōu)解：x1=4,x2=1,x3=9;目標(biāo)函數(shù)值Z=-2。目前五十八頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)58二、單純型法中存在的問(wèn)題1.存在兩個(gè)以上的最大正檢驗(yàn)數(shù)。選擇任何變量（對(duì)應(yīng)最大正檢驗(yàn)數(shù)）作為進(jìn)基變量。2.最小比值相同。LP問(wèn)題出現(xiàn)退化現(xiàn)象，即基變量取值為0★目前五十九頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)59Cj3/4-201/2-6000CBXBbX1X2X3X4X5X6X70X501/4-8-191000X601/2-12-1/230100X71001000103/4-201/2-6000目前六十頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)60Cj3/4-201/2-6000CBXBbX1X2X3X4X5X6X73/4X101-32-4364000X60043/2-150100X7100100010047/221-300選取x1為換入變量；按Bland算法，選取下標(biāo)最小的x5為換出變量，得下表：此時(shí)換出變量為x1，換入變量為x4，迭代后目標(biāo)函數(shù)值不變，繼而出現(xiàn)了循環(huán)現(xiàn)象，達(dá)不到最優(yōu)解。Cj3/4-201/2-6000CBXBbX1X2X3X4X5X6X73/4X101-32-4364000X60043/2-150100X7100100010047/221-300目前六十一頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)61解決退化的方法有：“攝動(dòng)法”、“辭典序法”、Bland規(guī)則等1974年Bland提出Bland算法規(guī)則：目前六十二頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)623.最小比值原則失效Cj2300CBXBbX1X2X3X40X36-20113X24-3101Cj-Zj-121100-3經(jīng)過(guò)一次迭代后可得右表★目前六十三頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)634.在最優(yōu)表中出現(xiàn)某非基變量檢驗(yàn)數(shù)為0目前六十四頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)64CBXBbX1X2X3X4X50X340012/3-1/34X260101/203X14100-2/31/3Cj-Zj-360000-10X46003/21-1/24X2301-3/401/43X1810100Cj-Zj-360000-1Cj-Zj034000結(jié)論：若線性規(guī)劃問(wèn)題存在某非基變量檢驗(yàn)數(shù)為0,而其對(duì)應(yīng)列向量ak≤0,仍可判斷線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。任一個(gè)LP問(wèn)題最優(yōu)解都可表示成其基本最優(yōu)解的凸組合加上其凸方向的線性組合.目前六十五頁(yè)\總數(shù)八十頁(yè)\編于十八點(diǎn)65第五節(jié)應(yīng)用舉例例1某工廠要用三種原材料C、P、H混合調(diào)配出三種不同規(guī)格的產(chǎn)品A、B、D。已知產(chǎn)品的規(guī)格要求、單價(jià)和原材料的供應(yīng)量、單價(jià)。該廠應(yīng)如何安排生產(chǎn)使利潤(rùn)最大？產(chǎn)品名稱(chēng)規(guī)格要求單價(jià)(元/kg）A原材料C不少于50%原材料P不超過(guò)25%50B原材料C不少于25%原材料P不超過(guò)50%35