線性規(guī)劃ppt課件(2)(編輯修改稿)
2025-05-26 02:51 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 … + 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ù)的問題： 設(shè)目標(biāo)函數(shù)為 Min f = c1x1 + c2x2 + … + xn (可以 )令 z ＝ f ， 則該極小化問題與下面的極大化問題有相同的最優(yōu)解 ，即 Max z = c1x1 c2x2 … xn 必須注意，盡管以上兩個(gè)問題的最優(yōu)解相同，但它們 最優(yōu)解的目標(biāo)函數(shù)值卻相差一個(gè)符號(hào)，即 Min f ＝ Max z 2） 約束條件不是等式的問題 ： 設(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í)， 類似地令 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í)稱為 “ 松弛變量 ” ；當(dāng)不等式為“大于等于”時(shí)稱為 “ 剩余變量 ” 。如果原問題中有若干個(gè)非等式 約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時(shí)，必須對(duì)各個(gè)約束引進(jìn)不同的松弛變量。 4）決策變量符號(hào)的問題： xj≤0時(shí) ,令 x/j=－ xj 。 b. 當(dāng)某一個(gè)決策變量 xj沒有符號(hào)限制時(shí)，可以令 xj = xj’ xj” 其中 xj’≥0， xj”≥0 即用兩個(gè)非負(fù)變量之差來表示一個(gè)無符號(hào)限制的變量，當(dāng)然 xj的符號(hào)取決于 xj’和 xj”的大小。 3） 右端項(xiàng)有負(fù)值的問題： 在標(biāo)準(zhǔn)形式中 ， 要求右端項(xiàng)必須每一個(gè)分量非負(fù) 。 當(dāng)某一個(gè)右端項(xiàng)系數(shù)為負(fù)時(shí) ， 如 bi0， 則把該等式約束兩端同時(shí)乘以 1， 得到： ai1 x1ai2 x2 … ain xn = bi。 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。=x－ a，則 a≤x≤b等價(jià)于 0≤ x39?！躡－ a，增加一個(gè)約束 x39?！躡－ a并且將原問題所有 x用 x= x39。+a替換。 【 例 28】 將下列線性規(guī)劃化為標(biāo)準(zhǔn)型 321 3m in xxxZ ????????????????????????無符號(hào)要求、32132132132100)3(523)2(3)1(82xxxxxxxxxxxx【 解 】 : (1)目標(biāo)函數(shù)為 min，令 Z’=Z； (2)因?yàn)?x3無符號(hào)要求 ，即 x3取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以令 0, 33333 ????????? xxxxx 其中 (4)第二個(gè)約束條件是 ≥號(hào)，在 ≥號(hào) 左端減去剩余變量 (Surplus variable)x5， x5≥0。也稱松馳變量 321 3m in xxxZ ????????????????????????無符號(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。 綜合起來得到下列標(biāo)準(zhǔn)型： 3321 33m a x xxxxZ ???????????????????????????????????????????05)(233826543321633215332143321xxxxxxxxxxxxxxxxxxxxxx、、【 例 29】 ：將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式 Min f = 2 x1 3x2 + 4 x3 . 3 x1 + 4x2 5 x3 ≤6 2 x1 + x3 ≥8 x1 + x2 + x3 = 9 x1 , x2 , x3 ≥ 0 解：首先 ,將目標(biāo)函數(shù)轉(zhuǎn)換成極大化： 令 z= f = 2x1+3x24x3 其次考慮約束 ， 有 2個(gè)不等式約束 ， 引進(jìn)松弛變量 x4， x5 ≥ 0。 第三個(gè)約束條件的右端值為負(fù)，在等式兩邊同時(shí)乘 1。 通過以上變換 ， 可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問題： Max z = 2x1 + 3 x2 4x3 . 3x1+4x25x3 +x4 = 6 2x1 +x3 x5 = 8 x1 x2 x3 = 9 x1 ,x2 ,x3 ,x4 ,x5 ≥ 0 【 例 210】 將下例線性規(guī)劃化為標(biāo)準(zhǔn)型 ???????????無約束、 211212145||||m a xxxxxxxxZ【 解 】 此題關(guān)鍵是將目標(biāo)函數(shù)中的絕對(duì)值去掉。 令 ： ???????????????????????????????0000000000002222222211111111xxxx
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1