對偶線性規(guī)劃理論及其在經(jīng)濟(jì)中的應(yīng)用[文獻(xiàn)綜述]

1、畢業(yè)論文文獻(xiàn)綜述畢業(yè)論文文獻(xiàn)綜述信息與計算科學(xué)信息與計算科學(xué)對偶線性規(guī)劃理論及其在經(jīng)濟(jì)中的應(yīng)用對偶線性規(guī)劃理論及其在經(jīng)濟(jì)中的應(yīng)用一、前言部分一、前言部分任一線性規(guī)劃問題都存在另一與之伴隨的線性規(guī)劃問題，他們從不同角度對一個實際問題提出并進(jìn)行描述，組成一對互為對偶的線性規(guī)劃問題。什么是“對偶問題”呢？對偶問題實際上是換一個角度來分析原問題。在線性規(guī)劃分析方法中，假設(shè)原問題的目標(biāo)是盡可能地利用可利用的資源來獲得最大化利潤的話，那么從問題的另

2、一個側(cè)面來思考問題，目標(biāo)變成盡可能地利用原問題所給出的利潤指標(biāo)來調(diào)整范圍條件來減少資源的消耗，于是以原問題目標(biāo)函數(shù)中的決策變量系數(shù)作為新問題的資源，其所形成的線性規(guī)劃模型就成為對偶問題的線性規(guī)劃模型。當(dāng)原問題與對偶問題的最優(yōu)化目標(biāo)函數(shù)值相同時，可以揭示公平交易最為根本的東西：無論是從買方看，還是從賣方看，都實現(xiàn)了自己的交易目標(biāo)最優(yōu)化。在一樁交易中，賣方總是希望獲利最大化，而買方則是希望采購成本最小化，他們的成交底線在哪里呢？從對偶規(guī)劃的

3、角度看，如果交易雙方都是理性交易的話，他們的成交底線應(yīng)該是相同的，即賣方的利益最大化目標(biāo)值等于買方的成本最小化目標(biāo)值。[1][1]所以，對偶線性規(guī)劃理論在經(jīng)濟(jì)中的應(yīng)用是很有實用價值，也是很值得研究的。二、主題部分二、主題部分2.12.1對偶線性規(guī)劃理論概述對偶線性規(guī)劃理論概述2.1.12.1.1對偶線性規(guī)劃理論的發(fā)展歷程及現(xiàn)狀對偶線性規(guī)劃理論的發(fā)展歷程及現(xiàn)狀[2][2][3][3]線性規(guī)劃理論產(chǎn)生于20世紀(jì)30年代。1939年，蘇聯(lián)數(shù)學(xué)

4、家康托羅維奇在《生產(chǎn)組織與計劃中的數(shù)學(xué)方法》一書中，最早提出和研究了線性規(guī)劃問題。1947年，美國數(shù)學(xué)家丹齊克提出線性規(guī)劃的一般數(shù)學(xué)模型和求解線性規(guī)劃問題的通用方法─單純形法，為這門學(xué)科奠定了基礎(chǔ)。1947年，美國數(shù)學(xué)家諾伊曼提出對偶理論開創(chuàng)TTcxwb?3.無界性問題和同時有最優(yōu)解的充分必要條件是它們同時有可行解。而且，若其中有()P()D一個問題無界，則另一個問題無解。4.強對偶性設(shè)和分別為和的可行解，則它們分別為和的最優(yōu)解當(dāng)且僅當(dāng)

5、xw()P()D()P()D()TTcxwb?5.互補松弛性設(shè)和分別為原問題和對偶問題的可行解，則它們分別為和的最xw()P()D()P()D優(yōu)解當(dāng)且僅當(dāng)11()012()012niijjijmjijijibaxwimcawxjn????????????使用矩陣形式，可得和的互補松弛性條件：xw()()0()0TTwAxbcwAx????6.唯一性問題有非退化的最優(yōu)基可行解，那么，其對偶規(guī)劃有唯一的最優(yōu)解。()P()D7.對偶變量的經(jīng)濟(jì)