目標規劃與整數規劃第1頁，課件共188頁，創作于2023年2月0引言從線性規劃問題可看出：線性規劃只研究在滿足一定條件下，單一目標函數取得最優解，而在企業管理中，經常遇到多目標決策問題，如擬訂生產計劃時，不僅考慮總產值，同時要考慮利潤，產品質量和設備利用率等。這些指標之間的重要程度（即優先順序）也不相同，有些目標之間往往相互發生矛盾。第2頁，課件共188頁，創作于2023年2月線性規劃致力于某個目標函數的最優解，這個最優解若是超過了實際的需要，很可能是以過分地消耗了約束條件中的某些資源作為代價。線性規劃把各個約束條件的重要性都不分主次地等同看待，這也不符合實際情況。第3頁，課件共188頁，創作于2023年2月求解線性規劃問題，首先要求約束條件必須相容，如果約束條件中，由于人力，設備等資源條件的限制，使約束條件之間出現了矛盾，就得不到問題的可行解，但生產還得繼續進行，這將給人們進一步應用線性規劃方法帶來困難。第4頁，課件共188頁，創作于2023年2月為了彌補線性規劃問題的局限性，解決有限資源和計劃指標之間的矛盾，在線性規劃基礎上，建立目標規劃方法，從而使一些線性規劃無法解決的問題得到滿意的解答。第5頁，課件共188頁，創作于2023年2月多目標優先級

先將目標等級化：將目標按重要性的程度不同依次分成一級目標、二級目標…..。最次要的目標放在次要的等級中。第6頁，課件共188頁，創作于2023年2月目標優先級作如下約定：對同一個目標而言，若有幾個決策方案都能使其達到，可認為這些方案就這個目標而言都是最優方案；若達不到，則與目標差距越小的越好。第7頁，課件共188頁，創作于2023年2月目標優先級作如下約定：不同級別的目標的重要性是不可比的。即較高級別的目標沒有達到的損失，任何較低級別的目標上的收獲都不可彌補。所以在判斷最優方案時，首先從較高級別的目標達到的程度來決策，然后再其次級目標的判斷。第8頁，課件共188頁，創作于2023年2月目標優先級作如下約定：同一級別的目標可以是多個。各自之間的重要程度可用數量（權數）來描述。因此，同一級別的目標的其中一個的損失，可有其余目標的適當收獲來彌補。第9頁，課件共188頁，創作于2023年2月1多目標規劃問題的數學模型多目標的處理為了將不同級別的目標的重要性用數量表示，引進P1，P2，….,用它表示一級目標，二級目標，….，的重要程度，規定P1》P2》

P3》….。稱P1，P2，….,為級別系數。同一級Pi中，系數大的優先考慮。第10頁，課件共188頁，創作于2023年2月約束方程的處理差異變量：決策變量x超過目標值b的部分記d+為正偏差；決策變量x不足目標值b的部分記d-為負偏差d+

0,d-

0且x+d--d+=b同一個目標約束中d-×d+=0。第11頁，課件共188頁，創作于2023年2月多目標的綜合

x+d--d+=b若決策目標中規定x

b,故d+取最小。若決策目標中規定x

b,d-取最小若決策目標中規定x=b,故d-+d+取最小。絕對約束（硬約束）：必須嚴格滿足的等式約束和不等式約束。目標約束（軟約束）：含正負偏差的約束。bd+

d-

第12頁，課件共188頁，創作于2023年2月目標規劃問題的求解(1)目標規劃問題的圖解法(2)用單純形法求目標函數的最優解(3)靈敏度分析:

目標規劃的靈敏度分析與線性規劃類似，對優先因子的變化問題進行舉例說明。第13頁，課件共188頁，創作于2023年2月例1：某電器公司經營的唱機和錄音機均有車間A、B流水作業組裝。數據見下表。第14頁，課件共188頁，創作于2023年2月第15頁，課件共188頁，創作于2023年2月目標級為：(1)庫存費用不超過4600元；(2)每月銷售唱機不少于80臺；(3)不使A、B車間停工（權數由生產費用確定）；(4)A車間加班時間限制在20小時內；（5）每月銷售錄音機至少為100臺；（6）兩車間加班時數總和要盡可能小（權數由生產費用確定）；第16頁，課件共188頁，創作于2023年2月解：設每月生產唱機、錄音機X1，X2臺。且A、B的生產費用之比為100：50=2：1P1:庫存費用不超過4600元,50X1+30X2+d1--d1+=4600第17頁，課件共188頁，創作于2023年2月解：設每月生產唱機、錄音機X1，X2臺。且A、B的生產費用之比為100：50=2：1P1:庫存費用不超過4600元,P1d1+50X1+30X2+d1--d1+=4600第18頁，課件共188頁，創作于2023年2月解：設每月生產唱機、錄音機X1，X2臺。且A、B的生產費用之比為100：50=2：1P1:庫存費用不超過4600元,P1d1+50X1+30X2+d1--d1+=4600P2:每月銷售唱機不少于80臺,

