物流運(yùn)籌學(xué) 課件 劉蓉 第1-3章 物流與運(yùn)籌學(xué)、線性規(guī)劃、對(duì)偶理論x

導(dǎo)論軟科學(xué)中“硬度”較大的一門科學(xué)，兼有邏輯的數(shù)學(xué)和數(shù)學(xué)的邏輯的性質(zhì)。系統(tǒng)工程學(xué)和現(xiàn)代管理學(xué)中一種基礎(chǔ)理論和不可缺少的方法。運(yùn)籌學(xué)與現(xiàn)實(shí)1、2015,迪頓通過引入經(jīng)濟(jì)規(guī)劃研究中的對(duì)偶理論，著重討論了這一理論在福利經(jīng)濟(jì)學(xué)和計(jì)量分析中的應(yīng)用，獲諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。2、2012，羅思和沙普利因“穩(wěn)定匹配理論和市場(chǎng)設(shè)計(jì)實(shí)踐”獲諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)，其理論源于博弈論的思想，運(yùn)籌學(xué)的分支。從1994年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)授予3位博弈論專家（Nash）開始，共有5屆諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)與博弈論的研究有關(guān)。3、作為一種管理層決策的工具，所有管理類專業(yè)、管理科學(xué)與工程、機(jī)械設(shè)計(jì)、建筑設(shè)計(jì)、土建等等專業(yè)都需要運(yùn)籌學(xué)，涉及軍事、建筑、紡織、鋼鐵、煤炭、石油、電力、農(nóng)業(yè)等領(lǐng)域。4、大到國(guó)防戰(zhàn)爭(zhēng)，小到生活瑣事，上至宏觀戰(zhàn)略、下至微觀行動(dòng)，處處涉及運(yùn)籌學(xué)。

運(yùn)籌學(xué)的由來與發(fā)展運(yùn)籌學(xué)的性質(zhì)與特點(diǎn)

運(yùn)籌學(xué)的主要內(nèi)容運(yùn)籌學(xué)的學(xué)科地位運(yùn)

籌

學(xué)

概

況名稱的由來

OperationResearch

運(yùn)籌帷幄“史記”運(yùn)作研究發(fā)展歷程

運(yùn)籌學(xué)的由來與發(fā)展二戰(zhàn)以前萌芽二戰(zhàn)期間產(chǎn)生五六十年代發(fā)展七八十年代成熟一、運(yùn)籌學(xué)的產(chǎn)生與發(fā)展早期運(yùn)籌學(xué)思想及例子齊王賽馬丁渭修皇宮哥尼斯堡七橋問題丁謂修宮宋真宗大中祥符年間，大內(nèi)失火，一夜之間，大片宮室樓臺(tái)、殿閣亭榭變成了廢墟。為了修復(fù)這些宮殿，宋真宗挑選了善于思考的晉國(guó)公丁謂負(fù)責(zé)。當(dāng)時(shí)，要完成這項(xiàng)重大建筑工程，需要解決一系列相關(guān)難題：一是取土困難，因?yàn)橐浇紖^(qū)去取土，路途太遠(yuǎn)；二是與此相關(guān)的物資運(yùn)輸問題難于解決，這不光是運(yùn)土問題，還要運(yùn)輸大量其它材料；三是大片廢墟垃圾的處理問題。丁謂運(yùn)籌規(guī)劃，制定了高明的施工方案。首先下令“鑿?fù)ㄡ槿⊥痢?，從施工現(xiàn)場(chǎng)向外挖了若干條大深溝，挖出的土作為施工用土。這樣一來，取土問題就舍遠(yuǎn)求近地就地解決了。第二步，再把宮外的汴水引入新挖的大溝中，“引諸道竹木筏排及船運(yùn)雜材，盡自塹中入至宮門”。這樣，又解決了大批木材、石料的運(yùn)輸問題。待建筑運(yùn)輸任務(wù)完成之后，再排除塹水，把工地所有垃圾倒入溝內(nèi)，重新填為平地。簡(jiǎn)單歸納起來，就是這樣一個(gè)過程：挖溝（取土）－

引水入溝（運(yùn)輸）－

填溝（處理垃圾）。此方案不僅取得了“一舉而三役濟(jì)”的效果，而且“省費(fèi)以億萬(wàn)計(jì)”，還大大縮短了工期。丁謂所設(shè)計(jì)的方案，其思想與如今運(yùn)籌學(xué)中的統(tǒng)籌方法是一致的。

運(yùn)籌學(xué)思想及例子。。。。。運(yùn)籌學(xué)名詞使用是在1938年(英國(guó)解決雷達(dá)站同整個(gè)作戰(zhàn)系統(tǒng)的協(xié)調(diào)配合問題)。二戰(zhàn)中美，英，加拿大等國(guó)用于戰(zhàn)爭(zhēng)。1948年美國(guó)麻省理工學(xué)院率先開設(shè)了運(yùn)籌學(xué)課程，運(yùn)籌學(xué)成為一門學(xué)科。戰(zhàn)后擴(kuò)展到工業(yè)政府等部門。自60年代以來，由于計(jì)算機(jī)的應(yīng)用運(yùn)籌學(xué)得到了迅速的發(fā)展并開始普及。我國(guó)50年代中期由錢學(xué)森、許國(guó)志等學(xué)者引入我國(guó)，1958年建立了運(yùn)籌學(xué)研究室。1962年管梅谷提出“中國(guó)郵路問題”。1970年華羅庚教授領(lǐng)導(dǎo)下在全國(guó)推廣統(tǒng)籌法和優(yōu)選法，取得顯著成績(jī)，在很多分支領(lǐng)域達(dá)到了當(dāng)時(shí)的國(guó)際水平。1980年4月中國(guó)運(yùn)籌學(xué)學(xué)會(huì)成立，基本形成了自己的理論體系，并在各領(lǐng)域中得到廣泛應(yīng)用。運(yùn)籌學(xué)的產(chǎn)生和發(fā)展

數(shù)學(xué)對(duì)運(yùn)籌學(xué)的作用——是有關(guān)理論和方法的研究基礎(chǔ)，是建立運(yùn)籌學(xué)模型的工具。計(jì)算機(jī)的發(fā)展，促進(jìn)運(yùn)籌學(xué)的進(jìn)一步發(fā)展——高速、可靠的計(jì)算是運(yùn)籌學(xué)解決問題的基本保障。

運(yùn)籌學(xué)定義運(yùn)籌學(xué)是運(yùn)用科學(xué)的方法（如分析、試驗(yàn)、量化等）來決定如何最佳地運(yùn)營(yíng)和設(shè)計(jì)各種系統(tǒng)的一門學(xué)科。運(yùn)籌學(xué)對(duì)經(jīng)濟(jì)管理系統(tǒng)中的人力、物力、財(cái)力等資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理。

