線性規(guī)劃圖解法教案課件

線性規(guī)劃圖解法線性規(guī)劃圖解法11832和1911年法國數(shù)學家J.B.J.傅里葉和C.瓦萊－普森分都分別獨立地提出線性規(guī)劃的想法，但未引起注意。

1939年，前蘇聯(lián)數(shù)學家康托洛維奇用線性規(guī)劃模型研究提高組織和生產(chǎn)效率問題

1947年，Dantzig提出求解線性規(guī)劃的單純形法

1950-1956年，主要研究線性規(guī)劃的對偶理論1951年美國經(jīng)濟學家T.C.庫普曼斯把線性規(guī)劃應(yīng)用到經(jīng)濟領(lǐng)域，為此與康托羅維奇一起獲1975年諾貝爾經(jīng)濟學獎。

1958年，發(fā)表整數(shù)規(guī)劃的割平面法

1960年，Dantzig和Wolfe研究成功分解算法，奠定了大規(guī)模線性規(guī)劃問題理論和算法的基礎(chǔ)。一、線性規(guī)劃發(fā)展概況第1頁/共44頁1832和1911年法國數(shù)學家J.B.J.傅里葉2線性規(guī)劃的研究成果還直接推動了其他數(shù)學規(guī)劃問題包括整數(shù)規(guī)劃、隨機規(guī)劃和非線性規(guī)劃的算法研究。由于數(shù)字電子計算機的發(fā)展，出現(xiàn)了許多線性規(guī)劃軟件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解幾千個變量的線性規(guī)劃問題。

1979年，Khachiyan，1984年，Karmarkaa研究成功線性規(guī)劃的多項式算法。用卡馬卡方法求解線性規(guī)劃問題在變量個數(shù)為5000時只要單純形法所用時間的1/50。

第2頁/共44頁線性規(guī)劃的研究成果還直接推動了其他數(shù)學規(guī)劃問題包括整數(shù)規(guī)劃、3二、線性規(guī)劃研究解決的主要問題

實際上，上述兩類問題是一個問題的兩個不同的方面，都是求問題的最優(yōu)解（max或min）。

另一類是當一項任務(wù)確定以后，研究如何統(tǒng)籌安排，才能使完成任務(wù)所耗費的資源量為最少。一類是已有一定數(shù)量的資源（人力、物質(zhì)、時間等），研究如何充分合理地使用它們，才能使完成的任務(wù)量為最大。線性規(guī)劃在工商管理中應(yīng)用有著廣泛的用處，可以用來解決諸如：人力資源分配問題、生產(chǎn)計劃問題、下料配料、投資問題（見第4章）以及運輸問題（第7章）等。實際上遠不止這些具體問題。但從一般意義上解決得問題有兩類：第3頁/共44頁二、線性規(guī)劃研究解決的主要問題實際上，上述兩類問題是一4三、LP解決問題的一般思路5、模型求解與解的調(diào)適。（獲得最優(yōu)方案——一組決策變量的取值）。1、對問題進行系統(tǒng)分析,搞清決策什么和決策目標是什么？2、明確是哪些因素（人為可控的，決策變量）影響決策目標（大小變化），確定決策變量對目標（函數(shù)）影響系數(shù)，且與目標函數(shù)是否呈線形關(guān)系。3、哪些資源約束（或需求約束）條件制約著目標（最大或最?。?。決策變量對這些資源（或需求）的單位消耗（單位產(chǎn)出）是多少？，即要獲得資源總量和投入產(chǎn)出系數(shù)。4、建立線形規(guī)劃數(shù)學模型。6、方案實施與調(diào)整。第4頁/共44頁三、LP解決問題的一般思路5、模型求解與解的調(diào)適。（獲得最優(yōu)5§2.1LP問題的提出及其數(shù)學模型一、例示——問題提出例2.1-1某廠在計劃期內(nèi)安排生產(chǎn)兩種產(chǎn)品，生產(chǎn)所需資源限制及單位產(chǎn)品原料消耗由下表給給出

利潤50100問：應(yīng)如何安排生產(chǎn)計劃才能使總利潤最大？

甲乙資源限制設(shè)備11300臺時原料A21400kg原料B01250kg解：確定決策變量：設(shè)產(chǎn)品甲乙的產(chǎn)量分別為：x1、x22.建立目標函數(shù)：設(shè)總利潤為z，本例是：

maxz=50x1+100x23.考慮約束條件：x1+x2≤3002x1+x2≤400x2≤250

x1，x2≥0第5頁/共44頁§2.1LP問題的提出及其數(shù)學模型一、例示——問題提出例26目標函數(shù)：maxz=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250

x1，x2≥0滿足

約束條件：4.得到本問題的數(shù)學模型：第6頁/共44頁目標函數(shù)：maxz=50x1+100x2x7例2.1-2某廠生產(chǎn)兩種產(chǎn)品，下表給出了單位產(chǎn)品所需資源及單位產(chǎn)品利潤問：應(yīng)如何安排生產(chǎn)計劃，才能使總利潤最大？

解：1.決策變量：設(shè)產(chǎn)品I、II的產(chǎn)量分別為x1、x22.目標函數(shù)：設(shè)利潤為z，則有：

maxz=2x1+3x23.約束條件：

x1+2x2≤84x1≤16

4x2≤12

x1，x2≥0第7頁/共44頁例2.1-2某廠生產(chǎn)兩種產(chǎn)品，下表給問：應(yīng)如何安排生產(chǎn)計8例2.1-3某廠生產(chǎn)三種藥物，這些藥物可從四種不同的原料中提取。下表給出了單位原料可提取藥物的量（有效單位數(shù)）要求：生產(chǎn)A種藥物至少160單位；B種藥物恰好200單位，C種藥物不超過180單位，且使原料總成本最小。解：1.決策變量：設(shè)四種原料的使用量分別為：x1、x2、x3

、x42.目標函數(shù)：設(shè)總成本為z，則有：

minz=5x1+6x2+7x3+8x43.約束條件：

