管理運(yùn)籌學(xué)課件

運(yùn)籌學(xué)的產(chǎn)生與發(fā)展

運(yùn)籌學(xué)的基本內(nèi)涵

運(yùn)籌學(xué)模型

運(yùn)籌學(xué)的工作步驟

運(yùn)籌學(xué)的基本內(nèi)容第一章緒論**

運(yùn)籌學(xué)的產(chǎn)生1.時(shí)間：第二次世界大戰(zhàn)前後

2.地點(diǎn)：英國

3.主要事件

(1)1937年研究雷達(dá)運(yùn)作問題

(2)1938年整個(gè)防空作戰(zhàn)系統(tǒng)運(yùn)行的研究

(3)1939年成立軍事攻關(guān)小組，其主要研究內(nèi)容為：

雷達(dá)佈置與運(yùn)作問題

反空襲系統(tǒng)的運(yùn)行與控制

海軍艦隊(duì)的編制問題

潛艇問題

**

運(yùn)籌學(xué)的發(fā)展1.1941年英國皇家陸、海、空三軍均成立了O.R.小組

2.後來美國、前蘇聯(lián)等盟軍也相繼成立了O.R.小組

3.戰(zhàn)後O.R.走向社會(huì)經(jīng)濟(jì)領(lǐng)域

4.50年代O.R.成為一門獨(dú)立的學(xué)科

5.60年代O.R.迅速普及和發(fā)展

6.O.R.在中國的發(fā)展

**50年代O.R.成為一門獨(dú)立的學(xué)科主要標(biāo)誌：大量O.R.學(xué)會(huì)的成立和相應(yīng)期刊的問世

1.英國1948年創(chuàng)立O.R.學(xué)會(huì)

2.美國1952年成立O.R.學(xué)會(huì)

1953年成立管理科學(xué)研究所刊物分別為“運(yùn)籌學(xué)”和“管理科學(xué)”

3.1956~1959有10個(gè)國家成立O.R.學(xué)會(huì)，並有6種期刊問世

4.1959年國際O.R.學(xué)會(huì)成立

5.1986年已有38個(gè)國家有O.R.學(xué)會(huì)

**60年代O.R.迅速普及和發(fā)展

主要標(biāo)誌:

電腦的普及與發(fā)展方法理論成熟使O.R.成本降低高校普遍開設(shè)的重要課程

**O.R.在中國的發(fā)展1.50年代中期錢學(xué)森、華羅庚、許國志等著名學(xué)者將O.R.從西方引入我國2.1956年將O.R.直譯為“運(yùn)用學(xué)”3.1957年將O.R.意譯為“運(yùn)籌學(xué)”4.1956年成立O.R.小組5.1958年成立O.R.研究室6.1960年召開全國O.R.會(huì)議7.1980年成立O.R.學(xué)會(huì)

**

運(yùn)籌學(xué)的基本內(nèi)涵1.英國O.R.學(xué)會(huì)的定義

2.美國O.R.學(xué)會(huì)的定義

3.我國辭海的釋義

4.中國企業(yè)管理百科全書的釋義

5.概括性定義

**英國O.R.學(xué)會(huì)的定義

OperationalResearchistheapplicationofthemethodsofsciencetocomplexproblemsarisinginthedirectionandmanagementoflargesystemsofmen,machines,materials,andmoneyinindustry,business,government,anddefense.Thedistinctiveapproachistodevelopascientificmodelofthesystem,incorporatingmeasurementsoffactorssuchaschanceandrisk,withwhichtopredictandcomparetheoutcomesofalternativedecisions,strategiesorcontrols.Thepurposeistohelpmanagementdetermineitspolicyandactionsscientifically.**美國O.R.學(xué)會(huì)的定義

OperationalResearchisconcernedwithscientificallydecidinghowtobestdesignandoperateman-machinesystems,usuallyunderconditionsrequiringtheallocationofscarceresources.

**我國辭海的釋義

運(yùn)籌學(xué)：主要研究經(jīng)濟(jì)活動(dòng)與軍事活動(dòng)中能用數(shù)量表達(dá)的有關(guān)運(yùn)用、籌畫與管理方面的問題，它根據(jù)問題的要求，通過數(shù)學(xué)的分析與運(yùn)算，作出綜合性的合理安排，以達(dá)到較經(jīng)濟(jì)較有效地使用人力物力。

**中國企業(yè)管理百科全書的釋義

運(yùn)籌學(xué)：應(yīng)用分析、試驗(yàn)、和量化的方法，對(duì)經(jīng)濟(jì)管理系統(tǒng)中人、財(cái)、物等有限資源統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理。

**

概括性定義

運(yùn)籌學(xué)：通過建立、求解數(shù)學(xué)模型，規(guī)劃、優(yōu)化有限資源的利用方案，為決策者提供科學(xué)決策依據(jù)，以實(shí)現(xiàn)有限資源的合理利用的系統(tǒng)知識(shí)體系。**

運(yùn)籌學(xué)模型1.模型的定義：模型是客觀事物的簡化和抽象，是研究者經(jīng)過思維抽象後用文字、圖表、符號(hào)、關(guān)係式及實(shí)物對(duì)客觀事物的描述

2.模型的種類：形象模型、模擬模型和數(shù)學(xué)模型

3.數(shù)學(xué)模型：用字母、數(shù)字和運(yùn)算符來精確地反映變數(shù)之間相互關(guān)係的式子或式子組。

4.數(shù)學(xué)模型三要素：決策變數(shù)、目標(biāo)函數(shù)和約束條件。

5.建立數(shù)學(xué)模型常用的假設(shè)**建立數(shù)學(xué)模型常用的假設(shè)(1)離散變數(shù)的連續(xù)性假設(shè)；

(2)非線性函數(shù)的線性假設(shè)；

(3)非主要因素的不相關(guān)假設(shè)；

(4)隨機(jī)變數(shù)的確定性假設(shè)；

