單純形法小結(jié)

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

單純形法小結(jié)

目標函數(shù)單純形法計算步驟框圖單純形法小結(jié)

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

6bcd10

1-13e01

a-1200

fg2-11/204hi11/210-7jkl

6bcd10

1-13e01

a-1200

fg2-11/204hi11/210-7jkLb=2102c/2=2c=44d/2=-1d=-2-2-2a-1=-7a=33350g=1h=01=-1+ee=225-3/2解：二、LP問題maxz=CX,AX=b，X≥0，如是該問題的最優(yōu)解，又為某一常數(shù)，分別討論下列情況時最優(yōu)解的變化。（1）目標函數(shù)變?yōu)椋?）目標函數(shù)變?yōu)椋?）目標函數(shù)變?yōu)榧s束條件變?yōu)榻猓海╝）仍為最優(yōu)解，；（b）一般不再是問題的最優(yōu)解。（c）最優(yōu)解變?yōu)?，目標函?shù)值不變。

三、考慮LP問題，分別用大M法和兩階段法求解

大M法，第一步轉(zhuǎn)化成標準型：

第二步建表：

兩階段法：

化成標準型：

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

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

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）1221k=-5/2k=-3/4o

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

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