引入數(shù)學(xué)方法解決實(shí)際問題

--定性與定量方法結(jié)合系統(tǒng)與整體性

--從全局考察問題應(yīng)用性

--源于實(shí)踐、為了實(shí)踐、服務(wù)于實(shí)踐交叉學(xué)科

--涉及經(jīng)濟(jì)、管理、數(shù)學(xué)、工程和系統(tǒng)等多學(xué)科開放性

--不斷產(chǎn)生新的問題和學(xué)科分支多分支

--問題的復(fù)雜和多樣性運(yùn)籌學(xué)的性質(zhì)與特點(diǎn)線性規(guī)劃數(shù)學(xué)規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃動(dòng)態(tài)規(guī)劃學(xué)科內(nèi)容多目標(biāo)規(guī)劃雙層規(guī)劃組合優(yōu)化最優(yōu)計(jì)數(shù)問題網(wǎng)絡(luò)優(yōu)化排序問題統(tǒng)籌圖隨機(jī)優(yōu)化對(duì)策論排隊(duì)論庫(kù)存論決策分析可靠性分析運(yùn)籌學(xué)的主要內(nèi)容

實(shí)際問題舉例

對(duì)策問題（囚徒困境）

Resource-allocation資源分配Portfolioselection投資組合

Supplychainnetworkdesign供應(yīng)鏈網(wǎng)絡(luò)設(shè)計(jì)實(shí)際問題對(duì)策問題：囚徒困境

囚B囚A

坦白

抵賴

坦白-8，-80，-10

抵賴-10，0-1，-1實(shí)際問題資源分配實(shí)際問題

潘得羅索工業(yè)公司生產(chǎn)膠合板，根據(jù)厚度和所用木材的質(zhì)量而有所不同。因?yàn)楫a(chǎn)品在一個(gè)競(jìng)爭(zhēng)的環(huán)境中進(jìn)行銷售，產(chǎn)品的價(jià)格由市場(chǎng)決定。所以每個(gè)月管理層面臨的一個(gè)關(guān)鍵問題是選擇產(chǎn)品組合以獲取盡可能多的利潤(rùn)。需要考慮當(dāng)前生產(chǎn)產(chǎn)品必須的各種資源的可得數(shù)量。六項(xiàng)最重要的資源為（1）四種類型的原木（根據(jù)原木的質(zhì)量區(qū)分）和（2）生產(chǎn)膠合板的兩項(xiàng)關(guān)鍵作業(yè)的生產(chǎn)能力（模壓作業(yè)和刨光作業(yè)）。

Portfolioselection投資組合實(shí)際問題比爾是Nesbit投資公司的財(cái)務(wù)主管，他必須組合長(zhǎng)期市場(chǎng)有價(jià)證券的業(yè)務(wù)量的每月支付計(jì)劃。證券業(yè)務(wù)量的金額高達(dá)$50,000,000。組合此業(yè)務(wù)量的有價(jià)證券必須很快確定下來，在風(fēng)險(xiǎn)控制限度內(nèi)，以使得一定時(shí)限內(nèi)的收益最大。Supplychainnetworkdesign供應(yīng)鏈網(wǎng)絡(luò)設(shè)計(jì)實(shí)際問題上海國(guó)美電器商場(chǎng)有限公司在上海的商場(chǎng)為什么圓形布點(diǎn)？圍繞上海市外環(huán)線內(nèi)部圓形均勻分布著9家商場(chǎng)，為什么只有一個(gè)配送中心，為什么要建在外環(huán)線的外面？你對(duì)這個(gè)問題如何分析！模型要素

變量—可控因素目標(biāo)—優(yōu)化的動(dòng)力和依據(jù)約束—內(nèi)部條件和外部約束研究?jī)?nèi)容

建模概念最優(yōu)性條件算法靈敏度分析最優(yōu)化模型

實(shí)例問題線性規(guī)劃模型建模分析線性規(guī)劃模型模型線性規(guī)劃模型運(yùn)籌學(xué)在管理中的應(yīng)用生產(chǎn)計(jì)劃：生產(chǎn)作業(yè)的計(jì)劃、日程表的編排、合理下料、配料問題、物料管理等庫(kù)存管理：多種物資庫(kù)存量的管理，庫(kù)存方式、庫(kù)存量等運(yùn)輸問題：確定最小成本的運(yùn)輸線路、物資的調(diào)撥、運(yùn)輸工具的調(diào)度以及建廠地址的選擇等人事管理：對(duì)人員的需求和使用的預(yù)測(cè)，確定人員編制、人員合理分配，建立人才評(píng)價(jià)體系等市場(chǎng)營(yíng)銷：廣告預(yù)算、媒介選擇、定價(jià)、產(chǎn)品開發(fā)與銷售計(jì)劃制定等財(cái)務(wù)和會(huì)計(jì)：預(yù)測(cè)、貸款、成本分析、定價(jià)、證券管理、現(xiàn)金管理等***設(shè)備維修、更新，項(xiàng)目選擇、評(píng)價(jià)，工程優(yōu)化設(shè)計(jì)與管理等運(yùn)籌學(xué)在物流中的運(yùn)用規(guī)劃論：線性規(guī)劃可解決物資調(diào)運(yùn)、配送和人員分派等問題；整數(shù)規(guī)劃可以求解完成工作所需的人數(shù)、機(jī)器設(shè)備臺(tái)數(shù)和廠、庫(kù)的選址等；動(dòng)態(tài)規(guī)劃可用來解決諸如最優(yōu)路徑、資源分配、生產(chǎn)調(diào)度、庫(kù)存控制、設(shè)備更新等問題。存儲(chǔ)論：物資庫(kù)存策略（量、時(shí)間、結(jié)構(gòu)）網(wǎng)絡(luò)（圖）論：路線選擇決策論：對(duì)策論是一種定量分析方法，可以幫助我們尋找最佳的競(jìng)爭(zhēng)策略，以便戰(zhàn)勝對(duì)手或者減少損失。例如在一個(gè)城市內(nèi)有兩個(gè)配送中心經(jīng)營(yíng)相同的業(yè)務(wù)，為了爭(zhēng)奪市場(chǎng)份額，雙方都有多個(gè)策略可供選擇，可以運(yùn)用對(duì)策論進(jìn)行分析，尋找最佳策略。又如，某一地區(qū)，汽車運(yùn)輸公司要與鐵路系統(tǒng)爭(zhēng)奪客源，有多種策略可供選擇，這也可用對(duì)策論研究競(jìng)爭(zhēng)方案，等等排隊(duì)論：排隊(duì)論在物流過程中具有廣泛地應(yīng)用，例如機(jī)場(chǎng)跑道設(shè)計(jì)和機(jī)場(chǎng)設(shè)施數(shù)量問題，如何才能既保證飛機(jī)起降的使用要求，又不浪費(fèi)機(jī)場(chǎng)資源；又如碼頭的泊位設(shè)計(jì)和裝卸設(shè)備的購(gòu)置問題，如何達(dá)到既能滿足船舶到港的裝卸要求，而又不浪費(fèi)港口資源；再如倉(cāng)庫(kù)保管員的聘用數(shù)量問題、物流機(jī)械維修人員的聘用數(shù)量問題，如何達(dá)到既能保證倉(cāng)儲(chǔ)保管業(yè)務(wù)和物流機(jī)械的正常運(yùn)轉(zhuǎn)，又不造成人力浪費(fèi)，等等，這些問題都可以運(yùn)用排隊(duì)論方法加以解決。運(yùn)籌學(xué)解決問題的過程1）提出問題：認(rèn)清問題2）尋求可行方案：建模、求解3）確定評(píng)估目標(biāo)及方案的標(biāo)準(zhǔn)或方法、途徑4）評(píng)估各個(gè)方案：解的檢驗(yàn)、靈敏性分析等5）選擇最優(yōu)方案：決策6）方案實(shí)施：回到實(shí)踐中7）后評(píng)估：考察問題是否得到完滿解決1）2）3）：形成問題；4）5）分析問題：定性分析與定量分析。構(gòu)成決策。教學(xué)計(jì)劃

