第三節(jié)用單純形法求解

第三節(jié)用單純形法求解1第1頁，課件共10頁，創(chuàng)作于2023年2月◆解目標規(guī)劃問題的單純形法計算步驟

(1)建立初始單純形表。表中檢驗數(shù)行按優(yōu)先因子個數(shù)分別列成K行。當不含絕對約束時，di-(i=1,2,…,K)構(gòu)成了一組基本可行解,其系數(shù)列向量構(gòu)成一個基。列出初始單純形表。置k=1；第2頁，課件共10頁，創(chuàng)作于2023年2月(2)確定換入變量。檢查當前第k行中是否存在小于0，且對應前k-1行的同列檢驗數(shù)為零的檢驗數(shù)。若有，則取其中最小者對應變量為換入變量，轉(zhuǎn)(3)。若無這樣的檢驗數(shù)，則轉(zhuǎn)(5)；第3頁，課件共10頁，創(chuàng)作于2023年2月(3)確定換出變量。按單純形法中的最小比值規(guī)則確定換出變量，當存在兩個和兩個以上相同的最小比值時，選取具有較高優(yōu)先級別的變量為換出變量，轉(zhuǎn)(4)；第4頁，課件共10頁，創(chuàng)作于2023年2月(4)按照單純形法進行基變換運算(行初等變換運算)，換入變量替換換出變量，建立新的單純形表，返回(2)；

(5)當k=K

時，計算結(jié)束。表中的解即為滿意解。否則置k=k+1，返回(2)。

第5頁，課件共10頁，創(chuàng)作于2023年2月例3：用單純形法求解下述目標規(guī)劃問題：第6頁，課件共10頁，創(chuàng)作于2023年2月解：步1，以d1-、d2-、d3-為基變量列出初始單純形表見表5-1。步2，確定換入變量。x1為換入變量。步3，確定換出變量。d1-為換出變量。步4，進行迭代運算。得到表5-2。步5，重復步2到步4的運算得到表5-3。第7頁，課件共10頁，創(chuàng)作于2023年2月cj→00P100P1P20CB基b

x1x2d1-d1+

d2-

d2+

d3-

d3+

P1

d1-

100d2-

40P2

d3-

100[1]01-1211-1321-1cj-zjP1-111P2-3-21表5-1第8頁，課件共10頁，創(chuàng)作于2023年2月表5-2cj→00P100P1P20CB基b

x1x2d1-d1+

d2-

d2+

d3-

d3+

0x1

100d2-

20P2

d3-

70101-11-2[2]1-12-331-1cj-zjP111P2-23-31第9頁，課件共10頁，創(chuàng)作于2023年2月表5-3cj→00P100P1P20CB基b

x1x2d1-d1+

d2-

d2+

d3-

d3+

0x1

200d1-

10P2

d3-

4011/21/2-1/2[1/2]-111/2-1/21/2-3/23/21-1cj-zjP111P2-1/2-3/210x1

200x210P2

d3-

4011-11-221-11-1-221-1cj-zj