scau數(shù)學(xué)建模課件(優(yōu)化模型-線性規(guī)劃)

規(guī)劃模型（1）效益最大化或費(fèi)用最小化（2）各種條件約束1、有關(guān)線性規(guī)劃問題的介紹：幾個(gè)例子2、線性規(guī)劃問題的標(biāo)準(zhǔn)形式3、關(guān)于整數(shù)規(guī)劃3、應(yīng)用一、線性規(guī)劃問題——例1某化工廠生產(chǎn)A1，A2，A3，A4四種化工產(chǎn)品，每種產(chǎn)品生產(chǎn)1噸消耗的工時(shí)、能源和獲得的利潤(rùn)如下表：產(chǎn)品A1A2A3A4工時(shí)/h10025038075能源/噸標(biāo)準(zhǔn)煤0.20.30.50.1利潤(rùn)/萬元2581

已知該廠明年的工時(shí)限額為18480h，能耗限額為100t標(biāo)準(zhǔn)煤，欲使該廠明年的總利潤(rùn)最高，請(qǐng)確定各種產(chǎn)品的生產(chǎn)數(shù)量。模型產(chǎn)品A1A2A3A4生產(chǎn)數(shù)量x1x2x3x4假設(shè)：工時(shí)限制供煤限制一、線性規(guī)劃問題——例2

一飼養(yǎng)場(chǎng)飼養(yǎng)供實(shí)驗(yàn)用的動(dòng)物，已知?jiǎng)游锷L(zhǎng)對(duì)蛋白質(zhì)、礦物質(zhì)和維生素特別敏感，每個(gè)動(dòng)物每天至少需蛋白質(zhì)70g、礦物質(zhì)3g和維生素10mg，該廠能得到五種飼料A1、A2、A3、A4和A5，每種飼料10kg的成本分別為2、7、4、3、5。每一千克飼料所含營(yíng)養(yǎng)成分如下表：飼料A1A2A3A4A5蛋白質(zhì)（g）0.3210.61.8礦物質(zhì)（g）0.10.050.020.20.05維生素（mg）0.050.10.020.20.08

希望建立數(shù)學(xué)模型，既能滿足動(dòng)物需要，又使總成本最低的飼料配方模型飼料A1A2A3A4A5符號(hào)x1x2x3x4x5二、線性規(guī)劃問題的標(biāo)準(zhǔn)形式{maxy=cTxs.t.Ax=bx≥0求解方法：（1）單純形法（2）軟件求解:Lindo，matlab，sas三、整數(shù)規(guī)劃

一個(gè)公司有22億元資金用來投資，現(xiàn)有6個(gè)項(xiàng)目可供選擇，各項(xiàng)目所需投資金額和預(yù)計(jì)年收益如下表所示：項(xiàng)目123456投資526468收益0.50.40.60.50.91應(yīng)選擇哪幾個(gè)項(xiàng)目投資收益最大？求解方法：分枝定界法四、分派問題——0-1規(guī)劃問題：五、網(wǎng)絡(luò)問題問題：右圖是一公路交通圖，弧上數(shù)字為路程，求汽車從（1）到（7）最短路。符號(hào)假設(shè)：模型：?jiǎn)栴}變形——最大流問題問題變形——最小費(fèi)用流問題上圖六、問題應(yīng)用——鋼管下料問題：某鋼管零售商從鋼管廠進(jìn)貨，將鋼管按顧客的要求切割后售出，從鋼管廠進(jìn)貨時(shí)得到的原料鋼管都是19m。（1）現(xiàn)有一客戶需要50根4m、20根6m和15根8m

的鋼管，應(yīng)如何下料最省。（2）零售商如果采用的不同切割模式太多，將會(huì)導(dǎo)致生產(chǎn)過程的復(fù)雜化，從而增加生產(chǎn)和管理成本，所以該零售商規(guī)定采用的不同切割模式不能超過3種。此外，該客戶除需要（1）中的三種鋼管外，還需要10根5m的鋼管，應(yīng)如何下料最省。問題（1）解答鋼管下料合理切割模式：4m鋼管數(shù)6m鋼管數(shù)8m鋼管數(shù)余料（m）模式14003模式23101模式32013模式41203模式51111模式60301模式70023問題：按何種切割模式，切割多少根原鋼管，最為節(jié)省。節(jié)?。?）余料最少2）原鋼管總數(shù)最少雙目標(biāo)模型設(shè)xi表示照第i種模式切割原材料鋼管的根數(shù)總余料最小原鋼管條數(shù)最少問題（2）解答問題分析：一合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小尺寸，故本題中合理的切割模式的余量不能大于3m。故可選擇總根數(shù)最少為目標(biāo)進(jìn)行求解。模型建立設(shè)xi表示照第i種模式切割原材料鋼管的根數(shù)（i=1,2,3）r

ij分別表示第i種切割模式下生產(chǎn)j米（j=4,5,6,8）鋼管數(shù)七、幾個(gè)應(yīng)用（AMCM-88B）

將七種不同規(guī)格的包裝箱裝到兩輛鐵路平板車上，各包裝箱寬、高均相等，但厚度t(厘米)與重量w(公斤)不同。每平板車有10.2米長(zhǎng)的地方用來裝包裝箱，載重40噸。由于貨運(yùn)限制，對(duì)c5、c6、c7類包裝箱總數(shù)有限定：總厚度不超過302.7(厘米)。試把箱子裝到平板車并使空間浪費(fèi)最小。c1c2c3c4c5c6c7T45.75162.57149.25260W200030001000500400020001000件數(shù)8796648八、應(yīng)用（AMCM-89B）

機(jī)場(chǎng)通常按“先來先走”的原則來分配飛機(jī)跑道，即當(dāng)飛機(jī)準(zhǔn)備好離開登機(jī)口時(shí)，駕駛員電告地面控制中心，加入等候跑道的隊(duì)伍。假設(shè)控制中心可以從快速聯(lián)機(jī)數(shù)據(jù)庫(kù)中得到每架飛機(jī)如下信息：1、預(yù)定離開登機(jī)口的時(shí)間2、實(shí)際離開登機(jī)口的時(shí)間3、機(jī)上乘客人數(shù)4、預(yù)定在下一站轉(zhuǎn)機(jī)的人數(shù)和時(shí)間5、到達(dá)下一站的預(yù)定時(shí)間。又設(shè)飛機(jī)共有七種型號(hào)，載