數(shù)學(xué)規(guī)劃以線性規(guī)劃和整數(shù)規(guī)劃為教授重點(diǎn)，組合優(yōu)化部分主要講網(wǎng)絡(luò)優(yōu)化，而隨機(jī)優(yōu)化講授對(duì)策論，其它部分作為選講內(nèi)容。教學(xué)方法

以授課為主，案例分析與上機(jī)實(shí)習(xí)相結(jié)合。而講課中主要培養(yǎng)用最優(yōu)化方法解決實(shí)際問題的能力。教學(xué)計(jì)劃與方法考核內(nèi)容

理論方法—筆試70%

應(yīng)用能力—實(shí)驗(yàn)10%學(xué)習(xí)態(tài)度--平時(shí)20%考試與要求韓伯棠，管理運(yùn)籌學(xué)，

高等教育出版社，北京，2000年徐光輝等，運(yùn)籌學(xué)手冊(cè)，

科學(xué)出版社，北京，1999年參考資料線性規(guī)劃LinearProgramming

線性規(guī)劃（LinearProgramming，簡(jiǎn)稱LP）運(yùn)籌學(xué)的一個(gè)重要分支，是運(yùn)籌學(xué)中研究較早、發(fā)展較快、理論上較成熟和應(yīng)用上極為廣泛的一個(gè)分支。

1947年G.B.Dantying提出了一般線性規(guī)劃問題求解的方法——單純形法之后，線性規(guī)劃的理論與應(yīng)用都得到了極大的發(fā)展。

60年來，隨著計(jì)算機(jī)的發(fā)展，線性規(guī)劃已廣泛應(yīng)用于工業(yè)、農(nóng)業(yè)、商業(yè)、交通運(yùn)輸、經(jīng)濟(jì)管理和國(guó)防等各個(gè)領(lǐng)域，成為現(xiàn)代化管理的有力工具之一?！?線性規(guī)劃問題及其數(shù)學(xué)模型e.g.1

資源的合理利用問題問：如何安排生產(chǎn)計(jì)劃，使得既能充分利用現(xiàn)有資源又使總利潤(rùn)最大？

表1

產(chǎn)品資源 甲乙?guī)齑媪?/p>

A 1 3 60 B 1 1 40

單件利潤(rùn)

15 25

某工廠在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，要消耗A、B兩種資源，已知每件產(chǎn)品對(duì)這兩種資源的消耗，這兩種資源的現(xiàn)有數(shù)量和每件產(chǎn)品可獲得的利潤(rùn)如表1。第一章線性規(guī)劃及單純形法maxz=15x1+25x2s.t.x1+3x2≤60

x1

+x2≤40x1，x2≥0

解：

設(shè)x1，x2

為下一個(gè)生產(chǎn)周期產(chǎn)品甲和乙的產(chǎn)量；

約束條件：Subjecttox1+3x2≤60x1

+x2≤40x1，x2≥0目標(biāo)函數(shù)：z=15x1+25x2

表1

產(chǎn)品資源 甲乙?guī)齑媪?/p>

A 1 3 60 B 1 1 40

單件利潤(rùn)

15 25

決策變量§1線性規(guī)劃問題及其數(shù)學(xué)模型e.g.2

營(yíng)養(yǎng)問題

假定在市場(chǎng)上可買到B1,B2,…Bnn

種食品，第

i

種食品的單價(jià)是ci,另外有m

種營(yíng)養(yǎng)A1,A2,…Am。設(shè)

Bj內(nèi)含有

Ai

種營(yíng)養(yǎng)數(shù)量為aij

(i=1~m,j=1~n)，又知人們每天對(duì)Ai

營(yíng)養(yǎng)的最少需要量為bi。見表2：

表2

食品最少營(yíng)養(yǎng) B1B2…Bn

需要量

A1 a11 a12…a1n b1A2 a21 a22…a2n b2………………Amam1am2…amn

bm

單價(jià)

c1c2…cn

試在滿足營(yíng)養(yǎng)要求的前提下，確定食品的購(gòu)買量，使食品的總價(jià)格最低。第一章線性規(guī)劃及單純形法

表2

食品最少營(yíng)養(yǎng) B1B2…Bn

需要量

A1 a11 a12…a1n b1A2 a21 a22…a2n b2………………Amam1am2…amn

bm

單價(jià)

c1c2…cn

解：

設(shè)xj

為購(gòu)買食品

Bj

的數(shù)量(j=1,2,…,n)（i=1,2,…,m）xj≥0（j=1,2,…,n）§1線性規(guī)劃問題及其數(shù)學(xué)模型三個(gè)基本要素：Note：1、善于抓住關(guān)鍵因素，忽略對(duì)系統(tǒng)影響不大的因素；2、可以把一個(gè)大系統(tǒng)合理地分解成n

個(gè)子系統(tǒng)處理。1、決策變量xj≥0

2、約束條件——一組決策變量的線性等式或不等式3、目標(biāo)函數(shù)——決策變量的線性函數(shù)第一章線性規(guī)劃及單純形法max（min）z=c1x1+c2x2+…+cnxn

s.t.a11x1+a12x2+…+a1nxn≤（或=，≥）b1

a21x1+a22x2+…+a2nxn≤（或=，≥）b2

