[管理學(xué)]管理運(yùn)籌學(xué)第一章_線性規(guī)劃-wenkub
2023-02-03 07:41:21 本頁(yè)面
【正文】 X AX=b X ≥ 0 . 其中： C=(c1,c2, …, c n) 稱為 價(jià)格系數(shù) A=(aij)m n 稱為 技術(shù)系數(shù) b= (b1,b2, …, b m) 稱為 資源系數(shù) 非標(biāo)準(zhǔn)型 標(biāo)準(zhǔn)型 （ 1） Min Z = CX Max Z39。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)解。已知原料每根長(zhǎng) m，問：應(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。 問如何選擇井位使總費(fèi)用最??？ 課堂練習(xí) 1: 某鉆井隊(duì)要從 S1~S10共 10個(gè)井位中確定五個(gè)鉆井探油，如果選 Si，估計(jì)鉆探費(fèi)用為 ci元，并且井位選擇上要滿足下列條件： （ 1）或選擇 S1和 S7，或選擇 S8 （ 2）選擇了 S3或 S4就不能選擇 S5，反過來也一樣 （ 3）在 S5， S6 ， S7， S8中最多只能選兩個(gè) 問如何選擇井位使總費(fèi)用最?。? 1， Si被選中 0， Si沒被選中 ?????解：令 xi= min z= ??101iiixc?????. 5101???iix 181 ?? xx187 ?? xx153 ?? xx154 ?? xx28765 ???? xxxx或 1， i=1, … ,10 0?ix 某籃球隊(duì)有 8名隊(duì)員，其身高和專長(zhǎng)如下表，現(xiàn)要選拔 5名球員上場(chǎng)參賽，要求： （ 1）中鋒只有 1人上場(chǎng) （ 2）后衛(wèi)至少有一人上場(chǎng) （ 3）只有 2號(hào)上場(chǎng)， 6號(hào)才上場(chǎng) 要求平均身高最高，應(yīng)如何選拔隊(duì)員？ 隊(duì)員 1 2 3 4 5 6 7 8 身高 1. 92 1. 90 1. 88 1. 86 1. 85 1. 83 1. 80 1. 78 專長(zhǎng) 中鋒 中鋒 前鋒 前鋒 前鋒 后衛(wèi) 后衛(wèi) 后衛(wèi) 課堂練習(xí) 2: 1， 隊(duì)員 i被選中 0，隊(duì)員 i沒被選中 ?????解：令 xi= max z= ??8151iii xc 581???iix 121 ?? xx1876 ??? xxx 26 xx ?或 1， i=1, … ,8 0?ix?????. 某籃球隊(duì)有 8名隊(duì)員，其身高和專長(zhǎng)如下表，現(xiàn)要選拔 5名球員上場(chǎng)參賽，要求： （ 1）中鋒只有 1人上場(chǎng) （ 2）后衛(wèi)至少有一人上場(chǎng) （ 3）只有 2號(hào)上場(chǎng)， 6號(hào)才上場(chǎng) 要求平均身高最高，應(yīng)如何選拔隊(duì)員？ 2. 指派問題 例： 有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作任務(wù) E、 J、 G、 R，現(xiàn)有甲、乙、丙、丁四人，他們將中文說明書翻譯成不同語種說明書所需的時(shí)間如下表所示，問應(yīng)指派何人去完成何項(xiàng)任務(wù)，使所需總時(shí)間最少？ E J G R 甲 2 1 5 13 4 乙 10 4 14 15 丙 9 14 1 6 13 丁 7 8 11 9 問題描述： n項(xiàng)任務(wù)可由 n個(gè)人完成，由于專長(zhǎng)不同，各人完成各任務(wù)的時(shí)間也不同，求最優(yōu)安排。 問題： 攜帶哪些物品可使總價(jià)值最大？ 一般模型 ???miii xczM ax1?????. bxamiii ??? 110 或?ix1， 物品 i被選中
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1