運(yùn)籌帷幄之中決勝千里之外.ppt

LinearProgramming 運(yùn)籌學(xué)課件 線性規(guī)劃 線性規(guī)劃問題可行區(qū)域與基本可行解單純形算法初始可行解對偶理論靈敏度分析計(jì)算軟件案例分析 線性規(guī)劃問題 線性規(guī)劃實(shí)例生產(chǎn)計(jì)劃問題運(yùn)輸問題線性規(guī)劃模型一般形式規(guī)范形式標(biāo)準(zhǔn)形式形式轉(zhuǎn)換概念 某工廠用三種原料生產(chǎn)三種產(chǎn)品 已知的條件如表2 1 1所示 試制訂總利潤最大的生產(chǎn)計(jì)劃 生產(chǎn)計(jì)劃問題 問題分析 模型 計(jì)算結(jié)果 運(yùn)輸問題 問題分析 模型 一般形式 目標(biāo)函數(shù) 約束條件 注釋 規(guī)范形式 標(biāo)準(zhǔn)形式 概念 模型轉(zhuǎn)換 約束轉(zhuǎn)換實(shí)例 目標(biāo)轉(zhuǎn)換 變量轉(zhuǎn)換 約束轉(zhuǎn)換 不等式變等式不等式變不等式 等式變不等式 不等式變等式 松弛變量 剩余變量 不等式變不等式 例2 1 3把問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式 可行區(qū)域與基本可行解 圖解法可行域的幾何結(jié)構(gòu)基本可行解與基本定理 圖解法 例2 2 1解線性規(guī)劃 注釋 可能出現(xiàn)的情況 可行域是空集可行域無界無最優(yōu)解最優(yōu)解存在且唯一 則一定在頂點(diǎn)上達(dá)到最優(yōu)解存在且不唯一 一定存在頂點(diǎn)是最優(yōu)解 可行域的幾何結(jié)構(gòu) 基本假設(shè)凸集可行域的凸性 基本假設(shè) 凸集 可行域的凸性 問題 基本可行解與基本定理 定義基本定理問題 基本可行解定義 基本定理 問題 單純形算法 理論方法算法步驟單純形表算例 理論方法 定理2 3 1 定理2 3 2 定理2 3 3 算法步驟 單純形表 算例 初始單純形表 迭代1 迭代2 初始解 兩階段法大M法說明 兩階段法 基本思想第一階段 通過求解輔助問題的最優(yōu)基可行解得到原問題的初始基可行解 第二階段 求原問題的最優(yōu)解算例 輔助問題 原輔助題問與題的關(guān)系 求輔助問題的三種情況 算例 第1階段 第1階段 第1階段 第1階段 第1階段 第2階段 大M法 說明 對偶理論 對偶規(guī)劃對偶理論對偶單純形算法 對偶規(guī)劃 標(biāo)準(zhǔn)形式線性規(guī)劃的對偶規(guī)劃規(guī)范形式線性規(guī)劃的對偶規(guī)劃一般形式線性規(guī)劃的對偶規(guī)劃實(shí)例 標(biāo)準(zhǔn)形式的對偶規(guī)劃 規(guī)范形式的對偶規(guī)劃 一般形式的對偶規(guī)劃 實(shí)例 對偶理論 定理2 5 1 定理2 5 2 定理2 5 5 對偶單純形算法 基本思想算法過程算例 基本思想 單純形算法 對偶單純形 正則解 正則解 對偶可行解 正則解的單純性表 規(guī)劃無可行解 保持正則性 入基變量 否 算法過程 初始正則解 是則停止 得最優(yōu)解 選出基變量 檢查是否無可行解 是則停止 否 無最優(yōu)解 選入基變量 計(jì)算典式檢驗(yàn)數(shù) 算例 迭代 迭代 迭代 靈敏度分析 概況改變價(jià)值向量改變右端向量 概況 信息的不確定性信息的變化 價(jià)值向量 市場變化右端向量 資源變化系數(shù)矩陣 技術(shù)進(jìn)步認(rèn)知的誤差分析方法靜態(tài)分析 比較靜態(tài)分析 動(dòng)態(tài)分析 改變價(jià)值向量 一般改變情況改變非基變量的價(jià)值向量改變基變量的價(jià)值向量算例 一般改變 非基變量 基變量 算例 改變右端向量 基本思想算例 基本思想 算例 計(jì)算軟件 LinDoLinGoMatlab LinDo 輸入模型求解點(diǎn)擊求解按鈕即可結(jié)果 輸入模型 注釋內(nèi)容 可用中文 目標(biāo)函數(shù) 最大 max 最小 min 大小寫不分max3x1 5x2 4x3 約束 以subjectto開始subjectto2x1 3x2 15002x2 4x3 8003x1 2x2 5x3 2000end 注意事項(xiàng) 變量以字母開頭 下標(biāo)寫在后面 系數(shù)與邊量之間加空格不等號為 與 等同變量非負(fù)約束可省略結(jié)束時(shí)以end標(biāo)示 結(jié)果 LPOPTIMUMFOUNDATSTEP3OBJECTIVEFUNCTIONVALUE1 2675 000VARIABLEVALUEREDUCEDCOSTX1375 0000000 000000X2250 0000000 000000X375 0000000 000000ROWSLACKORSURPLUSDUALPRICES2 0 0000001 0500003 0 0000000 6250004 0 0000000 300000 LinGo 輸入模型LinDo模式LinGo模式求解點(diǎn)擊求解按鈕即可結(jié)果 LinDo輸入模式 model MAX 3 x1 5 x2 4 x3 2 x1 3 x2 1500 2 x2 4 x3 800 3 x1 2 x2 5 x3 2000 end 注意與LinDo的區(qū)別 目標(biāo)函數(shù)中加等號變量與系數(shù)之間用 Model end可省略 LinGo模式 集合部分 model 開始sets 定義集合ve 1 3 c x co 1 3 b ma co ve a endsets 注 集表達(dá)式 名稱 成員 屬性名稱 初始集 屬性 定義數(shù)據(jù) data 定義數(shù)據(jù)c 354 ba 230024325 Enddata 注 數(shù)據(jù)的大小與集合定義中一致 分量中間用空格或逗號分開 數(shù)據(jù)結(jié)束后用分號 調(diào)用函數(shù) max sum ve j c j x j for co i sum ve j a i j x j b i 主要函數(shù) for set set index list condition expression sum set set index list condition expression min max set set index list condition expression 結(jié)果 Globaloptimalsolutionfoundatiteration 3Objectivevalue 2675 000VariableValueReducedCostC 1 3 0000000 000000C 2 5 0000000 000000C 3 4 0000000 000000X 1 375 00000 000000X 2 250 00000 000000X 3 75 000000 000000 B 1 1500 0000 000000B 2 800 00000 000000B 3 2000 0000 000000A 1 1 2 0000000 000000A 1 2 3 0000000 000000A 1 3 0 0000000 000000A 2 1 0 0000000 000000A 2 2 2 0000000 000000A 2 3 4 0000000 000000A 3 1 3 0000000 000000A 3 2 2 0000000 000000A 3 3 5 0000000 000000 RowSlackorSurplusDualPrice12675 0001 00000020 0000001 05000030 0000000 625000040 0000000 3000000 Scilab函數(shù) 命令1 x lagr f linpro p C b x0 命令2 x lagr f linpro p C b ci cs x0 命令3 x lagr f linpro p C b ci cs me x0 命令4 x lagr f linpro p C b ci cs me x0 imp 命令5 x1 crit karmarkar a b c x0 注意事項(xiàng) 命令1 問題形式minp xs t C x b x lagr f linpro p C b x0 命令2 命令3 命令4 x lagr f linpro p C b ci cs me x0 imp 問題形式minp xs t C j x b j j 1 meC j x b j j me 1 me mdci x cs指定初始可行解x0 命令5 x1 crit karmarkar a b c x0 問題形式minc xs t a x bx 0 注意事項(xiàng) 命令2和3中x0可省略 但命令4和5中不可省略向量都是列向量 參數(shù)的順序不可換命令3中等式約束必須在前面 人力資源分配問題 某個(gè)中型百貨商場對售貨人員 周工資200元 的需求經(jīng)統(tǒng)計(jì)如下表為了保證銷售人員充分休息 銷售人員每周工作5天 休息2天 問應(yīng)如何安排銷售人員的工作時(shí)間 使得所配售貨人員的總費(fèi)用最小 模型假設(shè) 每天工作8小時(shí) 不考慮夜班的情況 每個(gè)人的休息時(shí)間為連續(xù)的兩天時(shí)間 每天安排的人員數(shù)不得低于需求量 但可以超過需求量 問題分析 因素 不可變因素 需求量 休息時(shí)間 單位費(fèi)用 可變因素 安排的人數(shù) 每人工作的時(shí)間 總費(fèi)用 方案 確定每天工作的人數(shù) 由于連續(xù)休息2天 當(dāng)確定每個(gè)人開始休息的時(shí)間就等于知道工作的時(shí)間 因而確定每天開始休息的人數(shù)就知道每天開始工作的人數(shù) 從而求出每天工作的人數(shù) 變量 每天開始休息的人數(shù)約束條件 1 每人休息時(shí)間2天 自然滿足 2 每天工作人數(shù)不低于需求量 第i天工作的人數(shù)就是從第i 2天往前數(shù)5天內(nèi)開始工作的人數(shù) 所以有約束 3 變量非負(fù)約束 目標(biāo)函數(shù) 總費(fèi)用最小 總費(fèi)用與使用的總?cè)藬?shù)成正比 由于每個(gè)人必然在且僅在某一天開始休息 所以總?cè)藬?shù)等于 模型 計(jì)算 注解 該問題本質(zhì)上是個(gè)整數(shù)規(guī)劃問題 放松的線性規(guī)劃的最優(yōu)解是個(gè)整數(shù)解 所以兩規(guī)劃等價(jià) 定義整數(shù)變量用函數(shù) gin x1 gin x7 0 1整數(shù)變量為 bin x1 配料問題 某化工廠要用三中原料混合配置三種不同規(guī)格的產(chǎn)品各產(chǎn)品的規(guī)格單價(jià)如表1 問如何安排生產(chǎn)使得生產(chǎn)利潤最大 原料的單價(jià)與每天最大供應(yīng)量如表2 配料問題案例 問題問題分