……am1x1+am2x2+…+amnxn

≤（或=，≥）bm

xj

≥0（j=1,2,…,n） 其中aij、bi、cj（i=1,2,…,m；j=1,2,…,n）為已知常數(shù)線性規(guī)劃問題的一般形式：§1線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題的標(biāo)準(zhǔn)形式：maxz=c1x1+c2x2+…+cnxn

s.t.a11x1+a12x2+…+a1nxn=b1

a21x1+a22x2+…+a2nxn=b2

……am1x1+am2x2+…+amnxn

=bm

xj

≥0（j=1,2,…,n）

bi≥0（i=1,2,…,m） 特點(diǎn)：1、目標(biāo)函數(shù)為極大化；2、除決策變量的非負(fù)約束外，所有的約束條件都是等式，且右端常數(shù)均為非負(fù)；3、所有決策變量均非負(fù)。第一章線性規(guī)劃及單純形法如何轉(zhuǎn)化為標(biāo)準(zhǔn)形式？1、目標(biāo)函數(shù)為求極小值，即為：。

因?yàn)榍髆inz等價(jià)于求max(-z)，令z’=-z，即化為：

2、約束條件為不等式，xn+1≥0松弛變量如何處理？§1線性規(guī)劃問題及其數(shù)學(xué)模型

３、右端項(xiàng)bi<0時(shí)，只需將等式兩端同乘（-1）則右端項(xiàng)必大于零

4、決策變量無非負(fù)約束

設(shè)xj

沒有非負(fù)約束，若xj≤0，可令xj=-xj’

，則xj’≥0；

又若xj

為自由變量，即xj

可為任意實(shí)數(shù)，可令xj

=xj’-xj’’，且xj’,xj’’≥0第一章線性規(guī)劃及單純形法e.g.3試將LP

問題minz=-x1+2x2-3x3

s.t.x1+x2+x3

≤7x1-x2+x3≥2-3x1+x2+2x3=-5x1,x2≥0

化為標(biāo)準(zhǔn)形式。解：令x3=x4-x5

其中x4、x5

≥0；對(duì)第一個(gè)約束條件加上松弛變量x6

；對(duì)第二個(gè)約束條件減去松弛變量x7

；對(duì)第三個(gè)約束條件兩邊乘以“-1”；令z’=-z

把求minz

改為求maxz’maxz’=x1-2x2+3x4-3x5

s.t.x1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=23x1-x2-2x4+2x5=5x1,x2,x4,x5,x6,x7≥0

§1線性規(guī)劃問題及其數(shù)學(xué)模型LP的幾種表示形式：§2線性規(guī)劃問題的圖解法定義1在LP問題中，凡滿足約束條件(2)、(3)的解x=(x1,x2,…,xn)T

稱為L(zhǎng)P問題的可行解，所有可行解的集合稱為可行解集（或可行域）。記作D={x|Ax=b,x≥0}。定義2

設(shè)LP問題的可行域?yàn)镈，若存在x*∈D，使得對(duì)任意的x∈D

都有cx*≥cx，則稱x*為L(zhǎng)P問題的最優(yōu)解，相應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)值，記作z*=cx*?！?線性規(guī)劃問題的圖解法maxz=15x1+25x2s.t.x1+3x2≤60

x1

+x2≤40x1，x2≥0

(40,0)(0,0)BC(30,10)O(0,20)AL1L2Z=250目標(biāo)函數(shù)變形：x2=-3/5

x1+z/25x2x1最優(yōu)解：

x1=30x2=10最優(yōu)值：zmax=700B點(diǎn)是使z達(dá)到最大的唯一可行點(diǎn)第一章線性規(guī)劃及單純形法LP問題圖解法的基本步驟：1、在平面上建立直角坐標(biāo)系；2、圖示約束條件，確定可行域和頂點(diǎn)坐標(biāo)；3、圖示目標(biāo)函數(shù)（等值線）和移動(dòng)方向；4、尋找最優(yōu)解?！?線性規(guī)劃問題的圖解法maxz=3x1+5.7x2

s.t.x1+1.9x2≥3.8

x1-1.9x2≤3.8x1+1.9x2≤11.4

x1-1.9x2≥-3.8

x1，x2≥0x1x2ox1-1.9x2=3.8x1+1.9x2=3.8x1+1.9x2=11.4（7.6,2）D0=3x1

+5.7x2

maxZ

minZ（3.8,4）34.2=3x1

+5.7x2

可行域x1-1.9x2=-3.8(0,2)(3.8,0)

綠色線段上的所有點(diǎn)都是最優(yōu)解,即有無窮多最優(yōu)解。Zman=34.2第一章線性規(guī)劃及單純形法maxz=2x1+2x2s.t.2x1–x2≥2-x1+4x2≤4

x1，x2≥0OA(１,0)x1x2Note:可行域?yàn)闊o界區(qū)域，目標(biāo)函數(shù)值可無限增大，即解無界。稱為無最優(yōu)解。可行域?yàn)闊o界區(qū)域一定無最優(yōu)解嗎？無可行解

指找不到一組變量能滿足線性規(guī)劃的所有約束條件的情況，也就是線性規(guī)劃問題不存在可行解，或者說可行域是空集。例如線性規(guī)劃問題：§2線性規(guī)劃問題的圖解法由以上兩例分析可得如下重要結(jié)論：1、LP問題從解的角度可分為：⑴有可行解⑵無可行解有唯一最優(yōu)解b.有無窮多最優(yōu)解C.無最優(yōu)解2、LP問題若有最優(yōu)解，必在可行域的某個(gè)頂點(diǎn)上取到；若有兩個(gè)頂點(diǎn)上同時(shí)取到，則這兩點(diǎn)的連線上任一點(diǎn)都是最優(yōu)解?！?線性規(guī)劃問題的圖解法圖解法優(yōu)點(diǎn)：直觀、易掌握。有助于了解解的結(jié)構(gòu)。圖解法缺點(diǎn)：只能解決低維問題，對(duì)高維無能為力。例某工廠經(jīng)市場(chǎng)調(diào)研，決定生產(chǎn)甲、乙兩種產(chǎn)品，其單臺(tái)利潤(rùn)分別為60元和30元，兩種產(chǎn)品共用一種鋼材、一臺(tái)設(shè)備，其資源及獲利情況如下：甲乙現(xiàn)有資源鋼材消耗定額（公斤/臺(tái)）24600公斤臺(tái)時(shí)消耗定額（小時(shí)/臺(tái)）31400小時(shí)配件（件/臺(tái)）20250件利潤(rùn)（元）6030求利潤(rùn)最大的產(chǎn)品結(jié)構(gòu)決策。作業(yè)練習(xí)②確定目標(biāo)函數(shù)及約束條件——建立數(shù)學(xué)模型目標(biāo)函數(shù)：③將不等式變?yōu)榈仁讲⒃趚1－x2坐標(biāo)圖中作出直線④最優(yōu)點(diǎn)在凸邊形的頂點(diǎn)，代入（1）式可得maxP解：①設(shè)變量：設(shè)甲生產(chǎn)x1臺(tái)，乙生產(chǎn)x2臺(tái)，可得最大利潤(rùn)約束條件：05050100100150150200250300350200250300350400x1x2A(0,150)B(100,100)C(125,25)D(125,0)(4)基、基向量、基變量⊙設(shè)r(A)=m,并且B是A的m階非奇異的子矩陣（det(B)

