優(yōu)化建模與l第0章

1、優(yōu)化建模與優(yōu)化建模與LINDO/LINGO軟件軟件第第1章引言章引言原書相關(guān)信息原書相關(guān)信息謝金星謝金星, 薛毅編著薛毅編著, 清華大學(xué)出版社清華大學(xué)出版社, 2005年年7月第月第1版版. 內(nèi)容提要內(nèi)容提要1. 優(yōu)化模型的基本概念優(yōu)化模型的基本概念2. 優(yōu)化問題的建模實(shí)例優(yōu)化問題的建模實(shí)例3. LINDO/LINGO 軟件簡介軟件簡介1. 優(yōu)化模型的基本概念優(yōu)化模型的基本概念 最優(yōu)化是工程技術(shù)、經(jīng)濟(jì)管理、科學(xué)研究、社最優(yōu)化是工程技術(shù)、經(jīng)濟(jì)管理、科學(xué)研究、社會(huì)生活中經(jīng)常遇到的問題會(huì)生活中經(jīng)常遇到的問題, 如如:優(yōu)化模型和算法的重要意義優(yōu)化模型和算法的重要意義結(jié)構(gòu)設(shè)計(jì)結(jié)構(gòu)設(shè)計(jì)資源分配資源分配生產(chǎn)