x1+2x2+x3+x4≥1602x1+4x3+2x4

＝1603x1

＋x2+x3+2x4

≤180

x1、x2

、x3

、x4≥0

藥物原料ABC單位成本（元／噸）甲1235乙2016丙1417丁1228第8頁/共44頁例2.1-3某廠生產(chǎn)三種藥物，這些藥物可從四種不同的原料9二、LP問題一般模型1.決策變量：X=(x1,x2,…..,xn)T2.目標函數(shù)：max(minz)=c1

x1+c2

x2+…….+cnxn3.約束條件：a11x1+a12

x2+……..+a1n

xn≤(=≥)b1

a21x1+a22

x2+……..+a2n

xn≤(=≥)b2

…………am1x1+am2

x2+……..+amnxn≤(=≥)bmx1,x2,……xn≥0第9頁/共44頁二、LP問題一般模型1.決策變量：X=(x1,x2,…10三、LP模型特點1、都用一組決策變量X=(x1,x2,…,xn)T表示某一方案，且決策變量取值非負；———滿足以上三個條件的數(shù)學模型稱為線性規(guī)劃數(shù)學模型或LP模型2、都有一個要達到的目標，并且目標要求可以表示成決策變量的線性函數(shù)；3、都有一組約束條件，這些約束條件可以用決策變量的線性等式或線性不等式來表示。第10頁/共44頁三、LP模型特點1、都用一組決策變量X=(x1,x2,11LP模型的其它表達形式①簡約形式②矩陣形式?jīng)Q策變量常數(shù)項系數(shù)矩陣價值系數(shù)其中：第11頁/共44頁LP模型的其它表達形式①簡約形式②矩陣形式?jīng)Q策變量常數(shù)項12四、線性規(guī)劃數(shù)學模型的建立（一）建模條件1優(yōu)化條件：問題所要達到的目標能用線型函數(shù)描述，且能夠用極值（max或min）來表示；2限定條件：達到目標受到一定的限制，且這些限制能夠用決策變量的線性等式或線性不等式表示；3選擇條件：有多種可選擇的方案供決策者選擇，以便找出最優(yōu)方案。第12頁/共44頁四、線性規(guī)劃數(shù)學模型的建立（一）建模條件1優(yōu)化條件：問題所13（二）LP建模步驟1確定決策變量并收集有關(guān)參數(shù)：即需要我們作出決策或選擇的量。一般情況下題目問什么，就把什么設(shè)置為決策變量。2找列出所有限定條件：即決策變量受到的所有的資源與需求等約束；3寫出目標函數(shù)：即問題所要達到的目標，并明確是max還是min。（三）建模案例例2.1-4某廠生產(chǎn)A、B兩種產(chǎn)品，有關(guān)參數(shù)資料如下表所示，問如何組織生產(chǎn)才能使效益最大：設(shè)：總利潤為Z；產(chǎn)品A、B產(chǎn)量為x1、x2，產(chǎn)品C的銷量為x3，報廢量為x4，則：

maxz=4x1+10x2+3x3－2x4

2x1+3x2≤123x1+4x2≤244x2-x3-x4=0x3≤5

x1、x2

、x3

、x4≥0第13頁/共44頁（二）LP建模步驟1確定決策變量并收集有關(guān)參數(shù)：即需要我們14§2.2線性規(guī)劃圖解法一、解題步驟4將最優(yōu)解代入目標函數(shù)，求出最優(yōu)值。1建立坐標系并在直角平面坐標系中畫出所有的約束等式，然后找出滿足所有約束條件的公共部分，稱為可行域，可行域中的點稱為可行解。2標出目標函數(shù)值改善的方向。3畫出目標函數(shù)等值線，若求最大（?。┲?，則令目標函數(shù)等值線沿目標函數(shù)值增加（或減少）的方向平行移動，找與可行域最后相交的點，該點就是最優(yōu)解。第14頁/共44頁§2.2線性規(guī)劃圖解法一、解題步驟4將最優(yōu)解代入目標函15用圖解法求解下列線性規(guī)劃問題（例1）

x1+2x2≤8①4x1≤16②

4x2≤12③

x1，x2≥0

maxz=2x1+3x2最優(yōu)解：X*=(2,4)T最優(yōu)值：Z*=14目標函數(shù)等值線Z=0x2x1①②③第15頁/共44頁用圖解法求解下列線性規(guī)劃問題（例1）x1+2x216線性規(guī)劃的圖解（例2）max z=x1+3x2 s.t. x1+x2≤6 -x1+2x2≤8 x1≥0,x2≥0可行域目標函數(shù)等值線最優(yōu)解64-860x1x2第16頁/共44頁線性規(guī)劃的圖解（例2）max z=x1+3x2 可行域目標17目標函數(shù)：分別取決策變量為坐標向量建立直角坐標系。在直角坐標系里，圖上任意一點的坐標代表了決策變量的一組值，每個約束條件都代表一個半平面。圖示如下：用圖解法求解下列線性規(guī)劃問題第17頁/共44頁目標函數(shù)：分別取決策變量為坐標向量建立直角坐標系。在直角坐標18x2x1X2≥0X2=0x2x1X1≥0X1=0100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖2-1第18頁/共44頁x2x1X2≥0X2=0x2x1X1≥0X1=010020019x1x2z=20000=50x1+100x2圖2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE

綜上得到最優(yōu)解：最優(yōu)目標值:第19頁/共44頁x1x2z=20000=50x1+100x2圖2-2z=27201、凸集若連接n維點集P中任意兩點x（1），x（2），其線段仍在P內(nèi)，則稱P為凸集。即：{x|x=x(1)+(1-)x(2)，0<<1,x(1)P,x(2)P}P,則稱P為凸集）2、極點若點x∈Ｐ,且x不是P中任何線段的內(nèi)點，則稱點x為凸集P的極點。顯然多邊形的頂點都是極點，四面體的頂點也都是極點，而圓周上、球面上的每一個點都是極點，其它點都不是極點。二、關(guān)于凸集、極點的概念第20頁/共44頁1、凸集若連接n維點集P中任意兩點x（1），x（2），21三、線性規(guī)劃解的性質(zhì)定理1