0),則稱矩陣B為線性規(guī)劃問題的一個(gè)基?！丫仃嘊=（P1，P2….Pm)，其列向量Pj稱為對(duì)應(yīng)基B的基向量?！雅c基向量Pj

相對(duì)應(yīng)的變量xj就稱為基變量，其余的就稱為非基變量。MaxS=CX（3-6）

s.t.AX=b（3-7）

X

0（3-8）基解.基可行解.可行基⊙對(duì)于某一特定的基B，非基變量取0值的解，稱為基解?！褲M足非負(fù)約束條件的基礎(chǔ)解，稱為基可行解?！雅c基可行解對(duì)應(yīng)的基，稱為可行基。為了理解基解.基可行解.最優(yōu)解的概念，用下列例子說明：例：maxS=2x1+3x2s.t.-2x1+3x2

63x1-2x2

6x1+x2

4x1,x2

0x243211234x1O-1-1-2-2-3-3-2x1+3x2=63x1-2

x2=6x1+x2=4AQ1Q2Q3Q4BmaxS=2x1+3x2s.t.-2x1+3x2

63x1-2x2

6x1+x2

4x1,x2

0x243211234x1O-1-1-2-2-3-3ABx243211234x1O-1-1-2-2-3-3-2x1+3x2

63x1-2

x2

6x1+x2

4AQ1Q2Q3Q4BmaxS=2x1+3x2s.t.-2x1+3x2

63x1-2x2

6x1+x2

4x1,x2

0滿足約束條件

-2x1+3x2

63x1-2

x2

6x1+x2

4

與坐標(biāo)系

x1,x2=0的交點(diǎn)（O，A，B，Q1，Q2，Q3，Q4）都是代表基解。注意：點(diǎn)（4，0）（0，4）不滿足約束條件滿足約束條件

-2x1+3x2

63x1-2

x2

6x1+x2

4

且滿足

x1,x2

0的交點(diǎn)（O，Q1，Q2，Q3，Q4）都是代表基可行解。注意：點(diǎn)A，B不滿足x1,x2

0點(diǎn)（O，Q1，Q2，Q3，Q4）剛好是可行域的頂點(diǎn)。x243211234x1O-1-1-2-2-3-3-2x1+3x2

63x1-2

x2

6x1+x2

4AQ1Q2Q3Q4B可行域x243211234x1O-1-1-2-2-3-3-2x1+3x2

63x1-2

x2

6x1+x2

4AQ1Q2Q3Q4B可行域本問題解的情況：基解：點(diǎn)（O，A，B，Q1，Q2，Q3，Q4）可行解：由點(diǎn)（O，Q1，Q2，Q3，Q4）圍成的區(qū)域。基可行解：點(diǎn)（O，Q1，Q2，Q3，Q4）最優(yōu)解：

Q3解的集合：非可行解可行解解的集合：基解解的集合：可行解基解基可行解解的集合：可行解基解基最優(yōu)解基可行解線性規(guī)劃（2）-單純形方法單純形方法基本思路：從可行域中某個(gè)基可行解（一個(gè)頂點(diǎn)）開始（稱為初始基可行解）。如可能，從可行域中求出具有更優(yōu)目標(biāo)函數(shù)值的另一個(gè)基可行解（另一個(gè)頂點(diǎn)），以改進(jìn)初始解。繼續(xù)尋找更優(yōu)的基可行解，進(jìn)一步改進(jìn)目標(biāo)函數(shù)值。當(dāng)某一個(gè)基礎(chǔ)可行解不能再改善時(shí)，該解就是最優(yōu)解。

由于軍事上的需要，擔(dān)任美國(guó)空軍審計(jì)官的數(shù)學(xué)顧問旦茨基博士，根據(jù)在第二次世界大戰(zhàn)中實(shí)際規(guī)劃的經(jīng)歷，從1946年起就開始尋找一種方法，想用它較快地計(jì)算出包括進(jìn)度、訓(xùn)練及后勤供應(yīng)在內(nèi)的規(guī)劃問題。研究先從建立數(shù)學(xué)模型著手。在研究中，得到了投入—產(chǎn)出模型的啟發(fā)，并在其他數(shù)學(xué)家的支持下，提出了解決線性規(guī)劃問題極其有效的單純形方法。單純形法的由來

旦茨基教授在一次演說中，形象而風(fēng)趣地說明了單純形解法的奇效：設(shè)給70個(gè)人分配70項(xiàng)任務(wù)，每人一項(xiàng)。如果每人完成各項(xiàng)任務(wù)所需要付出的代價(jià)（時(shí)間、工資）都知道，要尋求代價(jià)最小的方案。所有的可行方案共有70！種。70！比還要大。如果用窮舉法，逐個(gè)來比較的話，基本是不可能的。而用單純形法軟件，幾秒鐘就可以給出答案。

不僅如此，還能預(yù)測(cè)當(dāng)方案中某因素發(fā)生變化，對(duì)決策目標(biāo)的影響。神奇的單純形法返回目錄

線性規(guī)劃問題的可行解有無窮多個(gè)，與某一凸集上的無窮多個(gè)點(diǎn)一一對(duì)應(yīng)。要從無窮多個(gè)可行解中尋找最優(yōu)解，幾乎不可能?？梢宰C明，最優(yōu)解必定能取在凸集的頂點(diǎn)（極點(diǎn)、基本可行解）上，而極點(diǎn)的個(gè)數(shù)是有限的。當(dāng)然，這個(gè)“有限”，數(shù)字往往相當(dāng)可觀，如前面的70！，要逐個(gè)比較的話，也不現(xiàn)實(shí)。而單純形解法，用跨躍的方式，高速地優(yōu)化基本可行解，迅速達(dá)到最優(yōu)。單純形法—跨躍式地尋求最優(yōu)解優(yōu)maxSS=ooABCDE凸集概念：

設(shè)D是n維線性空間Rn的一個(gè)點(diǎn)集，若D中的任意兩點(diǎn)x(1),x(2)的連線上的一切點(diǎn)x仍在D中，則稱D為凸集。凸集（非凸集）