X1+d2--d2+=80第19頁，課件共188頁，創作于2023年2月解：設每月生產唱機、錄音機X1，X2臺。且A、B的生產費用之比為100：50=2：1P1:庫存費用不超過4600元,P1d1+50X1+30X2+d1--d1+=4600P2:每月銷售唱機不少于80臺,P2d2-

X1+d2--d2+=80第20頁，課件共188頁，創作于2023年2月解：設每月生產唱機、錄音機X1，X2臺。且A、B的生產費用之比為100：50=2：1P1:庫存費用不超過4600元,P1d1+50X1+30X2+d1--d1+=4600P2:每月銷售唱機不少于80臺,P2d2-

X1+d2--d2+=80P3:不使A車間停工,不使B車間停工,

A車間:2X1+X2+d3--d3+=180B車間:X1+3X2+d4--d4+=200

第21頁，課件共188頁，創作于2023年2月解：設每月生產唱機、錄音機X1，X2臺。且A、B的生產費用之比為100：50=2：1P1:庫存費用不超過4600元,P1d1+50X1+30X2+d1--d1+=4600P2:每月銷售唱機不少于80臺,P2d2-

X1+d2--d2+=80P3:不使A車間停工,不使B車間停工,2

P3d3-+P3d4-

2X1+X2+d3--d3+=180X1+3X2+d4--d4+=200

第22頁，課件共188頁，創作于2023年2月

P4:A車間加班時間限制在20小時內；2X1+X2+d5--d5+=200第23頁，課件共188頁，創作于2023年2月

P4:A車間加班時間限制在20小時內；P4d5+2X1+X2+d5--d5+=200第24頁，課件共188頁，創作于2023年2月

P4:A車間加班時間限制在20小時內；P4d5+2X1+X2+d5--d5+=200P5:每月銷售錄音機至少為100臺；X2+d6--d6+=100第25頁，課件共188頁，創作于2023年2月

P4:A車間加班時間限制在20小時內；P4d5+2X1+X2+d5--d5+=200P5:每月銷售錄音機至少為100臺；P5d6-X2+d6--d6+=100第26頁，課件共188頁，創作于2023年2月

P4:A車間加班時間限制在20小時內；P4d5+2X1+X2+d5--d5+=200P5:每月銷售錄音機至少為100臺；P5d6-X2+d6--d6+=100P6:兩車間加班時數總和要盡可能小（權數由生產費用確定）,2P6d5++P6d4+

X1,X2,di-,di+,

0(i=1,2,3,4,5,6)第27頁，課件共188頁，創作于2023年2月MinS=P1d1++P2d2-+2

P3d3-+P3d4-+P4d5++P5d6-+P5d3++2P6d5++P6d4+約束方程：50X1+30X2+d1--d1+=4600

X1+d2--d2+=80

2X1+X2+d3--d3+=180

X1+3X2+d4--d4+=2002X1+X2+d5--d5+=200X2+d6--d6+=100

X1,X2,di-,di+,

0(i=1,2,3,4,5,6)第28頁，課件共188頁，創作于2023年2月2目標規劃的圖解法

ⅠⅡ擁有量原材料（kg）2111設備1210利潤（元/件）810例：某工廠生產Ⅰ、Ⅱ兩種產品，數據如下決策者在原材料供應嚴格受限制的情況考慮：首先產品Ⅱ的產量不低于產品Ⅰ的產量；其次充分利用設備有效臺時，不加班；再次利潤不低于56元。列出模型，并求解。第29頁，課件共188頁，創作于2023年2月MinZ=P1d1++P2(d2-+d2+)+P3d3-約束方程：2X1+X2≤11X1-X2+d1--d1+=0X1+2X2+d2--d2+=108X1+10X2+d3--d3+=56X1,X2,di-,di+,

0(i=1,2,3,)

第30頁，課件共188頁，創作于2023年2月1086422x1+x2

11BA△OABO①MinZ=P1d1++P2(d2-+d2+)+P3d3-約束方程：2X1+X2≤11①

X1-X2+d1--d1+=0②

X1+2X2+d2--d2+=10③

8X1+10X2+d3--d3+=56④X1,X2,di-,di+,

0(i=1,2,3,)

246810第31頁，課件共188頁，創作于2023年2月1086422x1+x2

