1、第 2 章整數(shù)規(guī)劃習(xí)題解答2.1解 做變量替換 y x1 x2 ，則有如下關(guān)系x1 x2 1 y x1 ， x1 x2 1 y x2 ，從而可以得到如下的線性0 1規(guī)劃maxz x1 y x3 ， 23 3,x x 1 y x ,121s.t. x1 x2 1 y x2 ,x 0或1， ( j 1,2,3),j y 0或1.2.2解 令 1,在備選校址Bi 建學(xué)校,xi0,在備選校址Bi 不建學(xué)校，由于小區(qū) A1 可以被備選校址 B1 ，B2 ，B3 處所建的學(xué)校覆蓋，則有約束條件3 1，類似地，可以寫(xiě)出其它的約束條件，建立如下的 0-1 整數(shù)規(guī)劃模型6 xii 1min3 1,x x 1,2

2、4x3 x5 1,x x 146s.t. 1,35 6 1, x x 1246計(jì)算的 Lingo 程序如下m:sets: var/1.6/:x; endsetsmin=sum(var:x); x(1)+x(2)+x(3)1;-7-x(2)+x(4)1;x(3)+x(5)1;x(4)+x(6)1;x(5)+x(6)1; x(1)1; x(2)+x(4)+x(6)1;end求得在備選校址 B1 ， B4 ， B5 建小學(xué)。2.3 解 用 j 1,2,3,4 分別表示甲、乙、丙、丁四個(gè)企業(yè)， cij 表示第i （ i 1,6 ）臺(tái)設(shè)備分配給第 j 個(gè)企業(yè)創(chuàng)造的利潤(rùn)，引進(jìn)0 1 變量1,第i臺(tái)設(shè)備分配

