數(shù)學(xué)建模專題

數(shù)學(xué)建模專題

——柏慶國中國古代馬鞍數(shù)學(xué)建模馬克思說：任何一門學(xué)科只有運用了數(shù)學(xué)才能稱為科學(xué)。數(shù)學(xué)建模對于現(xiàn)實世界的一個特定對象，為了一個特定目的，根據(jù)特有的內(nèi)在規(guī)律，做出一些必要的簡化假設(shè)，運用恰當?shù)臄?shù)學(xué)工具，得到一個數(shù)學(xué)結(jié)構(gòu)。模型分類

占絕對優(yōu)勢的模型可以歸為三類：最優(yōu)化模型動態(tài)模型概率模型數(shù)學(xué)建模例1常山機器廠生產(chǎn)1、2兩種產(chǎn)品，這兩種產(chǎn)品都要分別在A、B、C三種不同的設(shè)備上加工，按工藝資料規(guī)定，生產(chǎn)每件產(chǎn)品1需要占用設(shè)備分別為2h、4h、0h；生產(chǎn)每件產(chǎn)品2，需要占用設(shè)備分別為2h、0h、5h。已知各設(shè)備計劃期內(nèi)用于生產(chǎn)這兩種產(chǎn)品的能力分別為12h、16h、15h；又知每生產(chǎn)一件產(chǎn)品1企業(yè)能獲得2元利潤，每產(chǎn)一件產(chǎn)品2企業(yè)能獲得3元利潤。問：該企業(yè)應(yīng)安排生產(chǎn)兩種產(chǎn)品個多少件使總的利潤最大？模型求解例２：貨物打折的存貯模型某生產(chǎn)商為銷售產(chǎn)品，對于前來采購的商店采取打折優(yōu)惠活動試對此商店的庫存與銷售情況，建立數(shù)學(xué)模型模型分析：商店首先要采購一定數(shù)量的此種物品，將其放在倉庫中，而具體一段時間內(nèi)采購多少，主要取決于這時期內(nèi)銷售多少。因此我們可對某種物品的需求量劃分若干個時期，在同一時期內(nèi)需求是常數(shù)，但在不同時期內(nèi)需求是變化的。另外商家到生產(chǎn)上訂貨時，還需考慮不同時期生產(chǎn)上給出的優(yōu)惠是不同的。因此建立數(shù)學(xué)模型的目的就是制定最有存貯策略，即多長時間訂一次貨，每次訂多少貨，使總的費用最少。什么方法才是好的？很強的理論結(jié)果，漂亮的證明?

不管白貓黑貓，抓住老鼠就是好貓！模型求解提出問題選擇建模方法推導(dǎo)模型的數(shù)學(xué)表達式求解模型回答問題演示文稿

后

等我們所講的模型離散模型1.整數(shù)規(guī)劃模型2.圖優(yōu)化模型3.不規(guī)則離散優(yōu)化模型4.離散概率模型所屬學(xué)科：計算機、運籌學(xué)與控制論、概率的交叉學(xué)科一、整數(shù)規(guī)劃1、整數(shù)規(guī)劃的數(shù)學(xué)模型2、整數(shù)規(guī)劃解法3、0-1整數(shù)規(guī)劃4、指派問題及解法1.整數(shù)規(guī)劃數(shù)學(xué)模型

