物流優(yōu)化技術(shù)課件 第3章3.2.2 線性規(guī)劃問題解的基本理論

1、二、二、 線性規(guī)劃問題線性規(guī)劃問題 解的概念和性質(zhì)解的概念和性質(zhì) ：滿足約束條件和非負(fù)條滿足約束條件和非負(fù)條件的決策變量的一組取值。件的決策變量的一組取值。：所有可行解的集合。所有可行解的集合。：LP問題可行解集構(gòu)成問題可行解集構(gòu)成n維維空間的區(qū)域，可以表示為：空間的區(qū)域，可以表示為：0,|XbAXXD4.:使目標(biāo)函數(shù)達(dá)到最優(yōu)值的可行解。使目標(biāo)函數(shù)達(dá)到最優(yōu)值的可行解。5.：最優(yōu)解對應(yīng)目標(biāo)函數(shù)的取值。：最優(yōu)解對應(yīng)目標(biāo)函數(shù)的取值。6.:求出問題的最優(yōu)解和最優(yōu)值。求出問題的最優(yōu)解和最優(yōu)值。7.基本解基本解:令非基變量等于令非基變量等于0，從，從AXb中解出中解出的基變量所得的解稱為的基變量所得的解稱

2、為LP關(guān)于基關(guān)于基B的基本解。的基本解。可行解與基本解的區(qū)別？可行解與基本解的區(qū)別？ 設(shè)設(shè)AX=bAX=b是含是含n n個決策變量、個決策變量、mm個個約束條件的約束條件的LPLP的約束方程組，若的約束方程組，若B B是是LPLP問問題的一個基，若令不與題的一個基，若令不與B B的列相應(yīng)的的列相應(yīng)的n-mn-m個分量（非基變量）都等于零，所得方程個分量（非基變量）都等于零，所得方程組的解組的解X=0,0, ,0,xn-m+1,xn-m+2,xnT稱為稱為，簡稱，簡稱為為。8.9.10.m基本解的個數(shù)基本解的個數(shù)CCn n基本可行解的非零分量均為正分量基本可行解的非零分量均為正分量個數(shù)不超過個數(shù)不超過mm最優(yōu)解基本最優(yōu)解： 線性規(guī)劃問題的可行解集線性規(guī)劃問題的可行解集（即可行域）（即可行域） 是凸集。是凸集。 njjjjxbxPXD10, 線性規(guī)劃幾何理論基本定理線性規(guī)劃幾何理論基本定理若若 ，則則X是是D的一個頂點的充分必要條件是的一個頂點的充分必要條件是X為線為線性規(guī)性規(guī) 劃的基本可行解。劃的基本可行解。njjjjxbxPXD10, 若可行域非空有界，則線性規(guī)劃問若可行域非空有界，則線性規(guī)劃問題的目標(biāo)函數(shù)一定可以在可行域的頂點上題的目標(biāo)函數(shù)一定可以在可行域的頂點上達(dá)到最優(yōu)值。達(dá)到最優(yōu)值。 若目標(biāo)函數(shù)在若目標(biāo)函數(shù)在k個點處達(dá)到最優(yōu)值個點處