線性規(guī)劃的可行域R是一個凸集，且有有限個極點。定理2X是線性規(guī)劃可行域R頂點的充要條件是X線性規(guī)劃的基本可行解。定理3

若線性規(guī)劃有最優(yōu)解，則必有基本最優(yōu)解。定理4

若線性規(guī)劃在可行域的兩個頂點上達到最優(yōu)，則在兩個頂點的連線上也達到最優(yōu)。——線性規(guī)劃的每一個基本可行解對應(yīng)凸集的每一個頂點?！艟€性規(guī)劃有最優(yōu)解，則一定在凸集的某個（些）頂點上達到最優(yōu)?！艟€性規(guī)劃在兩個頂點以上達到最優(yōu),則一定有無窮多個最優(yōu)解?！顑?yōu)解一定是基本可行解，但基本可行解不一定是最優(yōu)解。第21頁/共44頁三、線性規(guī)劃解的性質(zhì)定理1線性規(guī)劃的可行域R是一個22四、線性規(guī)劃問題求解可能出現(xiàn)的情況x1x2z=20000=50x1+100x2圖2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE則可行域為空域，不存在滿足約束條件的解，當然也就不存在最優(yōu)解了。

4、無可行解。如果例3再增加一個約束條件3、無界解。即可行域延伸到無窮遠，目標函數(shù)值可以無窮大或無窮小。2、如果最優(yōu)解出現(xiàn)在兩個極點上，則會有無窮多個最優(yōu)解。1、如果LP有最優(yōu)解，則一定有一個可行域的極點對應(yīng)這個最優(yōu)解；

第22頁/共44頁四、線性規(guī)劃問題求解可能出現(xiàn)的情況x1x2z=20000=523五、LP解的有關(guān)概念及其關(guān)系1可行解（feasiblesolution）：滿足線性規(guī)劃約束條件的解稱為可行解。（一）有關(guān)概念2最優(yōu)解（optimalsolution）：使線性規(guī)劃目標函數(shù)達到最優(yōu)的可行解稱為最優(yōu)解。3基本解（basicsolution）：以線性規(guī)劃約束等式的系數(shù)矩陣A中任意m行m列組成的m×m滿秩子矩陣為基矩陣，與基矩陣相對應(yīng)的變量稱為基變量（basicvariable），其余變量稱為非基變量，若令非基變量為零，則可求得基變量的解（值），這個解稱為基本解。

4基本可行解（basicfeasiblesolution）：滿足非負約束的基本解稱為基本可行解。若約束等式中有n個變量，m個約束，則基本解的個數(shù)≤第23頁/共44頁五、LP解的有關(guān)概念及其關(guān)系1可行解（feasible24令非基變量x1＝0，x2

＝0則得：X＝(0,0,3,1)T基本解當基變量為x2、x3，則非基變量為x1、x4令非基變量x1＝0，x4

＝0則得：X＝(0,－1,5,0)T基本解／基本可行解？／是基本可行解？x1

＋2x2

＋x3

＝32x1

－x2

