物流運(yùn)籌學(xué) 課件 1單純型作業(yè)及軟件運(yùn)用

單純形法的進(jìn)一步討論考慮如何求解線性規(guī)劃問題首先將其標(biāo)準(zhǔn)化得到：添加人工變量上面的問題與前面求解的線性規(guī)劃問題的區(qū)別在于標(biāo)準(zhǔn)化以后沒有前面所述的初始基變量。為了用單純形法求解，可以人為的添加一些變量（人工變量）作為初始基變量。但人工變量是人為添加的，對(duì)原來線性規(guī)劃問題并無意義，并且添加人工變量后的約束方程組的解一般并不是原來的約束方程的解，為了保證所得到的就是原來線性規(guī)劃問題的解，可以讓在求得的解中人工變量取值為零。可見這可以讓人工變量為非基變量來達(dá)到這一目的。也就是讓人工變量盡量從基變量中換出來。在添加人工變量后為了在單純形計(jì)算中使人工變量逐個(gè)從基變量中換出，有兩種處理方式：大M法和兩階段法。將約束方程添加人工變量得到：大M法將人工變量在目標(biāo)函數(shù)中反映出來得到如下形式的線性規(guī)劃：-231000-M-MCBXBx1x2x3x4x5x6x7x8b-Mx7[2]-12-100101-Mx82210-100120x6-121001004-2+4M3+M1+3M-M-M000-2x11-1/21-1/2001/201/2-Mx80[3]-11-10-1110x603/22-1/2011/209/202+3M3-M-1+M-M01-M0-2x110[5/6]-1/3-1/601/31/62/33x201-1/31/3-1/30-1/31/31/30x6005/2-11/211-1/24008/3-5/32/30-M+5/3-M-2/3-231000-M-MCBXBx1x2x3x4x5x6x7x8b1x36/501-2/5-1/502/51/54/53x22/5101/5-2/50-1/52/53/50x6-3000[1]10-12-22/500-1/57/50-M+1/5-M-3/51x33/501-2/501/52/506/53x2-4/5101/502/5-1/507/50x5-3000110-12-1/500-1/50-7/5-M+1/5-M27/5。為了減少計(jì)算工作量，紅色陰影部分可以不寫！因此最優(yōu)解為最優(yōu)目標(biāo)函數(shù)值為需要說明的是，如果在用大M法求解線性規(guī)劃問題時(shí)，最終表的基變量中還含有人工變量，那么這個(gè)最終表并沒有給出原來問題的基可行解，從而沒有給出原來的線性規(guī)劃問題最優(yōu)解。這時(shí)原來線性規(guī)劃問題為無可行解。兩階段法求解如下LP:第一階段：求解輔助的線性規(guī)劃問題約束條件就是原來問題的(標(biāo)準(zhǔn)化后的)約束條件目標(biāo)函數(shù)是所有人工變量的和,求最小值

00000011

CBXBx1x2x3x4x5x6x7x8b1x7[2]-12-1001011x82210-100120x6-121001004

-4-1-311000

0x11-1/21-1/2001/201/21x80[3]-11-10-1110x603/22-1/2011/209/2

0-31-11020

0x1105/6-1/3-1/601/31/62/30x201-1/31/3-1/30-1/31/31/30x6005/2-11/211-1/24

000000110第一階段第一階段的最優(yōu)目標(biāo)函數(shù)值必須等于零.否則為無可行解,不必進(jìn)行第二階段.第二階段（去掉人工變量，換為原來的目標(biāo)函數(shù)）

-231000

CBXBx1x2x3x4x5x6b-2x110[5/6]-1/3-1/602/33x201-1/31/3-1/301/30x6005/2-11/214

0011/3-5/32/30

1x36/501-2/5-1/504/53x22/5101/5-2/503/50x6-3000[1]12

-22/500-1/57/50

1x33/501-2/501/56/53x2-4/5101/502/57/50x5-3000112

-1/500-1/50-7/527/5第二階段的初始單純形表其實(shí)就是第一階段的最終表,只須將其中的人工變量去掉,并將目標(biāo)函數(shù)系數(shù)換成原來的目標(biāo)函數(shù)系數(shù).故原來問題的最優(yōu)解為最優(yōu)目標(biāo)函數(shù)值這一結(jié)果與大M法得到的結(jié)果是一致的。無可行解的判別：在用大M法求解線性規(guī)劃問題時(shí)，若最終單純形表的基變量中含人工變量；或用兩階段法求解時(shí)，第一階段最終表的基變量中含非零的人工變量，也就是第一階段最優(yōu)目標(biāo)函數(shù)值不等于零，則線性規(guī)劃問題無可行解。練習(xí)：將下列問題化成標(biāo)準(zhǔn)型:MinS=-x1+2x2-3x3s.t.x1+x2+x3

