-線性規(guī)劃建模舉例

1、1-7線性規(guī)劃建模舉例 導(dǎo)讀：就愛閱讀網(wǎng)友為您分享以下“1-7線性規(guī)劃建模舉例”資訊，希望對(duì)您有所幫助，感謝您對(duì)的支持!線性規(guī)劃應(yīng)用舉例線性規(guī)劃模型舉例繼續(xù)返回一、使用線性規(guī)劃方法處理實(shí)際問題 必須具備的條件(建模條件) 必須具備的條件(建模條件)：1) 優(yōu)化條件-問題的目標(biāo)有極大化或極 優(yōu)化條件 問題的目標(biāo)有極大化或極小化的要求, 小化的要求,而且能用決策變量的線性 函數(shù)來表示。 函數(shù)來表示。2) 選擇條件 有多種可供選擇的可行方 選擇條件-有多種可供選擇的可行方案，以便從中選取最優(yōu)方案。 以便從中選取最優(yōu)方案。上頁 下頁 返回3）限制條件-達(dá)到目標(biāo)的條件是有一定限 ）限制條件 達(dá)到目標(biāo)的條

2、件是有一定限 制的（比如， 資源的供應(yīng)量有限度等）， 制的 （ 比如 ， 資源的供應(yīng)量有限度等） 而且這些限制可以用決策變量的線性等 式或線性不等式表示出來。 式或線性不等式表示出來。 此外， 描述問題的決策變量相互之 此外 ， 間應(yīng)有一定的聯(lián)系， 間應(yīng)有一定的聯(lián)系 ， 有可能建立數(shù)學(xué)關(guān) 即這些變量之間是內(nèi)部相關(guān) 變量之間是內(nèi)部相關(guān)的 系，即這些變量之間是內(nèi)部相關(guān)的。上頁 下頁 返回二、建模步驟： 建模步驟：第一步：設(shè)置要求解的決策變量。決策變量 第一步：設(shè)置要求解的決策變量。 選取得當(dāng)， 選取得當(dāng)，不僅能順利地建立模型而且能方便 地求解，否則很可能事倍功半。 地求解，否則很可能事倍功半。 第

3、二步：找出所有的限制，即約束條件， 第二步：找出所有的限制，即約束條件，并 用決策變量的線性方程或線性不等式來表示。 用決策變量的線性方程或線性不等式來表示。 當(dāng)限制條件多，背景比較復(fù)雜時(shí)，可以采用圖 當(dāng)限制條件多，背景比較復(fù)雜時(shí)，可以采用圖 示或表格形式列出所有的已知數(shù)據(jù)和信息， 示或表格形式列出所有的已知數(shù)據(jù)和信息，以 避免“遺漏” 重復(fù)”所造成的錯(cuò)誤。 避免“遺漏”或“重復(fù)”所造成的錯(cuò)誤。上頁 下頁 返回第三步：明確目標(biāo)要求，并用決策變量 第三步：明確目標(biāo)要求， 的線性函數(shù)來表示， 的線性函數(shù)來表示 ， 確定對(duì)函數(shù)是取極大 還是取極小的要求。 還是取極小的要求。 決策變量的非負(fù)要求可以根

4、據(jù)問題的 實(shí)際意義加以確定。 實(shí)際意義加以確定。上頁下頁返回線性規(guī)劃模型舉例(一)運(yùn)輸問題 (二)布局問題 (三)分派問題 (四)生產(chǎn)計(jì)劃問題 (五)合理下料問題上頁下頁返回(一) 運(yùn)輸問題設(shè)某種物資有m個(gè)產(chǎn)地， 設(shè)某種物資有m個(gè)產(chǎn)地，A1，A2，Am；聯(lián) ， 合供應(yīng)n個(gè)銷地： 合供應(yīng)n個(gè)銷地：B1，B2，Bn。 ， 各產(chǎn)地產(chǎn)量（單位： ），各銷地銷量 各銷地銷量（ 各產(chǎn)地產(chǎn)量（單位：噸），各銷地銷量（單 ），各產(chǎn)地至各銷地單位運(yùn)價(jià) 單位： 各產(chǎn)地至各銷地單位運(yùn)價(jià)（ 位：噸），各產(chǎn)地至各銷地單位運(yùn)價(jià)（單位：元 如下表所示。 噸）如下表所示。應(yīng)如何調(diào)運(yùn)， 應(yīng)如何調(diào)運(yùn)， 才使總運(yùn)費(fèi)最 少？上頁下頁

