2線(xiàn)性規(guī)劃圖解法

§2.0線(xiàn)性規(guī)劃簡(jiǎn)介第二章線(xiàn)性規(guī)劃及其圖解法（LinearProgramming，簡(jiǎn)稱(chēng)LP）本章結(jié)合了第五章的一些概念

線(xiàn)性規(guī)劃是運(yùn)籌學(xué)中研究較早、應(yīng)用廣泛、發(fā)展較快、方法較成熟的一個(gè)重要分支,是輔助人們進(jìn)行科學(xué)管理的一種數(shù)學(xué)方法。是研究線(xiàn)性約束條件下線(xiàn)性目標(biāo)函數(shù)的極值問(wèn)題的數(shù)學(xué)理論和方法，英文縮寫(xiě)LP。

LP是運(yùn)籌學(xué)的一個(gè)重要分支，廣泛應(yīng)用于軍事作戰(zhàn)、經(jīng)濟(jì)分析、經(jīng)營(yíng)管理和工程技術(shù)等方面。為合理地利用有限的人力、物力、財(cái)力等資源作出的最優(yōu)決策，提供科學(xué)的依據(jù)。

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

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

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

1950-1956年，主要研究線(xiàn)性規(guī)劃的對(duì)偶理論

1951年美國(guó)經(jīng)濟(jì)學(xué)家T.C.庫(kù)普曼斯把線(xiàn)性規(guī)劃應(yīng)用到經(jīng)濟(jì)領(lǐng)域，為此與康托羅維奇一起獲1975年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。

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

1960年，Dantzig和Wolfe研究成功分解算法，奠定了大規(guī)模線(xiàn)性規(guī)劃問(wèn)題理論和算法的基礎(chǔ)。一、線(xiàn)性規(guī)劃發(fā)展概況線(xiàn)性規(guī)劃的研究成果還直接推動(dòng)了其他數(shù)學(xué)規(guī)劃問(wèn)題包括整數(shù)規(guī)劃、隨機(jī)規(guī)劃和非線(xiàn)性規(guī)劃的算法研究。由于數(shù)字電子計(jì)算機(jī)的發(fā)展，出現(xiàn)了許多線(xiàn)性規(guī)劃軟件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解幾千個(gè)變量的線(xiàn)性規(guī)劃問(wèn)題。

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

二、線(xiàn)性規(guī)劃研究解決的主要問(wèn)題

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

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

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

甲乙資源限制設(shè)備11300臺(tái)時(shí)原料A21400kg原料B01250kg解：確定決策變量：設(shè)產(chǎn)品甲乙的產(chǎn)量分別為

：

x1、x22.建立目標(biāo)函數(shù)：設(shè)總利潤(rùn)為z，本例是：

maxz=50x1+100x23.考慮約束條件：

x1+x2≤3002x1+x2≤400x2≤250

x1，x2≥0目標(biāo)函數(shù)：maxz=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250

x1，x2≥0滿(mǎn)足

約束條件：4.得到本問(wèn)題的數(shù)學(xué)模型：例2.1-2某廠生產(chǎn)兩種產(chǎn)品，下表給出了單位產(chǎn)品所需資源及單位產(chǎn)品利潤(rùn)問(wèn)：應(yīng)如何安排生產(chǎn)計(jì)劃，才能使總利潤(rùn)最大？

解：1.決策變量：設(shè)產(chǎn)品I、II的產(chǎn)量分別為

x1、x22.目標(biāo)函數(shù)：設(shè)利潤(rùn)為z，則有：

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

x1+2x2≤84x1≤16

4x2≤12

x1，x2≥0例2.1-3某廠生產(chǎn)三種藥物，這些藥物可從四種不同的原料中提取。下表給出了單位原料可提取藥物的量（有效單位數(shù)）要求：生產(chǎn)A種藥物至少160單位；B種藥物恰好200單位，C種藥物不超過(guò)180單位，且使原料總成本最小。解：1.決策變量：設(shè)四種原料的使用量分別為：

x1、x2、x3