7x1-x2+x3

2-3x1+x2+2x3=5x1,x2

0x3無非負(fù)限制MaxS=x1-2x2+3x3

-3x3

s.t.x1+x2+x3

-x3

+x4=7x1-x2+x3

-x3

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

-2x3

=5x1,x2,

x3

，x3

,x4，x5

0線性規(guī)劃問題解的概念（二維）線性規(guī)劃問題圖解法：（1）滿足約束條件的變量的值，稱為可行解。（2）使目標(biāo)函數(shù)取得最優(yōu)值的可行解，稱為最優(yōu)解。

maxS=50x1+30x2s.t.4x1+3x2

1202x1+x2

50x1,x2

0x2504030201010203040x14x1+3x2

120由4x1+3x2

120x1

0x2

0圍成的區(qū)域x2504030201010203040x12x1+x2

50由2x1+x2

50x1

0x2

0圍成的區(qū)域x2504030201010203040x12x1+x2

504x1+3x2

120可行域同時(shí)滿足：2x1+x2

504x1+3x2

120x1

0x2

0的區(qū)域——可行域x2504030201010203040x1可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）可行域是由約束條件圍成的區(qū)域，該區(qū)域內(nèi)的每一點(diǎn)都是可行解，它的全體組成問題的解集合。該問題的可行域是由O，Q1，Q2，Q3作為頂點(diǎn)的凸多邊形x2504030201010203040x1可行域目標(biāo)函數(shù)是以S作為參數(shù)的一組平行線x2=

S/30-（5/3）x1x2504030201010203040x1可行域當(dāng)S值不斷增加時(shí)，該直線x2=

S/30-（5/3）x1沿著其法線方向向右上方移動(dòng)。x2504030201010203040x1可行域當(dāng)該直線移到Q2點(diǎn)時(shí)，S（目標(biāo)函數(shù)）值達(dá)到最大：MaxS=50

15+30

20=1350此時(shí)最優(yōu)解=（15，20）Q2（15，20）線性規(guī)劃問題解的概念線性規(guī)劃標(biāo)準(zhǔn)型的矩陣形式：Max

S=CX（3-6）

s.t.

AX=b（3-7）

X

0（3-8）

a11a12….a1nb1A=a21a22….a2nb

=

b2………am1am2….amn

bn

c1x10c2x20C=X=0=……………..

cn

xn0解、可行解、最優(yōu)解⊙滿足約束條件（3-7）與（3-8）的X，稱為線性規(guī)劃的問題可行解。⊙滿足目標(biāo)函數(shù)（3-6）的可行解X，稱為線性規(guī)劃的問題最優(yōu)解?；?、基向量、基變量⊙設(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就稱為

基變量，其余的就稱為非基變量。基解.基可行解.可行基⊙對(duì)于某一特定的基B，非基變量取

0值的解，稱為基解?！褲M足非負(fù)約束條件的基礎(chǔ)解，稱為基可行解。⊙與基可行解對(duì)應(yīng)的基，稱為可行基。為了理解基解.基可行解.最優(yōu)解的概念，用下列例子說明：例：maxS=2x1+3x2

s.t.-2x1+3x2

6

3x1-2x2

6

x1+x2

4

x1,x2

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

x2=6x1+x2=4AQ1Q2Q3Q4Bx243211234x1O-1-1-2-2-3-3ABx243211234x1O-1-1-2-2-3-3-2x1+3x2

63x1-2

x2

6x1+x2

4AQ1Q2Q3Q4B滿足約束條件

-2x1+3x2

6

3x1-2

x2

6

x1+x2

4

與坐標(biāo)系

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

-2x1+3x2

6

3x1-2

x2

6

x1+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ū)域?；尚薪猓狐c(diǎn)（O，Q1，Q2，Q3，Q4）最優(yōu)解：

Q3解的集合：非可行解可行解解的集合：基礎(chǔ)解解的集合：可行解基礎(chǔ)解基礎(chǔ)可行解解的集合：可行解基礎(chǔ)解基礎(chǔ)最優(yōu)解基礎(chǔ)可行解例

