运筹学作业1

某企业计划开办五家商店，企业决策由3家建筑公司承建，每家建筑公司可承建最多两个商店。已知各建筑公司建造各个商店的成本（万元）。决策问题：该企业选择建筑公司，可使成本最少。 商店公司 A1 A2 A3 B1 4 7 6 B2 8 9 9 B3 7 17 12 B4 15 14 8 B5 12 10 7 B1B2B3B4B5

A14871512解：反映成本的效率矩阵为：A2 79171410 A3691287

由于每家建筑公司最多可承建两个商店，因此把每家建筑公司化作相同的两家（Ai和Ai’，i=1、2、3），上面的效率矩阵就有六列五行，为了使“人”和“事”的数目相同，引入一件虚事，使之成为标准化指派问题的效率矩阵，这样便得到了如下矩阵：

B1 B2 B3 B4 B5 B6 B1 B2 B3 B4 B5 B6

44776688999977171712121515141488121210107700000000A1'3A23A2' (每列减列中最小值） 2A3A3'2A1750A100750A1'110630A2110630A2'

15000A315000A3'00

(3、4行减1）

B1 B2 B3 B4 B5 B6 B1 B2 B3 B4 B5 B6

002 22200750075095209521500150000110000A1'2A22A2'（第6列加1） 2A3A3'2A100751A100751A1'09520A209520A2'

15001A315001A3'

覆盖所有零元素的最少数直线数为6.可以确定最有解，有：

B1B2B3B4B5

A11010001000A2

A300011由此得出A1承建B1和B3；A2承建B2；A3承建B4和B5，总成本=4+7+9+8+7=35（万

元）