一、線性規(guī)劃（Linear Programming，LP）
1.1 引例
在人們的生產(chǎn)實踐中，經(jīng)常會遇到如何利用現(xiàn)有資源來安排生產(chǎn)，以取得最大經(jīng)濟效益的問題。 此類問題構(gòu)成了運籌學(xué)的一個重要分支一數(shù)學(xué)規(guī)劃，而線性規(guī)劃（Linear Programming, LP） 則是數(shù)學(xué)規(guī)劃的一個重要分支。
簡而言之，線性規(guī)劃就是在有限的條件下，獲得最大的收益。
【例】 某機床廠生產(chǎn)甲、乙兩種機床，每臺銷售后的利潤分別為4000元與3000元。生產(chǎn)甲機床需用A、B機器加工，加工時間分別為每臺2h和1h；生產(chǎn)乙機床需用A、B、C三種機器加工，加工時間為每臺各1h。若每天可用于加工的機器時數(shù)分別為A機器10h、B機器8h和C機器7h，問該廠應(yīng)生產(chǎn)甲、乙機床各幾臺，才能使總利潤最大?
上述問題的數(shù)學(xué)模型為：（其中，
x
1
x_1
x1? 和
x
2
x_2
x2? 是決策變量）
總之，線性規(guī)劃問題是在一組線性約束條件的限制下，求一線性目標(biāo)函數(shù)最大或最小的問題。 “線性”意味著所有變量都是一次方。
在解決實際問題時，把問題歸結(jié)成一個線性規(guī)劃數(shù)學(xué)模型是很重要的一步，往往也是很困難的一步，模型建立得是否恰當(dāng)，直接影響到求解。而選擇適當(dāng)?shù)臎Q策變量，是建立有效模型的關(guān)鍵之一。
1.2 線性規(guī)劃問題的解
一般線性規(guī)劃問題的（數(shù)學(xué)）標(biāo)準(zhǔn)型為：
1.3 Matlab標(biāo)準(zhǔn)形式
線性規(guī)劃的目標(biāo)函數(shù)可以是求最大值，也可以是求最小值，約束條件的不等號可以是
小于等號也可以是大于等號。為了避免這種形式多樣性帶來的不便，Matlab中規(guī)定線性規(guī)劃的標(biāo)準(zhǔn)形式為：
Matlab中求解線性規(guī)劃的命令為：
[x, fval] = linprog(f, A, b) % A和b對應(yīng)線性不等式約束
[x, fval] = linprog(f, A, b, Aeq, beq) % Aeq和beq對應(yīng)線性等式約束
[x, fval] = linprog(f, A, b, Aeq, beq, lb, ub) % lb和ub分別對應(yīng)決策變量的下界向量和上界向量
其中， x x x 返回決策向量的取值； f v a l fval fval 返回目標(biāo)函數(shù)的最優(yōu)值。
如果線性規(guī)劃問題的解為max形式，可以通過以下轉(zhuǎn)換，再應(yīng)用Matlab提供的方法：
【例】 求解下列線性規(guī)劃問題。
將其轉(zhuǎn)換為Matlab標(biāo)準(zhǔn)形式：
Matlab代碼實現(xiàn)為：
f = [-40;-30] % 目標(biāo)函數(shù)中變量的系數(shù)矩陣
a = [1,1;-1,0;0,-1;240,120] % 小于等于的約束條件中變量系數(shù)矩陣
b = [6;-1;-1;1200] % 小于等于的約束條件中常數(shù)項矩陣
[x,y] = linprog(f, a, b) % 從等式約束開始后都沒有，可以都不寫
y = -y % 注意要還原成求最大值?。。。?求解結(jié)果為：
【例】 求解下列線性規(guī)劃問題。
代碼如下：
clc;clear
c=[2;3;1];
a=[1,4,2;3,2,0];
b=[8;6];
[x,y]=linprog(c,-a,-b,[],[],zeros(3,1)) %這里沒有等式約束，對應(yīng)的矩陣為空矩陣
求解結(jié)果為：
1.4 投資的收益和風(fēng)險（模型建立與分析）
1.4.1 符號規(guī)定和基本假設(shè)
符號規(guī)定：
基本假設(shè)：
注意，這里將M假設(shè)為1，可以方便后面的計算。（建模比賽中可以適當(dāng)進行假設(shè)）
1.4.2 模型的分析與建立
（1）總體風(fēng)險用所投資的
s
i
s_i
si? 中最大的一個風(fēng)險來衡量，即
（2）購買
s
i
（
i
=
1
,
2
,
.
.
.
,
n
)
s_i（i=1,2,...,n)
si?（i=1,2,...,n) 所付交易費是一個分段函數(shù)，即
而題目中所給的定值
u
i
u_i
ui? （單位：元）相對總投資
M
M
M 很少，
p
i
u
i
p_iu_i
pi?ui? 更小，這樣購買
s
i
s_i
si? 的凈收益可以簡化為
(
r
i
?
p
i
)
x
i
(r_i-p_i)x_i
(ri??pi?)xi? 。
（3）要使凈收益盡可能大，總體風(fēng)險盡可能小，這是一個多目標(biāo)規(guī)劃模型 。
目標(biāo)函數(shù)為：
約束條件為：
（4）模型簡化。
模型一： 在實際投資中，投資者承受風(fēng)險的程度不一樣，若給定風(fēng)險一個界限 a，使最大的一個風(fēng)險率為a，即 q i x i / M ≤ a ( i = 1 , 2 , … , n ) q_ix_i/M ≤ a (i=1,2,…,n) qi?xi?/M≤a(i=1,2,…,n)，可找到相應(yīng)的投資方案。這樣以來就可以把多目標(biāo)規(guī)劃變成一個目標(biāo)的線性規(guī)劃。
即固定風(fēng)險水平，優(yōu)化收益：
通俗理解，就是把原來多目標(biāo)優(yōu)化中第二個
m
i
n
min
min 目標(biāo)函數(shù)轉(zhuǎn)變?yōu)榧s束條件，只要風(fēng)險小于
a
a
a 都是投資者可接受的風(fēng)險范圍。
模型二： 若投資者希望總盈利至少達到水平 k k k 以上，在風(fēng)險最小的情況下尋求相應(yīng)的投資組合。
即固定盈利水平，極小化風(fēng)險：
和模型一類似，這里將
m
a
x
max
max 目標(biāo)函數(shù)轉(zhuǎn)換為了只要總收益大于
k
k
k ，投資者都可以接受。
模型三： 投資者在權(quán)衡資產(chǎn)風(fēng)險和預(yù)期收益兩方面時，希望選擇一個令自己滿意的投資組合。因此對風(fēng)險收益分別賦予權(quán)重 s s s 和 ( 1 ? s ) (1-s) (1?s) ， s s s 稱為投資偏好系數(shù)。
這里可以簡單理解成投資者是更注重哪一個目標(biāo)，投資者傾向的那個權(quán)重設(shè)置的更大即可。
上述模型對應(yīng)的兩條思路也是在數(shù)學(xué)建模中經(jīng)常會使用到的：①將多目標(biāo)轉(zhuǎn)換為單目標(biāo)規(guī)劃；②將多目標(biāo)函數(shù)賦予相應(yīng)的權(quán)重進行搜索。
1.4.3 模型一的求解
模型一為：
注意：這里將原目標(biāo)函數(shù)
m
a
x
max
max 轉(zhuǎn)換成了Matlab標(biāo)準(zhǔn)型的
m
i
n
min
min 形式，就要在所有值前面加負(fù)號。
【數(shù)值細(xì)節(jié)解釋】
x
0
x_0
x0? 對應(yīng)的-0.05代表的是題目中假定的同期銀行存款利率
r
0
=
0.5
r_0=0.5
r0?=0.5 ，既無交易費又無風(fēng)險的條件。
x
1
x_1
x1? 對應(yīng)的是當(dāng)投資第一個資產(chǎn)
s
1
s_1
s1? 時，其對應(yīng)的
?
(
r
i
?
p
i
)
x
i
-(r_i-p_i)x_i
?(ri??pi?)xi? 值。同理可得其他值。
由于 α α α 是任意給定的風(fēng)險度，不同的投資者有不同的風(fēng)險度。下面從 α = 0 α=0 α=0 開始，以步長 △ α = 0.001 △α=0.001 △α=0.001 進行循環(huán)搜索。Matlab求解代碼如下：
clc,clear
a=0;
hold on
while a<0.05
c=[-0.05,-0.27,-0.19,-0.185,-0.185];
A=[zeros(4,1),diag([0.025,0.015,0.055,0.026])]; % 生成對角矩陣
b=a*ones(4,1); % 不等式約束右邊的值
Aeq=[1,1.01,1.02,1.045,1.065];
beq=1;
LB=zeros(5,1); % 下界
[x,Q]=linprog(c,A,b,Aeq,beq,LB);
Q=-Q; % 注意求得是max?。。。。。。。。。。。? plot(a,Q,'*k');
a=a+0.001; % 以步長α=0.001進行循環(huán)搜索
end
xlabel('a'),ylabel('Q')
運行結(jié)果為：
1.4.4 結(jié)果分析
風(fēng)險
α
α
α 與收益
Q
Q
Q 之間的關(guān)系如上圖所示，我們可以看出：
(1) 風(fēng)險大，收益也大。
(2) 當(dāng)投資越分散時，投資者承擔(dān)的風(fēng)險越小，這與題意一致。冒險的投資者會出現(xiàn)集中投資的情況，保守的投資者則盡量分散投資。
(3) 在
a
=
0.006
a=0.006
a=0.006 附近有一個轉(zhuǎn)折點，在這一點左邊，風(fēng)險增加很少時，利潤增長很快；在這一點右邊，風(fēng)險增加很大時，利潤增長很緩慢。所以對于風(fēng)險和收益沒有特殊偏好的投資者來說，應(yīng)該選擇曲線的轉(zhuǎn)折點作為最優(yōu)投資組合，大約是
a
=
0.6
a=0.6
a=0.6%，
Q
=
20
Q=20
Q=20%。
所對應(yīng)的投資方案我們可以在代碼中加入a=0.6%查看具體的
x
x
x 和
Q
Q
Q ：
while a == 0.006
disp(x);
disp(Q);
break;
end
得到具體的投資方案為：
二、整數(shù)規(guī)劃
2.1 引例
數(shù)學(xué)規(guī)劃中的變量（部分或全部）限制為整數(shù)時，稱為整數(shù)規(guī)劃。若在線性規(guī)劃模型中，變量限制為整數(shù)，則稱為整數(shù)線性規(guī)劃。目前所流行的求解整數(shù)規(guī)劃的方法，往往只適用于整數(shù)線性規(guī)劃。目前還沒有一種方法能有效地求解一切整數(shù)規(guī)劃。
整數(shù)規(guī)劃的分類：
如不加特殊說明，則一般指整數(shù)線性規(guī)劃。整數(shù)線性規(guī)劃模型大致分為兩類：
1）變量全限制為整數(shù)時，稱純（完全）整數(shù)規(guī)劃。
2）變量部分限制為整數(shù)時，稱混合整數(shù)規(guī)劃。
整數(shù)規(guī)劃特點：
1）原線性規(guī)劃有最優(yōu)解，當(dāng)自變量限制為整數(shù)后，其整數(shù)規(guī)劃解出現(xiàn)下述情況。
①原線性規(guī)劃最優(yōu)解全是整數(shù)，則整數(shù)規(guī)劃最優(yōu)解與線性規(guī)劃最優(yōu)解一致。
?、谡麛?shù)規(guī)劃無可行解。
③有可行解（當(dāng)然就存在最優(yōu)解），但最優(yōu)解值變差。
2）整數(shù)規(guī)劃最優(yōu)解不能按照實數(shù)最優(yōu)解簡單取整而獲得。
求解方法分類：
| 方法 | 說明 |
|---|---|
| 分支定界法 | 可求純或混合整數(shù)線性規(guī)劃 |
| 割平面法 | 可求純或混合整數(shù)線性規(guī)劃 |
| 隱枚舉法 | 求解“0-1”整數(shù)規(guī)劃。 分為過濾隱枚舉法和分支隱枚舉法。 |
| 匈牙利法 | 解決指派問題（0-1規(guī)劃特殊情形） |
| 蒙特卡洛法 | 求解各種類型規(guī)劃 |
注：蒙特卡羅算法請看之前的筆記：數(shù)學(xué)建模十大算法01-蒙特卡洛算法（Monte Carlo）
2.2 “0-1 型”整數(shù)規(guī)劃
0-1型整數(shù)規(guī)劃是整數(shù)規(guī)劃中的特殊情形，它的變量 x j x_j xj? 僅取值0或1。這時 x j x_j xj? 稱為0-1變量，或稱二進制變量。 x j x_j xj? 僅取值0或1這個條件可由下述約束條件 0 ≤ x j ≤ 1 且 x j 為整數(shù) 0≤x_j≤1且 x_j 為整數(shù) 0≤xj?≤1且xj?為整數(shù)所代替，是和一般整數(shù)規(guī)劃的約束條件形式一致的。在實際問題中，如果引人0-1變量，就可以把有各種情況需要分別討論的數(shù)學(xué)規(guī)劃問題統(tǒng)一在一個問題中討論了。下面先介紹引入0-1變量的實際問題。
2.2.1 相互排斥的約束條件
有兩種運輸方式可供選擇，但只能選擇一運輸方式，或者用車運輸，或者用船運輸。
用車運輸?shù)募s束條件為
5
x
1
+
4
x
2
≤
24
5x_1+ 4x_2≤24
5x1?+4x2?≤24，用船運輸?shù)募s束條件為
7
x
1
+
3
x
2
≤
45
7x_1 +3x_2 ≤45
7x1?+3x2?≤45。即有兩個相互排斥的約束條件
5
x
1
+
4
x
2
≤
24
或
7
x
1
+
3
x
2
≤
45
5x_1+ 4x_2≤24 或 7x_1 +3x_2 ≤45
5x1?+4x2?≤24或7x1?+3x2?≤45
為了統(tǒng)一在一個問題中，引入0-1變量：
則上述約束條件可改寫為：
把相互排斥的約束條件改成普通的約束條件，未必需要引進充分大的正實數(shù)，例如相互排斥的約束條件：
如果有
m
m
m 個互相排斥的約束條件：
2.2.2 指派問題的數(shù)學(xué)模型
擬分配 n n n 人去做 n n n 項工作，每人做且僅做1項工作，若分配第 i i i 人去做第 j j j 項工作，需花費 c i j c_{ij} cij? 單位時間，問應(yīng)該如何分配工作才能使工人花費的總時間最少？
思路： 只需要給出矩陣 C = c i j C = c_{ij} C=cij? （指派問題的系數(shù)矩陣）。
引入0-1變量：
上述指派問題的數(shù)學(xué)模型為：
上述指派問題的可行解可以用一個矩陣表示，其每行、每列均有且只有一個元素為1，其余元素均為0；還可以用
1
,
.
.
.
,
n
1,...,n
1,...,n 中的一個置換表示。
Matlab中指派問題可用以下語法格式實現(xiàn)：
[x,fval]=intlinprog(f,intcon,a,b,aeq,beq,lb,ub)
對應(yīng)下列數(shù)學(xué)模型：
【例】 求解下列指派問題，已知指派矩陣為：
這里需要把二維決策變量
x
i
j
(
i
,
j
=
1
,
.
.
.
,
5
)
x_{ij}(i,j=1,...,5)
xij?(i,j=1,...,5) 變?yōu)橐痪S決策變量
y
k
(
k
=
1
,
.
.
.
,
25
)
y_k(k=1,...,25)
yk?(k=1,...,25)。可以理解成將每行每列只有一個“1”轉(zhuǎn)換為一維考慮。
Matlab實現(xiàn)代碼如下：
clc,clear
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(:); % 將矩陣c中的每列（！?。。┖喜⒊梢粋€長的列向量
a = zeros(10,25);
intcon = 1:25;
for i = 1:5
a(i,(i-1)*5+1:5*i) = 1; % 第i行，連續(xù)5個值為1---->
a(5+i,i:5:25) = 1; % 第5+i行，每隔5個賦值1---->
end
b = ones(10,1);
lb = zeros(25,1);
ub = ones(25,1);
x = intlinprog(c,intcon,[],[],a,b,lb,ub)
把5個物品放入一個5×5的方陣中，且每行、每列都必須且只能有一個物品。使用混合整數(shù)線性規(guī)劃的函數(shù)intlinprog求解，就要把這5x5的位置看成25個優(yōu)化變量，每個變量只能取0或1。a和b表示等式約束，10行表示10個等式，其中前5個表示每行有一個物品，后5行表示每列有一個物品。
最終求得的最優(yōu)指派方案為：用x = reshape(x,[5,5])查看：
【例】 求解如下的混合整數(shù)規(guī)劃問題：
Matlab代碼如下：
clc,clear
f=[-3;-2;-1]; intcon=3; % 整數(shù)變量的地址
a=ones(1,3); b=7;
aeq = [4 2 1]; beq=12;
lb=zeros(3,1); ub=[inf;inf;1]; % x(3)為0-1變量
x=intlinprog(f,intcon,a,b,aeq,beq,lb,ub)
z=dot(f,x) % 目標(biāo)函數(shù)的最優(yōu)值為-12
求解結(jié)果為：
【例】 某公司新購置了某種設(shè)備6臺，欲分配給下屬的4個企業(yè)，已知各企業(yè)獲得這種設(shè)備后年創(chuàng)利潤如表所列（單位：千萬元）。問應(yīng)如何分配這些設(shè)備能使年創(chuàng)總利潤最大，最大利潤是多少？
思路：用
j
=
1
,
2
,
3
,
4
j=1,2,3,4
j=1,2,3,4 分別表示甲乙丙丁四個企業(yè)，
c
i
j
c_{ij}
cij? 表示第
i
(
i
=
1
,
.
.
.
,
6
)
i(i=1,...,6)
i(i=1,...,6) 臺設(shè)備分配給第
j
j
j 個企業(yè)創(chuàng)造的利潤，引進0-1變量：
則問題的數(shù)學(xué)模型為：
Matlab代碼如下：（和上述代碼不同，這里用的是基于問題的求解方法）
% 非常規(guī)指派問題
clc,clear
prob = optimproblem('ObjectiveSense','max'); % 基于問題的求解方法：ObjectiveSense可以是max和min，代表優(yōu)化最大值還是最小值，默認(rèn)是min
x = optimvar('x',6,4,'TYPE','integer','LowerBound',0,'UpperBound',1); % x是變量名，x為6行4列。該函數(shù)所屬類型為int。下界為0，上界為1.
c = [4 2 3 4;6 4 5 5;7 6 7 6;7 8 8 6;7 9 8 6;7 10 8 6];
M=c.*x;
prob.Objective = sum(sum(M)); % 目標(biāo)函數(shù)，目標(biāo)函數(shù)需要得到一個標(biāo)量數(shù)值，不是矩陣向量
% 約束條件 .con是標(biāo)簽，可以自己命名，多個約束條件時，必須標(biāo)簽不能一樣。
prob.Constraints.con2 =sum(x)>=1; % 每列求和，結(jié)果大于等于1
prob.Constraints.con1 =sum(x,2)==1; % 每行求和，結(jié)果等于1
[sol,flav,flag] = solve(prob); % fval是最優(yōu)值，sol.x是決策變量的值，當(dāng)多個決策變量時，可以sol.y，flag在線性規(guī)劃中不用在意，在非線性規(guī)劃中注意不能為負(fù)值。
xx = sol.x
sum(sum(c.*xx))
Python實現(xiàn)代碼如下所示：
# 決策變量
n = 8
# nonneg參數(shù)，變量是否為非負(fù)
x = cp.Variable(n,nonneg = True)
# 約束1
A1 = np.array([[1,1,1,0,0,0,0,0],
[0,1,0,1,0,0,0,0],
[0,0,1,0,1,0,0,0],
[0,0,0,1,0,1,0,0],
[0,0,0,0,1,1,0,0],
[1,0,0,0,0,0,0,0],
[0,1,0,1,0,1,0,0]])
b1 = np.array([1,1,1,1,1,1,1])
# 約束2
A2 = np.ones((8, 8))
for i in range(A2.shape[0]):
for j in range(A2.shape[1]):
if i == j:
pass
else:
A2[i, j] = A2[i, j]*0
b2 = np.array([0,0,0,0,0,0,0,0])
# 約束3
A3 = np.ones((8, 8))
for i in range(A3.shape[0]):
for j in range(A3.shape[1]):
if i == j:
pass
else:
A3[i, j] = A3[i, j]*0
b3 = np.array([1,1,1,1,1,1,1,1])
# 目標(biāo)函數(shù)
c = np.array([1,1,1,1,1,1,1,1])
# 定義問題，添加約束條件
prob = cp.Problem(cp.Minimize(c.T @ x),
[A1 @ x >= b1,
A2 @ x >= b2,
A3 @ x <= b3])
# 求解
ans = prob.solve(solver=cp.GLOP)
# 輸出結(jié)果
print("目標(biāo)函數(shù)最小值:", ans)
# 對x向量各元素取整數(shù)后再輸出
print(x.value)
運行結(jié)果為：
更多用Python實現(xiàn)的例題可參考：數(shù)學(xué)建模算法與應(yīng)用—整數(shù)規(guī)劃（cvxpy包）
指派問題的求解可以使用匈牙利算法、拍賣算法等算法，這里就不討論了。
三、非線性規(guī)劃
3.1 引例
如果目標(biāo)函數(shù)或約束條件中包含非線性函數(shù)，就稱這種規(guī)劃問題為非線性規(guī)劃問題。簡而言之，就是至少有一個變量不是一次方。
一般說來，解非線性規(guī)劃要比解線性規(guī)劃問題困難得多。而且，也不像線性規(guī)劃有單純形法這一通用方法，非線性規(guī)劃目前還沒有適于各種問題的一般算法，各個方法都有自己特定的適用范圍。
3.2 Matlab求解
Matlab中非線性規(guī)劃的的數(shù)學(xué)模型寫成以下形式：
Matlab中的命令是：
[x, fval] = fmincon(fun, x0, A, b, Aeq, beq, lb, ub, nonlcon)
其中，各項的含義如下表：
注意：這里的fun是單獨函數(shù)文件里面定義的目標(biāo)函數(shù)。
【例】 求下列非線性規(guī)劃：
第一步：編寫M函數(shù)fun1.m定義目標(biāo)函數(shù)：
第二步：編寫M函數(shù)fun2.m定義非線性約束條件：
第三步：編寫主程序文件如下：
求得最優(yōu)情況下，x和y的取值為：
3.3 數(shù)學(xué)建模中的應(yīng)用
非線性規(guī)劃適用的典型賽題有：
題目中提到“怎么安排/分配”、“盡量多（少）”、“最多（少）”、“利潤最大”、“最合理”等詞，且變量要非一次方。
- 投資規(guī)劃： 組合投資、總收益率最大/最大投資方案
- 角度調(diào)整： 飛行管理避免相撞；影院最佳視角等；設(shè)計三角函數(shù)為非線性
- 生產(chǎn)安排： 原材料、設(shè)備有限制，總利潤最大（目標(biāo)函數(shù)或約束條件含有非線性變量）
★【例】飛行管理問題。
在約10000m高空的某邊長160km的正方形區(qū)域內(nèi)，經(jīng)常有若干架飛機作水平飛行。區(qū)域內(nèi)每架飛機的位置和速度向量均由計算機記錄其數(shù)據(jù)，以便進行飛行管理。當(dāng)一架欲進入該區(qū)域的飛機到達區(qū)域邊緣時，記錄其數(shù)據(jù)后，要立即計算并判斷是否會與區(qū)域內(nèi)的飛機發(fā)生碰撞。如果會碰撞，則應(yīng)計算如何調(diào)整各架（包括新進入的）飛機飛行的方向角，以避免碰撞。現(xiàn)假定條件如下：
(1) 不碰撞的標(biāo)準(zhǔn)為任意兩架飛機的距離大于8km。
(2) 飛機飛行方向角調(diào)整的幅度不應(yīng)超過30°。
(3) 所有飛機飛行速度均為800km/h。
(4) 進入該區(qū)域的飛機在到達區(qū)域邊緣時，與區(qū)域內(nèi)飛機的距離應(yīng)在60km以上。
(5) 最多需考慮6架飛機。
(6) 不必考慮飛機離開此區(qū)域后的狀況。
請對這個避免碰撞的飛行管理問題建立數(shù)學(xué)模型，列出計算步驟，對以下數(shù)據(jù)進行計
算（方向角誤差不超過0.01度），要求飛機飛行方向角調(diào)整的幅度盡量小。
設(shè)該區(qū)域4個頂點的坐標(biāo)為(0,0)、(160,0)、(160,160)、(0,160)。記錄數(shù)據(jù)見表3.1。
注：方向角指飛行方向與
x
x
x 軸正向的夾角。
為方便以后的討論，引進如下記號：
模型一： 目標(biāo)函數(shù)為所有飛機的調(diào)整量絕對值之和的最小值。
根據(jù)相對運動的觀點在考察兩架飛機
i
i
i 和
j
j
j 的飛行時，可以將
i
i
i 視為不動，而飛機
j
j
j 以相對速度
相對于飛機
i
i
i 運動，對上式進行適當(dāng)?shù)挠嬎?，得?br>
不妨設(shè)
θ
j
≥
θ
i
θ_j ≥ θ_i
θj?≥θi? ，此時相對飛行方向角為，如圖所示：
由于兩架飛機的初始距離為：
因此只要當(dāng)相對非新方向角
β
i
j
β_{ij}
βij? 滿足：
時，兩架飛機就不可能碰撞。
本問題中的優(yōu)化目標(biāo)函數(shù)可以有不同的形式：如使所有飛機的最大調(diào)整量最小，所有飛機的調(diào)整量絕對值之和最小等。這里以所有飛機的調(diào)整量絕對值之和最小為目標(biāo)函數(shù)，可以得到如下的數(shù)學(xué)規(guī)劃模型：
Matlab代碼如下所示：
clc,clear
x0=[150 85 150 145 130 0];
y0=[140 85 155 50 150 0];
q=[243 236 220.5 159 230 52];
xy0=[x0; y0];
d0=dist(xy0); %求矩陣各個列向量之間的距離
d0(find(d0==0))=inf;
a0=asind(8./d0) %以度為單位的反函數(shù)
xy1=x0+i*y0
xy2=exp(i*q*pi/180)
for m=1:6
for n=1:6
if n~=m
b0(m,n)=angle((xy2(n)-xy2(m))/(xy1(m)-xy1(n)));
end
end
end
b0=b0*180/pi;
dlmwrite('txt1.txt',a0,'delimiter', '\t','newline','PC');
dlmwrite('txt1.txt','~','-append'); %往純文本文件中寫LINGO數(shù)據(jù)的分割符
dlmwrite('txt1.txt',b0,'delimiter', '\t','newline','PC','-append','roffset', 1)
求得
α
i
j
0
α^0_{ij}
αij0? 的值如表所示：
求得
β
i
j
0
β^0_{ij}
βij0? 的值如表所示：
該題還有其他思路，可以參考：【數(shù)學(xué)建?！客ㄟ^調(diào)整飛行角度使飛機順利飛行（Matlab）
四、多目標(biāo)規(guī)劃
4.1 引例
簡單理解就是：既要……，又要……。
【例】某工廠生產(chǎn)產(chǎn)品Ⅰ和產(chǎn)品Ⅱ，有關(guān)數(shù)據(jù)下，若只追求最大化利潤，得到模型：
但現(xiàn)在有3個目標(biāo)：①盡量使產(chǎn)品Ⅰ的產(chǎn)量不超過產(chǎn)品Ⅱ的產(chǎn)量；②盡可能充分利用所有設(shè)備；③盡可能使利潤不少于56w。
絕對約束： 模型自帶的約束條件，必須滿足，否則是不可行解。
目標(biāo)約束： 模型中對不等式右端追求的值允許有偏差。
上述三個目標(biāo)使我們要盡可能實現(xiàn)的目標(biāo)。目標(biāo)1是“不超過”，也就是盡量“≤”；目標(biāo)2是“充分利用”，也就是盡量“=”；目標(biāo)3是“不少于”，也就是盡量“>”。
需要衡量每個目標(biāo)的完成情況，并主觀上區(qū)分三個目標(biāo)的重要性，使得整體的完成情況盡量好。
衡量每個目標(biāo)的完成情況：正負(fù)偏差變量，絕對約束和目標(biāo)約束，優(yōu)先因子。
加上與目標(biāo)值差值，減去超過目標(biāo)值的部分。即多退少補，把目標(biāo)函數(shù)變成了等式約束條件。
優(yōu)先因子： 主觀上確定優(yōu)先因子 P k P_k Pk? ，優(yōu)先滿足那個目標(biāo)。
回到最原始的例子，得到多目標(biāo)規(guī)劃模型：
其中，第二個等式代表第一個目標(biāo)：盡量使產(chǎn)品Ⅰ的產(chǎn)量不超過Ⅱ的產(chǎn)量。第三個等式表示第二個目標(biāo)：盡可能充分利用所有設(shè)備。第四個等式表示第三個目標(biāo)：盡可能使利潤不少于56萬。注意這里的優(yōu)化函數(shù)中P體現(xiàn)了重要性。
4.2 Matlab求解
fgoalattain函數(shù)或者序貫算法或者用Lingo求解。
語法格式如下：
[X,FVAL] = fgoalattain(fun,x0,goal,a,b,Aeq,Beq,LB,UB,nonlcon)；
- X 為最終解 ， FVAL為最終解對應(yīng)的函數(shù)值。 注意：求最大值時，結(jié)果FVAL需要取反
- fun是定義的決策函數(shù)，通常通過M文件或者匿名函數(shù)進行定義。 注意：當(dāng)所求為最大值時，系數(shù)需要取反。
- goal為欲達到的目標(biāo)，通常通過linprog函數(shù)先計算得到每個決策函數(shù)目標(biāo)值
- a 為約束條件中不等式組的系數(shù)矩陣 ，a的列數(shù)等于f的列數(shù)。 注意：當(dāng)不等號為 > 或 ≥ 時，矩陣需要取反
- b 為約束條件中不等式組右邊的值。 注意：當(dāng)不等號為 > 或 ≥ 時，矩陣需要取反
- Aeq 為約束條件中等式組的系數(shù)矩陣 ，Aeq的列數(shù)等于f的列數(shù)
- Beq 為約束條件中等式組右邊的值
- LB、UB是解的范圍
- nonlcon 為定義的向量函數(shù)
【例】 求解多目標(biāo)線性規(guī)劃問題。
Matlab求解代碼如下：
a = [-1,-1,0,0;0,0,-1,-1;3,0,2,0;0,3,0,2]; % 不等式約束左邊x系數(shù)
b = [-30;-30;120;48]; % 不等式約束右邊值
c1 = [-100,-90,-80,-70]; % 第一個目標(biāo)函數(shù)的系數(shù)
c2 = [0,3,0,2]; % 第二個目標(biāo)函數(shù)的系數(shù)
fun = @(x)[c1;c2]*x; % 目標(biāo)函數(shù)
[x1,g1] = linprog(c1,a,b,[],[],zeros(4,1)); % 求解第一個目標(biāo)
[x2,g2] = linprog(c2,a,b,[],[],zeros(4,1)); % 求解第二個目標(biāo)
g3 = [g1,g2]; % ★★
[x,fval] = fgoalattain(fun,rand(4,1),g3,abs(g3),a,b,[],[],zeros(4,1)) % abs(g3)為權(quán)重項
運行結(jié)果為：
文章來源：http://www.zghlxwxcb.cn/news/detail-538426.html
參考資料
[1] 數(shù)學(xué)建?！麛?shù)規(guī)劃筆記
[2] 數(shù)學(xué)建模算法與應(yīng)用—整數(shù)規(guī)劃（cvxpy包）
[3] 數(shù)學(xué)建模3.9—多目標(biāo)規(guī)劃文章來源地址http://www.zghlxwxcb.cn/news/detail-538426.html
到了這里，關(guān)于數(shù)學(xué)建模十大算法03—線性規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃、多目標(biāo)規(guī)劃的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