某工廠經(jīng)市場(chǎng)調(diào)研，決定生產(chǎn)甲、乙兩種產(chǎn)品，其單臺(tái)利潤分別為60元和30元，兩種產(chǎn)品共用一種鋼材、一臺(tái)設(shè)備，其資源及獲利情況如下：甲乙現(xiàn)有資源鋼材消耗定額（公斤/臺(tái)）24600公斤臺(tái)時(shí)消耗定額（小時(shí)/臺(tái)）31400小時(shí)配件（件/臺(tái)）20250件利潤（元）6030求利潤最大的產(chǎn)品結(jié)構(gòu)決策。②確定目標(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)，可得最大利潤約束條件：05050100100150150200250300350200250300350400x1x2A(0,150)B(100,100)C(125,25)D(125,0)(4)線性規(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)任美國空軍審計(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è)來比較的話，即使用個(gè)地球或個(gè)太陽的容量來裝計(jì)算機(jī)，這些計(jì)算機(jī)從150億年前開始，全部投入計(jì)算，大約要算到太陽熄滅才有答案。而用單純形法軟件，幾秒鐘就可以給出答案。

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

線性規(guī)劃問題的可行解有無窮多個(gè)，與某一凸集上的無窮多個(gè)點(diǎn)一一對(duì)應(yīng)。要從無窮多個(gè)可行解中尋找最優(yōu)解，幾乎不可能。可以證明，最優(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返回目錄用單純形表求解問題例、用單純形表求解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

30400-1Z

341017x51

x1x2x3x4x5bXBCBΘ

523-11C

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

1

1

1/2

04x33

1-40-2015Z5/230-1/213x51

x1

x2

x3

x4

x5bXBCBΘ

523-11C

122108x4-1

30400-1Z

341017x51

x1x2x3x4x5bXBCBΘ

523-11C8/27/1

最優(yōu)解最優(yōu)值

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

1

1

1/2

04x33

1-40-2015Z3/5/25/230-1/213x51

x1

x2

x3

x4

x5bXBCBΘ

523-11C

02/513/5-1/517/5x33

0-26/50-9/5-2/581/5Z

16/50-1/52/56/5x15

x1x2x3x4x5bXBCBΘ

523-11C例3、用單純形方法求解線性規(guī)劃問題解：本題的目標(biāo)函數(shù)是求極小化的線性函數(shù)，可以令則這兩個(gè)線性規(guī)劃問題具有相同的可行域和最優(yōu)解，只是目標(biāo)函數(shù)相差一個(gè)符號(hào)而已。

010103x22

0012-12x30-010103x224/1101004x303/1010103x40_101004x30

0000-18Z’

100-212x11

100-206Z’2/1100-212x50

120000Z’8/2120018x50

x1x2x3x4x5bXBCBΘ

12000C最優(yōu)解最優(yōu)值2/23/1-單純形法的計(jì)算步驟結(jié)束例?；瘶?biāo)準(zhǔn)形式：Maxz=50x1+100x2s.t.x1+x2+x3=3002x1+x2+x4=400x2+x5=250x1,x2,x3,x4,x5≥0最優(yōu)解

x1=50x2=250x4=50（松弛標(biāo)量，表示原料A有50個(gè)單位的剩余）

線性規(guī)劃解的性質(zhì)（幾何意義）凸集概念：

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

例某鐵器廠生產(chǎn)甲、乙、丙三種產(chǎn)品，生產(chǎn)一件甲種產(chǎn)品需要1小時(shí)車工加工、2小時(shí)銑工加工、2小時(shí)裝配，獲得利潤100元；生產(chǎn)一件乙種產(chǎn)品需要2小時(shí)車工加工、1小時(shí)銑工加工、2小時(shí)裝配，獲得利潤90元；生產(chǎn)一件丙種產(chǎn)品需要2小時(shí)車工加工、1小時(shí)銑工加工、1小時(shí)裝配，獲得利潤60元。工廠每月可供利用的車工加工工時(shí)為4200小時(shí)，銑工加工工時(shí)為6000小時(shí)，裝配工時(shí)為3600小時(shí)。工廠在每月內(nèi)應(yīng)如何安排生產(chǎn)，使總利潤最大。

解設(shè)甲、乙、丙三種產(chǎn)品的月產(chǎn)量分別為件；總利潤為S元。excel計(jì)算舉例下面用單純形法解此線性規(guī)劃問題。其數(shù)學(xué)模型為：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：解引進(jìn)松馳變量：

打開Excel，出現(xiàn)新工作簿.

