對偶問題在經(jīng)濟(jì)活動中的應(yīng)用

1、湖北民族學(xué)院理學(xué)院畢業(yè)論文(設(shè)計(jì)) 開題報告題 目對偶問題在經(jīng)濟(jì)活動中的應(yīng)用專業(yè)數(shù)學(xué)與應(yīng)用數(shù)學(xué)班 級0209409學(xué) 號 020940907學(xué)生姓名諶小洋指導(dǎo)教師時凌2013年5月24日一、 選題理由運(yùn)籌學(xué)是近六十年代發(fā)展起來的一門學(xué)科。運(yùn)籌學(xué)在生產(chǎn)管理 工程技術(shù) 軍事作戰(zhàn) 科學(xué)實(shí)驗(yàn) 財政經(jīng)濟(jì) 社會科學(xué)以及自然科學(xué)和其他學(xué)科都已去的很多令人矚目的成果。對偶問題是其中一個重要分支。對偶理論是線性規(guī)劃最重要的內(nèi)容之一，其應(yīng)用范圍十分廣泛。主要用于研究有限資源的最佳分配問題，即如何對有限的資源做出最佳方式的太歐賠和最有利的使用，以便最從分得發(fā)揮資源的效能出過去最佳經(jīng)濟(jì)效益。線性規(guī)劃對偶單純形法在實(shí)際

2、應(yīng)用中是一種非常有用的算法，線性規(guī)劃問題是數(shù)學(xué)的一個重要分支,它們所研究的問題是討論在眾多的方案中什么樣的方案是最優(yōu)的,以及怎么找出這些最優(yōu)方案.在現(xiàn)實(shí)的生產(chǎn)活動中這類問題普遍存在,例如在生產(chǎn)計(jì)劃安排中,選擇什么樣的生產(chǎn)方案才能提高產(chǎn)值利潤;在原料配給問題中,怎樣確定各種成分的比例,才能使提高質(zhì)量降低成本的目標(biāo)得以實(shí)現(xiàn):在城市建設(shè)規(guī)劃中,怎樣安排工廠、機(jī)關(guān)、學(xué)校、商店、醫(yī)院、居民區(qū)以及其它單位的合理布局,才能方便群眾,有利于城區(qū)各行各業(yè)的發(fā)展;在資源的分配問題中,怎樣分配有限的資源,使得分配方案既能滿足于各方面的基本要求,又能獲得好的經(jīng)濟(jì)效益。通過對偶單純形法能有效地解決最優(yōu)化問題。本文通過對

3、對偶問題及對偶單純形法的介紹，并對其結(jié)果中所體現(xiàn)的經(jīng)濟(jì)現(xiàn)象中的影子價格做相應(yīng)的解釋，以實(shí)例完成一整套方法的應(yīng)用，展現(xiàn)該方法在經(jīng)濟(jì)活動實(shí)例分析中的應(yīng)用價值。二、 國內(nèi)外研究現(xiàn)狀綜述在線性規(guī)劃早期發(fā)展中最重要的發(fā)現(xiàn)就是對偶問題，即每一個線性規(guī)劃問題(稱為原始問題)都有一個與它對應(yīng)的對偶線性規(guī)劃問題（稱為對偶問題）。1928年美籍匈牙利數(shù)學(xué)家 J.von諾伊曼在研究對策論時已發(fā)現(xiàn)線性規(guī)劃與對策論之間存在著密切的聯(lián)系。兩人零和對策可表達(dá)成線性規(guī)劃的原始問題和對偶問題。他于1947年提出對偶理論。1951年G.B.丹齊克引用對偶理論求解線性規(guī)劃的運(yùn)輸問題，研究出確定檢驗(yàn)數(shù)的位勢法原理。1954年C.萊姆

