第四次課表上作業(yè)法及大法和兩階段法

第四次課表上作業(yè)法及大法和兩階段法演示文稿現(xiàn)在是1頁\一共有41頁\編輯于星期二優(yōu)選第四次課表上作業(yè)法及大法和兩階段法現(xiàn)在是2頁\一共有41頁\編輯于星期二E單位陣N非基陣基變量XB非基變量XN0單純形表現(xiàn)在是3頁\一共有41頁\編輯于星期二

21000

檢驗(yàn)數(shù)單純形表結(jié)構(gòu)單純形表

—24/65/1C已知現(xiàn)在是4頁\一共有41頁\編輯于星期二

21000

—24/65/1C檢驗(yàn)數(shù)單純形表結(jié)構(gòu)單純形表基可行解：現(xiàn)在是5頁\一共有41頁\編輯于星期二單純形表結(jié)構(gòu)單純形表

21000

—24/65/1C檢驗(yàn)數(shù)有時(shí)不寫此項(xiàng)求現(xiàn)在是6頁\一共有41頁\編輯于星期二單純形表結(jié)構(gòu)單純形表

21000

—24/65/1C檢驗(yàn)數(shù)求現(xiàn)在是7頁\一共有41頁\編輯于星期二單純形表結(jié)構(gòu)單純形表

21000

—24/65/1C檢驗(yàn)數(shù)求不妨設(shè)此為主列主行現(xiàn)在是8頁\一共有41頁\編輯于星期二單純形表結(jié)構(gòu)單純形表

21000

—24/65/1C檢驗(yàn)數(shù)主元現(xiàn)在是9頁\一共有41頁\編輯于星期二用單純形表求解LP問題例、用單純形表求解LP問題現(xiàn)在是10頁\一共有41頁\編輯于星期二解：化標(biāo)準(zhǔn)型現(xiàn)在是11頁\一共有41頁\編輯于星期二

21000

01505100

0

24620100511001

21000

—24/65/1主元化為1主列單位向量換出換入表1：列初始單純形表（單位矩陣對(duì)應(yīng)的變量為基變量）正檢驗(yàn)數(shù)中最大者對(duì)應(yīng)的列為主列最小的值對(duì)應(yīng)的行為主行現(xiàn)在是12頁\一共有41頁\編輯于星期二

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=表2：換基

（初等行變換，主列化為單位向量，主元為1）檢驗(yàn)數(shù)>0確定主列最小確定主列主元現(xiàn)在是13頁\一共有41頁\編輯于星期二

21000

015/20015/4-15/2

2

7/21001/4-1/213/2010-1/43/2000-1/4-1/2

