大M法和兩階段法課件

LP當(dāng)前解已是最優(yōu)的四大特征：⑴存在一組(初始)可行基（其系數(shù)矩陣為單位陣）。⑵檢驗(yàn)數(shù)行的基變量系數(shù)=0。⑶檢驗(yàn)行的非基變量系數(shù)≤0。全部

唯一解。存在無窮多個(gè)解。⑷常數(shù)列向量≥0。Q:所給LP的標(biāo)準(zhǔn)型中約束矩陣中沒有現(xiàn)成的可行基怎么辦？1ppt課件LP當(dāng)前解已是最優(yōu)的四大特征：⑴存在一組(初始)可行基（1.5.2單純形的進(jìn)一步討論2ppt課件1.5.2單純形的進(jìn)一步討論2ppt課件例解下列線性規(guī)劃解:先化為標(biāo)準(zhǔn)形式系數(shù)矩陣中不存在單位矩陣，無法建立初始單純形表。3ppt課件例解下列線性規(guī)劃解:先化為標(biāo)準(zhǔn)形式系數(shù)矩陣中不存在單位x5可作為一個(gè)基變量，第一、三約束中分別加入人工變量x6、x7，得4ppt課件x5可作為一個(gè)基變量，第一、三約束中分別加入人工變量x6、x說明：①不易接受。因?yàn)槭菑?qiáng)行引進(jìn)，稱為人工變量。它們與不一樣。稱為松弛變量和剩余變量，是為了將不等式改寫為等式而引進(jìn)的，而改寫前后兩個(gè)約束是等價(jià)的。②人工變量的引入一般來說是前后不等價(jià)的。只有當(dāng)最優(yōu)解中，人工變量都取值零時(shí)（此時(shí)人工變量實(shí)質(zhì)上就不存在了）才可認(rèn)為兩個(gè)問題的最優(yōu)解是相同的。

處理辦法：把人工變量從基變量中“趕”出去使其變?yōu)榉腔兞?，以求出原問題的初始基本可行解。5ppt課件說明：①不易接受。因?yàn)槭菑?qiáng)行引進(jìn)，稱為人工變量結(jié)論1.若新LP的最優(yōu)解中，人工變量都處在非基變量位置（即取零值）時(shí)，原LP有最優(yōu)解。2.若新LP的最優(yōu)解中，包含有非零的人工變量，則原LP無可行解。3.若新LP的最優(yōu)解的基變量中，包含有人工變量，但該人工變量取值為零。這時(shí)可將某個(gè)非基變量引入基變量中來替換該人工變量，從而得到原LP的最優(yōu)解。6ppt課件結(jié)論1.若新LP的最優(yōu)解中，人工變量都處在非基

以

X(0)作初始基本可行解進(jìn)行迭代時(shí)，怎樣才能較快地將所有的人工變量從基變量中全部“趕”出去（如果能全部“趕”出去的話）。這會(huì)影響到得到最優(yōu)解的迭代次數(shù)。－－大M法與兩階段法7ppt課件以X(0)作初始基本可行解進(jìn)行迭代時(shí)，例1-20用大M法解下列線性規(guī)劃1.大M法解:先化為標(biāo)準(zhǔn)形式系數(shù)矩陣中不存在單位矩陣，無法建立初始單純形表。8ppt課件例1-20用大M法解下列線性規(guī)劃1.大M法解:先化為目標(biāo)函數(shù)修改為：其中M為任意大的實(shí)數(shù)，“-M”稱為“罰因子”。9ppt課件目標(biāo)函數(shù)修改為：其中M為任意大的實(shí)數(shù)，“-M”稱為“罰因子”Cj32－100－M－MbCBXBx1x2x3x4x5x6x7－M

0－Mx6x5x7－4123－1－212[1]－1000101000014101→λj3-2M2+M-1+2M↑－M000－M0－1x6x5x3－6－32[5]3－2001－1000101003→81λj5-6M5M↑0－M0020－1x2x5x3－6/5[3/5]－2/5100001－1/53/5－2/50103/531/5→11/5λj5↑000023－1x2x1x301010000111025/32/31331/319/3λj000－5-25/3最優(yōu)解X＝（31/3，13，19/3，0，0)T；最優(yōu)值Z＝152/310ppt課件Cj32－100－M－MbCBXBx1x2x3x4x5x6x例1-21求解線性規(guī)劃

解:化為標(biāo)準(zhǔn)型加入人工變量x5，得11ppt課件例1-21求解線性規(guī)劃解:化為標(biāo)準(zhǔn)型加入人工變量x5，用單純形法計(jì)算如下表所示。Cj5－800MbCBXBx1x2x3x4x50Mx3x5[3]11－2100－1016→4λj5－M↑－8+2M0M0