4、基提出對偶單純形法，成為管理決策中進(jìn)行靈敏度分析的重要工具。對偶理論有許多重要應(yīng)用：在原始的和對偶的兩個線性規(guī)劃中求解任何一個規(guī)劃時，會自動地給出另一個規(guī)劃的最優(yōu)解；當(dāng)對偶問題比原始問題有較少約束時，求解對偶規(guī)劃比求解原始規(guī)劃要方便得多；對偶規(guī)劃中的變量就是影子價格。三、 設(shè)計(jì)（論文）方案通過對偶理論以及社會生產(chǎn)生活中相關(guān)現(xiàn)象的探究，發(fā)現(xiàn)對偶單純形法能有效的解決最優(yōu)化問題，是生產(chǎn)生活更方便。本文通過對對偶問題及對偶單純形法的介紹，并對其結(jié)果中所體現(xiàn)的經(jīng)濟(jì)現(xiàn)象中的影子價格做相應(yīng)的解釋，以實(shí)例完成一整套方法的應(yīng)用，展現(xiàn)該方法在經(jīng)濟(jì)活動實(shí)例分析中的應(yīng)用價值。四、 重點(diǎn)難點(diǎn)及創(chuàng)新之處 本文的重點(diǎn)在于對

5、偶理論以及對偶理論在社會經(jīng)濟(jì)到橫禍中的應(yīng)用，并對其結(jié)果中所體現(xiàn)的經(jīng)濟(jì)現(xiàn)象中的影子價格做相應(yīng)的解釋，從而完成一整套的方法應(yīng)用，體現(xiàn)對偶單純形法在經(jīng)濟(jì)活動實(shí)例中的應(yīng)用價值。五、 應(yīng)收集資料及參考文獻(xiàn)（不低于15篇）1黃培青運(yùn)籌學(xué) ：管理中的定量方法 M上海 :上海交通大學(xué)出版社，20002胡運(yùn)權(quán)運(yùn)籌學(xué)基礎(chǔ)及運(yùn)用M第四版 .北京 :高等教育出版社，20043程理民運(yùn)籌學(xué)模型與方法教程M北京: 清華大學(xué)出版社，20034劉滿鳳 運(yùn)籌學(xué)模型與方法教程例題分析與題解M北京：清華大學(xué)出版社，20045郭耀煌運(yùn)籌學(xué)原理與方法 M西安:西南交通大學(xué)出版社，1998.6 刁在鈞. 運(yùn)籌學(xué).M.第三版.北京: 高等

6、教育出版社 20077 鄧成梁. 運(yùn)籌學(xué)的原理和方法M.第二版.武漢：華中科技大學(xué)出版社，2001.8 胡運(yùn)權(quán).運(yùn)籌學(xué)教程M.北京：清華大學(xué)出版社，1998.9 耿吉第.影子價格的經(jīng)濟(jì)含義及其應(yīng)用J.數(shù)量經(jīng)濟(jì)技術(shù)研究，1994，（06）：46-47.10林豐巖.影子價格在企業(yè)管理中的應(yīng)用J.價值工程，2006，（7）：15-17.11鄧成梁.經(jīng)濟(jì)管理數(shù)學(xué)M.第二版.華中理工大學(xué)出版社，2003.12徐光輝.運(yùn)籌學(xué)與基礎(chǔ)手冊M.北京：科學(xué)出版社，1993.13陶樹人.技術(shù)經(jīng)濟(jì)學(xué)M.北京：經(jīng)濟(jì)管理出版社，1992.14甘應(yīng)愛.運(yùn)籌學(xué)M.北京：清華大學(xué)出版社，1990.15J.富蘭克林 著，俞建，顧

