【正文】 x1 ， x2 ， … ， xn ≥ 0 **練習(xí)： p 6870 習(xí)題 1 11， 12 14 線 性 規(guī) 劃 （續(xù) ） 1. 2 線性規(guī)劃問(wèn)題解的概念及性質(zhì) ? 熟悉下列一些解的概念（ p1516） 可行解、可行解集（可行域），最優(yōu)解、最優(yōu)值，基、基變量、非基變量，基本解、基本可行解，可行基、最優(yōu)基。 ? 單純形法的理論基礎(chǔ)（ p2030） ，了解如何直接通過(guò)對(duì)約束矩陣的分析求出基本可行解 , ，如單純形法思想和關(guān)于線性規(guī)劃解的四個(gè) 定理，而對(duì)證明過(guò)程則可根據(jù)自己的數(shù)學(xué)基礎(chǔ)來(lái)掌握： 基礎(chǔ)很好，可要求掌握；否則，也可略去不看。要通過(guò)讀懂教材內(nèi)容以及大量練習(xí)來(lái)掌握。 xn+i = bi i = 1 , … , m 是基本可行解 對(duì)應(yīng)的基是單位矩陣?；瘶?biāo)準(zhǔn)形式： Max z = 50 x1 + 100 x2 . x1 + x2 + x3 = 300 2 x1 + x2 + x4 = 400 x2 + x5 = 250 x1 , x2 , x3 , x4 , x5 ≥ 0 最優(yōu)解 x1 = 50 x2 = 250 x4 = 50（松弛標(biāo)量，表示原料 A有 50個(gè)單位的剩余） 20 ? 注意：?jiǎn)渭冃畏ㄖ校? 每一步運(yùn)算只能用矩陣初等行變換； 表中第 3列的數(shù)總應(yīng)保持非負(fù)（ ≥ 0）； 當(dāng)所有檢驗(yàn)數(shù)均非正（ ≤ 0）時(shí)，得到最優(yōu)單純形表。要弄清它的原理，并通過(guò)例 114 ~ 例 117掌握這些方法，同時(shí)進(jìn)一步熟悉用單純形法解題。 充分大正數(shù) M 。 xn+i = bi i =1 , … , m 是基本可行解 對(duì)應(yīng)的基是單位矩陣。 23 線 性 規(guī) 劃 （續(xù) ） ? 兩階段法： 引入人工變量 xn+i ≥ 0， i = 1 , … , m ；構(gòu)造， Max z = xn+1 xn+2 … xn+m . a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2 …… …… am1 x1 + am2 x2 + … + amn xn + xn+m = bm x1 ， x2 ， … ， xn ， xn+1 ， … ， xn+m ≥ 0 ? 第一階段求解上述問(wèn)題： 顯然， xj = 0 j=1, … , n 。 ? 結(jié)論：若得到的最優(yōu)解滿(mǎn)足 xn+i = 0 i = 1 , … , m 則是原問(wèn)題的基本可行解；否則，原問(wèn)題無(wú)可行解。 24 線 性 規(guī) 劃 （續(xù) ）例題 例：（ LP） Max z = 5 x1 + 2 x2 + 3 x3 x4 . x1 + 2 x2 + 3 x3 = 15 2 x1 + x2 + 5 x3 = 20 x1 + 2 x2 + 4 x3 + x4 = 26 x1 , x2 , x3 , x4 ≥ 0 ? 大 M法問(wèn)題（ LP M） Max z = 5 x1 + 2 x2 + 3 x3 x4 M x5 M x6 . x1 + 2 x2 + 3 x3 + x5 = 15 2 x1 + x2 + 5 x3 + x6 = 20 x1 + 2 x2 + 4 x3 + x4 = 26 x1 , x2 , x3 , x4 , x5 , x6 ≥ 0 ? 兩階段法 ：第一階段問(wèn)題（ LP 1） Max z = x5 x6 . x1 + 2 x2 + 3 x3 + x5 = 15 2 x1 + x2 + 5 x3 + x6 = 20 x1 + 2 x2 + 4 x3 + x4 = 26 x1 , x2 , x3 , x4 , x5 , x6 ≥ 0 25 線 性 規(guī) 劃 （續(xù) ）大 M法例 5 2 3 1 M MCBXBx1x2x3x4x5x6θiM x515 1 2 3 0 1 0 5M x620 2 1 ( 5) 0 0 1 41 x426 1 2 4 1 0 0 z 35M+26 3M+6 3M+4 8M+7 0 0 0M x53 1/5 ( 7/5) 0 0 1 3/5 15/73 x34 2/5 1/5 1 0 0 1/5 201 x410 3/5 6/5 0 1 0 4/5 25/3z 3M 2 M/5+16/ 5 7/5M+13/5 0 0 0 8/5M 7/52 x215/7 1/7 1 0 0 5/7 3/73 x325/7 ( 3/7) 0 1 0 1/7 2/7 25/31 x452/7 3/7 0 0 1 6/7 2/7z 53/7 25/7 0 0 0 M 13 /7 M 2 /72 x210/3 0 1 1/3 0 2/3 1/35 x125/3 1 0 7/3 0 1/3 2/31 x411 0 0 1 1 1 0z 1 12/3 0 0 25/3 0 M 2 /3 M+8/3?大 M法 （ LP M） ? 得到最優(yōu)解： (25/3， 10/3， 0， 11)T 最優(yōu)目標(biāo)值： 112/3 26 線 性 規(guī) 劃 （續(xù) ）兩階段法例 0 0 0 0 1 1CBXBx1x2x3x4x5x6θi1 x515 1 2 3 0 1 0 51 x620 2 1 ( 5) 0 0 1 40 x426 1 2 4 1 0 0 z 35 3 3 8 0 0 01 x53 1/5 ( 7/5) 0 0 1 3/5 15/70 x34 2/5 1/5 1 0 0 1/5 200 x410 3/5 6/5 0 1 0 4/5 25/3z 3 1/5 7/5 0 0 0 8/50 x215/7 1/7 1 0 0 5/7 3/70 x325/7 3/7 0 1 0 1/7 2/7 25/30 x452/7 3/7 0 0 1 6/7 2/7z 0 0 0 0 0 1 1?第一階段 （ LP 1） ? 得到原問(wèn)題的基本可行解： (0， 15/7， 25/7， 52/7)T 27 線 性 規(guī) 劃 （續(xù) ）兩階段法例 5 2 3 1CBXB x 1 x 2 x 3 x 4 θ i2 x215/7 1/7 1 0 03 x325/7 ( 3/7) 0 1 0 25/31 x452/7 3/7 0 0 1z 53/7 25/7 0 0 02 x210/3 0 1 1/3 05 x125/3 1 0 7/3 01 x411 0 0 1 1z 1 12/3 0 0 25/3 0?第二階段 把基本可行解填入表中 ? 得到原問(wèn)題的最優(yōu)解： (25/3， 10/3， 0， 11)T ?最優(yōu)目標(biāo)值： 112/3 28 線 性 規(guī) 劃 （續(xù) ） 矩陣描述 —— 此段為選讀，有困難者可不看。 **習(xí)題： p7071 習(xí)題 1 15， 16 29 1. 4 線性規(guī)劃應(yīng)用 —— 建模（ p5568） 本節(jié)介紹了些線性規(guī)劃應(yīng)用的例子，這些例子從多個(gè)方面介紹建模對(duì)未來(lái)是很有用的，應(yīng)認(rèn)真對(duì)待。這些例子有一定的難度，做起來(lái)會(huì)有一些困難。 目標(biāo)函數(shù)： Min x1 + x2 + x3 + x4 + x5 + x6 約束條件： . 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 例：人力資源分配的問(wèn)題（續(xù)） 32 例、 明興公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過(guò)鑄造、機(jī)加工和裝配三個(gè)車(chē)間。數(shù)據(jù)如下表。 求 xi 的利潤(rùn)：利潤(rùn) = 售價(jià) 各成本之和 可得到 xi（ i=1,2,3,4,5）的利潤(rùn)分別為 1 1 9元。 目標(biāo)函數(shù)： Max 15x1 + 10x2 + 7x3 + 13x4 + 9x5 約束條件： . 5x1 + 10x2 + 7x3 ≤ 8000 6x1 + 4x2 + 8x3 + 6x4 + 4x5 ≤ 12022 3x1 + 2x2 + 2x3 + 3x4 + 2x5 ≤ 10000 x1,x2,x3,x4,x5 ≥ 0 例：生產(chǎn)計(jì)劃的問(wèn)題（續(xù)） 34 例、 永久機(jī)械廠生產(chǎn) Ⅰ 、 Ⅱ 、 Ⅲ 三種產(chǎn)品，均要經(jīng)過(guò) A、 B 兩道工序加工。 Ⅰ 可在 A、 B的任何規(guī)格的設(shè)備上加工； Ⅱ 可在任意規(guī)格的 A設(shè)備上加工，但對(duì) B工序，只能在 B1設(shè)備上加工； Ⅲ 只能在 A2與 B2設(shè)備上加工；數(shù)據(jù)如下表。 利潤(rùn) = [（銷(xiāo)售單價(jià) 原料單價(jià)） * 產(chǎn)品件數(shù) ]之和 （每臺(tái)時(shí)的設(shè)備費(fèi)用 *設(shè)備實(shí)際使用的總臺(tái)時(shí)數(shù)）之和。 j = 1,2。已知原料每根長(zhǎng) m，問(wèn)：應(yīng)如何下料，可使所用原料最??？ 解： 設(shè)計(jì)下列 5 種下料方案 方案 1 方案 2 方案 3 方案 4 方案 5 方案 6 方案 7 方案 82. 9 m 1 2 0 1 0 1 0 02. 1 m 0 0 2 2 1 1 3 01. 5 m 3 1 2 0 3 1 0 4合計(jì) 7. 4 7. 3 7. 2 7. 1 6. 6 6. 5 6. 3 6. 0剩余料頭 0 0. 1 0. 2 0. 3 0. 8 0. 9 1. 1 1 . 4假設(shè) x1,x2,x3