＋x4＝1x1,x2,x3,x4≥0解：系數(shù)矩陣為：設(shè)基變量為x3、x4，則非基變量為x1、x23）X＝(1/2,1/2,3/2,1/2)T／不是基本解可行解／是基本可行解？例討論下述約束方程的解第24頁/共44頁令非基變量x1＝0，x2＝0則得：X＝(0,0,251可行解與最優(yōu)解：最優(yōu)解一定是可行解，但可行解不一定是最優(yōu)解。（二）線性規(guī)劃解之間的關(guān)系基本解不一定是可行解，可行解也不一定是基本解。2可行解與基本解：3可行解與基本可行解：基本可行解一定是可行解，但可行解不一定是基本解。基本可行解一定是基本解，但基本解不一定是基本可行解。4基本解與基本可行解：5最優(yōu)解與基本解：最優(yōu)解不一定是基本解，基本解也不一定是最優(yōu)解。問題：最優(yōu)解與基本可行解？非可行解可行解基本可行解基本解第25頁/共44頁1可行解與最優(yōu)解：最優(yōu)解一定是可行解，但可行解不一定是最優(yōu)26六、線性規(guī)劃模型的標準形式及其標準化（一）線性規(guī)劃模型標準形式特點1．目標最大化；2．約束為等式；

3．決策變量均非負；4．右端項非負。特點Maxz=c1x1+c2x2

+…+cnxna11x1+a12x2+

…

+a1nxn

=b1a21x1+a22x2+…

+a2nxn

=b2

...am1x1+am2x2+…+amnxn

=bm

x1，x2，…

，xn≥0s.t第26頁/共44頁六、線性規(guī)劃模型的標準形式及其標準化（一）線性規(guī)劃模型標準形27

如果目標函數(shù)為Min該極小化問題與下面的極大化問題有相同的最優(yōu)解，但必須注意，盡管以上兩個問題的最優(yōu)解相同，但它們最優(yōu)解的目標函數(shù)值卻相差一個符號，即：

（二）線性規(guī)劃模型標準化問題1、極小化目標函數(shù)的問題：則令：z

＝-f

，Minf

＝—Maxz第27頁/共44頁該極小化問題與下面的極大化問題有相同的最優(yōu)解，但必須注282、約束條件不是等式的問題：

時，可以引進一個新的變量，使它等于約束右邊與左邊之差（2）當約束條件為類似地令則有：則有：（1）當約束條件為第28頁/共44頁2、約束條件不是等式的問題：時，可以引進一個新的變量，使293.右端項有負值的問題：

則把該等式約束兩端同時乘以-1，得到：

為了使約束方程由不等式成為等式而引進的變量,當不等式為“小于等于”時稱引進的變量為“松弛變量”；當不等式為“大于等于”時稱為“剩余變量”。如果原問題中有若干個非等式約束，則將其轉(zhuǎn)化為標準形式時，必須對各個約束引進不同的松弛變量或剩余變量。

在標準形式中，要求右端項必須每一個分量非負。當某一個右端項系數(shù)為負時，如

第29頁/共44頁3.右端項有負值的問題：則把該等式約束兩端同時乘以-304.變量無符號限制的問題

在標準形式中，必須每一個變量均有非負約束。當某一個變量xj沒有非負約束時，可以令xj=xj’-xj”

其中xj’≥0，xj”≥0即用兩個非負變量之差來表示一個無符號限制的變量，當然xj的符號取決于xj’和xj”的大小?？傊ㄟ^上述問題的處理，線性規(guī)劃模型的一般形式均可化為標準形式。第30頁/共44頁4.變量無符號限制的問題第30頁/共44頁31標準化例題1一般形式標準形式第31頁/共44頁標準化例題1一般形式標準形式第31頁/共44頁32標準化例題2第32頁/共44頁標準化例題2第32頁/共44頁33§2.3靈敏度分析

靈敏度分析是建立數(shù)學模型和求得最優(yōu)解后，研究線性規(guī)劃的一個或多個參數(shù)()變化時，對最優(yōu)解產(chǎn)生的影響，或者這些參數(shù)在一個多大范圍內(nèi)變化時，原LP問題的最優(yōu)解不變的問題。

目標函數(shù)中的系數(shù)的變化只影響目標函數(shù)等值線的斜率，不影響可行域。所謂C的靈敏度分析是指，研究在目標函數(shù)中其他的系數(shù)不變，只有一個系數(shù)在保持最優(yōu)解不變時該系數(shù)的取值范圍。1．目標函數(shù)中的系數(shù)“C”的靈敏度分析第33頁/共44頁§2.3靈敏度分析靈敏度分析是建立數(shù)學模型和求得最優(yōu)解34一般情況：可將其寫成：目標函數(shù)等值線的斜率為：有：可使原最優(yōu)解仍是最優(yōu)解。先假設(shè)產(chǎn)品乙的利潤100元不變，即：代入（*）并整理得：考慮例1目標函數(shù)為：x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖2-1要使最優(yōu)解不變，其變化必然在構(gòu)成極點的相交直線的斜率之間。對C1進行靈敏度分析maxz=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1，x2≥0滿足第34頁/共44頁一般情況：可將其寫成：目標函數(shù)等值線的斜率為：有：可使原最35同樣：假設(shè)C1=50不變時，代入：有：-1≤-（50/C2）≤0整理后得：50≤C2≤+∞即當50≤C2≤+∞時原最優(yōu)解不變。第35頁/共44頁同樣：假設(shè)C1=50不變時，代入：有：-1≤-（50/C362．約束條件中右邊系數(shù)的靈敏度分析

當約束條件中右邊系數(shù)變化時，線性規(guī)劃的可行域發(fā)生變化，可能引起的最優(yōu)解的變化，進而了解當其他約束不變時，某一約束條件的右端項每變化一個單位，使目標函數(shù)值的改變量。由講義例1可知：（1）假設(shè)設(shè)備臺時增加10個臺時，即變?yōu)?10臺時，這時可行域擴大，但最優(yōu)解所在的基點不變，得最優(yōu)解為：X1=60，X2=250x1x2x2=0x1=0x2=250x1+x2=3102x1+x2=400圖2-1第36頁/共44頁2．約束條件中右邊系數(shù)的靈敏度分析由講義例1可知：x37（2）假設(shè)原料A增加10千克時，即變化為410，這時可行域擴大，但最優(yōu)解仍為①和③約束方程的交點。此變化對總利潤無影響，因此該約束條件的對偶價格為0。由于原最優(yōu)解沒有把原料A用盡，有50千克的剩余，因此增加10千克值增加了庫存，而不會增加利潤。

這時，即變化后的總利潤—變化前的總利潤=增加的利潤

(50×60+100×250)—(50×50+100×250)=500元，即：每增加一個臺時的利潤為：500/10=50元說明在一定范圍內(nèi)每增加（減少）1個臺時的設(shè)備能力就可增加（減少）50元利潤，稱為該約束條件的對偶價格。圖2-1x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=410第37頁/共44頁（2）假設(shè)原料A增加10千克時，即變化為410，這時38

在一定范圍內(nèi)，當約束條件右邊常數(shù)增加1個單位時（1）若約束條件的對偶價格大于0，則其最優(yōu)目標函數(shù)值得到改善（變好）；（2）若約束條件的對偶價格小于0，則其最優(yōu)目標函數(shù)值受到影響（變壞）；（3）若約束條件的對偶價格等于0，則最優(yōu)目標函數(shù)值不變。作業(yè)布置：1、P24第3（2，3），第4題2、P25第6、7題第38頁/共44頁在一定范圍內(nèi)，當約束條件右邊常數(shù)增加1個單位時第38頁/共39原問題LP模型：Maxz=50x1+100x2s.t.x1+x2≤300 2x1+x2≤400 x2≤250 x1,x2≥02.4線性規(guī)劃的對偶問題最優(yōu)解為：x1=50x2=250

；maxZ=27500對偶問題：不妨提出這樣的問題，如果該廠把設(shè)備（工時）和A、B原料租賃和轉(zhuǎn)讓出去，又要不比自己生產(chǎn)賺的少，該廠如何收取租金和轉(zhuǎn)讓費？或者說設(shè)備租賃至少多少錢一個工時，原料A、B應(yīng)收多少錢一公斤？原問題：例2.1某廠在計劃期內(nèi)安排生產(chǎn)兩種產(chǎn)品，生產(chǎn)所需資源限制及單位產(chǎn)品原料消耗由下表給給出甲乙資源限制設(shè)備11300臺時原料A21400kg原料B01250kg利潤50100第39頁/共44頁原問題LP模型：2.4線性規(guī)劃的對偶問題最優(yōu)解為：x1=5040定價的原則是：既要能夠轉(zhuǎn)讓出去，又不比自己生產(chǎn)賺的總利潤少。不妨設(shè)：y1

