數學模組化基本算法模型Charpter1--線性規劃（LP）

By 進棧需檢票

一、線性規劃基本概念

1.Linear Programming （LP問題）

列出方程組不等式求解（基本形式）

包含目标函數以及限制條件

目标函數及限制條件均為線性函數，故稱為線性規劃問題，目标是求解目标函數最大最小的問題

關鍵：如何吧問題歸結成一個線性規劃問題，以及模型的建構是否恰當，這就需要找到合适的決策變量

Attention：前面的s.t.就是限制條件的意思，在論文中間寫出來表示其專業性

a.可行解：滿足限制條件（4）的解

b.最優解：使得目标函數（3）達到最大值的可行解成為最優解

c.可行域：所有可行解構成的集合稱為問題的可行域，記作R

2.應用情況

注意：“線性”意味着所有的變量都是一次方

超過一次方就屬于非線性規劃

①“怎麼安排/配置設定”、“盡量多（少）”、"最多（少）"、“利潤最大”、“最合理”

②生産安排：原材料、裝置有限制、總利潤最大

③投資收益：資産配置、收益率、損失率、組合投資、總收益最大（總收益率則不是線性規劃）

④銷售運輸：産地、銷量、産量、銷量、運費、總運費最省

⑤車輛安排：路線、起點終點、承載量、時間點、車次安排最合理

⑥還有的就是整數規劃和0-1規劃，往往預設為線性規劃問題

二、Matlab的線性規劃标準以及軟體求解

1.功能簡介

“雖然Matlab自帶函數，但是你必須将資料化成其支援的形式，例如，隻求最小值不能直接求最大值，要求最大值則将資料整理為負數然後求負數的最小值，絕對值後則是原目标函數的最大值”

同樣的，隻支援小于等于和等于，若是大于等于則一樣的要化作負數進行計算轉化

（價值向量為f，minf^Tx）資源向量：問題資源（金錢）的總和，也就是最關鍵的限制因素

(1)每個模型都有若幹個決策變量(x1,x2,x3,…,xn), 其中n 為決策變量個數。決策變量的一組值表示一種方案,同時決策變量一般是非負的。

(2)目标函數是決策變量的線性函數,根據具體問題可以是最大化(max)或最小化 (min),二者統稱為最優化(opt)。

(3)限制條件也是決策變量的線性函數。

2.函數功能介紹

x傳回的最優解為變量範圍，fval傳回的目标函數的最優解

f價值向量，為列向量

A不等式限制條件的變量系數矩陣，b不等式限制條件的常數項矩陣

Aeq等式限制條件的系數矩陣，beq等式限制條件的常數項矩陣

lb決策變量的最小值 ub決策變量的最大值（自變量的取值範圍）

使用特例：

①若不存在不等式限制，用[ ]來代替A與b

②若不存在等式限制，用[ ]來代替Aeq與beq

③沒有等式限制和最大最小的取值限制的時候，可以不寫Aeq，beq，lb以及ub

④若求最大值，先取負号得出結論之後再去絕對值得到正确的最大值解

三、簡單的使用案例

1.單純形線性規劃

Example1 -- 簡單的線性回歸1

f = [-5 , -4 , -6];
A = [1 -1 1
     3 2 4
     3 2 0];
b = [20 , 42 , 30];
lb = [0 , 0 , 0];
ub = [inf , inf , inf];
Aeq = [];
beq = [];
[x , fval] = linprog(f , A , b , Aeq , beq , lb , ub);
x
fval

輸出結果：

Optimal solution found.


x =

         0
   15.0000
    3.0000


fval =

   -78

Example2 -- 簡單的線性回歸（zeros(3 , 1)）

對于求這個max，記得f一定要求負數的形式，以及後面的A，Aeq，以此類推

f = [-2 , -3 , 5];
A = [-2 5 -1
     1  3  1];
b = [-10 , 12];
Aeq = [1 , 1 , 1];
beq = 7;
ub = [inf , inf , inf];
lb = [0 , 0 , 0];
[x , fval] = linprog(f , A , b , Aeq , beq , lb , ub);
x
fval
-fval

當然，對于後面的lb，我們還可以寫成zeros(3 , 1)

也就是三行一列的行列式中的元素全部為0，其實也就是

ub = inf，在函數中可以忽略或者用[ ]代替使用

也就是：

[x , fval] = linprog(f , A , b , Aeq , beq , zeros(3 , 1));

Example3 -- 方程整體優化問題之[x,fval,exitflag,output,lambda]=linprog(...)

■ [x,fval,exitflag]=linprog(...)———傳回exitflag值,描述函數計算的退出條件。

■ [x,fval,exitflag,output]= linprog(...)———返回包含優化信息的輸出變量 output。

■ [x,fval,exitflag,output,lambda]=linprog(...)———将解x處的 Lagrange乘子返 156 回到lambda參數中。

clear all
f = [-5 , -4 , -6];
A = [1 -1 1
     3 2  4
     3 2  0];
b = [20 , 42 , 30];
Aeq = [ ];
beq = [ ];
lb = zeros(3 , 1);
ub = [inf , inf , inf];
[x , fval , exitflag , output , lamba] = linprog(f , A , b , Aeq , beq , lb , ub);
x
fval
exitflag
output
lamba

