對偶理論和靈敏度分析-第1節(jié)

運籌學（第三版）《運籌學》教材編寫組編清華大學出版社

第2章對偶理論和靈敏度分析

第1節(jié)單純形法的矩陣描述

錢頌迪制作對偶理論和靈敏度分析-第1節(jié)共15頁，您現(xiàn)在瀏覽的是第1頁!

第2章對偶理論和靈敏度分析

第1節(jié)單純形法的矩陣描述

第2節(jié)改進單純形法第3節(jié)對偶問題的提出第4節(jié)線性規(guī)劃的對偶理論第5節(jié)對偶問題的經(jīng)濟解釋——影子價格第6節(jié)對偶單純形法第7節(jié)靈敏度分析第8節(jié)*參數(shù)線性規(guī)劃對偶理論和靈敏度分析-第1節(jié)共15頁，您現(xiàn)在瀏覽的是第2頁!

第1節(jié)單純形法的矩陣描述

設線性規(guī)劃問題:目標函數(shù)maxz=CX;約束條件AX≤b;非負條件X≥0對偶理論和靈敏度分析-第1節(jié)共15頁，您現(xiàn)在瀏覽的是第3頁!給這線性規(guī)劃問題的約約束條件加入松弛變量以后，得到標準型：maxz=CX+0Xs;

AX+IXs=b;X，X

s≥0這里I是m×m單位矩陣。

對偶理論和靈敏度分析-第1節(jié)共15頁，您現(xiàn)在瀏覽的是第4頁!將目標函數(shù)的系數(shù)C分為CB，CN

分別對應于基變量XB和非基變量XN。并且記作C=（CB,CN）。兩邊左乘B-1，得到xB+B–1NxN=B–1b

即：xB=B–1b–B-1

NxN

對偶理論和靈敏度分析-第1節(jié)共15頁，您現(xiàn)在瀏覽的是第5頁!令非基變量=0；由上式得到：對偶理論和靈敏度分析-第1節(jié)共15頁，您現(xiàn)在瀏覽的是第6頁!（1）非基變量的系數(shù)表示為：對偶理論和靈敏度分析-第1節(jié)共15頁，您現(xiàn)在瀏覽的是第7頁!（3）單純形表與矩陣表示的關系對偶理論和靈敏度分析-第1節(jié)共15頁，您現(xiàn)在瀏覽的是第8頁!單純形表中的數(shù)據(jù)基變量非基變量等式右邊系數(shù)矩陣檢驗數(shù)對偶理論和靈敏度分析-第1節(jié)共15頁，您現(xiàn)在瀏覽的是第9頁!若以Xs為基變量，并標記成XB

這是將系數(shù)矩陣（A，I）分為（B，N）兩塊。B是基變量的系數(shù)矩陣，N是非基變量的系數(shù)矩陣。決策變量分為：對偶理論和靈敏度分析-第1節(jié)共15頁，您現(xiàn)在瀏覽的是第10頁!因此z=cBxB+cNxN=cBB–1b–cBB–1NxN+cNxN=cBB–1b+(cN－cBB–1N)xN對偶理論和靈敏度分析-第1節(jié)共15頁，您現(xiàn)在瀏覽的是第11頁!一般來說，經(jīng)過迭代運算之后N由兩部分構成：1)原決策變量中非基部分XN12)松弛變量XSz

=cBB–1b+(cN-cBB–1N)xN

=cBB–1b＋(cN1-cBB–1N1)xN1＋

(cS-cBB–1I)xS＝cBB–1b＋(cN1-cBB–1N1)xN1＋

(-cBB–1)xS（2－5）對偶理論和靈敏度分析-第1節(jié)共15頁，您現(xiàn)在瀏覽的是第12頁!（2）Θ規(guī)則表示為：RHS值表示選用>0的分量換入變量的系數(shù)向量對偶理論和靈敏度分析-第1節(jié)共15頁，您現(xiàn)在瀏覽的是第13頁!矩陣關系式：對偶理論和靈敏度分析-第1節(jié)共15頁，您現(xiàn)在瀏