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

規(guī)劃模型（1）效益最大化或費用最小化（2）各種條件約束1、有關(guān)線性規(guī)劃問題的介紹：幾個例子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噸消耗的工時、能源和獲得的利潤如下表：產(chǎn)品A1A2A3A4工時/h10025038075能源/噸標(biāo)準(zhǔn)煤0.20.30.50.1利潤/萬元2581

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

一飼養(yǎng)場飼養(yǎng)供實驗用的動物，已知動物生長對蛋白質(zhì)、礦物質(zhì)和維生素特別敏感，每個動物每天至少需蛋白質(zhì)70g、礦物質(zhì)3g和維生素10mg，該廠能得到五種飼料A1、A2、A3、A4和A5，每種飼料10kg的成本分別為2、7、4、3、5。每一千克飼料所含營養(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é)模型，既能滿足動物需要，又使總成本最低的飼料配方模型飼料A1A2A3A4A5符號x1x2x3x4x5二、線性規(guī)劃問題的標(biāo)準(zhǔn)形式{maxy=cTxs.t.Ax=bx≥0求解方法：（1）單純形法（2）軟件求解:Lindo，matlab，sas三、整數(shù)規(guī)劃

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

的鋼管，應(yīng)如何下料最省。（2）零售商如果采用的不同切割模式太多，將會導(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é)省：1）余料最少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ù)七、幾個應(yīng)用（AMCM-88B）

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

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