現(xiàn)實(shí)生活中，比如機(jī)器的臺(tái)數(shù)，參與工作的人數(shù)，可調(diào)動(dòng)的車輛數(shù)，這些數(shù)據(jù)都是整數(shù)。因此對(duì)于變量中包含整數(shù)、或者完全是整數(shù)的規(guī)劃問(wèn)題，我們稱之為整數(shù)規(guī)劃。在解決整數(shù)規(guī)劃常用的算法便是單純形法。

課題名稱：任務(wù)的分配

設(shè)有甲、乙、丙、丁四個(gè)人，各有能力去完成A、B、C、D、E五項(xiàng)任務(wù)中的任一項(xiàng)，由于四個(gè)人的能力和經(jīng)驗(yàn)不同，所需完成各項(xiàng)任務(wù)的時(shí)間如表1所示.由于任務(wù)數(shù)多于人數(shù)，要求考慮如下問(wèn)題：

（1）?????? 任務(wù)E必須完成，其他四項(xiàng)中可任選三項(xiàng)完成；

（2）?????? 要求有一個(gè)人完成兩項(xiàng)任務(wù)，其他人各完成一項(xiàng)；

（3）?????? 要求任務(wù)A可由甲或丙完成，任務(wù)C可由丙或丁完成，任務(wù)E可由甲、乙或丁完成，且規(guī)定四個(gè)人中丙或丁能夠完成兩項(xiàng)任務(wù)，其他人完成一項(xiàng)任務(wù)。

試分別確定最優(yōu)的分配方案，使得完成任務(wù)的總時(shí)間最少。

表1?? 每個(gè)人完成各項(xiàng)任務(wù)的能力

項(xiàng)目 人員	A	B	C	D	E
甲	25	29	31	42	37
乙	39	38	26	20	33
丙	34	27	28	40	32
丁	24	42	36	23	45

????由于任務(wù)數(shù)大于人數(shù)，所以需要有一個(gè)虛擬的人，設(shè)為戊。因?yàn)楣ぷ鱁必須完成，故設(shè)戊完成E的時(shí)間為M（M為非常大的數(shù)），即戊不能做工作E，其余的假想時(shí)間為0，建立的效率矩陣如表2：

表2?? 每個(gè)人完成各項(xiàng)任務(wù)的能力

項(xiàng)目 人員	A	B	C	D	E
甲	25	29	31	42	37
乙	39	38	26	20	33
丙	34	27	28	40	32
丁	24	42	36	23	45
戊	0	0	0	0	M

令第 i 個(gè)人表示甲、乙、丙、丁、戊，第 j 個(gè)任務(wù)分別表示A、B、C、D、E項(xiàng)任務(wù)，cij 表示第 i 個(gè)人完成第 j 個(gè)任務(wù)的時(shí)間（d）。設(shè)：

Z為完成任務(wù)的總時(shí)間（d）。則該問(wèn)題的數(shù)學(xué)模型為：

為輸入程序方便，令M=1000.

方法一：Matlab求解

Matlab程序：

c=[25 29 31 42 37;39 38 26 20 33;34 27 28 40 32;24 42 36 23 45;0 0 0 0 1000]; n=size(c,1); c=c(:); a=zeros(2*n,n^2); for i=1:na(i,(i-1)*n+1:n*i)=1;a(n+i,i:n:n^2)=1; end b=ones(2*n,1); [x,y]=linprog(c,[],[],a,b,zeros(n^2,1),ones(n^2,1)); X=reshape(x,n,n); X_min=round((X)),y

Matlab運(yùn)行結(jié)果：

Optimization terminated. X_min =0 1 0 0 00 0 0 1 00 0 0 0 11 0 0 0 00 0 1 0 0 y =105.0000

方案：甲——B ,乙——D ,丙——E ,丁——A ,? 總時(shí)間為105（d）.

方法二：lingo求解

Lingo程序：