，y2

，y3

分別為每個設(shè)備工時出租和每公斤原料A、B的轉(zhuǎn)讓純利。對偶問題

：Minf=300y1+400y2+250y3s.t.y1+2y2≥50 y1+y2+y3≥

100 y1,y2,y3≥0甲乙資源限制設(shè)備11300臺時原料A21400kg原料B01250kg利潤501001、對偶問題數(shù)學模型的建立目標函數(shù)：轉(zhuǎn)讓總利潤為各種資源租賃和轉(zhuǎn)讓利潤之和——f.

約束條件1：用于生產(chǎn)甲產(chǎn)品的原料利潤之和不小于自己生產(chǎn)約束條件2：用于生產(chǎn)乙產(chǎn)品的原料利潤之和也不小于自己生產(chǎn)即f=300y1+400y2+250y3——min第40頁/共44頁定價的原則是：既要能夠轉(zhuǎn)讓出去，又不比自己生產(chǎn)賺的總利潤少。41

對偶問題最優(yōu)解：y1=50y2=0y3=50minf=27500（P114）即兩種決策結(jié)果相同，這樣一對互為對偶的LP問題無論是外在還是內(nèi)在都有密切的關(guān)系。見Ｐ113。

第41頁/共44頁對偶問題最優(yōu)解：y1=50y2=042

如果我們把求目標函數(shù)最大值的線性規(guī)劃問題看成原問題，則求目標函數(shù)最小大值的線性規(guī)劃問題看成對偶問題。這兩個問題在數(shù)學模型上有以下關(guān)系。A=則2、對偶問題與原問題數(shù)學模型的關(guān)系4對偶問題的約束條件的系數(shù)矩陣A是原問題約束矩陣的轉(zhuǎn)置。設(shè):3原問題的約束條件的右邊常數(shù)項為對偶問題的目標函數(shù)中的變量的系數(shù)。并且原問題的第i個約束條件的右邊常數(shù)項就等于對偶問題的目標函數(shù)中的第i個變量的系數(shù)。2原問題的目標函數(shù)中的變量系數(shù)為對偶問題中的約束條件的右邊常數(shù)項，并且原問題的目標函數(shù)中的第i個變量的系數(shù)就等于對偶問題中的第i個約束條件的右邊常數(shù)項。1求目標函數(shù)最大值的線性規(guī)劃問題中有n個變量m個約束條件，它的約束條件都是小于等于不等式。而其對偶則是求目標函數(shù)為最小值的線性規(guī)劃問題，有m個變量n個約束條件，其約束條件都為大于等于不等式。第42頁/共44頁如果我們把求目標函數(shù)最大值的線性規(guī)劃問題看成原問題，則求目43其中A是矩陣m*n，該問題有m個約束條件n個變量

對偶問題模型：x=b=c=y=：A的轉(zhuǎn)置：b的轉(zhuǎn)置,：c的轉(zhuǎn)置,原問題模型第43頁/共44頁其中A是矩陣m*n，該問題有m個約束條件n個變量對偶問題44線性規(guī)劃圖解法線性規(guī)劃圖解法451832和1911年法國數(shù)學家J.B.J.傅里葉和C.瓦萊－普森分都分別獨立地提出線性規(guī)劃的想法，但未引起注意。

1939年，前蘇聯(lián)數(shù)學家康托洛維奇用線性規(guī)劃模型研究提高組織和生產(chǎn)效率問題

1947年，Dantzig提出求解線性規(guī)劃的單純形法

1950-1956年，主要研究線性規(guī)劃的對偶理論1951年美國經(jīng)濟學家T.C.庫普曼斯把線性規(guī)劃應(yīng)用到經(jīng)濟領(lǐng)域，為此與康托羅維奇一起獲1975年諾貝爾經(jīng)濟學獎。

1958年，發(fā)表整數(shù)規(guī)劃的割平面法

1960年，Dantzig和Wolfe研究成功分解算法，奠定了大規(guī)模線性規(guī)劃問題理論和算法的基礎(chǔ)。一、線性規(guī)劃發(fā)展概況第1頁/共44頁1832和1911年法國數(shù)學家J.B.J.傅里葉46線性規(guī)劃的研究成果還直接推動了其他數(shù)學規(guī)劃問題包括整數(shù)規(guī)劃、隨機規(guī)劃和非線性規(guī)劃的算法研究。由于數(shù)字電子計算機的發(fā)展，出現(xiàn)了許多線性規(guī)劃軟件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解幾千個變量的線性規(guī)劃問題。

1979年，Khachiyan，1984年，Karmarkaa研究成功線性規(guī)劃的多項式算法。用卡馬卡方法求解線性規(guī)劃問題在變量個數(shù)為5000時只要單純形法所用時間的1/50。

第2頁/共44頁線性規(guī)劃的研究成果還直接推動了其他數(shù)學規(guī)劃問題包括整數(shù)規(guī)劃、47二、線性規(guī)劃研究解決的主要問題

實際上，上述兩類問題是一個問題的兩個不同的方面，都是求問題的最優(yōu)解（max或min）。

另一類是當一項任務(wù)確定以后，研究如何統(tǒng)籌安排，才能使完成任務(wù)所耗費的資源量為最少。一類是已有一定數(shù)量的資源（人力、物質(zhì)、時間等），研究如何充分合理地使用它們，才能使完成的任務(wù)量為最大。線性規(guī)劃在工商管理中應(yīng)用有著廣泛的用處，可以用來解決諸如：人力資源分配問題、生產(chǎn)計劃問題、下料配料、投資問題（見第4章）以及運輸問題（第7章）等。實際上遠不止這些具體問題。但從一般意義上解決得問題有兩類：第3頁/共44頁二、線性規(guī)劃研究解決的主要問題實際上，上述兩類問題是一48三、LP解決問題的一般思路5、模型求解與解的調(diào)適。（獲得最優(yōu)方案——一組決策變量的取值）。1、對問題進行系統(tǒng)分析,搞清決策什么和決策目標是什么？2、明確是哪些因素（人為可控的，決策變量）影響決策目標（大小變化），確定決策變量對目標（函數(shù)）影響系數(shù)，且與目標函數(shù)是否呈線形關(guān)系。3、哪些資源約束（或需求約束）條件制約著目標（最大或最?。?。決策變量對這些資源（或需求）的單位消耗（單位產(chǎn)出）是多少？，即要獲得資源總量和投入產(chǎn)出系數(shù)。4、建立線形規(guī)劃數(shù)學模型。6、方案實施與調(diào)整。第4頁/共44頁三、LP解決問題的一般思路5、模型求解與解的調(diào)適。（獲得最優(yōu)49§2.1LP問題的提出及其數(shù)學模型一、例示——問題提出例2.1-1某廠在計劃期內(nèi)安排生產(chǎn)兩種產(chǎn)品，生產(chǎn)所需資源限制及單位產(chǎn)品原料消耗由下表給給出