(5)灰數(shù)的白化假設(shè)。**運(yùn)籌學(xué)的工作步驟提出和形成問題；建立模型；求解模型；解的檢驗(yàn)與轉(zhuǎn)譯；解的實(shí)施。**

運(yùn)籌學(xué)的基本內(nèi)容

線性規(guī)劃及其擴(kuò)展非線性規(guī)劃

動(dòng)態(tài)規(guī)劃存貯論

圖論排隊(duì)論

對(duì)策論

決策論

**2024-1-2171.線性規(guī)劃問題及其數(shù)學(xué)模型2.線性規(guī)劃的圖解法3.線性規(guī)劃問題的標(biāo)準(zhǔn)形式4.線性規(guī)劃的解集特徵5.線性規(guī)劃的單純形法6.單純形法的進(jìn)一步討論第二章線性規(guī)劃2024-1-218線性規(guī)劃問題及其數(shù)學(xué)模型

資源合理利用問題：第5頁例2-1品質(zhì)檢驗(yàn)問題：第6頁例2-2線性規(guī)劃數(shù)學(xué)模型的一般形式2024-1-219資源合理利用問題：第5頁例2-1

1.決策變數(shù)：x1和x22.目標(biāo)函數(shù)：max(2x1+3x2)3.約束條件：10

x1+20x2804x1

166x218

x1，x202024-1-220

品質(zhì)檢驗(yàn)問題：第6頁例2-21.決策變數(shù)：x1和x22.目標(biāo)函數(shù)：min(40

x1+36x2)

3.約束條件：5

x1+3x2

45

x1

8x2

10

x1，x202024-1-221線性規(guī)劃數(shù)學(xué)模型的一般形式1.決策變數(shù)是非負(fù)變數(shù)；

2.目標(biāo)函數(shù)是線性函數(shù)；

3.約束條件是線性等式或不等式組。一般形式為：

max(min)(c1

x1+c2

x2+…+

cnxn

)

a11

x1+a12

x2+…+a1nxn

(=,)b1

a21

x1+a22

x2+…+a2n

xn

(=,)b2

……

am1

x1+am2

x2+…+amnxn

(=,)bm

x1，

x2，

…，xn

0

2024-1-222

線性規(guī)劃的圖解法1.局限性：只能求解具有兩個(gè)變數(shù)的線性規(guī)劃問題。2.學(xué)習(xí)目的：圖解法只能求解具有兩個(gè)決策變數(shù)的線性規(guī)劃問題，其應(yīng)用具有很大的局限性，因此學(xué)習(xí)圖解法的目的並非是要掌握一種線性規(guī)劃問題的求解方法，而是要通過圖解法揭示線性規(guī)劃問題的內(nèi)在規(guī)律，為學(xué)習(xí)線性規(guī)劃問題的一般演算法（單純形法）奠定基礎(chǔ)。3.線性規(guī)劃有關(guān)解的幾個(gè)概念4.圖解法的基本步驟5.圖解法所反映出的一般結(jié)論2024-1-223線性規(guī)劃有關(guān)解的幾個(gè)概念1.可行解：滿足約束條件的一組決策變數(shù)的取值；

2.可行域：可行解所構(gòu)成的集合；

3.最優(yōu)解：使目標(biāo)函數(shù)達(dá)到極值的可行解；

4.最優(yōu)值：與最優(yōu)解相對(duì)應(yīng)的目標(biāo)函數(shù)的取值。2024-1-224圖解法的基本步驟1.畫出平面直角坐標(biāo)系；

2.將約束條件逐一反映進(jìn)平面直角坐標(biāo)系，用標(biāo)號(hào)和箭線表明約束條件的順序和不等號(hào)的方向；

3.找出可行域並反映出目標(biāo)函數(shù)直線的斜率；

4.平移目標(biāo)函數(shù)直線找出最優(yōu)解。

5.例題：第7頁例2-3：用圖解法求解例2-16.習(xí)題：第8頁例2-4：用圖解法求解例2-2

2024-1-225用圖解法求解例2-1x1x2

4

3

2

1

0123456782024-1-226用圖解法求解例2-1x1x2

4

3

2

1

0123456782024-1-227用圖解法求解例2-1x1x2

4

3

2

1

0123456782024-1-228用圖解法求解例2-1x1x2

4

3

2

1

0123456782024-1-229用圖解法求解例2-1x1x2

4

3

2

1

0123456782024-1-230用圖解法求解例2-1x1x2

4

3

2

1

0123456782024-1-231用圖解法求解例2-1x1x2

4

3

2

1

0123456782024-1-232用圖解法求解例2-2x1x251015

15

10

5

02024-1-233圖解法所反應(yīng)出的一般結(jié)論1.線性規(guī)劃問題的可行域是凸多邊形；2.如果線性規(guī)劃問題有最優(yōu)解，其最優(yōu)解一定可以在其可行域的頂點(diǎn)上得到，而不會(huì)在可行域的內(nèi)部；3.如果線性規(guī)劃問題在其可行域的兩個(gè)頂點(diǎn)上得到最優(yōu)解，那麼兩頂點(diǎn)連線上的所有點(diǎn)均為最優(yōu)解點(diǎn)；4.線性規(guī)劃問題的解可能有四種情況：唯一最優(yōu)解；無窮多最優(yōu)解；無界解和無可行解。2024-1-234線形規(guī)劃問題的標(biāo)準(zhǔn)形式1.標(biāo)準(zhǔn)形式的基本條件：（1）決策變數(shù)非負(fù)；（2）目標(biāo)函數(shù)極大化（或極小化）；（3）約束條件為嚴(yán)格等式，且右端項(xiàng)非負(fù)。2.標(biāo)準(zhǔn)形式的表示：

代數(shù)式；和式；向量式；矩陣式

3.

標(biāo)準(zhǔn)形式的轉(zhuǎn)化2024-1-235線性規(guī)劃的標(biāo)準(zhǔn)型：代數(shù)式minz=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn=b1

a21x1+a22x2+…+a2nxn=b2………

am1x1+am2x2+…+amnxn=bm

xj