5、返回產(chǎn) 地銷 地B1 C11 C21 Cm1 b1B2 C12 C22 Cm2 b2 Bn C1n C2n Cmn bn產(chǎn)量（ 產(chǎn)量（噸） a1 a2 amA1 A2 Am 銷量（ 銷量（噸）表中： 表示產(chǎn)地A 的產(chǎn)量(i=1， m)； 表中：ai表示產(chǎn)地Ai的產(chǎn)量(i=1，2， ，m)； bj表示銷地Bj的銷量(j=1，2， ，n)； 表示銷地B 的銷量(j=1， n)； cij表示AiBj間的單位運(yùn)價(jià)（元噸）(i=1，2， ，m; 表示A 間的單位運(yùn)價(jià)（ (i=1， j=1， j=1，2， ，n)； n)；上頁 下頁 返回(一) 運(yùn)輸問題()產(chǎn)銷平衡 ()產(chǎn)銷平衡即()產(chǎn)銷平衡 ()產(chǎn)銷平

6、衡 ()產(chǎn)銷不平衡 ()產(chǎn)銷不平衡na i= 1mi= j bj= 1設(shè)xij表示由產(chǎn)地Ai運(yùn)往銷地Bj的物資 表示由產(chǎn)地A 運(yùn)往銷地B ,n)。 數(shù)(i=1,2, ,m;j=1,2, ,n)。 那么，上述運(yùn)輸問題的數(shù)學(xué)模型為： 那么，上述運(yùn)輸問題的數(shù)學(xué)模型為： 求一組變量x 求一組變量xij(i=1,2, ,m;j=1,2, ,n) 的值, 的值, 使它滿足上頁 下頁 返回()產(chǎn)銷平衡的模型 ()產(chǎn)銷平衡的模型產(chǎn)地A 產(chǎn)地Ai發(fā)到各銷地的發(fā)量 總和應(yīng)等于ai的產(chǎn)量 總和應(yīng)等于a 約束條件 各產(chǎn)地發(fā)到銷地B 各產(chǎn)地發(fā)到銷地Bj的發(fā)量 發(fā)到銷地 總和應(yīng)等于b 總和應(yīng)等于bj的銷量 調(diào)運(yùn)量不能為負(fù)

7、數(shù) 調(diào)運(yùn)量不能為負(fù)數(shù)0 量不能為負(fù)數(shù)上頁下頁返回()產(chǎn)銷平衡的模型 ()產(chǎn)銷平衡的模型產(chǎn)地A 產(chǎn)地Ai發(fā)到各銷地的發(fā)量 總和應(yīng)等于A 總和應(yīng)等于Ai的產(chǎn)量ij ix = aj= 1 mn約束條件x = bij各產(chǎn)地發(fā)到銷地B 各產(chǎn)地發(fā)到銷地Bj的發(fā)量 發(fā)到銷地 總和應(yīng)等于B 總和應(yīng)等于Bj的銷量(i =1,2,L m) ,xij 0 (i =12,L m j =1L n) , , ; , ,調(diào)運(yùn)量不能為負(fù)數(shù) 調(diào)運(yùn)量不能為負(fù)數(shù)0 量不能為負(fù)數(shù)上頁 下頁 返回i= 1j( j =1,2,L n) ,()產(chǎn)銷平衡的模型 ()產(chǎn)銷平衡的模型n m目 函 mn s = ijxij 的 最 標(biāo) 數(shù) i c