、x42.目標(biāo)函數(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二、LP問(wèn)題一般模型1.決策變量：X=(x1,x2,…..,xn)T2.目標(biāo)函數(shù)：max(minz)=c1

x1+c2

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

x2+……..+a1n

xn≤(=≥)b1

a21x1+a22

x2+……..+a2n

xn≤(=≥)b2

…………am1x1+am2

x2+……..+amn

xn

≤(=≥)bm

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

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

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

x1、x2

、x3

、x4≥0§2.2線(xiàn)性規(guī)劃圖解法一、解題步驟4將最優(yōu)解代入目標(biāo)函數(shù)，求出最優(yōu)值。1建立坐標(biāo)系并在直角平面坐標(biāo)系中畫(huà)出所有的約束等式，然后找出滿(mǎn)足所有約束條件的公共部分，稱(chēng)為可行域，可行域中的點(diǎn)稱(chēng)為可行解。2標(biāo)出目標(biāo)函數(shù)值改善的方向。3畫(huà)出目標(biāo)函數(shù)等值線(xiàn)，若求最大（?。┲担瑒t令目標(biāo)函數(shù)等值線(xiàn)沿目標(biāo)函數(shù)值增加（或減少）的方向平行移動(dòng)，找與可行域最后相交的點(diǎn)，該點(diǎn)就是最優(yōu)解。用圖解法求解下列線(xiàn)性規(guī)劃問(wèn)題（例1）

x1+2x2≤8①4x1≤16

②

4x2≤12③

x1，x2≥0

maxz=2x1+3x2最優(yōu)解：X*=(2,4)T最優(yōu)值：Z*=14目標(biāo)函數(shù)等值線(xiàn)Z=0x2x1①②③線(xiàn)性規(guī)劃的圖解（例2）max z=x1+3x2 s.t. x1+x2≤6 -x1+2x2≤8 x1≥0,x2≥0可行域目標(biāo)函數(shù)等值線(xiàn)最優(yōu)解64-860x1x2目標(biāo)函數(shù)：分別取決策變量為坐標(biāo)向量建立直角坐標(biāo)系。在直角坐標(biāo)系里，圖上任意一點(diǎn)的坐標(biāo)代表了決策變量的一組值，每個(gè)約束條件都代表一個(gè)半平面。圖示如下：用圖解法求解下列線(xiàn)性規(guī)劃問(wèn)題x2x1X2≥0X2=0x2x1X1≥0X1=0100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖2-1x1x2z=20000=50x1+100x2圖2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE綜上得到最優(yōu)解：最優(yōu)目標(biāo)值:1、凸集若連接n維點(diǎn)集P中任意兩點(diǎn)x（1），x（2），其線(xiàn)段仍在P內(nèi)，則稱(chēng)P為凸集。即：{x|x=

x(1)+(1-)x(2)，0<<1,x(1)P,x(2)P}P,則稱(chēng)P為凸集）2、極點(diǎn)若點(diǎn)x∈Ｐ,且x不是P中任何線(xiàn)段的內(nèi)點(diǎn)，則稱(chēng)點(diǎn)x為凸集P的極點(diǎn)。顯然多邊形的頂點(diǎn)都是極點(diǎn)，四面體的頂點(diǎn)也都是極點(diǎn)，而圓周上、球面上的每一個(gè)點(diǎn)都是極點(diǎn)，其它點(diǎn)都不是極點(diǎn)。二、關(guān)于凸集、極點(diǎn)的概念三、線(xiàn)性規(guī)劃解的性質(zhì)定理1

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

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

若線(xiàn)性規(guī)劃在可行域的兩個(gè)頂點(diǎn)上達(dá)到最優(yōu)，則在兩個(gè)頂點(diǎn)的連線(xiàn)上也達(dá)到最優(yōu)。——線(xiàn)性規(guī)劃的每一個(gè)基本可行解對(duì)應(yīng)凸集的每一個(gè)頂點(diǎn)?！艟€(xiàn)性規(guī)劃有最優(yōu)解，則一定在凸集的某個(gè)（些）頂點(diǎn)上達(dá)到最優(yōu)。——若線(xiàn)性規(guī)劃在兩個(gè)頂點(diǎn)以上達(dá)到最優(yōu),則一定有無(wú)窮多個(gè)最優(yōu)解?！顑?yōu)解一定是基本可行解，但基本可行解不一定是最優(yōu)解。四、線(xiàn)性規(guī)劃問(wèn)題求解可能出現(xiàn)的情況x1x2z=20000=50x1+100x2圖2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE則可行域?yàn)榭沼?，不存在滿(mǎn)足約束條件的解，當(dāng)然也就不存在最優(yōu)解了。

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

