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

線性規(guī)劃原問題與對(duì)偶問題的轉(zhuǎn)化及其應(yīng)用摘要線性規(guī)劃對(duì)偶問題是運(yùn)籌學(xué)中應(yīng)用較廣泛的一個(gè)重要分支，它是輔助人們進(jìn)行科學(xué)管理的一種數(shù)學(xué)方法.線性規(guī)劃對(duì)偶問題能從不同角度為管理者提供更多的科學(xué)理論依據(jù)，使管理者的決定更加合理準(zhǔn)確.本文主要探討了線性規(guī)劃原問題與對(duì)偶問題之間的關(guān)系、線性規(guī)劃原問題與對(duì)偶問題的轉(zhuǎn)化以及對(duì)偶理論的應(yīng)用.本文的研究主要是將復(fù)雜的線性規(guī)劃原問題轉(zhuǎn)化成對(duì)偶問題進(jìn)行解決，簡(jiǎn)化了線性規(guī)劃問題，使人們能夠快速的找出線性規(guī)劃問題的最優(yōu)解.關(guān)鍵詞：線性規(guī)劃；原問題；對(duì)偶問題；轉(zhuǎn)化LinearProgrammingistheOriginalProblemandtheTransfbrmationoftheDu

alProblemandApplicationsAbstract:Linearprogramminginoperationalresearchisresearchearlier,rapiddevelopmentandwideapplication,themethodisanimportantbranchofmature,itisoneofthescientificmanagementofauxiliarypeoplemathematicalmethod.Canfromdifferentanglestolinearprogrammingdualproblemforpolicymakerstoprovidemorescientifictheorybasis.Thisarticlemainlyprobesintothelinearprogrammingproblemandtherelationshipbetweenthedualproblem,linearprogrammingproblemandthetransformationofthedualproblem,theapplicationoflinearprogrammingdualproblem.Thisarticleisthecomplexoftheoriginalproblemintoitsdualproblemtobesolved,simplifiesthelinearprogrammingproblem,enablesustorapidlyfindtheoptimalsolutionoflinearprogrammingproblem.Keywords：linearprogramming;theoriginalproblem;thedualproblem;conversion目錄104.4非對(duì)稱型原問題轉(zhuǎn)化為對(duì)偶問題1引言10線性規(guī)劃問題是運(yùn)籌學(xué)里的一個(gè)重要的分支，它的應(yīng)用比較廣泛，因而是輔助人們進(jìn)行現(xiàn)代科學(xué)管理的一種數(shù)學(xué)方法.隨著線性規(guī)劃理論的逐步深入，人們發(fā)現(xiàn)線性規(guī)劃問題具有對(duì)偶性，即每一個(gè)線性問題都伴有另外一個(gè)線性問題的產(chǎn)生，兩者相互配對(duì)，密切聯(lián)系，反之亦然.我們把線性規(guī)劃的這個(gè)特性稱為對(duì)偶性.于是，我們將其中的一個(gè)問題稱為原問題，另一個(gè)問題則稱為它的對(duì)偶問題.對(duì)偶性不僅僅是數(shù)學(xué)上的理論問題，而且也是線性規(guī)劃中實(shí)際問題的內(nèi)在經(jīng)濟(jì)聯(lián)系的必然反映.我們通過對(duì)對(duì)偶問題的深入研究，發(fā)現(xiàn)對(duì)偶問題能從不同角度對(duì)生產(chǎn)計(jì)劃進(jìn)行分析，從而使管理者能夠間接地獲得更多比較有用的信息.2文獻(xiàn)綜述2.1國(guó)內(nèi)外研究現(xiàn)狀在所查閱到的國(guó)內(nèi)外參考文獻(xiàn)［1-15］中，有不少文章是探討了原問題轉(zhuǎn)化為對(duì)偶問題的方法以及對(duì)偶性質(zhì)的證明，并在對(duì)偶理論的應(yīng)用方面有所研究.如郝英奇，胡運(yùn)權(quán)在［1］、［10］中主要介紹了線性規(guī)劃中原問題與對(duì)偶問題中的一些基本概念，探究了實(shí)際問題中的數(shù)學(xué)模型以及解.孫君曼，馮巧玲，孫慧君，李淑君等在［2］中探討了對(duì)偶理論中互補(bǔ)松弛定理在各種情況下的使用方法，使學(xué)生更好地掌握互補(bǔ)松弛定理的含義和應(yīng)用方法.胡運(yùn)權(quán)，郭耀煌，殷志祥等在［3］、［5］中系統(tǒng)的介紹了線性規(guī)劃中原始問題與對(duì)偶問題的兩種形式.郭鵬，徐玖平等在［6］、［8］中用不同例子來說明了原問題轉(zhuǎn)化為對(duì)偶問題的必要性.崔永新等在［9］、［15］中探討了對(duì)偶問題的相關(guān)定理以及對(duì)偶問題的可行解和最優(yōu)解之間的若干性質(zhì).李師正，王德勝在［11］中探討了如何用計(jì)算機(jī)計(jì)算對(duì)偶問題的最優(yōu)解.岳宏志，藺小林，孫文喻等在［12］、［14］中探討了對(duì)偶理論的證明過程，并用常見的例子來說明對(duì)偶理論的基本思想和解題方法.曾波，葉宗文在［13］中主要從經(jīng)濟(jì)管理的實(shí)際問題中闡述了線性規(guī)劃的基本概念，基本原理，對(duì)偶理論，靈敏度分析等.2.2國(guó)內(nèi)外研究現(xiàn)狀評(píng)價(jià)文獻(xiàn)［1-15］分別探討了線性規(guī)劃問題中原問題轉(zhuǎn)化為對(duì)偶問題的理論依據(jù)以及如何利用對(duì)偶理論去解決實(shí)際生產(chǎn)問題.文獻(xiàn)中主要探討了對(duì)稱型的原問題轉(zhuǎn)化為對(duì)偶問題的方法.沒有全面介紹非對(duì)稱型的原問題與對(duì)偶問題之間轉(zhuǎn)化的具體步驟，而且文獻(xiàn)中對(duì)原問題轉(zhuǎn)化為對(duì)偶問題的步驟提及甚少，大都一帶而過，對(duì)應(yīng)用中存在的問題也未給出詳細(xì)深入的說明.2.3提出問題在線性規(guī)劃問題中，根據(jù)實(shí)際生產(chǎn)中具體情況的需要，我們常常要把原問題與它的對(duì)偶問題進(jìn)行轉(zhuǎn)換，以解決一些復(fù)雜的線性規(guī)劃問題，因而對(duì)偶問題的應(yīng)用較為廣泛.但大部分書籍都只介紹了線性規(guī)劃問題的基礎(chǔ)知識(shí)，并沒有給出原問題與對(duì)偶問題轉(zhuǎn)換的具體步驟.因此本文主要探討了線性規(guī)劃原問題與對(duì)偶問題之間轉(zhuǎn)化的具體步驟，體會(huì)不同類型原問題的轉(zhuǎn)化過程.3預(yù)備知識(shí)首先我先簡(jiǎn)單的介紹一些關(guān)于線性規(guī)劃問題中的原問題和對(duì)偶問題的一些基本的知識(shí).3.1對(duì)稱形式的原問題我們將滿足下列條件的線性規(guī)劃問題稱之為具有對(duì)稱形式的線性規(guī)劃問題.這類問題的變量都具有非負(fù)約束，當(dāng)目標(biāo)函數(shù)求極大值時(shí)，它的約束條件都取“V”號(hào)，當(dāng)目標(biāo)函數(shù)求極小值時(shí)它的約束條件均取">”號(hào).因而，這類數(shù)學(xué)模型的特點(diǎn)是：（1）所有的決策變量都是非負(fù)的；（2）所有的約束條件都是“<”型；（3）目標(biāo)函數(shù)是最大化類型.線性規(guī)劃原問題的對(duì)稱形式的一般形式［1］為:ax+ax+A+ax<b1111221nn1ax+ax+A+ax<b2112222nnM2(3.1)ax+ax+A+axm11m22mnix.>0(j=1,2,A,n)3.2非對(duì)稱形式的原問題不是所有的線性規(guī)劃問題都具有對(duì)稱的形式，我們將沒有對(duì)稱形式的線性規(guī)劃問題稱之為非對(duì)稱形式的線性規(guī)劃問題.非對(duì)稱形式的線性規(guī)劃問題指的是一般情況下的線性規(guī)劃問題，即是目標(biāo)函數(shù)值求極小或者求極大；約束條件：?，.-.：；頊，*。"（〕，或是無限制的隨意的組合.例如:ax+ax+ax<b1111221331ax+ax+ax=b/、s.t〈2112222332(3.2)ax+ax+ax<b3113223333x>0,x<0,x無約束3.3對(duì)偶問題的定義在運(yùn)籌學(xué)中，關(guān)于對(duì)線性規(guī)劃的對(duì)偶規(guī)劃給出的定義⑵如下.設(shè)給定的線性規(guī)劃為:IAX<b°、