利潤50100問：應(yīng)如何安排生產(chǎn)計劃才能使總利潤最大？

甲乙資源限制設(shè)備11300臺時原料A21400kg原料B01250kg解：確定決策變量：設(shè)產(chǎn)品甲乙的產(chǎn)量分別為：x1、x22.建立目標函數(shù)：設(shè)總利潤為z，本例是：

maxz=50x1+100x23.考慮約束條件：x1+x2≤3002x1+x2≤400x2≤250

x1，x2≥0第5頁/共44頁§2.1LP問題的提出及其數(shù)學模型一、例示——問題提出例250目標函數(shù)：maxz=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250

x1，x2≥0滿足

約束條件：4.得到本問題的數(shù)學模型：第6頁/共44頁目標函數(shù)：maxz=50x1+100x2x51例2.1-2某廠生產(chǎn)兩種產(chǎn)品，下表給出了單位產(chǎn)品所需資源及單位產(chǎn)品利潤問：應(yīng)如何安排生產(chǎn)計劃，才能使總利潤最大？

解：1.決策變量：設(shè)產(chǎn)品I、II的產(chǎn)量分別為x1、x22.目標函數(shù)：設(shè)利潤為z，則有：

maxz=2x1+3x23.約束條件：

x1+2x2≤84x1≤16

4x2≤12

x1，x2≥0第7頁/共44頁例2.1-2某廠生產(chǎn)兩種產(chǎn)品，下表給問：應(yīng)如何安排生產(chǎn)計52例2.1-3某廠生產(chǎn)三種藥物，這些藥物可從四種不同的原料中提取。下表給出了單位原料可提取藥物的量（有效單位數(shù)）要求：生產(chǎn)A種藥物至少160單位；B種藥物恰好200單位，C種藥物不超過180單位，且使原料總成本最小。解：1.決策變量：設(shè)四種原料的使用量分別為：x1、x2、x3

、x42.目標函數(shù)：設(shè)總成本為z，則有：

minz=5x1+6x2+7x3+8x43.約束條件：

x1+2x2+x3+x4≥1602x1+4x3+2x4

＝1603x1

＋x2+x3+2x4

≤180

x1、x2

、x3

、x4≥0

藥物原料ABC單位成本（元／噸）甲1235乙2016丙1417丁1228第8頁/共44頁例2.1-3某廠生產(chǎn)三種藥物，這些藥物可從四種不同的原料53二、LP問題一般模型1.決策變量：X=(x1,x2,…..,xn)T2.目標函數(shù)：max(minz)=c1

x1+c2

x2+…….+cnxn3.約束條件：a11x1+a12

x2+……..+a1n

xn≤(=≥)b1

a21x1+a22

x2+……..+a2n

xn≤(=≥)b2

…………am1x1+am2

x2+……..+amnxn≤(=≥)bmx1,x2,……xn≥0第9頁/共44頁二、LP問題一般模型1.決策變量：X=(x1,x2,…54三、LP模型特點1、都用一組決策變量X=(x1,x2,…,xn)T表示某一方案，且決策變量取值非負；———滿足以上三個條件的數(shù)學模型稱為線性規(guī)劃數(shù)學模型或LP模型2、都有一個要達到的目標，并且目標要求可以表示成決策變量的線性函數(shù)；3、都有一組約束條件，這些約束條件可以用決策變量的線性等式或線性不等式來表示。第10頁/共44頁三、LP模型特點1、都用一組決策變量X=(x1,x2,55LP模型的其它表達形式①簡約形式②矩陣形式?jīng)Q策變量常數(shù)項系數(shù)矩陣價值系數(shù)其中：第11頁/共44頁LP模型的其它表達形式①簡約形式②矩陣形式?jīng)Q策變量常數(shù)項56四、線性規(guī)劃數(shù)學模型的建立（一）建模條件1優(yōu)化條件：問題所要達到的目標能用線型函數(shù)描述，且能夠用極值（max或min）來表示；2限定條件：達到目標受到一定的限制，且這些限制能夠用決策變量的線性等式或線性不等式表示；3選擇條件：有多種可選擇的方案供決策者選擇，以便找出最優(yōu)方案。第12頁/共44頁四、線性規(guī)劃數(shù)學模型的建立（一）建模條件1優(yōu)化條件：問題所57（二）LP建模步驟1確定決策變量并收集有關(guān)參數(shù)：即需要我們作出決策或選擇的量。一般情況下題目問什么，就把什么設(shè)置為決策變量。2找列出所有限定條件：即決策變量受到的所有的資源與需求等約束；3寫出目標函數(shù)：即問題所要達到的目標，并明確是max還是min。（三）建模案例例2.1-4某廠生產(chǎn)A、B兩種產(chǎn)品，有關(guān)參數(shù)資料如下表所示，問如何組織生產(chǎn)才能使效益最大：設(shè)：總利潤為Z；產(chǎn)品A、B產(chǎn)量為x1、x2，產(chǎn)品C的銷量為x3，報廢量為x4，則：

maxz=4x1+10x2+3x3－2x4

2x1+3x2≤123x1+4x2≤244x2-x3-x4=0x3≤5