⑴在單元格A1--A7中，依次輸入字符串：“x1”、“x2”“x3”、“車工”、“銑工”、“安裝”、“S”，以表示B列中相應(yīng)單元格的項(xiàng)目名；

⑵在B列單元格B4—B6中，依次輸入相應(yīng)約束條件左邊的線式；⑶在單元格B7中輸入目標(biāo)函數(shù)的線性式。因?yàn)閱卧馚1、B2、B3的默認(rèn)值是0，所以單元格B4—B6的計(jì)算結(jié)果都等于0。

⑷單擊工具菜單中的[規(guī)劃求解]菜單。

在彈出的[規(guī)劃求解參數(shù)]對(duì)話框中：設(shè)置目標(biāo)單元格為B7；選[最大值]；可變單元格：B1、B2、B3。

在彈出的[添加約束]對(duì)話框中，逐條輸入約束條件：?jiǎn)卧褚梦恢脵?，先后分別選B1—B6；在關(guān)系符號(hào)中，選擇“≥”或“≤”；約束值欄，先后分別輸入：0、0、0、4200、6000、3600。每輸入一條后，均需點(diǎn)擊[添加]按紐。下面對(duì)話框中輸入的約束條件是：車工的加工工時(shí)不能超過420小時(shí)。

最后單擊[確定]，回到[規(guī)劃求解參數(shù)]對(duì)話框，約束欄內(nèi)出

了6條約束條件。

單擊[求解]按紐，彈出[規(guī)劃求解結(jié)果]對(duì)話框。

B列單元格即出最優(yōu)解和最優(yōu)值。最優(yōu)解為：最優(yōu)值為：maxS=196000所以工廠在每月內(nèi)應(yīng)生產(chǎn)1000件甲種產(chǎn)品、不生產(chǎn)乙種產(chǎn)品、生產(chǎn)1600件丙種產(chǎn)品，才能使總利潤最大，最大利潤為196000元。LinDo輸入模型求解點(diǎn)擊求解按鈕即可結(jié)果輸入模型!注釋內(nèi)容，可用中文!目標(biāo)函數(shù)：最大-max,最小-min,大小寫不分

max3x1+5x2+4x3!約束，以subjectto開始

subjectto2x1+3x2<=15002x2+4x3<=8003x1+2x2+5x3<=2000end注意事項(xiàng)變量以字母開頭，下標(biāo)寫在后面，系數(shù)與邊量之間加空格不等號(hào)為:<=(<),>=(>),=,<=與<等同變量非負(fù)約束可省略結(jié)束時(shí)以end標(biāo)示結(jié)果

LPOPTIMUMFOUNDATSTEP3OBJECTIVEFUNCTIONVALUE1)2675.000

VARIABLEVALUEREDUCEDCOSTX1375.0000000.000000X2250.0000000.000000X375.0000000.000000

ROWSLACKORSURPLUSDUALPRICES2)0.0000001.0500003)0.0000000.6250004)0.0000000.300000LinGo輸入模型

LinDo模式

LinGo模式求解點(diǎn)擊求解按鈕即可結(jié)果LinDo輸入模式model:MAX=3*x1+5*x2+4*x3;2*x1+3*x2<=1500;2*x2+4*x3<=800;3*x1+2*x2+5*x3<=2000;end注意與LinDo的區(qū)別目標(biāo)函數(shù)中加等號(hào)變量與系數(shù)之間用“*”Model:-end可省略LinGo模式Model:

Sets:

Endsets

Data:

Enddata

調(diào)用函數(shù)與計(jì)算end!定義集合！定義數(shù)據(jù)集合部分model:！開始sets:！定義集合ve/1..3/:c,x;co/1..3/:b;ma(co,ve):a;endsets！注：集表達(dá)式：名稱/成員/：屬性名稱（初始集）：屬性定義數(shù)據(jù)data:！定義數(shù)據(jù)c=354;ba=230024325;Enddata！注：數(shù)據(jù)的大小與集合定義中一致，分量中間用空格或逗號(hào)分開，數(shù)據(jù)結(jié)束后用分號(hào)；調(diào)用函數(shù)max=@sum(ve(j):c(j)*x(j));@for(co(i):@sum(ve(j):a(i,j)*x(j))<=b(i));主要函數(shù)：@for(set(set_index_list)|condition:expression)@sum(set(set_index_list)|condition:expression)@min(max)(set(set_index_list)|condition:expression)結(jié)果Globaloptimalsolutionfoundatiteration:3Objectivevalue:2675.000VariableValueReducedCostC(1)3.0