【正文】 標(biāo)準(zhǔn)形式和解的性質(zhì) 線性規(guī)劃的標(biāo)準(zhǔn)形式\在不同情況下，歸結(jié)出來的線性規(guī)劃問題可能多種多樣，在目標(biāo)函數(shù)和約束條件上也可能各有不同。盡管圖解法只能解決含有兩個決策變量的線性規(guī)劃問題，但從它的解題思路和幾何直觀上得到了線性規(guī)劃問題的若干規(guī)律，對之后介紹求解一般線性規(guī)劃問題的代數(shù)方法——單純形法很有啟示：(1) 求解線性規(guī)劃問題時，解有四種情況：唯一最優(yōu)解、無窮多最優(yōu)解（也稱為多重最優(yōu)解）、無界解（也稱為有可行解但無最優(yōu)解）和無可行解。解 用圖解法求解，如圖14所示，該問題的可行域上方無邊界，目標(biāo)函數(shù)等值線沿著優(yōu)化方向可以無限延伸，使得目標(biāo)函數(shù)值無限增大。此時唯一切點即為最優(yōu)解，這個切點是凸五邊形的一個頂點，如圖12所示。注意在實際意義中決策變量的取值一般為非負(fù)實數(shù)。一般地，假設(shè)線性規(guī)劃數(shù)學(xué)模型有n個決策變量，分別用xj（j=1,2…,n）表示。同理得到類似的不等式；。第一節(jié) 線性規(guī)劃的基本概念 線性規(guī)劃的數(shù)學(xué)模型 線性規(guī)劃問題通常有兩大類型：一類是在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最大的經(jīng)濟效益（如產(chǎn)量最多或利潤最大等）；另一類是當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源 （如資金、設(shè)備、原材料、人工或時間等）去完成給定的任務(wù)或目標(biāo)?，F(xiàn)各舉一例如下：常山機器廠生產(chǎn) I、II 兩型產(chǎn)品。該飼料廠的目標(biāo)是在滿足動物生長需求的情況下，使總的費用為最小。目標(biāo)函數(shù)中變量系數(shù)用cj表示, 通常cj稱為價值系數(shù)。在單純數(shù)學(xué)意義下也可以有決策變量取非正實數(shù)。此問題有唯一最優(yōu)解當(dāng) x1=x2=3 時，Zmax = 15。此時問題有可行解但目標(biāo)函數(shù)值無界，故無最優(yōu)解，常稱之為無界解。(2) 若線性規(guī)劃問題的可行域不是空集，則可行域為凸集。為了討論問題的方便，規(guī)定線性規(guī)劃問題的標(biāo)準(zhǔn)形式如下：（）標(biāo)準(zhǔn)形式的線性規(guī)劃問題中，目標(biāo)函數(shù)為求極大值（有些書上規(guī)定是求極小值），約束條件全為等式，約束條件右端常數(shù)全為非負(fù)值，決策變量的取值必須非負(fù)。松弛變量或剩余變量在實際問題中表示未被利用的資源數(shù)或短缺的資源數(shù)，均未轉(zhuǎn)化為價值和利潤，所以引入到模型后它們在目標(biāo)函數(shù)中的系數(shù)均為零。、xq39?；尚薪?滿足變量非負(fù)取值的基解稱為基可行解(或基本可行解)。設(shè)E是n維向量的集合，X1和X2是E的任意兩點，若X1和X2連線段上的點X=aX1+(1a)X2 (0≤a≤1)仍屬于集合E，則稱E為凸集。0，X2179。,xk的系數(shù)列向量P1,P2,定理2 線性規(guī)劃模型的基可行解對應(yīng)其可行域的頂點。+ (xm+ mdm)Pm=b由 (1)(2)得 (x1 md1)P1+ (x2 md2)P2+ mdj179。 證明：設(shè)X(1)，X(2)，…， X(k)是可行域D的頂點，若X(0)不是頂點，且目標(biāo)函數(shù)在X(0)處達(dá)到最大值Z＊＝C X(0)。一、單純形法的解題思路 因為線性規(guī)劃問題若有最優(yōu)解，則一定可以在基可行解中找到，所以用單純形法求解線性規(guī)劃的基本思想是：先找到一個初始基可行解，若不是最優(yōu)解，則設(shè)法轉(zhuǎn)換到另一個基可行解，并使目標(biāo)函數(shù)值不斷增大，直到找到最優(yōu)解為止（如果有的話）。,bm)T注意：用這個方法確定初始基可行解，必須保證約束條件全是“≤” 。, 0)T ，且前m個分量為正值。一個含有n個決策變量m個約束條件的標(biāo)準(zhǔn)線性規(guī)劃問題，對應(yīng)的單純形表中第一行稱為價值行，用Cj表示，列出每個決策變量在目標(biāo)函數(shù)中的系數(shù)；第二行稱為變量行，列出n個決策變量；最后一行稱為檢驗數(shù)行，列出每個決策變量的檢驗數(shù)（易見基變量的檢驗數(shù)為0）；第一列稱為基價值列，用CB表示，列出每個基變量在目標(biāo)函數(shù)中的系數(shù)；第二列稱為基列（或基變量列），用B或XB表示,列出m個基變量；第三列稱為基解列，用b表示，即每個基變量的取值；最后一列稱為比值列；而中心位置m行n列的矩陣為約束條件的系數(shù)矩陣，注意基變量對應(yīng)的系數(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ù)才有對應(yīng)的比值，即故變量x3為換出變量，從而元素2為主元（用[]標(biāo)記），再將[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)解。對應(yīng)的約束方程組為：為使兩個方程組等價，常稱為罰因子（其中M為任意大的正數(shù)）。第一階段的作用是判斷原線性規(guī)劃問題是否存在可行解。當(dāng)任取一個對應(yīng)的變量為換出變量時，則下一張表中有基變量的值等于0，這種現(xiàn)象稱為退化。解：在圖解法中已看到本例有無窮多最優(yōu)解，用單純形法求解時，先化為標(biāo)準(zhǔn)形式列單純形表如下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ù)學(xué)模型，這是一項極具創(chuàng)造性和技巧性的工作，既要求能熟練地掌握運用有關(guān)的數(shù)學(xué)知識，又要求對所研究經(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)設(shè)最優(yōu)解為X*，當(dāng)C變?yōu)闀r，最優(yōu)解為，求證：。，其結(jié)構(gòu)尺寸如圖11所示。每一個線性規(guī)劃必然有與之相伴而生的另一個線性規(guī)劃問題，這就是對偶問題。IN39。= B1，其中B1是初始表中基變量在最終表對應(yīng)的系數(shù)矩陣。注意以上討論中的最終單純形表可相應(yīng)替換為單純形法迭代過程中任何一步的單純形表。在市場競爭的時代，常山廠的最佳決策顯然應(yīng)符合以下兩條：二、對稱形式的對偶問題將滿足下列條件的線性規(guī)劃問題及其對偶問題稱為具有對稱形式（或典式）：具有對稱形式的原問題和對偶問題，滿足變量均為非負(fù)數(shù)，當(dāng)目標(biāo)函數(shù)求極大值時約束條件均取≤（簡稱為“大目標(biāo)小約束”），而當(dāng)目標(biāo)函數(shù)求極小值時約束條件均取≥號（簡稱為“小目標(biāo)大約束”）。 寫出下列問題的對偶問題。= CB CB B1B。也可以敘述為，若對偶問題有無界解，則原問題無可行解。即 s = C CB B1 A 163。性質(zhì)5 互補松弛性證明：注意：通常把最優(yōu)解中的非零變量稱為松變量，而為0變量稱為緊變量；將最優(yōu)解代入約束條件中成為嚴(yán)格不等式的稱為松約束，而成為嚴(yán)格等式的稱為緊約束。 若原問題是非可行解，而對偶問題是可行解，則相應(yīng)解代入目標(biāo)函數(shù)后有z：一對互補的基解代入目標(biāo)函數(shù)原問題可行解非可行解對偶問題可行解最優(yōu)解zzmax非可行解zzmax不確定第四節(jié) 影子價格從上節(jié)對偶問題的基本性質(zhì)看出，在單純形法的每一步迭代中有一對互補的基解，代入目標(biāo)函數(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)達(dá)到，否則令，即選取bl所對應(yīng)的變量為換出基的變量（簡稱換出變量）；計算比值，并選取所對應(yīng)的變量為換入基的變量（簡稱為換入變量）；稱為主元素或主元，常用方括號[ ]標(biāo)記，利用主元進行迭代，即通過矩陣的初等行變換，把xk所對應(yīng)的列向量變?yōu)閱挝涣邢蛄?，即主元aik變?yōu)?，同列中其它元素變?yōu)?，轉(zhuǎn)第2 步。因此對偶單純形法一般不單獨使用，而主要應(yīng)用于下一節(jié)將要介紹的靈敏度分析中。通常將需要進行分析的參數(shù)分成三組：cj ——目標(biāo)函數(shù)系數(shù)的變化，即市場條件的改變； bi ——約束右端項的變化，即資源擁有量的改變；Pj ——約束左端系數(shù)的變化，即工藝技術(shù)條件的改變。（1）cj的變化：利用公式計算或直接反映到最終表中，即重新計算檢驗數(shù)。（5）增加新工序：即增加一個約束條件，直接反映到最終表中。若基變量的取值沒有負(fù)數(shù)，則原問題的基解是可行解；若檢驗數(shù)沒有正數(shù)，則對偶問題的基解是可行解。=B1（b+△b） = B1 b+ B1△b = b180。當(dāng)線性規(guī)劃問題中的一個或者幾個參數(shù)變化時，可以用單純形從頭計算，看最優(yōu)解有無變化，這樣做思路簡單，但計算很麻煩。對后一種情況的判斷準(zhǔn)則是：當(dāng)某個基變量的取值br小于0時，這一行所有的系數(shù)都非負(fù)即arj≥0(j=1,2,...,n)，此時不妨假設(shè)對應(yīng)的第r行的約束方程為：因為arj≥0(j=m+1,...,n),且br0,所有不可能存在滿足xj≥0(j=1,2,...,n)的解。 0，即保證對偶問題為可行解。單純形法可以解釋為：在保持原問題可行性的前提下，使目標(biāo)函數(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代入對偶問題的目標(biāo)函數(shù)值，有w=YTb= CB B1b= CB XB=z。：第三節(jié) 對偶問題的基本性質(zhì) 在本節(jié)討論中，設(shè)原問題和對偶問題是如下對稱形式的：下面將利用單純形法計算的矩陣描述，分析單純形法的迭代過程中體現(xiàn)的原問題和對偶問題之間變量的對應(yīng)關(guān)系，再介紹對偶問題的基本性質(zhì)。在對稱形式下，二者的聯(lián)系與區(qū)別如下：（1）原目標(biāo)求極大值，對偶目標(biāo)求極小值；（2）原約束的個數(shù)=對偶變量的個數(shù)，原變量的數(shù)=對偶約束的個數(shù)，而且原約束決定對偶變量，原變量決定對偶約束；（3）原約束全≤方向，對偶約束全≥方向；（4）原目標(biāo)的系數(shù)對應(yīng)對偶約束的