≥0j=1,2,…,n2024-1-236線性規(guī)劃的標(biāo)準(zhǔn)型：和式minz=∑cjxj

∑aijxj=bi

i=1,2,…,m

xj

≥0

j=1,2,…,nj=1nnj=12024-1-237線性規(guī)劃的標(biāo)準(zhǔn)型：向量式minz=CX

∑pjxj=bi

i=1,2,…,m

xj≥0j=1,2,…,n

C=(c1,c2,c3,…,cn)

X=(X1,X2,X3,…,Xn)Tnj=12024-1-238線性規(guī)劃的標(biāo)準(zhǔn)型：矩陣式minz=CX

AX=b，X

≥0，

b≥0

其中：

b=(b1,b2,…,bm)T

a11

a12….a1n

A=a21

a22…a2n………

am1

am2…amn2024-1-239標(biāo)準(zhǔn)形式的轉(zhuǎn)化1.無約束變數(shù)x的處理：

x=y-z,其中y,z02.負(fù)數(shù)變數(shù)x的處理：

x=-y,其中y03.目標(biāo)函數(shù)極小化的處理：

MinCX=-Max(-CX)4.非等式約束條件的處理：加鬆弛變數(shù)或減剩餘變數(shù)5.右端項(xiàng)為負(fù)：兩端同乘“-1”2024-1-240線形規(guī)劃的解集特徵1.線性規(guī)劃基與解的概念

(1)基、基列、基變數(shù)和非基變數(shù)

(2)基解、基可行解和可行基2.凸集的概念與解集的基本定理

(1)凸集的概念

(2)解集的基本定理2024-1-241線性規(guī)劃基與解的概念1.基、基列、基變數(shù)和非基變數(shù)

(1)基：MaxCX,AX=b,X0,b0Amn其秩為m，B是Amn中的一個(gè)mm階滿秩矩陣，則稱B是線性規(guī)劃問題的一個(gè)基

(2)基列：基B中所包含的m個(gè)列向量

(3)基變數(shù)：基列所對(duì)應(yīng)的決策變數(shù)

(4)非基變數(shù)：基變數(shù)以外的決策變數(shù)2.基解、基可行解、可行基

(1)基解：令所有的非基變數(shù)為零，所求得的一組解

(2)基可行解：所有分量均為非負(fù)的基解

(3)可行基：與基可行解所對(duì)應(yīng)的基2024-1-242凸集的概念與解集的基本定理1.凸集的概念：設(shè)K是n維歐氏空間的一點(diǎn)集，若任意兩點(diǎn)X(1)

k，X(2)

k的連線上的一切點(diǎn)

X(1)+(1-)X(2)

k，(0<<1)

則稱k為凸集。2.解集的基本定理：

(1)若線性規(guī)劃問題存在可行域，則其可行域是凸集；

(2)線性規(guī)劃問題的基可行解對(duì)應(yīng)其可行域的頂點(diǎn)；

(3)若線性規(guī)劃問題存在最優(yōu)解，則其最優(yōu)解一定能在基可行解中找到。2024-1-243線性規(guī)劃的單純形法1.單純形法的基本原理

(1)單純形法的基本思路

(2)第12頁例2-62.最優(yōu)性檢驗(yàn)與解的判別3.單純形表4.單純形法的基本步驟5.用單純形法求解例2-66.課上習(xí)題2024-1-244單純形法的基本思路1.找出一個(gè)初始的基可行解；2.判斷其最優(yōu)性；3.轉(zhuǎn)移至另一個(gè)較優(yōu)的基可行解；4.重複2、3兩步直至最優(yōu)。2024-1-245第12頁例2-6Maxz=2x1+3x210x1+20x2+x3=804x1+x4=16

6x2+x5=18x1，

x2，

x3，

x4，

x50B=(p3，p4，p5)X(0)=(0，0，80，16，18)TZ(0)=0，z=2x1+3x2尋找相鄰的基可行解2024-1-246例2-6Max(2，3)=3

x2入基Min(80/20，18/6)=3

x5出基B=(p3，p4，p2)10x1+x3-10/3x5=204x1+x4=16x2+1/6x5=3X(1)=(0，3，20，16，0)TZ(1)=9，z=9+2x1-1/2x52024-1-247例2-6Max(2)=2

x1入基Min(20/10，16/4)=2

x3出基B=(p1，p4，p2)x1+1/10x3-1/3x5=2-2/5x3+x4+4/3x5=8x2+1/6x5=3X(2)=(2，3，0，8，0)TZ(2)=13，z=13-1/5x3+1/6x52024-1-248例2-6Max(1/6)=1/6

x5入基Min(8/(4/3)，3/(1/6))=6

x4出基B=(p1，p5，p2)x1+1/4x4=4-3/10x3+3/4x4+x5=6x2+1/20x3-1/8x4=2X(3)=(4，2，0，0，6)TZ(3)=14，z=14-9/10

x3

-1/8x42024-1-249最優(yōu)性檢驗(yàn)與解的判別2024-1-250單純形表2024-1-251單純形法的基本步驟1.數(shù)學(xué)模型標(biāo)準(zhǔn)化、正規(guī)化；2.建立初始單純形表；3.計(jì)算檢驗(yàn)數(shù)並判斷最優(yōu)性，結(jié)束或繼續(xù)；4.確定入基變數(shù)和出基變數(shù)，5.迭代運(yùn)算；6.重複3、4、5步，直至結(jié)束。2024-1-252用單純形法求解例2-62024-1-253用單純形法求解例2-62024-1-254用單純形法求解例2-62024-1-255用單純形法求解例2-62024-1-256課上習(xí)題1.Maxz=2x1+4x2+x3+x4x1+3x2

+x48

2x1+x2

6x2

+x3

+x4

6x1

+x2

+x3

9x1~4

02.第17頁例2-103.第19頁例2-112024-1-257單純形法的進(jìn)一步討論1.計(jì)算問題

(1)入基變數(shù)的選擇

(2)解的退化2.人工變數(shù)與初始正規(guī)基

(1)大M法