50MinZ=P1d1++P2(d2-+d2+)+P3d3-約束方程：2X1+X2≤11①

X1-X2+d1--d1+=0②

X1+2X2+d2--d2+=10③

8X1+10X2+d3--d3+=56④X1,X2,di-,di+,

0(i=1,2,3,)

d1+d1-BDA△OAB△ODBO①②第32頁，課件共188頁，創作于2023年2月1086422x1+x2

50MinZ=P1d1++P2(d2-+d2+)+P3d3-約束方程：2X1+X2≤11①

X1-X2+d1--d1+=0②

X1+2X2+d2--d2+=10③

8X1+10X2+d3--d3+=56④X1,X2,di-,di+,

0(i=1,2,3,)

d1+d1-d2+BEDA△OAB△ODBDEO①②③d2-246810第33頁，課件共188頁，創作于2023年2月1086422x1+x2

50MinZ=P1d1++P2(d2-+d2+)+P3d3-約束方程：2X1+X2≤11

X1-X2+d1--d1+=0

X1+2X2+d2--d2+=10

8X1+10X2+d3--d3+=56

X1,X2,di-,di+,

0(i=1,2,3,)

2468x110d1+d1-d2+d2-d3+d3-BFEGDJA△OAB△OCBDEDGO第34頁，課件共188頁，創作于2023年2月彩電黑白擁有量裝配線（小時）1140銷量2430利潤（元/件）8040例2：某工廠生產彩電、黑白兩種電視機，數據如下第35頁，課件共188頁，創作于2023年2月解：P1:充分利用裝配線每周計劃開動40小時；X1+X2+d1--d1+=40P2:允許裝配線加班；但加班時間每周盡量不超過10小時；X1+X2+d2--d2+=50P3:電視機的數量盡量滿足市場要求，權系數為利潤比。X1+d3--d3+=24；X2+d4--d4+=30目標函數：MinS=P1d1-+P2d2++

P3(2d3-+d4-)第36頁，課件共188頁，創作于2023年2月MinZ=P1d1-+P2d2++P3（2d3-+d4-）約束方程：X1+X2+d1--d1+=40①X1+X2+d1--d1+=50②X1+d3--d3+=24③X2+d4--d4+=30④X1,X2,di-,di+,

0(i=1,2,3,)

第一：充分利用裝配線每周計劃開動40小時；第二：允許加班，但盡量不超過10小時；第三：電視機要滿足市場要求，彩電權系數取2。第37頁，課件共188頁，創作于2023年2月108642O①MinZ=P1d1-+P2d2++P3（2d3-+d4-）約束方程：X1+X2+d1--d1+=40①X1+X2+d1--d1+=50②X1+d3--d3+=24③X2+d4--d4+=30④X1,X2,di-,di+,

0(i=1,2,3,)

A2468BCDHGEF②③④d1-d1+d2-d2+d3-d3+d4+d4-第38頁，課件共188頁，創作于2023年2月例MinS=d1-X1+2X2+d1--d1+=10X1+2X2

6X1+X2

4X1,X2,d1-,d1+

0第39頁，課件共188頁，創作于2023年2月x1x204681021342X1+2X2

6第40頁，課件共188頁，創作于2023年2月x1x204681021342X1+X2

4第41頁，課件共188頁，創作于2023年2月x1x204681021342第42頁，課件共188頁，創作于2023年2月x1x204681021342第43頁，課件共188頁，創作于2023年2月x1x204681021342x1+2x2=105d1+d1-AB(2,2)X1+2X2

6第44頁，課件共188頁，創作于2023年2月x1x204681021342x1+2x2=105d1+d1-AB(2,2)當MinS=d1-達到時d1-=0X1+2X2

6第45頁，課件共188頁，創作于2023年2月x1x204681021342x1+2x2=105d1-AB(2,2)X1+2X2

6當MinS=d1-達到時d1-=0第46頁，課件共188頁，創作于2023年2月x1x204681021342x1+2x2+d1-=10d1-=45d1-AB(2,2)有無窮多解：點（0，3）和點（2，2）連線上的點都是最優解。(0,3)第47頁，課件共188頁，創作于2023年2月（1）目標函數求最小化，檢驗數大于等于0為最優準則；（2）非基變量的檢驗數中含有不同等級的優先因子，即cj-zj=∑akjPk,j=1,2,…,n;k=1,2,…,K因P1》P2》…》Pk,從整體來看：檢驗數的正負首先取決于Pi的系數aij的正負。若a1j=0，這時檢驗數的正負取決于P2的系數a2j的正負，下面依次類推。目標規劃的單純形法第48頁，課件共188頁，創作于2023年2月目標規劃的單純形法例：用單純形法求解目標規劃問題第49頁，課件共188頁，創作于2023年2月X2換入，

