【正文】 標準形式和解的性質(zhì) 線性規(guī)劃的標準形式\在不同情況下，歸結(jié)出來的線性規(guī)劃問題可能多種多樣，在目標函數(shù)和約束條件上也可能各有不同。盡管圖解法只能解決含有兩個決策變量的線性規(guī)劃問題，但從它的解題思路和幾何直觀上得到了線性規(guī)劃問題的若干規(guī)律，對之后介紹求解一般線性規(guī)劃問題的代數(shù)方法——單純形法很有啟示：(1) 求解線性規(guī)劃問題時，解有四種情況：唯一最優(yōu)解、無窮多最優(yōu)解（也稱為多重最優(yōu)解）、無界解（也稱為有可行解但無最優(yōu)解）和無可行解。解 用圖解法求解，如圖14所示，該問題的可行域上方無邊界，目標函數(shù)等值線沿著優(yōu)化方向可以無限延伸，使得目標函數(shù)值無限增大。此時唯一切點即為最優(yōu)解，這個切點是凸五邊形的一個頂點，如圖12所示。注意在實際意義中決策變量的取值一般為非負實數(shù)。一般地，假設線性規(guī)劃數(shù)學模型有n個決策變量，分別用xj（j=1,2…,n）表示。同理得到類似的不等式；。第一節(jié) 線性規(guī)劃的基本概念 線性規(guī)劃的數(shù)學模型 線性規(guī)劃問題通常有兩大類型：一類是在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最大的經(jīng)濟效益（如產(chǎn)量最多或利潤最大等）；另一類是當任務或目標確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源 （如資金、設備、原材料、人工或時間等）去完成給定的任務或目標。現(xiàn)各舉一例如下：常山機器廠生產(chǎn) I、II 兩型產(chǎn)品。該飼料廠的目標是在滿足動物生長需求的情況下，使總的費用為最小。目標函數(shù)中變量系數(shù)用cj表示, 通常cj稱為價值系數(shù)。在單純數(shù)學意義下也可以有決策變量取非正實數(shù)。此問題有唯一最優(yōu)解當 x1=x2=3 時，Zmax = 15。此時問題有可行解但目標函數(shù)值無界，故無最優(yōu)解，常稱之為無界解。(2) 若線性規(guī)劃問題的可行域不是空集，則可行域為凸集。為了討論問題的方便，規(guī)定線性規(guī)劃問題的標準形式如下：（）標準形式的線性規(guī)劃問題中，目標函數(shù)為求極大值（有些書上規(guī)定是求極小值），約束條件全為等式，約束條件右端常數(shù)全為非負值，決策變量的取值必須非負。松弛變量或剩余變量在實際問題中表示未被利用的資源數(shù)或短缺的資源數(shù)，均未轉(zhuǎn)化為價值和利潤，所以引入到模型后它們在目標函數(shù)中的系數(shù)均為零。、xq39。基可行解 滿足變量非負取值的基解稱為基可行解(或基本可行解)。設E是n維向量的集合，X1和X2是E的任意兩點，若X1和X2連線段上的點X=aX1+(1a)X2 (0≤a≤1)仍屬于集合E，則稱E為凸集。0，X2179。,xk的系數(shù)列向量P1,P2,定理2 線性規(guī)劃模型的基可行解對應其可行域的頂點。+ (xm+ mdm)Pm=b由 (1)(2)得 (x1 md1)P1+ (x2 md2)P2+ mdj179。 證明：設X(1)，X(2)，…， X(k)是可行域D的頂點，若X(0)不是頂點，且目標函數(shù)在X(0)處達到最大值Z＊＝C X(0)。一、單純形法的解題思路 因為線性規(guī)劃問題若有最優(yōu)解，則一定可以在基可行解中找到，所以用單純形法求解線性規(guī)劃的基本思想是：先找到一個初始基可行解，若不是最優(yōu)解，則設法轉(zhuǎn)換到另一個基可行解，并使目標函數(shù)值不斷增大，直到找到最優(yōu)解為止（如果有的話）。,bm)T注意：用這個方法確定初始基可行解，必須保證約束條件全是“≤” 。, 0)T ，且前m個分量為正值。一個含有n個決策變量m個約束條件的標準線性規(guī)劃問題，對應的單純形表中第一行稱為價值行，用Cj表示，列出每個決策變量在目標函數(shù)中的系數(shù)；第二行稱為變量行，列出n個決策變量；最后一行稱為檢驗數(shù)行，列出每個決策變量的檢驗數(shù)（易見基變量的檢驗數(shù)為0）；第一列稱為基價值列，用CB表示，列出每個基變量在目標函數(shù)中的系數(shù)；第二列稱為基列（或基變量列），用B或XB表示,列出m個基變量；第三列稱為基解列，用b表示，即每個基變量的取值；最后一列稱為比值列；而中心位置m行n列的矩陣為約束條件的系數(shù)矩陣，注意基變量對應的系數(shù)矩陣是m階的單位矩陣。 0時，若存在非基變量檢驗數(shù)為0時，則有無窮多解，否則只有唯一最優(yōu)解。利用初等行變換將[5]變?yōu)?，此列其它系數(shù)變?yōu)?，得到新的單純形表（見表18）表18cj23000CBBbX1X2X3X4X5θ0X36[2]0102/530X4164001043X2301001/5σj20003/5注意表中x1為換入變量；依照比值的計算規(guī)則，只有x1的正系數(shù)才有對應的比值，即故變量x3為換出變量，從而元素2為主元（用[]標記），再將[2]變?yōu)?，此列其它系數(shù)變?yōu)?，得到新的單純形表（見表19）表19cj23000CBBbX1X2X3X4X5θ2X13101/201/50X4400214/53X2301001/5σj00101/5表19中所有檢驗數(shù)均非正，得到最優(yōu)解X=(3,3,0,4,0)T,zmax=15,進一步由于非基變量的檢驗數(shù)全小于0，該問題是唯一最優(yōu)解。對應的約束方程組為：為使兩個方程組等價，常稱為罰因子（其中M為任意大的正數(shù)）。第一階段的作用是判斷原線性規(guī)劃問題是否存在可行解。當任取一個對應的變量為換出變量時，則下一張表中有基變量的值等于0，這種現(xiàn)象稱為退化。解：在圖解法中已看到本例有無窮多最優(yōu)解，用單純形法求解時，先化為標準形式列單純形表如下cj22000CBBbX1X2X3X4X5θ0X3122210060X416[4]001040X51505001σj220000X340[2]11/2012X141001/400X515050013σj 0201/202X22011/21/402X141001/400X55005/25/41σj00100表中所有檢驗數(shù)均非正且無人工變量，得到最優(yōu)解X(1)=(4,2,0,0,5)T,zmax=12,進一步由于非基變量x4的檢驗數(shù)等于0，取x4作為換入變量，繼續(xù)用單純形法計算如下：cj22000CBBbX1X2X3X4X5θ2X22011/21/402X141001/40160X55005/2[5/4]14σj001002X2301001/52X13101/201/50X4400214/5σj00100表中所有檢驗數(shù)均非正且無人工變量，得到另一個最優(yōu)解X(2)=(4,2,0,0,5)T,zmax=12,連接X(1)和X(2)的線段上的點也都是最優(yōu)解。將經(jīng)濟管理領(lǐng)域的實際問題抽象為數(shù)學模型，這是一項極具創(chuàng)造性和技巧性的工作，既要求能熟練地掌握運用有關(guān)的數(shù)學知識，又要求對所研究經(jīng)濟對象的本質(zhì)有深刻的理解，同時還需要相關(guān)方面的專業(yè)人員的互相配合和通力合作。P為50kg。 ，其中x4，x5，x6是松弛變量。112a211表1x1x2x3x4x5x46(b)(c)(d)10x5113(e)01cjzj(a)1200表2x1x2x3x4x5x1(f)(g)211/20x54(h)(i)11/21cjzj07(j)(k)(l)設最優(yōu)解為X*，當C變?yōu)闀r，最優(yōu)解為，求證：。，其結(jié)構(gòu)尺寸如圖11所示。每一個線性規(guī)劃必然有與之相伴而生的另一個線性規(guī)劃問題，這就是對偶問題。IN39。= B1，其中B1是初始表中基變量在最終表對應的系數(shù)矩陣。注意以上討論中的最終單純形表可相應替換為單純形法迭代過程中任何一步的單純形表。在市場競爭的時代，常山廠的最佳決策顯然應符合以下兩條：二、對稱形式的對偶問題將滿足下列條件的線性規(guī)劃問題及其對偶問題稱為具有對稱形式（或典式）：具有對稱形式的原問題和對偶問題，滿足變量均為非負數(shù)，當目標函數(shù)求極大值時約束條件均取≤（簡稱為“大目標小約束”），而當目標函數(shù)求極小值時約束條件均取≥號（簡稱為“小目標大約束”）。 寫出下列問題的對偶問題。= CB CB B1B。也可以敘述為，若對偶問題有無界解，則原問題無可行解。即 s = C CB B1 A 163。性質(zhì)5 互補松弛性證明：注意：通常把最優(yōu)解中的非零變量稱為松變量，而為0變量稱為緊變量；將最優(yōu)解代入約束條件中成為嚴格不等式的稱為松約束，而成為嚴格等式的稱為緊約束。 若原問題是非可行解，而對偶問題是可行解，則相應解代入目標函數(shù)后有z：一對互補的基解代入目標函數(shù)原問題可行解非可行解對偶問題可行解最優(yōu)解zzmax非可行解zzmax不確定第四節(jié) 影子價格從上節(jié)對偶問題的基本性質(zhì)看出，在單純形法的每一步迭代中有一對互補的基解，代入目標函數(shù)有其中bi是線性規(guī)劃原問題約束條件的右端項，表示第i種資源的擁有量；而對偶變量yi的意義表示對一個單位的第i種資源的估價，這種估價不是資源的市場價格，而是根據(jù)資源在生產(chǎn)中做出的貢獻而作出的估價，為區(qū)別起見稱為第i種資源的影子價格（shadow price）.資源的市場價格只隨市場的供求關(guān)系變化，在企業(yè)內(nèi)通常是穩(wěn)定的；而它的影子價格則有賴于資源的利用情況。由對偶問題的互補松弛性知在最優(yōu)配置下，若資源bi未得到充分利用，則影子價格yi為0；若影子價格yi大于0，則表明該資源bi在生產(chǎn)中已經(jīng)耗費。第五節(jié) 對偶單純形法一、對偶單純形法的基本思路對偶單純形法是求解線性規(guī)劃的另一種基本方法。二、對偶單純形法的計算步驟 化線性規(guī)劃問題的約束條件為≤形式，且引入松弛變量建立初始單純形表；若所有右端常數(shù)項bi≥0，則最優(yōu)解已經(jīng)達到，否則令，即選取bl所對應的變量為換出基的變量（簡稱換出變量）；計算比值，并選取所對應的變量為換入基的變量（簡稱為換入變量）；稱為主元素或主元，常用方括號[ ]標記，利用主元進行迭代，即通過矩陣的初等行變換，把xk所對應的列向量變?yōu)閱挝涣邢蛄浚粗髟猘ik變?yōu)?，同列中其它元素變?yōu)?，轉(zhuǎn)第2 步。因此對偶單純形法一般不單獨使用，而主要應用于下一節(jié)將要介紹的靈敏度分析中。通常將需要進行分析的參數(shù)分成三組：cj ——目標函數(shù)系數(shù)的變化，即市場條件的改變； bi ——約束右端項的變化，即資源擁有量的改變；Pj ——約束左端系數(shù)的變化，即工藝技術(shù)條件的改變。（1）cj的變化：利用公式計算或直接反映到最終表中，即重新計算檢驗數(shù)。（5）增加新工序：即增加一個約束條件，直接反映到最終表中。若基變量的取值沒有負數(shù)，則原問題的基解是可行解；若檢驗數(shù)沒有正數(shù)，則對偶問題的基解是可行解。=B1（b+△b） = B1 b+ B1△b = b180。當線性規(guī)劃問題中的一個或者幾個參數(shù)變化時，可以用單純形從頭計算，看最優(yōu)解有無變化，這樣做思路簡單，但計算很麻煩。對后一種情況的判斷準則是：當某個基變量的取值br小于0時，這一行所有的系數(shù)都非負即arj≥0(j=1,2,...,n)，此時不妨假設對應的第r行的約束方程為：因為arj≥0(j=m+1,...,n),且br0,所有不可能存在滿足xj≥0(j=1,2,...,n)的解。 0，即保證對偶問題為可行解。單純形法可以解釋為：在保持原問題可行性的前提下，使目標函數(shù)值不斷增大，向?qū)ε紗栴}可行解的方向迭代。用影子價格解釋檢驗數(shù)的經(jīng)濟意義。影子價格是一種邊際價格。因此互補松弛性也稱為“由松得緊性”。 C令 CBB1 = Y* T，有 Y*T A 179。即若原問題無可行解，則對偶問題可能無可行解，也可能有無界解，也可以統(tǒng)稱為對偶問題無最優(yōu)解。常稱CB B1為單純形乘子，記作YT，即YT=CB B1，則YT滿足下列關(guān)系：從而說明最終表中檢驗數(shù)行的相反數(shù)恰好是對偶問題的一個可行解，將這個解YT代入對偶問題的目標函數(shù)值，有w=YTb= CB B1b= CB XB=z。：第三節(jié) 對偶問題的基本性質(zhì) 在本節(jié)討論中，設原問題和對偶問題是如下對稱形式的：下面將利用單純形法計算的矩陣描述，分析單純形法的迭代過程中體現(xiàn)的原問題和對偶問題之間變量的對應關(guān)系，再介紹對偶問題的基本性質(zhì)。在對稱形式下，二者的聯(lián)系與區(qū)別如下：（1）原目標求極大值，對偶目標求極小值；（2）原約束的個數(shù)=對偶變量的個數(shù)，原變量的數(shù)=對偶約束的個數(shù)，而且原約束決定對偶變量，原變量決定對偶約束；（3）原約束全≤方向，對偶約束全≥方向；（4）原目標的系數(shù)對應對偶約束的