線性規(guī)劃原問(wèn)題與對(duì)偶問(wèn)題的轉(zhuǎn)化及其應(yīng)用.doc

線性規(guī)劃原問(wèn)題與對(duì)偶問(wèn)題的轉(zhuǎn)化及其應(yīng)用摘 要線性規(guī)劃對(duì)偶問(wèn)題是運(yùn)籌學(xué)中應(yīng)用較廣泛的一個(gè)重要分支，它是輔助人們進(jìn)行科學(xué)管理的一種數(shù)學(xué)方法.線性規(guī)劃對(duì)偶問(wèn)題能從不同角度為管理者提供更多的科學(xué)理論依據(jù)，使管理者的決定更加合理準(zhǔn)確.本文主要探討了線性規(guī)劃原問(wèn)題與對(duì)偶問(wèn)題之間的關(guān)系、線性規(guī)劃原問(wèn)題與對(duì)偶問(wèn)題的轉(zhuǎn)化以及對(duì)偶理論的應(yīng)用.本文的研究主要是將復(fù)雜的線性規(guī)劃原問(wèn)題轉(zhuǎn)化成對(duì)偶問(wèn)題進(jìn)行解決，簡(jiǎn)化了線性規(guī)劃問(wèn)題，使人們能夠快速的找出線性規(guī)劃問(wèn)題的最優(yōu)解.關(guān)鍵詞：線性規(guī)劃；原問(wèn)題；對(duì)偶問(wèn)題 ；轉(zhuǎn)化Linear Programming is the Original Problem and the Transformation of the Dual Problem and ApplicationsAbstract: Linear programming in operational research is research earlier, rapid development and wide application, the method is an important branch of mature, it is one of the scientific management of auxiliary people mathematical method. Can from different angles to linear programming dual problem for policy makers to provide more scientific theory basis. This article mainly probes into the linear programming problem and the relationship between the dual problem, linear programming problem and the transformation of the dual problem, the application of linear programming dual problem. This article is the complex of the original problem into its dual problem to be solved, simplifies the linear programming problem, enables us to rapidly find the optimal solution of linear programming problem.Keywords: linear programming; the original problem; the dual problem; conversion目 錄1 引言12 文獻(xiàn)綜述12.1 國(guó)內(nèi)外研究現(xiàn)狀12.2 國(guó)內(nèi)外研究現(xiàn)狀評(píng)價(jià)22.3 提出問(wèn)題23 預(yù)備知識(shí)23.1對(duì)稱(chēng)形式的原問(wèn)題23.2 非對(duì)稱(chēng)形式的原問(wèn)題33.3 對(duì)偶問(wèn)題的定義33.4原問(wèn)題轉(zhuǎn)化為對(duì)偶問(wèn)題的理論依據(jù)44 原問(wèn)題與對(duì)偶問(wèn)題的轉(zhuǎn)化54.1 原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系54.2 對(duì)稱(chēng)型原問(wèn)題化為對(duì)偶問(wèn)題64.3 對(duì)稱(chēng)型對(duì)偶問(wèn)題轉(zhuǎn)換為原問(wèn)題94.4 非對(duì)稱(chēng)型原問(wèn)題轉(zhuǎn)化為對(duì)偶問(wèn)題104.5 對(duì)偶問(wèn)題的應(yīng)用135 結(jié)論155.1主要發(fā)現(xiàn)155.2啟示155.3局限性155.4努力方向15參考文獻(xiàn)161 引言線性規(guī)劃問(wèn)題是運(yùn)籌學(xué)里的一個(gè)重要的分支，它的應(yīng)用比較廣泛，因而是輔助人們進(jìn)行現(xiàn)代科學(xué)管理的一種數(shù)學(xué)方法.隨著線性規(guī)劃理論的逐步深入，人們發(fā)現(xiàn)線性規(guī)劃問(wèn)題具有對(duì)偶性，即每一個(gè)線性問(wèn)題都伴有另外一個(gè)線性問(wèn)題的產(chǎn)生，兩者相互配對(duì)，密切聯(lián)系，反之亦然.我們把線性規(guī)劃的這個(gè)特性稱(chēng)為對(duì)偶性.于是，我們將其中的一個(gè)問(wèn)題稱(chēng)為原問(wèn)題，另一個(gè)問(wèn)題則稱(chēng)為它的對(duì)偶問(wèn)題.對(duì)偶性不僅僅是數(shù)學(xué)上的理論問(wèn)題，而且也是線性規(guī)劃中實(shí)際問(wèn)題的內(nèi)在經(jīng)濟(jì)聯(lián)系的必然反映.我們通過(guò)對(duì)對(duì)偶問(wèn)題的深入研究，發(fā)現(xiàn)對(duì)偶問(wèn)題能從不同角度對(duì)生產(chǎn)計(jì)劃進(jìn)行分析，從而使管理者能夠間接地獲得更多比較有用的信息.2 文獻(xiàn)綜述2.1 國(guó)內(nèi)外研究現(xiàn)狀在所查閱到的國(guó)內(nèi)外參考文獻(xiàn)1-15中，有不少文章是探討了原問(wèn)題轉(zhuǎn)化為對(duì)偶問(wèn)題的方法以及對(duì)偶性質(zhì)的證明，并在對(duì)偶理論的應(yīng)用方面有所研究.如郝英奇，胡運(yùn)權(quán)在1、10中主要介紹了線性規(guī)劃中原問(wèn)題與對(duì)偶問(wèn)題中的一些基本概念，探究了實(shí)際問(wèn)題中的數(shù)學(xué)模型以及解.孫君曼，馮巧玲，孫慧君，李淑君等在2中探討了對(duì)偶理論中互補(bǔ)松弛定理在各種情況下的使用方法,使學(xué)生更好地掌握互補(bǔ)松弛定理的含義和應(yīng)用方法.胡運(yùn)權(quán)，郭耀煌，殷志祥等在3、5中系統(tǒng)的介紹了線性規(guī)劃中原始問(wèn)題與對(duì)偶問(wèn)題的兩種形式.郭鵬，徐玖平等在6、8中用不同例子來(lái)說(shuō)明了原問(wèn)題轉(zhuǎn)化為對(duì)偶問(wèn)題的必要性. 崔永新等在9、15中探討了對(duì)偶問(wèn)題的相關(guān)定理以及對(duì)偶問(wèn)題的可行解和最優(yōu)解之間的若干性質(zhì).李師正，王德勝在11中探討了如何用計(jì)算機(jī)計(jì)算對(duì)偶問(wèn)題的最優(yōu)解.岳宏志，藺小林，孫文喻等在12、14中探討了對(duì)偶理論的證明過(guò)程，并用常見(jiàn)的例子來(lái)說(shuō)明對(duì)偶理論的基本思想和解題方法. 曾波，葉宗文在13中主要從經(jīng)濟(jì)管理的實(shí)際問(wèn)題中闡述了線性規(guī)劃的基本概念，基本原理，對(duì)偶理論，靈敏度分析等. 2.2 國(guó)內(nèi)外研究現(xiàn)狀評(píng)價(jià)文獻(xiàn)1-15分別探討了線性規(guī)劃問(wèn)題中原問(wèn)題轉(zhuǎn)化為對(duì)偶問(wèn)題的理論依據(jù)以及如何利用對(duì)偶理論去解決實(shí)際生產(chǎn)問(wèn)題.文獻(xiàn)中主要探討了對(duì)稱(chēng)型的原問(wèn)題轉(zhuǎn)化為對(duì)偶問(wèn)題的方法.沒(méi)有全面介紹非對(duì)稱(chēng)型的原問(wèn)題與對(duì)偶問(wèn)題之間轉(zhuǎn)化的具體步驟，而且文獻(xiàn)中對(duì)原問(wèn)題轉(zhuǎn)化為對(duì)偶問(wèn)題的步驟提及甚少，大都一帶而過(guò)，對(duì)應(yīng)用中存在的問(wèn)題也未給出詳細(xì)深入的說(shuō)明.2.3 提出問(wèn)題在線性規(guī)劃問(wèn)題中,根據(jù)實(shí)際生產(chǎn)中具體情況的需要,我們常常要把原問(wèn)題與它的對(duì)偶問(wèn)題進(jìn)行轉(zhuǎn)換,以解決一些復(fù)雜的線性規(guī)劃問(wèn)題,因而對(duì)偶問(wèn)題的應(yīng)用較為廣泛.但大部分書(shū)籍都只介紹了線性規(guī)劃問(wèn)題的基礎(chǔ)知識(shí)，并沒(méi)有給出原問(wèn)題與對(duì)偶問(wèn)題轉(zhuǎn)換的具體步驟.因此本文主要探討了線性規(guī)劃原問(wèn)題與對(duì)偶問(wèn)題之間轉(zhuǎn)化的具體步驟，體會(huì)不同類(lèi)型原問(wèn)題的轉(zhuǎn)化過(guò)程.3 預(yù)備知識(shí)首先我先簡(jiǎn)單的介紹一些關(guān)于線性規(guī)劃問(wèn)題中的原問(wèn)題和對(duì)偶問(wèn)題的一些基本的知識(shí).3.1對(duì)稱(chēng)形式的原問(wèn)題我們將滿(mǎn)足下列條件的線性規(guī)劃問(wèn)題稱(chēng)之為具有對(duì)稱(chēng)形式的線性規(guī)劃問(wèn)題.這類(lèi)問(wèn)題的變量都具有非負(fù)約束，當(dāng)目標(biāo)函數(shù)求極大值時(shí)，它的約束條件都取“”號(hào)，當(dāng)目標(biāo)函數(shù)求極小值時(shí)它的約束條件均取“”號(hào). 因而，這類(lèi)數(shù)學(xué)模型的特點(diǎn)是：（1）所有的決策變量都是非負(fù)的；（2）所有的約束條件都是“”型；（3）目標(biāo)函數(shù)是最大化類(lèi)型.線性規(guī)劃原問(wèn)題的對(duì)稱(chēng)形式的為： (3.1)3.2 非對(duì)稱(chēng)形式的原問(wèn)題不是所有的線性規(guī)劃問(wèn)題都具有對(duì)稱(chēng)的形式，我們將沒(méi)有對(duì)稱(chēng)形式的線性規(guī)劃問(wèn)題稱(chēng)之為非對(duì)稱(chēng)形式的線性規(guī)劃問(wèn)題.非對(duì)稱(chēng)形式的線性規(guī)劃問(wèn)題指的是一般情況下的線性規(guī)劃問(wèn)題，即是目標(biāo)函數(shù)值求極小或者求極大；約束條件,=,；變量0,0，或是無(wú)限制的隨意的組合.例如： (3.2)3.3 對(duì)偶問(wèn)題的定義在運(yùn)籌學(xué)中，關(guān)于對(duì)線性規(guī)劃的對(duì)偶規(guī)劃給出的如下.設(shè)給定的線性規(guī)劃為： (3.2)其中，因此，定義它的對(duì)偶問(wèn)題為： (3.4)其中是行向量. (3.4)是對(duì)偶問(wèn)題，(3.3)是原問(wèn)題，(3.3)與(3.4)合在一起我們就稱(chēng)為是一對(duì)對(duì)稱(chēng)形式的對(duì)偶規(guī)劃問(wèn)題.3.4原問(wèn)題轉(zhuǎn)化為對(duì)偶問(wèn)題的理論依據(jù)我們根據(jù)線性規(guī)劃問(wèn)題中約束條件和變量的對(duì)應(yīng)關(guān)系，統(tǒng)一歸納為下所示：項(xiàng)目原問(wèn)題（對(duì)偶問(wèn)題）對(duì)偶問(wèn)題（原問(wèn)題）約束系數(shù)矩陣約束系數(shù)矩陣的轉(zhuǎn)置約束條件右端項(xiàng)向量目標(biāo)函數(shù)中的價(jià)格系數(shù)向量目標(biāo)函數(shù)中的價(jià)格系數(shù)向量約束條件右端項(xiàng)向量目標(biāo)函數(shù)表14 原問(wèn)題與對(duì)偶問(wèn)題的轉(zhuǎn)化一對(duì)對(duì)偶的線性規(guī)劃問(wèn)題表示了同一個(gè)問(wèn)題的兩個(gè)側(cè)面，是從兩個(gè)角度對(duì)同一個(gè)研究對(duì)象提出的極值問(wèn)題，兩類(lèi)極值的問(wèn)題都具有相同的目標(biāo)函數(shù)值.我們發(fā)現(xiàn)在很多時(shí)候求解對(duì)偶問(wèn)題比原問(wèn)題更加容易，為決策者提供更多的科學(xué)理論依據(jù)，因此我們常常需要把原問(wèn)題轉(zhuǎn)化為對(duì)偶問(wèn)題.4.1原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系一對(duì)對(duì)偶的線性規(guī)劃問(wèn)題具有相互對(duì)應(yīng)的關(guān)系：（1）原問(wèn)題中的目標(biāo)函數(shù)值是，約束條件是“”的形式；對(duì)偶問(wèn)題的，的形式.（2）原問(wèn)題的價(jià)值系數(shù)和對(duì)偶問(wèn)題的右端項(xiàng)對(duì)應(yīng)，原始問(wèn)題的右端項(xiàng)和對(duì)偶問(wèn)題的價(jià)值系數(shù)對(duì)應(yīng).（3）原問(wèn)題的變量和對(duì)偶問(wèn)題的約束條件對(duì)應(yīng)，即，原問(wèn)題中有變量，那么對(duì)偶問(wèn)題就有約束條件；原問(wèn)題有約束條件，那么對(duì)偶問(wèn)題就有變量.（4）對(duì)偶問(wèn)題的系數(shù)矩陣就是原問(wèn)題的系數(shù)矩陣的轉(zhuǎn)置.用矩陣表示，原問(wèn)題為：則對(duì)偶問(wèn)題為：需要注意的是，我們所討論的對(duì)偶問(wèn)題一定是指一對(duì)問(wèn)題，而原問(wèn)題和對(duì)偶問(wèn)題是相對(duì)的，它們互為對(duì)偶問(wèn)題，一個(gè)問(wèn)題可以是原問(wèn)題也可以是對(duì)偶問(wèn)題.4.2 對(duì)稱(chēng)型原問(wèn)題轉(zhuǎn)化為對(duì)偶問(wèn)題當(dāng)線性規(guī)劃問(wèn)題為一般形式（3.1）時(shí)，我們將根據(jù)下面的四條規(guī)則轉(zhuǎn)換為它的對(duì)偶問(wèn)題：（1）原問(wèn)題和它的對(duì)偶問(wèn)題之間的系數(shù)矩陣互為轉(zhuǎn)置.（2）原問(wèn)題中變量的個(gè)數(shù)等于它的對(duì)偶問(wèn)題的約束條件的個(gè)數(shù).（3）原問(wèn)題的右端常數(shù)就是對(duì)偶問(wèn)題的目標(biāo)函數(shù)的系數(shù).（4）原問(wèn)題的目標(biāo)函數(shù)求極大時(shí)，約束條件是“”類(lèi)型，而它的對(duì)偶問(wèn)題的目標(biāo)函數(shù)求極小，約束條件則為“”類(lèi)型.因此，它的對(duì)偶問(wèn)題可以轉(zhuǎn)變?yōu)槿缦碌模豪? 生產(chǎn)計(jì)劃問(wèn)題云南一公司加工生產(chǎn)甲，乙兩種產(chǎn)品，它的市場(chǎng)前景非常的好，銷(xiāo)路也不成問(wèn)題，各種制約因素主要有技術(shù)工人、設(shè)備臺(tái)時(shí)和原材料供應(yīng).已知制造每噸產(chǎn)品的資源消耗系數(shù)、每天的資源限量和售價(jià)等參數(shù)如表2所示.問(wèn)題：云南的這家公司應(yīng)該怎樣制定每天的生產(chǎn)計(jì)劃，才能使它的產(chǎn)量得到最大？甲產(chǎn)品乙產(chǎn)品資源限量人力86320設(shè)備68260原材料410300售價(jià)（元/公斤）90150表2分析：為了建立此問(wèn)題的數(shù)學(xué)模型，第一，要選定決策變量.第二，要確定問(wèn)題的目標(biāo)，即用來(lái)評(píng)價(jià)不同方案優(yōu)劣的標(biāo)準(zhǔn)，這種目標(biāo)總是決策變量的函數(shù)，稱(chēng)為目標(biāo)函數(shù).第三，我們把要確定達(dá)到目標(biāo)時(shí)所受的限制條件，稱(chēng)之為約束條件.這里要決策的問(wèn)題是，在現(xiàn)有人力、設(shè)備、礦石的限制下，如何確定產(chǎn)量使得產(chǎn)值自大？設(shè)和分別表示該公司A，B產(chǎn)品的數(shù)量，用z表示產(chǎn)值，則每天的產(chǎn)值表示為，使其最大化，即，稱(chēng)為目標(biāo)函數(shù).將制約因素表達(dá)出來(lái)，即有：人力不超過(guò)320工時(shí)，為；設(shè)備不超過(guò)260臺(tái)時(shí)有，；原材料不超過(guò)300公斤有，。表述限制條件的數(shù)學(xué)表達(dá)式稱(chēng)為約束條件，由此該問(wèn)題的數(shù)學(xué)模型可表示為：上面的問(wèn)題是一個(gè)典型的求解利潤(rùn)最大化的生產(chǎn)計(jì)劃的問(wèn)題.題中，“”是 “maximize”的縮寫(xiě)，意思是“最大化”；“”是”subject to”單詞的縮寫(xiě)，表示“滿(mǎn)足于”.因此，上述模型的含義是：在給定的條件限制下，求出使目標(biāo)函數(shù)值達(dá)到最大的的值.從數(shù)學(xué)模型中看出，上面的例題具有下面的三個(gè)特征：(1) 用一組決策變量表示問(wèn)題的一個(gè)方案，決策變量的一組取值代表一個(gè)具體的方案.通常狀況下，決策變量的取值是非負(fù)的，部分情況下，還要求決策變量取值為整數(shù).(2) 每個(gè)問(wèn)題都有一個(gè)目標(biāo)，而且都可以用決策變量的線性函數(shù)表示.根據(jù)問(wèn)題的不同，要求目標(biāo)實(shí)現(xiàn)最大或者最小.(3) 決策變量都滿(mǎn)足一定的約束條件，而且都可以用決策變量的線性等式或者不等式表示.具備以上三個(gè)要素的問(wèn)題稱(chēng)為線性規(guī)劃問(wèn)題，簡(jiǎn)單地講，線性規(guī)劃問(wèn)題就是求一個(gè)線性目標(biāo)函數(shù)在滿(mǎn)足一組線性等式（或不等式方程）約束條件下的極值問(wèn)題.例2 云南一公司加工生產(chǎn)甲，乙兩種產(chǎn)品，市場(chǎng)前景非常的很好，銷(xiāo)路也不成問(wèn)題，各種制約因素主要有技術(shù)工人、設(shè)備臺(tái)時(shí)和原材料供應(yīng).已知制造每噸產(chǎn)品的資源消耗系數(shù)、每天的資源限量和售價(jià)等參數(shù)如表3所示.現(xiàn)在公司有意轉(zhuǎn)換經(jīng)營(yíng)方式，現(xiàn)在將各種資源出租轉(zhuǎn)讓?zhuān)覀兗俣ㄊ袌?chǎng)廣闊.問(wèn)題：公司轉(zhuǎn)讓資源的價(jià)格底線是什么？甲產(chǎn)品乙產(chǎn)品資源限量人力86320設(shè)備68260原材料410300售價(jià)（元/公斤）90150表3我們將例1叫做原問(wèn)題，將例2叫做對(duì)偶問(wèn)題.原問(wèn)題的數(shù)學(xué)模型是： (4.1)分析：現(xiàn)在在對(duì)偶問(wèn)題中我們需要考慮的是，將例題中的三種資源租讓或者轉(zhuǎn)出，應(yīng)該是不少于原來(lái)的收益的，否則這家公司寧愿選擇自己繼續(xù)生產(chǎn).所以，決策的約束條件應(yīng)該是：出租制造的產(chǎn)品消耗掉的資源不能少于自己生產(chǎn)該產(chǎn)品的收益；目標(biāo)函數(shù)應(yīng)該是：資源轉(zhuǎn)讓的收益底線.所以，我們?cè)O(shè)，分別為人力、設(shè)備臺(tái)時(shí)和原材料的轉(zhuǎn)讓或者出租的價(jià)格.由于生產(chǎn)1公斤A產(chǎn)品需消耗8個(gè)工時(shí)，6個(gè)臺(tái)時(shí)和4公斤的原材料，可創(chuàng)造產(chǎn)值90元.所以出讓生產(chǎn)A產(chǎn)品資源至少應(yīng)帶來(lái)90元的產(chǎn)值，即 同理，生產(chǎn)1公斤B產(chǎn)品需耗時(shí)4個(gè)工時(shí)，6個(gè)臺(tái)時(shí)和8公斤的原材料，可創(chuàng)造產(chǎn)值150元，出讓這些資源所獲得的銷(xiāo)售收益應(yīng)滿(mǎn)足上面兩個(gè)不等式保證了“出售”資源所獲得的收益不低于自己組織生產(chǎn)所能創(chuàng)造的收益.但是也不能隨意要價(jià)，否則由于市場(chǎng)的調(diào)節(jié)作用將會(huì)使資源賣(mài)不出去.因此目標(biāo)函數(shù)應(yīng)該是表達(dá)所獲的收益的底線，即 解：從轉(zhuǎn)讓資源的方面考慮，得到此問(wèn)題的數(shù)學(xué)模型應(yīng)是 (4.2)評(píng)注：通過(guò)分析我們可以知道，重新得到的對(duì)偶問(wèn)題是一個(gè)非常重要的線性規(guī)劃問(wèn)題，它對(duì)問(wèn)題的分析又加深了一步，減少了管理工作中的盲目性，為決策者提供了更多的科學(xué)依據(jù).原問(wèn)題與對(duì)偶問(wèn)題之間是相互對(duì)應(yīng)的關(guān)系，原問(wèn)題與對(duì)偶問(wèn)題是從不同的角度對(duì)同一問(wèn)題進(jìn)行了分析研究.它們之間存在著很密切的關(guān)系，這些關(guān)系我們將在通過(guò)分析可知.從形式上我們可以看到，在原問(wèn)題中，制訂生產(chǎn)計(jì)劃有3種設(shè)備的總工時(shí)構(gòu)成規(guī)劃的資源約束，可建立3個(gè)約束不等式，其中2種要生產(chǎn)的產(chǎn)品將構(gòu)成決策變量；而在它的對(duì)偶問(wèn)題中，原問(wèn)題里的3個(gè)資源約束所對(duì)應(yīng)的資源估價(jià)正好構(gòu)成了對(duì)偶問(wèn)題的決策變量，原問(wèn)題中的2個(gè)決策變量對(duì)應(yīng)的2種產(chǎn)品則構(gòu)成了對(duì)偶問(wèn)題的2個(gè)約束條件.小結(jié)：通過(guò)分析可以得出，問(wèn)題和問(wèn)題具有下面的關(guān)系：(1)問(wèn)題的目標(biāo)函數(shù)值求極小；問(wèn)題的目標(biāo)函數(shù)值求極大.(2)問(wèn)題有2個(gè)決策變量和3個(gè)主約束條件，問(wèn)題有3個(gè)決策變量和2個(gè)主約束條件.即問(wèn)題中決策變量的個(gè)數(shù)和問(wèn)題中主約束條件的個(gè)數(shù)相等，問(wèn)題中的主約束條件的個(gè)數(shù)和問(wèn)題中的決策變量的個(gè)數(shù)是相等.原因是，問(wèn)題的系數(shù)矩陣和問(wèn)題的系數(shù)矩陣是互為轉(zhuǎn)置的.(3)問(wèn)題的價(jià)格指標(biāo)與問(wèn)題的資源指標(biāo)對(duì)應(yīng)，且問(wèn)題的指標(biāo)與問(wèn)題的指標(biāo)對(duì)應(yīng).(4)問(wèn)題的資源指標(biāo)與問(wèn)題的價(jià)格指標(biāo)對(duì)應(yīng)，且問(wèn)題的指標(biāo)與問(wèn)題的指標(biāo)對(duì)應(yīng).(5)問(wèn)題的主約束條件是 “”型的約束條件；而問(wèn)題的主約束條件是 “”型的約束條件.4.3對(duì)稱(chēng)型對(duì)偶問(wèn)題轉(zhuǎn)換為原問(wèn)題對(duì)偶理論中關(guān)于線性規(guī)劃問(wèn)題里，對(duì)偶問(wèn)題的對(duì)偶就是原問(wèn)題.設(shè)原問(wèn)題為： (4.3)則對(duì)偶問(wèn)題為： (4.4)而對(duì)偶問(wèn)題的對(duì)偶為： (4.5)由此可見(jiàn)，線性規(guī)劃問(wèn)題（4.3），（4.5）的形式是完全一致，因而，原問(wèn)題和它的對(duì)偶問(wèn)題是互為對(duì)偶的關(guān)系，也即是對(duì)偶問(wèn)題的對(duì)偶就是原問(wèn)題.4.4 非對(duì)稱(chēng)型的原問(wèn)題轉(zhuǎn)化為對(duì)偶問(wèn)題線性規(guī)劃有時(shí)以非對(duì)稱(chēng)型出現(xiàn)，那么如何從原始問(wèn)題寫(xiě)出它的對(duì)偶問(wèn)題，將是下面要討論的問(wèn)題.在非對(duì)稱(chēng)形式的規(guī)劃問(wèn)題中，可以按照下面的對(duì)應(yīng)規(guī)則直接給出它的對(duì)偶問(wèn)題:（1）將線性規(guī)劃問(wèn)題統(tǒng)一為“”或“”的形式，而其中的等式約束按照下面（2），（3）中的方法進(jìn)行處理.（2）若原問(wèn)題的某個(gè)約束條件時(shí)等式約束，則對(duì)偶問(wèn)題中與此約束對(duì)應(yīng)的那個(gè)變量取值沒(méi)有非負(fù)限制的.（3）若原問(wèn)題的某個(gè)變量的值沒(méi)有非負(fù)限制，則在它的偶問(wèn)題中與此變量對(duì)應(yīng)的約束條件是等式約束.下面對(duì)于規(guī)則（2）做一些必要的說(shuō)明，對(duì)于規(guī)則（3）可以給出類(lèi)似的證明設(shè)原問(wèn)題中的第一個(gè)約束是等式：那么，此等式與下面的兩個(gè)不等式等價(jià)：這樣，原問(wèn)題可以寫(xiě)成 因?yàn)榫娃D(zhuǎn)換為對(duì)稱(chēng)形式，所以可以直接寫(xiě)出對(duì)偶問(wèn)題這里，我們把y1看作,，于是沒(méi)有限制，規(guī)則（2）的說(shuō)明完畢.將非對(duì)稱(chēng)的線性規(guī)劃問(wèn)題轉(zhuǎn)換為對(duì)稱(chēng)形式時(shí)可能會(huì)有以下幾種：（1）目標(biāo)函數(shù)的轉(zhuǎn)換設(shè)，令，則將求最小值的問(wèn)題轉(zhuǎn)換為求最大值的問(wèn)題，即將求 轉(zhuǎn)化為求，且.反之，要將極大化目標(biāo)函數(shù)轉(zhuǎn)化為極小化目標(biāo)函數(shù)，也可以直接給原目標(biāo)函數(shù)乘以-1，把改寫(xiě)成 .（2）主約束條件的轉(zhuǎn)換A將“”型（或者“”）的約束條件（或），轉(zhuǎn)化為“”型（或者“”型）的約束條件時(shí)，直接將原約束條件兩邊同乘以-1，即（或）B將“=”型的約束條件轉(zhuǎn)化為“”型或者“”型的約束條件時(shí)，首先將其寫(xiě)成兩個(gè)不等式約束條件，然后再轉(zhuǎn)化為所需形式的不等式約束條件，即：（3）非負(fù)約束條件的轉(zhuǎn)換A 若變量xj沒(méi)有非負(fù)限制，取值可正可負(fù)，這時(shí)可設(shè)兩個(gè)非負(fù)變量和，令,B若變量，可令：例3：請(qǐng)寫(xiě)出下列的線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題分析：首先將上述非對(duì)稱(chēng)型問(wèn)題轉(zhuǎn)換為我們所熟悉的對(duì)稱(chēng)型問(wèn)題，然后按照對(duì)稱(chēng)型問(wèn)題的方法將原問(wèn)題轉(zhuǎn)化為對(duì)偶問(wèn)題。第一，在第一個(gè)約束條件的兩邊同乘以-1.第二，將第三個(gè)約束方程分解成 和再將約束條件兩邊同時(shí)乘以-1，即解：原問(wèn)題轉(zhuǎn)換為如下的對(duì)稱(chēng)型：現(xiàn)在四個(gè)約束，分別對(duì)應(yīng)四個(gè)對(duì)偶變量，按表1可得到下面的對(duì)偶問(wèn)題： 再設(shè)，代入上面的數(shù)學(xué)模型就可得出原問(wèn)題的對(duì)偶問(wèn)題為：評(píng)注：將上面對(duì)偶問(wèn)題同原問(wèn)題對(duì)比發(fā)現(xiàn)，無(wú)論是對(duì)稱(chēng)的形式或者是非對(duì)稱(chēng)形式的線性規(guī)劃問(wèn)題在寫(xiě)出它的對(duì)偶問(wèn)題時(shí)，表格中前四行的對(duì)應(yīng)關(guān)系都適應(yīng)，區(qū)別的只是約束條件的形式與其對(duì)應(yīng)變量的取值.4.5對(duì)偶問(wèn)題的應(yīng)用設(shè)有如下線性規(guī)劃問(wèn)題：已知它的最優(yōu)解為，求對(duì)偶問(wèn)題的最優(yōu)解.解：根據(jù)對(duì)偶規(guī)則，我們很容易的寫(xiě)出了原問(wèn)題的對(duì)偶問(wèn)題：根據(jù)對(duì)偶性質(zhì)，有如下對(duì)應(yīng)關(guān)系：原問(wèn)題中的原始變量原問(wèn)題中的松弛變量對(duì)偶問(wèn)題的剩余變量對(duì)偶問(wèn)題的原始變量將對(duì)偶問(wèn)題標(biāo)準(zhǔn)化為：由于為零，上述約束條件簡(jiǎn)化為：由此的對(duì)偶問(wèn)題的最優(yōu)解為：評(píng)注：線性規(guī)劃問(wèn)題中，有時(shí)為了計(jì)算變得簡(jiǎn)單，我們常常需要把線性規(guī)劃問(wèn)題的原問(wèn)題轉(zhuǎn)換為它的對(duì)偶問(wèn)題進(jìn)行解決.5 結(jié)論5.1主要發(fā)現(xiàn)對(duì)偶理論是線性規(guī)劃問(wèn)題的重要內(nèi)容之一，任何一個(gè)線性規(guī)劃都有一個(gè)伴生的線性規(guī)劃，稱(chēng)之為原問(wèn)題的對(duì)偶規(guī)劃問(wèn)題.本文主要探究了原問(wèn)題與對(duì)偶問(wèn)題之間的關(guān)系，原問(wèn)題與對(duì)偶問(wèn)題轉(zhuǎn)化的具體步驟和對(duì)偶理論的應(yīng)用.用科學(xué)的方法對(duì)生產(chǎn)計(jì)劃進(jìn)行預(yù)測(cè)，及時(shí)調(diào)整、科學(xué)決策，使企業(yè)決策更加合理.5.2啟示線性規(guī)劃中常常用到對(duì)偶問(wèn)題，它的思想方法是利用線性代數(shù)的方法找出線性規(guī)劃模型中目標(biāo)函數(shù)與約束條件的可行解.同時(shí)利用對(duì)偶問(wèn)題能夠快速的找出問(wèn)題的最優(yōu)解，對(duì)解的特性的判斷起關(guān)鍵作用.在計(jì)算工具不斷發(fā)展的今天，用對(duì)偶問(wèn)題處理生產(chǎn)、經(jīng)營(yíng)上的問(wèn)題已經(jīng)越來(lái)越廣泛.企業(yè)經(jīng)營(yíng)者可以根據(jù)市場(chǎng)的具體情況，建立相應(yīng)的數(shù)學(xué)模型，然后用對(duì)偶問(wèn)題加以分析，科學(xué)的為決策者提供理論依據(jù).5.3局限性本文主要研究了對(duì)稱(chēng)型與非對(duì)稱(chēng)型的線性規(guī)劃原問(wèn)題轉(zhuǎn)化為對(duì)偶問(wèn)題的具體步驟.對(duì)偶問(wèn)題是一組線性約束條件下的線性規(guī)劃問(wèn)題，它只能處理單個(gè)目標(biāo)函數(shù)的優(yōu)化問(wèn)題.而實(shí)際問(wèn)題中往往要考慮多個(gè)目標(biāo)函數(shù)，這些目標(biāo)函數(shù)之間可能是相互矛盾、相互排斥的.5.4努力方向雖然對(duì)偶問(wèn)題的適用范圍很大，但受實(shí)際問(wèn)題中約束條件的制約，只能處理單目標(biāo)的優(yōu)化問(wèn)題,所以研究線性規(guī)劃最優(yōu)解的求解方法是有必要的.因此，線性規(guī)劃的對(duì)偶理論，單純形法求最優(yōu)解這些都值得進(jìn)一步的研究.參考文獻(xiàn)1郝英奇.實(shí)用應(yīng)籌學(xué)M.北京:中國(guó)人民大學(xué)出版社,2011:70-113.2孫君曼，馮巧玲，孫慧君，李淑君，趙秀花.線性規(guī)劃中原問(wèn)題與對(duì)偶問(wèn)題轉(zhuǎn)化方法探究J.鄭州輕工業(yè)學(xué)院學(xué)報(bào)，2001,(2):44-47.3胡運(yùn)權(quán)，郭耀煌.運(yùn)籌學(xué)教程M.北京：清華大學(xué)出版社，2001:50-78.4李玉林，李成松，趙永滿(mǎn)，宋海草.線性規(guī)劃中原問(wèn)題與對(duì)偶問(wèn)題轉(zhuǎn)化的思考J.石河子大學(xué)院，2010,(7)