開始，用單純形表進(jìn)行換基迭代。后來的改進(jìn)單純形法，大大減少了計(jì)算量。為利用計(jì)算機(jī)創(chuàng)造了條件。最初使用手搖和電動(dòng)臺(tái)式計(jì)算器，不能完成特大量的計(jì)算。由于線性規(guī)劃應(yīng)用廣泛，大到整個(gè)國(guó)民經(jīng)濟(jì)計(jì)劃，小到一個(gè)車間的生產(chǎn)安排，因此受到重視。解線性規(guī)劃的能力迅速提高。1951年只能解約束條件為十幾個(gè)方程的問題?，F(xiàn)在，能解上萬(wàn)個(gè)方程的問題。且解題速度大大加快。專家們已經(jīng)用單純形解法開發(fā)出了計(jì)算效率極高應(yīng)用軟件。運(yùn)用這個(gè)軟件，輸入數(shù)據(jù)，立即就可以打印出結(jié)果。

單純形解法應(yīng)用的發(fā)展過程例：一個(gè)企業(yè)需要同一種原材料生產(chǎn)甲乙兩種產(chǎn)品，它們的單位產(chǎn)品所需要的原材料的數(shù)量及所耗費(fèi)的加工時(shí)間各不相同，從而獲得的利潤(rùn)也不相同（如下表）。那么，該企業(yè)應(yīng)如何安排生產(chǎn)計(jì)劃，才能使獲得的利潤(rùn)達(dá)到最大？解：數(shù)學(xué)模型

maxS=6x1+4x2s.t.2x1+3x2

1004x1+2x2

120x1,x2

0引進(jìn)松弛變量x3,x4

0數(shù)學(xué)模型標(biāo)準(zhǔn)形式：

maxS=6x1+4x2s.t.2x1+3x2+x3=1004x1+2x2+x4=120x1,x2,

x3,x4

0

A=（P1，P2，P3，P4）

=23104201

X=（x1,x2,x3,x4)B=(P3，P4

）=1001P3，P4線性無關(guān)，x3和x4是基變量，x1、x2是非基變量。

用非基變量表示的方程：

x3=100-2x1-3x2x4=120-4x1-2x2(I)S=6x1+4x2令非基變量（x1,

x2）t=（0，0）t

得基礎(chǔ)可行解：

x(1)=(0,0,100,120)t

S1=0

經(jīng)濟(jì)含義：不生產(chǎn)產(chǎn)品甲乙，利潤(rùn)為零。分析：S=

6x1+

4x2（分別增加單位產(chǎn)品甲、乙，目標(biāo)函數(shù)分別增加6、4，即利潤(rùn)分別增加6百元、4百元。）

增加單位產(chǎn)品對(duì)目標(biāo)函數(shù)的貢獻(xiàn)，這就是檢驗(yàn)數(shù)的概念。

增加單位產(chǎn)品甲（x1）比乙對(duì)目標(biāo)函數(shù)的貢獻(xiàn)大（檢驗(yàn)數(shù)最大），把非基變量x1換成基變量，稱x1為進(jìn)基變量，而把基變量x4換成非基變量，稱x4為出基變量。確定了進(jìn)基變量x1

，出基變量x4

以后，得到新的系統(tǒng)：

x3=40-2x2+（1/2）x4x1=30-（1/2）x2-（1/4）x4(II)S=180+x2-（3/2）x4令新的非基變量（

x2，x4）=（0，0）t得到新的基礎(chǔ)可行解：x(2)=(30,0,40,0)t

S2=180經(jīng)濟(jì)含義：生產(chǎn)甲產(chǎn)品30個(gè)，獲得利潤(rùn)18000元。

這個(gè)方案比前方案，但是否是最優(yōu)？分析：S=180+x2-（3/2）x4非基變量x2系數(shù)仍為正數(shù)，確定x2為進(jìn)基變量。在保證常數(shù)項(xiàng)非負(fù)的情況下，確定x3為出基變量。得到新的系統(tǒng)：

x1=20+（1/4）x3-（3/8）x4x2=20-（1/2）x3+（1/4）x4(III)S=200-（1/2）x3-（5/4）x4

令新的非基變量（x3,x4）t=（0,0）t得到新的基礎(chǔ)可行解：x(3)=(20,20,0,0)t

S3=200經(jīng)濟(jì)含義：分別生產(chǎn)甲乙產(chǎn)品20個(gè)，可獲得利潤(rùn)20000元。分析：S=200-（1/2）x3-（5/4）x4目標(biāo)函數(shù)中的非基變量的系數(shù)無正數(shù)，S3=200是最優(yōu)值，x(3)=(20,20,0,0)t是最優(yōu)解。該企業(yè)分別生產(chǎn)甲乙產(chǎn)品20個(gè)，可獲得最大利潤(rùn)20000元。X(3)=(20,20,0,0)t相當(dāng)于Q2(20,20)X(1)=(0,0,100,120)t相當(dāng)于O(0,0)X(1)=(0,0,100,120)t相當(dāng)于O(0,0)X(2)=(30,0,40,0)t相當(dāng)于Q1(30,0)X(2)=(30,0,40,0)t相當(dāng)于Q1(30,0)X(3)=(20,20,0,0)t相當(dāng)于Q2(20,20)舉例:求解下列線性規(guī)劃問題maxz＝1.5x1+2.4x2+0x3+0x4+0x5S.t.x1+x2+x3=1003x1+2x2+x4=1902x1+3x2+x5=240xj≥0(j=1,2,3…5)解：約束方程的系數(shù)矩陣為：1

1

100

A=(P1，P2，P3

，P4

，P5

）＝3

2

010

23

001初始可行基為：100B＝（P3，P4

，P5

）＝010001用非基變量表達(dá)基變量：

x3=100

－x1－1x2

x4=190

－3x1－2x2

x5=240

－2x1－3x2

將上式代入目標(biāo)函數(shù)得：

z=0+１.５x1+2.4x2令非基變量為零，即令x1＝0，x2＝0得一個(gè)基可行解：x（0）＝（0,0,100,190,240)此時(shí)得z＝0非基變量的系數(shù)都是正數(shù)，因此將非基變量變換成基變量，目標(biāo)函數(shù)的值就可能變大。取x2為入基變量（一般選擇正價(jià)值系數(shù)最大的非基變量為入基變量，而2.4>1.5）于是還要確定基變量x3，x4，x5中的一個(gè)換出來成為非基變量。下面來確定換出變量：當(dāng)x1=0時(shí)（先固定x1是兩個(gè)非基變量中的一個(gè)）,x3=100

－1x2≥0x4=190

－2x2≥0x5=240

－3x2≥0要讓x3，x4，x5非負(fù)，且有一個(gè)為0，只有選擇x2≤80時(shí)，才能使x3,x4x5同時(shí)非負(fù)。(此時(shí)x3≥20>0，x4≥30>0，x5≥0)因此只有當(dāng)x2=min(100/1,190/2,240/3)=80時(shí),才能使x3,x4x5非負(fù)的同時(shí)，有一個(gè)原來的基變量x5取值為0，從而可以換出來成為非基變量。其中x3=20

>0，

x4=30

>0，

X5=0，取X5為出基變量（所謂的最小比值規(guī)則）x2≤100x2≤

95x2≤80x2≤80用非基變量表達(dá)基變量：

x3+x2=100-x1x3=20

-1/3x1+1/3x5

x4+2x2=190-3x1x4=30-5/3x1+2/3x5

3x2=240-2x1-

x5x2=80

-2／3x1-1/3x5

將上式代入目標(biāo)函數(shù)得：z=192-0.1x1-0.8x5令非基變量為零，即x1＝0，x5＝0得一個(gè)基本可行解：x（1）＝（0,80,20,30,0),z=192由于非基變量的價(jià)值系數(shù)都是負(fù)數(shù)，而x1≥0，x5≥0，因此當(dāng)x1＝0，x5＝0時(shí)，z取得最大值192。所以最優(yōu)解