8、 值 小x = aij inj= 1 m(i =1,2,L m) , ( j =1,2,L n) ,1 1 j= i=約束條件x = bijxij 0 (i =12,L m j =1L n) , , ; , ,上頁 下頁 返回i= 1j(一) 運(yùn)輸問題()產(chǎn)銷不平衡 產(chǎn)大于銷 ()產(chǎn)銷不平衡產(chǎn)大于銷 產(chǎn)銷不平衡m n 即 a j i j=1 b i= 1 這一問題的數(shù)學(xué)模型應(yīng)為： 求一組變量xij(i =12 L m j =12 L n) , , , ; , , , 的值,使它滿足上頁下頁返回()產(chǎn)銷不平衡 ()產(chǎn)銷不平衡產(chǎn)大于銷的模型 產(chǎn)銷不平衡產(chǎn)地A 產(chǎn)地Ai發(fā)到各銷地的發(fā)量 目 函 標(biāo)

9、數(shù) mn s = i cijxij 總和不超過A 總和不超過Ai的產(chǎn)量 j= i= 1 1 產(chǎn)小于 n xij 銷的模各產(chǎn)地發(fā)到銷地m的發(fā)量 ai 各產(chǎn)地=12,L Bj i 發(fā)到銷地B , , 發(fā)到銷地 型呢 j= 1 總和應(yīng)等于B 總和應(yīng)等于Bi的銷量 m 約束條件nmi= 1？j()x = bij( j =1,2,L n) ,xij 0(i =1,2,L m; j =1,2,L n) , ,上頁 下頁 返回調(diào)運(yùn)量不能為負(fù)數(shù) 調(diào)運(yùn)量不能為負(fù)數(shù)（二）布局問題 作物布局在n塊地上種植m種作物，已知各塊土地 畝數(shù)、各種作物計(jì)劃播種面積及各種作 物在各塊的單產(chǎn)（每畝的產(chǎn)量）如表 （與運(yùn)輸問題相似）