在許多經(jīng)濟管理的實際問題中，決策變量只有非負整數(shù)才有實際意義。對求整數(shù)最優(yōu)解的問題，稱為整數(shù)規(guī)劃。又稱約束條件和函數(shù)均為線性的IP為整數(shù)線性規(guī)劃。根據(jù)變量取整數(shù)的情況,將整數(shù)規(guī)劃分為：（1）純整數(shù)規(guī)劃，所有變量都取整數(shù).（2）混合整數(shù)規(guī)劃，一部分取整數(shù),一部分取實數(shù)。（3）0-1整數(shù)規(guī)劃,所有變量均取0或11.整數(shù)規(guī)劃數(shù)學(xué)模型例3.某廠擬用集裝箱托運甲、乙兩種貨物，每箱的體積、重量、可獲的利潤以及托運所受限制如下。問：兩種貨物各托運多少箱，使利潤最大？貨物體積重量利潤甲乙54252010托運限制24131.整數(shù)規(guī)劃數(shù)學(xué)模型2.整數(shù)規(guī)劃的解法枚舉法分支定界法割平面法智能算法2.整數(shù)規(guī)劃的解法分支定界法例：2.整數(shù)規(guī)劃的解法分支定界法步驟：1.尋找替代問題說明(1)若替代問題無可行解，則原問題無可界，停止；（2）若替代問題有最優(yōu)解，且符合原問題的整數(shù)條件，則替代問題的最優(yōu)解就是原問題的最優(yōu)解；（3）若替代問題有最優(yōu)解，且不符合原問題的條件，則分支。2.分支3.定界4.剪支2.整數(shù)規(guī)劃的解法割平面法思路：不考慮某個變量的整數(shù)約束這一條件，但增加線性約束條件（割平面）使得由原可行域中切割掉一部分，這部分只包含非整數(shù)解。如此進行使得切割最終的得到這樣的可行域，它的一個整數(shù)坐標的極點恰好是問題的最優(yōu)解。3.0-1整數(shù)規(guī)劃問題特征：包含的變量取0或1.構(gòu)造0-1整數(shù)規(guī)劃模型所利用的條件m個約束條件中只有k起作用。約束條件的右端項可能是r個值中的某一個，即3.兩組條件中滿足其中一組。例4

某城市消防總部將全市劃分為11個防火區(qū)，設(shè)有4個消防站，下圖中表示了各防火區(qū)域與消防站的位置，其中①，②，③，④表示消防站，1，2，3，……，11表示消防區(qū)域。根據(jù)歷史資料證實，各消防站可在事先規(guī)定的允許時間內(nèi)對所負責(zé)的地區(qū)火災(zāi)予以消滅，圖中虛線即表示各地區(qū)由哪個消防站負責(zé)（沒有虛線連接就表示不負責(zé)），現(xiàn)在總部提出，在同樣負責(zé)全市消防的前提下，是否可以減少消防站的數(shù)目？如果可以，應(yīng)當關(guān)閉哪個？①②③④1287345611910解：令對各防火區(qū)域可分別列出以下約束條件：防火區(qū)1：防火區(qū)2：防火區(qū)3：防火區(qū)4：防火區(qū)5：防火區(qū)6：防火區(qū)7：防火區(qū)8：防火區(qū)9：防火區(qū)10：防火區(qū)11：由上述約束條件知：必須x1,x3,x4為1，x2可為0，也可為1，由此，消防站②可以關(guān)閉而不影響任務(wù)的執(zhí)行

在實際中經(jīng)常會遇到這樣的問題，有n項不同的任務(wù)，需要n個人分別完成其中的一項，使完成n項任務(wù)的總效率最高（或所需時間最少），這類問題稱為指派問題或分派問題。

（一）指派問題的數(shù)學(xué)模型設(shè)n個人被分配去做n件工作，規(guī)定每個人只做一件工作，每件工作只有一個人去做。已知第i個人去做第j件工作的的效率（時間或費用）為Cij。問應(yīng)如何分配才能使總效率（時間或費用）最高？4.指派問題例：

任務(wù)人員ABCD甲21097乙154148丙13141611丁415139設(shè)決策變量1分配第i個人去做第j件工作

xij=0相反(i,j=1.2.…n)其數(shù)學(xué)模型為：理論結(jié)果定理1.從系數(shù)矩陣中一行（列）各元素分別減去該行（列）的最小元素得到新的矩陣，則以新的矩陣為系數(shù)矩陣求得到最優(yōu)解和原系數(shù)矩陣求得最優(yōu)解相同。定理2.若矩陣A的元素可分成0與非0兩部分，則覆蓋0元素的最少直線數(shù)等于位于不同行不同列的0元素的個數(shù)。定理3.在系數(shù)矩陣中若能找到n個不同行不同列的0元素，則令解矩陣中對應(yīng)的這個n個不同行不同列0元素的值為1，其他元素的值為0，則該解即為最優(yōu)。解題步驟

指派問題是0-1規(guī)劃的特例，也是運輸問題的特例，當然可用整數(shù)規(guī)劃，0-1規(guī)劃或運輸問題的解法去求解，這就如同用單純型法求解運輸問題一樣是不合算的。利用指派問題的特點可有更簡便的解法，這就是匈牙利法。