X*=x（1）＝（0,80,20,30,0),目標(biāo)函數(shù)值z(mì)*=192

c

c1c2cmcm+1cm+2cncBxBx1x2xmxm+1xm+2xnbc1c2cmx1x2xm

100a’1m+1a’1m+2a’1n

010a’2m+1a’2m+2a’2n

001a’mm+1a’mm+2a’mnb’1b’2b’m檢驗(yàn)數(shù)

0

00-z(0)用單純形表求解問題例、用單純形表求解LP問題解：化標(biāo)準(zhǔn)型表1：列初始單純形表（單位矩陣對(duì)應(yīng)的變量為基變量）

21000

01505100

0

24620100511001

21000

—24/65/1正檢驗(yàn)數(shù)中最大者對(duì)應(yīng)的列為主列主元化為1主列單位向量換出換入最小的值對(duì)應(yīng)的行為主行表2：換基（初等行變換，主列化為單位向量，主元為1）

21000

01505100

2

412/601/600104/60-1/61

01/30-1/30

15/524/26/4

0*52*2/6+0*4/61-2/3=主元檢驗(yàn)數(shù)>0確定主列

最小確定主列表3：換基

（初等行變換，主列化為單位向量，主元為1）

21000

015/20015/4-15/2

2

7/21001/4-1/213/2010-1/43/2000-1/4-1/2

最優(yōu)解為X=(7/2,3/2,15/2,0,0)目標(biāo)函數(shù)值Z=8.5

2*7/21*3/2+0*15/28.5檢驗(yàn)數(shù)<=0例2、試?yán)脝渭冃伪砬罄?中的最優(yōu)解解：

得初始的單純形表：初始基本可行解，Z=-1，122108x4-1-130400341017x51x1x2x3x4x5bXBCBΘ523-11C

換入變量，換出變量，２為主元進(jìn)行旋轉(zhuǎn)變換基本可行解，Z=15，1/2

1

1

1/2

04x33151-40-205/230-1/213x51

x1

x2

x3

x4

x5bXBCBΘ523-11C122108x4-1-130400341017x51x1x2x3x4x5bXBCBΘ523-11C8/27/1

最優(yōu)解

最優(yōu)值

換入變量，換出變量，５/２為主元進(jìn)行旋轉(zhuǎn)變換4/1/21/2

1

1

1/2

04x33151-40-203/5/25/230-1/213x51

x1

x2

x3

x4

x5bXBCBΘ523-11C02/513/5-1/517/5x3381/5

0-26/50-9/5-2/516/50-1/52/56/5x15x1x2x3x4x5bXBCBΘ

523-11Cmaxz=15x1+25x2s.t.x1+3x2≤60

x1

+x2≤40x1，x2≥0

maxz=15x1+25x2+0x3+0x4s.t.x1+3x2+x3=60

x1

+x2++x4=40x1，x2

，x3

，x4≥0

00

ccBxB00x3x4檢驗(yàn)數(shù)152500x1

x2

x3

x413101101152500b6040001θx(0)=(0,0,60,40)Tz0=0x21/3-500x(1)=(0,20,0,20)Tz1=500x10700x(2)=(30,10,0,0)Tz2=7001/2檢驗(yàn)數(shù)都小于等于零x(2)為最優(yōu)解

zmax

=70060/340/12531/312000-1/312020/3-25/3020/1/320/2/3152/32/310-1/23/2300-1/2100-5-10唯一最優(yōu)解與無窮多個(gè)最優(yōu)解若最終單純形表的非基變量的檢驗(yàn)數(shù)都小于零,則線性規(guī)劃問題有唯一的最優(yōu)解若最終單純形表中存在某個(gè)非基變量,其檢驗(yàn)數(shù)等于零,則該線性規(guī)劃問題有無窮多個(gè)最優(yōu)解.例3、用單純形方法求解線性規(guī)劃問題解：本題的目標(biāo)函數(shù)是求極小化的線性函數(shù)，可以令則這兩個(gè)線性規(guī)劃問題具有相同的可行域和最優(yōu)解，只是目標(biāo)函數(shù)相差一個(gè)符號(hào)而已。

010103x220012-12x30-010103x224/1101004x303/1010103x40_101004x308

0000-1100-212x116

100-202/1100-212x500

120008/2120018x50

x1x2x3x4x5bXBCBΘ12000C最優(yōu)解最優(yōu)值2/23/1-利用單純形法求解下列線性規(guī)劃問題首先將線性規(guī)劃標(biāo)準(zhǔn)化很明顯可以以x4、x5作為初始基變量，得到初始單純形如下：-22100CBXBx1x2x3x4x5b00x4x532-2-1-21100114-22100此時(shí)，x2的檢驗(yàn)數(shù)大于0，還沒有得到最優(yōu)解。但是我們以x2作為換入變量，但是x2所在列所有系數(shù)都小于0，此時(shí)該線性規(guī)劃存在無界解。單純形法計(jì)算過程構(gòu)造初始單純形表對(duì)標(biāo)準(zhǔn)化后的線性規(guī)劃問題，首先找出初始基變量，構(gòu)造初始單純形表，其中檢驗(yàn)數(shù)由（2.18）計(jì)算。相應(yīng)地可以得到初始基可行解，基可行解的目標(biāo)函數(shù)值。最優(yōu)性檢驗(yàn)若得到單純形表中所有的檢驗(yàn)數(shù)都小于或等于零，則該單純形表給出的基可行解就是最優(yōu)解，終止計(jì)算。否則進(jìn)行下一步。確定換入變量選擇最大的正檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量為換入變量。確定換出變量若換入變量（更一般地，若某個(gè)正檢驗(yàn)數(shù)對(duì)應(yīng)的變量）所作列的系數(shù)均小于或等于零，則線性規(guī)劃問題為無界解，終止計(jì)算。否則用換入變量所作列的系數(shù)去除b列的對(duì)應(yīng)數(shù)，在除得的商中選擇最小者對(duì)應(yīng)的基變量為換出變量。旋轉(zhuǎn)運(yùn)算確定換入和換出變量后得到新的基變量，然后以換入變量所在列、換出變量所在行交叉處的元素為主元，通過矩陣的初等行變換（一般不使用交換兩行的運(yùn)算）將約束方程組增廣矩陣中主元變換為1，主元列的其它元素變換為零。從而得到一個(gè)新的單純形表。然后回到第2步。第3章線性規(guī)劃對(duì)偶理論及其應(yīng)用例1

