單純形法小結(jié)

基本概念線性規(guī)劃模型三個(gè)要素：決策變量、目標(biāo)函數(shù)、約束條件線性性線性規(guī)劃解的性質(zhì)線性規(guī)劃問題的可行域是凸集。第一頁，共24頁。最優(yōu)解必在頂點(diǎn)上得到。線性規(guī)劃求解方法圖解法單純形法重點(diǎn)掌握內(nèi)容第二頁，共24頁。單純形法小結(jié)一般線性規(guī)劃問題的標(biāo)準(zhǔn)化及初始單純形法表.—變量第三頁，共24頁?！s束條件

單純形法小結(jié)第四頁，共24頁。

目標(biāo)函數(shù)單純形法計(jì)算步驟框圖單純形法小結(jié)第五頁，共24頁。

引進(jìn)松弛變量、人工變量列出初始單純行表計(jì)算非基變量各列檢驗(yàn)數(shù)σj找出最大的正檢驗(yàn)數(shù)σk所有σj≤0基變量中有人工變量某非基變量檢驗(yàn)數(shù)為0唯一最優(yōu)解存在aik>0無可行解無窮多解無界解是是是是否否否否第六頁，共24頁。一、已知某LP的初始單純形表和單純形法迭代的表，求未知數(shù)a~l的值。

6bcd10

1-13e01

a-1200

fg2-11/204h

i11/210-7jkl第七頁，共24頁。

6bcd10

1-13e01

a-1200

fg2-11/204h

i11/210-7jkLb=2102c/2=2c=44d/2=-1d=-2-2-2a-1=-7a=33350g=1h=01=-1+ee=225-3/2解：第八頁，共24頁。二、LP問題maxz=CX,AX=b，X≥0，如是該問題的最優(yōu)解，又為某一常數(shù)，分別討論下列情況時(shí)最優(yōu)解的變化。（1）目標(biāo)函數(shù)變?yōu)椋?）目標(biāo)函數(shù)變?yōu)椋?）目標(biāo)函數(shù)變?yōu)榧s束條件變?yōu)榈诰彭?，?4頁。解：（a）仍為最優(yōu)解，；（b）一般不再是問題的最優(yōu)解。（c）最優(yōu)解變?yōu)?，目?biāo)函數(shù)值不變。

第十頁，共24頁。三、考慮LP問題，分別用大M法和兩階段法求解

第十一頁，共24頁。大M法，第一步轉(zhuǎn)化成標(biāo)準(zhǔn)型：

第二步建表：

第十二頁，共24頁。第十三頁，共24頁。兩階段法：

化成標(biāo)準(zhǔn)型：

第十四頁，共24頁。第十五頁，共24頁。四、已知線性規(guī)劃問題用單純形法求解得最終單純形表如下,表中x4x5為松弛變量試計(jì)算確定c1、c2、c3和b1、b2的值。續(xù)第十六頁，共24頁。解：建立初始單純形表,根據(jù)單純形法的矩陣描述，有由

,解出c1=1.5,c2=2,c3=3及b1=5,b2=5。續(xù)第十七頁，共24頁。五、設(shè)線性規(guī)劃問題（1）分別用圖解法和單純形法求解；（2）對照指出單純形表中的各基本可行解對應(yīng)圖解法中可行域的哪一頂點(diǎn)。續(xù)第十八頁，共24頁。（3）若目標(biāo)函數(shù)變?yōu)橛懻揷、d的值如何變化，使每個(gè)頂點(diǎn)依次使目標(biāo)函數(shù)達(dá)到最優(yōu)。解：化為標(biāo)準(zhǔn)型第十九頁，共24頁。1221最優(yōu)解k=-5/2k=-3/4o第二十頁，共24頁。10500

093410

0

8520110500

021/5014/51-3/5108/512/501/5010-253/2015/14-3/1410110-1/72/700-5/14-25/14O（0，0）第二十一頁，共24頁。1221k=-5/2k=-3/4o第二十二頁，共24頁。

cdc/d最優(yōu)解的頂點(diǎn)

c/d>5/2Q1

c/d=5/2Q1,Q2>0>03/4<c/d<5/2Q2

c/d=3/4Q2,Q3

c/d<3/4Q3=0>0不限Q3>0=0---