第11講整數規劃(二)

——指派問題浙江工業大學經貿管理學院曹柬一、指派問題的概念運籌學第11講：整數規劃(二)例1(習題5-2)甲、乙、丙、丁四人加工A、B、C、D四種工件所需時間如表所示。問應指派何人加工何種工件，使總的加工時間最少？

工件工人ABCD甲14111317乙9729丙491015丁1510513在實際問題中，cij可表示費用、時間、距離等。為方便購物，規劃任一居民小區至其中一個連鎖店的距離不超過800m。第11講整數規劃(二)

——指派問題一般稱C=(cij)n×n為指派問題的系數矩陣。xa+xb+xc+xh+xi>=1ACEGHI一般稱C=(cij)n×n為指派問題的系數矩陣。運籌學第11講：整數規劃(二)例2(P143-例12)運籌學第11講：整數規劃(二)運籌學第11講：整數規劃(二)xa+xc+xe+xg>=1在實際問題中，cij可表示費用、時間、距離等。運籌學第11講：整數規劃(二)運籌學第11講：整數規劃(二)ACEGHIxd+xf+xj+xk+xl>=1指派問題的標準形式(以人和事為例)是：有n個人和n件事，已知第i人做第j事的付出為cij(i,j=1,2,…,n)，要求確定人與事之間的一一對應的指派方案，使完成這n件事的總付出最小。一般稱C=(cij

)n×n為指派問題的系數矩陣。在實際問題中，cij

可表示費用、時間、距離等。為建立標準指派問題的數學模型，引入n2個0-1變量：指派問題有個可行解n!二、指派問題的標準形式運籌學第11講：整數規劃(二)運籌學第11講：整數規劃(二)運籌學第11講：整數規劃(二)Bj已知建筑公司Ai對新商店Bj的建造費用報價如下表所示。二、指派問題的標準形式例2(P143-例12)minxa+xb+xc+xd+xe+xf+xg+xh+xi+xj+xk+xl某商業公司計劃開辦5家新商店，為盡快建成營業，公司決定由5家建筑公司分別承建。xf+xg+xk>=1已知建筑公司Ai對新商店Bj的建造費用報價如下表所示。例2(P143-例12)表中的元素表示4人完成3項任務的利潤，“/”表示不勝任。若人數和任務數不同，即C非方陣，可添加虛擬的人或任務，取系數為0指派問題標準形式的特點模型為min型

系數矩陣C為方陣

系數cij≥0運籌學第11講：整數規劃(二)三、匈牙利法運籌學第11講：整數規劃(二)(以習題5-2為例)甲、乙、丙、丁四人加工A、B、C、D四種工件所需時間如表所示。問應指派何人加工何種工件，使總的加工時間最少？

工件工人ABCD甲14111317乙9729丙491015丁1510513運籌學第11講：整數規劃(二)某商業公司計劃開辦5家新商店，為盡快建成營業，公司決定由5家建筑公司分別承建。已知建筑公司Ai對新商店Bj的建造費用報價如下表所示。問商業公司應對5家建筑公司如何分配建造任務，使得總建造費用最小？

BjAiB1B2B3B4B5A14871512A279171410A3691287A46714610A56912106例2(P143-例12)四、非標準形式指派問題的求解若為max型，可用C中最大元素分別減去C中每一元素若人數和任務數不同，即C非方陣，可添加虛擬的人或任務，取系數為0

一個人做幾項任務，可將該人化為幾個人；反之亦然某任務不能由某人做，取系數為M運籌學第11講：整數規劃(二)運籌學第11講：整數規劃(二)某商業公司計劃開辦5家新商店，公司決定由3家建筑公司分別承建，允許每家建筑公司承建一家或二家商店。已知建筑公司Ai對新商店Bj的建造費用報價如下表所示。求使總費用最小的指派方案。

BjAiB1B2B3B4B5A14871512A279171410A3691287例3(P147-例13)采用匈牙利法求得：A1承建B1和B3，A2承建B2，A3承建B4和B5，總造價為35萬元。作業：習題5-3，習題5-4思考：案例7例4甲乙丙丁A32-21B2-20/C/-110表中的元素表示4人完成3項任務的利潤，“/”表示不勝任。由于精力所限，每人只能承擔一項任務，求使總利潤最大的指派方案。運籌學第11講：整數規劃(二)Bj該小區800m半徑內的各小區問商業公司應對5家建筑公司如何分配建造任務，使得總建造費用最小？運籌學第11講：整數規劃(二)一般稱C=(cij)n×n為指派問題的系數矩陣。四、非標準形式指派問題的求解例2(P143-例12)甲、乙、丙、丁四人加工A、B、C、D四種工件所需時間如表所示。xf+xj+xk+xl>=1運籌學第11講：整數規劃(二)二、指派問題的標準形式系數矩陣C為方陣為方便購物，規劃任一居民小區至其中一個連鎖店的距離不超過800m。一般稱C=(cij)n×n為指派問題的系數矩陣。表中的元素表示4人完成3項任務的利潤，“/”表示不勝任。ACEGHI便民超市準備在城市西北郊新建的居民小區中開設若干連鎖店。為方便購物，規劃任一居民小區至其中一個連鎖店的距離不超過800m。下表給出了新建的居民小區及離該居民小區半徑800m內的各個小區，問該超市最少應在上述小區中建多少個連鎖店及建于哪些小區內。例5(習題5-7)小區代號該小區800m半徑內的各小區AACEGHIBBHICACGHIDDJEAEGFFJKGACEGHABCHIIABCHIJDFJKLKFJKLLJKLminxa+xb+xc+xd+xe+xf+xg+xh+xi+xj+xk+xlstxa+xc+xe+xg+xh+xi>=1xb+xg+xi>=1xa+xc+xg+xh+xi>=1xd+