s."(3.2)IX>0其中X=(x,x,A,x》，A=(a)，b=(b,b,A,b》，C=(,c,A,c)jmxn12m12n因此，定義它的對(duì)偶問題為:\YA>Cs.t<|Y>0(3.4)其中Y=（y,y,A,y）是行向量.（3.4）是對(duì)偶問題，（3.3）是原問題，（3.3）與（3.4）合12m在一起我們就稱為是一對(duì)對(duì)稱形式的對(duì)偶規(guī)劃問題.3.4原問題轉(zhuǎn)化為對(duì)偶問題的理論依據(jù)我們根據(jù)線性規(guī)劃問題中約束條件和變量的對(duì)應(yīng)關(guān)系，統(tǒng)一歸納為下表1[3]所示:項(xiàng)目原問題（對(duì)偶問題）對(duì)偶問題（原問題）約束系數(shù)矩陣約束系數(shù)矩陣的轉(zhuǎn)置約束條件右端項(xiàng)向量目標(biāo)函數(shù)中的價(jià)格系數(shù)向量目標(biāo)函數(shù)中的價(jià)格系數(shù)向量約束條件右端項(xiàng)向量目標(biāo)函數(shù)表14原問題與對(duì)偶問題的轉(zhuǎn)化一對(duì)對(duì)偶的線性規(guī)劃問題表示了同一個(gè)問題的兩個(gè)側(cè)面，是從兩個(gè)角度對(duì)同一個(gè)研究對(duì)象提出的極值問題，兩類極值的問題都具有相同的目標(biāo)函數(shù)值.我們發(fā)現(xiàn)在很多時(shí)候求解對(duì)偶問題比原問題更加容易，為決策者提供更多的科學(xué)理論依據(jù)，因此我們常常需要把原問題轉(zhuǎn)化為對(duì)偶問題.4.1原問題與對(duì)偶問題的關(guān)系一對(duì)對(duì)偶的線性規(guī)劃問題具有相互對(duì)應(yīng)的關(guān)系：（1）原問題中的目標(biāo)函數(shù)值是max，約束條件是“<”的形式；對(duì)偶問題的目標(biāo)函數(shù)值為min，約束條件是“2”的形式.（2）原問題的價(jià)值系數(shù)和對(duì)偶問題的右端項(xiàng)對(duì)應(yīng)，原始問題的右端項(xiàng)和對(duì)偶問題的價(jià)值系數(shù)對(duì)應(yīng).（3）原問題的變量和對(duì)偶問題的約束條件對(duì)應(yīng)，即，原問題中有〃個(gè)變量，那么對(duì)偶問題就有〃個(gè)約束條件；原問題有m個(gè)約束條件，那么對(duì)偶問題就有m個(gè)變量.（4）對(duì)偶問題的系數(shù)矩陣就是原問題的系數(shù)矩陣的轉(zhuǎn)置.用矩陣表示，原問題為：則對(duì)偶問題為：需要注意的是，我們所討論的對(duì)偶問題一定是指一對(duì)問題，而原問題和對(duì)偶問題是相對(duì)的，它們互為對(duì)偶問題，一個(gè)問題可以是原問題也可以是對(duì)偶問題.4.2對(duì)稱型原問題轉(zhuǎn)化為對(duì)偶問題當(dāng)線性規(guī)劃問題為一般形式（3.1）時(shí)，我們將根據(jù)下面的四條規(guī)則轉(zhuǎn)換為它的對(duì)偶問題：（1）原問題和它的對(duì)偶問題之間的系數(shù)矩陣互為轉(zhuǎn)置.（2）原問題中變量的個(gè)數(shù)等于它的對(duì)偶問題的約束條件的個(gè)數(shù).（3）原問題的右端常數(shù)就是對(duì)偶問題的目標(biāo)函數(shù)的系數(shù).（4）原問題的目標(biāo)函數(shù)求極大時(shí)，約束條件是“V”類型，而它的對(duì)偶問題的目標(biāo)函數(shù)求極小，約束條件則為“>”類型.因此，它的對(duì)偶問題可以轉(zhuǎn)變?yōu)槿缦碌男问舰?例1生產(chǎn)計(jì)劃問題云南一公司加工生產(chǎn)甲，乙兩種產(chǎn)品，它的市場(chǎng)前景非常的好，銷路也不成問題，各種制約因素主要有技術(shù)工人、設(shè)備臺(tái)時(shí)和原材料供應(yīng).已知制造每噸產(chǎn)品的資源消耗系數(shù)、每天的資源限量和售價(jià)等參數(shù)如表2所示.問題：云南的這家公司應(yīng)該怎樣制定每天的生產(chǎn)計(jì)劃，才能使它的產(chǎn)量得到最大？甲產(chǎn)品乙產(chǎn)品資源限量人力86320設(shè)備68260原材料410300售價(jià)（元/公斤）90150表2分析：為了建立此問題的數(shù)學(xué)模型，第一，要選定決策變量.第二，要確定問題的目標(biāo)，即用來評(píng)價(jià)不同方案優(yōu)劣的標(biāo)準(zhǔn)，這種目標(biāo)總是決策變量的函數(shù)，稱為目標(biāo)函數(shù).第三，我們把要確定達(dá)到目標(biāo)時(shí)所受的限制條件，稱之為約束條件.這里要決策的問題是，在現(xiàn)有人力、設(shè)備、礦石的限制下，如何確定產(chǎn)量使得產(chǎn)值自大？設(shè)X和x12分別表示該公司A，B產(chǎn)品的數(shù)量，用z表示產(chǎn)值，則每天的產(chǎn)值表示為z=90氣+150x2，使其最大化，即maxz=90氣+150x2，稱為目標(biāo)函數(shù).將制約因素表達(dá)出來，即有：人力不超過320工時(shí)，為8xi+6x2<320；設(shè)備不超過260臺(tái)時(shí)有，6七+8x2<260；原材料不超過300公斤有，4xi+10x2<300。表述限制條件的數(shù)學(xué)表達(dá)式稱為約束條件，由此該問題的數(shù)學(xué)模型可表示為：上面的問題是一個(gè)典型的求解利潤(rùn)最大化的生產(chǎn)計(jì)劃的問題.題中，“max”是“maximize”的縮寫，意思是"最大化”；“s.七”是”subjectto"單詞的縮寫，表示“滿足于”.因此，上述模型的含義是：在給定的條件限制下，求出使目標(biāo)函數(shù)值達(dá)到最大的氣,x2的值.從數(shù)學(xué)模型中看出，上面的例題具有下面的三個(gè)特征：用一組決策變量表示問題的一個(gè)方案，決策變量的一組取值代表一個(gè)具體的方案.通常狀況下，決策變量的取值是非負(fù)的，部分情況下，還要求決策變量取值為整數(shù).每個(gè)問題都有一個(gè)目標(biāo)，而且都可以用決策變量的線性函數(shù)表示.根據(jù)問題的不同，要求目標(biāo)實(shí)現(xiàn)最大或者最小.決策變量都滿足一定的約束條件，而且都可以用決策變量的線性等式或者不等式表示.具備以上三個(gè)要素的問題稱為線性規(guī)劃問題，簡(jiǎn)單地講，線性規(guī)劃問題就是求一個(gè)線性目標(biāo)函數(shù)在滿足一組線性等式(或不等式方程)約束條件下的極值問題.例2云南一公司加工生產(chǎn)甲，乙兩種產(chǎn)品，市場(chǎng)前景非常的很好，銷路也不成問題，各種制約因素主要有技術(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)讓，我們假定市場(chǎng)廣闊.問題：公司轉(zhuǎn)讓資源的價(jià)格底線是什么？甲產(chǎn)品乙產(chǎn)品資源限量人力86320設(shè)備68260原材料410300售價(jià)(元/公斤)90150表3我們將例1叫做原問題，將例2叫做對(duì)偶問題.原問題的數(shù)學(xué)模型是:〔8尤+6x<3206x+8x<260/.s.t.<12(4.1)4x+10x<30012s.t.<x,x>0分析：現(xiàn)在在對(duì)偶問題中我們需要考慮的是，將例題中的三種資源租讓或者轉(zhuǎn)出，應(yīng)該是不少于原來的收益的，否則這家公司寧愿選擇自己繼續(xù)生產(chǎn).所以，決策的約束條件應(yīng)該是：出租制造的產(chǎn)品消耗掉的資源不能少于自己生產(chǎn)該產(chǎn)品的收益；目標(biāo)函數(shù)應(yīng)該是：資源轉(zhuǎn)讓的收益底線.所以，我們?cè)O(shè)y，y，y分別為人力、設(shè)備臺(tái)時(shí)和123原材料的轉(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)帶來90元的產(chǎn)值，即8yi+6y2+4y3>90同理，生產(chǎn)1公斤B產(chǎn)品需耗時(shí)4個(gè)工時(shí)，6個(gè)臺(tái)時(shí)和8公斤的原材料，可創(chuàng)造產(chǎn)值150元，出讓這些資源所獲得的銷售收益應(yīng)滿足6yi+8y2+10y3>150上面兩個(gè)不等式保證了“出售”資源所獲得的收益不低于自己組織生產(chǎn)所能創(chuàng)造的收益.但是也不能隨意要價(jià)，否則由于市場(chǎng)的調(diào)節(jié)作用將會(huì)使資源賣不出去.因此目標(biāo)函數(shù)應(yīng)該是表達(dá)所獲的收益的底線，即解：從轉(zhuǎn)讓資源的方面考慮，得到此問題的數(shù)學(xué)模型應(yīng)是|8義+6y2+4，3>90s.t.〈6y+8y+10y>150(4.2)y:y,/>03、123評(píng)注：通過分析我們可以知道，重新得到的對(duì)偶問題是一個(gè)非常重要的線性規(guī)劃問題，它對(duì)問題的分析又加深了一步，減少了管理工作中的盲目性，為決策者提供了