(2)兩階段法2024-1-258入基變數(shù)的選擇

入基變數(shù)是根據(jù)最大正檢驗(yàn)數(shù)來選擇的，這樣做的目的是為了使目標(biāo)函數(shù)得到最大的增量，因此當(dāng)最大正檢驗(yàn)數(shù)有多個(gè)時(shí)，可主觀地選擇它們中的任意一個(gè)作為入基變數(shù)。其實(shí)具有正檢驗(yàn)數(shù)的所有非基變數(shù)都可作為入基變數(shù)。2024-1-259出基變數(shù)的選擇與解的退化1.退化解：部分基變數(shù)的值為零的基可行解稱為退化解。2.在選擇出基變數(shù)時(shí)，如果最小比值不唯一，可主觀確定出基變數(shù)，此時(shí)產(chǎn)生退化解。3.例2024-1-260例Maxz=2x4+(3/2)x6

x1+x4-x5=8

x2+2x4+x6=4

x3+x4+x5+x6=3

x1~602024-1-261例2024-1-262例2024-1-263例2024-1-264例2024-1-265例2024-1-266人工變數(shù)與初始正規(guī)基第21頁例2-13:

Minz=-3x1+x2+x3x1-2x2+x311-4x1+x2+2x332x1-x3=-1x1，

x2，x30(1)標(biāo)準(zhǔn)化2024-1-267例2-13的標(biāo)準(zhǔn)化

Minz=-3x1+x2+x3x1-2x2+x3+x4=11-4x1+x2+2x3-x5=3-2x1+x3=1x1~50(2)正規(guī)化2024-1-268例2-13的正規(guī)化人工變數(shù)：為構(gòu)造基變數(shù)（正規(guī)基）人為加入的變數(shù)

x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6

=3-2x1+x3+x7

=1x1~70初始正規(guī)基B=(p4,p6,p7)=E2024-1-269大M法1.大M法：令人工變數(shù)的價(jià)值係數(shù)為“-M”(極大值)或“M”(極小值)的單純形法即稱為大M法；例如：

Minz=-3x1+x2+x3+Mx人1+Mx人2

Maxz=2x1+x2+4x3-Mx人1+Mx人22.例2-13的大M法3.習(xí)題（大M法）2024-1-270用大M法求解例2-13

Minz=-3x1+x2+x3x1-2x2+x311-4x1+x2+2x332x1-x3=-1x1，

x2，x302024-1-271用大M法求解例1.13

Minz=-3x1+x2+x3+Mx6+Mx7x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6

=3-2x1+x3+x7

=1x1~702024-1-272用大M法求解例1.132024-1-273用大M法求解例1.132024-1-274用大M法求解例1.132024-1-275用大M法求解例1.132024-1-276習(xí)題（用大M法求解）

Maxz=2x1+4x2+x3x1+x2+x36x1+x2-2x34x1-2x2+x38x1，

x2，x302024-1-277習(xí)題（用大M法求解）

Maxz=2x1+4x2+x3-Mx7x1+x2+x3+x4=6x1+x2-2x3+x5=4x1-2x2+x3-x6+x7

=8x1~702024-1-278習(xí)題（用大M法求解）2024-1-279習(xí)題（用大M法求解）2024-1-280習(xí)題（用大M法求解）2024-1-281兩階段法1.兩階段法：第一階段，在原約束條件下，求所有人工變數(shù)和的最小值；第一階段的目的是獲得問題的一個(gè)初始基可行解（人工變數(shù)和的最小值為零）或得出問題無可行解（人工變數(shù)和的最小值大於零）的結(jié)論；第二階段，去掉人工變數(shù)，在原目標(biāo)下從已得到的基可行解開始優(yōu)化。2.例2-13的兩階段法3.習(xí)題（兩階段法）2024-1-282用兩階段法求解例2-13

Minz=-3x1+x2+x3x1-2x2+x311-4x1+x2+2x332x1-x3=-1x1，

x2，x302024-1-283用兩階段法求解例2-13第一階段：

Minz=x6+x7x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6

=3-2x1+x3+x7

=1x1~702024-1-284用兩階段法求解例2-132024-1-285用兩階段法求解例2-132024-1-286用兩階段法求解例2-132024-1-287用兩階段法求解例2-132024-1-288用兩階段法求解例2-132024-1-289習(xí)題（用兩階段法求解）

Maxz=2x1+4x2+x3x1+x2+x36x1+x2-2x34x1-2x2+x38x1，

x2，x302024-1-290習(xí)題（用兩階段法求解）第一階段：Minz=x7x1+x2+x3+x4=6x1+x2-2x3+x5=4x1-2x2+x3-x6+x7

=8x1~702024-1-291習(xí)題（用兩階段法求解）2024-1-292習(xí)題（用兩階段法求解）2024-1-293習(xí)題（用兩階段法求解）2024-1-21.對(duì)偶問題的提出2.對(duì)偶關(guān)係3.對(duì)偶性質(zhì)4.對(duì)偶單純形法5.靈敏度分析第三章線性規(guī)劃的對(duì)偶理論2024-1-21.對(duì)偶問題的提出1.從數(shù)學(xué)角度提出對(duì)偶問題(1)正規(guī)化的線性規(guī)劃數(shù)學(xué)模型(2)檢驗(yàn)數(shù)與最優(yōu)條件(3)對(duì)偶模型2.從經(jīng)濟(jì)學(xué)角度提出對(duì)偶問題(1)例1(2)例1的數(shù)學(xué)模型(3)例1的對(duì)偶模型2024-1-2正規(guī)化的線性規(guī)劃數(shù)學(xué)模型Maxz=CXAX+EXs=bX,Xs

02024-1-2檢驗(yàn)數(shù)與最優(yōu)條件2024-1-2對(duì)偶模型2024-1-2例12024-1-2例1的數(shù)學(xué)模型Maxz=8x1+7x2x1+2x2

1004x1+3x2

2005x1+6x2

300x1，

x2

02024-1-2例1的對(duì)偶模型Minz=100x1+200x2+300x3x1+4x2+5x3