5Mx1x5101/3－7/31/3－1/30－10122λj0－29/3+7/3M－5/3+1/3MM0

12ppt課件用單純形法計(jì)算如下表所示。Cj5－800MbCBXBx1x最優(yōu)解X=（2，0，0，0，2），Z=10+2M。大M法小結(jié)：（1）求極大值時(shí)，目標(biāo)函數(shù)變?yōu)椋?）求極小值時(shí)，目標(biāo)函數(shù)變?yōu)橛糜?jì)算機(jī)求解時(shí)，不容易確定M的取值，且M過大容易引起計(jì)算誤差。不足：最優(yōu)解中含有人工變量x5≠0說明這個(gè)解不是最優(yōu)解，是不可行的，因此原問題無可行解。13ppt課件最優(yōu)解X=（2，0，0，0，2），Z=10+2M。大M法小2.兩階段法約束條件是加入人工變量后的約束方程。用大M法處理人工變量，在計(jì)算機(jī)求解時(shí)，對(duì)M只能在計(jì)算機(jī)內(nèi)輸入一個(gè)機(jī)器最大字長(zhǎng)的數(shù)字。這有時(shí)可能使計(jì)算結(jié)果發(fā)生錯(cuò)誤。為克服這個(gè)困難，可以對(duì)添加人工變量的線性規(guī)劃問題分兩階段來求解——稱為兩階段法。將LP的求解過程分成兩個(gè)階段：第一階段：求解第一個(gè)LP：14ppt課件2.兩階段法約束條件是加入人工變量后的約束方程。用大M法第一個(gè)LP的結(jié)果有三種可能情形：1.最優(yōu)值,且人工變量皆為非基變量。從第一階段的最優(yōu)解中去掉人工變量后，即為原LP的一個(gè)基本可行解。作為原LP的一個(gè)初始基本可行解，再求原問題，從而進(jìn)入第二階段。2.最優(yōu)值,說明至少有一個(gè)人工變量不為零。原LP無可行解。不再需要進(jìn)入第二個(gè)階段計(jì)算。

3.最優(yōu)值,且存在人工變量為基變量，但取值為零，把某個(gè)非基變量與該人工變量進(jìn)行調(diào)換。兩階段法的第一階段求解的目的：

1.判斷原LP有無可行解。

2.若有，則可得原LP的一個(gè)初始基本可行解，再對(duì)原LP進(jìn)行第二階段的計(jì)算。15ppt課件第一個(gè)LP的結(jié)果有三種可能情形：1.最優(yōu)值例1-22用兩階段單純形法求解例20的線性規(guī)劃。用單純形法求解，得到第一階段問題的計(jì)算表如下：目標(biāo)函數(shù)為人工變量之和加入人工變量的約束條件第一階段問題為解:標(biāo)準(zhǔn)型為16ppt課件例1-22用兩階段單純形法求解例20的線性規(guī)劃。用單純形法Cj0000011bCBXBx1x2x3x4x5x6x7101x6x5x7－4123－1－212[1]－1000101000014101→λj2－1－2↑1000

100x6x5x3－6－32[5]3－2001－100010100

3→81λj6－5↑0100

000x2x5x3－6/53/5－2/5100001－1/53/5－2/5010

3/531/511/5λj00000

17ppt課件Cj0000011CBXBx1x2x3x4x5x6x71x6最優(yōu)解為，最優(yōu)值w=0。原問題目標(biāo)函數(shù)第二階段問題為說明找到了原問題的一組基本可行解，將它作為初始基可行解，進(jìn)行第二階段的計(jì)算。18ppt課件最優(yōu)解為Cj32-100bCBXBx1x2x3x4x5

2

0

－1

x2

x5

x3

1

0

0

0

0

1

0

1

0λj5↑0000

2

3

－1x2

x1

x30

1

01

0

0

0

0

11

1

0213λj000－5

Cj32－100bCBXBx1x2x3x4x520－1x2x5x3－6/5[3/5]－2/5100001－1/53/5－2/50103/531/5→11/5λj5↑0000

23－1x2x1x301010000111025/32/31331/319/3λj000－5－25/3

用單純形法計(jì)算得到下表最優(yōu)解X＝（31/3，13，19/3，0，0)T；最優(yōu)值Z＝152/319ppt課件Cj32-100bCBXBx1x2x3x4x5

λj例1-23用兩階段法求解用單純形法計(jì)算如下表：解:第一階段問題為20ppt課件例1-23用兩階段法求解用單純形法計(jì)算如下表：解:第一Cj00001bCBXBx1x2x3x4x501x3x5[3]11－2100－1016→4λj

－1↑2010

01x1x5101/3－7/31/3－1/30－10122λj

07/31/310

