線性規(guī)劃運輸問題(編輯修改稿)
2025-08-17 11:54 本頁面
【文章內(nèi)容簡介】 回路，而且一般情況下基變量的個數(shù)恰為m+n1個（退化的情況基變量可能少于m+n1，），而且基變量位于每一行每一列，因而得到的是一個基礎可行解。西北角法的缺點是在安排運量時不考慮運價，因而得到的初始解可能離開最優(yōu)解比較遠。以上例子中用西北角法得到的初始解的目標函數(shù)值為z=Σcijxij=10180。15+11180。15+12180。5+16180。31+9180。9+10180。50+13180。25=1777 最小元素法這種方法是按運價由小到大的順序安排運量。先從各運價中找到最小運價，設為cij，然后比較供應量si和需求量dj，如果sidj，取xij=dj，并將發(fā)地i的供應量改為sidj，將收地j的需求量改為0；如果sidj，取xij=si，并將發(fā)地i的供應量改為0，將收地j的需求量改為djsi；如果si和dj中有一個為0，則不分配運量給xij。分配完最小運價的運量后，用同樣的方法分配運價次小的運量，依次類推，直到每一個發(fā)地的供應量和每一個收地的需求量都為0。以下是用最小元素法確定運輸問題的初始可行解的例子。 給出運輸表如下。最小運價為c33=7，發(fā)地3的供應量為50，收地3的需求量為31，安排運量x33=31。發(fā)地3和收地3的供應量和需求量分別變?yōu)?9和0。1234110119153021312169453118710503131414131213251520313184對于c32=8，發(fā)地3的供應量為19，收地2的需求量為20，安排x32=19，發(fā)地3的供應量為0，收地2的需求量為1。12341101191530213121694531187101919193141413121325152019084對于c13=9，c24=9，可以任選一個，但是（1，3）中收地3的需求量為0，安排x24=45，發(fā)地2的供應量為0，收地4的需求量為39。12341101191530213121694545453118710019314141312132515108445對于c11=10和c34=10，由于發(fā)地3的需求量已經(jīng)為0，安排x11=15，發(fā)地1的供應量為15，收地1的需求量為0；123411011915301515213121690453118710019314141312132515151039對于c12=11，安排x12=1，發(fā)地1的供應量為14，收地2的需求量為0；1234110119151511512131216904531187100193141413121325011039對于c44=13，安排x44=25，發(fā)地4的供應量為0，收地4的需求量為14。12341101191514151213121690453118710019314141312132525250003925最后安排x14=14，所有發(fā)地和收地的供應量、需求量都等于0。1234110119151414=015114213121690453118710019314141312130250001414=0這樣就得到一個運輸問題的初始基礎可行解。這個初始基礎可行解的目標函數(shù)值為z=10180。15+11180。1+15180。14+9180。45+8180。19+7180。31+13180。25=1470比用西北角法得到的初始基礎可行解的目標函數(shù)值小。 計算非基變量的檢驗數(shù)zijcij對于非基變量xij，檢驗數(shù)為其中向量Yij可由該非基變量與基變量形成的閉回路來確定，這個閉回路轉(zhuǎn)角處的基變量對應于y=177。1，其余的基變量對應于y=0。這樣就等于轉(zhuǎn)角處基變量對應的cij依次加減的值。 ，用西北角法得到初始基礎可行解，計算各非基變量的檢驗數(shù)zijcij1234110119153015152131216945531931187105050414131213252515203184非基變量（1，3）相應的閉回路為1234+6110119153015152131216945531931187105050414131213252515203184因此x13的檢驗數(shù) z13c13=(c12c22+c23)c13=(1112+16)9=+6。非基變量（1，4）相應的閉回路為12347110119153015152131216945531931187105050414131213252515203184因此x14的檢驗數(shù) z14c14=(c12c22+c24)c14=(1112+9)15=7非基變量（2，1）相應的閉回路為12341101191530151522131216945531931187105050414131213252515203184因此x21的檢驗數(shù) z21c21=(c11c12+c22)c21=(1011+12)13=2非基變量（3，1）相應的閉回路為12341101191530151521312169455319+131187105050414131213252515203184因此x31的檢驗數(shù)z31c31=(c11c12+c22c24+c34)c31=(1011+129+10)11=+1用同樣的方法可以求得其他非基變量的檢驗數(shù)z32c32=(c22c24+c34)c32=(129+10)8=+5z33c33=(c23c24+c34)c33=(169+10)7=+10z41c41=(c11c12+c23c24+c44)c41=(1011+129+13)14=+1z42c42=(c22c24+c44)c42=(129+13)13=+3z43c43=(c23c24+c44)c43=(169+13)12=+8將以上檢驗數(shù)填入運輸表，用“○”表示。1234+3+1+1+82+6+571101191530151521312169455319+1031187105050414131213252515203184對用最小元素法得到的初始基礎可行解，也可以用同樣的方法求得各非基變量的檢驗數(shù)zijcij，計算過程略，計算結(jié)果見下表。123497124+2644+1111101191530151142131216945
黨政相關相關推薦
鄂ICP備17016276號-1