基礎(chǔ)數(shù)學(xué)建模（1）線性規(guī)劃問題

線性規(guī)劃模型（IP）

線性規(guī)劃（linear problem）的發(fā)展曾被20世紀(jì)中期稱為最重要的科學(xué)進(jìn)展之一，這以評估也奠定了線性規(guī)劃模型在數(shù)學(xué)應(yīng)用和工程管理等領(lǐng)域的重要學(xué)術(shù)地位，今天我們就來探討一下線性規(guī)劃中子問題------整數(shù)規(guī)劃的魅力。

這里雖然探討的是數(shù)學(xué)建模的內(nèi)容，但是屬于管理類和工程類的學(xué)科同學(xué)，有時間可以直接學(xué)習(xí)《運籌學(xué)》或者《管理運籌學(xué)》這類的書籍。運籌學(xué)這門學(xué)科是直接從數(shù)學(xué)理論基礎(chǔ)的角度解釋相當(dāng)一部分模型，是對模型更加深入的理論探討的學(xué)科，學(xué)有余力的同學(xué)可以認(rèn)真研究相關(guān)內(nèi)容。

數(shù)學(xué)規(guī)劃通俗的來講就是通過數(shù)學(xué)建?；蛘呓?shù)學(xué)方程組，建立關(guān)于問題的符號公式和數(shù)學(xué)關(guān)系，從而求解一定的實際問題的數(shù)學(xué)方法。

數(shù)學(xué)規(guī)劃中的變量（部分或全部）限制為整數(shù)時，稱為整數(shù)規(guī)劃。整數(shù)規(guī)劃是線性規(guī)劃模型的一個子分支，當(dāng)線性規(guī)劃模型中的所有變量被限制為整數(shù)時，我們將這個線性規(guī)劃問題統(tǒng)稱為整數(shù)線性規(guī)劃問題。
當(dāng)線性規(guī)劃中變量是普通的值的時候，我們直接稱為線性規(guī)劃，線性規(guī)劃中的變量一般都是大于0的，當(dāng)然也存在部分變量沒有限制的特殊情況。
對于整數(shù)規(guī)劃來說，還有一類問題叫做混合整數(shù)規(guī)劃，未來的日子，我們帶領(lǐng)大家詳細(xì)做這些問題的研究。

Part01.線性規(guī)劃簡單介紹

現(xiàn)在我們舉個例子大概講解一下線性規(guī)劃模型。有相關(guān)基礎(chǔ)的同學(xué)可以直接略過。

假設(shè)我們遇到一個問題，小王和小李共同經(jīng)營了一家公司，雙方都進(jìn)行投資。小王希望經(jīng)營電商相關(guān)的業(yè)務(wù)，而小李希望經(jīng)營軟件相關(guān)的業(yè)務(wù)，于是他們共同決定根據(jù)自身愛好分別對兩個業(yè)務(wù)進(jìn)行投資，其中投資的相關(guān)數(shù)據(jù)如下：

業(yè)務(wù) 電商單位花費 軟件單位花費 資金限制
小王 30 20 4250
小李 15 40 4300
獲得的利潤 20 30

現(xiàn)在詢問，如何進(jìn)行投資才能使得小王和小李的總利潤最多。

通過上面的數(shù)據(jù)，我們可以進(jìn)行簡單的數(shù)學(xué)假設(shè)。

設(shè)小王和小李的針對不同業(yè)務(wù)的投資設(shè)施量分別為x_{ij}。i代表小王小李，j代表不同業(yè)務(wù)。所以根據(jù)線性代數(shù)的相關(guān)分析，我們可以建立一個線性方程組如下：

