線性規(guī)劃問題的基本理論.ppt

第二章第2節(jié)線性規(guī)劃問題的基本理論 一 線性規(guī)劃問題的標(biāo)準(zhǔn)化二 線性規(guī)劃問題的解三 線性規(guī)劃問題的幾何意義 一 線性規(guī)劃問題的標(biāo)準(zhǔn)化 一般形式目標(biāo)函數(shù) Max Min z c1x1 c2x2 cnxn約束條件 a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bm決策變量 x1 x2 xn 0 標(biāo)準(zhǔn)形式目標(biāo)函數(shù) Maxz c1x1 c2x2 cnxn約束條件 a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bm決策變量 bi 0 x1 x2 xn 0 一般型和標(biāo)準(zhǔn)型的區(qū)別 可以看出 線性規(guī)劃的標(biāo)準(zhǔn)形式有如下四個(gè)特點(diǎn) 目標(biāo)最大化 約束為等式 決策變量均非負(fù) 右端項(xiàng)非負(fù) 對(duì)于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題 我們總可以通過以下變換 將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式 1 極小化目標(biāo)函數(shù)的問題 設(shè)目標(biāo)函數(shù)為Minf c1x1 c2x2 cnxn 可以 令z f 則該極小化問題與下面的極大化問題有相同的最優(yōu)解 即Maxz c1x1 c2x2 cnxn但必須注意 盡管以上兩個(gè)問題的最優(yōu)解相同 但它們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個(gè)符號(hào) 即Minf Maxz 2 約束條件不是等式的問題 設(shè)約束條件為ai1x1 ai2x2 ainxn bi可以引進(jìn)一個(gè)新的變量s 使它等于約束右邊與左邊之差 一般稱S為松弛變量 s bi ai1x1 ai2x2 ainxn 顯然 s也具有非負(fù)約束 即s 0 這時(shí)新的約束條件成為ai1x1 ai2x2 ainxn s bi 當(dāng)約束條件為ai1x1 ai2x2 ainxn bi時(shí) 類似地令s ai1x1 ai2x2 ainxn bi顯然 s也具有非負(fù)約束 即s 0 這時(shí)新的約束條件成為ai1x1 ai2x2 ainxn s bi稱S為剩余變量 不等式情況下 當(dāng) 引入松弛變量s當(dāng) 引入剩余變量s松弛變量 需要補(bǔ)充的資源剩余變量 沒有使用的資源如果原問題中有若干個(gè)非等式約束 則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時(shí) 必須對(duì)各個(gè)約束引進(jìn)不同的松弛變量 3 右端項(xiàng)有負(fù)值的問題 在標(biāo)準(zhǔn)形式中 要求右端項(xiàng)必須每一個(gè)分量非負(fù) 當(dāng)某一個(gè)右端項(xiàng)系數(shù)為負(fù)時(shí) 如bi 0 則把該等式約束兩端同時(shí)乘以 1 得到 ai1x1 ai2x2 ainxn bi 4 決策變量不定 當(dāng)Xio當(dāng)某一個(gè)變量xj沒有非負(fù)約束時(shí) 可以令xj xj xj 其中xj 0 xj 0即用兩個(gè)非負(fù)變量之差來表示一個(gè)無符號(hào)限制的變量 當(dāng)然xj的符號(hào)取決于xj 和xj 的大小 例 將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式Minf 2x1 3x2 4x3s t 3x1 4x2 5x3 62x1 x3 8x1 x2 x3 9x1 x2 x3 0 解 首先 將目標(biāo)函數(shù)轉(zhuǎn)換成極大化 令z f 2x1 3x2 4x3其次考慮約束 有2個(gè)不等式約束 引進(jìn)松弛變量x4 和剩余變量x5 0 第三個(gè)約束條件的右端值為負(fù) 在等式兩邊同時(shí)乘 1 通過以上變換 可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問題 Maxz 2x1 3x2 4x3s t 3x1 4x2 5x3 x4 62x1 x3 x5 8 x1 x2 x3 9x1 x2 x3 x4 x5 0 練習(xí) P24習(xí)題3 1 和 2 作業(yè) P24習(xí)題3 3 二 線性規(guī)劃問題的解 1 解的情況2 幾個(gè)重要的解概念 1 解的情況 1 存在有限最優(yōu)解 a 唯一最優(yōu)解b 無窮多個(gè)最優(yōu)解 2 不存在最優(yōu)解a 無有限最優(yōu)解 無界解 b 無可行解 可行域空 判斷題 線性規(guī)劃問題無有限最優(yōu)解的充要條件是可行域?yàn)榭?2 幾個(gè)重要的解概念 1 可行解 可行域 最優(yōu)解 最優(yōu)值 2 基 基本解 3 基本可行解 基可行解 4 可行基 1 可行解 可行域 最優(yōu)解 最優(yōu)值 滿足約束條件 1 2 1 3 式的解X x1 x2 xn T 稱為線性規(guī)劃問題的可行解 其中使目標(biāo)函數(shù)達(dá)到最大值的可行解稱為最優(yōu)解 由可行解組成的集合就是可行域 滿足約束條件不等式所有點(diǎn)組成的集合 將最優(yōu)解代目標(biāo)函數(shù)得到的函數(shù)值就是最優(yōu)值 例 Maxz 1500 x1 2500 x2s t 3x1 2x2 652x1 x2 403x2 75x1 x2 0 2 基 基本解 設(shè)B為A中的一個(gè)基 令A(yù)x b 中所有的非基變量 n m個(gè) 為0 得出的解x 稱為是B的基本解 x1x2x3x4x5bi321006521010400300175P1P2P3P4P5A P1 P2 P3 P4 P5 B P1 P2 P3 基變量 x3x4x5 非基變量 x1x2 B的基本解是 0 0 65 40 70 3 基本可行解 1 滿足非負(fù)的基本解 為基本可行解 2 可行解滿足的條件是 Ax b和x 0 而基本解必然滿足Ax b 只需滿足X 0 4 可行基 對(duì)應(yīng)于基可行解的基 稱為可行基 基本解數(shù)目最多是Cnm個(gè) 一般基可行解的數(shù)目要小于基本解的數(shù)目 當(dāng)基本解中的非零分量的個(gè)數(shù)小于m時(shí) 該基本解是退化解 練習(xí) P96例題1作業(yè) P96例題2 1 找出所有基本解 并指出哪些是基本可行解 1 基本概念2 基本定理3 幾何意義 三 線性規(guī)劃問題的幾何意義 三 線性規(guī)劃問題的幾何意義 1 基本概念 1 凸集 2 頂點(diǎn) 1 凸集定義 設(shè)K是n維歐氏空間的一點(diǎn)集 若任意兩點(diǎn)X 1 K X 2 K的連線上的所有點(diǎn) X 1 1 X 2 K 0 1 則稱K為凸集 任何兩個(gè)凸集的交集是凸集 2 頂點(diǎn)設(shè)K是凸集 X K 若X不能用不同的兩點(diǎn)X 1 K和X 2 K的線性組合表示為X X 1 1 X 2 0 1 則稱X為K的一個(gè)頂點(diǎn) 或極點(diǎn) 2 基本定理定理1 若線性規(guī)劃問題有可行域 則可行域必為凸集 定理2 線性規(guī)劃問題的基可行解X對(duì)應(yīng)于可行域D的頂點(diǎn) 定理3 若可行域有界 則最優(yōu)解一定在頂點(diǎn)上達(dá)到 定理的意義 定理1 可行域是凸集 定理2 基本可行解對(duì)應(yīng)頂點(diǎn) 定理3 最優(yōu)解在頂點(diǎn)上找 幾何意義的作用 線性規(guī)劃問題的所有可行解構(gòu)成的集合是凸集 也可能為無界域 它們有有限個(gè)頂點(diǎn) 線性規(guī)劃問題的每個(gè)基可行解對(duì)應(yīng)可行域的一個(gè)頂點(diǎn) 若線性規(guī)劃問題有最優(yōu)解 必在某頂點(diǎn)上