優(yōu)化問題與規(guī)劃模型(更新版)
【正文】 3）求新的消防站的最佳位置。 原來的消防站在舊城中心。 其中每一格代表一平方英里 ， 格內(nèi)的數(shù)字為每年從此區(qū)域打來的緊急求救電話的數(shù)量 。 優(yōu)化問題與規(guī)劃模型 優(yōu)化問題 ：與最大、最小、最長、最短等等有關(guān)的問題。 命題 1 線性規(guī)劃問題的可行解集是凸集 可行解集：線性不等式組的解 +=4 15x1+10x2=450 命題 2 線性規(guī)劃問題的目標(biāo)函數(shù) (關(guān)于不同的目標(biāo)值是一族平行直線 , 目標(biāo)值的大小描述了直線離原點(diǎn)的遠(yuǎn)近 命題 3 線性規(guī)劃問題的最優(yōu)解一定在可行解集的某個(gè) 極點(diǎn) 上達(dá)到 (穿過可行域的目標(biāo)直線組中最遠(yuǎn)離(或接近 )原點(diǎn)的直線所穿過的凸多邊形的 頂點(diǎn) ). 單純形法 : 通過確定約束方程組的基本解 , 并計(jì)算相應(yīng)目標(biāo)函數(shù)值 , 在可行解集的極點(diǎn)中搜尋最優(yōu)解 . 1. 模型的標(biāo)準(zhǔn)化 正則模型 : 決策變量 : x1,x2,… ,xn. 目標(biāo)函數(shù) : Z=c1x1+c2x2+… +xn. 約束條件 : a11x1+… +a1nxn≤b1, …… am1x1+… +amnxn≤bm, 模型的標(biāo)準(zhǔn)化 10. 引入松弛變量將不等式約束變?yōu)榈仁郊s束 若有 ai1x1+… +ainxn≤bi, 則引入 xn+i≥ 0, 使得 ai1x1+… +ainxn+ xn+i =bi 若有 aj1x1+… +ajnxn≥bj, 則引入 xn+j≥ 0, 使得 aj1x1+… +ajnxn xn+j =bj. 且有 Z=c1x1+c2x2+… +xn+0xn+1+… +0xn+m. 20. 將目標(biāo)函數(shù)的優(yōu)化變?yōu)槟繕?biāo)函數(shù)的極大化 . 若求 min Z, 令 Z’=–Z, 則問題變?yōu)? max Z’ . 30. 引入人工變量 ,使得所有變量均為非負(fù) . 若 xi 沒有非負(fù)的條件 , 則引入 xi’≥ 0 和 xi’’≥0, 令 xi= xi’– xi’’, 則可使得問題的全部變量均非負(fù) . 標(biāo)準(zhǔn)化模型 求變量 x1, x2,… , xn, max Z = c1x1+… + xn, s. t. a11x1+… + a1nxn= b1, …… am1x1+… + amnxn= bm, x1 ≥ 0,… , xn ≥ 0, ??????0..m a x,xbxAtsxcZxT??????求 定義 : 若代數(shù)方程 AX=B的解向量有 nm個(gè)分量為零 , 其余 m個(gè)分量對(duì)應(yīng) A的 m個(gè)線性無關(guān)列 , 則稱該解向量為方程組的一個(gè) 基本解 . 在一個(gè)線性規(guī)劃問題中 , 如果一個(gè)可行解也是約束方程組的基本解 , 則稱之為 基本可行解 命題 4 一個(gè)向量 x 是線性規(guī)劃問題可行解集的一個(gè) 極點(diǎn) , 當(dāng)且僅當(dāng)它是約束方程的一個(gè) 基本可行解 . 一般線性規(guī)劃的數(shù)學(xué)模型及解法： min f=cTx . Ax ? b A1x=b1 LB ? x ? UB Matlab求解程序 [x,f]=linprog(c,A,b,A1,b1,LB,UB) 模型 II . 在不降低當(dāng)前生產(chǎn)水平的前提下評(píng)估資源的貢獻(xiàn)，使“成本”投入最低。 2*x1+3*x2+3*x3+4*x4=6。這是一個(gè)整數(shù)規(guī)劃問題）。 蛙泳 蝶泳 自由泳 仰泳 甲 99 60 59 73 乙 79 65 93 87 丙 67 93 63 81 丁 56 79 86 76
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1