d2-

換出表1

CjP1P2P2P3CBXBbX1X2XSd1-d1+d2-d2+d3-d3+Xs

11d1-0P2d2-

10P3d3-5621181-1[2]1011

-11-11-110/2

P1Cj–zjP2

P3-1-8-2-10121第50頁，課件共188頁，創作于2023年2月

CjP1P2P2P3CBXBbX1X2XSd1-d1+d2-d2+d3-d3+Xs

6d1-5

X2

5P3d3-63/23/21/2[3]

1

11-1-1/21/21/2-51/2-1/2-1/25

1-16/3

P1Cj–zjP2

P3-31151-51X1換入，

d3-

換出表2第51頁，課件共188頁，創作于2023年2月

CjP1P2P2P3CBXBbX1X2XSd1-d1+d2-d2+d3-d3+Xs

3d1-2

X2

4P3X1

23242

1

111234/3-5/3-2-3-4/35/3-1/2-1/2-1/61/31/21/21/6-1/3

P1Cj–zjP2

P311

11

非基變量

d3+檢驗數為0，有無窮多最優解表3第52頁，課件共188頁，創作于2023年2月

CjP1P2P2P3CBXBbX1X2XSd1-d1+d2-d2+d3-d3+Xs

1d3+4

X2

10/3X110/3

1

1

1

-12-1/32/31-21/3-2/3-161/31/31-6-1/3-1/3-11

P1Cj–zjP2

P311

11

d3+換入，d1-換出第53頁，課件共188頁，創作于2023年2月4目標規劃的靈敏度分析例：已知目標規劃問題用單純形法得到的最終標為表4-5第54頁，課件共188頁，創作于2023年2月表4-5目標函數的優先等級變化為：原問題的目標函數第55頁，課件共188頁，創作于2023年2月目標函數的優先等級變化為：分析原最優解有什么變化。解：分析（1）相當于檢驗數中第二行與第三行互換。檢驗數仍為非負，最優解不變。分析（2）相當于檢驗數中第一行與第二行互換。有檢驗數為負，最優解變化了。原問題的目標函數第56頁，課件共188頁，創作于2023年2月第57頁，課件共188頁，創作于2023年2月第58頁，課件共188頁，創作于2023年2月例:某單位領導在考慮本單位職工的升級調資方案時,依次遵守以下規定:(1)不超過月工資總額60000元;(2)每級人數不超過定編規定的人數;(3)Ⅱ、Ⅲ級的升級面盡可能達到現有人數的20%；(4)Ⅲ級不足的人數可錄用新職工,又Ⅰ級的職工中有10%要退休.相關資料如下表:第59頁，課件共188頁，創作于2023年2月等級工資額(元/月)現有人數編制人數ⅠⅡⅢ2000150010001012151215153742第60頁，課件共188頁，創作于2023年2月解:設x1,x2,x3分別表示提升到Ⅰ、Ⅱ級和錄用新職工的人數.P1:不超過月工資總額60000元;P2:每級人數不超過定編規定的人數;P3:Ⅱ、Ⅲ級的升級面盡可能達到現有人數的20%調整以后各級的人數為:Ⅰ級:10-10×10%+x1Ⅱ級:12-x1+x2Ⅲ級:15-x2+x3第61頁，課件共188頁，創作于2023年2月分析:P1:不超過月工資總額60000元,P1d1+2000(10-10×10%+x1)+1500(12-x1+x2)+1000(15-x2+x3)+d1--d1+=60000P2:每級人數不超過定編規定的人數,P2(d2++d3++d4+)Ⅰ級:10-10×10%+x1+d2--d2+=12Ⅱ級:12-x1+x2+d3--d3+=15Ⅲ級:15-x2+x3+d4--d4+=15第62頁，課件共188頁，創作于2023年2月P3:Ⅱ、Ⅲ級的升級面盡可能達到現有人數的20%,P3(d5-+d6-)Ⅱ級:x1+d5–d5+=12×20%Ⅲ級:x2+d6–d6+=15×20%第63頁，課件共188頁，創作于2023年2月數學模型為:Minz=P1d1++P2(d2++d3++d4+)+P3(d5-+d6-)2000(10-10×10%+x1)+1500(12-x1+x2)+1000(15-x2+x3)+d1--d1+=6000010-10×10%+x1+d2--d2+=1212-x1+x2+d3--d3+=1515-x2+x3+d4--d4+=15x1+d5–d5+=12×20%x2+d6–d6+=15×20%X1,x2,x3≥0,di--di+≥0,i=1,2,3,4,5,6第64頁，課件共188頁，創作于2023年2月例3:已知三個產地給四個銷地供應某種產品,供需量與單位運價表如下表:

