某電力公司要沿道路為8個(gè)居民點(diǎn)架設(shè)輸電網(wǎng)絡(luò),連接8個(gè)居民點(diǎn)的道路如下圖所示,其中v1,v2,v3,v4,v5,v6,v7,v8表示8個(gè)居民點(diǎn),圖中的邊表示8個(gè)居民點(diǎn)之間道路,邊上的賦權(quán)數(shù)位這條道路的路長,單位為公里,請?jiān)O(shè)計(jì)一個(gè)輸電網(wǎng)絡(luò),連通這8個(gè)居民點(diǎn),并使總的輸電線長度最短。
燃?xì)夤緶?zhǔn)備在甲、乙兩地沿路鋪設(shè)一條管路,問如何鋪設(shè)使其管路最短?下圖給出了甲乙兩地間的交通圖。權(quán)數(shù)表示兩地間公路的長度(單位:公里)
已知指派問題的效率矩陣如下,試用匈牙利法求出其最優(yōu)指派方案。