物流運籌學 課件 劉蓉 第1-11章 物流與運籌學-物流對策論

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

運籌學的由來與發(fā)展運籌學的性質(zhì)與特點

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

籌

學

概

況名稱的由來

OperationResearch

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

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

引水入溝（運輸）－

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

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

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

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

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

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

--從全局考察問題應用性

--源于實踐、為了實踐、服務于實踐交叉學科

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

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

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

實際問題舉例

對策問題（囚徒困境）

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

Supplychainnetworkdesign供應鏈網(wǎng)絡設(shè)計實際問題對策問題：囚徒困境

囚B囚A

坦白

抵賴

坦白-8，-80，-10

抵賴-10，0-1，-1實際問題資源分配實際問題

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

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

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

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

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

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

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

理論方法—筆試70%

應用能力—實驗10%學習態(tài)度--平時20%考試與要求韓伯棠，管理運籌學，

高等教育出版社，北京，2000年徐光輝等，運籌學手冊，

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

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

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

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

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

表1

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

A 1 3 60 B 1 1 40

單件利潤

15 25

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

x1

+x2≤40x1，x2≥0

解：

設(shè)x1，x2

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

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

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

表1

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

A 1 3 60 B 1 1 40

單件利潤

15 25

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

營養(yǎng)問題

假定在市場上可買到B1,B2,…Bnn

種食品，第

i

種食品的單價是ci,另外有m

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

Bj內(nèi)含有

Ai

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

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

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

表2

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

需要量

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

bm

單價

c1c2…cn

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

表2

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

需要量

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

bm

單價

c1c2…cn

解：

設(shè)xj

為購買食品

Bj

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

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

2、約束條件——一組決策變量的線性等式或不等式3、目標函數(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ù)學模型線性規(guī)劃問題的標準形式：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） 特點：1、目標函數(shù)為極大化；2、除決策變量的非負約束外，所有的約束條件都是等式，且右端常數(shù)均為非負；3、所有決策變量均非負。第一章線性規(guī)劃及單純形法如何轉(zhuǎn)化為標準形式？1、目標函數(shù)為求極小值，即為：。

因為求minz等價于求max(-z)，令z’=-z，即化為：

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

３、右端項bi<0時，只需將等式兩端同乘（-1）則右端項必大于零

4、決策變量無非負約束

設(shè)xj

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

，則xj’≥0；

又若xj

為自由變量，即xj

可為任意實數(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

化為標準形式。解：令x3=x4-x5

其中x4、x5

≥0；對第一個約束條件加上松弛變量x6

；對第二個約束條件減去松弛變量x7

；對第三個約束條件兩邊乘以“-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ù)學模型LP的幾種表示形式：§2線性規(guī)劃問題的圖解法定義1在LP問題中，凡滿足約束條件(2)、(3)的解x=(x1,x2,…,xn)T

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

設(shè)LP問題的可行域為D，若存在x*∈D，使得對任意的x∈D

都有cx*≥cx，則稱x*為LP問題的最優(yōu)解，相應的目標函數(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目標函數(shù)變形：x2=-3/5

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

x1=30x2=10最優(yōu)值：zmax=700B點是使z達到最大的唯一可行點第一章線性規(guī)劃及單純形法LP問題圖解法的基本步驟：1、在平面上建立直角坐標系；2、圖示約束條件，確定可行域和頂點坐標；3、圖示目標函數(shù)（等值線）和移動方向；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)

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

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

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

相對應的變量xj就稱為基變量，其余的就稱為非基變量。MaxS=CX（3-6）

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

X

0（3-8）基解.基可行解.可行基⊙對于某一特定的基B，非基變量取0值的解，稱為基解?！褲M足非負約束條件的基礎(chǔ)解，稱為基可行解?！雅c基可行解對應的基，稱為可行基。為了理解基解.基可行解.最優(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

與坐標系

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

-2x1+3x2

63x1-2

x2

6x1+x2

4

且滿足

x1,x2

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

0點（O，Q1，Q2，Q3，Q4）剛好是可行域的頂點。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可行域本問題解的情況：基解：點（O，A，B，Q1，Q2，Q3，Q4）可行解：由點（O，Q1，Q2，Q3，Q4）圍成的區(qū)域?；尚薪猓狐c（O，Q1，Q2，Q3，Q4）最優(yōu)解：

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

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

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

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

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

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

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

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

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

1004x1+2x2

120x1,x2

0引進松弛變量x3,x4

0數(shù)學模型標準形式：

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)濟含義：不生產(chǎn)產(chǎn)品甲乙，利潤為零。分析：S=

6x1+

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