2、計(jì)劃生產(chǎn)計(jì)劃運(yùn)輸方案運(yùn)輸方案解決優(yōu)化問題的手段解決優(yōu)化問題的手段 經(jīng)驗(yàn)積累，主觀判斷經(jīng)驗(yàn)積累，主觀判斷 作試驗(yàn)，比優(yōu)劣作試驗(yàn)，比優(yōu)劣 建立數(shù)學(xué)模型，求解最優(yōu)策略建立數(shù)學(xué)模型，求解最優(yōu)策略最優(yōu)化最優(yōu)化: : 在一定條件下，尋求使目標(biāo)最大在一定條件下，尋求使目標(biāo)最大( (小小) )的決策的決策 優(yōu)化問題三要素：決策變量；目標(biāo)函數(shù)；約束條件優(yōu)化問題三要素：決策變量；目標(biāo)函數(shù)；約束條件約約束束條條件件決策變量決策變量優(yōu)化問題的一般形式優(yōu)化問題的一般形式njiDxljxgmixhtsxf,.,1, 0)(,.,1, 0)(. .)(min 無約束優(yōu)化無約束優(yōu)化(沒有約束沒有約束)與約束優(yōu)化與約束優(yōu)化(有

3、約束有約束) 可行解（只滿足約束）與最優(yōu)解可行解（只滿足約束）與最優(yōu)解(取到最優(yōu)值取到最優(yōu)值)目標(biāo)函數(shù)目標(biāo)函數(shù)局部最優(yōu)解與整體最優(yōu)解局部最優(yōu)解與整體最優(yōu)解 局部最優(yōu)解局部最優(yōu)解 (Local Optimal Solution, 如如 x1 ) 整體最優(yōu)解整體最優(yōu)解 (Global Optimal Solution, 如如 x2 )x*f(x)x1x2o優(yōu)化模型的優(yōu)化模型的簡單分類簡單分類 線性規(guī)劃線性規(guī)劃(LP) 目標(biāo)和約束均為線性函數(shù)目標(biāo)和約束均為線性函數(shù) 非線性規(guī)劃非線性規(guī)劃(NLP) 目標(biāo)或約束中存在非線性函數(shù)目標(biāo)或約束中存在非線性函數(shù) 二次規(guī)劃二次規(guī)劃(QP) 目標(biāo)為二次函數(shù)、約束為線

4、性目標(biāo)為二次函數(shù)、約束為線性 整數(shù)規(guī)劃整數(shù)規(guī)劃(IP) 決策變量決策變量(全部或部分全部或部分)為整數(shù)為整數(shù) 整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃(ILP)，整數(shù)非線性規(guī)劃，整數(shù)非線性規(guī)劃(INLP) 純整數(shù)規(guī)劃純整數(shù)規(guī)劃(PIP), 混合整數(shù)規(guī)劃混合整數(shù)規(guī)劃(MIP) 一般整數(shù)規(guī)劃，一般整數(shù)規(guī)劃，0-1（整數(shù)）規(guī)劃（整數(shù)）規(guī)劃njiDxljxgmixhtsxf,.,1, 0)(,.,1, 0)(. .)(min連連續(xù)續(xù)優(yōu)優(yōu)化化離離散散優(yōu)優(yōu)化化數(shù)學(xué)規(guī)劃數(shù)學(xué)規(guī)劃優(yōu)化模型的簡單分類和求解難度優(yōu)化模型的簡單分類和求解難度 優(yōu)化線性規(guī)劃非線性規(guī)劃二次規(guī)劃連續(xù)優(yōu)化整數(shù)規(guī)劃 問題求解的難度增加 2. 優(yōu)化問題的建模實(shí)

5、例優(yōu)化問題的建模實(shí)例 1桶牛奶 3公斤A1 12小時(shí) 8小時(shí) 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶桶牛奶 時(shí)間時(shí)間480小時(shí)小時(shí) 至多加工至多加工100公斤公斤A1 制訂生產(chǎn)計(jì)劃，使每天獲利最大制訂生產(chǎn)計(jì)劃，使每天獲利最大 35元可買到元可買到1桶牛奶，買嗎？若買，每天最多買多少桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元? A1的獲利增加到的獲利增加到 30元元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？公斤，應(yīng)否改變生產(chǎn)計(jì)劃？ 每天：每天：線性規(guī)劃模型例線性規(guī)劃模型例1.1: 奶制品生產(chǎn)計(jì)劃奶制品生產(chǎn)計(jì)劃

6、1桶牛奶 3公斤A1 12小時(shí) 8小時(shí) 4公斤A2 或獲利24元/公斤 獲利16元/公斤 x1桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1 x2桶牛奶生產(chǎn)桶牛奶生產(chǎn)A2 獲利獲利 243x1 獲利獲利 164 x2 原料供應(yīng)原料供應(yīng) 5021 xx勞動(dòng)時(shí)間勞動(dòng)時(shí)間 48081221 xx加工能力加工能力 10031x決策變量決策變量 目標(biāo)函數(shù)目標(biāo)函數(shù) 216472xxzMax每天獲利每天獲利約束條件約束條件非負(fù)約束非負(fù)約束 0,21xx線性線性規(guī)劃規(guī)劃模型模型(LP)時(shí)間時(shí)間480小時(shí)小時(shí) 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天模型分析與假設(shè)模型分析與假設(shè) 比比例例性性 可可加加性性 連續(xù)

7、性連續(xù)性 xi對(duì)目標(biāo)函數(shù)的對(duì)目標(biāo)函數(shù)的“貢獻(xiàn)貢獻(xiàn)”與與xi取值成取值成正比正比 xi對(duì)約束條件的對(duì)約束條件的“貢獻(xiàn)貢獻(xiàn)”與與xi取值成取值成正比正比 xi對(duì)目標(biāo)函數(shù)的對(duì)目標(biāo)函數(shù)的“貢獻(xiàn)貢獻(xiàn)”與與xj取值無取值無關(guān)關(guān) xi對(duì)約束條件的對(duì)約束條件的“貢獻(xiàn)貢獻(xiàn)”與與xj取值無取值無關(guān)關(guān) xi取值連續(xù)取值連續(xù) A1,A2每公斤的獲利是與各每公斤的獲利是與各自產(chǎn)量無關(guān)的常數(shù)自產(chǎn)量無關(guān)的常數(shù)每桶牛奶加工出每桶牛奶加工出A1,A2的數(shù)量的數(shù)量和時(shí)間是與各自產(chǎn)量無關(guān)的常和時(shí)間是與各自產(chǎn)量無關(guān)的常數(shù)數(shù)A1,A2每公斤的獲利是與相每公斤的獲利是與相互產(chǎn)量無關(guān)的常數(shù)互產(chǎn)量無關(guān)的常數(shù)每桶牛奶加工出每桶牛奶加工出A1,

8、A2的數(shù)量的數(shù)量和時(shí)間是與相互產(chǎn)量無關(guān)的常和時(shí)間是與相互產(chǎn)量無關(guān)的常數(shù)數(shù)加工加工A1,A2的牛奶桶數(shù)是實(shí)的牛奶桶數(shù)是實(shí)數(shù)數(shù) 線性規(guī)劃模型線性規(guī)劃模型模型求解模型求解 圖解法圖解法 x1x20ABCDl1l2l3l4l55021 xx48081221 xx10031x0,21xx約約束束條條件件50:211 xxl480812:212 xxl1003:13xl0:, 0:2514xlxl216472xxzMax目標(biāo)目標(biāo)函數(shù)函數(shù) Z=0Z=2400Z=3600z=c (常數(shù)常數(shù)) 等值線等值線c在在B(20,30)點(diǎn)得到最優(yōu)解點(diǎn)得到最優(yōu)解目標(biāo)函數(shù)和約束條件是線性函數(shù)目標(biāo)函數(shù)和約束條件是線性函數(shù) 可

9、行域?yàn)橹本€段圍成的凸多邊形可行域?yàn)橹本€段圍成的凸多邊形 目標(biāo)函數(shù)的等值線為直線目標(biāo)函數(shù)的等值線為直線 最優(yōu)解一定在凸多邊最優(yōu)解一定在凸多邊形的某個(gè)頂點(diǎn)取得。形的某個(gè)頂點(diǎn)取得。 求解求解LP的基本思想的基本思想思路：從可行域的某一頂點(diǎn)開始，只需在有限多個(gè)思路：從可行域的某一頂點(diǎn)開始，只需在有限多個(gè)頂點(diǎn)中一個(gè)一個(gè)找下去，一定能得到最優(yōu)解。頂點(diǎn)中一個(gè)一個(gè)找下去，一定能得到最優(yōu)解。LP的約束和目標(biāo)函數(shù)均為線性函數(shù)的約束和目標(biāo)函數(shù)均為線性函數(shù)2維維可行域可行域 線段組成的凸多邊形線段組成的凸多邊形目標(biāo)函數(shù)目標(biāo)函數(shù) 等值線為直線等值線為直線最優(yōu)解最優(yōu)解 凸多邊形的某個(gè)頂點(diǎn)凸多邊形的某個(gè)頂點(diǎn)n維維超平面組成