更多的科學(xué)依據(jù).原問題與對(duì)偶問題之間是相互對(duì)應(yīng)的關(guān)系，原問題與對(duì)偶問題是從不同的角度對(duì)同一問題進(jìn)行了分析研究.它們之間存在著很密切的關(guān)系，這些關(guān)系我們將在通過分析可知.從形式上我們可以看到，在原問題中，制訂生產(chǎn)計(jì)劃有3種設(shè)備的總工時(shí)構(gòu)成規(guī)劃的資源約束，可建立3個(gè)約束不等式，其中2種要生產(chǎn)的產(chǎn)品將構(gòu)成決策變量；而在它的對(duì)偶問題中，原問題里的3個(gè)資源約束所對(duì)應(yīng)的資源估價(jià)正好構(gòu)成了對(duì)偶問題的決策變量，原問題中的2個(gè)決策變量對(duì)應(yīng)的2種產(chǎn)品則構(gòu)成了對(duì)偶問題的2個(gè)約束條件.小結(jié)：通過分析可以得出，問題(4.1)和問題(4.2)具有下面的關(guān)系：(1)問題(4.1)的目標(biāo)函數(shù)值求極??；問題(4.2)的目標(biāo)函數(shù)值求極大.(2)問題(4.1)有2個(gè)決策變量和3個(gè)主約束條件，問題(4.2)有3個(gè)決策變量和2個(gè)主約束條件.即問題(4.1)中決策變量的個(gè)數(shù)和問題(4.2)中主約束條件的個(gè)數(shù)相等，問題(4.1)中的主約束條件的個(gè)數(shù)和問題(4..2)中的決策變量的個(gè)數(shù)是相等.原因是，問題(4.1)的系數(shù)矩陣和問題(4.2)的系數(shù)矩陣是互為轉(zhuǎn)置的.(3)問題(4.1)的價(jià)格指標(biāo)與問題(4.2)的資源指標(biāo)對(duì)應(yīng)，且問題(4.1)的第，個(gè)價(jià)格指標(biāo)與問題(4.2)的第，個(gè)資源指標(biāo)對(duì)應(yīng).(4)問題(4.1)的資源指標(biāo)與問題(4.2)的價(jià)格指標(biāo)對(duì)應(yīng)，且問題(4.1)的第，個(gè)資源指標(biāo)與問題(4.2)的第i個(gè)價(jià)格指標(biāo)對(duì)應(yīng).⑸問題(4.1)的主約束條件是會(huì)”型的約束條件；而問題(4.2)的主約束條件是“V”型的約束條件.4.3對(duì)稱型對(duì)偶問題轉(zhuǎn)換為原問題對(duì)偶理論中關(guān)于線性規(guī)劃問題里，對(duì)偶問題的對(duì)偶就是原問題.設(shè)原問題為：(4.3)IAX<bs.t.<IX>0(4.3)則對(duì)偶問題為：(4.4)\YA>Cs.t.<|Y>0