3、給第j個(gè)企業(yè) ， i 1,6 ， j 1,2,3,4xij0,第i臺(tái)設(shè)備不分配給第j個(gè)企業(yè)則問(wèn)題的數(shù)學(xué)模型為max cij xiji1 j 1646x 1,j 1,2,3,4ij i14 xij 1,i 1,6s.t. j 1x 0或1， i 1,6;j 1,2,3,4ij計(jì)算的 Lingo 程序如下:msets:shebei/1.6/; qiye/1.4/; link(shebei,qiye):c,x; endsetsdata:c=4 23456666;677774567889810 8enddatamax=sum(link:c*x);for(qiye(j):sum(shebei(i):x(

4、i,j)1);for(shebei(i):sum(qiye(j):x(i,j)=1); for(link:bin(x);end求得 x14 1， x21 1， x31 1， x43 1 ， x52 1 ， x62 1 。最大利潤(rùn)為44。2.4 解 問(wèn)題（1）-8-記i 1,2,3,4 分別表示高低杠，平衡木，跳馬，體操四項(xiàng)運(yùn)動(dòng)。引進(jìn)決策變量 1,第j個(gè)人參加第i個(gè)項(xiàng)目， i 1,2,3,4 ， j 1,2,10 xij0， 第j個(gè)人不參加第i個(gè)項(xiàng)目cij 表示在某種情形下第 j 個(gè)人參加第i 個(gè)項(xiàng)目的得分建立如下的非線性整數(shù)規(guī)劃模型max cij xiji1 j14 1010 x 6， i 1

5、,2,3,4ij j1 10s.t.4 ij 4x j1 i1總的得分為 212.3。使用計(jì)算機(jī)進(jìn)行計(jì)算時(shí)，首先構(gòu)造純文本文件sj.txt，把原始的4個(gè)項(xiàng)目，10個(gè)人的數(shù)據(jù)放在純文件中，然后把分?jǐn)?shù)和概率之間的符號(hào)“”替換成空格，具體數(shù)據(jù)格式如下：8.49.59.29.48.48.89.0109.19.39.59.88.78.99.19.90.15 9.3 0.10.5 9.5 0.10.25 9.6 0.68.48.89.0108.19.19.39.58.49.59.29.49.59.79.80.10.20.60.10.10.50.30.10.150.50.250.10.10.10.68.19

6、.19.39.58.78.99.19.99.09.49.59.78.48.89.00.10.50.30.10.10.20.60.10.10.10.50.30.10.20.68.49.59.29.49.09.29.49.78.38.78.99.39.49.69.79.90.150.50.250.10.10.10.60.20.10.10.60.20.10.10.60.29.49.69.79.98.78.99.19.98.58.78.99.18.49.59.29.40.10.10.60.20.10.20.60.10.10.10.50.30.150.50.250.19.59.79.8108.48.89

7、.0108.38.78.99.38.48.89.29.80.10.10.60.20.10.20.60.10.10.10.60.20.10.10.60.28.48.89.0108.89.29.8108.78.99.19.98.29.39.59.80.10.20.60.10.050.050.50.40.10.20.60.10.10.50.30.18.49.59.29.48.48.89.29.88.48.89.0109.39.59.79.90.150.50.250.10.10.10.60.20.10.20.60.10.10.10.50.39.09.29.49.78.19.19.39.58.29.29

8、.49.69.19.39.59.80.10.10.60.20.10.50.30.10.10.50.30.10.10.10.60.20.1 9.80.1 8.40.2 9.00.6 9.20.1 9.40.1 8.40.1 8.80.6 9.00.2 100.1 8.90.2 9.10.6 9.30.1 9.60.20.150.50.250.10.10.20.60.10.10.10.60.210 0.210 0.1提出最低分的 load sj.txt fen=sj(:,1:2:20);gai=sj(:,2:2:20);for i=1:4for j=1:10程序：low(i,j)=min(fen(

9、4*i-3:4*i,j);endenddlmwrite(data2.txt,low)%把最低分的矩陣寫(xiě)到純文本文件data2.txt，供Lingo使用求解上述非線性 0-1 整數(shù)規(guī)劃模型的 Lingo 程序：m:sets:xm/1.4/;yd/1.10/:y; links(xm,yd):c,x; endsetsdata:c=file(data2.txt);enddata max=sum(links:c*x);for(xm(i):sum(yd(j):x(i,j)=6);-9-sum(yd(j):x(1,j)*x(2,j)*x(3,j)*x(4,j)=4; for(links:bin(x);for

10、(yd:bin(y); end下面通過(guò)巧妙地引進(jìn)0 1變量1,j,第人參加全能比賽y j0，第j人不參加全能比賽,建立線性0-1整數(shù)規(guī)劃模型max cij xiji1 j14 1010 x 6,i 1,2,3,4ij j1s.t. 4 y j4 xij 3 y j ,j 1,2,10i1 10 y j 4 j1計(jì)算的Lingo程序如下：:msets:xm/1.4/;yd/1.10/:y; links(xm,yd):c,x; endsetsdata:c=file(data2.txt);enddata max=sum(links:c*x);for(xm(i):sum(yd(j):x(i,j)=6)

11、; for(yd(j):4*y(j)sum(xm(i):x(i,j);sum(xm(i):x(i,j)4*y(j);for(yd(j):sum(xm(i):x(i,j)=236.2;for(xm(i): for(yd(j): p(i,j)=sum(pm(k): b(i,j,k)*z(i,j,k);for(xm(i): for(yd(j): c(i,j)=sum(pm(k): a(i,j,k)*z(i,j,k);for(xm(i): for(yd(j): sum(pm(k): z(i,j,k)=1); for(yd:bin(y);for(link:bin(x); for(link2: bin(z

12、); end目標(biāo)函數(shù)的最大值為 P 6.9121019 ，說(shuō)明該隊(duì)無(wú)論以什么陣容出場(chǎng)，獲得冠軍的可能性幾乎是不可能的。根據(jù)每個(gè)運(yùn)動(dòng)員參加每個(gè)項(xiàng)目的得分均值，可以得到以該陣容出場(chǎng)時(shí)，得分的數(shù)學(xué)期望為222.9。記Cij 為第 j 個(gè)人參加第i 個(gè)項(xiàng)目的得分的隨S xij Ciji1 j1假設(shè)總得分 S 服從正態(tài)分布，類似地可以求得最樂(lè)觀情形下，該隊(duì)的總得分為236.9。所以 S 212.3,236.9 。量，總得分隨量4 10各個(gè)Cij 均為相互獨(dú)立的隨E(S) xij E(Cij )i1 j1總分的方差為D(S) xij D(Cij )i1 j1上面已求出 E(S) 222.9 ，計(jì)算得4 10量，所以總