10、的凸多面體超平面組成的凸多面體等值線是超平面等值線是超平面凸多面體的某個(gè)頂點(diǎn)凸多面體的某個(gè)頂點(diǎn)LPLP的通常解法是單純形法的通常解法是單純形法(G. B. Dantzig, 1947)(G. B. Dantzig, 1947)內(nèi)點(diǎn)算法內(nèi)點(diǎn)算法(Interior point method) 20世紀(jì)世紀(jì)80年代人們提出的一類新的算法年代人們提出的一類新的算法內(nèi)內(nèi)點(diǎn)算法點(diǎn)算法也是迭代法，但不再從可行域的一個(gè)頂點(diǎn)轉(zhuǎn)換也是迭代法，但不再從可行域的一個(gè)頂點(diǎn)轉(zhuǎn)換到另一個(gè)頂點(diǎn)，而是直接從可行域的內(nèi)部逼近最到另一個(gè)頂點(diǎn)，而是直接從可行域的內(nèi)部逼近最優(yōu)解。優(yōu)解。 LPLP其他算法其他算法有效集有效集(Activ

11、e Set)方法方法 LP是是QP的特例（只需令所有二次項(xiàng)為零即可）的特例（只需令所有二次項(xiàng)為零即可） 可以用可以用QP的算法解的算法解QP(如如: 有效集方法有效集方法) 線性規(guī)劃模型的解的幾種情況線性規(guī)劃模型的解的幾種情況 線性規(guī)劃問題線性規(guī)劃問題有可行解有可行解(Feasible)無可行解無可行解（Infeasible）有最優(yōu)解（有最優(yōu)解（Optimal）無最優(yōu)解無最優(yōu)解(Unbounded)牌牌號(hào)號(hào)產(chǎn)量成本價(jià)格甲甲x1q1p1乙乙x2q2p2假設(shè)假設(shè)A產(chǎn)銷平衡產(chǎn)銷平衡假設(shè)假設(shè)Bp隨隨x (兩種牌號(hào)兩種牌號(hào))增加而減小，呈線性關(guān)系增加而減小，呈線性關(guān)系12111211121211111,

