【数学建模】day02-整数规划
基本類似于中學(xué)講的整數(shù)規(guī)劃--線性規(guī)劃中變量約束為整數(shù)的情形。
目前通用的解法適合整數(shù)線性規(guī)劃。不管是完全整數(shù)規(guī)劃(變量全部約束為整數(shù))，還是混合整數(shù)規(guī)劃(變量既有整數(shù)又有實(shí)數(shù))，MATLAB都提供了通用的求解函數(shù)。
?
?
一、0-1型整數(shù)規(guī)劃
這類規(guī)劃將變量限制為0和1，有時候多個規(guī)劃問題可以通過引入0-1變量將問題統(tǒng)一在一個規(guī)劃問題中討論。例如：
擁有相互排斥的規(guī)劃約束：
一般的，
?
?
二、0-1整數(shù)規(guī)劃的一個解法：隱枚舉法
因?yàn)樽兞康娜≈凳侨?-1的，所以可以枚舉所有取值求得極大/極小值。例如，求解
（1）試探一個可行解(x1,x2,x3)=(1,0,0)，相應(yīng)的目標(biāo)函數(shù)值是3。暫做最優(yōu)解。
（2）繼續(xù)試探其他可行解。倘若目標(biāo)函數(shù)值小于3則不考慮，這相當(dāng)于增加了目標(biāo)大于等于3的又一個約束。否則目標(biāo)函數(shù)值大于3，則新的可行解暫做最優(yōu)解，更新當(dāng)前最優(yōu)目標(biāo)函數(shù)值，重復(fù)（2）。
（3）直到：枚舉完所有可行解。
?
三、固定費(fèi)用問題
舉例說明這類問題是：有三種產(chǎn)品投資方式，相應(yīng)增加A產(chǎn)品投資會使得A的固定成本上升，而由于產(chǎn)品產(chǎn)量增加使得單個產(chǎn)品費(fèi)用下降，問如何投資使得成本最低。
解決這個問題的一個方法可以是：列成本函數(shù)，引入0-1變量統(tǒng)一到一個規(guī)劃問題中。具體求解不贅述。
?
四、非線性整數(shù)規(guī)劃的一個方法：蒙特卡洛法
盡管整數(shù)規(guī)劃由于限制變量為整數(shù)而增加了難度；然而又由于整數(shù)解是有限個，于是為枚舉法提供了方便。
當(dāng)然，當(dāng)自變量維數(shù)很大和取值范圍很寬情況下，企圖用顯枚舉法（即窮舉法）計(jì)算出優(yōu)值是不現(xiàn)實(shí)的，但是應(yīng)用概率理論可以證明，在一定的計(jì)算量的情況下（這里指蒙特卡羅法隨機(jī)抽取可行點(diǎn)求解近似解），完全可以得出一個滿意解。
所謂蒙特卡洛法（隨機(jī)取樣），是指對于計(jì)算量過大的問題，通過隨機(jī)取樣計(jì)算部分，而非整體，來降低計(jì)算量的方法。這通常是近似解，但概率統(tǒng)計(jì)的方法證明，這是可靠的。
蒙特卡洛的應(yīng)用實(shí)例。
（1）計(jì)算面積：計(jì)算y=x^2,y=12-x與x軸在第一象限圍城的曲邊三角形的面積。
方法：利用蒙特卡羅法。在矩形(0,0),(0,9),(12,9),(12,0)中隨機(jī)生成n個點(diǎn)，統(tǒng)計(jì)落在曲邊三角形內(nèi)的點(diǎn)個數(shù)，計(jì)算頻度即為曲邊三角形與矩形的面積之比。
?
使用matlab生成一維均勻分布隨機(jī)數(shù)：R = unifrnd(A,B)：生成區(qū)間(A,B)內(nèi)的隨機(jī)數(shù)，A，B可以是向量。R = unifrnd(A,B,M,N)：生成區(qū)間(A,B)內(nèi)的M*N個隨機(jī)數(shù)。R = unifrnd(A,B,[M,N])：同上。生成二維均勻分布隨機(jī)數(shù)則由一維組合而成。?
matlab實(shí)現(xiàn)：
?
1 clc,clear 2 x = unifrnd(0,12,1,10000000); 3 y = unifrnd(0,9,1,10000000); 4 pinshu = sum(y<x.^2 & x<=3) + sum(x>3 & y <12-x); 5 area = pinshu/10000000*12*9; 6 area?
?
?
（2）一個非線性規(guī)劃蒙特卡洛求解實(shí)例
使用：產(chǎn)生隨機(jī)數(shù)種子：為了防止相同狀態(tài)開始會產(chǎn)生相同的偽隨機(jī)數(shù)（特別是程序中有l(wèi)oop）1. rand('state',sum(100*clock)):根據(jù)當(dāng)前時間，已經(jīng)不推薦使用2. rand('twister',mod(floor(now*8640000),2^31-1))：也可以3. rng命令
注：
?
實(shí)現(xiàn)：
先定義函數(shù)：
1 function [f,g] = mente(x) 2 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) 3 4 -x(4)-2*x(5); 5 g=[sum(x)-400 6 7 x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800 8 9 2*x(1)+x(2)+6*x(3)-200 10 11 x(3)+x(4)+5*x(5)-200];?再求解：
?
五、指派問題
分配n人去做n個任務(wù)，每人做且只做一項(xiàng)任務(wù)。第i個人做第j項(xiàng)任務(wù)，花費(fèi)cij時間。問如何分配人去做任務(wù)，使得總時間花費(fèi)最少。
可以看出，花費(fèi)cij構(gòu)成矩陣，稱為指派矩陣。引入0-1變量矩陣n*n，則該矩陣每行每列只有一個1，其余為0，為1代表i做任務(wù)j，轉(zhuǎn)化為一個整數(shù)規(guī)劃問題。
匈牙利算法可解。
?
六、整數(shù)規(guī)劃的matlab通用解法
| 函數(shù)： [x,fval] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub) param： f：目標(biāo)函數(shù)系數(shù)列向量 intcon：整數(shù)變量的地址，如變量有x1,x2,x3,若x2,x3為整數(shù)變量，則intcon = 2:3 A，b對應(yīng)不等約束 Aeq，beq對應(yīng)等式約束 lb，ub對應(yīng)邊界約束 return: x：取得最優(yōu)值的對應(yīng)變量取值 fval：最優(yōu)值。同理，這是求標(biāo)準(zhǔn)型即min，若求max則目標(biāo)函數(shù)求反 |
求解實(shí)例：
（1）求解指派問題：已知指派矩陣為
?
?
?
也就是相應(yīng)C矩陣，取xij1則對應(yīng)i做任務(wù)j。
（2）求解混合整數(shù)規(guī)劃問題
min z = –3x1 –2x2 – x3
s.t.
x1 + x2 + x3 <=7,
4x1 + 2x2 + x3 =12,
x1,x2 >=0
x3 = 0或1
分析知，只有x3是0-1整數(shù)變量，則intcon = 3
求解：
?
1 clc,clear 2 f = [-3;-2;-1]; 3 A = [1,1,1]; 4 b = 7; 5 Aeq = [4,2,1]; 6 beq = 12; 7 lb = zeros(3,1); 8 ub = [inf;inf;1]; 9 intcon = 3; 10 [x,y] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub); 11 x 12 y
?
?
?
轉(zhuǎn)載于:https://www.cnblogs.com/duye/p/9327955.html
創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎總結(jié)
以上是生活随笔為你收集整理的【数学建模】day02-整数规划的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 微信小程序 背景图片设置
- 下一篇： ABB 机器人 DRVIO_1通信报警