線性規(guī)劃問題的數(shù)學(xué)模型和標(biāo)準(zhǔn)形式

線性規(guī)劃問題的數(shù)學(xué)模型和標(biāo)準(zhǔn)形式當(dāng)下我們接觸的不論是教科書還是各種學(xué)習(xí)資料，其實很多時候都會存在一個普遍性的問題，就是很多作者為了在追求嚴(yán)謹(jǐn)?shù)幕A(chǔ)上往往會將內(nèi)容寫得晦澀難懂。對于學(xué)習(xí)者來說，很多時候還是很頭疼的。在將來，我也許會不定時分享一些有意思的學(xué)術(shù)文，我會用我自己的理解來表達(dá)出來，可能會有不太嚴(yán)謹(jǐn)?shù)牡胤?，也可能會存在一些錯誤，歡迎各位讀者指正。在這個系列當(dāng)中，我會分享一些關(guān)于數(shù)學(xué)建模的內(nèi)容。但是我自己本身也是一個在學(xué)習(xí)階段的數(shù)模小白，所以我就單純分享一些較為基礎(chǔ)的學(xué)習(xí)筆記。今天這篇分享的是數(shù)學(xué)建模里的第一個模型——線性規(guī)劃。在這篇文章里的例子均是在網(wǎng)上摘錄的，如果碰到相似的部分就是我借鑒的。什么是線性規(guī)劃問題？首先我們先理解一下什么是線性線性這個詞在我們的學(xué)習(xí)過程中還是挺經(jīng)常會碰見的。從定義上來說，只要兩個變量之間表現(xiàn)為一次函數(shù)關(guān)系，則這兩個變量就呈現(xiàn)出線性關(guān)系。在幾何意義上表示為直線。因此僅有一次函數(shù)參與的問題就可稱之為線性問題。由線性可以引出兩條代數(shù)性質(zhì)若f(x)為線性函數(shù)1）可加性2）比例性兩則性質(zhì)相結(jié)合可知請在初高中的學(xué)習(xí)階段我們可能會遇到這樣的問題：根據(jù)高中線性規(guī)劃問題的做法，具體解題過程如下：這就是簡單的線性規(guī)劃問題，線性規(guī)劃其實就是研究線性約束條件下線性目標(biāo)函數(shù)的極值問題。數(shù)學(xué)建模中的線性規(guī)劃問題數(shù)學(xué)建模中的線性規(guī)劃問題則會更貼近我們的生活以及生產(chǎn)實踐日常，在已知條件下去找到最優(yōu)方案等。在接下來筆者會通過一道具體例子來進(jìn)行展開解釋。例.某機床廠生產(chǎn)甲、乙兩種機床，每臺銷售后的利潤分別為4000元與3000元。生產(chǎn)甲機床需用A、B機器加工，加工時間分別為每臺2小時和1小時；生產(chǎn)乙機床需用A、B、C三種機器加工，加工時間為每臺各一小時。若每天可用于加工的機器時數(shù)分別為A機器10小時、B機器8小時和C機器7小時，問該廠應(yīng)生產(chǎn)甲、乙機床各幾臺，才能使總利潤最大？