x1、x2

、x3

、x4≥0第13頁/共44頁（二）LP建模步驟1確定決策變量并收集有關(guān)參數(shù)：即需要我們58§2.2線性規(guī)劃圖解法一、解題步驟4將最優(yōu)解代入目標函數(shù)，求出最優(yōu)值。1建立坐標系并在直角平面坐標系中畫出所有的約束等式，然后找出滿足所有約束條件的公共部分，稱為可行域，可行域中的點稱為可行解。2標出目標函數(shù)值改善的方向。3畫出目標函數(shù)等值線，若求最大（?。┲?，則令目標函數(shù)等值線沿目標函數(shù)值增加（或減少）的方向平行移動，找與可行域最后相交的點，該點就是最優(yōu)解。第14頁/共44頁§2.2線性規(guī)劃圖解法一、解題步驟4將最優(yōu)解代入目標函59用圖解法求解下列線性規(guī)劃問題（例1）

x1+2x2≤8①4x1≤16②

4x2≤12③

x1，x2≥0

maxz=2x1+3x2最優(yōu)解：X*=(2,4)T最優(yōu)值：Z*=14目標函數(shù)等值線Z=0x2x1①②③第15頁/共44頁用圖解法求解下列線性規(guī)劃問題（例1）x1+2x260線性規(guī)劃的圖解（例2）max z=x1+3x2 s.t. x1+x2≤6 -x1+2x2≤8 x1≥0,x2≥0可行域目標函數(shù)等值線最優(yōu)解64-860x1x2第16頁/共44頁線性規(guī)劃的圖解（例2）max z=x1+3x2 可行域目標61目標函數(shù)：分別取決策變量為坐標向量建立直角坐標系。在直角坐標系里，圖上任意一點的坐標代表了決策變量的一組值，每個約束條件都代表一個半平面。圖示如下：用圖解法求解下列線性規(guī)劃問題第17頁/共44頁目標函數(shù)：分別取決策變量為坐標向量建立直角坐標系。在直角坐標62x2x1X2≥0X2=0x2x1X1≥0X1=0100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖2-1第18頁/共44頁x2x1X2≥0X2=0x2x1X1≥0X1=010020063x1x2z=20000=50x1+100x2圖2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE

綜上得到最優(yōu)解：最優(yōu)目標值:第19頁/共44頁x1x2z=20000=50x1+100x2圖2-2z=27641、凸集若連接n維點集P中任意兩點x（1），x（2），其線段仍在P內(nèi)，則稱P為凸集。即：{x|x=x(1)+(1-)x(2)，0<<1,x(1)P,x(2)P}P,則稱P為凸集）2、極點若點x∈Ｐ,且x不是P中任何線段的內(nèi)點，則稱點x為凸集P的極點。顯然多邊形的頂點都是極點，四面體的頂點也都是極點，而圓周上、球面上的每一個點都是極點，其它點都不是極點。二、關(guān)于凸集、極點的概念第20頁/共44頁1、凸集若連接n維點集P中任意兩點x（1），x（2），65三、線性規(guī)劃解的性質(zhì)定理1

線性規(guī)劃的可行域R是一個凸集，且有有限個極點。定理2X是線性規(guī)劃可行域R頂點的充要條件是X線性規(guī)劃的基本可行解。定理3

若線性規(guī)劃有最優(yōu)解，則必有基本最優(yōu)解。定理4

若線性規(guī)劃在可行域的兩個頂點上達到最優(yōu)，則在兩個頂點的連線上也達到最優(yōu)。——線性規(guī)劃的每一個基本可行解對應(yīng)凸集的每一個頂點。——若線性規(guī)劃有最優(yōu)解，則一定在凸集的某個（些）頂點上達到最優(yōu)。——若線性規(guī)劃在兩個頂點以上達到最優(yōu),則一定有無窮多個最優(yōu)解?！顑?yōu)解一定是基本可行解，但基本可行解不一定是最優(yōu)解。第21頁/共44頁三、線性規(guī)劃解的性質(zhì)定理1線性規(guī)劃的可行域R是一個66四、線性規(guī)劃問題求解可能出現(xiàn)的情況x1x2z=20000=50x1+100x2圖2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE則可行域為空域，不存在滿足約束條件的解，當然也就不存在最優(yōu)解了。

4、無可行解。如果例3再增加一個約束條件3、無界解。即可行域延伸到無窮遠，目標函數(shù)值可以無窮大或無窮小。2、如果最優(yōu)解出現(xiàn)在兩個極點上，則會有無窮多個最優(yōu)解。1、如果LP有最優(yōu)解，則一定有一個可行域的極點對應(yīng)這個最優(yōu)解；

第22頁/共44頁四、線性規(guī)劃問題求解可能出現(xiàn)的情況x1x2z=20000=567五、LP解的有關(guān)概念及其關(guān)系1可行解（feasiblesolution）：滿足線性規(guī)劃約束條件的解稱為可行解。（一）有關(guān)概念2最優(yōu)解（optimalsolution）：使線性規(guī)劃目標函數(shù)達到最優(yōu)的可行解稱為最優(yōu)解。3基本解（basicsolution）：以線性規(guī)劃約束等式的系數(shù)矩陣A中任意m行m列組成的m×m滿秩子矩陣為基矩陣，與基矩陣相對應(yīng)的變量稱為基變量（basicvariable），其余變量稱為非基變量，若令非基變量為零，則可求得基變量的解（值），這個解稱為基本解。

4基本可行解（basicfeasiblesolution）：滿足非負約束的基本解稱為基本可行解。若約束等式中有n個變量，m個約束，則基本解的個數(shù)≤第23頁/共44頁五、LP解的有關(guān)概念及其關(guān)系1可行解（feasible68令非基變量x1＝0，x2

＝0則得：X＝(0,0,3,1)T基本解當基變量為x2、x3，則非基變量為x1、x4令非基變量x1＝0，x4

＝0則得：X＝(0,－1,5,0)T基本解／基本可行解？／是基本可行解？x1