82x1+3x2+6x3

7x1，

x2

02024-1-22.對(duì)偶關(guān)係2024-1-23.對(duì)偶性質(zhì)1.對(duì)稱性:對(duì)偶問題的對(duì)偶是原問題；2.弱對(duì)偶性:CX

Yb,X和Y是可行解；3.無界性:原問題無界,對(duì)偶問題無可行解；4.最優(yōu)性:CX=Yb,X和Y是最優(yōu)解；5.對(duì)偶性:原問題與對(duì)偶問題同時(shí)具有最優(yōu)解且最優(yōu)值相等；6.互補(bǔ)鬆弛性；7.對(duì)應(yīng)性。2024-1-2互補(bǔ)鬆弛性對(duì)於線性規(guī)劃的最優(yōu)解，若某一約束條件的對(duì)偶變數(shù)值大於零，則該約束條件取嚴(yán)格等式；反之，若約束條件取嚴(yán)格不等式，則其對(duì)應(yīng)的對(duì)偶變數(shù)一定為零。2024-1-2對(duì)應(yīng)性1.原問題：Maxz=CXAX+EXs=b，X，Xs

0

2.對(duì)偶問題：Minz=YbYA-EYs=C，Y，Ys

0

3.對(duì)應(yīng)關(guān)係4.例2

2024-1-24.對(duì)偶單純形法1.對(duì)偶單純形法的內(nèi)涵2.對(duì)偶單純形法的優(yōu)點(diǎn)和應(yīng)用的前提條件3.對(duì)偶單純形法的計(jì)算步驟

4.例3（例3-5）2024-1-2對(duì)偶單純形法的內(nèi)涵對(duì)偶單純形法：在對(duì)偶可行基的基礎(chǔ)上進(jìn)行的單純形法即為對(duì)偶單純形法。單純形法是在原問題可行的基礎(chǔ)上，通過迭代使對(duì)偶問題達(dá)到可行，從而得到最優(yōu)解。根據(jù)對(duì)偶問題的對(duì)稱性，可這樣考慮，若原問題不可行而對(duì)偶問題可行，那麼在保持對(duì)偶問題可行的基礎(chǔ)上，逐步迭代使原問題達(dá)到可行，也可得到最優(yōu)解。2024-1-2對(duì)偶單純形法的優(yōu)點(diǎn)和

應(yīng)用的前提條件對(duì)偶單純形法的優(yōu)點(diǎn)是原問題的初始解不要求是可行解，可以從非可行解開始迭代，從而省去了引入人工變數(shù)的麻煩。當(dāng)然對(duì)偶單純形法的應(yīng)用也是有前提條件的，這一前提條件就是對(duì)偶問題的解是基可行解。2024-1-2對(duì)偶單純形法的計(jì)算步驟1.根據(jù)對(duì)偶基可行解列初始單純形表；2.最優(yōu)性檢驗(yàn)：若原問題也為基可行解，則已得到最優(yōu)解，過程結(jié)束；否則，進(jìn)入第3步。3.選擇出基變數(shù)：Min{bi|

bi0}4.選擇入基變數(shù)：Min{

j/aij

|

aij0}若所有的aij均大於零，則無可行解。5.迭代運(yùn)算，重複1~4步。2024-1-2例2Maxz=2x1+x23x1+4x2+x3=186x1+2x2+x4

=24

x1+x2+x5

=6

x1~4

0

Minw=18y1+24y2+6y33y1+6y2+y3-y4=24y1+2y2+y3-y5=1y1~5

0

2024-1-2例2的求解結(jié)果2024-1-2例3（第35頁例3-5）Minw=x1+4x2+3x4

x1+2x2-x3+x43-2x1-x2+4x3+x42

x1~40

轉(zhuǎn)換成標(biāo)準(zhǔn)形式：Minw=x1+4x2+3x4

x1+2x2-x3+x4-x5=3-2x1-x2+4x3+x4-x6=2

x1~60

2024-1-2例3的求解過程

2024-1-2例3的求解過程

2024-1-2例3的求解過程2024-1-25.線性規(guī)劃的靈敏度分析1.靈敏度分析的內(nèi)涵2.靈敏度分析的處理方法3.資源係數(shù)變化的靈敏度分析4.價(jià)值係數(shù)變化的靈敏度分析

5.技術(shù)係數(shù)變化的靈敏度分析6.增加新變數(shù)的靈敏度分析7.增加新約束的靈敏度分析2024-1-2靈敏度分析的內(nèi)涵靈敏度分析是對(duì)系統(tǒng)因環(huán)境變化顯示出來的敏感程度的分析。線上性規(guī)劃中討論靈敏度分析，目的是描述一種能確定模型結(jié)構(gòu)中元素變化對(duì)問題最優(yōu)解影響的分析方法。靈敏度分析主要回答兩方面問題：因素有一定量變化時(shí)，最優(yōu)解有什麼變化；因素在什麼範(fàn)圍內(nèi)變化時(shí)，最優(yōu)解保持不變。2024-1-2靈敏度分析的處理方法2024-1-2資源係數(shù)變化的靈敏度分析1.基本原理(B|E)

(E|B-1)A

B-1A，XB=B-1(b+b)

j保持不變，XB

非負(fù)最優(yōu)基不變。2.第37頁例3-6

Maxz=5x1+12x2+4x3+0x4-Mx5x1+2x2+x3+x4

=52x1-x2+3x3+x5=2

x1，x2，x3，x4

，x50

2024-1-2例3-6的求解

2024-1-2例3-6的求解

2024-1-2例3-6的求解

2024-1-2例3-6的求解2024-1-2價(jià)值係數(shù)變化的靈敏度分析1.原理：cj的變化只會(huì)影響

j2.第38頁例3-7

Maxz=2x1+3x2+x3x1+x2+x3+x4

=3x1+4x2+7x3+x5=9

x1，x2，x3，x4

，x50

2024-1-2第38頁例3-7的求解

2024-1-2第38頁例3-7的求解

