【正文】 若 Ai點(diǎn)投資為 bi萬元，每年可獲利潤為 ci萬元，投資總額為B萬 元，試建立利潤最大化的 0－ 1規(guī)劃模型。 （ 4， 1） 使目標(biāo)函數(shù)達(dá)到最大，即 z＝ 14。 注：如果表達(dá)式中參與酸的屬性屬于同一個(gè)集合，則 語句中索引（相當(dāng)于矩陣或數(shù)組的下標(biāo)可以省略）（隱藏），假如表達(dá)式中參與運(yùn)算的屬性屬于不同的集合，則不能省略屬性的索引 .本例的目標(biāo)函數(shù)可以表示成 MIN=SUM(LINKS:C*X)。 每個(gè)集合在使用之前需要預(yù)先給出定義，定義集合時(shí)要明確三方面的內(nèi)容 ： 集合 的名稱 ， 集合內(nèi)的成員（元素） 、 集合的屬性（可以看成與該集合有關(guān)的變量 或常量，相當(dāng)于數(shù)組） . 本例首先定義倉庫集合 ： WH/W1..W6/:AI。,1,0,1,1m i n111 1????產(chǎn)銷不平衡的運(yùn)輸問題 Total Supply not Equal to Total Demand 一、產(chǎn)大于銷 (total supply exceeds total demand) ? 產(chǎn)大于銷的運(yùn)輸問題的特征是 Σ ai Σ bj， 其數(shù)學(xué)模型為： ?????????????????????? ???? ?njmixnjbxmiaxxcfijmijijnjiijminjijij,1。 Aeq=[]。 b=[50]。0 0 0 0 ]。 Karl Marx Galileo : 展現(xiàn)在我們眼前的宇宙像一本用數(shù) 學(xué)語言寫成的大書，如不掌握數(shù)學(xué)符號語言，就像在黑暗 的迷宮里游蕩，什么也認(rèn)識不清。 Aeq=[]。 [x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub) To MATLAB (xxgh2) 123m i n ( 6 3 4 )xzxx????? ???????????????????????32120030xxx1231 1 1 1 2 0s .t . 0 1 0 5 0xxx??? ? ? ????? ? ? ???? ? ? ?????. ? ? Xz 8121110913m i n ? ?????????????????900800 X?????????????????????5 0 06 0 04 0 0100100010010001001X ，0654321??????????????????????xxxxxxX 改寫為： 例 3 問題一的解答 問題 編寫 M文件 : f = [13 9 10 11 12 8]。 1）若用 35元可以買到 1桶牛奶，應(yīng)否作這樣的投資？若投資， 每天最多購買多少桶牛奶 2）若可以聘用臨時(shí)工人以增加勞動時(shí)間，付給臨時(shí)工人的 工資最多是每小時(shí)幾元？ 3）由于市場需求變化，每公斤 A1的獲利增加到 30元，應(yīng)否 改變生產(chǎn)計(jì)劃？ 1桶牛奶 3kgA1 12小時(shí) 8小時(shí) 4kgA2 或 獲利 24元 /kg 獲利 16元 /kg x1桶牛奶生產(chǎn) A1 x2桶牛奶生產(chǎn) A2 獲利 24 3x1 獲利 16 4 x2 原料供應(yīng) 5021 ?? xx勞動時(shí)間 480812 21 ?? xx加工能力 1003 1 ?x決策變量 目標(biāo)函數(shù) 12M a x 72 64z x x??每天獲利 約束條件 非負(fù)約束 0, 21 ?xx線性規(guī)劃模型(LP) 時(shí)間 480小時(shí) 至多加工 100kgA1 50桶牛奶 每天 基本模型 模型求解 圖解法 x1 x2 0 A B C D l1 l2 l3 l4 l5 5021 ?? xx480812 21 ?? xx1003 1 ?x0, 21 ?xx約束條件 50: 211 ?? xxl480812: 212 ?? xxl1003: 13 ?xl0:,0: 2514 ?? xlxl12M a x 72 64z x x??目標(biāo)函數(shù) z=0 z=2400 z=3600 z =c (常數(shù) ) ~等值線 c 在 B(20,30)點(diǎn)得到最優(yōu)解 目標(biāo)函數(shù)和約束條件是線性函數(shù) 可行域?yàn)橹本€段圍成的凸多邊形 目標(biāo)函數(shù)的等值線為直線 最優(yōu)解一定在凸多邊形的某個(gè)頂點(diǎn)取得。,1,01,1,1m i n111111njmixnjbxmiaxxcfijmijijnjiijminjijij????二 、 銷大于產(chǎn) (total demand exceeds total supply) ? 銷大于產(chǎn)的運(yùn)輸問題的特征是 Σ ai Σ bj， 其數(shù)學(xué)模型為： ?????????????????????? ???? ?njmixnjbxmiaxxcfijmijijnjiijminjijij,1。 為表示數(shù)學(xué)模型中從貨棧到客戶的運(yùn)輸關(guān)系以及與此相關(guān)的運(yùn)輸單價(jià) 和運(yùn)量 再定義一個(gè)表示運(yùn)輸關(guān)系的集合： LINKS(WH,VD): C,X。 LINKS(WH,VD):C,X。 SET X2 TO = 2 AT 1, BND= TWIN= 7 SET X1 TO = 4 AT 2, BND= TWIN= 10 NEW INTEGER SOLUTION OF AT BRANCH 2 PIVOT 10 BOUND ON OPTIMUM: DELETE X1 AT LEVEL 2 DELETE X2 AT LEVEL 1 ENUMERATION COMPLETE. BRANCHES= 2 PIVOTS= 10 LAST INTEGER SOLUTION IS THE BEST FOUND REINSTALLING BEST SOLUTION... OBJECTIVE FUNCTION VALUE 1) VARIABLE VALUE REDUCED COST X1 X2 ROW SLACK OR SURPLUS DUAL PRICES 2) 3) NO. ITERATIONS= 10 BRANCHES= 2 DETERM.= 0 最優(yōu)值 松弛和剩余變量（ SLACK OR SURPLUS）仍然可以表示約束的松緊程度，但目前 IP尚無相應(yīng)完善的敏感性分析理論，因此 REDUCED COST和 DUAL PRICES的結(jié)果在整數(shù)規(guī)劃中意義不大。不考慮固定費(fèi)用，則問題的數(shù)學(xué)模型為 ?????????????????0,1 0 0323 0 04325 0 0842..321321321321xxxxxxxxxxxxts321 654m a x xxxz ???若考慮固定費(fèi)用就必須引入 0—1變量： 則該問題的數(shù)學(xué)模型為 3,2,10,0 0,1 ??????? ixixiyiii 種容器時(shí)即當(dāng)不生產(chǎn)第時(shí)種容器即當(dāng)生產(chǎn)第321321 200150100654m a x yyyxxxz ????????????????????????????????????10,0,0001 0 0323 0 04325 0 0842..321321332211321321321oryyyxxxMyxMyxMyxxxxxxxxxxts可以看出，當(dāng) xj0時(shí)，為使 Z 極大化， 應(yīng)有 Yj=0 （四）布點(diǎn)問題 (Location Problem) 例 某城市消防隊(duì)布點(diǎn)問題。 bin(x3)。 !約束條件 FOR(VD(J):SUM(VD(J):X(I,J))=DJ(J))。 DJ=35,37,22,32,41,32,43,38。 解 引入決策變量 代表從第 個(gè)貨棧到第 個(gè) 客戶的貨物運(yùn)量 . 設(shè) 表示從第 個(gè)貨棧 到第 個(gè)客戶的單位貨物運(yùn)價(jià) 表示第 個(gè)貨棧的最大供貨量 , 表示第 個(gè)客戶的訂貨量 . 目標(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ī)劃模型，用直接輸入的方法是有利的，如果模型的變量和約束的條件個(gè)數(shù)比較多，若仍然用直接的輸入方式，雖然也能求解并得到結(jié)果，但這種做法有明顯的不足之處。 gin(x1)。 vlb = zeros(6,1)。0。 優(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í)數(shù)分別為 800和900，三種工件的數(shù)量分別為 400、 600和 500，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺時(shí)數(shù)和加工費(fèi)用如下表 .問怎樣分配車床的加工任務(wù)，才能既滿足加工工件的要求，又使加工費(fèi)用最低？ 單位工件所需加工臺時(shí)數(shù) 單位工件的加工費(fèi)用 車床類 型 工件 1 工件 2 工件 3 工件 1 工件 2 工件 3 可用臺時(shí)數(shù) 甲 0. 4 1. 1 1. 0 13 9 10 800 乙 0. 5 1. 2 1. 3 11 12 8 900 兩個(gè)引例 建立線性規(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 ??????