12、 0,aaaabxaxabp某廠生產(chǎn)兩個(gè)牌號(hào)的同一種產(chǎn)品，如何確定產(chǎn)量使利潤最大某廠生產(chǎn)兩個(gè)牌號(hào)的同一種產(chǎn)品，如何確定產(chǎn)量使利潤最大21222221222212122, 0,aaaabxaxabp二次規(guī)劃模型例二次規(guī)劃模型例1.21.2：產(chǎn)銷計(jì)劃問題：產(chǎn)銷計(jì)劃問題22211121,)()(),(max21xqpxqpxxzxx目標(biāo)目標(biāo)利潤最大利潤最大=（100-x1-0.1 x2-2）x1+（280-0.2x1-2x2-3）x2=98 x1 + 277 x2 x12 0.3 x1 x2 2x22 約束約束x1 + x2 100 x1 2 x2x1 , x2 0 二次規(guī)劃模型二次規(guī)劃模型(QP)

13、若還要求產(chǎn)量為整數(shù)，則是整數(shù)二次規(guī)劃模型若還要求產(chǎn)量為整數(shù)，則是整數(shù)二次規(guī)劃模型(IQP)非線性規(guī)劃模型例非線性規(guī)劃模型例1.31.3：選址問題：選址問題某公司有某公司有6個(gè)建筑工地，位置坐標(biāo)為個(gè)建筑工地，位置坐標(biāo)為(ai, bi) (單位：公里單位：公里),水泥日用量水泥日用量di (單位：噸）單位：噸）ia1.258.750.55.7537.25b1.250.754.7556.57.75d35476111)現(xiàn)有 2 料場，位于 A (5, 1), B (2, 7),記(xj,yj),j=1,2, 日儲(chǔ)量 ej各有 20 噸。假設(shè)：料場假設(shè)：料場和工地之間和工地之間有直線道路有直線道路目標(biāo)：

14、制定每天的供應(yīng)計(jì)劃，即從 A, B 兩料場分別向各工地運(yùn)送多少噸水泥，使總的噸公里數(shù)最小。用例中數(shù)據(jù)計(jì)算，最優(yōu)解為i1234561ic（料料場場 A）3507012ic（料料場場 B）00406102 , 1,6,.,1,. .)()(min612121612/122jecidctsbyaxcjijiiijjjiijijij線性規(guī)劃模型線性規(guī)劃模型(LP)決策變量：決策變量：ci j (料場料場j到工地到工地i的的運(yùn)量）運(yùn)量）12維維選址問題：選址問題：NLPNLP2）改建兩個(gè)新料場，需要確定新料場位置）改建兩個(gè)新料場，需要確定新料場位置(xj,yj)和運(yùn)量和運(yùn)量cij ，在其它條件不變下使總

15、噸公里數(shù)最小。，在其它條件不變下使總噸公里數(shù)最小。2 , 1,6,.,1,. .)()(min612121612/122jecidctsbyaxcjijiiijjjiijijij決策變量：決策變量：ci j，(xj,yj)16維維非線性規(guī)劃模型非線性規(guī)劃模型(NLP)整數(shù)規(guī)劃整數(shù)規(guī)劃 - - 例例1.4: 1.4: 聘用方案聘用方案某 服 務(wù) 部 門 一 周 中 每 天 需 要 不 同 數(shù) 目 的 雇員 ： 周 一 到 周 四 每 天 至 少 50 人 ， 周 五 和 周 日每 天 至 少 80 人 ， 周 六 至 少 90 人 。決策變量：周一至周日每天決策變量：周一至周日每天(新新)聘用人

16、數(shù)聘用人數(shù) x1, x2,x7目標(biāo)函數(shù)：目標(biāo)函數(shù)：7天天(新新)聘用人數(shù)之和聘用人數(shù)之和約束條件：周一至周日每天需要人數(shù)約束條件：周一至周日每天需要人數(shù)現(xiàn) 規(guī) 定 應(yīng) 聘 者 需 連 續(xù) 工 作5 天 ， 試 確 定 聘 用方 案 ， 即 周 一 到 周 日 每 天 聘 用 多 少 人 ， 使 在滿 足 需 要 的 條 件 下 聘 用 總 人 數(shù) 最 少 。80908050505050.min765436543254321743217632176521765417654321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxz連續(xù)工作連續(xù)工作5天天5017

17、654xxxxx周一工作的應(yīng)是周一工作的應(yīng)是(上上)周四至周一聘用的周四至周一聘用的設(shè)系統(tǒng)已進(jìn)入穩(wěn)態(tài)（不是開始的幾周）設(shè)系統(tǒng)已進(jìn)入穩(wěn)態(tài)（不是開始的幾周）聘用方案聘用方案即為非負(fù)整數(shù)，Zxi整數(shù)規(guī)劃整數(shù)規(guī)劃模型模型(IP)(IP)丁的蛙泳成績退步到丁的蛙泳成績退步到115”2115”2；戊的自由泳成績；戊的自由泳成績進(jìn)步到進(jìn)步到57”5, 57”5, 組成接力隊(duì)的方案是否應(yīng)該調(diào)整？組成接力隊(duì)的方案是否應(yīng)該調(diào)整？如何選拔隊(duì)員組成如何選拔隊(duì)員組成4 4100100米混合泳接力隊(duì)米混合泳接力隊(duì)? ?0-1規(guī)劃規(guī)劃 混合泳接力隊(duì)的選拔混合泳接力隊(duì)的選拔 甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳106”857”211

18、8”110”107”4仰泳仰泳115”6106”107”8114”2111”蛙泳蛙泳127”106”4124”6109”6123”8自由泳自由泳58”653”59”457”2102”4例例1.5： 5名候選人的百米成績名候選人的百米成績窮舉法：組成接力隊(duì)的方案共有窮舉法：組成接力隊(duì)的方案共有5!=1205!=120種。種。目標(biāo)目標(biāo)函數(shù)函數(shù)若選擇隊(duì)員若選擇隊(duì)員i i參加泳姿參加泳姿j j 的比賽，記的比賽，記xij=1, xij=1, 否則記否則記xij=0 xij=0 0-1規(guī)劃模型規(guī)劃模型 cij(秒秒)隊(duì)員隊(duì)員i 第第j 種泳姿的百米成績種泳姿的百米成績約束約束條件條件每人最多入選泳姿之一

19、每人最多入選泳姿之一 ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.44151jiijijxcZMin每種泳姿有且只有每種泳姿有且只有1 1人人 5, 1, 141ixjij4, 1, 151jxiij0-1規(guī)劃規(guī)劃:整數(shù)規(guī)劃的特例整數(shù)規(guī)劃的特例整數(shù)規(guī)劃問題整數(shù)規(guī)劃問題一般形式一般形式ljxgmixhtsxfjiZxn,.,1, 0)(,.,1, 0)(. .)(min 整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃(ILP) 目標(biāo)和約束均為線性函數(shù)目標(biāo)和約束均為線性函

20、數(shù) 整數(shù)非線性規(guī)劃整數(shù)非線性規(guī)劃(NLP) 目標(biāo)或約束中存在非線性函數(shù)目標(biāo)或約束中存在非線性函數(shù)整數(shù)規(guī)劃問題的分類整數(shù)規(guī)劃問題的分類 純純(全全)整數(shù)規(guī)劃整數(shù)規(guī)劃(PIP) 決策變量均為整數(shù)決策變量均為整數(shù) 混合整數(shù)規(guī)劃混合整數(shù)規(guī)劃(MIP) 決策變量有整數(shù)，也有實(shí)數(shù)決策變量有整數(shù)，也有實(shí)數(shù) 0-1規(guī)劃規(guī)劃 決策變量只取決策變量只取0或或1取消整數(shù)規(guī)劃中決策變量為整數(shù)的限制（松弛），對(duì)應(yīng)的連續(xù)優(yōu)化問題稱為原問題的松弛問題整數(shù)規(guī)劃問題對(duì)應(yīng)的松弛問題整數(shù)規(guī)劃問題對(duì)應(yīng)的松弛問題松弛問題松弛整數(shù)規(guī)劃問題最優(yōu)解最優(yōu)解整數(shù)非整數(shù)整數(shù)舍入下界（對(duì)Min問題）上界（對(duì)Max問題）非最優(yōu)解用連續(xù)優(yōu)化方法求解松弛

21、問題，如果松弛問題最優(yōu)解（分量）全為整數(shù)，則也是原整數(shù)規(guī)劃問題的最優(yōu)解對(duì)松弛問題的最優(yōu)解（分量）舍入為整數(shù)，得到的往往不是原整數(shù)規(guī)劃問題的最優(yōu)解（甚至不是可行解）IPIP可行解對(duì)應(yīng)于整點(diǎn)可行解對(duì)應(yīng)于整點(diǎn)A(2,2)A(2,2)和和B(1,1),B(1,1),而最優(yōu)解為而最優(yōu)解為A A點(diǎn)點(diǎn). .但但LPLP松弛的最優(yōu)解為松弛的最優(yōu)解為C(3.5,2.5) C(3.5,2.5) 目標(biāo)函數(shù)下降方向目標(biāo)函數(shù)下降方向 x1x2CABO且為整數(shù)0,45956. .85max21212121xxxxxxtsxxzx1x20Po69Zmax56去掉整數(shù)限制后，可行域?yàn)辄c(diǎn)（0,0), (6,0), (0,5),

