【正文】 非負(fù)呢 0 5/2 1 0 0 1/2 10 0 1/2 0 1 0 1/2 6 0 1 0 0 1 0 3 1 –1/2 0 0 0 –1/2 2 A= _ X=（ 2， 0， 10， 6， 3， 0） ? 單純形法 線性規(guī)劃問題求解過程 相鄰基可行解 兩個基可行解稱為相鄰的，如果它們之間變換僅變換一個基 變量。 頂點 線性規(guī)劃解的性質(zhì) 幾個重要定（引）理獻(xiàn) ? 定理 1 若線性規(guī)劃問題存在可行解，則問題的可行域是凸集。 a1+ (1 223。 線性規(guī)劃解的性質(zhì) 如果 X X2為線性規(guī)劃的兩個可行解，則我們可以驗證由它們 X 構(gòu)造的 = aX1 + (1a)X2也為該問題的可行解。 只要滿足線性規(guī)劃問題的約束條件， 則稱該向量為線性規(guī)劃問題的可行解。不妨假設(shè)為前 m個， 則約束方程組的增廣矩陣可以表示成為： a11 a12 … a1m a1,m+1 … a1n a21 a22 … a2m a2,m+1 … a2n ┇ ┇ … ┇ ┇ … ┇ am1 am2 … amm am,m+1 … amn A= _ b1 b2 ┇ bm B1 B1 B1 B1 X= B1b 我們稱這個解為對應(yīng)與 基 B的 基解 。 一、線性規(guī)劃的數(shù)學(xué)模型的表示 上堂課回顧 xj ≥ 0 (j=1,2, … … ,n) st . max（ min） z = ??nj 1cjxj ??nj 1aijxj ≤ (或 =,≥) bi (i=1,2, … … ,m) max（ min） z = X ≥ 0 st . CX C=（ c1 , c2 , … … , ） Pjxj ≤ (或 =,≥) b 用向量表達(dá) ??nj 1Pj=（ a1j , a2j , … … , amj） 1 b=（ b1 , b2 , … … , bm） 1 簡化表示 X=（ x1 , x2 , … … , xn） 1 其中 X ≥ 0 st . AX ≤ (或 =,≥) b 用矩陣表達(dá) A= a11 a12 … a1n a21 a22 … a2n am1 am2 amn … … … 矩陣 A稱為約束方程組（約束條件）的系數(shù)矩陣。 資源擁有量 價值系數(shù) 在目標(biāo)函數(shù)中 xj的系數(shù) cj稱為 該決策變量的價值系數(shù)。 張良的故事 上堂課回顧 【運(yùn)籌學(xué)】 運(yùn)用數(shù)學(xué)方法研究經(jīng)濟(jì)、民政和國防等部門在內(nèi)外環(huán)境的約束條件下合理分配人力、物力、財力等資源，使實際系統(tǒng)有效運(yùn)行的技術(shù)科學(xué)，它可以用來預(yù)測發(fā)展趨勢，制定行動規(guī)劃或優(yōu)選方案?！比缓髲男渥永锾统鲆徊繒唤o張良，說 :“回去好好讀，將來可為國家出點兒力呢。 又過了五天，張良一聽雞叫就跑向大橋，還沒上橋，就看見老人了，老人瞪了他一眼，說 :“過五天再來吧。過五天，天一亮，你到橋上來見我?！? 張良沒說什么，就又順從地給老人穿上了鞋。他見張良走過來，故意將一只腳向后一縮，一只鞋掉到橋下去了。他們預(yù)先得知秦始皇要從博浪沙經(jīng)過，就在路旁樹林隱蔽的地方埋伏好，只等車隊到來，哪知這一椎扔出去沒砸準(zhǔn)，他們只得馬上躲起來。 一個最有代表性的例子 min z = x1 + 2x2 + 3x3 約束條件 2x1 + x2 + x3 ≤ 9 3x1 + x2 + 2x3 ≥ 4 4x1 2x2 3x3 = 6 x1 ≤ 0； x2 ≥ 0 ； x3取值無約束 st . 步驟 1）加入松弛變量把 不等式 約束 變?yōu)榈仁郊s束； 約束條件 2x1 + x2 + x3 ≤ 9 3x1 + x2 + 2x3 ≥ 4 4x1 2x2 3x3 = 6 x1 ≤ 0； st . x2 ≥ 0 ； x3取值無約束 + x + 2x – x5 = 4 2x1 + x2 + x3 + x4 = 9 x4， x5 ≥ 0 ； 一個最有代表性的例子 min z = x1 + 2x2 + 3x3 約束條件 2x1 + x2 + x3 ≤ 9 3x1 + x2 + 2x3 ≥ 4 4x1 2x2 3x3 = 6 x1 ≤ 0； x2 ≥ 0 ； x3取值無約束 st . 1）加入松弛變量把 不等式 約束 變?yōu)榈仁郊s束； 約束條件 4x1 2x2 3x3 = 6 x1 ≤ 0； st . x2 ≥ 0 ； x3取值無約束 3x1 + x2 + 2x3 – x5 = 4 2x1 + x2 + x3 + x4 = 9 2）把 b≤0 加等式約束兩邊同 乘以 1把 b變成 ≥0 約束； 1 + 2 + 3x3 6 x4， x5 ≥ 0 ； 步驟 一個最有代表性的例子 min z = x1 + 2x2 + 3x3 約束條件 2x1 + x2 + x3 ≤ 9 3x1 + x2 + 2x3 ≥ 4 4x1 2x2 3x3 = 6 x1 ≤ 0； x2 ≥ 0 ； x3取值無約束 st . 1）加入松弛變量把 不等式 約束 變?yōu)榈仁郊s束； 約束條件 x1 ≤ 0； st . x2 ≥ 0 ； x3取值無約束 3x1 + x2 + 2x3 – x5 = 4 2x1 + x2 + x3 + x4 = 9 2）把 b≤0 加等式約束兩邊同 乘以 1把 b變成 ≥0 約束； 4x1 + 2x2 + 3x3 = 6 3）把變量 xi≤0 ，令 xi/= xi 此時 xi/ ≥ 0 ； x1/ ≥ 0； 4x1/ + 2x2 + 3x3 = 6 3x1/ + x2 + 2x3 – x5 = 4 2x1/ + x2 + x3 + x4 = 9 x4， x5 ≥ 0 ； 步驟 一個最有代表性的例子 min z = x1 + 2x2 + 3x3 約束條件 2x1 + x2 + x3 ≤ 9 3x1 + x2 + 2x3 ≥ 4 4x1 2x2 3x3 = 6 x1 ≤ 0； x2 ≥ 0 ； x3取值無約束 st . 1）加入松弛變量把 不等式 約束 變?yōu)榈仁郊s束； 約束條件 st . x2 ≥ 0 ； x3取值無約束 2）把 b≤0 加等式約束兩邊同 乘以 1把 b變成 ≥0 約束； 3）把變量 xi≤0 ， 令 xi/= xi 此時 xi/ ≥ 0 ； x1/ ≥ 0； 4x1/ + 2x2 + 3x3 = 6 3x1/ + x2 + 2x3 – x5 = 4 2x1/ + x2 + x3 + x4 = 9 x4， x5 ≥ 0 ； 4）令 無約束變量 xi=xi/ xi∥ 代入 約束條件， xi用 xi/， xi∥ 代替； / ≥ 0 ， x3∥ ≥ 0 / 3x3∥ = 6 1/ 2 2 3/ 2x3∥ – x5 = 4 2x1/ + x2 + x3/ x3∥ + x4 = 9 步驟 一個最有代表性的例子 min z = x1 + 2x2 + 3x3 約束條件 2x1 + x2 + x3 ≤ 9 3x1 + x2 + 2x3 ≥ 4 4x1 2x2 3x3 = 6 x1 ≤ 0； x2 ≥ 0 ； x3取值無約束 st . 1）加入松弛變量把 不等式 約束 變?yōu)榈仁郊s束； 約束條件 st . x2 ≥ 0 ； 2）把 b≤0 加等式約束兩邊同 乘以 1把 b變成 ≥0 約束； 3）把變量 xi≤0 ， 令 xi/= xi 此時 xi/ ≥ 0 ； x1/ ≥ 0； x4， x5 ≥ 0 ； 4）令 無約束變量 xi=xi/ xi∥ 代入 約束條件， xi用 xi/， xi∥ 代替； x3/ ≥ 0 ， x3∥ ≥ 0 4x1/ + 2x2 + 3x3/ 3x3∥ = 6 3x1/ + x2 + 2x3/ 2x3∥ – x5 = 4 2x1/ + x2 + x3/ x3∥ + x4 = 9 5）如目標(biāo)為 min的，令 z/ = z ， 求 z/ 的 max。 max（ min） z = CX C=（ c1 , c2 , … … , ） 第二節(jié) 圖解法 項目 Ⅰ Ⅱ 每天可用能力 設(shè)備 A（ h） 設(shè)備 B（ h） 調(diào)試工序（ h） 0 6 1 5 2 1 15 24 5 利潤（元） 2 1 1）生產(chǎn)問題 利潤 max z= 2 x1 + x2 約束條件 5x2 ≤ 15 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1， x2 ≥ 0 st . z=0 z=3 z=6 z=12 z= x1 = x2 = 可行域 目標(biāo)函數(shù)等值線 最優(yōu)解 max z=x1+3x2 . x1+ x2≤6 x1+2x2≤8 x1 ≥0, x2≥0 例二 x1 x2 目標(biāo)函數(shù)等值線 可行域 最優(yōu)解 6 6 8 4 二）解的可能情況 1）無窮多最優(yōu)解 2）無解（無可行解） 利潤 max z= x1 + x2 約束條件 5x2 ≤ 15 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1， x2 ≥ 0 st . 約束條件 x1 + x2 ≥ 5 x1 + x2 ≤ 3 x1， x2 ≥ 0 st . max z= x1 + x2 二）解的可能情況 3）無界解 利潤 max z= x1 + x2 約束條件 5x2 ≤ 15 x1， x2 ≥ 0 st . 1）唯一最優(yōu)解 3）無解（無可行解） 2）無窮多最優(yōu)解 5）有限多個解 ？ 4）無界解 三、線性規(guī)劃問題的標(biāo)準(zhǔn)格式 1）線性規(guī)劃問題的標(biāo)準(zhǔn)格式 目標(biāo)為 最大化 max z = ??nj 1cjxj st . ??nj 1aijxj = bi (i=1,2, … … ,m) 其中： 1）目標(biāo)為最大化； 2） bi 為非負(fù)數(shù)； 3） xi 為非負(fù)數(shù)； 4）約束為等式。 技術(shù)系數(shù)或工藝系數(shù) aij量稱為該問題的技術(shù) 系數(shù)或工藝系數(shù)。 數(shù)學(xué)規(guī)劃的模型 一、問題的提出 及其數(shù)學(xué)模型 項目 Ⅰ Ⅱ 每天可用能力 設(shè)備 A（ h） 設(shè)備 B（ h） 調(diào)試工序（ h） 0 6 1 5 2 1 15 24 5 利潤（元） 2 1 1）生產(chǎn)問題 設(shè)： x1 —— I產(chǎn)品的生產(chǎn)量 x2 —— II產(chǎn)品的生產(chǎn)量 利潤 max z= 2 x1 + x2 約束條件 5x2 ≤ 15