銷地產地B1B2B3B4產量A15

2

6

7

300A23

5

4

6

200A3452

3

400銷量

2001004502509001000第65頁，課件共188頁，創作于2023年2月考慮調運方案時,依次考慮以下七項指標:P1:B4是重點保護單位必須全部滿足其要求;P2:A3向B1提供的產量不少于100;P3:每個銷地的供應量不小于需要量的80%;P4:所訂調運方案的總費用不超過最小調運方案的10%;P5:因路段的問題,盡量避免安排A2運往B4;P6:給B1和B3的供應率要相同;P7:力求總運費最省;試求滿意的調運方案第66頁，課件共188頁，創作于2023年2月解:由于產量小于銷量,假想一個產地A4,其產量為100.用表上作業法求得最優表如下,最小運費為2950元.

銷地產地B1B2B3B4產量A1200

100

300A20

200

200A3A4250

150

100400100銷量200100450250

第67頁，課件共188頁，創作于2023年2月分析:供應約束:x11+x12+x13+x14≤300x21+x22+x23+x24≤200x31+x32+x33+x34≤400需求約束:x11+x21+x31+d1--d1+=200x12+x22+x32+d2--d2+=100x13+x23+x33+d3--d3+=450

x14+x24+x34+d4--d4+=250P1:

B4是重點保護單位必須全部滿足其要求,P1d4-P2:A3向B1提供的產量不少于100,P2d5-x31+d5--d5+=100第68頁，課件共188頁，創作于2023年2月分析:P3:每個銷地的供應量不小于需要量的80%,

P3(d6-+d7-+d8-+d9-)x11+x21+x31+d6--d6+=200×0.8x12+x22+x32+d7--d7+=100×0.8x13+x23+x33+d8--d8+=450×0.8

x14+x24+x34+d9--d9+=250×0.8P4:所訂調運方案的總費用不超過最小調運方案的10%,P4d10+第69頁，課件共188頁，創作于2023年2月分析:

P5:因路段的問題,盡量避免安排A2運往B4,P5d11+x24+d11--d11+=0P6:給B1和B3的供應率要相同,P6(d12-+d11+)供應率=實際供應量/銷量,即:(x11+x21+x31)/200=(x13+x23+x33)/450,目標約束為:(x11+x21+x31)-(200/450)(x13+x23+x33)+d12--d12+=0P7:力求總運費最省,P7d13+第70頁，課件共188頁，創作于2023年2月

供應約束:x11+x12+x13+x14≤300x21+x22+x23+x24≤200x31+x32+x33+x34≤400需求約束:x11+x21+x31+d1--d1+=200x12+x22+x32+d2--d2+=100x13+x23+x33+d3--d3+=450P1

x14+x24+x34+d4--d4+=250P2x31+d5--d5+=100

第71頁，課件共188頁，創作于2023年2月P4x11+x21+x31+d6--d6+=200×0.8x12+x22+x32+d7--d7+=100×0.8x13+x23+x33+d8--d8+=450×0.8

x14+x24+x34+d9--d9+=250×0.8P5x24+d11--d11+=0P6(x11+x21+x31)-(200/450)(x13+x23+x33)+d12--d12+=0P7Minz=P1d4-+P2d5-+P3(d6-+d7+-+d8-+d9-)+P4d10++P5d11++P6(d12-+d11+)+P7d13+第72頁，課件共188頁，創作于2023年2月例：友誼農場有3萬畝農田欲種植玉米、大豆和小麥三種農作物，各種作物每畝需施化肥分別為0.12噸、0.20噸、0.15噸。預計秋后玉米每畝可收獲500千克，售價為0.24元/千克,大豆每畝可收獲200千克,售價為1.20元/千克,小麥每畝可收獲300千克,售價為0.70元/千克.農場年初規劃時考慮如下幾個方面::年終收益不低于350萬元;:總產量不低于1.25萬噸;:小麥產量以0.5萬噸為宜;:大豆產量不少于0.2萬噸;:玉米產量不超過0.6萬噸;:農場現能提供5000噸化肥;若不夠,可在市場高價購買,但希望高價采購愈少愈好.試就該農場生產計劃建立數學模型(不用求解).

第73頁，課件共188頁，創作于2023年2月玉米大豆小麥化肥噸/畝0.120.200.15收獲千克/畝500200300售價元/千克0.241.200.70第74頁，課件共188頁，創作于2023年2月解:設種植玉米、大豆和小麥三種農作物各為畝,該問題的數學模型為:第75頁，課件共188頁，創作于2023年2月第五章整數規劃