我們需要小王和小李的資金不超過自己的承擔(dān)水平：
所以建立方程組：
\left\{\begin{matrix} \ 20x_{11}+20x_{12}\leqslant 4250 \\15x_{21}+40x_{22}\leqslant 4300 \\x_{ij} \geqslant 0 \end{matrix}\right.
這個方程組相比大家都是非常樂于求解的，當(dāng)然在線性代數(shù)中，不等式應(yīng)該是等式才比較合適。
這個問題到了這一步并沒有結(jié)束，這里我們應(yīng)該針對問題的目標(biāo)添加一個目標(biāo)函數(shù)，如下：
max \space z = 20\sum_{i=1}^2x_{i1} + 30\sum_{i=1}^2x_{i2}
這個方程表示了最終要獲得的利潤應(yīng)該是最大的。通過上述兩個方程，我們可以將方程組組建為如下模型：
max \space z = 20\sum_{i=1}^2x_{i1} + 30\sum_{i=1}^2x_{i2} \\s.t. \left\{\begin{matrix} \ 20x_{11}+20x_{12}\leqslant 4250 \\15x_{21}+40x_{22}\leqslant 4300 \\x_{ij} \geqslant 0 \end{matrix}\right.

注釋：上述中的s.t.表示“使得”的意思，這個應(yīng)該在高中數(shù)學(xué)中講過，s.t.英文全稱是subject to 。

對于上述模型，我們可以進(jìn)行一個簡單的歸納，上述方程用普通方法描述，可以寫為如下公式：
max \space z = \sum_{i=1}^n\sum_{j=1}^nc_{ij}x_{ij} \\s.t. \left\{\begin{matrix} \\ Ax \leqslant b \\ A_{equ}x = b_{equ} \\x_{ij} \geqslant 0 \end{matrix}\right.
A大家應(yīng)該都知道什么東西，線性知識點是貫穿數(shù)學(xué)建模的整個體系的一塊知識內(nèi)容。
至此，我們對線性規(guī)劃的建模講述完畢。

Part02.線性規(guī)劃的求解

針對上述線性規(guī)劃模型，我們可以手動編寫python程序進(jìn)行求解，使用的還是線性代數(shù)或者運籌學(xué)書中的相關(guān)知識。也可以編寫matlab或者lingo程序進(jìn)行求解。
一般情況下，求解線性規(guī)劃的方法稱為單純型法，但是由于求解過程復(fù)雜，這里不在敘述，有興趣的同學(xué)可以詳細(xì)學(xué)習(xí)運籌學(xué)書中的相關(guān)知識。而對于python來說，學(xué)好單純形法是解決問題的基礎(chǔ)，所以python這里也不再和大家講解了。
這里使用matlab的相關(guān)程序進(jìn)行講解，當(dāng)然求解單純形法的工具還有很多，比如杉樹科技公司研究了一款求解器，目前從學(xué)術(shù)領(lǐng)域來說，是比較好用的工具，據(jù)說這款求解器的求解速度已經(jīng)達(dá)到全球領(lǐng)先。又況且這個公司是我國一些學(xué)者自主自建的公司，有一定的科技主導(dǎo)爭取意識，有興趣的同學(xué)可以增加涉獵知識深度，對這些公司的求解器和公司研究做一些了解。其余的求解器大部分以美國研究為主，有興趣同學(xué)可以進(jìn)行探索。

01.線性規(guī)劃模型標(biāo)準(zhǔn)化

我們根據(jù)教材中的內(nèi)容，對上述模型進(jìn)行規(guī)范性書寫，也就是標(biāo)準(zhǔn)化：
max \space z = \sum_{i=1}^n \sum_{j=1}^n c^Tx_{ij} \\s.t. \left\{\begin{matrix} \ Ax \leqslant b \\ A_{equ}x = b_{equ} \\lb \leqslant x_{ij} \leqslant ub \end{matrix}\right.
其中：
\\c = [c_1 \space c_2 \space ... \space c_m] \\ x = [ x_1 \space x_2 \space ... \space x_m]^T \\ b = [ b_1 \space b_2 \space ... \space b_n]^T \\ A =[a_{11}\space a_{12}\space ...\space a_{1m}\\ a_{21}\space a_{22}\space .... \space a_{2m}\\ ...\space ...\space ... \space...\\ a_{n1}\space a_{n2}\space...\space a_{nm}]_{n \times m}
A_{equ}x 和 b_{equ} 類似，equ表示等式約束情況下的矩陣表示.
lb表示x的下界,ub表示上界。
此時便可以使用matlab函數(shù)進(jìn)行計算，計算過程如下：

[x,fval]=linprog(c,A,b)
[x,fval]-linprog(c,A,b,Aeq,beq)
[x,fval]-linprog(c,A,b,Aeq,beq,lb,ub)

注釋：這里的c和b向量在輸入的時候，都是按照行向量進(jìn)行輸入，x表示結(jié)果，fval表示目標(biāo)函數(shù)的值。

到這里，線性規(guī)劃的基礎(chǔ)知識講解便結(jié)束了，有問題的可以關(guān)注公眾號 binder的學(xué)習(xí)空間 后臺留言咨詢，也可以直接在評論區(qū)留言。

數(shù)學(xué)建模相關(guān)學(xué)習(xí)資源推薦：
1.B站的數(shù)學(xué)建模相關(guān)教程（推薦老哥建模）
2.中文版《運籌學(xué)》（推薦使用清華大學(xué)出版的《管理運籌學(xué)》)
3.推薦使用英文版運籌學(xué)書籍《Introduction of operating Research》

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

相關(guān)閱讀更多精彩內(nèi)容

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