model: sets: row/1..5/; arrange/1..5/; link(row,arrange):c,x; endsets data: c=25,29,31,42,37,39,38,26,20,33,34,27,28,40,32,24,42,36,23,45,0,0,0,0,1000; enddata [OBJ]min=@sum(link(i,j):c(i,j)*x(i,j)); x(1,1)+x(1,2)+x(1,3)+x(1,4)+x(1,5)=1; x(2,1)+x(2,2)+x(2,3)+x(2,4)+x(2,5)=1; x(3,1)+x(3,2)+x(3,3)+x(3,4)+x(3,5)=1; x(4,1)+x(4,2)+x(4,3)+x(4,4)+x(4,5)=1; x(5,1)+x(5,2)+x(5,3)+x(5,4)+x(5,5)=1; x(1,1)+x(2,1)+x(3,1)+x(4,1)+x(5,1)=1; x(1,2)+x(2,2)+x(3,2)+x(4,2)+x(5,2)=1; x(1,3)+x(2,3)+x(3,3)+x(4,3)+x(5,3)=1; x(1,4)+x(2,4)+x(3,4)+x(4,4)+x(5,4)=1; x(1,5)+x(2,5)+x(3,5)+x(4,5)+x(5,5)=1; @for(link(i,j):x(i,j)>=0;); end

Lingo運(yùn)行結(jié)果：

Global optimal solution found.Objective value: 136.0000Infeasibilities: 0.000000Total solver iterations: 9Elapsed runtime seconds: 0.04Variable Value Reduced CostC( 1, 1) 25.00000 0.000000C( 1, 2) 29.00000 0.000000C( 1, 3) 1000.000 0.000000C( 1, 4) 42.00000 0.000000C( 1, 5) 37.00000 0.000000C( 2, 1) 1000.000 0.000000C( 2, 2) 38.00000 0.000000C( 2, 3) 1000.000 0.000000C( 2, 4) 20.00000 0.000000C( 2, 5) 33.00000 0.000000C( 3, 1) 34.00000 0.000000C( 3, 2) 27.00000 0.000000C( 3, 3) 28.00000 0.000000C( 3, 4) 40.00000 0.000000C( 3, 5) 1000.000 0.000000C( 4, 1) 1000.000 0.000000C( 4, 2) 42.00000 0.000000C( 4, 3) 36.00000 0.000000C( 4, 4) 23.00000 0.000000C( 4, 5) 45.00000 0.000000C( 5, 1) 34.00000 0.000000C( 5, 2) 27.00000 0.000000C( 5, 3) 28.00000 0.000000C( 5, 4) 23.00000 0.000000C( 5, 5) 45.00000 0.000000X( 1, 1) 1.000000 0.000000X( 1, 2) 0.000000 11.00000X( 1, 3) 0.000000 981.0000X( 1, 4) 0.000000 28.00000X( 1, 5) 0.000000 10.00000X( 2, 1) 0.000000 969.0000X( 2, 2) 0.000000 14.00000X( 2, 3) 0.000000 975.0000X( 2, 4) 0.000000 0.000000X( 2, 5) 1.000000 0.000000X( 3, 1) 0.000000 0.000000X( 3, 2) 0.000000 0.000000X( 3, 3) 1.000000 0.000000X( 3, 4) 0.000000 17.00000X( 3, 5) 0.000000 964.0000X( 4, 1) 0.000000 966.0000X( 4, 2) 0.000000 15.00000X( 4, 3) 0.000000 8.000000X( 4, 4) 1.000000 0.000000X( 4, 5) 0.000000 9.000000X( 5, 1) 0.000000 0.000000X( 5, 2) 1.000000 0.000000X( 5, 3) 0.000000 0.000000X( 5, 4) 0.000000 0.000000X( 5, 5) 0.000000 9.000000

lingo所得的方案與matlab一致。甲——B ,乙——D ,丙——E ,丁——A ,? 總時(shí)間為105（d）.

lingo的運(yùn)行結(jié)果怎么解讀的問(wèn)題，我已經(jīng)在上一篇“非線性規(guī)劃”的文章中說(shuō)了，不再贅述，不懂的同學(xué)可以過(guò)去看一看，以后用lingo解決的問(wèn)題還會(huì)有，不會(huì)每次都講解怎么看運(yùn)行結(jié)果哦，希望見諒，下面是“非線性規(guī)劃”文章的鏈接。

數(shù)據(jù)建模-用非線性規(guī)劃解決問(wèn)題

????整數(shù)規(guī)劃問(wèn)題是線性規(guī)劃問(wèn)題的一種特殊情況，本例題為典型的非標(biāo)準(zhǔn)形式的指派問(wèn)題，根據(jù)題目的不同要求，相應(yīng)地添加虛擬人或任務(wù)以及修改效率矩陣。另外，在轉(zhuǎn)換成程序語(yǔ)言時(shí)，引進(jìn)的M可以任意取定一個(gè)較大的數(shù)，方便計(jì)算的進(jìn)行。

總結(jié)

以上是生活随笔為你收集整理的线性规划 - 用单纯形法解决整数规划问题 - （Matlab、Lingo建模）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。