復(fù)習(xí)題.1.用單純形法求解下列規(guī)劃問(wèn)題Max

Z=5x1+2x2+3x3-x4

x1+2x2+3x3=152x1+x2+5x3=20

x1+2x2+4x3+x4=26

x1,x2,x3,x4≥0.2.已知運(yùn)輸問(wèn)題的供需關(guān)系表與運(yùn)價(jià)表,

試用表上作業(yè)法求最優(yōu)解

銷地產(chǎn)地甲乙丙丁產(chǎn)量132765027523603254525銷量60402015.3.某鉆井隊(duì)要從以下10個(gè)可供選擇的井位中確定5個(gè)鉆井探油,使得總的鉆探費(fèi)用為最小。若10個(gè)井位的代號(hào)為s1，s2，…s10，相應(yīng)的鉆探費(fèi)用為c1，c2，…，c10，并且井位選擇上要滿足下列限制條件：①或選擇s1和s7，或選擇鉆探s8；②選擇了s3或s4就不選s5，反之亦然；③在s5，s6，s7，s8中最多只能擇兩個(gè)；試建立這個(gè)問(wèn)題的整數(shù)規(guī)劃模型。.4．某彩色電視機(jī)組裝廠，生產(chǎn)A，B，C三種規(guī)格的電視機(jī)。裝配工作在同一生產(chǎn)線上完成，三種產(chǎn)品裝配時(shí)的工時(shí)消耗分別為6小時(shí)，8小時(shí)和10小時(shí)。生產(chǎn)線每月正常工作時(shí)間為200小時(shí)；三種規(guī)格電視機(jī)銷售后，每臺(tái)可獲利分別為500元，650元和800元。每月銷量預(yù)計(jì)為12臺(tái)，10臺(tái)，6臺(tái)。該廠經(jīng)營(yíng)目標(biāo)如下：P1:利潤(rùn)指標(biāo)定為每月16000元；P2:充分利用生產(chǎn)能力；P3:加班時(shí)間不超過(guò)24小時(shí)；P4:產(chǎn)量以預(yù)計(jì)銷量為標(biāo)準(zhǔn)；為確定生產(chǎn)計(jì)劃,試建立該問(wèn)題的目標(biāo)規(guī)劃模型。.5.用求V1至V6的最短距離與最短路徑139181071219125V1V2V3V5V4V6.6.用標(biāo)號(hào)算法,求V1至V6的最大流(14,8)(10,9)(10,2)(15,10)(6,6)(15,1)(8,3)(5,0)V1V2V3V5V4V6(18,16).1.用單純形法求解下列規(guī)劃問(wèn)題解:令于是原線性規(guī)劃問(wèn)題變?yōu)闃?biāo)準(zhǔn)形式：.迭代次數(shù)基CBx1x2x3x4b比值-3-1-1-10x3-1-221042x4-1310166zj-1-3-1-1j=

cj-zj-22001x2-1-111/202-x4-140-1/2141zj-3-10-1j=

cj-zj00-102x2-1013/81/43-x1-310-1/81/411zj100-1j=

cj-zj00-10.最優(yōu)解為：最優(yōu)值為：.Max

Z=5x1+2x2+3x3-x4-M

x5-Mx6

x1+2x2+3x3+x5

=152x1+x2+5x3+x6=20

x1+2x2+4x3+x4=26

x1,x2,x3,x4,x5,x6

≥0Max

Z=5x1+2x2+3x3-x4

x1+2x2+3x3=152x1+x2+5x3=20

x1+2x2+4x3+x4=26

x1,x2,x3,x4≥0.

基CBx1x2x3x4x5x6b比值523-1-M-Mx5-M123010155x6-M21(5)001204x4-1124100266.5j3M+63M+48M+700035M+26x5-M-1/57/5001-3/5315/7x332/51/51001/5420x4-1-3/56/5010-4/51025/3j-M/5+16/57/5M+13/5000-8/5M-7/53M-2x22-1/71005/7-3/715/7－x33(3/7)010-1/72/725/725/3x4-1-3/7001-6/7-2/752/7－j25/7000-M-13/7-M-2/7-53/7x22011/302/3-1/310/3x15107/30-1/32/325/3x4-10011-1011j00-25/30-M-2/3-M+8/3-112/3.得到最優(yōu)解：(25/3，10/3，0，11)T，最優(yōu)目標(biāo)值：112/3Max

Z=5x1+2x2+3x3-x4

x1+2x2+3x3=152x1+x2+5x3=20

x1+2x2+4x3+x4=26

x1,x2,x3,x4≥0.2已知運(yùn)輸問(wèn)題的供需關(guān)系表與運(yùn)價(jià)表,

試用表上作業(yè)法求最優(yōu)解

銷地產(chǎn)地甲乙丙丁產(chǎn)量132765027523603254525銷量60402015.銷地產(chǎn)地甲乙丙丁產(chǎn)量132765010409

7275236025-12015325452525

477銷量60402015135135解:(1)以最小元素法確定初始基本可行解

并以閉回路法判別.銷地產(chǎn)地甲乙丙丁產(chǎn)量13276501001040972752360402525-120153254525025477銷量6025400200150135135解:(1)以最小元素法確定初始基本可行解

并以閉回路法判別.銷地產(chǎn)地甲乙丙丁產(chǎn)量132765035158