增加單位產(chǎn)品對目標函數(shù)的貢獻，這就是檢驗數(shù)的概念。

增加單位產(chǎn)品甲（x1）比乙對目標函數(shù)的貢獻大（檢驗數(shù)最大），把非基變量x1換成基變量，稱x1為進基變量，而把基變量x4換成非基變量，稱x4為出基變量。確定了進基變量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)濟含義：生產(chǎn)甲產(chǎn)品30個，獲得利潤18000元。

這個方案比前方案，但是否是最優(yōu)？分析：S=180+x2-（3/2）x4非基變量x2系數(shù)仍為正數(shù)，確定x2為進基變量。在保證常數(shù)項非負的情況下，確定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)濟含義：分別生產(chǎn)甲乙產(chǎn)品20個，可獲得利潤20000元。分析：S=200-（1/2）x3-（5/4）x4目標函數(shù)中的非基變量的系數(shù)無正數(shù)，S3=200是最優(yōu)值，x(3)=(20,20,0,0)t是最優(yōu)解。該企業(yè)分別生產(chǎn)甲乙產(chǎn)品20個，可獲得最大利潤20000元。X(3)=(20,20,0,0)t相當于Q2(20,20)X(1)=(0,0,100,120)t相當于O(0,0)X(1)=(0,0,100,120)t相當于O(0,0)X(2)=(30,0,40,0)t相當于Q1(30,0)X(2)=(30,0,40,0)t相當于Q1(30,0)X(3)=(20,20,0,0)t相當于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用非基變量表達基變量：

x3=100

－x1－1x2

x4=190

－3x1－2x2

x5=240

－2x1－3x2

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

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

－1x2≥0x4=190

－2x2≥0x5=240

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

>0，

x4=30

>0，

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

95x2≤80x2≤80用非基變量表達基變量：

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

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

X*=x（1）＝（0,80,20,30,0),目標函數(shù)值z*=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檢驗數(shù)

0

00-z(0)用單純形表求解問題例、用單純形表求解LP問題解：化標準型表1：列初始單純形表（單位矩陣對應的變量為基變量）

21000

01505100

0

24620100511001

21000

—24/65/1正檢驗數(shù)中最大者對應的列為主列主元化為1主列單位向量換出換入最小的值對應的行為主行表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=主元檢驗數(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)目標函數(shù)值Z=8.5

2*7/21*3/2+0*15/28.5檢驗數(shù)<=0例2、試利用單純形表求例1中的最優(yōu)解解：

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

換入變量，換出變量，２為主元進行旋轉(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)值

換入變量，換出變量，５/２為主元進行旋轉(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檢驗數(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檢驗數(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)解與無窮多個最優(yōu)解若最終單純形表的非基變量的檢驗數(shù)都小于零,則線性規(guī)劃問題有唯一的最優(yōu)解若最終單純形表中存在某個非基變量,其檢驗數(shù)等于零,則該線性規(guī)劃問題有無窮多個最優(yōu)解.例3、用單純形方法求解線性規(guī)劃問題解：本題的目標函數(shù)是求極小化的線性函數(shù)，可以令則這兩個線性規(guī)劃問題具有相同的可行域和最優(yōu)解，只是目標函數(shù)相差一個符號而已。

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

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

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

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

3.1.4總結(jié)約束條件對變量，變量對約束條件；正常對正常，不正常對不正常；變量正常是非負，約束條件正常看目標(max≤，min≥)。

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

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

所以推論一：原問題任一可行解的目標函數(shù)值是其對偶問題目標函數(shù)值的下界；反之對偶問題任一可行解的目標函數(shù)值是其原問題目標函數(shù)值的上界。推論二：如果原問題存在無界解，則對偶問題一定無可行解；反之，如果對偶問題存在無界解，原問題也一定不存在可行解。3.2.3最優(yōu)性定理也就是說若原問題與對偶問題各存在一個可行解,且它們對應的目標函數(shù)值相等,則它們分別是原問題與對偶問題最優(yōu)解.如果原問題存在最優(yōu)解X*，則其對偶問題一定具有最優(yōu)解Y*，且初始單純形表的矩陣表示CBCN0CSxBxNxS0BNISbCBCN00最優(yōu)單純形表的矩陣表示CBCN0CBxBxNxSCBIB－1NB-1B-1b0CN-CBB－1N-CBB－1CBB－1b令則Y*>=0,且故Y*即為對偶問題的最優(yōu)解。又因為3.2.4強對偶性定理（對偶定理）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若迭代后的單純形表為最終表則該表也同時給出對偶問題的最優(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的原問題與對偶問題最終單純形表的比較

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