7、悅譯.數(shù)理經(jīng)濟(jì)學(xué)方法M.貴州人民出版社，198516何建坤.實(shí)用線性規(guī)劃及其計(jì)算機(jī)程序M.清華大學(xué)出版社，1985.6、 進(jìn)度安排（1） 四月上旬完成相關(guān)資料的查閱立即準(zhǔn)備工作。（2） 四月中旬通過推相關(guān)知識的理解，確定研究的課題以及完成開題報告。（3） 四月下旬到五月上旬完成論文初稿。（4） 之后對論文進(jìn)行不斷的修改。七、指導(dǎo)教師意見指導(dǎo)教師簽名：年月日八、專業(yè)負(fù)責(zé)人意見（或開題審查小組意見）簽名：年月日湖北民族學(xué)院理學(xué)院數(shù)學(xué)與應(yīng)用數(shù)學(xué) 專業(yè)畢業(yè)論文(設(shè)計(jì))題 目對偶問題在經(jīng)濟(jì)活動中的應(yīng)用設(shè) 計(jì) 人諶小洋教學(xué)基層組織名 稱教學(xué)基層組織負(fù)責(zé)人設(shè) 計(jì) 指 導(dǎo) 教 師 時凌評 閱 人 2013年5

8、月15日摘要線性規(guī)劃對偶單純形法在實(shí)際應(yīng)用中是一種非常有用的算法，線性規(guī)劃問題是數(shù)學(xué)的一個重要分支,它們所研究的問題是討論在眾多的方案中什么樣的方案是最優(yōu)的,以及怎么找出這些最優(yōu)方案.在現(xiàn)實(shí)的生產(chǎn)活動中這類問題普遍存在.關(guān)鍵詞 線性規(guī)劃 對偶單純形法 最優(yōu)方案 AbstractDual simple method for linear programming is a very useful method in the practical application.the linear programming is an important branch of mathematics.the q

9、uestion is discussed in a large number of projects what kind of program is optimal .And how to find the optimal solution.These problems exist in practical production activities.Keywords:method for linear dual simple method the optimal scheme 第一章 對偶問題以及原理1.1 對偶問題對偶問題 每一個線性規(guī)劃問題都伴隨有另一個線性規(guī)劃問題，稱為對偶問題。原來的

10、線性規(guī)劃問題則稱為原始線性規(guī)劃問題，簡稱原始問題。對偶問題有許多重要的特征，它的變量能提供關(guān)于原始問題最優(yōu)解的許多重要資料，有助于原始問題的求解和分析。對偶問題與原始問題之間存在著下列關(guān)系：目標(biāo)函數(shù)對原始問題是極大化，而對偶問題則是極小化。原始問題目標(biāo)函數(shù)中的收益系數(shù)是對偶問題約束不等式中的右端常數(shù)，而原始問題約束不等式中的右端常數(shù)則是對偶問題中目標(biāo)函數(shù)的收益系數(shù)。原始問題和對偶問題的約束不等式的符號方向相反。原始問題約束不等式系數(shù)矩陣轉(zhuǎn)置后即為對偶問題的約束不等式的系數(shù)矩陣。原始問題的約束方程數(shù)對應(yīng)于對偶問題的變量數(shù)，而原始問題的變量數(shù)對應(yīng)于對偶問題的約束方程數(shù)。對偶問題的對偶問題是原始問題

11、，這一性質(zhì)被稱為原始和對偶問題的對稱性。1.2 對偶模型原始問題 對偶問題式中max表示求極大值,min表示求極小值,s.t.表示“約束條件為”；為原始問題的目標(biāo)函數(shù)，為對偶問題的目標(biāo)函數(shù)；為原始問題的決策變量列向量，為對偶問題的決策變量行向量;為原始問題的系數(shù)矩陣,為原始問題的右端常數(shù)列向量，為原始問題的目標(biāo)函數(shù)系數(shù)行向量。1.3對偶問題的基本定理弱對偶定理 若上述原始問題和對偶問題分別有可行解和,則。這個定理表明極大化問題任一可行解的目標(biāo)函數(shù)值總是不大于它的對偶問題的任一可行解的目標(biāo)函數(shù)值。 強(qiáng)對偶定理 若上述原始問題和對偶問題都可行，則它們分別有最優(yōu)解x*和y*，且。 最優(yōu)準(zhǔn)則定理 若上

