物流運(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,迪頓通過(guò)引入經(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）開(kāi)始，共有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é)的由來(lái)與發(fā)展運(yùn)籌學(xué)的性質(zhì)與特點(diǎn)

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

籌

學(xué)

概

況名稱的由來(lái)

OperationResearch

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

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

引水入溝（運(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)配合問(wèn)題)。二戰(zhàn)中美，英，加拿大等國(guó)用于戰(zhàn)爭(zhēng)。1948年美國(guó)麻省理工學(xué)院率先開(kāi)設(shè)了運(yùn)籌學(xué)課程，運(yùn)籌學(xué)成為一門學(xué)科。戰(zhàn)后擴(kuò)展到工業(yè)政府等部門。自60年代以來(lái)，由于計(jì)算機(jī)的應(yīng)用運(yùn)籌學(xué)得到了迅速的發(fā)展并開(kāi)始普及。我國(guó)50年代中期由錢學(xué)森、許國(guó)志等學(xué)者引入我國(guó)，1958年建立了運(yùn)籌學(xué)研究室。1962年管梅谷提出“中國(guó)郵路問(wèn)題”。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é)解決問(wèn)題的基本保障。

運(yùn)籌學(xué)定義運(yùn)籌學(xué)是運(yùn)用科學(xué)的方法（如分析、試驗(yàn)、量化等）來(lái)決定如何最佳地運(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í)際問(wèn)題

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

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

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

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

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

--問(wèn)題的復(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èn)題網(wǎng)絡(luò)優(yōu)化排序問(wèn)題統(tǒng)籌圖隨機(jī)優(yōu)化對(duì)策論排隊(duì)論庫(kù)存論決策分析可靠性分析運(yùn)籌學(xué)的主要內(nèi)容

實(shí)際問(wèn)題舉例

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

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

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

囚B囚A

坦白

抵賴

坦白-8，-80，-10

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

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

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

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

實(shí)例問(wèn)題線性規(guī)劃模型建模分析線性規(guī)劃模型模型線性規(guī)劃模型運(yùn)籌學(xué)在管理中的應(yīng)用生產(chǎn)計(jì)劃：生產(chǎn)作業(yè)的計(jì)劃、日程表的編排、合理下料、配料問(wèn)題、物料管理等庫(kù)存管理：多種物資庫(kù)存量的管理，庫(kù)存方式、庫(kù)存量等運(yùn)輸問(wèn)題：確定最小成本的運(yùn)輸線路、物資的調(diào)撥、運(yùn)輸工具的調(diào)度以及建廠地址的選擇等人事管理：對(duì)人員的需求和使用的預(yù)測(cè)，確定人員編制、人員合理分配，建立人才評(píng)價(jià)體系等市場(chǎng)營(yíng)銷：廣告預(yù)算、媒介選擇、定價(jià)、產(chǎn)品開(kāi)發(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)、配送和人員分派等問(wèn)題；整數(shù)規(guī)劃可以求解完成工作所需的人數(shù)、機(jī)器設(shè)備臺(tái)數(shù)和廠、庫(kù)的選址等；動(dòng)態(tài)規(guī)劃可用來(lái)解決諸如最優(yōu)路徑、資源分配、生產(chǎn)調(diào)度、庫(kù)存控制、設(shè)備更新等問(wèn)題。存儲(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ì)論在物流過(guò)程中具有廣泛地應(yīng)用，例如機(jī)場(chǎng)跑道設(shè)計(jì)和機(jī)場(chǎng)設(shè)施數(shù)量問(wèn)題，如何才能既保證飛機(jī)起降的使用要求，又不浪費(fèi)機(jī)場(chǎng)資源；又如碼頭的泊位設(shè)計(jì)和裝卸設(shè)備的購(gòu)置問(wèn)題，如何達(dá)到既能滿足船舶到港的裝卸要求，而又不浪費(fèi)港口資源；再如倉(cāng)庫(kù)保管員的聘用數(shù)量問(wèn)題、物流機(jī)械維修人員的聘用數(shù)量問(wèn)題，如何達(dá)到既能保證倉(cāng)儲(chǔ)保管業(yè)務(wù)和物流機(jī)械的正常運(yùn)轉(zhuǎn)，又不造成人力浪費(fèi)，等等，這些問(wèn)題都可以運(yùn)用排隊(duì)論方法加以解決。運(yùn)籌學(xué)解決問(wèn)題的過(guò)程1）提出問(wèn)題：認(rèn)清問(wè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)估：考察問(wèn)題是否得到完滿解決1）2）3）：形成問(wèn)題；4）5）分析問(wèn)題：定性分析與定量分析。構(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í)際問(wèn)題的能力。教學(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ī)劃問(wèn)題求解的方法——單純形法之后，線性規(guī)劃的理論與應(yīng)用都得到了極大的發(fā)展。

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