＋2x2

＋x3

＝32x1

－x2

＋x4＝1x1,x2,x3,x4≥0解：系數(shù)矩陣為：設(shè)基變量為x3、x4，則非基變量為x1、x23）X＝(1/2,1/2,3/2,1/2)T／不是基本解可行解／是基本可行解？例討論下述約束方程的解第24頁/共44頁令非基變量x1＝0，x2＝0則得：X＝(0,0,691可行解與最優(yōu)解：最優(yōu)解一定是可行解，但可行解不一定是最優(yōu)解。（二）線性規(guī)劃解之間的關(guān)系基本解不一定是可行解，可行解也不一定是基本解。2可行解與基本解：3可行解與基本可行解：基本可行解一定是可行解，但可行解不一定是基本解。基本可行解一定是基本解，但基本解不一定是基本可行解。4基本解與基本可行解：5最優(yōu)解與基本解：最優(yōu)解不一定是基本解，基本解也不一定是最優(yōu)解。問題：最優(yōu)解與基本可行解？非可行解可行解基本可行解基本解第25頁/共44頁1可行解與最優(yōu)解：最優(yōu)解一定是可行解，但可行解不一定是最優(yōu)70六、線性規(guī)劃模型的標準形式及其標準化（一）線性規(guī)劃模型標準形式特點1．目標最大化；2．約束為等式；

3．決策變量均非負；4．右端項非負。特點Maxz=c1x1+c2x2

+…+cnxna11x1+a12x2+

…

+a1nxn

=b1a21x1+a22x2+…

+a2nxn

=b2

...am1x1+am2x2+…+amnxn

=bm

x1，x2，…

，xn≥0s.t第26頁/共44頁六、線性規(guī)劃模型的標準形式及其標準化（一）線性規(guī)劃模型標準形71

如果目標函數(shù)為Min該極小化問題與下面的極大化問題有相同的最優(yōu)解，但必須注意，盡管以上兩個問題的最優(yōu)解相同，但它們最優(yōu)解的目標函數(shù)值卻相差一個符號，即：

（二）線性規(guī)劃模型標準化問題1、極小化目標函數(shù)的問題：則令：z

＝-f

，Minf

＝—Maxz第27頁/共44頁該極小化問題與下面的極大化問題有相同的最優(yōu)解，但必須注722、約束條件不是等式的問題：

時，可以引進一個新的變量，使它等于約束右邊與左邊之差（2）當約束條件為類似地令則有：則有：（1）當約束條件為第28頁/共44頁2、約束條件不是等式的問題：時，可以引進一個新的變量，使733.右端項有負值的問題：

則把該等式約束兩端同時乘以-1，得到：

為了使約束方程由不等式成為等式而引進的變量,當不等式為“小于等于”時稱引進的變量為“松弛變量”；當不等式為“大于等于”時稱為“剩余變量”。如果原問題中有若干個非等式約束，則將其轉(zhuǎn)化為標準形式時，必須對各個約束引進不同的松弛變量或剩余變量。

在標準形式中，要求右端項必須每一個分量非負。當某一個右端項系數(shù)為負時，如

第29頁/共44頁3.右端項有負值的問題：則把該等式約束兩端同時乘以-744.變量無符號限制的問題

在標準形式中，必須每一個變量均有非負約束。當某一個變量xj沒有非負約束時，可以令xj=xj’-xj”

其中xj’≥0，xj”≥0即用兩個非負變量之差來表示一個無符號限制的變量，當然xj的符號取決于xj’和xj”的大小?？傊ㄟ^上述問題的處理，線性規(guī)劃模型的一般形式均可化為標準形式。第30頁/共44頁4.變量無符號限制的問題第30頁/共44頁75標準化例題1一般形式標準形式第31頁/共44頁標準化例題1一般形式標準形式第31頁/共44頁76標準化例題2第32頁/共44頁標準化例題2第32頁/共44頁77§2.3靈敏度分析

靈敏度分析是建立數(shù)學模型和求得最優(yōu)解后，研究線性規(guī)劃的一個或多個參數(shù)()變化時，對最優(yōu)解產(chǎn)生的影響，或者這些參數(shù)在一個多大范圍內(nèi)變化時，原LP問題的最優(yōu)解不變的問題。

目標函數(shù)中的系數(shù)的變化只影響目標函數(shù)等值線的斜率，不影響可行域。所謂C的靈敏度分析是指，研究在目標函數(shù)中其他的系數(shù)不變，只有一個系數(shù)在保持最優(yōu)解不變時該系數(shù)的取值范圍。1．目標函數(shù)中的系數(shù)“C”的靈敏度分析第33頁/共44頁§2.3靈敏度分析靈敏度分析是建立數(shù)學模型和求得最優(yōu)解78一般情況：可將其寫成：目標函數(shù)等值線的斜率為：有：可使原最優(yōu)解仍是最優(yōu)解。先假設(shè)產(chǎn)品乙的利潤100元不變，即：代入（*）并整理得：考慮例1目標函數(shù)為：x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖2-1要使最優(yōu)解不變，其變化必然在構(gòu)成極點的相交直線的斜率之間。對C1進行靈敏度分析maxz=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1，x2≥0滿足第34頁/共44頁一般情況：可將其寫成：目標函數(shù)等值線的斜率為：有：可使原最79同樣：假設(shè)C1=50不變時，代入：有：-1≤-（50/C2）≤0整理后得：50≤C2≤+∞即當50≤C2≤+∞時原最優(yōu)解不變。第35頁/共44頁同樣：假設(shè)C1=50不變時，代入：有：-1≤-（50/C802．約束條件中右邊系數(shù)的靈敏度分析

當約束條件中右邊系數(shù)變化時，線性規(guī)劃的可行域發(fā)生變化，可能引起的最優(yōu)解的變化，進而了解當其他約束不變時，某一約束條件的右端項每變化一個單位，使目標函數(shù)值的改變量。由講義例1可知：（1）假設(shè)設(shè)備臺時增加10個臺時，即變?yōu)?10