[管理學(xué)]管理運(yùn)籌學(xué) 第一章_線性規(guī)劃-預(yù)覽頁
【正文】 的一門 應(yīng)用科學(xué) 。 3 整數(shù)規(guī)劃 167。有關(guān)數(shù)據(jù)如下表，現(xiàn)飼料可從市場(chǎng)上出售的 M、 N兩種飼料中選擇，試決定總花費(fèi)最小的購買方案。 = CX （ 2）約束條件 例如： 9 x1 +4x2≤360 9 x1 +4x2+ x3=360 松弛變量 ? ―≤‖型約束，加松弛變量； ? ―≥‖型約束，減松弛變量； 例、將如下問題化為標(biāo)準(zhǔn)型 ??????????????????????0,52327..32321321321321321xxxxxxxxxxxxtsxxxzM i n解 ：令 第二個(gè)約束減松弛變量 x6， 得標(biāo)準(zhǔn)型： )( 39。 7x1+12x2=84 7x1+12x2=168 如：令 7 x1 +12x2=84 7 x1 +12x2=168 9x1+4x2=360 4x1+5x2=200 3x1+10x2=300 x1 x2 40 20 60 80 100 20 40 60 80 100 0 X*=（ 20， 24）， Z*=428 最優(yōu)解： x1 = 0， x2 = 1 最優(yōu)目標(biāo)值 z = 6 課堂練習(xí) 圖解法求解線性規(guī)劃 ????????????????0,)3(22)2(22)1(432m i n2121212121xxxxxxxxstxxz0 1 2 3 4 1 2 3 4 x 1 x 2 O 1 2 (1) (2) (3) 2. LP 解的幾種情況 （ 1）唯一解 （ 2）多重最優(yōu)解 （ 3）無可行解 注：出現(xiàn)（ 3）、（ 4）情況時(shí)，建模有問題 （ 4）無有限最優(yōu)解 圖解法的結(jié)論： ● 線性規(guī)劃的可行域是凸集 ● 線性規(guī)劃的最優(yōu)解若存在，必在可行域的在極點(diǎn)獲得 ● 若在兩個(gè)極點(diǎn)同時(shí)獲得，則有無窮多最優(yōu)解 凸集 不是凸集 極點(diǎn) 167。 3 整數(shù)規(guī)劃 Integer Programming(簡(jiǎn)稱 IP) 一、 整數(shù)規(guī)劃的一般模型 LP: max z=CX AX=b X≥0 ??????????IP: max z=CX AX=b X≥0 X為整數(shù) 整數(shù)規(guī)劃的解法：分枝定界法或割平面法 基本思想是把一個(gè)整數(shù)規(guī)劃問題化為一系列的線性規(guī)劃問題來求解 整數(shù)規(guī)劃的分類： ? 純整數(shù)規(guī)劃：所有變量都限制為整數(shù) ? 混合整數(shù)規(guī)劃：僅部分變量限制為整數(shù) ? 01整數(shù)規(guī)劃：變量的取值僅限于 0或 1 [例 ] 人力資源分配的問題 某晝夜服務(wù)的公交線路每天各時(shí)間段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下： 設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段一開始時(shí)上班，并連續(xù)工作八小時(shí)，問該公交線路怎樣安排司機(jī)和乘務(wù)人員，既能滿足工作需要，又配備最少司機(jī)和乘務(wù)人員 ? 班次 時(shí)間 所需人數(shù) 1 6： 00 —— 10： 00 60 2 10： 00 —— 14： 00 70 3 14： 00 —— 18： 00 60 4 18： 00 —— 22： 00 50 5 22： 00 —— 2： 00 20 6 2： 00 —— 6： 00 30 解：設(shè) xi 表示第 i班次時(shí)開始上班的司機(jī)和乘務(wù)人員數(shù) ,于是 LP模型為 : x1 + x6 ≥ 60 x1 + x2 ≥ 70 x2 + x3 ≥ 60 x3 + x4 ≥ 50 x4 + x5 ≥ 20 x5 + x6 ≥ 30 x1,x2,x3,x4,x5,x6 ≥ 0 且為整數(shù) min z=x1 + x2 + x3 + x4 + x5 + x6 ?????班次 時(shí)間 所需人數(shù) 1 6 ： 00 —— 10 ： 00 60 2 10 ： 00 —— 14 ： 00 70 3 14 ： 00 —— 18 ： 00 60 4 18 ： 00 —— 22 ： 00 50 5 22 ： 00 —— 2 ： 00 20 6 2 ： 00 —— 6 ： 00 30 最優(yōu)解： X* =(60 ， 10， 50 ， 0 ， 30 ， 0）， Z*=150 二、 01整數(shù)規(guī)劃 ? 投資場(chǎng)所的選址問題 ? 指派問題 ? 背包問題 ? 消防隊(duì)問題 1. 投資場(chǎng)所的選址問題 某城市擬在東、西、南三區(qū)設(shè)立商業(yè)網(wǎng)點(diǎn)，備選位置有A1~A7共 7個(gè)，如果選 Ai，估計(jì)投資為 bi元，利潤(rùn)為 ci元，要求總投資不超過 B元，規(guī)定 東區(qū)： A A A3中至多選 2個(gè) 西區(qū)： A A5中至少選一個(gè) 南區(qū)： A A7中至少選一個(gè) 問如何設(shè)點(diǎn)使總利潤(rùn)最大？ 1， Ai被選中 0， Ai沒被選中 ?????解：令 xi= max z= ??71iiixcxi=0或 1， i=1, … ,7 ∑ bixi≤B i=1 7 x1+x2+x3≤2 x4+x5≥1 x6+x7≥1 ?????. 課堂練習(xí) 1: 某鉆井隊(duì)要從 S1~S10共 10個(gè)井位中確定五個(gè)鉆井探油，如果選 Si，估計(jì)鉆探費(fèi)用為 ci元，并且井位選擇上要滿足下列條件： （ 1） 或選擇 S1和 S7，或選擇 S8 。 要求： 每人只能完成一項(xiàng)任務(wù)，每項(xiàng)任務(wù)只能由一人完成。他最多能帶 115kg的物品，現(xiàn)有 5件物品，分別重 5 35 4 19kg，其價(jià)值依次為 3。已知備選校址代號(hào)及其能覆蓋的居民小區(qū)編號(hào)如表所示，問為覆蓋所有小區(qū)至少應(yīng)建多少所小學(xué)？ 備選校址代號(hào) 覆蓋的居民小區(qū)編號(hào) ABCDEF 7 5 5 5 6 6 167。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如右表。已知該廠各季度的生產(chǎn)能 力及生產(chǎn)每臺(tái)柴油機(jī)的成本如右表
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1