某公司有6个建筑工地要开工 每个工地的位置（用平面坐标系a b表示 距离单位：km）及水泥日用量d（t)
已帮助 人
某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：km）及水泥日用量d（t)由下表给出．假设有两个待定的料场，日储量各有20t，从料场到工地之间均有直线道路相连．试建模（无需求解）确定料场位置和供应计划，使总的吨千米数最小。 工地位置（a，b）及水泥日用量d 1 2 3 4 5 6 a 1.25 8.75 0.5 5.75 3 7.25 b 1.25 0.75 4.75 5 6.5 7.25 d 3 5 4 7 6 11
回答
共1条回复-
首先画一个二部图G(V 1 ，V 2 )，其中V 1 ={L 1 ，L 2 ，…，L 6 }，V 2 ={G 1 ，G 2 ，…，G 6 }，当L i 和G j 互为意中人时，在L i 和G j 之间连一条边，见下图。 由图易见，使男女双方都满意且结婚的对数最多的匹配为 L 1 ——G 1 L 4 ——G 2 L 2 ——G 3 L 5 ——G 6 L 3 ——G 4 L 6 ——G 5