運籌學復習題

復習題.1.用單純形法求解下列規(guī)劃問題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è)法求最優(yōu)解

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

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

.4．某彩色電視機組裝廠，生產(chǎn)A，B，C三種規(guī)格的電視機。裝配工作在同一生產(chǎn)線上完成，三種產(chǎn)品裝配時的工時消耗分別為6小時，8小時和10小時。生產(chǎn)線每月正常工作時間為200小時；三種規(guī)格電視機銷售后，每臺可獲利分別為500元，650元和800元。每月銷量預計為12臺，10臺，6臺。該廠經(jīng)營目標如下：P1:利潤指標定為每月16000元；P2:充分利用生產(chǎn)能力；P3:加班時間不超過24小時；P4:產(chǎn)量以預計銷量為標準；為確定生產(chǎn)計劃,試建立該問題的目標規(guī)劃模型。.4.解:設生產(chǎn)A型電視機x1臺，B型電視機x2臺，C型電視機x3臺,該問題的目標規(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).１.給出點V1以標號(0，s)2.s12=l1+c12=0+13=13s13=l1+c13=0+9=9MIN(s12,

s13)=

s13=9

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

s34,

s35)=

s12=13

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

s34,

s35)=

s35=21

給出點V5以標號(21，3)5.s24=l2+c24=13+10=23s56=l5+c56=21+19=40MIN(s24,

s56)=

s24=23

給出點V4以標號(23，2)6.s46=l4+c46=23+12=35s56=l5+c56=21+19=40MIN(s46,

s56)=

s46=35

給出點V6以標號(35，4)7.計算結(jié)束,得到最短路

V1至V6的最短距離為35最短路徑為V1->V2->V4->V6.6.解(1)通過標號求尋找可增廣鏈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)再通過標號求尋找可增廣鏈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