資源的合理利用問(wèn)題問(wèn)：如何安排生產(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ī)劃問(wèn)題及其數(shù)學(xué)模型e.g.2

營(yíng)養(yǎng)問(wèn)題

假定在市場(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。見(jiàn)表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ī)劃問(wèn)題及其數(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ī)劃問(wèn)題的一般形式：§1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型線性規(guī)劃問(wèn)題的標(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ī)劃問(wèn)題及其數(shù)學(xué)模型

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

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

設(shè)xj

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

，則xj’≥0；

又若xj

為自由變量，即xj

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

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

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

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

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

都有cx*≥cx，則稱x*為L(zhǎng)P問(wèn)題的最優(yōu)解，相應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)值，記作z*=cx*。§2線性規(guī)劃問(wèn)題的圖解法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問(wèn)題圖解法的基本步驟：1、在平面上建立直角坐標(biāo)系；2、圖示約束條件，確定可行域和頂點(diǎn)坐標(biāo)；3、圖示目標(biāo)函數(shù)（等值線）和移動(dòng)方向；4、尋找最優(yōu)解?！?線性規(guī)劃問(wèn)題的圖解法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)解,即有無(wú)窮多最優(yōu)解。Zman=34.2第一章線性規(guī)劃及單純形法maxz=2x1+2x2s.t.2x1–x2≥2-x1+4x2≤4

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

指找不到一組變量能滿足線性規(guī)劃的所有約束條件的情況，也就是線性規(guī)劃問(wèn)題不存在可行解，或者說(shuō)可行域是空集。例如線性規(guī)劃問(wèn)題：§2線性規(guī)劃問(wèn)題的圖解法由以上兩例分析可得如下重要結(jié)論：1、LP問(wèn)題從解的角度可分為：⑴有可行解⑵無(wú)可行解有唯一最優(yōu)解b.有無(wú)窮多最優(yōu)解C.無(wú)最優(yōu)解2、LP問(wèn)題若有最優(yōu)解，必在可行域的某個(gè)頂點(diǎn)上取到；若有兩個(gè)頂點(diǎn)上同時(shí)取到，則這兩點(diǎn)的連線上任一點(diǎn)都是最優(yōu)解。§2線性規(guī)劃問(wèn)題的圖解法圖解法優(yōu)點(diǎn)：直觀、易掌握。有助于了解解的結(jié)構(gòu)。圖解法缺點(diǎn)：只能解決低維問(wèn)題，對(duì)高維無(wú)能為力。例某工廠經(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ī)劃問(wèn)題的一個(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ǔ)解，稱為基可行解。⊙與基可行解對(duì)應(yīng)的基，稱為可行基。為了理解基解.基可行解.最優(yōu)解的概念，用下列例子說(shuō)明：例：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可行域本問(wèn)題解的情況：基解：點(diǎn)（O，A，B，Q1，Q2，Q3，Q4）可行解：由點(diǎn)（O，Q1，Q2，Q3，Q4）圍成的區(qū)域?；尚薪猓狐c(diǎn)（O，Q1，Q2，Q3，Q4）最優(yōu)解：

Q3解的集合：非可行解可行解解的集合：基解解的集合：可行解基解基可行解解的集合：可行解基解基最優(yōu)解基可行解線性規(guī)劃（2）-單純形方法單純形方法基本思路：從可行域中某個(gè)基可行解（一個(gè)頂點(diǎn)）開(kāi)始（稱為初始基可行解）。如可能，從可行域中求出具有更優(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é)顧問(wèn)旦茨基博士，根據(jù)在第二次世界大戰(zhàn)中實(shí)際規(guī)劃的經(jīng)歷，從1946年起就開(kāi)始尋找一種方法，想用它較快地計(jì)算出包括進(jìn)度、訓(xùn)練及后勤供應(yīng)在內(nèi)的規(guī)劃問(wèn)題。研究先從建立數(shù)學(xué)模型著手。在研究中，得到了投入—產(chǎn)出模型的啟發(fā)，并在其他數(shù)學(xué)家的支持下，提出了解決線性規(guī)劃問(wèn)題極其有效的單純形方法。單純形法的由來(lái)

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

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

