【正文】 市政府希望設(shè)置的消防站最少，但必須滿足在城市任何地區(qū)發(fā)生火警時，消防車要在 15 分鐘內(nèi)趕到現(xiàn)場。 工時 /件 工序 型號 B1 B2 B3 利潤（元 /件） B31 B32 A1 25 A2 40 每周工時（小時 /月） 250 100 150 120 解：設(shè) A A2產(chǎn)品的生產(chǎn)數(shù)量分別為 x x2件，在不考慮 B31和B32相互排斥的情況下，問題的數(shù)學(xué)模型為 21 4025m a x xxz ????????????????????且為整數(shù),0,)2(1 2 )1(1 5 1 0 2 5 ..2121212121xxxxxxxxxxts工序 B3只能從兩種加工方式中選擇一種，那么約束條件（ 1）和（ 2）就成為相互排斥的約束條件。bin(x2)。 （仍然默認(rèn)為取值是非負(fù)的） LINDO可用于求解線性純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃 (IP)， 模型的輸入與 LP問題類似 , 但需 在 END標(biāo)志后定義整型變量 。 !目標(biāo)函數(shù) FOR(WH(I): SUM(VD(J):X(I,J))=AI(I))。 語句中的 FOR 是 LINGO提供的內(nèi)部函數(shù)，它的作用是對某個集合的所有成員 分別生成一個約束表達(dá)式，它有兩個參數(shù)，第一個參數(shù)是集合名，表示對該集合 的所有成員生成對應(yīng)的約束表達(dá)式，上式 FOR 的第一個參數(shù)為ＷＨ，它表示 貨棧，共有６個成員，故應(yīng)生成６個約束表達(dá)式， FOR 的第二個參數(shù)是約束 表達(dá)式的具體內(nèi)容，此處再調(diào)用 SUM 函數(shù)，表示該約束的左邊是求和，是對集合 ＶＤ的８個成員，并且對表達(dá)式Ｘ (I,J) 中的第二維 J 求和，即 約束表達(dá)式的右邊是集合ＷＨ的屬性 AI，它有 6個分量，與 6個約束表達(dá)式一一對應(yīng)， 本句中的屬性分別屬于不同的集合，所以不能省略 I,J. 約束條件 表示為 FOR(D(J)): SUM(VD(J):X(I,J))=DJ(J))。 ENDSETS 注：集合定義部分以語句 SETS: 開始， 以 ENDSETS語句結(jié)束，這兩個語句需單獨(dú)成一行， ENDSETS后面不加標(biāo)點(diǎn)符號 . 二、數(shù)據(jù)初始化（數(shù)據(jù)段） 以上集合中屬性 X（有 48個分量）是決策變量，是待求的未知數(shù)，屬性 AI、 DJ和Ｃ（分別有６ ,8,48個分量）都是已知數(shù)， LINKS 建模語言通過數(shù)據(jù)初始化部分來實(shí)現(xiàn)對已知屬性賦以初始值，格式為： DATA: AI=60,55,51,43,41,52。 集合、成員、屬性的命名規(guī)則與變量相同，可按自己的意愿，用有一定意義 的字母數(shù)串來表示，式中“ / ”和“ /:” 是規(guī)定的語法規(guī)則 。1,1,0,11,1m i n11111 1????例 某公司有 6個供貨棧（倉庫），庫存貨物總數(shù)分別為 60， 55， 51， 43， 41， 52，現(xiàn)有 8個客戶各要一批貨數(shù)量分別為 35， 37， 22， 32， 41， 32， 43， 38，各供貨棧道 8個客戶的單位貨物運(yùn)輸價見表 供貨棧到客戶的單位貨物運(yùn)價 客戶 貨棧 V1 V2 V3 V4 V5 V6 V7 V8 W1 6 2 6 7 4 2 5 9 W2 4 9 5 3 8 5 8 2 W3 5 2 1 9 7 4 3 3 W4 7 6 7 3 9 2 7 1 W5 2 3 9 5 7 2 6 5 W6 5 5 2 2 8 1 4 3 試確定各貨棧到各客戶處的貨物調(diào)運(yùn)數(shù)量，使總的運(yùn)輸費(fèi)用最小。 因?yàn)?xi， n+1實(shí)際上表示 Ai產(chǎn)地沒有運(yùn)出去而庫存的物資數(shù)量 。 2*x1+x2=600。 vlb = zeros(2,1)。 beq=[400 600 500]。 beq=[120]。0。700。 嚴(yán)格 l .opt . 嚴(yán)格 g .opt . l .opt . 數(shù)學(xué)規(guī)劃模型的一般形式 ? 函數(shù)形式 : f(x), gi(x) , hj(x) : Rn?R min f(x) (fgh) . gi(x) ≤ 0 , i = 1,2,…,m hj(x) = 0 , j = 1,2,…,l ? 矩陣形式 : min f(x) ， f(x) : Rn?R (fgh) . g(x) ≤ 0 , g(x) : Rn?Rm h(x) = 0 , h(x) : Rn?Rl 當(dāng) f(x), gi(x) , hj(x)均為線性函數(shù)時，稱線性規(guī)劃；若其中有非線性函數(shù)時，稱非線性規(guī)劃 。數(shù)學(xué)建模 優(yōu)化模型介紹 引言 數(shù)學(xué)之重要 …… 數(shù)學(xué)使人周密 …… Francis Bacon 數(shù)學(xué)處于人類智能的中心領(lǐng)域 …… 數(shù)學(xué)方 法滲透、支配著一切自然科學(xué)的理論分支 …… 它已愈來愈成為衡量成就的主要標(biāo)志。 優(yōu)化模型的 簡單分類 ? 線性規(guī)劃 (LP) 目標(biāo)和約束均為線性函數(shù) ? 非線性規(guī)劃 (NLP) 目標(biāo)或約束中存在非線性函數(shù) ? 二次規(guī)劃 (QP) 目標(biāo)為二次函數(shù)、約束為線性 ? 整數(shù)規(guī)劃 (IP) 決策變量 (全部或部分 )為整數(shù) ? 整數(shù) 線性 規(guī)劃 (ILP)，整數(shù) 非線性 規(guī)劃 (INLP) ? 純整數(shù)規(guī)劃 (PIP), 混合整數(shù)規(guī)劃 (MIP) ? 一般整數(shù)規(guī)劃， 01（整數(shù)）規(guī)劃 njiDxljxgmixhtsxf???????, . . . ,1,0)(, . . . ,1,0)(..)(m i n連續(xù)優(yōu)化 離散優(yōu)化 數(shù)學(xué)規(guī)劃 優(yōu)化模型的簡單分類和求解難度 優(yōu)化 線性規(guī)劃 非線性規(guī)劃 二次規(guī)劃 連續(xù)優(yōu)化 整數(shù)規(guī)劃 問題求解的難度增加 線性規(guī)劃 Linear Programming 問題一 ： 任務(wù)分配問題 ： 某車間有甲、乙兩臺機(jī)床，可用于加工三種工件 .假定這兩臺車床的可用臺時數(shù)分別為 800和900，三種工件的數(shù)量分別為 400、 600和 500，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺時數(shù)和加工費(fèi)用如下表 .問怎樣分配車床的加工任務(wù)，才能既滿足加工工件的要求，又使加工費(fèi)用最低？ 單位工件所需加工臺時數(shù) 單位工件的加工費(fèi)用 車床類 型 工件 1 工件 2 工件 3 工件 1 工件 2 工件 3 可用臺時數(shù) 甲 0. 4 1. 1 1. 0 13 9 10 800 乙 0. 5 1. 2 1. 3 11 12 8 900 兩個引例 建立線性規(guī)劃模型的基本步驟 ： （ 1） 設(shè)出決策變量 （ 2） 確定目標(biāo)函數(shù) （ 3） 確定約束條件 找出待定的未知變量（決策變量），并用代數(shù)符號表示 找到模型的目標(biāo)或判據(jù)，寫成決策變量的線性函數(shù)，以便求出 其最大值或最小值 找出問題的所有的限制或約束，寫出未知變量的線性方程或 線性不等式 解 設(shè)在甲車床上加工工件 3的數(shù)量分別為 x x x3，在乙車床上加工工件 3的數(shù)量分別為 x x x6,可建立以下線性規(guī)劃模型： 654321 8121110913m i n xxxxxxz ?????? 1425361 2 34 5 6x 40 0600500. 0. 4 1. 1 80 00. 5 1. 2 1. 3 90 00 , 1 , 2 , , 6ixxxxxx x xx x xxi???????? ????? ? ???? ? ?????? 解答 問題二： 某廠每日 8小時的產(chǎn)量不低于 1800件 .為了進(jìn)行質(zhì)量控制，計劃聘請兩種不同水平的檢驗(yàn)員 .一級檢驗(yàn)員的標(biāo)準(zhǔn)為：速度 25件 /小時，正確率 98%，計時工資 4元 /小時；二級檢驗(yàn)員的標(biāo)準(zhǔn)為：速度 15件 /小時，正確率 95%，計時工資 3元 /小時 .檢驗(yàn)員每錯檢一次，工廠要損失 2元 .為使總檢驗(yàn)費(fèi)用最省，該工廠應(yīng)聘一級、二級檢驗(yàn)員各幾名？ 解 設(shè)需要一級和二級檢驗(yàn)員的人數(shù)分別為 x x2人 , 則應(yīng)付檢驗(yàn)員的工資為： 2121 24323848 xxxx ???????因檢驗(yàn)員錯檢而造成的損失為 ： 2121 1282)%5158%2258( xxxx ??????????故目標(biāo)函數(shù)為： 212121 3640)128()2432(m i n xxxxxxz ??????約束條件為： ?????????????????????0,01 8 0 01581 8 0 02581 8 0 0158258212121xxxxxx線性規(guī)劃模型： 21 3640m in xxz ??1212125 3 4 59s. t. 150 , 0xxxxxx?????????? ??? 解答 返 回 –模型特點(diǎn)：目標(biāo)函數(shù) (Objective function) –與約束條件 (Constraint)均為線性的； –目標(biāo)函數(shù)實(shí)現(xiàn)極大化或極小化。100。0。 vlb=[30,0,20]。 vlb = zeros(6,1)。 vub=[9 15]。 gin(x1)。 經(jīng)處理后 ， 問題變成了產(chǎn)銷平衡的運(yùn)輸問題 ， 其數(shù)學(xué)模型為： 這樣， m個產(chǎn)地、 n個銷地的不平衡運(yùn)輸問題，轉(zhuǎn)化成了 m個產(chǎn)地、n+1個銷地的平衡運(yùn)輸問題，此時可用表上作業(yè)法求解。 解 引入決策變量 代表從第 個貨棧到第 個 客戶的貨物運(yùn)量 . 設(shè) 表示從第 個貨棧 到第 個客戶的單位貨物運(yùn)價 表示第 個貨棧的最大供貨量 , 表示第 個客戶的訂貨量 . 目標(biāo)函數(shù)是總運(yùn)輸費(fèi)用最少 . 約束條件有三條： 1. 各貨棧運(yùn)出的貨物總量不超過其庫存數(shù) 3. 決策變量 非負(fù) 數(shù)學(xué)模型為 前面介紹的 LinGO的基本用法，其優(yōu)點(diǎn)是輸入模型較直觀，一般的數(shù)學(xué)表達(dá)式無需作大的變換即可直接輸入 .對于規(guī)模較小的的規(guī)劃模型，用直接輸入的方法是有利的，如果模型的變量和約束的條件個數(shù)比較多，若仍然用直接的輸入方式，雖然也能求解并得到結(jié)果，但這種做法有明顯的不足之處。 本例再定義客戶集合 ： VD/V1..V8/:DJ。 DJ=35,37,22,32,41,32,43,38。 完整的模型 MODEL: SETS: WH/W1..W6/:AI。 !約束條件 FOR(VD(J):SUM(VD(J):X(I,J))=DJ(J))。 0/1型的變量可由 INTEGER（可簡寫為 INT）命令來標(biāo)識， 有以下兩種可能的用法： INT vname INT n 前者只將決策變量 vname標(biāo)識為 0/1型 , 后者將當(dāng)前模型中前 n 個變量標(biāo)識為 0/1型（模型中變量順序由模型中輸入時出現(xiàn)的先后順序決定 , 該順序可由輸出結(jié)果中的變量順序查證是否一致）。 bin(x3)。為了統(tǒng)一在一個問題中，引入 01變量 則數(shù)學(xué)模型為 2,1,0 ,13333 ????? iBBBByiii 加工方式不采用加工方式采用???????????????????????????10,0,1)1(1 2 )1(1 5 1 0 2 5 ..2121212211212121或且為整數(shù)yyxxyyyMxxyMxxxxxxts21 4025m a x xxz ??（三）固定成本問題 (Fixed cost problem) 例 某公司制造小、中、大三種尺寸的容器，所需資源為金屬板、勞動力和機(jī)器設(shè)備，制造一個容器所需的各種資源的數(shù)量如下表所示：不考慮固定費(fèi)用，小、中、大號容器每售出一個其利潤分別為 4萬元、 5萬元、 6萬元