0-1整數規劃執行個體
1、投資場所的標明——互相排斥的計劃
解:解題時先引入0 −1變量xi,并進行問題轉換
2、引入0 −1變量y,來解決互相排斥的限制條件
3、擴充:利用0-1變量來解決m 個互相排斥的限制條件
如果有m 個互相排斥的限制條件
4、關于固定費用的問題(Fixed Cost Problem)
某工廠為了生産某種産品,有幾種不同的生産方式可供選擇,如標明的生産方式投資高(選購自動化程度高的裝置),由于産量大,因而配置設定到每件産品的變動成本就降低;反之,如標明的生産方式投資低,将來配置設定到每件産品的變動成本可能增加。是以必須全面考慮。今設有三種方式可供選擇,令
5、舉例說明一種解0 −1型整數規劃的隐枚舉法
6、蒙特卡洛法求解非線性整數規劃
(1)、首先編寫M 檔案mente.m 定義目标函數f 和限制向量函數g,程式如下
function [f,g]=mengte(x);
f=x(1)^2+x(2)^2+3*x(3)^2+4*x(4)^2+2*x(5)-8*x(1)-2*x(2)-3*x(3)-...
x(4)-2*x(5);
g=[sum(x)-400
x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800
2*x(1)+x(2)+6*x(3)-200
x(3)+x(4)+5*x(5)-200];
(2)、編寫M檔案mainint.m如下求問題的解
rand('state',sum(clock));
p0=0;
tic
for i=1:10^6
x=99*rand(5,1);
x1=floor(x);x2=ceil(x);
[f,g]=mengte(x1);
if sum(g<=0)==4
if p0<=f
x0=x1;p0=f;
end
end
[f,g]=mengte(x2);
x0=x2;p0=f;
x0,p0
toc
7、Matlab求解指派問題等0 −1整數規劃問題
解:編寫 Matlab 程式如下:
c=[3 8 2 10 3;8 7 2 9 7;6 4 2 7 5
8 4 2 3 5;9 10 6 9 10];
c=c(:);
a=zeros(10,25);
for i=1:5
a(i,(i-1)*5+1:5*i)=1;
a(5+i,i:5:25)=1;
b=ones(10,1);
[x,y]=bintprog(c,[],[],a,b);
x=reshape(x,[5,5]),y