檢驗(yàn)數(shù)<=0最優(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表3：換基

（初等行變換，主列化為單位向量，主元為1）現(xiàn)在是14頁\一共有41頁\編輯于星期二

21000

01505100

0

24620100511001

21000練習(xí):一般主列選擇正檢驗(yàn)數(shù)中最大者對(duì)應(yīng)的列,也可選擇其它正檢驗(yàn)數(shù)的列.以第2列為主列,用單純形法求解。正檢驗(yàn)數(shù)對(duì)應(yīng)的列為主列現(xiàn)在是15頁\一共有41頁\編輯于星期二結(jié)束2.4單純形法的計(jì)算步驟現(xiàn)在是16頁\一共有41頁\編輯于星期二2.5.1單純形法的進(jìn)一步討論一、大M法二、兩階段法----人工變量法現(xiàn)在是17頁\一共有41頁\編輯于星期二人工變量法問題：線性規(guī)劃問題化為標(biāo)準(zhǔn)形時(shí)，若約束條件的系數(shù)矩陣中不存在單位矩陣，如何構(gòu)造初始可行基？

現(xiàn)在是18頁\一共有41頁\編輯于星期二人工變量法加入人工變量設(shè)線性規(guī)劃問題的標(biāo)準(zhǔn)型為：現(xiàn)在是19頁\一共有41頁\編輯于星期二

加入人工變量,構(gòu)造初始可行基.人工變量法系數(shù)矩陣為單位矩陣，可構(gòu)成初始可行基。現(xiàn)在是20頁\一共有41頁\編輯于星期二

約束條件已改變，目標(biāo)函數(shù)如何調(diào)整？人工變量法現(xiàn)在是21頁\一共有41頁\編輯于星期二“懲罰”人工變量?。?）大M法（2）兩階段法現(xiàn)在是22頁\一共有41頁\編輯于星期二一、大M法人工變量在目標(biāo)函數(shù)中的系數(shù)為-M,

其中，M為任意大的正數(shù)。目標(biāo)函數(shù)中添加“罰因子”-M（M是任意大的正數(shù)）為人工變量系數(shù)，只要人工變量>0，則目標(biāo)函數(shù)不可能實(shí)現(xiàn)最優(yōu)?，F(xiàn)在是23頁\一共有41頁\編輯于星期二例:求解線性規(guī)劃問題一、大M法現(xiàn)在是24頁\一共有41頁\編輯于星期二

一、大M法解:加入松弛變量和剩余變量進(jìn)行標(biāo)準(zhǔn)化,加入人工變量構(gòu)造初始可行基.

現(xiàn)在是25頁\一共有41頁\編輯于星期二求解結(jié)果出現(xiàn)檢驗(yàn)數(shù)非正若基變量中含非零的人工變量，則無可行解；否則，有最優(yōu)解。一、大M法用單純形法求解（見下頁）。目標(biāo)函數(shù)中添加“罰因子”-M為人工變量系數(shù)，只要人工變量>0，則目標(biāo)函數(shù)不可能實(shí)現(xiàn)最優(yōu)?，F(xiàn)在是26頁\一共有41頁\編輯于星期二

1-21-412-201

3-6MM-13M-1

3

-1-1

x1

x2

x3

0

x411-M

x63-M

x71Cj-Zj

Cj

CBXBb

100-100

0-M

00

x4

x5

113/21

001001

00

-

M-M

x6

x7

表1（初始單純形表）一、大M法（單純形法求解）現(xiàn)在是27頁\一共有41頁\編輯于星期二

3-20010

-201

1M-10

3

-1-1x1

x2

x3

0x410-M

x61-1x31Cj-Zj

Cj

CBXBb

100-100

0-M

00

x4

x5

1

0-11-201

01-3M

-

M-M

x6

x7

一、大M法（單純形法求解）表2現(xiàn)在是28頁\一共有41頁\編輯于星期二

3

00010-201

100

3

-1-1

x1

x2

x3

0x412-1x21-1x31Cj-Zj

Cj

CBXBb

1-20-100

0-1

00

x4

x5

4

i

2-51-2011-M-1

-M

-

M-M

x6

x7

表3一、大M法（單純形法求解）現(xiàn)在是29頁\一共有41頁\編輯于星期二

100010001

000

3

-1-1

x1

x2

x3

3x14-1x21-1x39

2

Cj

CBXB

b1/3-2/3

0-12/3-4/3

-1/3-1/3

00

x4

x5

2/3-5/3

1-24/3-7/3

1/3-M2/3-M

-

M-M

x6

x7

表4一、大M法（單純形法求解）最優(yōu)解為目標(biāo)函數(shù)值z(mì)=2檢驗(yàn)數(shù)均非正，此為最終單純形表現(xiàn)在是30頁\一共有41頁\編輯于星期二M在計(jì)算機(jī)上處理困難。分階段處理——先求初始基，再求解。二、兩階段法現(xiàn)在是31頁\一共有41頁\編輯于星期二二、兩階段法第一階段:構(gòu)造如下的線性規(guī)劃問題人工變量的系數(shù)矩陣為單位矩陣，可構(gòu)成初始可行基。

目標(biāo)函數(shù)僅含人工變量，并要求實(shí)現(xiàn)最大化。若其最優(yōu)解的目標(biāo)函數(shù)值不為0，也即最優(yōu)解的基變量中含有非零的人工變量，則原線性規(guī)劃問題無可行解?，F(xiàn)在是32頁\一共有41頁\編輯于星期二

用單純形法求解上述問題,若ω=0,進(jìn)入第二階段,否則,原問題無可行解。第二階段：去掉人工變量，還原目標(biāo)函數(shù)系數(shù)，做出初始單純形表。用單純形法求解即可。二、兩階段法下面舉例說明，仍用大M法的例。現(xiàn)在是33頁\一共有41頁\編輯于星期二例：二、兩階段法現(xiàn)在是34頁\一共有41頁\編輯于星期二

二、兩階段法構(gòu)造第一階段問題并求解解：用單純形法求解現(xiàn)在是35頁\一共有41頁\編輯于星期二二、兩階段法—（第一階段、求minω

）

1-21-412-201

-613

000

x1

x2

x3

0x411-1x63-1x71

Ci

CBXBb

1000-11000

0-10

00-1--1

x4

x5

x6

01103/211

0

-

1

x7

i表1現(xiàn)在是36頁\一共有41頁\編輯于星期二

-1--211-

-3

-

1

x7

3-20010

-201

010

000

x1

x2x3

0x410-1x610x31

Ci

CBXBb

1000-11000

0-10

00-1

x4

x5

x6二、兩階段法—（第一階段、求minω

）表2現(xiàn)在是37頁\一共有41頁\編輯于星期二

-54-2-1-

-1

-

1

x7

3

00010-20

1

000

000

x1

x2x3

0x4120x210x31

Ci

CBXBb

1-220-11000

00-1

00-1

x4

x5

x6二、兩階段法—（第一階段、求minω

）表3：最終單純形表第二階段不含人工變量且ω=