PAGE21對偶規劃及其應用問題研究1緒論························································11.1研究背景及意義···········································11.2國內外研究現狀···········································12對偶規劃····················································22.1對偶問題·················································22.2對偶單純形法·············································52.3對偶理論···············································112.4對偶問題的靈敏度分析····································123對偶規劃的應用··············································153.1影子價格················································153.2對偶規劃應用實例分析···································164結語························································21參考文獻·····················································22對偶規劃及其應用摘要：對偶規劃是線性規劃的重要組成部分，對偶問題和原問題之間有著密不可分的關系，其理論和實際應用都具有重要研究意義，對偶規劃在經濟、工業、生產、軍事等方面都起到了不可取代的作用.本文主要對對偶問題、對偶單純形進行系統闡述，對對偶規劃的靈敏度進行分析，并以具體問題為例，更直觀地說明對偶規劃及其在應用方面的指導作用.關鍵詞：對偶規劃，對偶理論，對偶單純形法，靈敏度分析,影子價格.1緒論1.1研究背景及意義對偶思想最早出現于1928年，數學家JohnvonNeumann在對博弈論進行研究之時，認為二人零和博弈可以用線性規劃的原始問題及對偶問題表示出來.直至1939年，蘇聯數學家LeonidV.Kantorovich初次總結生產中的一系列問題，例如最好地利用原料、當地材料、燃料及運輸能力等問題，都屬于同一種數學問題即極值問題，而他所首創的解乘數法恰能求解這類問題.這種方法對于現代應用數學具有劃時代的意義，開創了解決線性規劃問題的先河.經過對對偶問題數年的不懈鉆研，JohnvonNeumann于1947年提出對偶理論，此后，線性規劃和對偶理論的發展進程得到了極大的推動，對偶規劃的理論和解法不斷向更深更廣的方向延伸，且廣泛應用在現實生活中的方方面面.線性規劃旨在研究取之有限的資源如何在有競爭的系統中如何分配才是最優的問題，而對偶理論占據線性規劃研究中重要的一角.線性規劃原問題和對偶問題之間有著千絲萬縷的關系，并且具有研究價值.當面臨復雜的原問題時，先求解其對偶問題為求解線性規劃問題提供了一定的便利.對偶問題的最優解對深入解釋線性規劃模型經濟含義起重要作用.對偶解的經濟含義是影子價格，影子價格的實質是對系統資源價格的估計，它可以應用于經濟管理中，是一個重要的參考指標.此外，對偶規劃在資源利用、生產方案、原料配比等方面也有重要作用.1.2國內外研究現狀1.2.1國內研究現狀國內對對偶問題的研究較晚，對于對偶問題的研究偏重于對實際的應用.1964年林詒勛[1]在前人已經奠定的線性規劃基礎之上，參考線性方程組的Fredholm定理，得到另一種求解辦法.1978年林銼云[2]對非線性規劃的對偶理論進行研究.王長鈺[3]將凸對偶規劃應用于運價為凸函數的運輸問題并研究其解的情況.1981年胡幼青[4]對對偶規劃的經濟含義影子價格做出了較為全面的介紹.此后，魏力仁[5]，劉序球[6]等人對對偶規劃的經濟應用做了進一步研究.1986年顧新華、連成平[7]運用對偶原理研究國民經濟控制,基于對偶系統指標，給出最優價格制定的模型.2003年，梁治安[8]研究多目標分式規劃的對偶模型并得到了相應的對偶定理.2020年，岳東萍[9]對廣義高階不變凸目標規劃的對偶性做研究，給出對偶性結果.1.2.2國外研究現狀1951年D.Gale，H.W.Kuhn，A.W.Tucher[10]首次提出了線性規劃的對偶模型，證明了對偶定理.1953年TjallingC.Koopmans[11]首次成功將線性規劃引入生產分析.不同于傳統生產和價格理論，他把各種可以使用的生產方法及其使用的程度作為決策變量，推動了資源分配最優理論向前發展.1954年對偶單純形法由數學家C.Lemke提出，就在同一年，S.Gass和T.Sadi研究并解決了參數規劃問題及完成了靈敏度分析的研究證明.1956年A.Tucher提出線性規劃中的一條重要定理——互補松弛定理.1962年DuffinR.J.1970年ElmorL.Peterson[12]通過研究Duffin原始公式的對偶無約束幾何規劃，為理解集合對偶問題的經濟學解釋提供了一種新的思路，給出最優解的存在性和唯一性的相關新定理.1972年V.A.Sposito[13]研究消去目標函數的下界的線性規劃及其對偶線性規劃，并給出了顯式最優解.1974年A.L.Soyster[14]拓展了凸規劃的概念，將目標向量替換為凸集，并公式化對偶問題.1981年G.R.Bitran[15]對非線性多目標優化問題建立了對偶理論，并提出了對偶矩陣的經濟解釋.1998年G.Giorgi,A.Gucrraggio[16]對廣義不變凸向量函數的光滑和非光滑多目標規劃進行研究，得到了一些對偶結果.近年來，許多人研究隨機動態規劃等較為復雜的問題.2020年，VincentGuigues[17]對凸非線性優化問題的隨機對偶動態規劃進行研究，對動態對偶規劃算法進行推廣，并應用于市場上投資組合的選擇和操作.2對偶規劃2.1對偶問題線性規劃原問題和對偶問題相伴存在，兩者有著千絲萬縷的關系.實際上，這兩個問題可以看成從待解決問題的不同角度出發建立模型所得到的目標和約束條件.例2.1.1水泥廠為生產甲、乙、丙三種不同品質的水泥需要用到A、B、C、D四種石料，具體要求如下表：表1石料水泥ABCD單件產品收益甲32112000乙41324000丙22343000原材料總量600400300200先考慮使收益最大時的生產安排.設生產甲、乙、丙的數目分別為、、.則模型表示為：..（2.1）現考慮另一種情況：水泥廠決定不安排生產任務，而將廠內所有石料全部出售，此時工廠需要定下一個合理的原材料價格，使原材料價格盡可能低，同時保證工廠收益不減少.在此情況下，設水泥廠擁有的石料A、B、C、D的價格分別為、、、.則此時模型為：..（2.2）上述例子所得的模型（2.1）和模型（2.2）互為原問題和對偶問題.對比兩者可以看出，它們之間存在緊密聯系：其中一個問題求目標值最大，另一個求目標值最小；兩個問題目標函數系數和約束條件的右邊互相對應；其中一個問題約束條件左邊的系數矩陣是另一個問題的轉置[18].下面給出對偶問題的一般表現形式.設線性規劃問題..（2.3）則對應的對偶問題為..（2.4）（2.3）和（2.4）可以簡寫為：....（2.5）其中，，，，是一個階的矩陣.2.2對偶單純形法單純形法是一種用來求解線性規劃問題的常用方法.首先引入一些定義.可行解是滿足線性規劃全部約束條件的向量[18].對給定線性規劃問題：，其中是一個階的矩陣且.將分為一個階方陣和一個階矩陣，且.則可以表示為.將也作對應的分割，表示為,其中稱為基變量，表示作對應分割后矩陣中相對應的個的分量；稱為非基變量，表示矩陣中相對應的個的分量.從而方程組可以表示為.（2.6）又因為可逆，可得，（2.7）則.特別地，令，得到（2.8）稱為基本解.若基本解滿足非負可行，即，（2.9）則稱其為基本可行解[19].單純形法的原理是在解一直可行的情況下，將一個可行解通過替換基變量得到新的可行解，此過程不斷迭代進行下去，直到每一個檢驗數都非正為止，就能得到線性規劃的最優解.矩陣依照上述方法分解后，線性規劃可以寫為..（2.10）.將（2.7）代入目標函數得（2.11）.令，可得，.若滿足，則是一個基本可行解.在上式（2.11）中，稱為檢驗向量，它的一個分量稱為檢驗數，可以表示為，，為非基變量下標的集合.根據檢驗數的取值可以判斷解是否為最優解.定理2.2.1設是一個可行基，是基本可行解，若滿足檢驗數，，則是一個最優解[18,20].證明：對應的目標函數值為.設是任一可行解，由、，可得.所以是最優解.若得到的解為最優解，即線性規劃問題已然得到解決，若不是最優解，則要進行換基迭代.這就要通過一些計算確定需要變化的基變量和非基變量，得到另一個基.若結果不是最優解，檢驗數中至少有一個大于零.只選擇非基變量中一個變量成為基變量，其余非基變量仍為零，則有.因為所有的基變量大于等于零，所以有.（2.12）又因為，，只有當時，式（2.12）才有可能不成立，所以有.設，（2.13）這稱為確定出基變量的檢驗準則，設經過檢驗后確定第個基變量出基，即.令入基變量，改變后的基變量為（2.14）改變后的目標函數為（2.15）得到新的基和目標函數后，再檢驗其最優性，循環此步驟直至得到最優解，這就是單純形法的過程.基于單純形法，對于原問題的單純形法的原理可以解釋為：保持原問題的解始終可行，由一個基本可行解不斷迭代，當其對偶問題的解從不可行轉變為可行時終止計算，原問題的最優解就是終止時原問題的可行解.因為原問題和對偶問題特殊的對稱性，所以對偶單純形法可以解釋為：保持對偶問題的解始終可行，由一個基本可行解不斷迭代，當原問題的解從不可行轉變為可行時終止計算，對偶問題的最優解就是終止時對偶問題的可行解.根據這一思路，就能完善對偶單純形法的詳細過程.設對偶問題已經得到一個對偶可行解，對這個解進行更新迭代.由（2.9）可知，當條件成立時，原問題的解是可行解，因此最優性檢驗可能存在以下三種情況：（1）若，則由定理2.2.1可知，該解為最優解.（2）若不成立，則中最少有一個分量.設該分量對應的行向量，其中.①若的所有分量大于等于零，則有.又因為且，所以不可能為正，可知原問題不存在可行解.②若有分量小于零，則此時原問題的解不是可行解，需要進行迭代.替換新基后新的檢驗數和對偶可行條件可以表示為：，（2.16）其中稱為旋轉元，且.由，可得.入基變量的檢驗準則為.（2.17）故只要按照（2.17）選擇入基變量，以為旋轉元進行換基迭代，經過一系列計算，就可以算得原問題的可行解.綜上，對偶單純形法的步驟如下：（1）找到一個初始對偶可行解.（2）檢驗是否為最優解.①若，初始解就是最優解，終止計算.②若，且，則該問題不可行，終止計算.③若，且存在，則應進行換基迭代，跳轉到步驟（3）.（3）確定入基變量.計算，其中.（4）以為旋轉元作旋轉變換，跳轉到步驟（2）.接下來以一個簡單的例子演示對偶單純形法的具體過程.例2.2.1用對偶單純形法求解...解：將此線性規劃標準化得..以、為初始基，為了方便計算，將標準化后的線性規劃的約束條件兩邊乘-1，有..，，,,，則相應的單純形表為表20-2-3-400-3-1-2-110-4-21-301為非可行解，但為對偶可行解.因，所以，則為離基變量.，、，有故，為入基變量.以為旋轉元進行旋轉變換，得到新的單純形表為表340-4-10-1-101210仍為非可行解.因為，所以，則為離基變量.，、，有故，為入基變量.以為旋轉元進行旋轉變換，得到新的單純形表為表4000110，因此最優解為，最優值為.2.3對偶理論由對偶問題的定義式可以得到一些性質，即對偶理論.定理2.3.1設原問題的可行解為，對偶問題的可行解為，則有.證明：由原問題和對偶問題的定義可得，，且，，從而有，即,整理對比得.這個定理也稱為弱對偶定理，它表現了線性規劃原問題和對偶問題的目標函數值具有一定的大小關系，由該定理進一步可以得到對偶定理.定理2.3.2（對偶定理）原問題和對偶問題存在以下關系[18,21]：（1）原問題有最優解的充要條件是對偶問題有最優解.（2）若原問題無界，則對偶問題無可行解，反之，若對偶問題無界，則原問題無可行解.（3）若、分別是原問題和對偶問題的可行解，若滿足，則、分別是原問題和對偶問題的最優解.證明：（1）必要性：設原問題的最優解是，是最優基.由定理2.2.1可推得最優性檢驗條件和.設是對偶問題的一個可行解，令，有，.由定理2.3.1可得，即是對偶問題的一個下界，且對偶問題的可行域是一個非空的閉凸子集，因此必定存在一個最優解滿足上述條件.充分性：由對稱性即可得證.（2）因為原問題與對偶問題具有對稱性，所以僅需證明一條結論即可.下證：若原問題無界，則對偶問題沒有可行解.反證法.假設原問題無界，對偶問題有可行解.由定理2.3.1，原問題的任意可行解有，由該式子可知，就是原問題的一個上界，矛盾.所以若原問題無界，則對偶問題無可行解.（3）充分性：設原問題的可行解為，對偶問題的可行解為，兩者滿足.設、分別是原問題和對偶問題的任意可行解，由定理2.3.1，滿足式子和，可知、分別是原問題和對偶問題的最優解.必要性：設原問題的最優解是，是最優基.由定理2.3.2（1）可知，是對偶問題的一個可行解，有.又由定理2.3.1，有.2.4對偶問題的靈敏度分析建立線性規劃模型時各個參數都是固定的，但現實生活中實際情況復雜多變，各種因素都會影響到數據的準確度，因此，對于對偶問題的靈敏度分析是十分重要的.下面對對偶問題目標函數系數變化和約束條件右邊項系數變化進行靈敏度分析.2.4.1目標函數系數變化的靈敏度分析對目標函數系數變化的靈敏度分析又可以分成非基變量系數變化和基變量系數變化兩種情況.設變化的系數為.（1）是非基變量的系數.設變化量為，若變化后仍保持原來的最優基不變，則需要檢驗數滿足定理2.2.1的條件，即，整理得.所以，在保持最優基不變的情況下，目標函數系數的變化量的取值范圍是.（2.18）變化量的取值落在這個范圍內時，最優基保持不變.變化量在增加的方向有上界，而在下降的方向無界.即是說變化量的大小增加時，對應的系數對目標函數的貢獻隨之增加，當變化量超過這個上界時，最優基就會發生變化.變化量下降時，會隨之減小，不可能大于零，因此最優基不變.（2）是基變量的系數.若是基變量的系數，則的變化會使跟著變化.設的變化量為.若變化后仍保持原來的最優基不變，則需要檢驗數滿足定理2.2.1的條件，即.（2.19）設第個基變量的系數發生變化，其他保持不變，則有,（2.20）.（2.21）將式（2.20）代入式（2.19）有（2.22）此時要分兩種情況討論.情況一：若，當時，式（2.22）可能不成立，所以有.情況二：若，當時，式（2.22）可能不成立，所以有.綜上所述，在保持最優基不變的情況下，目標函數系數的變化量的取值范圍是.（2.23）當變化量的取值落在這個范圍內時，最優基不變，只有目標函數改變，變化量為.若變化量的取值落在這個范圍外，最優基不再是原來的最優基，此時需要進行換基迭代求得最優解.2.4.2約束條件右邊項變化的靈敏度分析.約束條件右邊項的變化只會影響基變量和目標函數，而不影響檢驗數.設右邊項變化量為，發生變化的參數為，則有，.若要使得到的新基可行，則需要保證基變量非負，于是有.（2.24）其中是的第行第列元素.此時也要分兩種情況討論.情況一：若，當時，式（2.24）有可能不成立，所以有.情況二：若，當時，式（2.34）有可能不成立，所以有.綜上所述，在保持最優基不變的情況下，右邊項變化量的取值范圍是.（2.25）當變化量的取值落在這個范圍內時，最優基不變，基變量和目標函數值改變，變化量為.若變化量的取值落在這個范圍外，最優基會發生變化.3對偶規劃的應用3.1影子價格線性規劃討論的是取之有限的資源如何在有競爭的系統中如何分配才是最優的問題.若將模型（2.3）看成線性規劃在經濟活動中的應用，可以看作各種資源的可用量，可以看作每種產品或經濟活動的利潤，可以看作每種產品的產量或經濟活動的體量，目標函數可以看作經濟活動的總利潤[22].線性規劃的求解就是求在各種資源可利用量的限制內資源的最優化分配，對偶問題的解就表示各種資源在系統中所處的狀態及其變動對總利潤的影響，這就是影子價格.影子價格是對系統資源價格的合理估計，不是實際的價格.同時，影子價格是對系統資源價格的最優估計，是系統資源物盡其用，達到最合理分配時的資源價值.而在現實生活中，實際市場價格往往與影子價格不相等.當實際市場價格與影子價格相等時，該資源達到均衡狀態，此時資源得到最優分配.為了達到資源均衡狀態，就要對實際市場價格和影子價格進行比較大小，對資源實施買入或賣出策略，使企業的利潤達到最大.如果實際市場價格比影子價格高，說明該資源的實際價格被過低地估計，此時應該適當購入該資源以獲得更高利潤；如果實際市場價格比影子價格低，說明該資源的實際價格被過高地估計，應該適當拋售該資源.從另一個方面看，影子價格代表著資源是否稀缺及其稀缺程度.有越高影子價格的資源越稀缺[23].影子價格對經濟、生產等方面具有重要意義.其對資源分配有指導性作用，企業決策者可以利用影子價格對企業現有分配方案有更深層的了解，有助于調整企業資源.在企業內外部環境變化的影響下，企業決策者也可以利用影子價格靈活調整對企業的資源，使企業資源得到充分利用，企業利潤獲得最大化.3.2對偶規劃應用實例分析例3.2.1虎丘工廠用A、B兩種原料生產甲、乙兩種產品，具體的生產情況如下表（配比單位為千克/件）：表5產品原料甲乙原料庫存（千克）原料成本（元/千克）A204016001.5B302018002.5售價（元）130160求使銷售利潤最大使的生產分配.解：設生產甲產品件，生產乙產品件，為總利潤，表示為（3.1）建立模型如下：..（3.2）該模型的最優解為，.設原料A的影子價格為，原料B的影子價格為，則模型（3.2）的對偶模型為.（3.3）該模型的解為，.要使利潤最大化，生產的安排應是生產甲產品50件，生產乙產品15件，此時最大利潤為2000元.由對偶規劃的解，，可以知道對偶解的經濟含義為：每增加1千克原料A的供應量，工廠的利潤會增加1.25元；而增加原料B的供應量，工廠的利潤不會發生變化.因為原料A的影子價格為2，所以原料A在生產中屬于稀缺資源，增加原料A的供應量可以使總利潤增加.根據對模型（3.3）的靈敏度分析，當原料A的庫存的允許增加量為2000千克，此時，工廠的總利潤增加元.因為原料B的影子價格為0，所以原料B在生產中處于剩余狀態，那么決策者可以考慮適當改變原料B的庫存，增加工廠的現金流.根據對模型（3.3）的靈敏度分析，原料B的允許減少量為1000，允許增加量為600，即當原料B的庫存大于800且小于2400時，生產方案的最大利潤不變.因此可以減少800千克原料B的庫存，獲得2000元的流動資金.影子價格可以用來預測產品價格.在本例中，若北湖工廠是原料A的供應廠商，原料A的交易價格應該在原料A的影子價格和北湖工廠生產原料A的單位成本之間，才能達到共贏.否則，若交易價格比虎丘工廠原料A的影子價格高，虎丘工廠將不會愿意購買北湖工廠的原料A；若交易價格比北湖工廠的單位成本低，北湖工廠將會虧本.由上述可知，原料A的影子價格為2元，若北湖工廠生產原料A的單位成本為1.5元，則原料A的交易價格應該在1.5元和2元之間.例3.2.2某企業旗下有甲、乙兩種產品，在南京的A、B兩個工廠生產，在工廠加工生產后銷往蘇南和蘇北.企業產品和工廠相關資料如下表.表6出售地區產品類別最大庫存（kg）單價（元）銷售費用（元）銷售費用（元）工廠A工廠B銷往蘇南產品甲1200013312產品乙1000017412銷往蘇北產品甲1500016422產品乙750018512表7工廠產品類別生產成本（元/kg）時間定額（小時）時間限額（小時）第一車間第二車間第一車間第二車間工廠A產品甲71.521300030000產品乙62315000工廠B產品甲721800040000產品乙52.5220000現該企業希望做出一些決策提高企業的總利潤，那么就需要建立對偶規劃，通過影子價格得到啟發.解：設為工廠A生產的將銷往蘇南的產品甲，為工廠B生產的將銷往蘇南的產品甲，為工廠A生產的將銷往蘇北的產品甲，為工廠B生產的將銷往蘇北的產品甲，為工廠A生產的將銷往蘇南的產品乙，為工廠B生產的將銷往蘇南的產品乙，為工廠A生產的將銷往蘇北的產品乙，為工廠B生產的將銷往蘇北的產品乙，為總利潤，表示為（3.4）建立模型如下..（3.5）求解該模型得，，，，，，，.模型（3.5）對應的對偶模型為.（3.6）其中，為銷往蘇南的產品甲的影子價格，為銷往蘇北的產品甲的影子價格，為銷往蘇南的產品乙的影子價格，為銷往蘇北的產品乙的影子價格，在工廠A第一車間生產的產品甲的影子價格，在工廠A第一車間生產的產品乙的影子價格，在工廠A第二車間生產的產品甲、乙的影子價格，在工廠B第一車間生產的產品甲的影子價格，在工廠B第一車間生產的產品乙的影子價格，在工廠B第二車間生產的產品甲、乙的影子價格.求解模型（3.6）得，，，，，，，，，.由影子價格的結果，該企業決策者可以得到一些啟發.由于值最大，所以首要考慮增加銷往蘇北的產品乙的銷售量，這將會提高總利潤；由于，其他銷售安排無需變動，增加它們的銷量對總利潤沒有影響.其次考慮各車間的生產安排.由于，所以首先考慮的是擴大工廠B第一車間生產產品乙的規模，其次是擴大工廠A第二車間生產規模和工廠B第一車間生產產品甲的規模，最后是擴大工廠A第一車間生產產品乙的規模.由于，所以不用擴大工廠A第一車間生產產品甲的規模，這對增加總利潤沒有幫助.4結語在運籌學中，線性規劃對偶問題是一個重要的研究課題，在基礎的對偶問題的基礎上，世界對對偶問題的研究不斷向更深更廣的方向前進.本文主要對對偶問題、對偶單純形法、對偶理論進行系統闡述，分析不同變量的變化對對偶問題的影響，通過實際案例進行分析，具體說明對偶規劃的作用.對偶規劃的理論研究和實際應用都具有不可替代的作用，對人類的生產生活具有重要貢獻.參考文獻[1]林詒勛.線性規劃的對偶理論(Ⅰ)[J].鄭州大學學報(自然科版),1964(01):9-20.[2]林銼云.非線性規劃對偶理論[J].南昌大學學報(理科版),1978(00):77-84.[3]王長鈺.一類凸對偶規劃與運價為凸函數的運輸問題[J].曲阜師院學報(自然科學版),1978(03):17-30.[4]胡幼青.影子價格問題介紹[J].價格理論與實踐,1981(05):51-60.[5]魏力仁,米天林,李伯經.數學規劃中的影子價格[J].湖南財經學院學報，1982(01):100-108.[6]劉序球.對偶規劃問題的經濟分析意義[J].江西財經學院學報,1983(02):90-94.[7]顧新華,連成平.試論國民經濟控制系統的對偶問題[J].自動化學報，1986(04):333-338.[8]Z.A.Liang,H.X.Huang,P.M.Pardalos.E?ciencyconditionsanddualityforaclassofmultiobjectivefractionalprogrammingproblems[J].JournalofGlobalOpti-mization,2003,27:447-471.[9]岳冬萍.廣義高階不變凸多目標規劃的最優性和對偶性[D].西安科技大學,2020.[10]D.Gale,H.W.Kuhn,A.W.Tucker.Linearprogrammingandthetheoryofgames[C].In:Koopamans(Ed)TC,”Activit