12、述原始問題和對偶問題分別有可行解和,且兩者的目標(biāo)函數(shù)值相等，即,則兩個可行解分別為對應(yīng)線性規(guī)劃的最優(yōu)解。 互補(bǔ)松弛定理 若上述原始問題和對偶問題分別有可行解和，且和分別為它們的松弛變量,則當(dāng)且僅當(dāng)時，和分別為它們的最優(yōu)解。 松弛定理 若上述原始問題和對偶問題分別有可行解和且和分別為它們的松弛變量，則當(dāng)且僅當(dāng) 和時, 和分別為它們的最優(yōu)解。和這兩個等式稱為互補(bǔ)松弛條件。 對稱對偶線性規(guī)劃 具有對稱形式的線性規(guī)劃的特點(diǎn)是：全部約束條件均為不等式，對極大化問題為，對極小化問題為。全部變量均為非負(fù)。列出對稱對偶線性規(guī)劃的步驟是：規(guī)定非負(fù)的對偶變量，變量數(shù)等于原始問題的約束方程數(shù)。把原始問題的目標(biāo)函數(shù)系

13、數(shù)作為對偶問題約束不等式的右端常數(shù)。把原始問題約束不等式的右端常數(shù)作為對偶問題的目標(biāo)函數(shù)系數(shù)。把原始問題的系數(shù)矩陣轉(zhuǎn)置后作為對偶問題的系數(shù)矩陣。把原始問題約束條件中的不等號反向作為對偶問題約束條件的不等號。將原始問題目標(biāo)函數(shù)取極大化改成對偶問題目標(biāo)函數(shù)取極小化。 非對稱對偶線性規(guī)劃 有時線性規(guī)劃并不以對稱方式出現(xiàn)，如約束條件并不都是同向不等式，變量可以是非正的或沒有符號約束。列寫非對稱對偶線性規(guī)劃可參照原始-對偶表（見表）按下列步驟進(jìn)行：規(guī)定對偶變量，變量個數(shù)等于原始問題約束不等式數(shù)。把原始問題的目標(biāo)函數(shù)系數(shù)作為對偶問題約束不等式的右端常數(shù)。把原始問題約束不等式的右端常數(shù)作為對偶問題的目標(biāo)函數(shù)

14、系數(shù)。把原始問題的系數(shù)矩陣轉(zhuǎn)置后作為對偶問題的系數(shù)矩陣。根據(jù)原始問題的約束不等式情況，確定對偶變量的符號約束。根據(jù)原始問題決策變量的符號約束，確定對偶問題約束不等式的符號方向。 對偶問題的最優(yōu)解 從原始問題的最終單純形表中（最優(yōu)單純形算子）可直接得到對偶問題的最優(yōu)解。原始問題中松弛變量的檢驗(yàn)數(shù)對應(yīng)著對偶問題的解（符號相反）。在用單純形法時每一步迭代可得到原始問題的可行解和對偶問題的補(bǔ)充解,且,若不是原始問題的最優(yōu)解，就不是對偶問題的可行解。最后一步迭代得到原始問題的最優(yōu)解和對偶問題的補(bǔ)充最優(yōu)解，且。是原始問題的影子價格。1.4對偶單純行法解題步驟單純形法求解一般線性規(guī)劃問題的基本方法，在應(yīng)用對

