運(yùn)籌學(xué)基礎(chǔ)對(duì)偶線性規(guī)劃(2)(編輯修改稿)
2025-05-27 12:05 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ） 對(duì)偶問(wèn)題對(duì)偶問(wèn)題 （或原問(wèn)題）目標(biāo)函數(shù)最大化 ( m ax Z )n 個(gè)變量m 個(gè)約束約束條件限定向量（右邊項(xiàng)）目標(biāo)函數(shù)價(jià)值向量（系數(shù)）≥ 0變量 ≤ 0 ≥無(wú)限制約束 ≤＝目標(biāo)函數(shù)最小化（ m i nS ）n 個(gè)約束m 個(gè)變量目標(biāo)函數(shù)價(jià)值向量（系數(shù)）約束條件限定向量（右邊項(xiàng)）≥約束 ≤≤ 0＝變量 ≥ 0 無(wú)限制原問(wèn)題原問(wèn)題 （或?qū)ε紗?wèn)題） 對(duì)偶問(wèn)題對(duì)偶問(wèn)題 （或原問(wèn)題）目標(biāo)函數(shù)最大化個(gè)變量個(gè)約束約束條件限定向量（右邊項(xiàng)）目標(biāo)函數(shù)價(jià)值向量（系數(shù)）≥變量 ≤≥無(wú)限制約束 ≤＝目標(biāo)函數(shù)最小化（ ）個(gè)約束個(gè)變量目標(biāo)函數(shù)價(jià)值向量（系數(shù)）約束條件限定向量（右邊項(xiàng)）≥約束 ≤≤＝變量 ≥無(wú)限制????????????????????無(wú)約束432143242143214321x,0x,x,0x6xxx4xx2x25xx3xxxx5x3x2fm i n 原問(wèn)題原問(wèn)題 （或?qū)ε紗?wèn)題） 對(duì)偶問(wèn)題對(duì)偶問(wèn)題 （或原問(wèn)題）目標(biāo)函數(shù)最小化 ( m i nS )n 個(gè)變量m 個(gè)約束約束條件限定向量（右邊項(xiàng)）目標(biāo)函數(shù)價(jià)值向量≥ 0變量 ≤ 0 ≥無(wú)限制約束 ≤＝目標(biāo)函數(shù)最大化（ m ax Z ）n 個(gè)約束m 個(gè)變量目標(biāo)函數(shù)價(jià)值向量（系數(shù)）約束條件限定向量≤約束 ≥≥ 0＝變量 ≤ 0無(wú)限制原問(wèn)題原問(wèn)題 （或?qū)ε紗?wèn)題） 對(duì)偶問(wèn)題對(duì)偶問(wèn)題 （或原問(wèn)題）目標(biāo)函數(shù)最小化個(gè)變量個(gè)約束約束條件限定向量（右邊項(xiàng)）目標(biāo)函數(shù)價(jià)值向量≥變量 ≤≥無(wú)限制約束 ≤＝目標(biāo)函數(shù)最大化（ ）個(gè)約束個(gè)變量目標(biāo)函數(shù)價(jià)值向量（系數(shù)）約束條件限定向量≤約束 ≥≥＝變量 ≤無(wú)限制練習(xí) ： 試求下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題 答案： 3 2 1 3 4 2 max x x x Z ? ? . 10 3 2 1 ? ? x x x 5 3 4 3 2 1 ? ? x x x 8 5 2 3 3 2 1 ? ? x x x 0 1 ? x ， 0 2 ? x 3 2 1 8 5 10 min y y y S ? ? . 2 3 3 2 1 ? ? y y y 4 2 4 3 2 1 ? ? ? y y y 3 5 3 3 2 1 ? y y y 0 1 ? y ， 0 3 ? y 原問(wèn)題原問(wèn)題 （或?qū)ε紗?wèn)題） 對(duì)偶問(wèn)題對(duì)偶問(wèn)題 （或原問(wèn)題）目標(biāo)函數(shù)最大化 ( m ax Z )n 個(gè)變量m 個(gè)約束約束條件限定向量（右邊項(xiàng)）目標(biāo)函數(shù)價(jià)值向量（系數(shù)）≥ 0變量 ≤ 0 ≥無(wú)限制約束 ≤＝目標(biāo)函數(shù)最小化（ m i nS ）n 個(gè)約束m 個(gè)變量目標(biāo)函數(shù)價(jià)值向量（系數(shù)）約束條件限定向量（右邊項(xiàng)）≥約束 ≤≤ 0＝變量 ≥ 0 無(wú)限制原問(wèn)題原問(wèn)題 （或?qū)ε紗?wèn)題） 對(duì)偶問(wèn)題對(duì)偶問(wèn)題 （或原問(wèn)題）目標(biāo)函數(shù)最大化個(gè)變量個(gè)約束約束條件限定向量（右邊項(xiàng)）目標(biāo)函數(shù)價(jià)值向量（系數(shù)）≥變量 ≤≥無(wú)限制約束 ≤＝目標(biāo)函數(shù)最小化（ ）個(gè)約束個(gè)變量目標(biāo)函數(shù)價(jià)值向量（系數(shù)）約束條件限定向量（右邊項(xiàng)）≥約束 ≤≤＝變量 ≥無(wú)限制練習(xí) ： 試求下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題 ????????????????????無(wú)約束432143242143214321x,0x,x,0x6xxx4xx2x25xx3xxxx5x3x2fm i n maxZ=5y1+4y2+6y3 y1+2y2≥ 2 y1 +2y2 +y3 ≤ 3 3y1 +y3 ≤ 5 y1 y2 +y3＝ 1 y1 ≥ 0, y2 , y3 ≤ 0 答案： 原問(wèn)題原問(wèn)題 （或?qū)ε紗?wèn)題） 對(duì)偶問(wèn)題對(duì)偶問(wèn)題 （或原問(wèn)題）目標(biāo)函數(shù)最小化 ( m i nS )n 個(gè)變量m 個(gè)約束約束條件限定向量（右邊項(xiàng)）目標(biāo)函數(shù)價(jià)值向量≥ 0變量 ≤ 0 ≥無(wú)限制約束 ≤＝目標(biāo)函數(shù)最大化（ m ax Z ）n 個(gè)約束m 個(gè)變量目標(biāo)函數(shù)價(jià)值向量（系數(shù)）約束條件限定向量≤約束 ≥≥ 0＝變量 ≤ 0無(wú)限制原問(wèn)題原問(wèn)題 （或?qū)ε紗?wèn)題） 對(duì)偶問(wèn)題對(duì)偶問(wèn)題 （或原問(wèn)題）目標(biāo)函數(shù)最小化個(gè)變量個(gè)約束約束條件限定向量（右邊項(xiàng)）目標(biāo)函數(shù)價(jià)值向量≥變量 ≤≥無(wú)限制約束 ≤＝目標(biāo)函數(shù)最大化（ ）個(gè)約束個(gè)變量目標(biāo)函數(shù)價(jià)值向量（系數(shù)）約束條件限定向量≤約束 ≥≥＝變量 ≤無(wú)限制線性規(guī)劃的對(duì)偶理論包括以下幾個(gè)基本定理。 定理 1 （對(duì)稱性定理） 167。 線性規(guī)劃的對(duì)偶理論 定理 2 （弱對(duì)偶定理） 即對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。 設(shè) x和 y分別是 原問(wèn)題 和對(duì)偶問(wèn)題的可行解，則必有 cx≤ yb，即原問(wèn)題的目標(biāo)值小于對(duì)偶問(wèn)題的目標(biāo)值 定理 3 （無(wú)界性） 若 原問(wèn)題 (對(duì)偶問(wèn)題 )為 無(wú)界解 ，則其對(duì)偶問(wèn)題 (原問(wèn)題 )無(wú)可行解 。 若原（對(duì)偶）問(wèn)題 有可行解 ,對(duì)偶（原）問(wèn)題 無(wú)可行解 ，則原（對(duì)偶）問(wèn)題一定 無(wú)界 ； 注 :此定理可以判定解的情況 定理 4 （可行解是最優(yōu)解的性質(zhì)） 定理 5 （強(qiáng)對(duì)偶定理） 設(shè) X*是原問(wèn)題的可行解， Y*是對(duì)偶問(wèn)題的可行解，當(dāng)CX*=Y*b時(shí)， X*與 Y*是最優(yōu)解 。 若原問(wèn)題有最優(yōu)解，那么對(duì)偶問(wèn)題也有最優(yōu)解，且目標(biāo)函數(shù)值相等 綜合上述結(jié)論得原問(wèn)題與對(duì)偶問(wèn)題的解的關(guān)系 一般是：cx≤yb 對(duì) 偶 問(wèn) 題 有最優(yōu)解 無(wú)界 無(wú)可行解 原 有最優(yōu)解 一定 不可能 不可能 問(wèn) 無(wú) 界 不可能 不可能 一定 題 無(wú)可行解 不可能 可能 可能 原問(wèn)題與對(duì)偶問(wèn)題解的
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1