【文章內(nèi)容簡介】 Ⅰ Ⅱ 每天可用能力 設(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）約束為等式。 xj ≥ 0 (j=1,2, … … ,n) 約束為等式 bi 為非負(fù)數(shù) xi 為非負(fù)數(shù) 2）線性規(guī)劃問題的標(biāo)準(zhǔn)格式方法 利潤 max z= 2 x1 + x2 約束條件 5x2 ≤ 15 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1， x2 ≥ 0 st . 怎么辦？ 5x2 + x3 = 15 6x1 + 2x2 + x4 = 24 x1 + x2 + x5 = 5 x1， x2 ， x3 ， x4 ， x5 ≥ 0 約束條件 st . 利潤 max z= 2 x1 + x2 + 0x3 + 0x4 + 0x5 2）線性規(guī)劃問題的標(biāo)準(zhǔn)格式方法 x11+x12 +x13 +x14 – x1 = 15 x12+x13 +x14 + x21+x22 +x23 – x2 = 10 x13+x14 + x22+x23 +x31 +x32 x3 = 20 xij ， x1 ， x2 ， x3 ， x4 ≥ 0 約束條件 st . 租金 max z/ = z = 2800（ x11+x21 +x31 +x41） 4500（ x12+x22 +x32） 6000（ x13+x23 ） 7300x14+ 0x1+ 0x2 + 0x3 + 0x4 租金 min z= 2800（ x11+x21 +x31 +x41） +4500（ x12+x22 +x32） +6000（ x13+x23 ） +7300x14 約束條件 x11+x12 +x13 +x14 ≥ 15 x12+x13 +x14 + x21+x22 +x23 ≥ 10 x13+x14 + x22+x23 +x31 +x32 ≥ 20 xij ≥ 0 (i, j = 1,2,3,4) st . x14+x23 +x24 +x32 +x41 ≥ 12 x14+x23 +x24 +x32 +x41 x4 = 12 180。 對于不等式約束中，通過加上（減去）一個變量，把不等式變?yōu)? 等式，我們稱這個變量為 松弛變量 松弛變量 松弛變量在有些教材中也稱為剩余變量，在實際問題中表示未被利用用的資源或超出的資源，我們在對偶問題的學(xué)習(xí)中我們知道，該資源的影子價格為零。 線性規(guī)劃問題都可以化為標(biāo)準(zhǔn)形式，在以后分析問題都以標(biāo)準(zhǔn)形式為基礎(chǔ)。 一個最有代表性的例子 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 z/ = z = x1/ 2x2 3x3/ + 3x3∥ + 0x4 0x5 步驟 返 回 公元前二一八年，秦始皇帶大隊人馬外出巡視，行進(jìn)到博浪沙 (河南原陽縣 )，車隊正在緩緩前進(jìn)，突然飛來一個大鐵椎，只聽嘩啦一聲，秦始皇座車后面的副車被打得粉碎，把秦始皇嚇壞了，他真發(fā)火了，立刻下令，全國搜捕刺客，結(jié)果搜查了十天，也沒抓到，只得算了。 刺客是誰呢 ?原來他叫張良，是韓國人，他要為韓國報仇。他有一個朋友是個大力士，使用的兵器是一個大鐵椎，足有六十斤重。他們預(yù)先得知秦始皇要從博浪沙經(jīng)過，就在路旁樹林隱蔽的地方埋伏好，只等車隊到來，哪知這一椎扔出去沒砸準(zhǔn)，他們只得馬上躲起來。 張良躲過了搜查，就在下邳 (江蘇睢寧西北 )住下來，一面鉆研兵法，一面再等報仇的機(jī)會。 說起張良學(xué)兵法，這里還有一個傳說故事呢。 有一次，張良獨(dú)自散步，走到一座大橋上，見一位穿土黃色大褂的老人，坐在橋頭上。他見張良走過來，故意將一只腳向后一縮，一只鞋掉到橋下去了。 老人不客氣地對張良說 :“年輕人，下去把我的鞋子撿上來。” 張良聽了有點不高興，可是一想，他是老人，不多計較，就到橋下，拾起鞋子，又走上來遞給老人。 誰知那老人不接鞋子，卻把腳一伸，說 :“給我穿上。” 張良沒說什么，就又順從地給老人穿上了鞋。 那老人這才微微一笑，站起身來走了。 張良覺得這位老人好奇怪，不是一般人，站著沒動，目送老人走遠(yuǎn) 。 誰知老人走了很遠(yuǎn)又返回來了，對張良說 :“年輕人，不錯呀，我倒樂意教導(dǎo)教導(dǎo)你。過五天，天一亮，你到橋上來見我?！? 張良聽后忙跪下答應(yīng)了。