15、偶理論時，需要用到對偶單純行法，就是將單純行法應(yīng)用于對偶問題的計(jì)算，基本思想是保持對偶問題為可行解（這時一般問題為非可行解）的基礎(chǔ)上，通過迭代減小目標(biāo)函數(shù)，當(dāng)原問題也達(dá)到可行解時，即得到了目標(biāo)函數(shù)的最優(yōu)值，對偶單純形法的解題步驟如下：（5） 建立初始單純形表，設(shè)表中檢驗(yàn)數(shù)行的值全部小于等于0，既是對偶問題的一個可行解；（6） 判斷最優(yōu)。檢查列的數(shù)字，若均為非負(fù)，則已得到最優(yōu)解，停止計(jì)算。若列有負(fù)分量則轉(zhuǎn)（3) (3)換基迭代。確定換出變量。在單純形表基解列中從上到下選負(fù)量所對應(yīng)的基變量出基。確定換入變量。在單純形表中若所在的行各系數(shù)（j=1,2，,n）即所有則無可行解，停止計(jì)算：否則在單純形表

16、中按最小值原則從到右變量進(jìn)基解，返回（2）。1.5對偶單純形法的優(yōu)點(diǎn)及用途（1）初始解可以是非可行解，當(dāng)檢驗(yàn)數(shù)都是小于等于零時，就可以經(jīng)行基變換，這樣就避免了增加人工變量，使運(yùn)算簡化。（2） 對變量較少，而約束條件很多的線性規(guī)劃問題可先將其變?yōu)閷ε紗栴}，再用對偶單純形法求解，簡化計(jì)算。（3） 用于靈敏度分析。1.6對偶問題的經(jīng)濟(jì)解釋 對偶問題的產(chǎn)生不是憑空的，往往有其實(shí)際的經(jīng)濟(jì)來源，從對偶問題的基本性質(zhì)看出，當(dāng)達(dá)到最優(yōu)解時，原問題與對偶問題的目標(biāo)函數(shù)值相等，即現(xiàn)考慮最優(yōu)解處，約束方程組右則常數(shù)變動對目標(biāo)函數(shù)的影響。求目標(biāo)函數(shù)對的偏導(dǎo)數(shù)，可得這說明，若原問題的某一約束條件的約束條件的右則常數(shù)增加

17、了一個單位，則由此引起最優(yōu)目標(biāo)函數(shù)值的增加量，就等于與改約束條件相對應(yīng)的對偶變量的最優(yōu)值，這樣一開，在有限資條件下使受益最大話這一問題中，即可把對偶變量的最優(yōu)值看成是相應(yīng)資源，每一單位對于目標(biāo)函數(shù)的貢獻(xiàn)，也就是這些資源被從分利用時所能帶來的利益。從而的值就相當(dāng)于對單位這種資源在實(shí)現(xiàn)最大了利益時的一種價格估計(jì)，這種估計(jì)是針對企業(yè)具體產(chǎn)品而存在的一種特出價格。稱之為影子價格。一般的，對線性規(guī)劃問題的求解是確定資源的最優(yōu)資源的最優(yōu)分配方案，而對于對偶問題的求解則是確定對資源的恰當(dāng)估價，這種古價直接涉及資源的最有效利用，比如在一個大公司的內(nèi)部，課借助資源的影子價格確定一些內(nèi)部結(jié)算價格，以便控制有限資源

18、的使用和考核下屬企業(yè)經(jīng)營的好壞。又如在社會上可對一些最緊缺的資源借助影子價格，規(guī)定使用這種資源，以控制一些經(jīng)濟(jì)效益低的企業(yè)自覺的節(jié)約使用緊缺資源，使有限資源發(fā)揮更大的經(jīng)濟(jì)效益。有效的利用資源的影子價格指導(dǎo)經(jīng)濟(jì)活動是有重大意義的。 第二章 對偶問題的應(yīng)用舉例資源單位消耗產(chǎn)品 A B C 資源限量 勞動力 6 3 5 45 原料 3 4 5 30 單位利潤 3 1 5 例一 某場準(zhǔn)備生產(chǎn)A,B,C三種產(chǎn)品，需要消耗勞動力和原料兩種資源，其有關(guān)數(shù)據(jù)如下表：（1） 用單純形法確定總利潤最大的生產(chǎn)計(jì)劃。（2） 分別求出勞動力和資源的影子價格。若原料不夠可到市場上夠沒，市場價為0.8元/單位。是否要購進(jìn)？