本章要求

理解整數規劃的含義

掌握分枝定界法的思想和方法

掌握0-1變量的含義和用法

掌握指派問題的算法

第76頁，課件共188頁，創作于2023年2月5.1整數規劃問題的提出決策問題中經常有整數要求，如人數、件數、機器臺數、貨物箱數……如何解決？四舍五入不行，枚舉法太慢問題分類：純整數規劃、混合整數規劃、0-1整數規劃專門方法：分枝定界法、割平面法、隱枚舉法、匈牙利法第77頁，課件共188頁，創作于2023年2月

整數規劃是數學規劃一個較弱的分支，目前只能解中等規模的線性整數規劃問題，而非線性整數規劃問題，還沒有好的辦法。問題舉例第78頁，課件共188頁，創作于2023年2月例1:某集裝箱運輸公司，箱型標準體積24m3，重量13T,現有兩種貨物可以裝運，甲貨物體積5m3、重量2T、每件利潤2000元；乙貨物體積4m3、重量5T、每件利潤1000元，如何裝運獲利最多？maxZ=2000x1+1000x25x1+4x2≤24①2x1+5x2

≤13②x1,x2≥0且為整數解此LP問題，得：x1=4.8，x2=0,z=96顯然不是可行解第79頁，課件共188頁，創作于2023年2月第80頁，課件共188頁，創作于2023年2月整數規劃圖解法x11234567BAx2maxZ=2000x1+1000x25x1+4x2≤242x1+5x2

≤13x1,x2≥0且為整數x1=4.8，x2=0,z=96①②①②第81頁，課件共188頁，創作于2023年2月先放棄變量的整數性要求，解一個線性規劃問題，最優解為x1=4.8，x2=0。然后用“四舍五入”法取整數解，這種方法，只有在變量的取值很大時，才有成功的可能性，而當變量的取值較小時，特別是0-1規劃時，往往不能成功。x1=5，x2=0不是可行解,因為不滿足5x1+4x2≤24x1=4，x2=0,z=80x1=4，x2=1是可行解,z=90maxZ=2000x1+1000x25x1+4x2≤242x1+5x2

≤13x1,x2≥0且為整數第82頁，課件共188頁，創作于2023年2月圖解法的啟示A（4.8，0）點是LP問題的可行解，不是IP問題的可行解，B（4，1）才是IP的最優解純整數規劃的可行解就是可行域中的整數點非整數點不是可行解，對于求解沒有意義，故切割掉可行域中的非可行解，不妨礙整數規劃問題的優化IP問題的最優解不優于LP問題的最優解第83頁，課件共188頁，創作于2023年2月例2：一登山隊員做登山準備，他需要攜帶的物品有：食品，氧氣，冰鎬，繩索，帳篷，照相機和通訊設備，每種物品的重要性系數和重量如下：假定登山隊員可攜帶最大重量為31公斤。序號1234567物品食品氧氣冰鎬繩索帳篷相機設備重量55261224重要系數201518141048第84頁，課件共188頁，創作于2023年2月解：如果令xi=1表示登山隊員攜帶物品i，xi=0表示登山隊員不攜帶物品i，則問題表示成0-1規劃:MaxZ=20x1+15x2+18x3+14x4

+8x5+4x6+10x7s.t.5x1+5x2+2x3+6x4+12x5+2x6

+4x7

25xi=1或xi=0i=1,2,….7第85頁，課件共188頁，創作于2023年2月數學模型整數規劃(IP)的一般數學模型:Max(min)Z=Σcjxjs.t.Σaijxj

bi(i=1,2,…m)xj

0且部分或全部是整數第86頁，課件共188頁，創作于2023年2月解法概述當人們開始接觸整數規劃問題時，常會有如下兩種初始想法：因為可行方案數目有限，因此經過一一比較后，總能求出最好方案，例如，背包問題充其量有2n種方式；指派問題充其量有n!種方式；實際上這種方法是不可行。第87頁，課件共188頁，創作于2023年2月設想計算機每秒能比較1000000個方式，那么要比較完20!（大于2*1018）種方式，大約需要800年。比較完260種方式，大約需要360世紀。第88頁，課件共188頁，創作于2023年2月例求下列問題：MaxZ=3x1+13x2s.t.2x1+9x2

4011x1-8x2

82x1,x2

0,且取整數值第89頁，課件共188頁，創作于2023年2月O12345678910x1x2I(2,4)B(9.2,2.4)AD可行域OABD內整數點，放棄整數要求后，最優解B(9.2,2.4)

Z0=58.8，而原整數規劃最優解I(2,4)

