【正文】 問(wèn)如何制定生產(chǎn)計(jì)劃使獲得的利潤(rùn)最大？ 資源 小號(hào)容器 中號(hào)容器 大號(hào)容器 金屬板 （ 噸 ） 2 4 8 勞動(dòng)力 （ 人 /月 ） 2 3 4 機(jī)器設(shè)備 （ 臺(tái) /月 ） 1 2 3 解 ：設(shè) x x x3分別為小號(hào)容器、中號(hào)容器、大號(hào)容器的生產(chǎn)數(shù)量。bin(x4)。 一般的整數(shù)變量可用命令 GIN （是 GENERAL INTEGER的意思） ,其使用方式及格式與 INT 命令相似。 END 以“ MODEL：”開(kāi)始 集合定義部分從(―SETS：”到“ ENDSETS‖ )：定義集合及其屬性 ?以“ END‖結(jié)束 ?給出優(yōu)化目標(biāo)和約束 集合定義部分從(“DATA：”到“ ENDDATA” ) 整數(shù)規(guī)劃 Integer Programming, IP 整數(shù)規(guī)劃 （ Integer Programming）主要是指整數(shù)線性規(guī)劃。 VD/V1..V8/:DJ。 C=6,2,6,7,4,2,5,9 4,9,5,3,8,5,8,2 5,2,1,9,7,4,3,3 7,6,7,3,9,2,7,1 2,3,9,5,7,2,6,5 5,5,2,2,8,1,4,3。 該集合有 8個(gè)成員， DJ 是集合的屬性（有 8個(gè)分量）表示各客戶的需求量 . 以上兩個(gè)集合稱為 初始集合（或稱基本集合、原始集合）初始集合的屬性都 相當(dāng)于一維數(shù)組。模型的篇幅很長(zhǎng)，不便于分析修改和擴(kuò)展。 ???????????????????????? ???????1,1。 gin(x2)。 %調(diào)用 linprog函數(shù)： [x,fval] = linprog(c,A,b,Aeq,beq,vlb,vub) To MATLAB (xxgh4) 結(jié)果為： x = fval =360 即只需聘用 9個(gè)一級(jí)檢驗(yàn)員 . 注： 本問(wèn)題應(yīng)還有一個(gè)約束條件： x x2取整數(shù) .故它是一個(gè)整數(shù)線性規(guī)劃問(wèn)題 .這里把它當(dāng)成一個(gè)線性規(guī)劃來(lái)解，求得其最優(yōu)解剛好是整數(shù)： x1=9， x2=0，故它就是該整數(shù)規(guī)劃的最優(yōu)解 .若用線性規(guī)劃解法求得的最優(yōu)解不是整數(shù)，將其取整后不一定是相應(yīng)整數(shù)規(guī)劃的最優(yōu)解，這樣的整數(shù)規(guī)劃應(yīng)用專門的方法求解 . 返 回 用 LINDO、 LINGO優(yōu)化工具箱解線性規(guī)劃 LINDO 公司軟件產(chǎn)品簡(jiǎn)要介紹 美國(guó)芝加哥 (Chicago)大學(xué)的 Linus Schrage教授于 1980年前后開(kāi)發(fā) , 后來(lái)成立 LINDO系統(tǒng)公司（ LINDO Systems Inc.）， 網(wǎng)址： LINDO: Linear INteractive and Discrete Optimizer () LINGO: Linear INteractive General Optimizer () LINDO API: LINDO Application Programming Interface () What’s Best!: (SpreadSheet . EXCEL) () 演 示 (試用 )版、學(xué)生版、高級(jí)版、超級(jí)版、工業(yè)版、擴(kuò)展版 … （求解 問(wèn)題規(guī)模 和 選件 不同） LINDO和 LINGO軟件能求解的優(yōu)化模型 LINGO LINDO 優(yōu)化模型 線性規(guī)劃 (LP) 非線性規(guī)劃 (NLP) 二次規(guī)劃 (QP) 連續(xù)優(yōu)化 整數(shù)規(guī)劃 (IP) 一、 LINDO軟件包 下面我們通過(guò)一個(gè)例題來(lái)說(shuō)明 LINDO軟件包的使用方法 . 問(wèn)題 ： 一奶制品加工廠用牛奶生產(chǎn) A1, A2 兩種奶制品，一桶 牛奶可以在甲類設(shè)備上用 12小時(shí)生產(chǎn)成 3公斤 A1，或者在乙類設(shè)備上用 8小時(shí)加工成 4公斤 ，生產(chǎn)的兩種奶制品全部 能售出，且每公斤 A1獲利 24元，每公斤 A2獲利 16元，現(xiàn)在每天加工廠每天能得到 50桶牛奶的供應(yīng)，每天正式工人總的勞動(dòng)時(shí)間為480小時(shí)，并且甲類設(shè)備每天至多能加工 100公斤 A1，乙類設(shè)備的加工能力沒(méi)有限制 .試為該廠制定一個(gè)生產(chǎn)計(jì)劃，使每天獲利最大，并進(jìn)一步討論以下 3個(gè)附加問(wèn)題。 vub=[]。 vub=[]。0]。900]。 線性規(guī)劃問(wèn)題的一般形式： Max(Min)S=c1x1+c2x2+… ..+xn . a11x1+a12x2+… .+a1nxn ?(=, ?)b1 a21x1+a22x2+… .+a2nxn ?(=, ?)b2 ………………… . am1x1+am2x2+… .+amnxn ?(=, ?)bm x1,x2… .xn ? 0 ?m i n().????? (m ax ) u c xA x bv l b x v u b矩 陣 形 式 ：線性規(guī)劃的 基本概念 (Feasible Solution)——任一滿足約束條件的 一組決策變量的數(shù)值 . (Feasible Region)——所有可行解組成的集合， 也稱為可行解集 . 3. 目標(biāo)函數(shù)等值線 (Objective function line)—— 為于同一直線上的點(diǎn)，具有相同的目標(biāo)函數(shù)值 . 線性規(guī)劃模型的解的幾種情況 線性規(guī)劃問(wèn)題 有可行解 (Feasible) 無(wú) 可 行 解（ Infeasible） 有最優(yōu)解 （ Optimal） 無(wú) 最 優(yōu) 解(Unbounded) 數(shù)學(xué)建模中線性規(guī)劃模型的常用解法 線性規(guī)劃問(wèn)題的求解在理在理論上有單純型法，在實(shí)際建模中常用以下解法： 4. MATLAB 軟件包 主要介紹線性規(guī)劃模型的 MATlAB軟件包和 LINGO軟件包解法 模型求解方法 1. 圖解法 例 1 max z=50x1+100x2 x1 + x2≤300 2x1 + x2≤400 x2≤250 x x2≥0 該問(wèn)題的最優(yōu)解為 x1=50； x2=250 x2 z*=50x1+100x2=27500 x1 + x2≤300 x1 x2≤250 2x1 + x2≤400 z1=50x1+100x2=0 B O A C D z2=14000 用 MATLAB優(yōu)化工具箱解線性規(guī)劃 min z=cX s .t . A X b?1. 模型： 命令： x=linprog（ c, A, b） 2. 模型 ： min z=cX s .t . A X b?be qXA e q ??命令： x=linprog（ c， A， b， Aeq,beq） 注意：若沒(méi)有不等式： 存在，則令 A=[ ]， b=[ ]. bAX ?式中： linprog 稱為調(diào)用函數(shù)， C, A, b 稱為輸入?yún)?shù)，全部由用戶 提供，必須按規(guī)定的位置放置在原括號(hào)內(nèi) . 3. 模型 ： min z=cX s .t . A X b?be qXA e q ??VLB≤X≤VUB 命令： [1] x=linprog（ c， A， b， Aeq, beq, VLB， VUB） [2] x=linprog（ c， A， b， Aeq, beq, VLB， VUB, X0） 注意： [1] 若沒(méi)有等式約束 : , 則令 Aeq=[ ], beq=[ ]. [2]其中 X0表示初始點(diǎn) ,設(shè)置它有些情況下可以減少 迭代工作量 be qXA e q ??4. 命令： [x,fval]=linprog(…) 返回最優(yōu)解 ｘ 及 ｘ 處的目標(biāo)函數(shù)值 fval. 解 編寫 M文件 ： c=[ ]。 von Neumann 引言 數(shù)學(xué)之重要 一門科學(xué)只有當(dāng)它達(dá)到能夠成功地運(yùn)用 數(shù)學(xué)時(shí)，才算真正發(fā)展了。 則稱 x*為 (f S)的局部最優(yōu)解 ,記 l .opt.(local optimum) ? 在上述定義中，當(dāng) x ? x* 時(shí)有嚴(yán)格不等式成立， 則分別稱 x* 為 (f S)的嚴(yán)格全局最優(yōu)解和嚴(yán)格局部最優(yōu)解 。 b=[850。0。 Aeq=[1 1 1]。 Aeq=[1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1]。 beq=[]。 x1=98。,1,0,1,1m i n111 1????– 解此類問(wèn)題可假想一個(gè)銷地 Bn+1， 其需要量為： bn+1=Σ ai －Σ bj；若用 xi， n+1表示從 Ai到 Bn+1的運(yùn)量 ， 可令 ci， n+1=0或等于第 Ai產(chǎn)地儲(chǔ)存單位物資的費(fèi)用 。 ???????????????????????? ?????? ?njmixnjbxmiaxxcfijmijijnjiijminjijij,1。 其中 WH是集合的名稱， W1..W6是集合內(nèi)的成員， “ ..” 是特定的省略號(hào) （如果不用該省略號(hào)，也可以把成員一一羅列出來(lái)，成員之間用逗號(hào)或 空格分開(kāi) ),表明該集合有 6個(gè)成員，分別對(duì)應(yīng)于 6個(gè)供貨棧， AI是集合的屬性， 它可以看成是一個(gè)數(shù)組，有 6個(gè)分量，分別表示各貨棧現(xiàn)有貨物的總數(shù)。 LINKS(WH,VD):C,X。 約束條件 用Ｌ INGO 語(yǔ)言描述該約束條件，語(yǔ)句為： FOR(WH(I): SUM(VD(J):X(I,J))=AI(I))。 ENDDATA MIN=SUM(LINKS (I,J):C(I,J)*X(I,J))。 IP可用 LINDO直接求解 max 3x1+2x2 st 2x1+3x214 x1+ end gin 2 ―gin 2‖表示 “ 前 2個(gè)變量為整數(shù) ” ，等價(jià)于： gin x1 gin x2 其中“ GIN 2”表示 2個(gè)變量都是一般整數(shù)變量。 bin(x1)。 解：設(shè)決策變量為 建立 0－ 1規(guī)劃模型如下： 7,2,1,0 ,1 ?????? iAAxiii 點(diǎn)未被選用當(dāng)點(diǎn)被選用當(dāng)772211m a x xcxcxcz ???? ???????????????????????????7,2,1,100112.52765432171?ixxxxxxxxxxBxbtsiiii，或（二） 相互排斥的約束條件 (Mutually exclusive constraints) 例 某產(chǎn)品有 A1和 A2兩種型號(hào)，需要經(jīng)過(guò) B B B3三道工序，單位工時(shí)和利潤(rùn)、各工序每周工時(shí)限制見(jiàn)表所示，問(wèn)工廠如何安排生產(chǎn)，才能使總利潤(rùn)最大？（ B3工序有兩種加工方式 B31和 B32，產(chǎn)品為整數(shù)）。據(jù)實(shí)地測(cè)定，各區(qū)之間消防車行駛的時(shí)間見(jiàn)表 4－ 9，請(qǐng)幫助該市制定一個(gè)布點(diǎn)最少的計(jì)劃。 （ 4）選 A2點(diǎn)必選 A5點(diǎn)。 5*x1+3*x2+x3+2*x4+4*x58。 （ 3， 2） 點(diǎn)盡管在可行域內(nèi)，但沒(méi)有使目標(biāo)達(dá)到極大化。 DJ=35,37,22,32,41,32,43,38。 式中， SUM 是 LINGO提供的內(nèi)部函數(shù)，其作用是對(duì)某個(gè)集合的所有成員 求制定表達(dá)式的和，該函數(shù)需要兩個(gè)參數(shù)，第一個(gè)參數(shù)是 集合名稱 ，制定對(duì)該 集合的所有成員求和，如果此集合是一個(gè)初始集合，它有 m 個(gè)成員，則求和運(yùn)算 對(duì) m 個(gè)成員進(jìn)行，相當(dāng)于求