19、購進(jìn)多少？利潤增加多少？解 （1）依題意可得該問題的線性規(guī)劃模型為： 其中分別為產(chǎn)品A,B,C的產(chǎn)量 該題用單純形法迭代的過程如下表31 500基b0456351003034501315010153-101-156100-300-1于是最優(yōu)生產(chǎn)計(jì)劃是生產(chǎn)A,B產(chǎn)品都是0，生產(chǎn)C產(chǎn)品=6可使得利潤最大化，最大利潤為30.（2） 勞動力和原料的影子價格分別是0和1，這說明在企業(yè)最優(yōu)按排中，勞動力資源沒有用完（實(shí)際只用了30單位），而原料資源一耗盡。根據(jù)題目書提供的條件很顯然應(yīng)該適量進(jìn)購原料擴(kuò)大生產(chǎn)。 設(shè)購進(jìn)的原料為，為保持最優(yōu)基不變，必須有。而 解得：-3015.因而最多可購進(jìn)原料12單位，總利潤

20、增加（單位）。凈利潤增加（單位） 例二 某工廠計(jì)劃在下一個生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，要消耗、和三種資源（例如鋼材、煤炭和設(shè)備），已知每件產(chǎn)品對這三種資源的消耗，這三種資源的現(xiàn)有數(shù)量和每件產(chǎn)品可獲得利潤如下表所示。問如何安排生產(chǎn)計(jì)劃，使得既能從分利用現(xiàn)有資源，有使總例如最大？資源資源單價消耗產(chǎn)品甲乙資源限制521702310015150單價例潤1018根據(jù)問題要求，設(shè)決策變量、分別表示下個生產(chǎn)周期產(chǎn)品甲和乙的產(chǎn)量，基于約束條件，本例的數(shù)學(xué)模型為：將其化為線性規(guī)劃的的標(biāo)準(zhǔn)形式為：其對偶問題是：根據(jù)單純形法求原問題的解，的最優(yōu)單純形表如下： 10180000 00110 10018 010000

21、從上表中可以看出，原問題的最優(yōu)解為;目標(biāo)函數(shù)最優(yōu)值為。根據(jù)互補(bǔ)松弛條件，則有： 即也就是說，原問題中的第一種資源（鋼材）的影子價格為，第二種資源（煤炭）的影子價格為，第三種資源（設(shè)備臺時）的影子價格為。此結(jié)果的經(jīng)濟(jì)意義為： （1）在現(xiàn)有資源的基礎(chǔ)上，若再增加1噸煤，可使總利潤增加 萬元；若增加1個臺時，可使總利潤增加 萬元。但增加1噸鋼材，將不會是利潤增加。 （2）對該企業(yè)來說，要加強(qiáng)對煤和機(jī)器設(shè)備的管理，在其不足時，要及時的補(bǔ)充該資源，從而保證生產(chǎn)計(jì)劃，提高企業(yè)利潤。同時，企業(yè)也可對這些資源采取囤積居奇的策略，即在資源市場價格較低，大量買進(jìn)資源，以便在這些資源價格上漲時候高價賣出這些資源。 （3）可根據(jù)資源的影子價格，分析新產(chǎn)品使用資源的經(jīng)濟(jì)效果，一決定新產(chǎn)品是否應(yīng)該投產(chǎn)。如考慮有兩種新產(chǎn)品A和B，他們對資源的消耗定額以及可能獲得的單件利潤如下表所示，決定他們是否值得投產(chǎn)。資源資源單價消耗產(chǎn)品AB影子價格鋼材120煤炭21機(jī)時34單價例潤109計(jì)算產(chǎn)品A和B的相對價值系數(shù)：則由于產(chǎn)品A所能提供的單件利潤小于其隱含成本，相對價值系數(shù)，故產(chǎn)品A不