Z0=58，實際上B附近四個整點(9,2)(10,2)(9,3)(10,3)都不是原規劃最優解。第90頁，課件共188頁，創作于2023年2月x2I(2,4)B(9.2,2.4)假如能求出可行域的“整點凸包”（包含所有整點的最小多邊形(OEFGHIJ），則可在此凸包上求線性規劃的解，即為原問題的解。但求“整點凸包”十分困難。FGHIJ第91頁，課件共188頁，創作于2023年2月x2I(2,4)B(9.2,2.4)假如把可行域分解成五個互不相交的子問題P1P2P3之和,,而放棄整數要求后P1最優解I(2,4),Z1=58P2最優解(6,3),Z2=57

P3最優解(98/11,2),Z4=52(8/11)

P1P2P3第92頁，課件共188頁，創作于2023年2月2分枝定界解法（BranchandBoundMethod)原問題的松馳問題：任何整數規劃（IP），凡放棄某些約束條件（如整數要求）后，所得到的問題（P）都稱為（IP）的松馳問題。第93頁，課件共188頁，創作于2023年2月

最通常的松馳問題是放棄變量的整數性要求后，（IP）為線性規劃問題。*整數規劃的解集是其對應的線性規劃解集的子集。

*整數規劃求最大化時，線性規劃的最優解是其解的上界。*整數規劃求最小化時，線性規劃的最優解是其解的下界。第94頁，課件共188頁，創作于2023年2月分枝定界法步驟一般求解對應的松馳問題，可能會出現下面幾種情況：若所得的最優解的各分量恰好是整數，則這個解也是原整數規劃的最優解，計算結束。若松馳問題無可行解，則原整數規劃問題也無可行解，計算結束。第95頁，課件共188頁，創作于2023年2月若松馳問題有最優解，但其各分量不全是整數，則這個解不是原整數規劃的最優解，轉下一步。從不滿足整數條件的基變量中任選一個xl進行分枝，它必須滿足xl

[xl]或xl

[xl]+1中的一個，把這兩個約束條件加進原問題中，形成兩個互不相容的子問題（兩分法）。第96頁，課件共188頁，創作于2023年2月定界：把滿足整數條件各分枝的最優目標函數值作為上（下）界，用它來判斷分枝是保留還是剪枝。剪枝：把那些子問題的最優值與界值比較，凡不優或不能更優的分枝全剪掉，直到每個分枝都查清為止。第97頁，課件共188頁，創作于2023年2月例5-6用分枝定界法求解：MaxZ=4x1+3x2s.t.

3x1+4x2

124x1+2x2

9x1,x2

0整數用單純形法可解得相應的松馳問題的最優解（6/5，21/10）Z=111/10為各分枝的上界。第98頁，課件共188頁，創作于2023年2月012344321x1x2分枝：X1

1,x1

2P1P2MaxZ=4x1+3x2s.t.

3x1+4x2

124x1+2x2

9x1,x2

0整數最優解（6/5，21/10）3x1+4x2

124x1+2x2

9第99頁，課件共188頁，創作于2023年2月兩個子問題：（P1）MaxZ=4x1+3x2s.t.

3x1+4x2

124x1+2x2

9x1,x2

0，x1

1，整數用單純形法可解得相應的（P1）的最優解（1，9/4）Z=10(3/4)第100頁，課件共188頁，創作于2023年2月（P2）MaxZ=4x1+3x2s.t.

3x1+4x2

124x1+2x2

9x1,x2

0，x1

2，整數用單純形法可解得相應的（P2）的最優解（2，1/2）Z=9(1/2)第101頁，課件共188頁，創作于2023年2月012344321x1x2再對（P1）分枝：X1

1（P3）x2

2（P4）x2

3P1P2P3P4第102頁，課件共188頁，創作于2023年2月（P1）兩個子問題：（P3）MaxZ=4x1+3x2s.t.

3x1+4x2

124x1+2x2

9x1,x2

0,x1

1,x2

2整數用單純形法可解得相應的（P3）的最優解（1，2）Z=10第103頁，課件共188頁，創作于2023年2月X1

2X2

2X1

1X2

3P1:(1,9/4)Z=10(3/4)P4:(0,3)Z=9P2:(2,1/2)Z=9(1/2)P3:(1,2)Z=10P:(6/5,21/10)Z=111/10原問題的最優解（1，2）Z=10第104頁，課件共188頁，創作于2023年2月例5-7用分枝定界法求解：MinZ=x1+4x2s.t.

2x1+x2

8x1+2x2

6x1,x2

0整數用單純形法可解得相應的松馳問題的最優解（10/3，4/3）Z=26/3為各分枝的下界。第105頁，課件共188頁，創作于2023年2月