穗羊公司的例子3.1線性規(guī)劃的對(duì)偶問題生產(chǎn)計(jì)劃問題（LP1）III每周可使用量A（千克）125B（噸）214C（百工時(shí)）439單位產(chǎn)品利潤(rùn)（萬(wàn)元）32III每周可使用量A（千克）125B（噸）214C（百工時(shí)）439單位產(chǎn)品利潤(rùn)（萬(wàn)元）32穗羊公司如果要出讓其擁有的資源:單價(jià)y1,y2,y3y1y2y3生產(chǎn)每件產(chǎn)品的資源出讓后獲得的收益應(yīng)該不低于該件產(chǎn)品的收益.產(chǎn)品I:產(chǎn)品II:接手其所有資源的廠家期望出價(jià)越低越好:資源定價(jià)問題（LP2）比較原問題（生產(chǎn)計(jì)劃）對(duì)偶問題（資源定價(jià)）3.1.2規(guī)范形式的線性規(guī)劃問題原問題（LP）對(duì)偶問題（DLP）

規(guī)范形式最大化問題:約束條件全為型決策變量全部非負(fù)最小化問題:約束條件全為型決策變量全部非負(fù)規(guī)范形式的對(duì)偶關(guān)系原問題對(duì)偶問題目標(biāo)函數(shù):maxCX目標(biāo)函數(shù):minb′Ym個(gè)約束條件:AXbm個(gè)決策變量:Y0n個(gè)決策變量:X0n個(gè)約束條件:A′YC′原問題對(duì)偶問題非規(guī)范形式的對(duì)偶關(guān)系對(duì)非規(guī)范形式的對(duì)偶關(guān)系，只需對(duì)上述表進(jìn)行相應(yīng)修改即可：例如對(duì)于一個(gè)最小化問題，若某個(gè)決策變量yi

0,則其對(duì)偶的約束條件為型的;若其某個(gè)約束條件是型,則其對(duì)應(yīng)的對(duì)偶變量是非正的.3.1.3非規(guī)范形式線性規(guī)劃的對(duì)偶問題1變量取值范圍不符合非負(fù)要求的情況3.1.3非規(guī)范形式線性規(guī)劃的對(duì)偶問題2約束方程不是“≤”的情況

3.1.4總結(jié)約束條件對(duì)變量，變量對(duì)約束條件；正常對(duì)正常，不正常對(duì)不正常；變量正常是非負(fù)，約束條件正?？茨繕?biāo)(max≤，min≥)。

例2.5求解下面線性規(guī)劃的對(duì)偶規(guī)劃LPDLP3.2對(duì)偶規(guī)劃的基本性質(zhì)3.2.1對(duì)稱性定理：線性規(guī)劃的對(duì)偶問題的對(duì)偶問題是原問題。證明：

對(duì)偶定義令w’=-w；約束方程左右同乘“-1”對(duì)偶定義令z=-z’；約束方程左右同乘“-1”3.2對(duì)偶規(guī)劃的基本性質(zhì)3.2.2弱對(duì)偶性定理：如果X、Y分別是原問題和對(duì)偶問題的一個(gè)可行解，則其對(duì)應(yīng)的原問題的目標(biāo)函數(shù)值不大于對(duì)偶問題的目標(biāo)函數(shù)值，也即證明：因?yàn)閄、Y分別是原問題（3.1）與對(duì)偶問題（3.2）的可行解，故：

所以推論一：原問題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問題目標(biāo)函數(shù)值的下界；反之對(duì)偶問題任一可行解的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值的上界。推論二：如果原問題存在無界解，則對(duì)偶問題一定無可行解；反之，如果對(duì)偶問題存在無界解，原問題也一定不存在可行解。3.2.3最優(yōu)性定理也就是說若原問題與對(duì)偶問題各存在一個(gè)可行解,且它們對(duì)應(yīng)的目標(biāo)函數(shù)值相等,則它們分別是原問題與對(duì)偶問題最優(yōu)解.如果原問題存在最優(yōu)解X*，則其對(duì)偶問題一定具有最優(yōu)解Y*，且初始單純形表的矩陣表示CBCN0CSxBxNxS0BNISbCBCN00最優(yōu)單純形表的矩陣表示CBCN0CBxBxNxSCBIB－1NB-1B-1b0CN-CBB－1N-CBB－1CBB－1b令則Y*>=0,且故Y*即為對(duì)偶問題的最優(yōu)解。又因?yàn)?.2.4強(qiáng)對(duì)偶性定理（對(duì)偶定理）B-1B-1B-1B-1在初始單純形表中單位矩陣經(jīng)過迭代后變?yōu)榛仃嘊的逆在初始單純形表給出的解中基變量Xs=b,而在迭代后的表給出的解中基變量

XB=B-1b系數(shù)矩陣的變化:[A,I]B-1[A,I]在初始單純形表中變量xj的系數(shù)為Pj經(jīng)過迭代后變?yōu)镻j′,并且Pj′=B-1Pj若迭代后的單純形表為最終表則該表也同時(shí)給出對(duì)偶問題的最優(yōu)解

32000

CBXBx1x2x3x4x5b0x3

0015/2-3/23/23x1

1003/2-1/23/22x2010-211

000-1/2-1/213/2

32000

CBXBx1x2x3x4x5b0x3

1210050x4

2101040x5430019

320000例3.1的初始表與最終表B?B-1例3.1的原問題與對(duì)偶問題最終單純形表的比較

32000

CBXBx1x2x3x4x5b0x3

0015/2-3/23/23x1

1003/2-1/23/22x2010-211

000-1/2-1/213/2

54900

y1y2y3y4y5

4y2-5/210-3