【正文】 jijijxnjbxmiaxstxcz??增加 松弛變量 ),1(11njbx jmiij ??????運(yùn)輸表： 實(shí)際意義： 虛設(shè)一 個(gè)產(chǎn)地 ?? ?? ij abB1 … Bn A1 x11 … x1n a1 … … … … … Am xm1 … xmn am Am+1 xm+1， 1 … xm+1,n am+1 b1 … bn 六、應(yīng)用舉例（ 生產(chǎn)與儲(chǔ)存問(wèn)題 ） 例 、某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供 1 2 20臺(tái)同一規(guī)格的柴油機(jī)。已知原料每根長(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。 2 線性規(guī)劃的舉例與軟件求解 167。 1 線性規(guī)劃的模型與圖解法 一、 LP問(wèn)題及其數(shù)學(xué)模型 二、線性規(guī)劃的標(biāo)準(zhǔn)型 三、線性規(guī)劃的圖解法 一、 LP問(wèn)題及其數(shù)學(xué)模型 例 1 某工廠可生產(chǎn)甲、乙兩種產(chǎn)品，需消耗煤、電、油三種資源，有關(guān)單耗數(shù)據(jù)如表，試擬定使總收入最大的生產(chǎn)計(jì)劃。 （ 3） 在 S5， S6 ， S7， S8中最多只能選兩個(gè)。 試求在完成合同的情況下，使該廠全年生產(chǎn)總費(fèi)用為最小的決策方案。 B1 B2 B3 B4 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 3 6 5 6 3 1 3 4 6 3 根據(jù)閉回路計(jì)算空格的檢驗(yàn)數(shù)： 檢驗(yàn)數(shù) = 奇數(shù)頂點(diǎn)的單位運(yùn)價(jià)之和 – 偶數(shù)頂點(diǎn)的單位運(yùn)價(jià)之和 B1 B2 B3 B4 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 3 6 5 6 3 1 3 4 6 3 1 2 1 1 10 12 檢驗(yàn)數(shù)的經(jīng)濟(jì)含義：當(dāng)由產(chǎn)地Ai往銷地 Bj增運(yùn)一個(gè)單位貨物時(shí)所引起的總運(yùn)輸成本的變化數(shù) 結(jié)論：若所有檢驗(yàn)數(shù)都大于等于 0，則當(dāng)前方案最優(yōu) B1 B2 B3 B4 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 3 6 5 6 3 1 3 4 6 3 1 1 2 1 10 12 對(duì)現(xiàn)有方案進(jìn)行調(diào)整 在負(fù)的檢驗(yàn)數(shù)中選擇絕對(duì)值最大的空格，在方案表中從該空格出發(fā)，沿著其閉回路依次標(biāo)上 “ +q‖、 “ q‖， +q q +q q 其中 q表示最大調(diào)整量，它的取值為標(biāo) “ q‖的數(shù)字中最小的數(shù)值。已知原料每根長(zhǎng) m，問(wèn)：應(yīng)如何下料，可使所用原料最省？ 例 1 （ 下料問(wèn)題） 某工廠要做 100套鋼架，每套用長(zhǎng)為 m, m, m的圓鋼各一根。 1 線性規(guī)劃的模型與圖解法 167。 12 7 單價(jià) 300 10 3 油 200 5 4 電 360 4 9 煤 資源限制 乙 甲 產(chǎn)品 資源 甲 乙 資源限制 煤 9 4 360 電 4 5 200 油 3 10 300 單價(jià) 7 12 產(chǎn)品 資源 線性規(guī)劃模型三要素： （ 1）決策變量 設(shè)甲產(chǎn)品生產(chǎn) x1，乙產(chǎn)品生產(chǎn) x2 （ 2）目標(biāo)函數(shù) Max Z=7 x1 +12x2 （ 3）約束條件 9 x1 +4x2≤360 4x1 +5x2 ≤200 3 x1 +10x2 ≤300 x1 , x2≥0 . 返回 Subject To， 意為“使其滿足” 目標(biāo)函數(shù)： Max （ Min） Z = c1 x1 + c2 x2 + … + c n xn a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ） b1 a21 x1 + a22 x2 + … + a2n xn ≤ （ =, ≥ ） b2 …… …… am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ） bm x1 ， x2 ， … ， xn ≥ 0 約束條