0123456

87654321x1x2pMinZ=x1+4x2s.t.

2x1+x2

8x1+2x2

6x1,x2

0整數最優解（10/3，4/3）Z=26/32x1+x2

8

x1+2x2

6

第106頁，課件共188頁，創作于2023年2月

0123456

87654321x1x2p選x1進行分枝：(P1)x1

3(P2)

x1

4為空集P1（P1）MinZ=x1+4x2s.t.

2x1+x2

8x1+2x2

6x1,x2

0x1

3整數用單純形法可解得（P1）的最優解（3，3/2）Z=9第107頁，課件共188頁，創作于2023年2月（P1）MinZ=x1+4x2s.t.

2x1+x2

8x1+2x2

6x1,x2

0x1

3整數用單純形法可解得（P1）的最優解（3，3/2）Z=9第108頁，課件共188頁，創作于2023年2月（P2）MinZ=x1+4x2s.t.

2x1+x2

8x1+2x2

6x1,x2

0x1

4整數無可行解。第109頁，課件共188頁，創作于2023年2月

0123456

87654321x1x2pP4（P3）MinZ=x1+4x2s.t.

2x1+x2

8x1+2x2

6x1,x2

0，x1

3，x2

1整數無可行解。（P4）MinZ=x1+4x2s.t.

2x1+x2

8x1+2x2

6x1,x2

0，x1

3，x2

2整數用單純形法可解得（P4）的最優解（2，2）Z=10第110頁，課件共188頁，創作于2023年2月（P3）MinZ=x1+4x2s.t.

2x1+x2

8x1+2x2

6x1,x2

0，x1

3，x2

1整數無可行解。第111頁，課件共188頁，創作于2023年2月（P4）MinZ=x1+4x2s.t.

2x1+x2

8x1+2x2

6x1,x2

0，x1

3，x2

2整數用單純形法可解得（P4）的最優解（2，2）Z=10第112頁，課件共188頁，創作于2023年2月X1

4X2

1X13X2

2P1:(3,3/2)Z=9P4:(2,2)Z=10P2:無可行解P3:無可行解P:(10/3,4/3)Z=26/3原問題的最優解（2，2）Z=10第113頁，課件共188頁，創作于2023年2月例：求解MaxZ=40x1+90x2s.t.

9x1+7x2

567x1+20x2

56x1,x2

0且為整數第114頁，課件共188頁，創作于2023年2月MaxZ=40x1+90x2s.t.

9x1+7x2

567x1+20x2

70(B)x1,x2

0且為整數最優解x1,=4.81,x2=1.82

z=35687654321x1x2

0123456789109x1+7x2

567x1+20x2

70第115頁，課件共188頁，創作于2023年2月87654321x1x2

0123456789109x1+7x2

56問題（B）x1,=4.81,x2=1.82

z=356P1P2問題（B1）x1,=4,x2=2.1

z=349問題（B2）x1,=5,x2=1.57z=341x14x2

5第116頁，課件共188頁，創作于2023年2月87654321x1x2

0123456789109x1+7x2

56問題（B）x1,=4.81,x2=1.82

z=356P3P2P4問題（B1）x1,=4,x2=2.1

P1z=349問題（B2）x1,=5,x2=1.57P2z=341x14x1

5x22x2

3第117頁，課件共188頁，創作于2023年2月87654321x1x2

0123456789109x1+7x2

56問題（B）x1,=4.81,x2=1.82

z=356P3P2P4問題（B1）x1,=4,x2=2.1

P1z=349問題（B2）x1,=5,x2=1.57P2z=341問題（B3）x1,=4,x2=2

P3z=340問題（B4）x1,=1.42,x2=3

P4z=327x14x1

5x22x2

3第118頁，課件共188頁，創作于2023年2月87654321x1x2

0123456789109x1+7x2

56問題（B）x1,=4.81,x2=1.82

z=356P3P2P4問題（B1）x1,=4,x2=2.1

P1z=349問題（B2）x1,=5,x2=1.57P2z=341問題（B3）x1,=4,x2=2

P3z=340問題（B4）x1,=1.42,x2=3

P4z=327x14x1

5x21x2

3x22x2

2x1x2

0123456789109x1+7x2

56問題（B）x1,=4.81,x2=1.82

z=356P3P2P4問題（B1）x1,=4,x2=2.1

P1z=349問題（B2）x1,=5,x2=1.57P2z=341問題（B3）x1,=4,x2=2

P3z=340問題（B4）x1,=1.42,x2=3

P4z=327x14x1

5x2

3第119頁，課件共188頁，創作于2023年2