10、，問：如何合理安排種植計(jì)劃，才使總 產(chǎn)量最多。上頁 下頁 返回（二）布局問題產(chǎn) 地 銷 地n塊土地B1 B2 Bn C1n C2n Cmn bn C11 C12 方法與運(yùn)輸 C問題類似 C22 21 Cm1 b1 Cm2 b2 產(chǎn)量（ 產(chǎn)量（噸） a1 a2 am種 農(nóng) 作 物m mA1 A2 Am銷量（ 銷量（噸）上頁下頁返回(三）生產(chǎn)組織與計(jì)劃問題總的加工成本最低上頁下頁返回(三）生產(chǎn)組織與計(jì)劃問題1 2 , m 某工廠用機(jī)床 A, A ,L A 加工 B1, B2,L Bn種零件。在一個(gè)生產(chǎn)周期， , 種零件。在一個(gè)生產(chǎn)周期， 各機(jī)床只能工作的機(jī)時(shí)、 各機(jī)床只能工作的機(jī)時(shí)、工廠必須完成各

11、 零件加工數(shù)、 零件加工數(shù)、各機(jī)床加工每個(gè)零件的時(shí)間 單位：機(jī)時(shí) （單位：機(jī)時(shí)個(gè)）和加工每個(gè)零件的成 單位： 如表1及表2 本（單位：元個(gè)）如表1及表2所示。 在這個(gè)生產(chǎn)周期， 問：在這個(gè)生產(chǎn)周期，怎樣安排各機(jī)床的 生產(chǎn)任務(wù)，才能既完成加工任務(wù)， 生產(chǎn)任務(wù)，才能既完成加工任務(wù)，又使總 的加工成本最低。 的加工成本最低。上頁下頁返回(三）生產(chǎn)組織與計(jì)劃問題機(jī) 床零 件B1 C11 C21 Cm1 b1B2 C12 C22 Cm2 b2 Bn C1n C2n Cmn bn在一周期能 工作機(jī)時(shí) a1 a2 amA1 A2 Am 必須加工零件數(shù)表1 ：加工每個(gè)零件的時(shí)間上頁 下頁 返回(三）生產(chǎn)組織與

12、計(jì)劃問題零 機(jī) 床 件B1 d11 d21 dm1B2 d12 d22 dm2 Bn d1n d2n dmnA1 A2 Am表 2：加工每個(gè)零件的成本 ：上頁 下頁 返回(三）生產(chǎn)組織與計(jì)劃問題解：設(shè)xij 為機(jī)床 A 在下一生產(chǎn)周期加工 零件B 的個(gè)數(shù) (i =12,L m j =12,L n) 。 , , ; , ,ij這一問題的數(shù)學(xué)模型為： 這一問題的數(shù)學(xué)模型為： 求一組變量 xij(i =12,L m j =12,L n) , , ; , , 的值, 的值,使它滿足目 函 s = ijxij 的 最 標(biāo) 數(shù) d 值 小j= i= 1 1nm上頁下頁返回(三）生產(chǎn)組織與計(jì)劃問題總的加工成

13、本最低的模型c x aij ij in1 j=(i =1,2,L m) , ( j =1,2,L n) ,B的總數(shù)不能少于 j(機(jī)床 A加工各零件總機(jī)時(shí)不 機(jī)床 i 能超過 A能工作機(jī)時(shí)） i能工作機(jī)時(shí)）ij約束條件x b1 i=mjxij 0 , 整 (i =12,L m j =12,L n) 數(shù) , , , , ,(加工零件個(gè)數(shù)不能為負(fù)數(shù)、分?jǐn)?shù)） 加工零件個(gè)數(shù)不能為負(fù)數(shù)、分?jǐn)?shù)） 加工零件個(gè)數(shù)不能為負(fù)數(shù)上頁 下頁 返回(各機(jī)床加工零件 各機(jī)床加工零件 B 需要數(shù)） j 需要數(shù)）(三）生產(chǎn)組織與計(jì)劃問題總的加工成本最低的模型目標(biāo)函數(shù)mn s = d xij i ijj= i= 1 1nmc x

14、 aij ij inj= 1 n(i =1,2,L m) , ( j =1,2,L n) ,約束條件x bij ixij 0 , 整 (i =12,L m j =12,L n) 數(shù) , , , , ,上頁 下頁 返回i= 1(四)合理下料問題設(shè)用某原材料(條材或板材) 設(shè)用某原材料(條材或板材)下零件 A, A ,L A 的毛坯.根據(jù)過去經(jīng)驗(yàn) 1 2 , m 的毛坯. 在一件原材料上有 B, B2,L B 種不同 1 , n 的下料方式,每種下料方式可得各種毛 的下料方式, 坯個(gè)數(shù)及每種零件需要量如下表所示。 坯個(gè)數(shù)及每種零件需要量如下表所示。問：應(yīng)怎樣安排下料方式，使得既 應(yīng)怎樣安排下料方式

15、， 能滿足需要，用的原材料又最少。 能滿足需要，用的原材料又最少。上頁下頁返回(四)合理下料問題下 料 方 式零件B1 C11 C21 Cm1 B2 C12 C22 Cm2 Bn C1n C2n Cmn零件 名稱需要量a1 a2 amA1 A2 Am上頁下頁返回解決這類問題一般有兩個(gè)步驟： 解決這類問題一般有兩個(gè)步驟：步驟一、按照一定的思路設(shè)法列出所有的排料 步驟一、按照一定的思路設(shè)法列出所有的排料 方案（也稱下料方案或排料圖） 當(dāng)方案很多， 方案（也稱下料方案或排料圖），當(dāng)方案很多， 甚至無法一一列出時(shí)，通常應(yīng)先確定一些篩選 甚至無法一一列出時(shí)，通常應(yīng)先確定一些篩選 原則，把明顯不合理的方案

16、刪除， 原則，把明顯不合理的方案刪除，僅僅考慮剩 余的為數(shù)不太多的方案； 余的為數(shù)不太多的方案； 步驟二、 表示按第 步驟二、設(shè)xi表示按第種方案下料的棒料根 數(shù) （ 或板材塊數(shù)） i=1,2,n， 按照問題的要 或板材塊數(shù) ） ， 求建立LP模型 模型。 求建立 模型上頁 下頁 返回某廠接受了一批加工定貨， 例1-9 某廠接受了一批加工定貨， 客戶要求加工100套鋼架 ， 每套由長 套鋼架， 客戶要求加工 套鋼架 2.9米 、 2.1米和 米的圓鋼各一根組 米和1.5米的圓鋼各一根組 米 米和 現(xiàn)在僅有一批長7.4米的棒料毛坯 米的棒料毛坯， 成?，F(xiàn)在僅有一批長 米的棒料毛坯， 問應(yīng)如何下料

17、， 問應(yīng)如何下料 ， 使所用的棒料根數(shù)最 少？上頁下頁返回最簡單的處理方法： 最簡單的處理方法：從一根棒料上截 米和1.5米的棒料各一根 取2.9米、2.1米和 米的棒料各一根， 米 米和 米的棒料各一根， 正好配成一套鋼架， 套鋼架總共需要 正好配成一套鋼架，100套鋼架總共需要 100根棒料毛坯。每根棒料毛坯剩下 根棒料毛坯。 根棒料毛坯 每根棒料毛坯剩下0.9 米的料頭,100根毛坯總共剩 米料頭。 根毛坯總共剩90米料頭 米的料頭 根毛坯總共剩 米料頭。 這是最好的辦法嗎？ 這是最好的辦法嗎？ 這是最好的辦法嗎 合理套裁肯定會(huì)有更好的效果。 合理套裁肯定會(huì)有更好的效果。 肯定會(huì)有更好的

18、效果 先設(shè)法列出所有的下料方案，思路如圖。 先設(shè)法列出所有的下料方案，思路如圖。上頁 下頁 返回排列下料方案思路圖原 料 （ 7 .4 米 長 棒 料 ） 1 .截 規(guī) 格 1 (2 .9 米 ) 2 .截 規(guī) 格 2 (2 .1 米 ) 截 規(guī) 格 3 (1 .5 米 )最 多 截 取 根 數(shù) n1=2 5 .8 余 料 1 .6 n1=1 用 料 2 .9 余 料 4 .5最 多 截 取 根 數(shù) n2= 3 用 料 6 .3 余 料 1 .1 n2=2 用 料 4 .2 余 料 3 .2 n2=1 用 料 2 .1 余 料 5 .3最多截取 根 數(shù) n3=4 用 料 6 .0 余 料 1

19、.4余 料 N 夠 截 規(guī) 格 2 嗎 ? ( 2 .1 米 ) Y N余 料 夠 截 規(guī) 格 3 嗎 ? (1 .5 米 ) Yn2=2 用 料 4 .2 余 料 0 .3n2=1 用 料 2 .1 余 料 2 .4n2=0 余 料 4 .5n3=2 用 料 3 .0 余 料 0 .2n3=3 用 料 4 .5 余 料 0 .8余 料 N 夠 截 規(guī) 格 3 嗎 ? (1 .5 米 ) Yn3=1 用 料 1 .5 余 料 0 .1 方 案 I 截 201 余 料 0 .1n3=0 用 料 0 余 料 0 .3 方 案 II (1 2 0 ) 余 料 0 .3n3=1 用 料 1 .5 余 料 0 .9 方 案 (111 ) 余 料 0 .9n3=3 用 料 4 .5 余 料 0 方 案 (1 0 3 ) 余 料 0 方 案 (0 3 0 ) 余 料 1.1 方 案 (0 2 2 ) 余 料 0 .2 方 案 (0 1 3 ) 余 料 0.8 方 案 (0 0 4 )上頁下頁余 料 1 .4返回設(shè)xi為按第i種方案下料的棒料根數(shù)， 為按第i種方案下料的棒料根數(shù)， 建立LP模型如下 模型如下： 建立 模型如下：MinZ = xii =1 82x1 + 1x2 + 1x3 + 1x4 + 0x5