【正文】 數(shù)據(jù)、模型與決策 線(xiàn)性規(guī)劃 Linear Programming LP的數(shù)學(xué)模型 Mathematical Model of LP 圖解法 Graphical Method 標(biāo)準(zhǔn)型 Standard form of LP 基本概念 Basic Concepts 單純形法 Simplex Method 2/4/2023 數(shù)學(xué)模型 Mathematical Model 2/4/2023 制作與教學(xué) 線(xiàn)性規(guī)劃 Linear Programming Page 3 線(xiàn)性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 線(xiàn)性規(guī)劃通常研究資源的最優(yōu)利用、設(shè)備最佳運(yùn)行等問(wèn)題。例如，當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源 （如資金、設(shè)備、原標(biāo)材料、人工、時(shí)間等）去完成確定的任務(wù)或目標(biāo)；企業(yè)在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多 、利潤(rùn)最大）。 線(xiàn)性規(guī)劃 （ Linear Programming,縮寫(xiě)為 LP） 是運(yùn)籌學(xué)的重要分支之一，在實(shí)際中應(yīng)用得較廣泛，其方法也較成熟，借助計(jì)算機(jī)，使得計(jì)算更方便，應(yīng)用領(lǐng)域更廣泛和深入。 2/4/2023 制作與教學(xué) 線(xiàn)性規(guī)劃 Linear Programming Page 4 【 例 】 最優(yōu)生產(chǎn)計(jì)劃問(wèn)題 。 某企業(yè)在計(jì)劃期內(nèi)計(jì)劃生產(chǎn)甲 、乙 、 丙三種產(chǎn)品 。 這些產(chǎn)品分別需要要在設(shè)備 A、 B上加工 ， 需要消耗材料 C、 D， 按工藝資料規(guī)定 ， 單件產(chǎn)品在不同設(shè)備上加工及所需要的資源如表 。 已知在計(jì)劃期內(nèi)設(shè)備的加工能力各為 200臺(tái)時(shí) ， 可供材料分別為 360、 300公斤；每生產(chǎn)一件甲 、乙 、 丙三種產(chǎn)品 ， 企業(yè)可獲得利潤(rùn)分別為 50元 ， 假定市場(chǎng)需求無(wú)限制 。 企業(yè)決策者應(yīng)如何安排生產(chǎn)計(jì)劃 ， 使企業(yè)在計(jì)劃期內(nèi)總的利潤(rùn)收入最大 ？ 線(xiàn)性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 應(yīng)用模型舉例 2/4/2023 制作與教學(xué) 線(xiàn)性規(guī)劃 Linear Programming Page 5 產(chǎn)品 資源 甲 乙 丙 現(xiàn)有資源 設(shè)備 A 3 1 2 200 設(shè)備 B 2 2 4 200 材料 C 4 5 1 360 材料 D 2 3 5 300 利潤(rùn)（元 /件） 40 30 50 表 產(chǎn)品資源消耗 線(xiàn)性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 2/4/2023 制作與教學(xué) 線(xiàn)性規(guī)劃 Linear Programming Page 6 321 503040max xxxZ ???????????????????????????0003005323605420232220233321321321321321xxxxxxxxxxxxxxx，【解】設(shè) x x x3 分別為甲、乙、丙三種產(chǎn)品的產(chǎn)量數(shù)學(xué)模型為： 線(xiàn)性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 產(chǎn)品 資源 甲 乙 丙 現(xiàn)有資源 設(shè)備 A 3 1 2 200 設(shè)備 B 2 2 4 200 材料 C 4 5 1 360 材料 D 2 3 5 300 利潤(rùn)（元 /件） 40 30 50 最優(yōu)解 X=(50,30,10)。Z=3400 2/4/2023 制作與教學(xué) 線(xiàn)性規(guī)劃 Linear Programming Page 7 線(xiàn)性規(guī)劃的數(shù)學(xué)模型由 決策變量 Decision variables 目標(biāo)函數(shù) Objective function 及約束條件 Constraints 構(gòu)成。稱(chēng)為三個(gè)要素 。 ?其特征是： ?1．解決問(wèn)題的目標(biāo)函數(shù)是多個(gè)決策變量的 線(xiàn)性函數(shù)，通常是求最大值或 最小值； ?2．解決問(wèn)題的 約束條件 是一組多個(gè)決策變量 的線(xiàn)性不等式或等式。 怎樣辨別一個(gè)模型是線(xiàn)性規(guī)劃模型？ 線(xiàn)性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 2/4/2023 制作與教學(xué) 線(xiàn)性規(guī)劃 Linear Programming Page 8 【 例 】 某商場(chǎng)決定：營(yíng)業(yè)員每周連續(xù)工作 5天后連續(xù)休息 2天 ，輪流休息 。 根據(jù)統(tǒng)計(jì) ， 商場(chǎng)每天需要的營(yíng)業(yè)員如表 。 表 營(yíng)業(yè)員需要量統(tǒng)計(jì)表 商場(chǎng)人力資源部應(yīng)如何安排每天的上班人數(shù)，使商場(chǎng)總的營(yíng)業(yè)員最少。 星期 需要人數(shù) 星期 需要人數(shù) 一 300 五 480 二 300 六 600 三 350 日 550 四 400 線(xiàn)性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 2/4/2023 制作與教學(xué) 線(xiàn)性規(guī)劃 Linear Programming Page 9 【解】 設(shè) xj(j=1， 2， … ， 7)為休息 2天后星期一到星期日開(kāi)始上班的營(yíng)業(yè)員，則這個(gè)問(wèn)題的線(xiàn)性規(guī)劃模型為 ?????????????????????????????????????????????????????????7,2,1,0550600480400350300300min765436543254321743217632176521765417654321?jxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZj 線(xiàn)性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 星期 需要人數(shù) 星期 需要人數(shù) 一 300 五 480 二 300 六 600 三 350 日 550 四 400 2/4/2023 制作與教學(xué) 線(xiàn)性規(guī)劃 Linear Programming Page 10 1 X1 0 C1 404 = 300 104 2 X2 67 C2 301 = 300 1 3 X3 146 C3 350 = 350 0 4 X4 170 C4 400 = 400 0 5 X5 97 C5 480 = 480 0 6 X6 120 C6 600 = 600 0 7 X7 17 C7 550 = 550 0 最優(yōu)解： Z＝ 617（人） 2/4/2023 制作與教學(xué) 線(xiàn)性規(guī)劃 Linear Programming Page 11 【例 】合理用料問(wèn)題。某汽車(chē)需要用甲、乙、丙三種規(guī)格的軸各一根，這些軸的規(guī)格分別是 ， 1， （ m），這些軸需要用同一種圓鋼來(lái)做，圓鋼長(zhǎng)度為 4 m?，F(xiàn)在要制造 1000輛汽車(chē)，最少要用多少圓鋼來(lái)生產(chǎn)這些軸？ 【解】這是一個(gè)條材下料問(wèn)題 ，設(shè)切口寬度為零。 設(shè)一根圓鋼切割成甲、乙、丙三種軸的根數(shù)分別為 y1， y2， y3,則切割方式可用不等式+y2+≤4表示，求這個(gè)不等式關(guān)于 y1， y2， y3的非負(fù)整數(shù)解。象這樣的非負(fù)整數(shù)解共有 10組，也就是有 10種下料方式，如表 。 表 1． 3 下料方案 方案 規(guī)格 1 2 3 4 5 6 7 8 9 10 需求量 y1(根 ) 2 2 1 1 1 0 0 0 0 0 1000 y2 1 0 2 1 0 4 3 2 1 0 1000 y3 0 1 0 2 3 0 1 2 4 5 1000 余料（ m） 0 0 線(xiàn)性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 2/4/2023 制作與教學(xué) 線(xiàn)性規(guī)劃 Linear Programming Page 12 設(shè) xj(j=1,2… ,10)為第 j種下料方案所用圓鋼的根數(shù) 。 則用料最少數(shù)學(xué)模型 為 : 求下料方案時(shí)應(yīng)注意，余料不能超過(guò)最短毛坯的長(zhǎng)度；最好將毛坯長(zhǎng)度按降的次序排列，即先切割長(zhǎng)度最長(zhǎng)的毛坯，再切割次長(zhǎng)的，最后切割最短的，不能遺漏了方案 。如果方案較多，用計(jì)算機(jī)編程排方案，去掉余料較長(zhǎng)的方案，進(jìn)行初選。 ????????????????????????????? ??102,1,010005423210002342100022min10987542987643154321101，jxxxxxxxxxxxxxxxxxxxxxZjjj 線(xiàn)性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 方案 規(guī)格 1 2 3 4 5 6 7 8 9 10 需求量 y1(根 ) 2 2 1 1 1 0 0 0 0 0 1000 y2 1 0 2 1 0 4 3 2 1 0 1000 y3 0 1 0 2 3 0 1 2 4 5 1000 余料（ m） 0 0 2/4/2023 制作與教學(xué) 線(xiàn)性規(guī)劃 Linear Programming Page 13 1 X1 500 2 X2 0 3 X3 0 4 X4 0 5 X5 0 6 X6 7 X7 0 8 X8 0 9 X9 250 10 X10 0 Z＝ 2/4/2023 制作與教學(xué) 線(xiàn)性規(guī)劃 Linear Programming Page 14 【 例 】 配料問(wèn)題 。 某鋼鐵公司生產(chǎn)一種合金 ， 要求的成分規(guī)格是：錫不少于 28%， 鋅不多于 15%， 鉛恰好 10%， 鎳要界于35%~55%之間 ， 不允許有其他成分 。 鋼鐵公司擬從五種不同級(jí)別的礦石中進(jìn)行冶煉 ， 每種礦物的成分含量和價(jià)格如表 。礦石雜質(zhì)在治煉過(guò)程中廢棄 ， 現(xiàn)要求每噸合金成本最低的礦物數(shù)量 。 假設(shè)礦石在冶煉過(guò)程中 ， 合金含量沒(méi)有發(fā)生變化 。 表 礦石的金屬含量 合金 礦石 錫 % 鋅 % 鉛 % 鎳 % 雜質(zhì) 費(fèi)用（元 /t ） 1 25 10 10 25 30 340 2 40 0 0 30 30 260 3 0 15 5 20 60 180 4 20 20 0 40 20 230 5 8 5 15 17 55 190 線(xiàn)性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 2/4/2023 制作與教學(xué) 線(xiàn)性規(guī)劃 Linear Programming Page 15 解 : 設(shè) xj（ j=1,2， … ， 5）是第 j 種礦石數(shù)量，得到下列線(xiàn)性規(guī)劃模型 注意 ， 礦石在實(shí)際冶煉時(shí)金屬含量會(huì)發(fā)生變化 ， 建模時(shí)應(yīng)將這種變化考慮進(jìn)去 ， 有可能是非線(xiàn)性關(guān)系 。 配料問(wèn)題也稱(chēng)配方問(wèn)題 、營(yíng)養(yǎng)問(wèn)題或混合問(wèn)題 ， 在許多行業(yè)生產(chǎn)中都能遇到 。 線(xiàn)性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 礦石 錫 % 鋅 % 鉛 % 鎳 % 雜質(zhì) 費(fèi)用（元 /t ） 1 25 10 10 25 30 340 2 40 0 0 30 30 260 3