第一步：變換系數(shù)矩陣。

(1)從（cij）的每行元素都減去該行的最小元素；

(2)再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。

保證每行、每列至少一個0元素。第二步：尋找獨立零元素。

(1)從只有一個0元素的行(列)開始，給這個0元素加圈，記作◎，然后劃去◎所在列和行的其它0元素，記作?

。

(2)如果所在行（列）中有多個0元素，任選一個加圈，記作◎

，同時，劃去◎所在列和行的其它0元素。

(3)反復(fù)進行上述幾步，直到所有0元素都被圈出和劃掉為止。

(4)

若◎元素的數(shù)目m等于矩陣的階數(shù)n，那么這指派問題的最優(yōu)解已得到。若m<n,則轉(zhuǎn)入第三步。

第三步：作最少的直線覆蓋所有0元素。

(1)對沒有◎的行打√號；

(2)對已打√號的行中所有含?元素的列打√號；

(3)再對打有√號的列中含◎元素的行打√號；(4)重復(fù)(2)，(3)直到得不出新的打√號的行、列為止；

(5)對沒有打√號的行畫橫線，有打√號的列畫縱線，這就得到覆蓋所有0元素的最少直線數(shù)

第四步：變換矩陣，增加0元素。在沒有被直線覆蓋的所有元素中找出最小元素，未被覆蓋的各行（或列）都減去這最小元素，如果出現(xiàn)負元素，則在該列（或行）都加上這最小元素（以保證系數(shù)矩陣中不出現(xiàn)負元素）。轉(zhuǎn)回第二步。例：

任務(wù)人員ABCD甲215134乙1041415丙9141613丁78119249742◎?◎??◎◎有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時間如下表所示，問如何分派任務(wù)，可使總時間最少？

任務(wù)人員ABCD甲67112乙4598丙31104丁5982例：求解過程如下：第一步，變換系數(shù)矩陣：－5第二步，獨立0元素：◎◎◎??找到3個獨立零元素但m=3<n=

4第三步，作最少的直線覆蓋所有0元素：

◎◎◎??√√√獨立零元素的個數(shù)m=3<n=4；第四步，變換矩陣(bij)以增加0元素：沒有被直線覆蓋的所有元素中的最小元素為1，然后打√各行都減去1；打√各列都加上1，得如下矩陣，并轉(zhuǎn)第二步進行試指派：000

0

00得到4個獨立零元素，所以最優(yōu)解矩陣為：

◎◎◎??√√√-1◎◎?-115◎◎◎??◎特殊的指派問題1．最大化指派問題構(gòu)造系數(shù)矩陣（max-Cij）2．人、事不對等指派問題添上虛擬的人或者事，回憶運輸問題？3．一人做幾事的指派問題將此人看作N個相同的人。4．某人一定不做某事的指派問題

其費用無窮大或者利潤無窮小。

從甲、乙、丙、丁、戊五人中挑選四人去完成四項工作。已知每人完成各項工作的時間如表所示。規(guī)定每項工作只能由一個人去單獨完成，每個人最多承擔(dān)一項任務(wù)。又假定對甲必須保證分配一項任務(wù)，丁因某種原因決定不同意承擔(dān)第4項任務(wù)。在滿足上述條件下，如何分配工作，使完成四項工作總的花費時間為最少。甲乙丙丁戊1234105152021051531514131527694158

分配甲、乙、丙、丁四個人去完成五項任務(wù)。每人完成各項任務(wù)時間如表所示。由于任務(wù)數(shù)多于人數(shù)，故規(guī)定其中有一個人可兼完成兩項任務(wù)，其余三人每人完成一項。試確定總花費時間為最少的指派方案。

ABCDE甲乙丙丁2539342429382742312628364220402337333245其他應(yīng)用舉例某大學(xué)計算機實驗室聘用4名大學(xué)生（代號1，2，3，4）和2名研究生（代號5，6）值班答疑。已知每人從周一至周五最多可安排的值班時間及每人每小時值班的報酬如下表。問：該實驗室安排一張人員的值班表使總支付的報酬最少？每天最多可安排的值班時間學(xué)生報酬（元/h）周一周二周三周四周五12345610109.99.810.811.360607060604830