五、LP解的有關(guān)概念及其關(guān)系1可行解（feasiblesolution）：滿(mǎn)足線(xiàn)性規(guī)劃約束條件的解稱(chēng)為可行解。（一）有關(guān)概念2最優(yōu)解（optimalsolution）：使線(xiàn)性規(guī)劃目標(biāo)函數(shù)達(dá)到最優(yōu)的可行解稱(chēng)為最優(yōu)解。3基本解（basicsolution）：以線(xiàn)性規(guī)劃約束等式的系數(shù)矩陣A中任意m行m列組成的m×m滿(mǎn)秩子矩陣為基矩陣，與基矩陣相對(duì)應(yīng)的變量稱(chēng)為基變量（basicvariable），其余變量稱(chēng)為非基變量，若令非基變量為零，則可求得基變量的解（值），這個(gè)解稱(chēng)為基本解。

4基本可行解（basicfeasiblesolution）：滿(mǎn)足非負(fù)約束的基本解稱(chēng)為基本可行解。若約束等式中有n個(gè)變量，m個(gè)約束，則基本解的個(gè)數(shù)≤令非基變量x1＝0，x2

＝0則得：X＝(0,0,3,1)T基本解當(dāng)基變量為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／不是基本解可行解／是基本可行解？例討論下述約束方程的解1可行解與最優(yōu)解：最優(yōu)解一定是可行解，但可行解不一定是最優(yōu)解。（二）線(xiàn)性規(guī)劃解之間的關(guān)系基本解不一定是可行解，可行解也不一定是基本解。2可行解與基本解：3可行解與基本可行解：基本可行解一定是可行解，但可行解不一定是基本解?；究尚薪庖欢ㄊ腔窘?，但基本解不一定是基本可行解。4基本解與基本可行解：5最優(yōu)解與基本解：最優(yōu)解不一定是基本解，基本解也不一定是最優(yōu)解。問(wèn)題：最優(yōu)解與基本可行解？非可行解可行解基本可行解基本解六、線(xiàn)性規(guī)劃模型的標(biāo)準(zhǔn)形式及其標(biāo)準(zhǔn)化（一）線(xiàn)性規(guī)劃模型標(biāo)準(zhǔn)形式特點(diǎn)

1．目標(biāo)最大化；2．約束為等式；

3．決策變量均非負(fù)；4．右端項(xiàng)非負(fù)。特點(diǎn)Maxz=c1x1+c2x2

+…+cnxna11x1+a12x2+…+a1nxn

=b1a21x1+a22x2+…+a2nxn

=b2

...am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn≥0s.t

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

（二）線(xiàn)性規(guī)劃模型標(biāo)準(zhǔn)化問(wèn)題1、極小化目標(biāo)函數(shù)的問(wèn)題：則令：z

＝-f

，Minf

＝—Maxz2、約束條件不是等式的問(wèn)題：時(shí)，可以引進(jìn)一個(gè)新的變量，使它等于約束右邊與左邊之差（2）當(dāng)約束條件為類(lèi)似地令則有：則有：（1）當(dāng)約束條件為3.右端項(xiàng)有負(fù)值的問(wèn)題：

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