第一階段的最優(yōu)解X=(2,0,0,0,2)T,最優(yōu)目標(biāo)值w=2≠0,x5仍在基變量中,從而原問題無可行解。21ppt課件Cj00001bCBXBx1x2x3x4x501x3[3]1

解的判斷唯一最優(yōu)解的判斷：最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)非零,則線規(guī)劃具有唯一最優(yōu)解

多重最優(yōu)解的判斷:最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零,則線性規(guī)劃具有多重最優(yōu)解。

無界解的判斷:

某個(gè)λk>0且aik≤０（i=1，2,…,m）則線性規(guī)劃具有無界解。無可行解的判斷：(1)當(dāng)用大M單純形法計(jì)算得到最優(yōu)解并且存在Ri>0時(shí)，則表明原線性規(guī)劃無可行解。(2)當(dāng)?shù)谝浑A段的最優(yōu)值w≠0時(shí)，則原問題無可行解。作業(yè)：1.12(1)22ppt課件解的判斷唯一最優(yōu)解的判斷：最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)非LP當(dāng)前解已是最優(yōu)的四大特征：⑴存在一組(初始)可行基（其系數(shù)矩陣為單位陣）。⑵檢驗(yàn)數(shù)行的基變量系數(shù)=0。⑶檢驗(yàn)行的非基變量系數(shù)≤0。全部

唯一解。存在無窮多個(gè)解。⑷常數(shù)列向量≥0。Q:所給LP的標(biāo)準(zhǔn)型中約束矩陣中沒有現(xiàn)成的可行基怎么辦？23ppt課件LP當(dāng)前解已是最優(yōu)的四大特征：⑴存在一組(初始)可行基（1.5.2單純形的進(jìn)一步討論24ppt課件1.5.2單純形的進(jìn)一步討論2ppt課件例解下列線性規(guī)劃解:先化為標(biāo)準(zhǔn)形式系數(shù)矩陣中不存在單位矩陣，無法建立初始單純形表。25ppt課件例解下列線性規(guī)劃解:先化為標(biāo)準(zhǔn)形式系數(shù)矩陣中不存在單位x5可作為一個(gè)基變量，第一、三約束中分別加入人工變量x6、x7，得26ppt課件x5可作為一個(gè)基變量，第一、三約束中分別加入人工變量x6、x說明：①不易接受。因?yàn)槭菑?qiáng)行引進(jìn)，稱為人工變量。它們與不一樣。稱為松弛變量和剩余變量，是為了將不等式改寫為等式而引進(jìn)的，而改寫前后兩個(gè)約束是等價(jià)的。②人工變量的引入一般來說是前后不等價(jià)的。只有當(dāng)最優(yōu)解中，人工變量都取值零時(shí)（此時(shí)人工變量實(shí)質(zhì)上就不存在了）才可認(rèn)為兩個(gè)問題的最優(yōu)解是相同的。

處理辦法：把人工變量從基變量中“趕”出去使其變?yōu)榉腔兞?，以求出原問題的初始基本可行解。27ppt課件說明：①不易接受。因?yàn)槭菑?qiáng)行引進(jìn)，稱為人工變量結(jié)論1.若新LP的最優(yōu)解中，人工變量都處在非基變量位置（即取零值）時(shí)，原LP有最優(yōu)解。2.若新LP的最優(yōu)解中，包含有非零的人工變量，則原LP無可行解。3.若新LP的最優(yōu)解的基變量中，包含有人工變量，但該人工變量取值為零。這時(shí)可將某個(gè)非基變量引入基變量中來替換該人工變量，從而得到原LP的最優(yōu)解。28ppt課件結(jié)論1.若新LP的最優(yōu)解中，人工變量都處在非基

以

X(0)作初始基本可行解進(jìn)行迭代時(shí)，怎樣才能較快地將所有的人工變量從基變量中全部“趕”出去（如果能全部“趕”出去的話）。這會(huì)影響到得到最優(yōu)解的迭代次數(shù)。－－大M法與兩階段法29ppt課件以X(0)作初始基本可行解進(jìn)行迭代時(shí)，例1-20用大M法解下列線性規(guī)劃1.大M法解:先化為標(biāo)準(zhǔn)形式系數(shù)矩陣中不存在單位矩陣，無法建立初始單純形表。30ppt課件例1-20用大M法解下列線性規(guī)劃1.大M法解:先化為目標(biāo)函數(shù)修改為：其中M為任意大的實(shí)數(shù)，“-M”稱為“罰因子”。31ppt課件目標(biāo)函數(shù)修改為：其中M為任意大的實(shí)數(shù)，“-M”稱為“罰因子”Cj32－100－M－MbCBXBx1x2x3x4x5x6x7－M