根據(jù)現(xiàn)有的數(shù)學(xué)知識很容易可以做出如下分析：在這里為了為后續(xù)代碼部分做鋪墊，筆者將約束條件分成以下三類1.不等式約束條件（上述式子中的1、2、3式）2.等式約束條件（上述式子中未出現(xiàn)，其實就是一次方程或一次方程組）3.決策變量的最小取值和最大取值（上述式子中的4式）線性規(guī)劃問題在Matlab中的具體代碼實現(xiàn)在數(shù)學(xué)建模當(dāng)中python也同樣可以實現(xiàn)相同的功能，筆者在這里采用matlab進(jìn)行具體問題解決。有關(guān)matlab的基礎(chǔ)語法在這里就不進(jìn)行過多的解釋。對于有一定編程基礎(chǔ)的來說，matlab一定不算太難的。在matlab標(biāo)準(zhǔn)型中，所求目標(biāo)函數(shù)為最小值（若要求最大值，則在此基礎(chǔ)上對目標(biāo)函數(shù)兩邊乘一個負(fù)號即可），同時要求約束條件必須為小于等于號或者等于號（若約束條件中出現(xiàn)大于等于號，則需在不等式兩邊乘上負(fù)號使其變號）。Linprog函數(shù)是解決線性規(guī)劃問題的代碼核心linprog函數(shù)標(biāo)準(zhǔn)形式為[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub)其中x為返回最優(yōu)解的變量取值，fval為返回目標(biāo)函數(shù)的最優(yōu)值。右邊的參數(shù)會在后面進(jìn)行相應(yīng)的解釋。接下來的部分會涉及一些有關(guān)線性代數(shù)的知識，當(dāng)然涉及的部分也不算太難。我們將其標(biāo)準(zhǔn)形式中的多個參數(shù)分別對應(yīng)到剛才闡釋過的目標(biāo)函數(shù)及三類約束條件來理解。1、參數(shù)ff表示的含義為目標(biāo)函數(shù)中的系數(shù)列向量。由于我們所求的是最大值，不滿足matlab所求的應(yīng)為最小值的要求，所以我們要先將目標(biāo)函數(shù)等式左右兩邊乘上負(fù)號。即目標(biāo)函數(shù)變?yōu)椋阂虼嗽诖a中f=[-4000;-3000]注意：由于是列向量，在代碼中相鄰之間是“;”而不是“,”。2、不等式約束條件中的參數(shù)A:不等式約束條件中的變量系數(shù)矩陣b:不等式約束條件中的常數(shù)項矩陣在該例中1、2、3不等式可以整合成如下矩陣形式在具體的代碼中呈現(xiàn)為：A=[2,1;1,1;0,1]b=[10;8;7]注意：若出現(xiàn)大于等于號，要在不等式兩邊同乘上一個負(fù)號，將其轉(zhuǎn)換為小于等于號。3、等式約束條件中的參數(shù)Aeq:等式約束條件的系數(shù)矩陣beq:等式約束條件的常數(shù)項矩陣在該例中未出現(xiàn)等式約束條件，在這里筆者舉一個例子假設(shè)存在這樣一組等式約束條件：由此我們可以轉(zhuǎn)換成矩陣形式：具體代碼寫作：Aeq=[1,1,1;0,2,3;2,0,0]beq=[7;0;14]4、決策變量的約束lb:決策變量的最小取值ub:決策變量的最大取值在這里我們也要將4式轉(zhuǎn)換為矩陣形式：即lb=[0;0]在這一例子當(dāng)中沒有決策變量的上界約束。關(guān)于linprog函數(shù)的調(diào)用細(xì)節(jié)細(xì)心的讀者讀到這里已經(jīng)會發(fā)現(xiàn)，在我們的例子當(dāng)中缺少了等式約束條件，同時也沒有決策變量的最大取值，但是在Matlab的linprog函數(shù)的標(biāo)準(zhǔn)形式中卻有這些參數(shù)，我們在調(diào)用的時候該如何處理呢？總體遵循以下規(guī)則：1、若從某一參數(shù)開始，后續(xù)的參數(shù)均不存在，則后續(xù)的均可省略不寫2、若在中間有出現(xiàn)參數(shù)缺失的情況，用“[]”在函數(shù)中進(jìn)行占位詳情見以下代碼及結(jié)果：由結(jié)果可知最優(yōu)方案為生產(chǎn)2臺甲機床和生產(chǎn)6臺乙機床，此時可以收獲最大利潤26000元。總結(jié)線性規(guī)劃的研究成果還推動著其他數(shù)學(xué)問題包括整數(shù)規(guī)劃、隨機規(guī)劃和非線性規(guī)劃的算法研究。在本篇文章中的具體例子為較為淺顯的情況，希望讀者能從中有所收獲。

數(shù)學(xué)建模常見最值求法——簡單的線性規(guī)劃問題

在建模賽題我們常常會遇到如何利用現(xiàn)有資源來安排生產(chǎn)，以取得最大經(jīng)濟效益的問題，實際上此類問題在生產(chǎn)實踐中也很常見。此類問題構(gòu)成了運籌學(xué)的一個重要分支—數(shù)學(xué)規(guī)劃，而線性規(guī)劃(LinearProgramming簡記LP)則是數(shù)學(xué)規(guī)劃的一個重要分支。1、線性規(guī)劃的實例與定義例1

某機床廠生產(chǎn)甲、乙兩種機床，每臺銷售后的利潤分別為4000

元與3000

元。生產(chǎn)甲機床需用A、B機器加工，加工時間分別為每臺2小時和1小時；生產(chǎn)乙機床

