線性規(guī)劃原問題與對(duì)偶問題的轉(zhuǎn)化及其應(yīng)用.doc_第1頁
線性規(guī)劃原問題與對(duì)偶問題的轉(zhuǎn)化及其應(yīng)用.doc_第2頁
線性規(guī)劃原問題與對(duì)偶問題的轉(zhuǎn)化及其應(yīng)用.doc_第3頁
線性規(guī)劃原問題與對(duì)偶問題的轉(zhuǎn)化及其應(yīng)用.doc_第4頁
線性規(guī)劃原問題與對(duì)偶問題的轉(zhuǎn)化及其應(yīng)用.doc_第5頁
已閱讀5頁,還剩16頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐ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)行解決,簡化了線性規(guī)劃問題,使人們能夠快速的找出線性規(guī)劃問題的最優(yōu)解.關(guān)鍵詞:線性規(guī)劃;原問題;對(duì)偶問題 ;轉(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 國內(nèi)外研究現(xiàn)狀12.2 國內(nèi)外研究現(xiàn)狀評(píng)價(jià)22.3 提出問題23 預(yù)備知識(shí)23.1對(duì)稱形式的原問題23.2 非對(duì)稱形式的原問題33.3 對(duì)偶問題的定義33.4原問題轉(zhuǎn)化為對(duì)偶問題的理論依據(jù)44 原問題與對(duì)偶問題的轉(zhuǎn)化54.1 原問題與對(duì)偶問題的關(guān)系54.2 對(duì)稱型原問題化為對(duì)偶問題64.3 對(duì)稱型對(duì)偶問題轉(zhuǎn)換為原問題94.4 非對(duì)稱型原問題轉(zhuǎn)化為對(duì)偶問題104.5 對(duì)偶問題的應(yīng)用135 結(jié)論155.1主要發(fā)現(xiàn)155.2啟示155.3局限性155.4努力方向15參考文獻(xiàn)161 引言線性規(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 國內(nèi)外研究現(xiàn)狀在所查閱到的國內(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 國內(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í)首先我先簡單的介紹一些關(guān)于線性規(guī)劃問題中的原問題和對(duì)偶問題的一些基本的知識(shí).3.1對(duì)稱形式的原問題我們將滿足下列條件的線性規(guī)劃問題稱之為具有對(duì)稱形式的線性規(guī)劃問題.這類問題的變量都具有非負(fù)約束,當(dāng)目標(biāo)函數(shù)求極大值時(shí),它的約束條件都取“”號(hào),當(dāng)目標(biāo)函數(shù)求極小值時(shí)它的約束條件均取“”號(hào). 因而,這類數(shù)學(xué)模型的特點(diǎn)是:(1)所有的決策變量都是非負(fù)的;(2)所有的約束條件都是“”型;(3)目標(biāo)函數(shù)是最大化類型.線性規(guī)劃原問題的對(duì)稱形式的為: (3.1)3.2 非對(duì)稱形式的原問題不是所有的線性規(guī)劃問題都具有對(duì)稱的形式,我們將沒有對(duì)稱形式的線性規(guī)劃問題稱之為非對(duì)稱形式的線性規(guī)劃問題.非對(duì)稱形式的線性規(guī)劃問題指的是一般情況下的線性規(guī)劃問題,即是目標(biāo)函數(shù)值求極小或者求極大;約束條件,=,;變量0,0,或是無限制的隨意的組合.例如: (3.2)3.3 對(duì)偶問題的定義在運(yùn)籌學(xué)中,關(guān)于對(duì)線性規(guī)劃的對(duì)偶規(guī)劃給出的如下.設(shè)給定的線性規(guī)劃為: (3.2)其中,因此,定義它的對(duì)偶問題為: (3.4)其中是行向量. (3.4)是對(duì)偶問題,(3.3)是原問題,(3.3)與(3.4)合在一起我們就稱為是一對(duì)對(duì)稱形式的對(duì)偶規(guī)劃問題.3.4原問題轉(zhuǎn)化為對(duì)偶問題的理論依據(jù)我們根據(jù)線性規(guī)劃問題中約束條件和變量的對(duì)應(yīng)關(guān)系,統(tǒng)一歸納為下所示:項(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ù)值是,約束條件是“”的形式;對(duì)偶問題的,的形式.(2)原問題的價(jià)值系數(shù)和對(duì)偶問題的右端項(xiàng)對(duì)應(yīng),原始問題的右端項(xiàng)和對(duì)偶問題的價(jià)值系數(shù)對(duì)應(yīng).(3)原問題的變量和對(duì)偶問題的約束條件對(duì)應(yīng),即,原問題中有變量,那么對(duì)偶問題就有約束條件;原問題有約束條件,那么對(duì)偶問題就有變量.(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í),約束條件是“”類型,而它的對(duì)偶問題的目標(biāo)函數(shù)求極小,約束條件則為“”類型.因此,它的對(duì)偶問題可以轉(zhuǎn)變?yōu)槿缦碌模豪? 生產(chǎn)計(jì)劃問題云南一公司加工生產(chǎn)甲,乙兩種產(chǎn)品,它的市場前景非常的好,銷路也不成問題,各種制約因素主要有技術(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è)和分別表示該公司A,B產(chǎn)品的數(shù)量,用z表示產(chǎn)值,則每天的產(chǎn)值表示為,使其最大化,即,稱為目標(biāo)函數(shù).將制約因素表達(dá)出來,即有:人力不超過320工時(shí),為;設(shè)備不超過260臺(tái)時(shí)有,;原材料不超過300公斤有,。表述限制條件的數(shù)學(xué)表達(dá)式稱為約束條件,由此該問題的數(shù)學(xué)模型可表示為:上面的問題是一個(gè)典型的求解利潤最大化的生產(chǎn)計(jì)劃的問題.題中,“”是 “maximize”的縮寫,意思是“最大化”;“”是”subject to”單詞的縮寫,表示“滿足于”.因此,上述模型的含義是:在給定的條件限制下,求出使目標(biāo)函數(shù)值達(dá)到最大的的值.從數(shù)學(xué)模型中看出,上面的例題具有下面的三個(gè)特征:(1) 用一組決策變量表示問題的一個(gè)方案,決策變量的一組取值代表一個(gè)具體的方案.通常狀況下,決策變量的取值是非負(fù)的,部分情況下,還要求決策變量取值為整數(shù).(2) 每個(gè)問題都有一個(gè)目標(biāo),而且都可以用決策變量的線性函數(shù)表示.根據(jù)問題的不同,要求目標(biāo)實(shí)現(xiàn)最大或者最小.(3) 決策變量都滿足一定的約束條件,而且都可以用決策變量的線性等式或者不等式表示.具備以上三個(gè)要素的問題稱為線性規(guī)劃問題,簡單地講,線性規(guī)劃問題就是求一個(gè)線性目標(biāo)函數(shù)在滿足一組線性等式(或不等式方程)約束條件下的極值問題.例2 云南一公司加工生產(chǎn)甲,乙兩種產(chǎn)品,市場前景非常的很好,銷路也不成問題,各種制約因素主要有技術(shù)工人、設(shè)備臺(tái)時(shí)和原材料供應(yīng).已知制造每噸產(chǎn)品的資源消耗系數(shù)、每天的資源限量和售價(jià)等參數(shù)如表3所示.現(xiàn)在公司有意轉(zhuǎn)換經(jīng)營方式,現(xiàn)在將各種資源出租轉(zhuǎn)讓,我們假定市場廣闊.問題:公司轉(zhuǎn)讓資源的價(jià)格底線是什么?甲產(chǎn)品乙產(chǎn)品資源限量人力86320設(shè)備68260原材料410300售價(jià)(元/公斤)90150表3我們將例1叫做原問題,將例2叫做對(duì)偶問題.原問題的數(shù)學(xué)模型是: (4.1)分析:現(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è),分別為人力、設(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)帶來90元的產(chǎn)值,即 同理,生產(chǎn)1公斤B產(chǎn)品需耗時(shí)4個(gè)工時(shí),6個(gè)臺(tái)時(shí)和8公斤的原材料,可創(chuàng)造產(chǎn)值150元,出讓這些資源所獲得的銷售收益應(yīng)滿足上面兩個(gè)不等式保證了“出售”資源所獲得的收益不低于自己組織生產(chǎn)所能創(chuàng)造的收益.但是也不能隨意要價(jià),否則由于市場的調(diào)節(jié)作用將會(huì)使資源賣不出去.因此目標(biāo)函數(shù)應(yīng)該是表達(dá)所獲的收益的底線,即 解:從轉(zhuǎn)讓資源的方面考慮,得到此問題的數(shù)學(xué)模型應(yīng)是 (4.2)評(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é):通過分析可以得出,問題和問題具有下面的關(guān)系:(1)問題的目標(biāo)函數(shù)值求極?。粏栴}的目標(biāo)函數(shù)值求極大.(2)問題有2個(gè)決策變量和3個(gè)主約束條件,問題有3個(gè)決策變量和2個(gè)主約束條件.即問題中決策變量的個(gè)數(shù)和問題中主約束條件的個(gè)數(shù)相等,問題中的主約束條件的個(gè)數(shù)和問題中的決策變量的個(gè)數(shù)是相等.原因是,問題的系數(shù)矩陣和問題的系數(shù)矩陣是互為轉(zhuǎn)置的.(3)問題的價(jià)格指標(biāo)與問題的資源指標(biāo)對(duì)應(yīng),且問題的指標(biāo)與問題的指標(biāo)對(duì)應(yīng).(4)問題的資源指標(biāo)與問題的價(jià)格指標(biāo)對(duì)應(yīng),且問題的指標(biāo)與問題的指標(biāo)對(duì)應(yīng).(5)問題的主約束條件是 “”型的約束條件;而問題的主約束條件是 “”型的約束條件.4.3對(duì)稱型對(duì)偶問題轉(zhuǎn)換為原問題對(duì)偶理論中關(guān)于線性規(guī)劃問題里,對(duì)偶問題的對(duì)偶就是原問題.設(shè)原問題為: (4.3)則對(duì)偶問題為: (4.4)而對(duì)偶問題的對(duì)偶為: (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)一為“”或“”的形式,而其中的等式約束按照下面(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ì)偶問題這里,我們把y1看作,,于是沒有限制,規(guī)則(2)的說明完畢.將非對(duì)稱的線性規(guī)劃問題轉(zhuǎn)換為對(duì)稱形式時(shí)可能會(huì)有以下幾種:(1)目標(biāo)函數(shù)的轉(zhuǎn)換設(shè),令,則將求最小值的問題轉(zhuǎn)換為求最大值的問題,即將求 轉(zhuǎn)化為求,且.反之,要將極大化目標(biāo)函數(shù)轉(zhuǎn)化為極小化目標(biāo)函數(shù),也可以直接給原目標(biāo)函數(shù)乘以-1,把改寫成 .(2)主約束條件的轉(zhuǎn)換A將“”型(或者“”)的約束條件(或),轉(zhuǎn)化為“”型(或者“”型)的約束條件時(shí),直接將原約束條件兩邊同乘以-1,即(或)B將“=”型的約束條件轉(zhuǎn)化為“”型或者“”型的約束條件時(shí),首先將其寫成兩個(gè)不等式約束條件,然后再轉(zhuǎn)化為所需形式的不等式約束條件,即:(3)非負(fù)約束條件的轉(zhuǎn)換A 若變量xj沒有非負(fù)限制,取值可正可負(fù),這時(shí)可設(shè)兩個(gè)非負(fù)變量和,令,B若變量,可令:例3:請(qǐng)寫出下列的線性規(guī)劃問題的對(duì)偶問題分析:首先將上述非對(duì)稱型問題轉(zhuǎn)換為我們所熟悉的對(duì)稱型問題,然后按照對(duì)稱型問題的方法將原問題轉(zhuǎn)化為對(duì)偶問題。第一,在第一個(gè)約束條件的兩邊同乘以-1.第二,將第三個(gè)約束方程分解成 和再將約束條件兩邊同時(shí)乘以-1,即解:原問題轉(zhuǎn)換為如下的對(duì)稱型:現(xiàn)在四個(gè)約束,分別對(duì)應(yīng)四個(gè)對(duì)偶變量,按表1可得到下面的對(duì)偶問題: 再設(shè),代入上面的數(shù)學(xué)模型就可得出原問題的對(duì)偶問題為:評(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)解為,求對(duì)偶問題的最優(yōu)解.解:根據(jù)對(duì)偶規(guī)則,我們很容易的寫出了原問題的對(duì)偶問題:根據(jù)對(duì)偶性質(zhì),有如下對(duì)應(yīng)關(guān)系:原問題中的原始變量原問題中的松弛變量對(duì)偶問題的剩余變量對(duì)偶問題的原始變量將對(duì)偶問題標(biāo)準(zhǔn)化為:由于為零,上述約束條件簡化為:由此的對(duì)偶問題的最優(yōu)解為:評(píng)注:線性規(guī)劃問題中,有時(shí)為了計(jì)算變得簡單,我們常常需要把線性規(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ù)測,及時(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)營上的問題已經(jīng)越來越廣泛.企業(yè)經(jīng)營者可以根據(jù)市場的具體情況,建立相應(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)1郝英奇.實(shí)用應(yīng)籌學(xué)M.北京:中國人民大學(xué)出版社,2011:70-113.2孫君曼,馮巧玲,孫慧君,李淑君,趙秀花.線性規(guī)劃中原問題與對(duì)偶問題轉(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李玉林,李成松,趙永滿,宋海草.線性規(guī)劃中原問題與對(duì)偶問題轉(zhuǎn)化的思考J.石河子大學(xué)院,2010,(7)

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論