單純形法小結(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）對照指出單純形表中的各基本可行解對應圖解法中可行域的哪一頂點。續(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