需用A、B、C三種機器加工，加工時間為每臺各一小時。若每天可用于加工的機器時數(shù)分別為A機器10

小時、B機器8小時和C機器7小時，問該廠應(yīng)生產(chǎn)甲、乙機床各幾臺，才能使總利潤最大？上述問題的數(shù)學(xué)模型：設(shè)該廠生產(chǎn)x?臺甲機床和x?乙機床時總利潤最大，則x?和x?應(yīng)滿足：這里變量x?和x?稱之為決策變量，（1）式被稱為問題的目標(biāo)函數(shù)，（2）中的幾個不等式是問題的約束條件，記為s.t.(即subjectto)。由于上面的目標(biāo)函數(shù)及約束條件均為線性函數(shù)，故被稱為線性規(guī)劃問題。線性規(guī)劃問題是在一組線性約束條件的限制下，求一線性目標(biāo)函數(shù)最大或最小的問題。2、線性規(guī)劃的Matlab

標(biāo)準(zhǔn)形式

線性規(guī)劃的目標(biāo)函數(shù)可以是求最大值，也可以是求最小值，約束條件的不等號可以是小于號也可以是大于號。為了避免這種形式多樣性帶來的不便，Matlab

中規(guī)定線性規(guī)劃的標(biāo)準(zhǔn)形式為其中c

和x

為n

維列向量，A

、Aeq

為適當(dāng)維數(shù)的矩陣，b、beq為適當(dāng)維數(shù)的列向量。例如線性規(guī)劃的Matlab標(biāo)準(zhǔn)型為3、線性規(guī)劃問題的解的概念

一般線性規(guī)劃問題的（數(shù)學(xué)）標(biāo)準(zhǔn)型為可行解：滿足約束條件（4）的解x

=

(

x?，x?,...,xn

)

，稱為線性規(guī)劃問題的可行解，而使目標(biāo)函數(shù)（3）達(dá)到最大值的可行解叫最優(yōu)解。

可行域：所有可行解構(gòu)成的集合稱為問題的可行域，記為R。4、

線性規(guī)劃的圖解法圖解法簡單直觀，有助于了解線性規(guī)劃問題求解的基本原理。我們先應(yīng)用圖解法來求解例1。對于每一固定的值z，使目標(biāo)函數(shù)值等于z的點構(gòu)成的直線稱為目標(biāo)函數(shù)等位線，當(dāng)z變動時，我們得到一族平行直線。對于例1，顯然等位線越趨于右上方，其上的點具有越大的目標(biāo)函數(shù)值。不難看出，本例的最優(yōu)解為x*

=

(2,6)T，最優(yōu)目標(biāo)值z*

=26。從上面的圖解過程可以看出并不難證明以下斷言：（1）可行域R可能會出現(xiàn)多種情況。R可能是空集也可能是非空集合，當(dāng)R非空

時，它必定是若干個半平面的交集（除非遇到空間維數(shù)的退化）。R既可能是有界區(qū)域，也可能是無界區(qū)域。（2）在R

非空時，線性規(guī)劃既可以存在有限最優(yōu)解，也可以不存在有限最優(yōu)解（其目標(biāo)函數(shù)值無界）。（3）若線性規(guī)劃存在有限最優(yōu)解，則必可找到具有最優(yōu)目標(biāo)函數(shù)值的可行域R的“頂點”。5、求解線性規(guī)劃的Matlab解法

單純形法是求解線性規(guī)劃問題的最常用、最有效的算法之一。這里我們就不再介紹單純形法。下面我們介紹線性規(guī)劃的Matlab解法。Matlab

中線性規(guī)劃的標(biāo)準(zhǔn)型為基本函數(shù)形式為linprog(c,A,b)，它的返回值是向量x的值。還有其它的一些函數(shù)調(diào)用形式（在Matlab指令窗運行helplinprog可以看到所有的函數(shù)調(diào)用形式），如：

[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)這里fval返回目標(biāo)函數(shù)的值，LB和UB

分別是變量x

的下界和上界，X

0是X

的初始值OPTIONS是控制參數(shù)。例2

求解下列線性規(guī)劃問題解

（i）編寫M

文件

c=[2;3;-5];a=[-2,5,-1;1,3,1];b=[-10;12];aeq=[1,1,1];beq=7;x=linprog(-c,a,b,aeq,beq,zeros(3,1))value=c'*