[管理學(xué)]管理運(yùn)籌學(xué) 第一章_線性規(guī)劃-文庫(kù)吧
2025-01-04 07:41 本頁(yè)面
【正文】 139。xxxxxxxxxxxxxxtsxxxzM a x，第一個(gè)約束加松弛變量 x5， 三、線性規(guī)劃的圖解法 1. 步驟 （ 1）作約束的圖形 ——可行域 可行解的集合 ① 先作非負(fù)約束 ②再作資源約束 9x1+4x2=360 4x1+5x2=200 3x1+10x2=300 公共部分，即為可行域 例：煤電油例 Max Z=7 x1 +12x2 9 x1 +4x2≤360 4x1 +5x2 ≤200 3 x1 +10x2 ≤300 x1 , x2≥0 . x1 x2 40 20 60 80 100 20 40 60 80 100 0 （ 2）作目標(biāo)函數(shù)的等值線 ① 給 z不同的值，作相應(yīng)直線，判斷出 z增大時(shí)，直線的移動(dòng)方向 ② 將直線向增大方向移動(dòng)，直至可行域邊界，交點(diǎn) X*即為最優(yōu)解。 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）無(wú)可行解 注：出現(xiàn)（ 3）、（ 4）情況時(shí)，建模有問(wèn)題 （ 4）無(wú)有限最優(yōu)解 圖解法的結(jié)論： ● 線性規(guī)劃的可行域是凸集 ● 線性規(guī)劃的最優(yōu)解若存在，必在可行域的在極點(diǎn)獲得 ● 若在兩個(gè)極點(diǎn)同時(shí)獲得，則有無(wú)窮多最優(yōu)解 凸集 不是凸集 極點(diǎn) 167。 2 線性規(guī)劃應(yīng)用舉例與軟件求解 例 1 （ 下料問(wèn)題） 某工廠要做 100套鋼架，每套用長(zhǎng)為 m, m, m的圓鋼各一根。已知原料每根長(zhǎng) m，問(wèn)：應(yīng)如何下料，可使所用原料最?。? 例 1 （ 下料問(wèn)題） 某工廠要做 100套鋼架，每套用長(zhǎng)為 m, m, m的圓鋼各一根。已知原料每根長(zhǎng) m，問(wèn)：應(yīng)如何下料，可使所用原料最??？ 方案 余料 m m 2 0 1 Ⅰ 1 2 0 Ⅱ 1 1 1 Ⅲ 1 0 3 0 Ⅳ 0 3 0 Ⅴ 0 2 2 Ⅵ 0 1 3 Ⅶ 0 0 4 Ⅷ 50 10 30 2x1 + x2 + x3 + x4 = 100 2x2 + x3 + 3x5 + 2x6 + x7 = 100 x1 + x3+ 3x4 + 2x6 + 3x7 + 4x8 = 100 x1, x2, x3, x4, x5, x6, x7, x8 ≥ 0 設(shè) x1,x2,x3,x4,x5,x6,x7,x8 分別為上述 8種方案下料的原材料根數(shù)， 建立如下的 LP模型： 最優(yōu)解為： x1=10,x2=50,x3=0,x4=30,x5=0,x6=0,x7=0,x8=0 min Z =x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 ?????. 余料 方案 2 0 1 Ⅰ 1 2 0 Ⅱ 1 1 1 Ⅲ 1 0 3 0 Ⅳ 0 3 0 Ⅴ 0 2 2 Ⅵ 0 1 3 Ⅶ 0 0 4 Ⅷ 線性規(guī)劃求解軟件 —— lindo 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ī)劃問(wèn)題化為一系列的線性規(guī)劃問(wèn)題來(lái)求解 整數(shù)規(guī)劃的分類： ? 純整數(shù)規(guī)劃：所有變量都限制為整數(shù) ? 混合整數(shù)規(guī)劃：僅部分變量限制為整數(shù) ? 01整數(shù)規(guī)劃：變量的取值僅限于 0或 1 [例 ] 人力資源分配的問(wèn)題 某晝夜服務(wù)的公交線路每天各時(shí)間段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下： 設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段一開(kāi)始時(shí)上班，并連續(xù)工作八小時(shí)，問(wèn)該公交線路怎樣安排司機(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í)開(kāi)始上班的司機(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
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1