線性規(guī)劃問(wèn)題的可行解有無(wú)窮多個(gè)，與某一凸集上的無(wú)窮多個(gè)點(diǎn)一一對(duì)應(yīng)。要從無(wú)窮多個(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為凸集。凸集（非凸集）

開(kāi)始，用單純形表進(jìn)行換基迭代。后來(lái)的改進(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è)方程的問(wèn)題?，F(xiàn)在，能解上萬(wàn)個(gè)方程的問(wèn)題。且解題速度大大加快。專家們已經(jīng)用單純形解法開(kāi)發(fā)出了計(jì)算效率極高應(yīng)用軟件。運(yùn)用這個(gè)軟件，輸入數(shù)據(jù)，立即就可以打印出結(jié)果。

單純形解法應(yīng)用的發(fā)展過(guò)程例：一個(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線性無(wú)關(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ù)無(wú)正數(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ī)劃問(wèn)題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è)換出來(lái)成為非基變量。下面來(lái)確定換出變量：當(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è)原來(lái)的基變量x5取值為0，從而可以換出來(lái)成為非基變量。其中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)用單純形表求解問(wèn)題例、用單純形表求解LP問(wèn)題解：化標(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)解與無(wú)窮多個(gè)最優(yōu)解若最終單純形表的非基變量的檢驗(yàn)數(shù)都小于零,則線性規(guī)劃問(wèn)題有唯一的最優(yōu)解若最終單純形表中存在某個(gè)非基變量,其檢驗(yàn)數(shù)等于零,則該線性規(guī)劃問(wèn)題有無(wú)窮多個(gè)最優(yōu)解.例3、用單純形方法求解線性規(guī)劃問(wèn)題解：本題的目標(biāo)函數(shù)是求極小化的線性函數(shù)，可以令則這兩個(gè)線性規(guī)劃問(wèn)題具有相同的可行域和最優(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ī)劃問(wèn)題首先將線性規(guī)劃標(biāo)準(zhǔn)化很明顯可以以x4、x5作為初始基變量，得到初始單純形如下：-22100CBXBx1x2x3x4x5b00x4x532-2-1-21100114-22100此時(shí)，x2的檢驗(yàn)數(shù)大于0，還沒(méi)有得到最優(yōu)解。但是我們以x2作為換入變量，但是x2所在列所有系數(shù)都小于0，此時(shí)該線性規(guī)劃存在無(wú)界解。單純形法計(jì)算過(guò)程構(gòu)造初始單純形表對(duì)標(biāo)準(zhǔn)化后的線性規(guī)劃問(wèn)題，首先找出初始基變量，構(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ī)劃問(wèn)題為無(wú)界解，終止計(jì)算。否則用換入變量所作列的系數(shù)去除b列的對(duì)應(yīng)數(shù)，在除得的商中選擇最小者對(duì)應(yīng)的基變量為換出變量。旋轉(zhuǎn)運(yùn)算確定換入和換出變量后得到新的基變量，然后以換入變量所在列、換出變量所在行交叉處的元素為主元，通過(guò)矩陣的初等行變換（一般不使用交換兩行的運(yùn)算）將約束方程組增廣矩陣中主元變換為1，主元列的其它元素變換為零。從而得到一個(gè)新的單純形表。然后回到第2步。第3章線性規(guī)劃對(duì)偶理論及其應(yīng)用例1

穗羊公司的例子3.1線性規(guī)劃的對(duì)偶問(wèn)題生產(chǎn)計(jì)劃問(wèn)題（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à)問(wèn)題（LP2）比較原問(wèn)題（生產(chǎn)計(jì)劃）對(duì)偶問(wèn)題（資源定價(jià)）3.1.2規(guī)范形式的線性規(guī)劃問(wèn)題原問(wèn)題（LP）對(duì)偶問(wèn)題（DLP）

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

0,則其對(duì)偶的約束條件為型的;若其某個(gè)約束條件是型,則其對(duì)應(yīng)的對(duì)偶變量是非正的.3.1.3非規(guī)范形式線性規(guī)劃的對(duì)偶問(wèn)題1變量取值范圍不符合非負(fù)要求的情況3.1.3非規(guī)范形式線性規(guī)劃的對(duì)偶問(wèn)題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ì)偶問(wèn)題的對(duì)偶問(wèn)題是原問(wèn)題。證明：

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

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

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

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