為了使約束方程由不等式成為等式而引進(jìn)的變量,當(dāng)不等式為“小于等于”時(shí)稱(chēng)引進(jìn)的變量為“松弛變量”；當(dāng)不等式為“大于等于”時(shí)稱(chēng)為“剩余變量”。如果原問(wèn)題中有若干個(gè)非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時(shí)，必須對(duì)各個(gè)約束引進(jìn)不同的松弛變量或剩余變量。

在標(biāo)準(zhǔn)形式中，要求右端項(xiàng)必須每一個(gè)分量非負(fù)。當(dāng)某一個(gè)右端項(xiàng)系數(shù)為負(fù)時(shí)，如

4.變量無(wú)符號(hào)限制的問(wèn)題

在標(biāo)準(zhǔn)形式中，必須每一個(gè)變量均有非負(fù)約束。當(dāng)某一個(gè)變量xj

沒(méi)有非負(fù)約束時(shí)，可以令xj

=

xj’-

xj”

其中xj’≥0，xj”≥0即用兩個(gè)非負(fù)變量之差來(lái)表示一個(gè)無(wú)符號(hào)限制的變量，當(dāng)然xj的符號(hào)取決于xj’和xj”的大小?？傊ㄟ^(guò)上述問(wèn)題的處理，線(xiàn)性規(guī)劃模型的一般形式均可化為標(biāo)準(zhǔn)形式。標(biāo)準(zhǔn)化例題1一般形式標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)化例題2§2.3靈敏度分析

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

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

當(dāng)約束條件中右邊系數(shù)變化時(shí)，線(xiàn)性規(guī)劃的可行域發(fā)生變化，可能引起的最優(yōu)解的變化，進(jìn)而了解當(dāng)其他約束不變時(shí)，某一約束條件的右端項(xiàng)每變化一個(gè)單位，使目標(biāo)函數(shù)值的改變量。由講義例1可知：（1）假設(shè)設(shè)備臺(tái)時(shí)增加10個(gè)臺(tái)時(shí)，即變?yōu)?10臺(tái)時(shí)，這時(shí)可行域擴(kuò)大，但最優(yōu)解所在的基點(diǎn)不變，得最優(yōu)解為：X1=60，X2=250x1x2x2=0x1=0x2=250x1+x2=3102x1+x2=400圖2-1（2）假設(shè)原料A增加10千克時(shí)，即變化為410，這時(shí)可行域擴(kuò)大，但最優(yōu)解仍為①和③約束方程的交點(diǎn)。此變化對(duì)總利潤(rùn)無(wú)影響，因此該約束條件的對(duì)偶價(jià)格為0。由于原最優(yōu)解沒(méi)有把原料A用盡，有50千克的剩余，因此增加10千克值增加了庫(kù)存，而不會(huì)增加利潤(rùn)。這時(shí)，即變化后的總利潤(rùn)—變化前的總利潤(rùn)=增加的利潤(rùn)

(50×60+100×250)—(50×50+100×250)=500元，即：每增加一個(gè)臺(tái)時(shí)的利潤(rùn)為：500/10=50元說(shuō)明在一定范圍內(nèi)每增加（減少）1個(gè)臺(tái)時(shí)的設(shè)備能力就可增加（減少）50元利潤(rùn)，稱(chēng)為該約束條件的對(duì)偶價(jià)格。圖2-1x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=410

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

；maxZ=27500對(duì)偶問(wèn)題：不妨提出這樣的問(wèn)題，如果該廠把設(shè)備（工時(shí)）和A、B原料租賃和轉(zhuǎn)讓出去，又要不比自己生產(chǎn)賺的少，該廠如何收取租金和轉(zhuǎn)讓費(fèi)？或者說(shuō)設(shè)備租賃至少多少錢(qián)一個(gè)工時(shí)，原料A、B應(yīng)收多少錢(qián)一公斤？原問(wèn)題：例2.1某廠在計(jì)劃期內(nèi)安排生產(chǎn)兩種產(chǎn)品，生產(chǎn)所需資源限制及單位產(chǎn)品原料消耗由下表給給出甲乙資源限制設(shè)備11300臺(tái)時(shí)原料