exitflag = 1表示過程正常收斂于解x 處。

Example4 -- 絕對值問題的線性規劃轉化思考

貌似不是線性規劃問題，但是可以通過相關的代數變換來使其成為所謂的線性規劃問題

Example5 -- 線性規劃在金融分析的實際問題

基本概況：

①首先，來一波符号定義

②然後來個基本假設

在這裡的假設也是很重要的，比如（4）這個獨立性問題，假如沒有在這路單獨提出來，評委可能就會在這個點上去提問，是以，完備的假設是成功的前提以及後續實驗的邏輯支撐

這些邏輯包括基本邏輯，類似（2）以及這個研究問題的操作性假設，例如（5）（6）這些影響結果和計算精确度的因素

③模型的建構

首先需要确定題目的已知條件

同時，由題目所知，總體風險是是可用投資Si中最大的那一個

通過分析（u_i的值不受影響），我i們分析出淨收益率：

然後就是分析現有的題目目标

也就是讓收益盡可能大，總體風險盡可能小

這是一個多目标的線性規劃問題

得出目标函數以及限制條件！！！

目标函數：

此所謂收益盡可能大

此所謂總體風險盡可能小

限制條件：

進行模型的分析、列舉以及篩選

這裡的模型将我們原型中的min(max{qixi})進行了轉化，通過一個風險率qixi/M來進行相應的限制，這樣做不僅讓評委能夠更好的了解，同時也讓整個模型分析的水準上了一個台階

同樣的，在模型二中，淡化了風險，增強了收益這個目标

模型一模型二的轉化其實就是将兩個目标函數（多目标的線性規劃）中的一個或者多個轉化到限制條件，進行模型的簡化以及可能性的提升

兩個變量不是不可以求解，而是根據不同的實際情況進行分别的分析了解計算模組化

模型三就是兩種變量情況都算在考慮之中，賦予不同的權重來表示其實際情況

變量的綜合分析以及使用才是思考的重點

模型三是推薦的一種模組化方式

将模型計算翻譯為Matlab的了解形式

#模型一

代碼書寫建構

#模型一

a = 0;
hold on
while a < 0.05
    f = [-0.05 , -0.27 , -0.19 , -0.185 , -0.185];
    A = [zeros(4 , 1) , diag([0.025 , 0.015 , 0.055 , .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(f , A , b , Aeq , beq , LB);
    Q = -Q;
    plot(a , Q , '*k');
    a = a + 0.001;
end
xlabel('a') , ylabel('Q')

得出結論

#模型一

2.多目标線性規劃

目标線性規劃：

限制條件：

1.理想點法

是以在這樣的題目條件下做題的順序就是先把一個個情況的求解出來，之後就是用minw[Z(x)]去求得真正的解，使用Matlab中的fmincon

Example6

①求解f1(x)最優解

clear all
clc
f= [3 , -2]; 
A= [2 3 
    2 1];    
b= [18 , 10];
lb= [0 , 0];
[x , fval] =linprog(f , A , b , [ ] , [ ] , lb);
x
fval

------------
Output

x =
    0.0000
    6.0000
fval =
    -12.0000

即最優解為12

②求解f2(x)最優解

f = [-4 , -3];
A = [2 , 3
     2 , 1];
b = [18 , 10];
lb = [0 , 0];
[x , fval] = linprog(f , A , b , [ ] , [ ] , lb);
x
fval

------------
Output

x =
  3.0000
  4.0000
fval =
  -24.0000

即最優解為24

③綜合公式求解該模型的最優解

A = [2 , 3
     2 , 1];
b = [18 , 10];
lb = [0 , 0];
x0 = [1 , 1];
x = fmincon('((-3*x(1)+2*x(2)-12)^2+(4*x(1)+3*x(2)-24)^2)^(1/2)' , x0 , A , b , [ ] , [ ] , lb , [ ]);
x

------------
Output
x =
  0.5268
  5.6488

這樣求出來的x1 , x2就是滿足以上兩個條件的最優解了

2.線性權重和法

相較于理想點法的不同，這個方法注重于題目給的目标函數是基于一個權重配置設定的形式。

Example7

f = [-0.5 , -2.5];
A = [2 , 3
     2 , 1];
b = [18 , 10];
lb = [0 , 0];
x = linprog(f , A , b , [ ] , [ ] , lb);
x

------------
Output
x =
  0.0000
  6.0000

其實就是兩個或多個函數根據一定的權重比例組合到一個目标函數裡面，再使用linprog函數進行求解，過程與單純性線性規劃一緻

3.最大最小法

例如Example5的目标函數的建構

Example8

function f = crition2022(x)
f(1) = 3*x(1) - 2*x(2);
f(2) = -4x*(x) - 3*x(2);

clear all
clc
x0 = [1 , 1];
A = [2 , 3
     2 , 1];
b = [18 , 10];
lb = zeros(2 , 1);
[x , fval] = fminimax('crition2022' , x0 , A , b , [ ] , [ ] , lb , [ ]);
x
fval

------------
Output
x =
  0
  6
fval =
  -12  -18

數學模組化基本算法模型Charpter1--線性規劃（LP）