22、 P (2.25,3.75) 圍成的4邊形LP最優(yōu)解PP的舍入解最靠近P的可行解IP最優(yōu)解（2.25，3.75）（2，4）（2，3）（0，5）z=41.25不可行z=34z=40從LP最優(yōu)解經(jīng)過簡單的 “移動(dòng)”不一定能得到IP最優(yōu)解例例1.6基本思想：隱式地枚舉一切可行解（基本思想：隱式地枚舉一切可行解（“分而治之分而治之”）所謂分枝，就是逐次對(duì)解空間（可行域）進(jìn)行劃分；而所謂分枝，就是逐次對(duì)解空間（可行域）進(jìn)行劃分；而所謂定界，是指對(duì)于每個(gè)分枝（或稱子域），要計(jì)算原所謂定界，是指對(duì)于每個(gè)分枝（或稱子域），要計(jì)算原問題的最優(yōu)解的下界（對(duì)極小化問題）問題的最優(yōu)解的下界（對(duì)極小化問題）. . 這些

23、下界用來這些下界用來在求解過程中判定是否需要對(duì)目前的分枝進(jìn)一步劃分，在求解過程中判定是否需要對(duì)目前的分枝進(jìn)一步劃分，也就是盡可能去掉一些明顯的非最優(yōu)點(diǎn)，避免完全枚舉也就是盡可能去掉一些明顯的非最優(yōu)點(diǎn)，避免完全枚舉. . 分枝定界法（分枝定界法（B&B: Branch and Bound）對(duì)于極小化問題，在子域上解LP，其最優(yōu)值是IP限定在該子域時(shí)的下界；IP任意可行點(diǎn)的函數(shù)值是IP的上界。 這里僅介紹整數(shù)線性規(guī)劃的分枝定界算法這里僅介紹整數(shù)線性規(guī)劃的分枝定界算法無無約約束束優(yōu)優(yōu)化化更多的優(yōu)化問題更多的優(yōu)化問題線線性性規(guī)規(guī)劃劃非非線線性性規(guī)規(guī)劃劃網(wǎng)網(wǎng)絡(luò)絡(luò)優(yōu)優(yōu)化化組組合合優(yōu)優(yōu)化化整整數(shù)數(shù)規(guī)