2024-1-2第38頁例3-7的求解

2024-1-2第39頁例3-8的求解

2024-1-2第39頁例3-8的求解

2024-1-2第39頁例3-8的求解2024-1-2技術(shù)係數(shù)變化的靈敏度分析1.原理：同bi的變化，B-1pj

反映進(jìn)最終單純形表。2.Xj為非基變數(shù)3.Xj為基變數(shù)4.練習(xí)第41頁例3-115.練習(xí)第41頁例3-122024-1-2Xj為非基變數(shù)（例3-7）2024-1-2

Xj為基變數(shù)（例3-7）

2024-1-2

Xj為基變數(shù)（例3-7）2024-1-2第41頁例3-11

Maxz=5x1+12x2+4x3x1+2x2+x3+x4

=52x1-x2+3x3+x5=2

x1，x2，x3，x4

，x50

2024-1-2第41頁例3-11

2024-1-2第41頁例3-112024-1-2第41頁例3-12

Maxz=2x1+3x2+x3x1+x2+x3+x4

=3x1+4x2+7x3+x5=9

x1，x2，x3，x4

，x50

2024-1-2第41頁例3-12

2024-1-2第41頁例3-12

2024-1-2第41頁例3-122024-1-2增加新變數(shù)的靈敏度分析1.步驟：(1)求

新，如果

新0，最優(yōu)解不變；如果

新0，最優(yōu)解有變化。(2)B-1p新

反映進(jìn)最終單純形表，並用單純形法求解。2.例題：第42頁例3-132024-1-2第42頁例3-13

2024-1-2第42頁例3-132024-1-2增加新約束的靈敏度分析1.步驟：(1)檢驗(yàn)原最優(yōu)解是否滿足新增加的約束條件，如果滿足，最優(yōu)解不變；如果不滿足，最優(yōu)解變化；(2)將新約束反映進(jìn)最終單純形表；(3)基變數(shù)係數(shù)向量單位化；(4)用單純形法、對(duì)偶單純形法或引入人工變數(shù)求解。2.例題：第43頁例3-142024-1-2第43頁例3-14

Maxz=2x1+3x2+x3x1+x2+x3+x4

=3x1+4x2+7x3+x5=9

x1，x2，x3，x4

，x50

2024-1-2第43頁例3-14

2024-1-2第43頁例3-14

2024-1-2第43頁例3-14的求解

2024-1-2第43頁例3-14的求解2024-1-21.運(yùn)輸問題的內(nèi)涵：運(yùn)輸問題不僅僅是把某種商品從若干個(gè)產(chǎn)地運(yùn)至若干個(gè)銷地而使總運(yùn)費(fèi)最小的問題；從更廣義上講，運(yùn)輸問題是具有一定模型特徵的線性規(guī)劃問題。2.運(yùn)輸問題的數(shù)學(xué)模型

3.運(yùn)輸問題的求解

4.運(yùn)輸問題的拓展及應(yīng)用第四章運(yùn)輸問題2024-1-22.

運(yùn)輸問題的數(shù)學(xué)模型

2024-1-2第46頁例4-1

2024-1-2例4-1的數(shù)學(xué)模型2024-1-23.運(yùn)輸問題的求解1.求解方法：表上作業(yè)法2.表上作業(yè)法的基本步驟:(1)找出初始基可行解；(2)求檢驗(yàn)數(shù)並判斷最優(yōu)性；(3)確定入基變數(shù)和出基變數(shù)；(4)調(diào)整運(yùn)輸方案；(5)重複2~4，直至最優(yōu)。2024-1-2找出初始基可行解1.最小元素法(1)基本思想：就近供應(yīng)(2)基本步驟(3)例4-12.伏格爾法(1)基本思想：機(jī)會(huì)成本(2)基本步驟(3)例4-12024-1-2最小元素法的基本步驟1.找出最小運(yùn)價(jià)，確定供求關(guān)係，最大量的供應(yīng)；2.劃掉已滿足要求的行或(和)列，如果需要同時(shí)劃去行和列，必須要在該行或列的任意位置填個(gè)“0”；3.在剩餘的運(yùn)價(jià)表中重複1、2兩步，直到得到初始基可行解。2024-1-2例4-1的最小元素法

2024-1-2例4-1的最小元素法

2024-1-2例4-1的最小元素法

2024-1-2例4-1的最小元素法

2024-1-2例4-1的最小元素法

2024-1-2例4-1的最小元素法2024-1-2伏格爾法的基本步驟1.計(jì)算每行、列兩個(gè)最小運(yùn)價(jià)的差；2.找出最大差所在的行或列；3.找出該行或列的最小運(yùn)價(jià)，確定供求關(guān)係，最大量的供應(yīng)；4.劃掉已滿足要求的行或(和)列，如果需要同時(shí)劃去行和列，必須要在該行或列的任意位置填個(gè)“0”；5.在剩餘的運(yùn)價(jià)表中重複1~4步，直到得到初始基可行解。2024-1-2例4-1的伏格爾法

2024-1-2例4-1的伏格爾法

2024-1-2例4-1的伏格爾法

2024-1-2例4-1的伏格爾法

2024-1-2例4-1的伏格爾法

2024-1-2例4-1的伏格爾法2024-1-2求檢驗(yàn)數(shù)並判斷最優(yōu)性1.閉合回路法：從任意一個(gè)空格（非基變數(shù)）出發(fā)，沿著行或列尋找的一條除此空格之外其餘頂點(diǎn)均為有數(shù)字格（基變數(shù)）的回路?？崭竦拈]合回路有且唯一，有數(shù)字格不存在閉合回路。2.位勢(shì)法：行因數(shù)

i，列因數(shù)

j，使每一個(gè)基變數(shù)有cij

=

i

+

j。3.判斷最優(yōu)性：若所有的檢驗(yàn)數(shù)均大於等於零，已得最優(yōu)方案；否則，進(jìn)行方案調(diào)整。2024-1-2閉合回路法的基本步驟1.找出某一空格的閉合回路；2.從該空格開始在閉合回路上給各個(gè)頂點(diǎn)進(jìn)行”+“、”-“間隔標(biāo)號(hào)；3.計(jì)算空格的檢驗(yàn)數(shù)空格檢驗(yàn)數(shù)=

