目標(biāo)規(guī)劃單純形法1

1、§4.3 解目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)與線性規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)形式上沒(méi)有本質(zhì)的區(qū)別，所以也可用單純形法求解目標(biāo)規(guī)劃模型。但須注意：（1）因目標(biāo)規(guī)劃問(wèn)題的目標(biāo)函數(shù)都是最小化，所以要達(dá)到最優(yōu)，應(yīng)該所有檢驗(yàn)數(shù) ；（2）因非基變量的檢驗(yàn)數(shù)中含有不同等級(jí)的優(yōu)先因子，故檢驗(yàn)時(shí)須優(yōu)先考察前一級(jí)的檢驗(yàn)數(shù)，在迭代中，要保證不使得上一級(jí)的目標(biāo)變差。解目標(biāo)規(guī)劃的單純形法的計(jì)算步驟：1.建立初始單純形表，在表中將檢驗(yàn)數(shù)行按優(yōu)先因子個(gè)數(shù)分別列成K行，置k=1;2.檢查該行中是否存在負(fù)數(shù)，且對(duì)應(yīng)的前k-1行的檢驗(yàn)數(shù)為零，若是，取其中最小者對(duì)應(yīng)的變量為換入變量，轉(zhuǎn)3，否則轉(zhuǎn)5；3.按最小比值規(guī)則確定

2、換出變量，當(dāng)存在兩個(gè)或兩個(gè)以上相同的最小比值時(shí)，選取具有較高級(jí)別的變量為換出變量；4.按單純形法進(jìn)行基變換迭代運(yùn)算，得新的單純形表，返回2；5.當(dāng)k=K時(shí)，計(jì)算結(jié)束。否則置k=k+1,返回2。例 試用單純形法求解目標(biāo)規(guī)劃解 取為初始基變量，可列出初始單純形表（表1）： 表1選定換入變量為,換出變量為，從而主元素為2，進(jìn)行基變換得（表2）： 表2由于表2中行檢驗(yàn)數(shù)均非負(fù)，故對(duì)第一，第二級(jí)目標(biāo)均優(yōu)化完畢。因行檢驗(yàn)數(shù)中有負(fù)數(shù)，故還需優(yōu)化第三級(jí)目標(biāo)。注意：在行檢驗(yàn)數(shù)中的檢驗(yàn)數(shù)為最小，似應(yīng)將作為換入變量，但由于其上一行對(duì)應(yīng)的檢驗(yàn)數(shù)為1，非零，從而若將引入基變量，必將使第二優(yōu)先級(jí)目標(biāo)變差，因此確定為換入變量，再按最小比值原則定為換出變量，于是為主元素，進(jìn)行基變換得（表3） 表3表3中所有檢驗(yàn)數(shù)均非負(fù)，因此給出了問(wèn)題的滿意解，.檢查表3的檢驗(yàn)數(shù)行，發(fā)現(xiàn)非基變量的檢驗(yàn)數(shù)為0，這表示存在多重解。在表3中以為換入變量，為換出變量，迭代可