24、規(guī)劃劃不不確確定定規(guī)規(guī)劃劃多多目目標(biāo)標(biāo)規(guī)規(guī)劃劃目目標(biāo)標(biāo)規(guī)規(guī)劃劃動(dòng)動(dòng)態(tài)態(tài)規(guī)規(guī)劃劃連續(xù)優(yōu)化連續(xù)優(yōu)化離散優(yōu)化離散優(yōu)化從其他角度分類從其他角度分類 應(yīng)用廣泛：生產(chǎn)和運(yùn)作管理、經(jīng)濟(jì)與金融、圖論和網(wǎng)應(yīng)用廣泛：生產(chǎn)和運(yùn)作管理、經(jīng)濟(jì)與金融、圖論和網(wǎng)絡(luò)優(yōu)化、目標(biāo)規(guī)劃問題、對(duì)策論、排隊(duì)論、存儲(chǔ)論，絡(luò)優(yōu)化、目標(biāo)規(guī)劃問題、對(duì)策論、排隊(duì)論、存儲(chǔ)論，以及更加綜合、更加復(fù)雜的決策問題等以及更加綜合、更加復(fù)雜的決策問題等 實(shí)際問題規(guī)模往往較大，用軟件求解比較方便實(shí)際問題規(guī)模往往較大，用軟件求解比較方便3. LINDO/LINGO軟件簡介軟件簡介常用優(yōu)化軟件常用優(yōu)化軟件 1. LINDO/LINGO軟件軟件2. MATLAB優(yōu)