cij(+)-

cij(-)

4.重複1~3，直至求得全部的檢驗(yàn)數(shù)。

2024-1-2例4-1(最小元素法)

2024-1-2閉合回路法求檢驗(yàn)數(shù)

2024-1-2閉合回路法求檢驗(yàn)數(shù)

2024-1-2閉合回路法求檢驗(yàn)數(shù)

2024-1-2例4-1(伏格爾法)

2024-1-2閉合回路法求檢驗(yàn)數(shù)2024-1-2位勢(shì)法的基本步驟1.把基變數(shù)對(duì)應(yīng)的運(yùn)價(jià)拿來；2.任意取一個(gè)位勢(shì)因數(shù)並賦予一個(gè)任意值；3.餘下的所有因數(shù)可根據(jù)基變數(shù)的運(yùn)價(jià)cij

=

i

+

j來唯一確定；4.計(jì)算空格檢驗(yàn)數(shù)

ij=cij-(

i

+

j)。

2024-1-2例4-1(最小元素法)

2024-1-2位勢(shì)法求檢驗(yàn)數(shù)

2024-1-2位勢(shì)法求檢驗(yàn)數(shù)

2024-1-2例1(伏格爾法)

2024-1-2位勢(shì)法求檢驗(yàn)數(shù)

2024-1-2位勢(shì)法求檢驗(yàn)數(shù)2024-1-2確定入基變數(shù)和出基變數(shù)1.確定入基變數(shù)：具有最大絕對(duì)值的負(fù)檢驗(yàn)數(shù)所對(duì)應(yīng)的變數(shù)即為入基變數(shù)。2.確定出基變數(shù)：在入基變數(shù)所處的閉合回路上，讓入基變數(shù)增加，由於供求平衡關(guān)係，帶“+”標(biāo)號(hào)的基變數(shù)將隨之增加；而帶“-”標(biāo)號(hào)的基變數(shù)將隨之減少，最先減少為零的基變數(shù)即為出基變數(shù)。2024-1-2確定入基變數(shù)2024-1-2確定出基變數(shù)2024-1-2調(diào)整運(yùn)輸方案1.在入基變數(shù)所在的閉合回路上，帶“+”標(biāo)號(hào)的格增加x出，帶“-”標(biāo)號(hào)的格減少x出。注意：出基變數(shù)減少後的“0”不要保留在表格中，如果同時(shí)有多個(gè)而帶“-”標(biāo)號(hào)的格減少為零，可人為確定之一為出基變數(shù)，在表格中保留其他“0”。2.對(duì)調(diào)整後的方案求檢驗(yàn)數(shù)並判斷其最優(yōu)性。3.重複1~2兩步，直至得到最優(yōu)方案。

2024-1-2運(yùn)輸方案

2024-1-2調(diào)整後的運(yùn)輸方案2024-1-2最優(yōu)運(yùn)輸方案2024-1-24.運(yùn)輸問題的拓展及應(yīng)用1.產(chǎn)銷不平衡的運(yùn)輸問題(1)產(chǎn)大於銷

(2)銷大於產(chǎn)2.運(yùn)輸問題的應(yīng)用(1)第59頁例4-4(2)第60頁例4-5(3)第62頁習(xí)題6

(4)第60頁例4-62024-1-2產(chǎn)大於銷的運(yùn)輸問題

2024-1-2產(chǎn)大於銷的運(yùn)輸問題2024-1-2銷大於產(chǎn)的運(yùn)輸問題

2024-1-2銷大於產(chǎn)的運(yùn)輸問題2024-1-2第59頁例4-4

2024-1-2第59頁例4-4

2024-1-2第59頁例4-42024-1-2第60頁例4-5

2024-1-2第60頁例4-52024-1-2第62頁習(xí)題6已知某廠每月可生產(chǎn)甲產(chǎn)品270噸，先運(yùn)至A1、A2、A3三個(gè)倉庫，然後在分別供應(yīng)B1、B2、B3、B4、B5五個(gè)用戶。已知倉庫容量分別為50、100、150噸，各用戶的需要量分別為25、105、60、30、70噸。已知從該廠經(jīng)各倉庫然後供應(yīng)各用戶的運(yùn)費(fèi)如下表所示，試確定一個(gè)使總運(yùn)費(fèi)最少的調(diào)運(yùn)方案。

2024-1-2第62頁習(xí)題6

2024-1-2第62頁習(xí)題62024-1-2第60頁例4-6

2024-1-2第60頁例4-6

2024-1-2第60頁例4-6

2024-1-2第60頁例4-62024-1-21.整數(shù)規(guī)劃的數(shù)學(xué)模型2.分枝定界法3.割平面法4.0-1型整數(shù)規(guī)劃5.指派問題第五章整數(shù)規(guī)劃2024-1-2整數(shù)規(guī)劃的數(shù)學(xué)模型Max(Min)(c1

x1+c2x2+…+

cnxn)a11

x1+a12x2+…+a1nxn(=,)

b1a21

x1+a22x2+…+a2nxn(=,)

b2……...am1

x1+am2x2+…+amnxn(=,)

bmx1~n

0

且取整數(shù)純整數(shù)規(guī)劃:所有變數(shù)都有取整約束混合整數(shù)規(guī)劃:只有部分變數(shù)有取整約束2024-1-2分枝定界法1.分枝定界法的基本思路2.第65頁例5-13.練習(xí)題2024-1-2分枝定界法的基本思路

2024-1-2分枝定界法的基本思路2024-1-2第65頁例5-1Maxz=40x1+90x29x1+7x2567x1+20x270x1，x20且取整

2024-1-2用分枝定界法解例5-11.求解相應(yīng)的線性規(guī)劃L0Maxz=40x1+90x29x1+7x2567x1+20x270x1，x20