(4.4)而對(duì)偶問題的對(duì)偶為:(4.5)IAZ<bs.t.<\Z>0(4.5)由此可見，線性規(guī)劃問題（4.3）,（4.5）的形式是完全一致，因而，原問題和它的對(duì)偶問題是互為對(duì)偶的關(guān)系，也即是對(duì)偶問題的對(duì)偶就是原問題.4.4非對(duì)稱型的原問題轉(zhuǎn)化為對(duì)偶問題線性規(guī)劃有時(shí)以非對(duì)稱型出現(xiàn)，那么如何從原始問題寫出它的對(duì)偶問題，將是下面要討論的問題.在非對(duì)稱形式的規(guī)劃問題中，可以按照下面的對(duì)應(yīng)規(guī)則直接給出它的對(duì)偶問題：（1）將線性規(guī)劃問題統(tǒng)一為“max,<”或“min,>”的形式，而其中的等式約束按照下面（2），（3）中的方法進(jìn)行處理.（2）若原問題的某個(gè)約束條件時(shí)等式約束，則對(duì)偶問題中與此約束對(duì)應(yīng)的那個(gè)變量取值沒有非負(fù)限制的.（3）若原問題的某個(gè)變量的值沒有非負(fù)限制，則在它的偶問題中與此變量對(duì)應(yīng)的約束條件是等式約束.下面對(duì)于規(guī)則（2）做一些必要的說明，對(duì)于規(guī)則（3）可以給出類似的證明設(shè)原問題中的第一個(gè)約束是等式：那么，此等式與下面的兩個(gè)不等式等價(jià)：這樣，原問題可以寫成因?yàn)榫娃D(zhuǎn)換為對(duì)稱形式，所以可以直接寫出對(duì)偶問題這里，我們把.「看作y=y-y”，，于是y沒有限制，規(guī)則（2）的說明完畢.將非對(duì)1111稱的線性規(guī)劃問題轉(zhuǎn)換為對(duì)稱形式時(shí)可能會(huì)有以下幾種情形[5]:（1）目標(biāo)函數(shù)的轉(zhuǎn)換設(shè)minz=cx+cx+A+cx，令z，=-z，則將求最小值的問題轉(zhuǎn)換為求最大值1122nn的問題，即將求minz轉(zhuǎn)化為求maxz，且maxz=-cx-cx-A-cx.反之，要將1122nn極大化目標(biāo)函數(shù)轉(zhuǎn)化為極小化目標(biāo)函數(shù)，也可以直接給原目標(biāo)函數(shù)乘以-1,把maxz'改寫成minz.主約束條件的轉(zhuǎn)換A.將y”型(或者“X')的約束條件乙x<b(或Zax>b)，轉(zhuǎn)化ijJiijJiTOC\o"1-5"\h\zj=1j=1為“>”型(或者“<”型)的約束條件時(shí)，直接將原約束條件兩邊同乘以1,即Zax>-b(或Zax<-b)ijjiijjij=1j=1B.將“二”型的約束條件￡ax.=氣轉(zhuǎn)化為“>”型或者“〈”型的約束條件時(shí)，j=1首先將其寫成兩個(gè)不等式約束條件，然后再轉(zhuǎn)化為所需形式的不等式約束條件，即：非負(fù)約束條件的轉(zhuǎn)換若變量*沒有非負(fù)限制，取值可正可負(fù)，這時(shí)可設(shè)兩個(gè)非負(fù)變量xj和xj，令x=x'一x",x',x''>0jjjjj若變量x<0，可令：x=一x',x'>0jjjj例3：請(qǐng)寫出下列的線性規(guī)劃問題的對(duì)偶問題分析：首先將上述非對(duì)稱型問題轉(zhuǎn)換為我們所熟悉的對(duì)稱型問題，然后按照對(duì)稱型問題的方法將原問題轉(zhuǎn)化為對(duì)偶問題。第一，在第一個(gè)約束條件的兩邊同乘以-1.TOC\o"1-5"\h\z第二，將第三個(gè)約束方程分解成x-x+3x<1和x-x+3x>1再將約束條件123123x一x+3x>1兩邊同時(shí)乘以-1，即一x+x一3x<-1123123解：原問題轉(zhuǎn)換為如下的對(duì)稱型：現(xiàn)在四個(gè)約束，分別對(duì)應(yīng)四個(gè)對(duì)偶變量y,y,y,y”，按表1可得到下面的對(duì)偶問題：1233再設(shè)y-y”=y，代入上面的數(shù)學(xué)模型就可得出原問題的對(duì)偶問題為：333評(píng)注：將上面對(duì)偶問題同原問題對(duì)比發(fā)現(xiàn)，無論是對(duì)稱的形式或者是非對(duì)稱形式的線性規(guī)劃問題在寫出它的對(duì)偶問題時(shí)，表格中前四行的對(duì)應(yīng)關(guān)系都適應(yīng)，區(qū)別的只是約束條件的形式與其對(duì)應(yīng)變量的取值.4.5對(duì)偶問題的應(yīng)用設(shè)有如下線性規(guī)劃問題：已知它的最優(yōu)解為X=(0,50,50,9,0,0)t，求對(duì)偶問題的最優(yōu)解.解：根據(jù)對(duì)偶規(guī)則，我們很容易的寫出了原問題的對(duì)偶問題:根據(jù)對(duì)偶性質(zhì)，有如下對(duì)應(yīng)關(guān)系：原問題中的原始變量原問題中的松弛變量對(duì)偶問題的剩余變量對(duì)偶問題的原始變量將對(duì)偶問題標(biāo)準(zhǔn)化為：由于y,y,y為零，上述約束條件簡(jiǎn)化為：156由此的對(duì)偶問題的最優(yōu)解為：y=0,y=8,y=2,y=4,y=0,y=0123456評(píng)注：線性規(guī)劃問題中，有時(shí)為了計(jì)算變得簡(jiǎn)單，我們常常需要把線性規(guī)劃問題的原問題轉(zhuǎn)換為它的對(duì)偶問題進(jìn)行解決.5結(jié)論5.1主要發(fā)現(xiàn)對(duì)偶理論是線性規(guī)劃問題的重要內(nèi)容之一，任何一個(gè)線性規(guī)劃都有一個(gè)伴生的線性規(guī)劃，稱之為原問題的對(duì)偶規(guī)劃問題.本文主要探究了原問題與對(duì)偶問題之間的關(guān)系，原問題與對(duì)偶問題轉(zhuǎn)化的具體步驟和對(duì)偶理論的應(yīng)用.用科學(xué)的方法對(duì)生產(chǎn)計(jì)劃進(jìn)行預(yù)測(cè)，及時(shí)調(diào)整、科學(xué)決策，使企業(yè)決策更加合理.5.2啟示線性規(guī)劃中常常用到對(duì)偶問題，它的思想方法是利用線性代數(shù)的方法找出線性規(guī)劃模型中目標(biāo)函數(shù)與約束條件的可行解.同時(shí)利用對(duì)偶問題能夠快速的找出問題的最優(yōu)解，對(duì)解的特性的判斷起關(guān)鍵作用.在計(jì)算工具不斷發(fā)展的今天，用對(duì)偶問題處理生產(chǎn)、經(jīng)營(yíng)上的問題已經(jīng)越來越廣泛.企業(yè)經(jīng)營(yíng)者可以根據(jù)市場(chǎng)的具體情況，建立相應(yīng)的數(shù)學(xué)模型，然后用對(duì)偶問題加以分析，科學(xué)的為決策者提供理論依據(jù).5.3局限性本文主要研究了對(duì)稱型與非對(duì)稱型的線性規(guī)劃原問題轉(zhuǎn)化為對(duì)偶問題的具體步驟.對(duì)偶問題是一組線性約束條件下的線性規(guī)劃問題，它只能處理單個(gè)目標(biāo)函數(shù)的優(yōu)化問題.而實(shí)際問題中往往要考慮多個(gè)目標(biāo)函數(shù)，這些目標(biāo)函數(shù)之間可能是相互矛盾、相互排斥的.5.4努力方向雖然對(duì)偶問題的適用范圍很大，但受實(shí)際問題中約束條件的制約，只能處理單目標(biāo)的優(yōu)化問題，所以研究線性規(guī)劃最優(yōu)解的求解方法是有必要的.因此，線性規(guī)劃的對(duì)偶理論，單純形法求最優(yōu)解這些都值得進(jìn)一步的研究.參考文獻(xiàn)郝英奇.實(shí)用應(yīng)籌學(xué)[M].北京：中國(guó)人民大學(xué)出版社,2011:70-113.孫君曼，馮巧玲，孫慧君，李淑君，趙秀花.線性規(guī)劃中原問題與對(duì)偶問題轉(zhuǎn)化方法探究[J].鄭州輕工業(yè)學(xué)院學(xué)報(bào)，2001,(2):44-47.胡運(yùn)權(quán)，郭耀煌.運(yùn)籌學(xué)教程[M].北京：清華大學(xué)出版