04第四章線性規(guī)劃的求解法-文庫(kù)吧資料
2025-05-21 01:19本頁(yè)面
【正文】 0102110100111000100300000110為了滿足單純形法的第三個(gè)特點(diǎn)：底行相應(yīng)于單位子塊位置的元素為0，對(duì)上表做初等變換，使所對(duì)應(yīng)的底行單位子塊位置的元素為0。 用兩階段法求下列線性規(guī)劃問(wèn)題的最優(yōu)解： （）先引進(jìn)松弛變量，把問(wèn)題化為標(biāo)準(zhǔn)形式。應(yīng)當(dāng)指出，為替換出基變量中的人工變量而采用的主元消去法，并不要求遵守單純形法確定的離基進(jìn)基變量的規(guī)則。且的分量都是非基變量，這時(shí)m個(gè)基變量都是原來(lái)的變量，又知： 是線性規(guī)劃（）的基本可行解，因此，是線性規(guī)劃（）的一個(gè)基本可行解。設(shè)最優(yōu)基本可行解是，這時(shí)有三種情況。 （）其中是分量全是1的m維列向量，是人工變量構(gòu)成的m維列向量。而人工變量的引進(jìn)，改變了原來(lái)的約束條件，從這個(gè)意義上講，它們是“不合法”的變量。也就是說(shuō)，在此可行解處，原來(lái)的約束是嚴(yán)格不等式成立還是等式成立的區(qū)別。松弛變量的作用是把不等式約束改寫為等式約束，改寫前后的兩個(gè)問(wèn)題是等價(jià)的。向量是人為引進(jìn)的，它的每個(gè)分量稱為人工變量。設(shè)中不包含階單位矩陣，為了使約束方程的系數(shù)矩陣中含有階單位矩陣，把每一個(gè)方程增加一個(gè)非負(fù)變量，令 （）即 （）顯然 是（）的一個(gè)基本可行解。若中不包含階單位矩陣，則可從兩階段法入手，先求得一個(gè)初始基本可行解。若中含有階單位矩陣，則初始基本可行解立即可得。 兩階段法的原理使用單純形方法，需要給定一個(gè)初始基本可行解，以便從這個(gè)基本可行解出發(fā)，求改進(jìn)的基本可行解，最終達(dá)到最優(yōu)解。把引進(jìn)的自由變量略去，則最優(yōu)解為，最優(yōu)值為。本例中把表改為：323106121014312MM0通過(guò)運(yùn)算使它具備第三個(gè)特點(diǎn)：底行相應(yīng)于單位子塊位置的元素為0，然后再嚴(yán)格按照單純形法的步驟求解：③2310612101434M*12+2M0010M12/311/30208/3②1/3120*0由于M為足夠大的正數(shù)，所以34M應(yīng)視為負(fù)數(shù)，故選它。只要不為零，就一定為正數(shù)，于是目標(biāo)函數(shù)的值就會(huì)增加它們和的M倍。 以上途徑通過(guò)修改（）的目標(biāo)函數(shù)來(lái)實(shí)現(xiàn)。如下例所述： （）列成表格：3236121431203236
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1