【正文】 ???? (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)—— 為于同一直線上的點，具有相同的目標(biāo)函數(shù)值 . 線性規(guī)劃模型的解的幾種情況 線性規(guī)劃問題 有可行解 (Feasible) 無 可 行 解（ Infeasible） 有最優(yōu)解 （ Optimal） 無 最 優(yōu) 解(Unbounded) 數(shù)學(xué)建模中線性規(guī)劃模型的常用解法 線性規(guī)劃問題的求解在理在理論上有單純型法，在實際建模中常用以下解法： 4. MATLAB 軟件包 主要介紹線性規(guī)劃模型的 MATlAB軟件包和 LINGO軟件包解法 模型求解方法 1. 圖解法 例 1 max z=50x1+100x2 x1 + x2≤300 2x1 + x2≤400 x2≤250 x x2≥0 該問題的最優(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） 注意：若沒有不等式： 存在，則令 A=[ ]， b=[ ]. bAX ?式中： linprog 稱為調(diào)用函數(shù)， C, A, b 稱為輸入?yún)?shù)，全部由用戶 提供，必須按規(guī)定的位置放置在原括號內(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] 若沒有等式約束 : , 則令 Aeq=[ ], beq=[ ]. [2]其中 X0表示初始點 ,設(shè)置它有些情況下可以減少 迭代工作量 be qXA e q ??4. 命令： [x,fval]=linprog(…) 返回最優(yōu)解 ｘ 及 ｘ 處的目標(biāo)函數(shù)值 fval. 解 編寫 M文件 ： c=[ ]。 0 0 0 0。0 0 0 0 ]。700。900]。 beq=[]。0。0。0]。 [x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub) 例 1 m ax 654321 xxxxxxz ?????? 1 2 3 4 5 . 0 .0 1 0 .0 1 0 .0 1 0 .0 3 0 .0 3 0 .0 3 8 5 0x x x x x x? ? ? ? ? ? 41 ?? xx 52 ?? xx 63 ?? xx 0 1 , 2 , , 6jxj ?? To MATLAB (xxgh1) 例 2 321 436m i n xxxz ??? 1 2 . 12 0x x x? ? ? 301 ?x 5002 ?? x 203 ?x 解 : 編寫 M文件 ： c=[6 3 4]。 b=[50]。 beq=[120]。 vub=[]。 A = [ 1 0 0 0 0 0 0 ]。 900]。 beq=[400 600 500]。 vub=[]。 A=[5 3]。 Aeq=[]。 vlb = zeros(2,1)。 %調(diào)用 linprog函數(shù)： [x,fval] = linprog(c,A,b,Aeq,beq,vlb,vub) To MATLAB (xxgh4) 結(jié)果為： x = fval =360 即只需聘用 9個一級檢驗員 . 注： 本問題應(yīng)還有一個約束條件： x x2取整數(shù) .故它是一個整數(shù)線性規(guī)劃問題 .這里把它當(dāng)成一個線性規(guī)劃來解，求得其最優(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)品簡要介紹 美國芝加哥 (Chicago)大學(xué)的 Linus Schrage教授于 1980年前后開發(fā) , 后來成立 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é)生版、高級版、超級版、工業(yè)版、擴展版 … （求解 問題規(guī)模 和 選件 不同） LINDO和 LINGO軟件能求解的優(yōu)化模型 LINGO LINDO 優(yōu)化模型 線性規(guī)劃 (LP) 非線性規(guī)劃 (NLP) 二次規(guī)劃 (QP) 連續(xù)優(yōu)化 整數(shù)規(guī)劃 (IP) 一、 LINDO軟件包 下面我們通過一個例題來說明 LINDO軟件包的使用方法 . 問題 ： 一奶制品加工廠用牛奶生產(chǎn) A1, A2 兩種奶制品，一桶 牛奶可以在甲類設(shè)備上用 12小時生產(chǎn)成 3公斤 A1，或者在乙類設(shè)備上用 8小時加工成 4公斤 ，生產(chǎn)的兩種奶制品全部 能售出，且每公斤 A1獲利 24元，每公斤 A2獲利 16元，現(xiàn)在每天加工廠每天能得到 50桶牛奶的供應(yīng)，每天正式工人總的勞動時間為480小時，并且甲類設(shè)備每天至多能加工 100公斤 A1，乙類設(shè)備的加工能力沒有限制 .試為該廠制定一個生產(chǎn)計劃，使每天獲利最大，并進一步討論以下 3個附加問題。 模型求解 軟件實現(xiàn) LINDO max 72x1+64x2 st 2） x1+x250 3） 12x1+8x2480 4） 3x1100 end OBJECTIVE FUNCTION VALUE 1) VARIABLE VALUE REDUCED COST X1 X2 ROW SLACK OR SURPLUS DUAL PRICES 2) 3) 4) DO RANGE (SENSITIVITY) ANALYSIS? No 20桶牛奶生產(chǎn) A1, 30桶生產(chǎn) A2，利潤 3360元。 x1+x2=。 2*x1+x2=600。 gin(x2)。每百箱乙飲料需用原料 5千克 ,工人 20名 ,可獲利 9萬元 .今工廠共有原料 60千克 ,工人 150名 ,又由于其他條件所限甲飲料產(chǎn)量不超過 800箱 .問如何安排生產(chǎn)計劃 ,即兩種飲料各生產(chǎn)多少使獲利最大 .進一步討論 : 1)若投資 1千克 ,問應(yīng)否作這項投資 . 2)若每 100箱甲飲料獲利可增加 1萬元 ,問應(yīng)否改變生產(chǎn)計劃 . 返 回 運輸問題 Transportation Problem 運輸問題 (Transportation Problem) 以知有 m個生產(chǎn)地點 (source)Ai， i=1， … ， m， 可供應(yīng)某種物資，其供應(yīng)量（產(chǎn)量） (supply)為 ai， i=1， … ，m； 有 n個銷售地點 (destination)Bj， j=1， … ， n， 需要該種物資，其需要量（產(chǎn)量） (demand)為 bj， j=1， … ，n；從 Ai到 Bj運輸單位物資的運價（單價）為 cij；設(shè)Σai=Σbj，這些數(shù)據(jù)可匯總于如下產(chǎn)銷平衡表，現(xiàn)要制定一個使總運費最小的調(diào)運方案。,1,0,1,1m i n111 1????產(chǎn)銷不平衡的運輸問題 Total Supply not Equal to Total Demand 一、產(chǎn)大于銷 (total supply exceeds total demand) ? 產(chǎn)大于銷的運輸問題的特征是 Σ ai Σ bj， 其數(shù)學(xué)模型為： ?????????????????????? ???? ?njmixnjbxmiaxxcfijmijijnjiijminjijij,1。 因為 xi， n+1實際上表示 Ai產(chǎn)地沒有運出去而庫存的物資數(shù)量 。 ???????????????????????? ???????1,1。,1,0,1,1m i n111 1????? 解此問題可假想一個產(chǎn)地 Am+1，其產(chǎn)量為： am+1 = Σ bj－ Σ ai； 若用 xm+1， j表示從 Am+1到 Bj的運量，可令 cm+1， j=0或等于第 Bj產(chǎn)地每缺單位物資的損失。經(jīng)處理后，問題變成了產(chǎn)銷平衡的運輸問題，其數(shù)學(xué)模型為： ?此時，可用表上作業(yè)法求解。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個客戶的單位貨物運輸價見表 供貨棧到客戶的單位貨物運價 客戶 貨棧 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)運數(shù)量，使總的運輸費用最小。模型的篇幅很長，不便于分析修改和擴展。 一、集合定義部分 集合是一組相關(guān)對象構(gòu)成的組合，代表模型中的實際事物，并與數(shù)學(xué)變量與 常量聯(lián)系起來，是實際問題到數(shù)學(xué)的抽象。 每個集合在使用之前需要預(yù)先給出定義，定義集合時要明確三方面的內(nèi)容 ： 集合 的