【正文】 右端常數(shù)，原約束的右端常數(shù)對(duì)應(yīng)對(duì)偶目標(biāo)的系數(shù)；（5）原系數(shù)矩陣與對(duì)偶系數(shù)矩陣互為轉(zhuǎn)置；（6）原變量與對(duì)偶變量都是非負(fù)取值。例如生產(chǎn)出一件Ⅰ型產(chǎn)品，需耗用A設(shè)備2小時(shí)，B設(shè)備4小時(shí)，這些資源可換得租金2y1+4y2。這對(duì)于下面要介紹的對(duì)偶問題和靈敏度分析很有用處。=0 CB B39。σj0σN39。不失一般性假設(shè)線性規(guī)劃問題形如：引入松弛變量后化為為敘述的方便，將變量分成三組：在初始單純形表中基變量為松弛變量用XS表示，經(jīng)過若干次迭代后對(duì)應(yīng)的最終單純形表中基變量用XB表示（注意XS和XB可以有公共變量），若存在既不在XS也不在XB中的其它變量則用XN表示。設(shè)A工序可分別在設(shè)備A1或A2上完成，有BBB3三種設(shè)備可用于完成B工序。表112cj問如何才能既滿足需要，又能使總的用料最少？解：設(shè)變量xj為使用第 j 種方式下料的圓鋼根數(shù)。一般而言，一個(gè)經(jīng)濟(jì)、管理問題只有滿足以下條件時(shí)，才能建立對(duì)應(yīng)的線性規(guī)劃模型。 用單純形法求解下列問題。為此人們已經(jīng)提出了三種避免出現(xiàn)死循環(huán)的方法，即攝動(dòng)法、字典序法或最小下標(biāo)法。若求得wmin=0，則表明已知問題有可行解，進(jìn)入第二階段，否則表明已知問題無可行解，計(jì)算結(jié)束。本例引入人工變量后轉(zhuǎn)化為：再用單純形法繼續(xù)計(jì)算如下：Cj230MMCBBbX1X2X3X4X5θMX43111103MX541[2]0012σj2+2M3+3MM00MX41[1/2]0111/223X221/21001/24σj1/2+M/20M03/23M/22X12102213X2101111σj0011M1M在最終單純形表中，檢驗(yàn)數(shù)全非正，且人工變量取值全為0，因此該問題有唯一最優(yōu)解：注意： 若表中所有sj 163。下一節(jié)將解決線性規(guī)劃問題化為標(biāo)準(zhǔn)形時(shí)，約束條件的系數(shù)矩陣中不存在單位矩陣，應(yīng)如何構(gòu)造初始可行基。⑤根據(jù)max{sj｜sj＞0}=sk原則，確定xk為換入基的變量，簡(jiǎn)稱為換入變量(或進(jìn)基變量)，再按比值q的選取規(guī)則計(jì)算：q=min{bi′/aik′| aik′＞0}=bl′/ aik′ 確定xBl為換出基的變量，簡(jiǎn)稱換出變量（或出基變量）。下面介紹用單純形表計(jì)算線性規(guī)劃問題的步驟。+165。 從一個(gè)基可行解轉(zhuǎn)換為另一個(gè)基可行解且系數(shù)矩陣取前m列的單位矩陣為基，則基可行解為X（0）=(x10, x20,引入松弛變量xsi ( i=1,2,…,m )化為標(biāo)準(zhǔn)形式：此時(shí)系數(shù)矩陣為：取后m列對(duì)應(yīng)的單位矩陣為基，得到初始基可行解：X=( 0,0,并且將X(r)代替(1)式中的所有X(i),這就得到: 由此得到 CX(0)≤ CX(r)。,xn0)T 是線性規(guī)劃模型的一個(gè)最優(yōu)解， z0=zmax=CX0 若X0非基可行解，即非頂點(diǎn)，只要取d為充分小的正數(shù)，則必能找出X1= X0d ，X2 = X0 +d ，即X1 、 X2為可行解，z1=CX1=CX0Cd=zmaxCd ，z2=CX2=CX0+Cd =zmax+Cd∵ z0 = zmax 179。②充分性： X非凸集頂點(diǎn)222。dm不全為0，兩端同乘m≠0，得md1P1+md2P2+X非凸集頂點(diǎn)①必要性：X非基可行解222。,Pk應(yīng)該線性獨(dú)立。C， (0a1)，∴ AX=aAX1+ (1a)AX2 = ab+ (1a)b =b , (0a1)，且 X 179。 頂點(diǎn)： 凸集E中的點(diǎn)X，若不存在凸集中的點(diǎn)X1,X2,使得X成為X1和X2連線段上的點(diǎn)，或者不存在X1及X2,使得X=aX1+(1a)X2，(0≤a≤1)，則稱點(diǎn)X為頂點(diǎn)?；顑?yōu)解 使目標(biāo)函數(shù)達(dá)到最大值的基可行解稱為基最優(yōu)解?！?.。4. 變量xp≤39。，即為因?yàn)樵跐M足相同約束條件的前提下使z達(dá)到極小值的那組決策變量必定使(z)達(dá)到極大值，反之亦然，故令新目標(biāo)函數(shù)z39。若在兩個(gè)頂點(diǎn)同時(shí)達(dá)到最優(yōu)解，則它們連線上的所有點(diǎn)都是最優(yōu)解，此時(shí)對(duì)應(yīng)問題有無窮多最優(yōu)解。注意：可行域無界僅是線性規(guī)劃問題出現(xiàn)無界解的必要條件，而不是充分條件。例3有唯一一個(gè)最優(yōu)解，而任意一個(gè)線性規(guī)劃問題的解還可能有其它情形。 圖解法對(duì)于僅含有兩個(gè)決策變量的線性規(guī)劃問題有一種簡(jiǎn)單直觀的幾何方法——圖解法。約束條件右端的常數(shù)用bi表示，通常bi稱為資源限量或資源擁有量。規(guī)劃問題的數(shù)學(xué)模型包含三個(gè)組成要素：（1）決策變量或變量，即決策者為實(shí)現(xiàn)規(guī)劃目標(biāo)采取的方案、措施，是問題中要確定的未知量。按工藝規(guī)定，生產(chǎn)每件產(chǎn)品的單位利潤、消耗三種設(shè)備的工時(shí)以及各種設(shè)備工時(shí)的限額如表11所示：表11 單位產(chǎn)品消耗設(shè)備工時(shí)III設(shè)備工時(shí)限量（小時(shí)）設(shè)備A2212設(shè)備B4016設(shè)備C0515單位利潤（元）23如何安排生產(chǎn)才能使總的利潤最大？解 設(shè)計(jì)劃期內(nèi)兩種產(chǎn)品的產(chǎn)量分別為x1和x2，由于設(shè)備A在計(jì)劃期內(nèi)的有效時(shí)間為12h，不允許超過，于是有2 x1+2 x2≤12。規(guī)劃論作為運(yùn)籌學(xué)的一大分支，常分成線性規(guī)劃、非線性規(guī)劃和動(dòng)態(tài)規(guī)劃三個(gè)部分。因此例1可以歸結(jié)為如下的數(shù)學(xué)模型 一飼養(yǎng)場(chǎng)飼養(yǎng)某種動(dòng)物用于出售，該動(dòng)物每天至少需要700克蛋白質(zhì)， 30克礦物質(zhì)，100毫克維生素。若在規(guī)劃問題的數(shù)學(xué)模型中，決策變量是可控的連續(xù)變量，目標(biāo)函數(shù)和約束條件都是線性的，則此類模型稱為線性規(guī)劃問題或線性規(guī)劃（Linear Programming）。研究線性規(guī)劃的根本目的在于求出它的最優(yōu)解，這個(gè)過程稱為求解線性規(guī)劃問題。解：由該問題所確定的可行域?yàn)閳D11所示的凸五邊形。故該問題有無窮多個(gè)最優(yōu)解，它們使目標(biāo)函數(shù)都達(dá)到同一個(gè)最大值。表明此問題無可行解（自然是最優(yōu)解的。若否，則該頂點(diǎn)就是最優(yōu)解的點(diǎn)或最優(yōu)解的點(diǎn)之一；若是，則轉(zhuǎn)到比該頂點(diǎn)的目標(biāo)函數(shù)值更優(yōu)的另一頂點(diǎn)。這樣增加的決策變量x3取非負(fù)值，加到原約束條件中把“≤”約束轉(zhuǎn)化為等式約束，故稱為松弛變量。xq39。可見只有先確定一個(gè)基，才有隨之確定的基變量和非基變量，且基變量有m個(gè)，非基變量有nm 個(gè)。解 先寫出系數(shù)矩陣因?yàn)?秩(A)≤3，所以只要找出3個(gè)列向量組成可逆矩陣就成為線性規(guī)劃問題的一個(gè)基，再求出對(duì)應(yīng)的基解。0并設(shè)其可行域?yàn)镃，若XX2為其可行解，且X1≠X2 ，則 X1206。 引理 線性規(guī)劃問題的可行解X為基可行解的充要條件，X的正分量所對(duì)應(yīng)的系數(shù)列向量是線性獨(dú)立的證明：①必要性：X基可行解222。m；當(dāng)k=m時(shí)，則x1,x2,+mdmPm=0 （2）由 (1)+(2)得 (x1+ md1)P1+ (x2+ md2)P2+若XX2仍不是頂點(diǎn)，可如此遞推，直至找出一個(gè)頂點(diǎn)為最優(yōu)解。即目標(biāo)函數(shù)在頂點(diǎn)X(r)處也達(dá)到了最大值。,0, b1,b2, xm0,0, ∴ 該線性規(guī)劃模型具有無界解。②構(gòu)造一個(gè)m階單位矩陣作為初始可行基，建立初始單純形表。 上述這種利用單純形表求解線性規(guī)劃問題的方法稱為單純形法（simplex method）。一、大M法 。但是若利用計(jì)算機(jī)求解，只能用很大的數(shù)代替M,則容易使機(jī)器判斷出錯(cuò)，從而使大M法失效。解：引入人工變量，轉(zhuǎn)化為：第一階段，求解線性規(guī)劃問題：先標(biāo)準(zhǔn)化：再用單純形法繼續(xù)計(jì)算如下：Cj00011CBBbX1X2X3X4X5θ1X431111031X541[2]0012σj231001X41[1/2]0111/220X221/21001/24σj1/20103/20X12102210X2101111σj00011在最終單純形表中，檢驗(yàn)數(shù)全非正，且人工變量取值全為0，因此第一階段問題有唯一最優(yōu)解：結(jié)果表明已知問題有可行解，進(jìn)入第二階段。解：在圖解法中已看到本例有無界解，用單純形法求解時(shí)，先化為標(biāo)準(zhǔn)形式列單純形表如下Cj230CBBbX1X2X3θ0X316401σj230表中最大的正檢驗(yàn)數(shù)σ2=30，但x2的系數(shù)為0，使得θ不能被確定，從而z無限增大。針對(duì)不同類型的線性規(guī)劃問題，應(yīng)如何進(jìn)行廣義標(biāo)準(zhǔn)化，具體方法（以大M法為例）參見表1，表中xs表示松弛變量，xa表示人工變量：表1模型決策變量約束條件目標(biāo)函數(shù)特點(diǎn)個(gè) 數(shù)取 值右 端 項(xiàng)等式或不等式極大或極小新加變量系數(shù)兩個(gè)三個(gè)以上xj≥0xj無約束xj ≤ 0 bi ≥0bi 0≤=≥maxZminZxs xa解法圖解法、單純形法單純形法不處理令xj =xj′ xj″ xj′ ≥0xj″ ≥0令 xj = xj不處理約束條件兩端同乘以1加松弛變量xs加入人工變量xa減去xs加入xa不處理令z′= ZminZ=－max z′0M經(jīng)過上述方法處理后可求出初始基可行解，列出初始單純形表，再用單純形法求解，對(duì)應(yīng)的步驟框圖如下圖：唯一最優(yōu)解 否 否否 是是是添加松弛變量、人工變量 列出初始單純形表計(jì)算各列檢驗(yàn)數(shù)бj所有бj163。（混合配料問題） 某工廠要用三種原材料C、P、H混合調(diào)配出三種不同規(guī)格的產(chǎn)品A、B、D。本章小結(jié)本章討論了線性規(guī)劃問題的數(shù)學(xué)模型，介紹了求解含有兩個(gè)變量的線性規(guī)劃問題的圖解法，詳細(xì)分析了單純形法的基本原理及基本步驟，并介紹了單純形法的進(jìn)一步討論，同時(shí)對(duì)一些實(shí)際問題建立了線性規(guī)劃問題的數(shù)學(xué)模型。，并指出問題具有唯一最優(yōu)解、無窮最優(yōu)解、無界解還是無可行解。設(shè)備產(chǎn)品設(shè)備有效臺(tái)時(shí)設(shè)備加工費(fèi)（元/小時(shí)）ⅠⅡⅢA1A2B1B2B357647109812116 00010 0004 0007 0004 000原料費(fèi)（元/件）售價(jià)（元/件）、X2均為某線性規(guī)劃的最優(yōu)解，證明這兩點(diǎn)連線上的所有點(diǎn)也是該問題的最優(yōu)解。,I,N39。比較得到下列關(guān)系：最終表的基解b39。而最終表中XN的檢驗(yàn)數(shù)σN39?？梢詮牧硪粋€(gè)角度來討論這個(gè)問題，假設(shè)常山廠考慮不進(jìn)行生產(chǎn)而把全部可利用的資源都出租給四海廠，常山廠希望給這些資源定出一個(gè)合理的價(jià)格，既使四海廠愿意租，又使本廠能得到生產(chǎn)這些產(chǎn)品所能獲得的最大收益。由此構(gòu)成了新問題的目標(biāo)函數(shù)。解：先改寫為原問題的對(duì)稱形式：再寫出對(duì)偶問題：最后簡(jiǎn)化得到所求問題的對(duì)偶問題：不難發(fā)現(xiàn)當(dāng)把四海廠對(duì)應(yīng)的LP2當(dāng)做原問題時(shí)，求出的對(duì)偶問題就是常山廠對(duì)應(yīng)的LP1。最終表中X的檢驗(yàn)數(shù)σN39。若原問題P和對(duì)偶問題D為對(duì)稱形式，則存在如下基本性質(zhì)：性質(zhì)1 弱對(duì)偶性（弱對(duì)偶原理）：設(shè)X和Y 分別是問題P和D的可行解，則必有CX≤bTY.證明：這條性質(zhì)表明：極大化問題的任何一個(gè)可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值是其對(duì)偶問題的目標(biāo)函數(shù)值的下界；而極小化問題的任何一個(gè)可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值都是其對(duì)偶問題的目標(biāo)函數(shù)值的上界。(1)(2)解：由圖解法知(1)Ｐ無可行解，Ｄ也無可行解；(2) Ｐ無可行解，Ｄ有無界解。 0，所以Y* = （s S′）T 179。又與原問題解中的基變量對(duì)應(yīng)的對(duì)偶問題變量取值為零，故對(duì)偶問題中非零的變量個(gè)數(shù)不超過對(duì)偶問題的約束條件數(shù)，且不難證明這些非零的變量對(duì)應(yīng)的系數(shù)向量線性獨(dú)立，故檢驗(yàn)數(shù)行的yi和(zjcj)值恰好是對(duì)偶問題的基解。在純市場(chǎng)條件下，若第i種資源的單位市場(chǎng)價(jià)格為mi ，而影子價(jià)格為yi 。這就是單純形法中各個(gè)檢驗(yàn)數(shù)的經(jīng)濟(jì)意義。即求解對(duì)偶問題時(shí)，應(yīng)在保持對(duì)偶問題可行性的前提下，使目標(biāo)函數(shù)值不斷減少，向原問題可行解的方向迭代。同時(shí)也得到對(duì)偶問題的最優(yōu)解X=(3,3,0,4,0)T,zmax=15。若敏感性太強(qiáng)，則說明最優(yōu)解的穩(wěn)定性程度較低。再直接對(duì)計(jì)算得到的已知問題最終表進(jìn)行修改，觀察這些參數(shù)變化后是否仍然滿足最優(yōu)解的要求。=B1△b（3）Pj的變化：當(dāng)系數(shù)列向量從Pj變化到Pj180。 （2）分析λ2的影響當(dāng)λ1=0時(shí)，將λ2反映到最終表得到cj23+λ2000CBBbX1X2X3X4X5θ2X13101/201/50X4400214/53+λ2