2024-1-2用分枝定界法解例5-1

x259x1+7x2=564327x1+20x2=701012345678910x1L0:x*=(4.81,1.82),Z*=356

2024-1-2用分枝定界法解例5-12.將L0分解為L1和L2L1：

Maxz=40x1+90x29x1+7x2567x1+20x270

x1

4x1，x20L1：X*=(4,2.10),Z*=349

L2：X*=(5,1.57),Z*=341

L2：

Maxz=40x1+90x29x1+7x2567x1+20x270

x1

5x1，x202024-1-2用分枝定界法解例5-13.分解L1形成L3、L4，其中：

L3={L1,x22}L4={L1,x23}

L3:X*=(4,2),Z*=340

L4:X*=(1.42,3),Z*=327(1)取下界min=340(L3);(2)捨棄L4

2024-1-2用分枝定界法解例5-14.分解L2形成L5、L6，其中：

L5={L2,x21}L6={L2,x22}

L5:X*=(5.44,1),Z*=308

L6:無可行解(1)捨棄L5、L6；(2)得最優(yōu)解X*=(4,2),Z*=340。

2024-1-2例5-1求解過程示意圖L0(4.81，1.82)356L1(4，2.1)349L2(5，1.57)341L3(4，2)340L4(1.42，3)327L5(5.44，1)308L6無可行解2024-1-2練習(xí)題Maxz=2x1+5x2+4x3x1+x2+x3

12x1+2x2154x1+5x326x1~30且取整

2024-1-2求解練習(xí)題首先求解線性規(guī)劃L0:Maxz=2x1+5x2+4x3x1+x2+x3+x4=12x1+2x2+x5=154x1+5x3+x6=26x1~60

2024-1-2求解練習(xí)題

2024-1-2求解練習(xí)題

2024-1-2求解練習(xí)題

2024-1-2求解練習(xí)題

L0（0，15/2，9/2）111/2

L1（0，7，5）55

L2無可行解2024-1-2割平面法1.割平面法的基本思路2.例3.練習(xí)題2024-1-2割平面法的基本思路同分枝定界法一樣，割平面法也是一種利用連續(xù)模型求解非連續(xù)問題的常用方法。割平面法的基本思路是：當(dāng)?shù)玫降慕獠粷M足取整約束時(shí)，就設(shè)法在問題上增加一個(gè)約束條件，把包含這個(gè)非整數(shù)解的一部分可行域從原來的可行域中割除，但不割掉任何一個(gè)整數(shù)可行解。這個(gè)新增加的約束條件就稱為割平面。2024-1-2例Maxz=x1+x2-x1+x213x1+x24x1，x20且取整

2024-1-2用割平面法解例1.求解相應(yīng)的線性規(guī)劃L0Maxz=x1+x2-x1+x213x1+x24x1，x20

2024-1-2用割平面法解例非整數(shù)解，為建立割平面，首先考慮非整數(shù)解中餘數(shù)最大的基變數(shù)，此例中x1、x2的餘數(shù)均為3/4，不妨選取x2：x2+3/4x3+1/4x4=7/4

2024-1-2用割平面法解例x2+3/4x3+1/4x4=7/4現(xiàn)將各係數(shù)分成整數(shù)和非負(fù)真分?jǐn)?shù)兩部分，從而可得：(1+0)x2+(0+3/4)x3+(0+1/4)x4=(1+3/4)將整數(shù)部分的變數(shù)移至等式右端有：3/4x3+1/4x4=3/4+（1-x2）非負(fù)整數(shù)解(1-x2)為整數(shù)，左端非負(fù)故有：3/4x3+1/4x4=3/4+非負(fù)整數(shù)從而：3/4x3+1/4x4

3/4或x2

1以x2

1為割平面可使可行域減少一個(gè)包括A點(diǎn)在內(nèi)的三角形。

2024-1-2x2A1

01x1用割平面法解例

2024-1-2用割平面法解例2024-1-2練習(xí)題Maxz=2x1+5x2+4x3x1+x2+x3

12x1+2x2154x1+5x326x1~30且取整

2024-1-2求解練習(xí)題

2024-1-2求解練習(xí)題選取x2：1/2x1+x2+1/2x5=15/21/2x1+1/2x5=1/2+（7-x2）

於是有割平面：1/2x1+1/2x5

1/2或

x27

2024-1-2求解練習(xí)題

2024-1-2求解練習(xí)題2024-1-20-1型整數(shù)規(guī)劃1.0-1規(guī)劃：0-1規(guī)劃是整數(shù)規(guī)劃的特例，是所有決策變數(shù)僅取0和1的整數(shù)規(guī)劃問題。2.引例（1）第69頁例5-3（2）引例23.0-1規(guī)劃的隱枚舉法（1）隱枚舉法的基本步驟（2）第70頁例5-4（3）第71頁例5-52024-1-2第69頁例5-3

某公司擬在東、西、南三個(gè)區(qū)建立銷售門市部，擬議中有7個(gè)場(chǎng)點(diǎn)A1~7可供選擇。東區(qū)的三個(gè)點(diǎn)A1~3最多選兩個(gè)，西區(qū)的兩個(gè)點(diǎn)A4~5最少選一個(gè)，南區(qū)的兩個(gè)點(diǎn)A6~7最少選一個(gè)。如果建設(shè)Ai點(diǎn)，需要投資bi元，年可獲利ci元，公司可籌集到的投資總額為B元，問應(yīng)如何決策才能使年利潤最大。

2024-1-2例5-3

令xi=0或1，其中：

xi=0表示第I個(gè)點(diǎn)未被選取

xi=1表示第I個(gè)點(diǎn)被選取其數(shù)學(xué)模型為：

x1+x2+x32x4+x51

x6+x71

2024-1-2引例2

兩種運(yùn)輸方式的限制條件分別為：6x1+4x2307x1+3x240互斥的約束統(tǒng)一於一個(gè)模型中：6x1+4x230+Mx37x1+3x240+M(1-x3)

其中x3為0-1變數(shù)。2024-1-2