【正文】 =zmax+Cd∵ z0 = zmax 179。證明：設(shè) X0=(x10, x20,②充分性： X非凸集頂點(diǎn)222。 mdj179。xm mdm ，0，xm+ mdm，0， + (xm+ mdm)Pm=b由 (1)(2)得 (x1 md1)P1+ (x2 md2)P2+dm不全為0，兩端同乘m≠0，得md1P1+md2P2+,Pm線性相關(guān)，即有d1P1+d2P2+,xm,0,0,X非凸集頂點(diǎn)①必要性：X非基可行解222。定理2 線性規(guī)劃模型的基可行解對(duì)應(yīng)其可行域的頂點(diǎn)。當(dāng)km時(shí)，則必定可再找出mk個(gè)列向量與P1,P2,xk的系數(shù)列向量P1,P2, X為基可行解若A的秩為m，則X的正分量的個(gè)數(shù)k163。,Pk應(yīng)該線性獨(dú)立。,0)T，若X為基可行解，顯然，由基可行解定義可知x1, x2,X的正分量所對(duì)應(yīng)的系數(shù)列向量線性獨(dú)立 可設(shè)X=(x1,x2,C，即C為凸集。C， (0a1)，∴ AX=aAX1+ (1a)AX2 = ab+ (1a)b =b , (0a1)，且 X 179。0，X2179。C，X2 206。證明：設(shè) max z=CX st. AX=b X179。 頂點(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)。設(shè)E是n維向量的集合，X1和X2是E的任意兩點(diǎn)，若X1和X2連線段上的點(diǎn)X=aX1+(1a)X2 (0≤a≤1)仍屬于集合E，則稱E為凸集。表11列出了本例的全部基和基解，其中共有5個(gè)基可行解，表中用＊標(biāo)注的為最優(yōu)解即X=(3,3,0,4,0)T。，列出全部基、基解、基可行解，并指出最優(yōu)解?；顑?yōu)解 使目標(biāo)函數(shù)達(dá)到最大值的基可行解稱為基最優(yōu)解?；尚薪?滿足變量非負(fù)取值的基解稱為基可行解(或基本可行解)。基解 在式（）的約束方程組中令所有非基變量xm+1=xm+2=…=xn =0 后，因?yàn)锽是可逆矩陣，根據(jù)克拉默法則，解出m個(gè)基變量的唯一值XB=(x1,x2,...,xm)T，再加上非基變量取0值得到的解 X=(x1,x2,...,xm,0,...,0)T 稱為相應(yīng)于基B的基解(或基本解)。不失一般性，設(shè)基為將B中每個(gè)列向量即P1,P2,… ,Pm稱為基向量，與基向量Pj對(duì)應(yīng)的變量xj稱為基變量(常記為XB)，除基本量以外的其它變量稱為非基變量(常記為XN)?！?.。、xq39。39?！?.5. =xq39。4. 變量xp≤39。松弛變量或剩余變量在實(shí)際問題中表示未被利用的資源數(shù)或短缺的資源數(shù)，均未轉(zhuǎn)化為價(jià)值和利潤(rùn)，所以引入到模型后它們?cè)谀繕?biāo)函數(shù)中的系數(shù)均為零。類似的，當(dāng)約束條件為“≥”時(shí)，例如3 x1+8 x2≥24，可令x4=3 x1+8 x224,得3 x1+8x2x4=12,顯然x4≥0。當(dāng)約束條件為“≤”時(shí)，例如2 x1+2 x2≤12，可令x3=122 x12 x2,得2 x1+2 x2+x3=12,顯然x3≥0。，即為因?yàn)樵跐M足相同約束條件的前提下使z達(dá)到極小值的那組決策變量必定使(z)達(dá)到極大值，反之亦然，故令新目標(biāo)函數(shù)z39。為了討論問題的方便，規(guī)定線性規(guī)劃問題的標(biāo)準(zhǔn)形式如下：（）標(biāo)準(zhǔn)形式的線性規(guī)劃問題中，目標(biāo)函數(shù)為求極大值（有些書上規(guī)定是求極小值），約束條件全為等式，約束條件右端常數(shù)全為非負(fù)值，決策變量的取值必須非負(fù)。重復(fù)上述過程，直到找到使目標(biāo)函數(shù)值達(dá)到最優(yōu)的頂點(diǎn)為止（如果有的話）。再與周圍相鄰頂點(diǎn)的目標(biāo)函數(shù)值比較是否比這個(gè)值更優(yōu)。若在兩個(gè)頂點(diǎn)同時(shí)達(dá)到最優(yōu)解，則它們連線上的所有點(diǎn)都是最優(yōu)解，此時(shí)對(duì)應(yīng)問題有無窮多最優(yōu)解。(2) 若線性規(guī)劃問題的可行域不是空集，則可行域?yàn)橥辜Ｆ湓蚴悄Ｐ捅旧碛绣e(cuò)誤，出現(xiàn)了矛盾約束。解 用圖解法求解時(shí)該問題的可行域是空集，如圖15所示。注意：可行域無界僅是線性規(guī)劃問題出現(xiàn)無界解的必要條件，而不是充分條件。此時(shí)問題有可行解但目標(biāo)函數(shù)值無界，故無最優(yōu)解，常稱之為無界解。 用圖解法求解下列線性規(guī)劃問題。 解 用圖解法求解，如圖13所示，沿優(yōu)化方向平移時(shí)目標(biāo)函數(shù)等值線與可行域在整個(gè)線段上相切，即該問題的最優(yōu)解為此線段上的所有點(diǎn)。例3有唯一一個(gè)最優(yōu)解，而任意一個(gè)線性規(guī)劃問題的解還可能有其它情形。此問題有唯一最優(yōu)解當(dāng) x1=x2=3 時(shí)，Zmax = 15。目標(biāo)函數(shù)z=2 x1+3 x2表示一族直線，向右上方平移目標(biāo)函數(shù)等值線將使目標(biāo)函數(shù)值增大，依此方向平移到與可行域相切為止。 用圖解法求例1的最優(yōu)解。 圖解法對(duì)于僅含有兩個(gè)決策變量的線性規(guī)劃問題有一種簡(jiǎn)單直觀的幾何方法——圖解法。在單純數(shù)學(xué)意義下也可以有決策變量取非正實(shí)數(shù)。式()也可簡(jiǎn)寫為()若各個(gè)約束條件左右兩端的連接符號(hào)都相同（都是“≤”，或都是“=”，或都是“≥”），則可利用向量把線性規(guī)劃問題寫成()在式()中式()還可用矩陣形式表示為 ()式()中A稱為約束條件中變量的系數(shù)矩陣，或簡(jiǎn)稱為約束變量的系數(shù)矩陣。全部可行解的集合稱為可行域．特別的，能使目標(biāo)函數(shù)達(dá)到最優(yōu)的可行解稱為最優(yōu)解。約束條件右端的常數(shù)用bi表示，通常bi稱為資源限量或資源擁有量。目標(biāo)函數(shù)中變量系數(shù)用cj表示, 通常cj稱為價(jià)值系數(shù)。實(shí)際問題中線性的含義：一是嚴(yán)格的比例性，如生產(chǎn)某產(chǎn)品可獲取的利潤(rùn)和產(chǎn)品的數(shù)量嚴(yán)格成比例；二是可疊加性，如生產(chǎn)多種產(chǎn)品時(shí)對(duì)某項(xiàng)資源的消耗量應(yīng)等于各產(chǎn)品對(duì)該項(xiàng)資源的消耗量之和。通常用 z=f(x1，x2，…，xn)表示，按優(yōu)化目標(biāo)分別在這個(gè)函數(shù)前面加上max或min；（3）約束條件，即決策變量取值時(shí)受到各種可用資源的限制，通常表示為含決策變量的等式或不等式。規(guī)劃問題的數(shù)學(xué)模型包含三個(gè)組成要素：（1）決策變量或變量，即決策者為實(shí)現(xiàn)規(guī)劃目標(biāo)采取的方案、措施，是問題中要確定的未知量。該飼料廠的目標(biāo)是在滿足動(dòng)物生長(zhǎng)需求的情況下，使總的費(fèi)用為最小?，F(xiàn)有四種飼料可供選用，各種飼料每千克營(yíng)養(yǎng)成分含量及單價(jià)如表12所示：表12 每千克飼料中各營(yíng)養(yǎng)成分的含量IIIIIIIV需要量蛋白質(zhì)（克）3215700礦物質(zhì)（克）1230維生素（毫克）1100單價(jià)（元/千克）2四種飼料各采購(gòu)多少，才能使總費(fèi)用最??？解 設(shè)四種飼料分別采購(gòu)x1,x2,x3,x4千克.根據(jù)該動(dòng)物每天對(duì)蛋白質(zhì)的需求，有 。該廠的目標(biāo)是在各種設(shè)備允許的情況下，使總的利潤(rùn)收入z=2 x1+3 x2為最大。按工藝規(guī)定，生產(chǎn)每件產(chǎn)品的單位利潤(rùn)、消耗三種設(shè)備的工時(shí)以及各種設(shè)備工時(shí)的限額如表11所示：表11 單位產(chǎn)品消耗設(shè)備工時(shí)III設(shè)備工時(shí)限量（小時(shí)）設(shè)備A2212設(shè)備B4016設(shè)備C0515單位利潤(rùn)（元）23如何安排生產(chǎn)才能使總的利潤(rùn)最大？解 設(shè)計(jì)劃期內(nèi)兩種產(chǎn)品的產(chǎn)量分別為x1和x2，由于設(shè)備A在計(jì)劃期內(nèi)的有效時(shí)間為12h，不允許超過，于是有2 x1+2 x2≤12?，F(xiàn)各舉一例如下：常山機(jī)器廠生產(chǎn) I、II 兩型產(chǎn)品。線性規(guī)劃是運(yùn)籌學(xué)創(chuàng)立初期人們重點(diǎn)研究的內(nèi)容，是生產(chǎn)、科研和企業(yè)管理中一種有效的優(yōu)化技術(shù)，其理論完善，方法簡(jiǎn)便，應(yīng)用廣泛，成為規(guī)劃問題乃至運(yùn)籌學(xué)最基本的內(nèi)容。第1章 線性規(guī)劃與單純形法 .生產(chǎn)和經(jīng)營(yíng)管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃論要解決的問題。規(guī)劃論作為運(yùn)籌學(xué)的一大分支，常分成線性規(guī)劃、非線性規(guī)劃和動(dòng)態(tài)規(guī)劃三個(gè)部分。第一節(jié) 線性規(guī)劃的基本概念 線性規(guī)劃的數(shù)學(xué)模型 線性規(guī)劃問題通常有兩大類型：一類是在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最大的經(jīng)濟(jì)效益（如產(chǎn)量最多或利潤(rùn)最大等）；另一類是當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源 （如資金、設(shè)備、原材料、人工或時(shí)間等）去完成給定的任務(wù)或目標(biāo)。這兩型產(chǎn)品都分別要在A、B、C三種不同設(shè)備上加工。對(duì)于B、C設(shè)備也可列出類似的不等式：4 x1≤16；5 x2≤15。因此例1可以歸結(jié)為如下的數(shù)學(xué)模型 一飼養(yǎng)場(chǎng)飼養(yǎng)某種動(dòng)物用于出售，該動(dòng)物每天至少需要700克蛋白質(zhì)， 30克礦物質(zhì)，100毫克維生素。同理得到類似的不等式；。因此例2可以歸結(jié)為如下的數(shù)學(xué)模型 從上面的例子可以看出，所謂規(guī)劃問題，就是求規(guī)劃目標(biāo)在若干限制條件下的極值問題。通常用x1，x2，…，xn表示；（2）目標(biāo)函數(shù)，即問題要達(dá)到的目標(biāo)要求，表示為決策變量的函數(shù)。若在規(guī)劃問題的數(shù)學(xué)模型中，決策變量是可控的連續(xù)變量，目標(biāo)函數(shù)和約束條件都是線性的，則此類模型稱為線性規(guī)劃問題或線性規(guī)劃（Linear Programming）。一般地，假設(shè)線性規(guī)劃數(shù)學(xué)模型有n個(gè)決策變量，分別用xj（j=1,2…,n）表示。有m個(gè)約束條件，第i個(gè)約束條件中變量xj的系數(shù)用aij表示，aij常稱為工藝系數(shù)或技術(shù)系數(shù)。于是線性規(guī)劃數(shù)學(xué)模型的一般表達(dá)式可寫成()一個(gè)線性規(guī)劃問題有解，是指能找出一組xj(j＝1,...,n)的值既滿足()中的約束條件，又滿足決策變量的取值要求，此時(shí)稱X=(x1,x2,...,xn)T為該問題的可行解。研究線性規(guī)劃的根本目的在于求出它的最優(yōu)解，這個(gè)過程稱為求解線性規(guī)劃問題。注意在實(shí)際意義中決策變量的取值一般為非負(fù)實(shí)數(shù)。另外若某個(gè)決策變量xj表示第j種產(chǎn)品本期產(chǎn)量相對(duì)于前期產(chǎn)量的變化量，則xj的取值范圍可以是全體實(shí)數(shù)。圖解法的步驟是：先在平面直角坐標(biāo)系中畫出約束條件所確定的可行域；再對(duì)任意確定的z，畫出目標(biāo)函數(shù)所代表的一族直線（常稱為目標(biāo)函數(shù)等值線）；最后沿優(yōu)化方向平移目標(biāo)函數(shù)等值線，確定最優(yōu)解（如果有的話）。解：由該問題所確定的可行域?yàn)閳D11所示的凸五邊形。此時(shí)唯一切點(diǎn)即為最優(yōu)解，這個(gè)切點(diǎn)是凸五邊形的一個(gè)頂點(diǎn)，如圖12所示。即常山機(jī)器廠生產(chǎn)的最佳方案為I、II型產(chǎn)品各生產(chǎn)3件，可獲得最大利潤(rùn)15元。 用圖解法求解下列線性規(guī)劃問題。故該問題有無窮多個(gè)最優(yōu)解，它們使目標(biāo)函數(shù)都達(dá)到同一個(gè)最大值。解 用圖解法求解，如圖14所示，該問題的可行域上方無邊界，目標(biāo)函數(shù)等值線沿著優(yōu)化方向可以無限延伸，使得目標(biāo)函數(shù)值無限增大。這種情形的出現(xiàn)往往是由于在建立數(shù)學(xué)模型時(shí)遺漏了某些必要的資源約束條件。 用圖解法求解下列線性規(guī)劃問題。表明此問題無可行解（自然是最優(yōu)解的。盡管圖解法只能解決含有兩個(gè)決策變量的線性規(guī)劃問題，但從它的解題思路和幾何直觀上得到了線性規(guī)劃問題的若干規(guī)律，對(duì)之后介紹求解一般線性規(guī)劃問題的代數(shù)方法——單純形法很有啟示：(1) 求解線性規(guī)劃問題時(shí)，解有四種情況：唯一最優(yōu)解、無窮多最優(yōu)解（也稱為多重最優(yōu)解）、無界解（也稱為有可行解但無最優(yōu)解）和無可行解。 (3) 若線性規(guī)劃問題有最優(yōu)解，則最優(yōu)解一定可以在可行域的某個(gè)頂點(diǎn)達(dá)到。(4) 解題思路：先找出凸集的任一頂點(diǎn)，計(jì)算其目標(biāo)函數(shù)值。若否，則該頂點(diǎn)就是最優(yōu)解的點(diǎn)或最優(yōu)解的點(diǎn)之一；若是，則轉(zhuǎn)到比該頂點(diǎn)的目標(biāo)函數(shù)值更優(yōu)的另一頂點(diǎn)。第2節(jié) 線性規(guī)劃的標(biāo)準(zhǔn)形式和解的性質(zhì) 線性規(guī)劃的標(biāo)準(zhǔn)形式\在不同情況下，歸結(jié)出來的線性規(guī)劃問題可能多種多樣，在目標(biāo)函數(shù)和約束條件上也可能各有不同。對(duì)于不符合標(biāo)準(zhǔn)形式的線性規(guī)劃問題（或稱為非標(biāo)準(zhǔn)形式），都可以分別通過下述方法轉(zhuǎn)化為標(biāo)準(zhǔn)形式。=z，即轉(zhuǎn)化為2. 約束條件為不等式。這樣增加的決策變量x3取非負(fù)值，加到原約束條件中把“≤”約束轉(zhuǎn)化為等式約束，故稱為松弛變量。這樣增加的決策變量x4取非負(fù)值，加到原約束條件中把“≥”約束轉(zhuǎn)化為等式約束，故稱為剩余變量（也可稱為剩余變量）。3. 若某個(gè)約束條件的右端項(xiàng)bi是負(fù)數(shù)，則可將此約束兩邊同時(shí)乘以(1)，從而(bi)成為正數(shù)。=xp,代入模型，顯然xp39。xq39。代入模型，顯然xq39。39。并引入松弛變量x4, x5,按照上述方法將問題化為如下標(biāo)準(zhǔn)形式：二、 線性規(guī)劃的基可行解的概念 已知線性規(guī)劃的標(biāo)準(zhǔn)形式： ()A=(aij)為約束方程組的mn階系數(shù)矩陣(設(shè)nm)，則稱B是線性規(guī)劃問題的一個(gè)基矩陣（簡(jiǎn)稱為基）?？梢娭挥邢却_定一個(gè)基，才有隨之確定的基變量和非基變量，且基變量有m個(gè)，非基變量有nm 個(gè)。顯然，基解的總數(shù)不會(huì)超過 個(gè)，在每個(gè)基解中取值非0的變量個(gè)數(shù)不會(huì)大于m?？尚谢?對(duì)應(yīng)于基可行解的基稱為可行基。最優(yōu)基 對(duì)應(yīng)于基最優(yōu)解的基稱為最優(yōu)基。解 先寫出系數(shù)矩陣因?yàn)?秩(A)≤3，所以只要找出3個(gè)列向量組成可逆矩陣就成為線性規(guī)劃問題的一個(gè)基，再求出對(duì)應(yīng)的基解。表11基基解是基可行解？目標(biāo)函數(shù)值 x1x2x3x4x5P1P2P343200否17P1P2P433040是15＊P1P2P542005是14P1P3P5404015是8P1P4P5600815否12P2P3P4036160是9P2P4P5060165否18P3P4P500121615是0三、 線性規(guī)劃解的性質(zhì)在介紹線性規(guī)劃問題解的性質(zhì)之前，先介紹凸集和頂點(diǎn)。直觀上講：凸集是沒有凹入部分，其內(nèi)部沒有空洞。定理1 若線