627523601252015325452525466銷量60402015135135解:(2)以閉回路法調(diào)整,并判別由于所有檢驗(yàn)數(shù)均大于等于零,此解是最優(yōu)解..3.某鉆井隊(duì)要從以下10個(gè)可供選擇的井位中確定5個(gè)鉆井探油,使得總的鉆探費(fèi)用為最小。若10個(gè)井位的代號(hào)為s1，s2，…s10，相應(yīng)的鉆探費(fèi)用為c1，c2，…，c10，并且井位選擇上要滿足下列限制條件：①或選擇s1和s7，或選擇鉆探s8；②選擇了s3或s4就不選s5，反之亦然；③在s5，s6，s7，s8中最多只能擇兩個(gè)；試建立這個(gè)問(wèn)題的整數(shù)規(guī)劃模型。.3.解:設(shè)0-1變量,該問(wèn)題的整數(shù)規(guī)劃模型為:x1＋x8=1x3＋x5≤1x7＋x8=1x4＋x5≤1x5＋x6＋

x7＋x8≤2xi≥0,且xi為0-1變量,(i=1,2…,10)

.4．某彩色電視機(jī)組裝廠，生產(chǎn)A，B，C三種規(guī)格的電視機(jī)。裝配工作在同一生產(chǎn)線上完成，三種產(chǎn)品裝配時(shí)的工時(shí)消耗分別為6小時(shí)，8小時(shí)和10小時(shí)。生產(chǎn)線每月正常工作時(shí)間為200小時(shí)；三種規(guī)格電視機(jī)銷售后，每臺(tái)可獲利分別為500元，650元和800元。每月銷量預(yù)計(jì)為12臺(tái)，10臺(tái)，6臺(tái)。該廠經(jīng)營(yíng)目標(biāo)如下：P1:利潤(rùn)指標(biāo)定為每月16000元；P2:充分利用生產(chǎn)能力；P3:加班時(shí)間不超過(guò)24小時(shí)；P4:產(chǎn)量以預(yù)計(jì)銷量為標(biāo)準(zhǔn)；為確定生產(chǎn)計(jì)劃,試建立該問(wèn)題的目標(biāo)規(guī)劃模型。.4.解:設(shè)生產(chǎn)A型電視機(jī)x1臺(tái)，B型電視機(jī)x2臺(tái)，C型電視機(jī)x3臺(tái),該問(wèn)題的目標(biāo)規(guī)劃模型為:Minz=P1（d1-）+P2（d2-）+P3（d3+）+P4（d4++

d4-+

d5++

d5-+

d6++

d6-）

500x1＋650x2＋800x3-d1++d1-

=160006x1＋8x2＋10x3–d2++d2-

=2006x1＋8x2＋10x3–d3++d3-

=224x1-d4++d4-=12x2-d5++d5-=10x3-d6++d6-=6x1,x2,x3≥0;di+,di-≥0(i=1,2…,6).5.解:139181071219125V1(0,s)V2(13,1)V3(9,1)V5(21,3)V4(23,2)V6(35,4).１.給出點(diǎn)V1以標(biāo)號(hào)(0，s)2.s12=l1+c12=0+13=13s13=l1+c13=0+9=9MIN(s12,

s13)=

s13=9

給出點(diǎn)V3以標(biāo)號(hào)(9，1)3.s12=l1+c12=0+13=13s34=l3+c34=9+18=27s35=l3+c35=9+12=21MIN(s12,

s34,

s35)=

s12=13

給出點(diǎn)V2以標(biāo)號(hào)(13，1)4.s24=l2+c24=13+10=23s34=l3+c34=9+18=27s35=l3+c35=9+12=21MIN(s24,

s34,

s35)=

s35=21

給出點(diǎn)V5以標(biāo)號(hào)(21，3)5.s24=l2+c24=13+10=23s56=l5+c56=21+19=40MIN(s24,

s56)=

s24=23

給出點(diǎn)V4以標(biāo)號(hào)(23，2)6.s46=l4+c46=23+12=35s56=l5+c56=21+19=40MIN(s46,

s56)=

s46=35

給出點(diǎn)V6以標(biāo)號(hào)(35，4)7.計(jì)算結(jié)束,得到最短路

V1至V6的最短距離為35最短路徑為V1->V2->V4->V6.6.解(1)通過(guò)標(biāo)號(hào)求尋找可增廣鏈V1->V2->V4->V6(14,8)(10,9)(10,2)(15,10)(6,6)(15,1)(8,3)(5,0)V1V2V3V5V4V6(18,16)[△，+∞][+V1，1

][+V1，6

][+V2，5

][-V2，2

][+V4，2

].6.解(2)調(diào)整值為2(14,10)(10,9)(10,2)(15,12)(6,6)(15,1)(8,3)(5,0)V1V2V3V5V4V6(18,18).6.解(3)再通過(guò)標(biāo)號(hào)求尋找可增廣鏈V1->V2->V5->V6(14,10)(10,9)(10,2)(15,12)(6,6)(15,1)(8,3)(5,0)V1V2V3V5V4V6(18,18)[△，+∞][+V1，4

][+V1，1

][+V2，3

][-V2，2

][+V5，2

].6.解(4)調(diào)整值為2(14,12)(10,9)(10,0)(15,12)(6,6)(15,3