高级运筹学第6章new.pptVIP

§5匈牙利法（16）为了确定完全分配分案，对上述第⑦步得到的新的费用矩阵，重复制定分配方案。具体说：于是一个完全的最优分配方案制定出来了。即分配如下：甲完成C乙完成B丙完成D丁完成A总费用为9+4+11+4=28（这亦可从变换中从每行（列）减去或加上的数值之代数和求得）。蒙特卡洛法（随机取样法）（1）由于整数解是有限个，于是为枚举法提供了方便。当然，当自变量维数很大和取值范围很宽情况下，企图用显枚举法（即穷举法）计算出最优值是不现实的，但是应用概率理论可以证明，在一定的计算量的情况下，完全可以得出一个满意解。[例6-9]已知非线性纯整数规划为：maxP=0≤xi≤99(i=1,…,5)?蒙特卡洛法（随机取样法）（2）x1+x2+x3+x4+x5≤400x1+2x2+2x3+x4+6x5≤8002x1+x2+6x3≤200x3+x4+5x5≤200对该题，目前尚无有效方法求出准确解。如果用显枚举法试探，共需计算(100)5=1010个点，其计算量非常之大。然而应用蒙特卡洛法去随机计算106个点，便可找到满意解。蒙特卡洛法（随机取样法）（3）当然，用计算机来计算106个标本点需花很长时间，然而，在微机日益普及的今天，这种矛盾日趋缓和。从国外一些国家的应用看，该法愈来愈显出其优越性，有广泛的发展前途。§6整数规划的应用(1)一、投资场所的选择例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置Aj(j＝1，2，3，…，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：在东区由A1，A2，A3三个点至多选择两个；在西区由A4，A5两个点中至少选一个；在南区由A6，A7两个点中至少选一个；在北区由A8，A9，A10三个点中至少选两个。Aj各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见右表所示(单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?解：设：0--1变量xi=1(Ai点被选用）或0(Ai点没被选用）。这样我们可建立如下的数学模型：Maxz=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10s.t.100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10≤720x1+x2+x3≤2x4+x5≥1x6+x7≥1x8+x9+x10≥2xj≥0xj为0--1变量，i=1,2,3,……,10二、固定成本问题例5．高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如右表所示。不考虑固定费用，每种容器售出一只所得的利润分别为4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人月，机器有100台月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为150万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。解：这是一个整数规划的问题。设x1，x2，x3分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设yi=1(当生产第i种容器,即xi＞0时)或0（当不生产第i种容器即xi=0时）引入约束xi≤Myi，i=1，2，3，M充分大，以保证当yi=0时，xi=0。这样我们可建立如下的数学模型：Maxz=4x1+5x2+6x3-100y1-150y2-200y3s.t.2x1+4x2+8x3≤5002x1+3x2+4x3≤300x1+2x2+3x3≤100xi≤Myi，i=1，2，