25、化工具箱優(yōu)化工具箱 / Mathematic的優(yōu)化功能的優(yōu)化功能3. SAS(統(tǒng)計(jì)分析統(tǒng)計(jì)分析)軟件的優(yōu)化功能軟件的優(yōu)化功能4. EXCEL軟件的優(yōu)化功能軟件的優(yōu)化功能5. 其他（如其他（如CPLEX等）等）MATLABMATLAB優(yōu)化工具箱能求解的優(yōu)化模型優(yōu)化工具箱能求解的優(yōu)化模型優(yōu)化工具箱優(yōu)化工具箱3.0 (MATLAB 7.0 R14)連續(xù)優(yōu)化連續(xù)優(yōu)化離散優(yōu)化離散優(yōu)化無約束優(yōu)化無約束優(yōu)化非線性非線性極小極小fminunc非光滑非光滑(不可不可微微)優(yōu)化優(yōu)化fminsearch非線性非線性方程方程(組組)fzerofsolve全局全局優(yōu)化優(yōu)化暫缺暫缺非線性非線性最小二乘最小二乘lsqnon

26、linlsqcurvefit線性規(guī)劃線性規(guī)劃linprog純純0-1規(guī)劃規(guī)劃 bintprog一般一般IP(暫缺暫缺)非線性規(guī)劃非線性規(guī)劃fminconfminimaxfgoalattainfseminf上下界約束上下界約束fminbndfminconlsqnonlinlsqcurvefit約束線性約束線性最小二乘最小二乘lsqnonneglsqlin約束優(yōu)化約束優(yōu)化二次規(guī)劃二次規(guī)劃quadprogLINDO LINDO 公司軟件產(chǎn)品簡要介紹公司軟件產(chǎn)品簡要介紹 美國芝加哥美國芝加哥(Chicago)大學(xué)的大學(xué)的Linus Schrage教授于教授于1980年前后開發(fā)年前后開發(fā), 后來成立后來

27、成立 LINDO系統(tǒng)公司（系統(tǒng)公司（LINDO Systems Inc.），）， 網(wǎng)址：網(wǎng)址： LINDO: Linear INteractive and Discrete Optimizer (V6.1)LINDO API: LINDO Application Programming Interface (V4.1)LINGO: Linear INteractive General Optimizer (V10.0)Whats Best!: (SpreadSheet e.g. EXCEL) (V8.0)演示演示(試用試用)版、高級(jí)版、超級(jí)版、工業(yè)版、擴(kuò)展版版、高級(jí)版、超級(jí)版、工業(yè)版、擴(kuò)展版 （求解問題規(guī)模和選件不同）（求解問題規(guī)模和選件不同）LINDO/LINGO軟件能求解的模型軟件能求解的模型優(yōu)化優(yōu)化線性規(guī)劃線性規(guī)劃非線性規(guī)劃非線性規(guī)劃二次規(guī)劃二次規(guī)劃連續(xù)優(yōu)化連續(xù)優(yōu)化整數(shù)規(guī)劃整數(shù)規(guī)劃 LINDOLINGOLINGO軟件的功能與