決策學(xué)基礎(chǔ)課件(編輯修改稿)
2025-02-11 02:34 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 （ 3）求初始解（即找出一個(gè)方案）； （ 4）畫出單純形表，應(yīng)用矩陣初等行變換知識(shí)，進(jìn)行表上運(yùn)算； （ 5）確定變換的“列”和“行”（在“檢驗(yàn)行”定列，利用“商最小原理”定行），“列”和“行”交叉的元素變?yōu)椤?1”，該“列”其余元素變?yōu)椤?0”； （ 6）重復(fù)（ 4） ~（ 5），若“檢驗(yàn)行”所有元素均 = 0 時(shí)，線性規(guī)劃的最優(yōu)化解找到。 幾種特殊情況的說明 ： * 無(wú)可行解：線性規(guī)劃的最優(yōu)解里，人工變量 0，該線性規(guī)劃無(wú)可行解。 * 無(wú)界解：在單純形表的某次迭代中，如果存在著一個(gè)大于零的檢驗(yàn)數(shù)，并且該列的系數(shù)向量的每一個(gè)于是都是小于或等于零，此線性規(guī)劃問題是無(wú)界的。此類問題由建模的錯(cuò)誤引起。 * 無(wú)窮多最優(yōu)解：對(duì)于某最優(yōu)的基本可行解，如存在某個(gè)非基變量的檢驗(yàn)數(shù)為零，有無(wú)窮多最優(yōu)解。 仍然用上述實(shí)例說明：（ 1）（省略）； （ 2）設(shè) :材料剩余 s1公斤，工時(shí)剩余 s2工時(shí)，外協(xié)件剩余 s3個(gè)。我們可以得到： Max Z = 60 X1 + 30 X2 + 0s1 + 0s2 + 0s3 s . t . 2 X1 + 4 X2 + 1s1 + 0s2 + 0s3 = 320 3 X1 + 1 X2 + 0s1 + 1s2 + 0s3 = 180 2 X1 + 0 X2 + 0s1 + 0s2 + 1s3 = 100 X1 , X2 , s1, s2, s3 = 0 （ 3）求初始解：令 X1 = 0 , X2 = 0 , 可得， s1 = 320 , s2 = 180 , s3 = 100. 這就是一個(gè)方案，一個(gè)不安排生產(chǎn)的方案。 （ 4）畫出單純形表，如下： 價(jià)格 解 量 60 30 0 0 0 向量 向量 向量 X1 X2 s1 s2 s3 0 s1 320 2 4 1 0 0 0 s2 180 3 1 0 1 0 0 s3 100 2 0 0 0 1 檢驗(yàn) Z 0 60 30 0 0 0 X1 X2 s1 s2 s3 0 s1 220 0 4 1 0 1 0 s2 30 0 1 0 1 3/2 60 X1 50 1 0 0 0 189。 檢驗(yàn) Z 3000 0 30 0 0 30 0 s1 100 0 0 1 4 5 30 X2 30 0 1 0 1 3/2 60 X1 50 1 0 0 0 189。 檢驗(yàn) Z 3900 0 0 0 30 15 0 s3 20 0 0 1/5 4/5 1 30 X2 60 0 1 3/10 1/5 0 60 X1 40 1 0 1/10 2/5 0 檢驗(yàn) Z 4200 0 0 3 18 0 結(jié)論：根據(jù)計(jì)算可知： Z = 4200 , X1= 40 , X2 = 60 , S1 = 0 , S2 = 0 , S3 = 20. 即最優(yōu)生產(chǎn)方案是： 甲產(chǎn)品生產(chǎn) 40件； 乙產(chǎn)品生產(chǎn) 60件； 利潤(rùn)為 4200元。 此時(shí)，材料用完，工時(shí)用完，外協(xié)件剩余 20個(gè)。 說明：如果約束方程中，還有大于等于、等于的情況，將引進(jìn)人工變量并用“大 M法”求解。 二、運(yùn)輸問題 運(yùn)輸問題就是研究物資調(diào)運(yùn)中的供應(yīng)需求平衡時(shí)，如何使運(yùn)輸成本最低?？梢?，運(yùn)輸問題本質(zhì)上是線性規(guī)劃問題。 由于其約束方程全是等式，必須應(yīng)用“大M法”求解，而且計(jì)算量很大（指人工計(jì)算）。 為此，介紹一種“表上運(yùn)算方法”。 實(shí)例：某公司有三個(gè)生產(chǎn)面包的工廠A1 , A2 , A3；有四個(gè)銷售門市部 B1 , B2 , B3 , B4 ，資料如下： B1 B2 B3 B4 產(chǎn)量 A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 銷量 3 6 5 6 20 （噸 /天） 說明： 橙色數(shù)字 表示產(chǎn)銷量（噸 /天）； 綠色數(shù)字 表示運(yùn)輸費(fèi)用（百元 /噸） 問題：食品公司應(yīng)該如何調(diào)運(yùn)，可以使其運(yùn)輸費(fèi)用最低？ （ 1）運(yùn)輸問題解題步驟（表上作業(yè)法）： ?按規(guī)定格式畫出調(diào)運(yùn)表格； ?按“最小元素法”求出“初始調(diào)運(yùn)方案”； ?用“閉回路法”檢驗(yàn)方案是否最優(yōu)； ?若不是最優(yōu)，則沿“閉回路”方向進(jìn)行調(diào)整； ?重復(fù) 4步； ?直到所有“閉回路”所形成的運(yùn)價(jià)的代數(shù)和都大于或等于零為止，此時(shí)最優(yōu)解確定。 （ 2）最小元素法：在運(yùn)輸價(jià)格中找出最小的，從此方格對(duì)應(yīng)的產(chǎn)、銷數(shù)量中選擇小的數(shù)填入，為 0 的行（列）者，該行（列）劃掉。若行（列）同時(shí)為 0 ，只能劃掉其一。 （ 3）閉回路法：從任何一個(gè)空格出發(fā)，見到有運(yùn)量的方格，才能轉(zhuǎn)向 90。 ，直到能轉(zhuǎn)回出發(fā)的空格，形成閉回路。最優(yōu)化檢驗(yàn)是將閉回路中奇數(shù)轉(zhuǎn)彎處的運(yùn)輸價(jià)格看成負(fù)數(shù)，偶數(shù)轉(zhuǎn)彎處的運(yùn)輸價(jià)格看成正數(shù)，沿閉回路求其代數(shù)和。代數(shù)和 0 的，不調(diào)整；代數(shù)和 = 0 的有多個(gè)最優(yōu)解，可不調(diào)整；代數(shù)和 0 的，要調(diào)整。調(diào)整方法是，將奇數(shù)轉(zhuǎn)彎處的運(yùn)輸量進(jìn)行 比較，選擇 最小的運(yùn)輸量 作為調(diào)整依據(jù)，沿著閉回路，將奇數(shù)轉(zhuǎn)彎處的運(yùn)輸量 減去 這個(gè)最小的運(yùn)輸量 ；偶數(shù)轉(zhuǎn)彎處的運(yùn)輸量 加上 這個(gè) 最小的運(yùn)輸量 ，直到完成所有轉(zhuǎn)彎處的運(yùn)算。（上述運(yùn)算過程，可以簡(jiǎn)約成：逢“雙”加，逢“單”減。） （ 4）注意： *運(yùn)輸問題必須產(chǎn)銷平衡； *填有運(yùn)輸量的方格數(shù)量，必須滿足 m+n1,以保證實(shí)現(xiàn)閉回路。若小于，填 0 占位。 B1 B2 B3 B4 產(chǎn)量 A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 銷量 3 6 5 6 20 （噸 /天） 3 0 1 1 0 4 4 0 3 6 0 3 3 0 3 0 0 3 這個(gè)就是初始調(diào)運(yùn)方案，運(yùn)輸費(fèi)用 =86百元 =8600元。此方案是否最優(yōu)化？？ 進(jìn)行最優(yōu)化檢驗(yàn)： B1 B2 B3 B4 產(chǎn)量 A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 銷量 3 6 5 6 20 （噸 /天） 4 3 3 1 6 3 ?A2B4— A1B4— A1B3— A2B3。 ?A1B1— A2B1— A2B3— A1B3: ?A3B1A3B4A1B4A1B3A2B3A2B1: ?A3B3— A3B4— A1B4— A1B3: ?A1B2— A3B2— A3B4— A1B4: ?A2B2A3B2A3B4A1B4A1B3A2B3: 閉回路法檢驗(yàn)表明：紅色線條所形成的“代數(shù)和”小于零，此回路上的運(yùn)輸量應(yīng)調(diào)整。其余不調(diào)整。調(diào)整結(jié)果如下表 :
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1