0－Mx6x5x7－4123－1－212[1]－1000101000014101→λj3-2M2+M-1+2M↑－M000－M0－1x6x5x3－6－32[5]3－2001－1000101003→81λj5-6M5M↑0－M0020－1x2x5x3－6/5[3/5]－2/5100001－1/53/5－2/50103/531/5→11/5λj5↑000023－1x2x1x301010000111025/32/31331/319/3λj000－5-25/3最優(yōu)解X＝（31/3，13，19/3，0，0)T；最優(yōu)值Z＝152/332ppt課件Cj32－100－M－MbCBXBx1x2x3x4x5x6x例1-21求解線性規(guī)劃

解:化為標(biāo)準(zhǔn)型加入人工變量x5，得33ppt課件例1-21求解線性規(guī)劃解:化為標(biāo)準(zhǔn)型加入人工變量x5，用單純形法計(jì)算如下表所示。Cj5－800MbCBXBx1x2x3x4x50Mx3x5[3]11－2100－1016→4λj5－M↑－8+2M0M0

5Mx1x5101/3－7/31/3－1/30－10122λj0－29/3+7/3M－5/3+1/3MM0

34ppt課件用單純形法計(jì)算如下表所示。Cj5－800MbCBXBx1x最優(yōu)解X=（2，0，0，0，2），Z=10+2M。大M法小結(jié)：（1）求極大值時(shí)，目標(biāo)函數(shù)變?yōu)椋?）求極小值時(shí)，目標(biāo)函數(shù)變?yōu)橛糜?jì)算機(jī)求解時(shí)，不容易確定M的取值，且M過大容易引起計(jì)算誤差。不足：最優(yōu)解中含有人工變量x5≠0說明這個(gè)解不是最優(yōu)解，是不可行的，因此原問題無可行解。35ppt課件最優(yōu)解X=（2，0，0，0，2），Z=10+2M。大M法小2.兩階段法約束條件是加入人工變量后的約束方程。用大M法處理人工變量，在計(jì)算機(jī)求解時(shí)，對(duì)M只能在計(jì)算機(jī)內(nèi)輸入一個(gè)機(jī)器最大字長(zhǎng)的數(shù)字。這有時(shí)可能使計(jì)算結(jié)果發(fā)生錯(cuò)誤。為克服這個(gè)困難，可以對(duì)添加人工變量的線性規(guī)劃問題分兩階段來求解——稱為兩階段法。將LP的求解過程分成兩個(gè)階段：第一階段：求解第一個(gè)LP：36ppt課件2.兩階段法約束條件是加入人工變量后的約束方程。用大M法第一個(gè)LP的結(jié)果有三種可能情形：1.最優(yōu)值,且人工變量皆為非基變量。從第一階段的最優(yōu)解中去掉人工變量后，即為原LP的一個(gè)基本可行解。作為原LP的一個(gè)初始基本可行解，再求原問題，從而進(jìn)入第二階段。2.最優(yōu)值,說明至少有一個(gè)人工變量不為零。原LP無可行解。不再需要進(jìn)入第二個(gè)階段計(jì)算。

3.最優(yōu)值,且存在人工變量為基變量，但取值為零，把某個(gè)非基變量與該人工變量進(jìn)行調(diào)換。兩階段法的第一階段求解的目的：

1.判斷原LP有無可行解。

2.若有，則可得原LP的一個(gè)初始基本可行解，再對(duì)原LP進(jìn)行第二階段的計(jì)算。37ppt課件第一個(gè)LP的結(jié)果有三種可能情形：1.最優(yōu)值例1-22用兩階段單純形法求解例20的線性規(guī)劃。用單純形法求解，得到第一階段問題的計(jì)算表如下：目標(biāo)函數(shù)為人工變量之和加入人工變量的約束條件第一階段問題為解:標(biāo)準(zhǔn)型為38ppt課件例1-22用兩階段單純形法求解例20的線性規(guī)劃。用單純形法Cj0000011bCBXBx1x2x3x4x5x6x7101x6x5x7－4123－1－212[1]－1000101000014101→λj2－1－2↑1000

100x6x5x3－6－32[5]3－2001－100010100

3→81λj6－5↑0100

000x2x5x3－6/53/5－2/5100001－1/53/5－2/5010

3/531/511/5λj00000

39ppt課件Cj0000011CBXBx1x2x3x4x5x6x71x6最優(yōu)解為，最優(yōu)值w=0。原問題目標(biāo)函數(shù)第二階段問題為說明找到了原問題的一組基本可行解，將它作為初始基可行解，進(jìn)行第二階段的計(jì)算。40ppt課件最優(yōu)解為Cj32-100bCBXBx1x2x3x4x5

2

0

－1

x2

x5

x3

1

0

0

0

0

1

0

1

0λj5↑0000

2

3

－1x2

x1

x30

1

01

0

0

0

0

11

1

0213λj000－5

Cj32－100bCBX