【數(shù)學(xué)建模算法】（1）線性規(guī)劃的基本形式

由于本人正在籌備9月的研究生數(shù)學(xué)建模比賽，所以需要學(xué)習(xí)數(shù)學(xué)建模的相關(guān)知識(shí)，想把一些學(xué)習(xí)的心得和成果分享給大家，第一部分就是數(shù)學(xué)建模中涉及的基本算法，從今天開始我將不定期更新關(guān)于數(shù)學(xué)建模中的基本算法知識(shí)以及Matlab實(shí)現(xiàn)過程，希望大家捧場。

線性規(guī)劃的定義及舉例

線性規(guī)劃這個(gè)詞相信大家并不陌生，但可能由于年代久遠(yuǎn)大家忘記了它是什么，那我們就看一道例題：

例1 某機(jī)床廠生產(chǎn)甲、乙兩種機(jī)床，每臺(tái)銷售后的利潤分別為4000與3000元。生產(chǎn)甲機(jī)床需用A,B兩種機(jī)器加工，加工時(shí)間分別為每臺(tái)2小時(shí)和1小時(shí)；生產(chǎn)乙機(jī)床需用A，B，C三種機(jī)器加工，加工時(shí)間為每臺(tái)各一小時(shí)。若每天可用于加工的機(jī)器時(shí)數(shù)分別為A機(jī)器10小時(shí)、B機(jī)器8小時(shí)和C機(jī)器 7小時(shí)，問該廠應(yīng)生產(chǎn)甲、乙機(jī)床各幾臺(tái)，才能使總利潤最大？

怎么做這道題呢，讓我們把已知條件列出來：

消耗工時(shí)如下表：

甲 乙
A 2 1
B 1 1
C 0 1

問題中給出了每臺(tái)機(jī)器每天的最大工作時(shí)間

A B C
最大工作時(shí)間 10 8 7

也給出了甲乙兩種機(jī)床的利潤

甲 乙
利潤 4000 3000

假設(shè)生產(chǎn)甲機(jī)床x_{1}臺(tái)和乙機(jī)床x_{2}臺(tái)時(shí)，利潤最大。
那么設(shè)z為總利潤，我們的任務(wù)目標(biāo)就是讓z=4000 x_{1}+3000 x_{2}最大。(1)
而限制條件是：
\left\{\begin{array}{l}{2 x_{1}+x_{2} \leq 10} \\ {x_{1}+x_{2} \leq 8} \\ {x_{2} \leq 7} \\ {x_{1}, x_{2} \geq 0}\end{array}\right.

上式（1）稱為問題的目標(biāo)函數(shù)，上式(2)稱為該問題的限制條件。
上面這個(gè)問題就是一個(gè)完整的線性規(guī)劃問題。

線性規(guī)劃問題的標(biāo)準(zhǔn)形式

目標(biāo)函數(shù)
\max \quad z=\sum_{j=1}^{n} c_{j} x_{j}
限制條件
\left\{\begin{array}{l}{\sum_{j=1}^{n} a_{i j} x_{j}=b_{i} \quad i=1,2, \cdots, m} \\ {x_{j} \geq 0 \quad j=1,2, \cdots, n}\end{array}\right.

滿足限制條件的解稱為可行解，既滿足限制條件又能使目標(biāo)函數(shù)達(dá)到最值的解稱為最優(yōu)解。所有可行解構(gòu)成的集合稱為可行域R。

Matlab中解決線性規(guī)劃問題的標(biāo)準(zhǔn)形式

目標(biāo)函數(shù)
\min _{x} c^{T} x

注意Matlab中的標(biāo)準(zhǔn)形式是讓目標(biāo)函數(shù)最小。

限制條件
\left\{\begin{array}{l}{A x \leq b} \\ {A e q \cdot x=b e q} \\ {l b \leq x \leq u b}\end{array}\right.

第一行是不等式限制條件。
第二行是等式限制條件。
第三行是自變量范圍。

其中c,x是n維列向量，A,Aeq是適當(dāng)維數(shù)的矩陣，b,beq是適當(dāng)維數(shù)的列向量。

Matlab中的線性規(guī)劃問題函數(shù)原型為：

[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS];
%x是最優(yōu)自變量，fval是對應(yīng)最優(yōu)值，LB和UB是x的上下界，X0是X的初值，OPTIONS是控制參數(shù)。

我們高中時(shí)學(xué)過一種線性規(guī)劃問題的求解算法———圖解法，其思想是在直角坐標(biāo)系中畫出限可行域，之后用代表目標(biāo)函數(shù)的直線族來掃過可行域來確定自變量的最優(yōu)解。


圖解法

不適用于此處，不再過多討論。

利用Matlab解決線性規(guī)劃問題

例1
仍然以上題為例，其目標(biāo)函數(shù)和限制條件為：

\max \quad z=4000 x_{1}+3000 x_{2}
\left\{\begin{array}{l}{2 x_{1}+x_{2} \leq 10} \\ {x_{1}+x_{2} \leq 8} \\ {x_{2} \leq 7} \\ {x_{1}, x_{2} \geq 0}\end{array}\right.

本題中目標(biāo)函數(shù)不符合Matlab標(biāo)準(zhǔn)型，只需將c^{T} x變?yōu)?img class="math-inline" src="https://math.jianshu.com/math?formula=-c%5E%7BT%7D%20x" alt="-c^{T} x" mathimg="1">（即代入時(shí)將c替換為-c即可）就可將求取最大值變?yōu)榍笕∽钚≈?，即可用matlab求解。

求解代碼：

c=[4000 3000];
A=[2 1;
    1 1;
    0 1];
b=[10 8 7]';
Aeq=[];
beq=[];
LB=zeros(2,1);

x=linprog(-c,A,b,Aeq,beq,LB);
%將-c替換成了c，此時(shí)函數(shù)輸出的最優(yōu)值是-c*x，不是我們想要的最優(yōu)值，若需要最優(yōu)值，需要自行計(jì)算c*x

輸出x

x =

    2.0000
    6.0000

問題求解完畢。

例2
\max z=2 x_{1}+3 x_{2}-5 x_{3}
x_{1}+x_{2}+x_{3}=7
2 x_{1}-5 x_{2}+x_{3} \geq 10（*）
x_{1}+3 x_{2}+x_{3} \leq 12
x_{1}, x_{2}, x_{3} \geq 0

本題中出現(xiàn)了不等號(hào)方向不符合標(biāo)準(zhǔn)型的情況，同理，需要先將不等號(hào)進(jìn)行調(diào)整，再代入Matlab函數(shù)進(jìn)行求解。
本題中，（*）標(biāo)注的不等式是"\geq"號(hào)，若要將其變?yōu)椤?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Cleq" alt="\leq" mathimg="1">”，需左右兩邊加一個(gè)“-”號(hào)。

代碼求解：

c=[2 3 -5];
A=[-2 -5 -1;%這一行不等式經(jīng)過調(diào)整，左右取負(fù)號(hào)
    1 3 1];
b=[-10 12]';
Aeq=[1 1 1];
beq=[7];
LB=zeros(3,1);

x=linprog(-c,A,b,Aeq,beq,LB);%由于目標(biāo)函數(shù)要求取最大值，所以此處代-c

求得：

x =

    4.5000
    2.5000
         0

至此，線性規(guī)劃問題的基本形式和基本解法就展示完了，下一部分，我們將會(huì)討論一些利用線性規(guī)劃思想解決的實(shí)際問題。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容