線性規(guī)劃ppt課件(2)-在線瀏覽
2025-06-16 02:51本頁(yè)面
【正文】 b1 的允許增加量為 325 300 = 25 ? 允許減少量 = 現(xiàn)在值 下限 c2 的允許減少量為 100 50 = 50 b3 的允許減少量為 250 200 = 50 ? 允許增加的百分比 = 增加量 / 允許增加量 ? 允許減少的百分比 = 減少量 / 允許減少量 例： c1 變?yōu)? 74 , c2 變?yōu)? 78, 則 (74 50) / 50 + (100 78 ) / 50 = 92%， 故最優(yōu)解不變； b1 變?yōu)? 315 , b3 變?yōu)? 240, 則 (315 50) / 25 + (250 240 ) / 50 = 80%， 故 對(duì)偶價(jià)格不變 （ 最優(yōu)解仍是原來(lái)幾個(gè)線性方程的解 ） 。 這種情況下 ， 需要重新進(jìn)行求解 。 ? 對(duì)偶價(jià)格 當(dāng)約束條件中的常數(shù)項(xiàng)增加一個(gè)單位時(shí)，最優(yōu)目標(biāo)函數(shù)值改進(jìn)的數(shù)量。 線性規(guī)劃的標(biāo)準(zhǔn)化 ? 一般形式 目標(biāo)函數(shù)： Max （ Min） z = c1 x1 + c2 x2 + … + 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 ? 標(biāo)準(zhǔn)形式 目標(biāo)函數(shù)： Max z = c1 x1 + c2 x2 + … + 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 ， bi ≥0 1） 極小化目標(biāo)函數(shù)的問(wèn)題： 設(shè)目標(biāo)函數(shù)為 Min f = c1x1 + c2x2 + … + xn (可以 )令 z ＝ f ， 則該極小化問(wèn)題與下面的極大化問(wèn)題有相同的最優(yōu)解 ，即 Max z = c1x1 c2x2 … xn 必須注意，盡管以上兩個(gè)問(wèn)題的最優(yōu)解相同，但它們 最優(yōu)解的目標(biāo)函數(shù)值卻相差一個(gè)符號(hào)，即 Min f ＝ Max z 2） 約束條件不是等式的問(wèn)題 ： 設(shè)約束條件為 ai1 x1+ai2 x2+ … +ain xn ≤ bi 可以引進(jìn)一個(gè)新的變量 s ， 使它等于約束右邊與左 邊之差 s=bi–(ai1 x1 + ai2 x2 + … + ain xn ) 顯然 ， s 也具有非負(fù)約束 ， 即 s≥ 0， 這時(shí)新的約束條件成為 ai1 x1+ai2 x2+ … +ain xn+ s = bi 當(dāng)約束條件為 ai1 x1+ai2 x2+ … +ain xn ≥ bi 時(shí)， 類(lèi)似地令 s=(ai1 x1+ai2 x2+ … + ain xn) bi 顯然 ， s 也具有非負(fù)約束 ， 即 s≥ 0， 這時(shí)新的約 束條件成為 ai1 x1+ai2 x2+ … + ain xns = bi 為了使 約束由不等式成為等式而引進(jìn)的變量 s,當(dāng)不等式為“小于等于”時(shí)稱(chēng)為 “ 松弛變量 ” ；當(dāng)不等式為“大于等于”時(shí)稱(chēng)為 “ 剩余變量 ” 。 4）決策變量符號(hào)的問(wèn)題： xj≤0時(shí) ,令 x/j=－ xj 。 3） 右端項(xiàng)有負(fù)值的問(wèn)題： 在標(biāo)準(zhǔn)形式中 ， 要求右端項(xiàng)必須每一個(gè)分量非負(fù) 。 c. 絕對(duì)值不等式 當(dāng)某個(gè)約束是絕對(duì)值不等式時(shí)，將絕對(duì)值不等式化為兩個(gè)不等式，再化為等式，例如約束 ： 974 321 ??? xxx可將其化為兩個(gè)不等式，再加入松馳變量化為等式： ??????????974974321321xxxxxxd. a≤x≤b (a、 b均大于零 ) 有兩種方法： 一種方法是增加兩個(gè)約束 x≥a及 x≤b 另一種方法是令 x39。≤b－ a，增加一個(gè)約束 x39。+a替換。也稱(chēng)松馳變量 321 3m in xxxZ ????????????????????????無(wú)符號(hào)要求、 32132132132100)3(523)2(3)1(82xxxxxxxxxxxx(3) 第一個(gè)約束條件是 ≤號(hào)，在 ≤左端加入松馳變量 (slack variable) x4，x4≥0,化為等式； (5)第三個(gè)約束條件是 ≤號(hào)且常數(shù)項(xiàng)為負(fù)數(shù)，因此在 ≤左邊加入松馳變量 x6， x6≥0，同時(shí)兩邊乘以－ 1。 第三個(gè)約束條件的右端值為負(fù)，在等式兩邊同時(shí)乘 1。 令 ： ???????????????????????????????0000000000002222222211111111xxxxxxxxxxxxxxxx，，，－，，222222111111,||,||xxxxxxxxxxxx????????????????????則有： 得到線性規(guī)劃的標(biāo)準(zhǔn)形式 1 1 2 21 1 2 2 31 1 41 1 2 2 3 4m a x ( ) ( )540Z x x x xx x x x xx x xx x x x x x? ?? ? ??? ? ? ? ?? ?? ? ??? ? ? ? ???? ??? ? ??? ? ?? ? ?? ?? 、 、 、 、 、作業(yè) ? 教材第五章習(xí)題 7中線性規(guī)劃化為標(biāo)準(zhǔn)型 普通單純形法 設(shè)線性規(guī)劃的標(biāo)準(zhǔn)型 max Z=CX （ ） AX=b （ ） X ≥0 （ ） 式中 A 是 m n矩陣 ， m≤n并且 r（ A） =m， 顯然 A中至少有一個(gè) m m子矩陣 B，
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1