2011優(yōu)化模型選講

優(yōu)化問題三要素：決策變量；目標函數(shù)；約束條件約束條件決策變量優(yōu)化問題的一般形式目標函數(shù)有人統(tǒng)計：優(yōu)化問題占CUMCM賽題的一半以上（1/3~2/3）建模時需要注意的幾個基本問題

1、盡量使用實數(shù)優(yōu)化，減少整數(shù)約束和整數(shù)變量2、盡量使用光滑優(yōu)化，減少非光滑約束的個數(shù)如：盡量少使用絕對值、符號函數(shù)、多個變量求最大/最小值、四舍五入、取整函數(shù)等3、盡量使用線性模型，減少非線性約束和非線性變量的個數(shù)（如x/y<5改為x<5y）4、合理設定變量上下界，盡可能給出變量初始值5、模型中使用的參數(shù)數(shù)量級要適當(如小于103)優(yōu)化建模如何創(chuàng)新？方法1：大膽創(chuàng)新，別出心裁

----采用有特色的目標函數(shù)、約束條件等

----你用非線性規(guī)劃，我用線性規(guī)劃

----你用整數(shù)/離散規(guī)劃，我用連續(xù)規(guī)劃/網絡優(yōu)化----……

方法2：細致入微，滴水不漏

----對目標函數(shù)、約束條件處理特別細致

----有算法設計和分析，不僅僅是簡單套用軟件

----敏感性分析詳細/全面

----……CUMCM-2005B:DVD在線租賃命題人：余剛先生（教授）時任亞馬遜公司全球供應鏈運營副總裁曾任美國德州大學奧斯汀分校管理學院JackG.Taylor講席教授獲多項美國專利，1995年創(chuàng)建美國科萊科技公司(CALEB

Technologies

Corp.)并任董事長和總裁航班管理：2001年為美國大陸航空公司所創(chuàng)造的價值超過6000萬美元，獲2002年運籌學與管理科學應用FranzEdelman獎(運籌學與管理科學應用的“世界杯”)CUMCM-2005B:DVD在線租賃網上DVD在線租賃業(yè)務（2005年時的背景）亞馬遜英國公司(amazon.co.uk)；美國和等；歐洲等著名公司租賃的DVD多達幾萬種，用戶多達幾十萬~幾百萬，有的包括多個配送中心題目：會員每月最多可租賃兩次，每次３張DVD第（1）、（2）問：分別考慮購買和分發(fā)子問題第（3）問：同時考慮購買和分發(fā)第（4）問：自己提出新問題，嘗試建模和求解問題1–網站購買DVD的數(shù)量調查1000個會員，愿意觀看這些DVD的人數(shù)如表;歷史數(shù)據顯示，60%的會員每月租2次，40%租1次;網站10萬個會員，每種DVD應該至少準備多少張，才能保證希望看到該DVD的會員中至少50%在一個月內能夠看到該DVD?如要保證三個月內至少95%能夠看到該DVD呢？

DVD名稱DVD1DVD2DVD3DVD4DVD5愿看人數(shù)200100502510p50.0250.01問題1:網站購買DVD的數(shù)量(x)假設：每種DVD獨立考慮（聯(lián)合考慮沒有足夠信息）希望看到該DVD的會員數(shù)量：確定？隨機?。。”ＷC一個月至少P%有需求的會員能得到滿足?會員希望看該DVD的概率為p網站的會員總數(shù)為nn比較大，可用正態(tài)分布N(np,npq)近似（q=1-p）

二項分布N(n,p)可近似認為1個月該DVD實際可用張數(shù)是1.6x張一定置信水平下成立！問題1:網站購買DVD的數(shù)量(x)置信水平１－αau1-ξ～N(np,npq)問題1:網站購買DVD的數(shù)量(x)１－α＝0.95;n=100000;P%=50%DVD名稱DVD1DVD2DVD3DVD4DVD5合計p50.0250.01x62903155158579732312150推廣到３個月的模型類似考慮：１張DVD在三個月內可以用多少次？歸還規(guī)律／出借規(guī)律的探討將變得復雜一些，一般需要在更多的假設下，才能得到（如還回網站的DVD是否一定能馬上分給某個需要的會員？）問題1:網站購買DVD的數(shù)量(x)其他模型：數(shù)值模擬（仿真）：需交代詳細過程

（歸還規(guī)律？出借規(guī)律）其他理解：例如認為表中給出的只是初始時段(一個月或半個月)的需求，并進一步假設以后時段的需求持續(xù)不變或按某種規(guī)律變化

（排隊論？隨機決策？）需求上限：一定置信水平下得到上限M

（x=P%*M/1.6）問題及數(shù)據形式(EXCEL表格)DVD編號D001D002D003D004…現(xiàn)有數(shù)量10401520…會員在線訂單C00016000…C00020000…C00030003…C00040000…………………cjaij問題2–DVD最優(yōu)分配模型一：0-1規(guī)劃模型（最常見）答卷中的問題：目標定義不合理約束不完整軟件使用不當(LINGO求解容易,Why?)定義滿意度模型問題2–DVD最優(yōu)分配模型二：網絡優(yōu)化模型–最小費用最大流12…n12…m3,0cj,0st會員DVDaij’=aij(aij

>0)aij’=M(aij

=0)

(或沒有弧)存在多項式時間算法兩個模型等價嗎?問題2–DVD最優(yōu)分配上海交大在一定的假設下，把問題近似分解成前面考慮過的購買和分發(fā)兩個子問題。例如，有的論文先根據會員訂單統(tǒng)計DVD的需求情況，確定DVD購買量，然后用前一問中建立的模型進行第一次分發(fā)，再對網站是否知道哪些會員租賃兩次作出一定假設，進行第二次分發(fā)。有的論文對前一問中建立的模型進行一定修改，建立購買和分發(fā)統(tǒng)一的多目標數(shù)學規(guī)劃模型，且同時考慮兩次分發(fā)和服務水平約束，不過往往在二次分配和服務水平約束方面考慮有些缺陷?？紤]到一個月內可能一個會員要發(fā)貨兩次，這又是一個多階段的決策問題，建立隨機決策模型并尋找最優(yōu)決策是可能的（例如采用馬氏決策方法），但由于后一階段決策時需要考慮前一階段哪些會員歸還了哪些DVD，因此這樣建立模型的難度較大，評委們在評閱中幾乎沒有見到非常成功的論文。采用數(shù)值模擬（仿真）建模和求解，或檢驗其他模型。問題３