整数规划的数学模型及解的特点

《整数规划的数学模型及解的特点》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、整数规划的数学模型及解的特点整数规划IP(integerprogramming)：在许多规划问题中，如果要求一部分或全部决策变量必须取整数。例如，所求的解是机器的台数、人数、车辆船只数等，这样的规划问题称为整数规划，简记IP。松弛问题(slackproblem)：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若松弛问题是一个线性规化问题，则该整数规划为整数线性规划(integerlinearprogramming)。一、整数线性规划数学模型的一般形式整数线性规划问题可

2、以分为以下几种类型1、纯整数线性规划(pureintegerlinearprogramming)：指全部决策变量都必须取整数值的整数线性规划。有时，也称为全整数规划。2、混合整数线性规划(mixedintegerlinerprogramming)：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。3、0—1型整数线性规划(zero—oneintegerlinerprogramming)：指决策变量只能取值0或1的整数线性规划。1解整数规划问题0—1型整数规划0—1型整数规划是整数规划中

3、的特殊情形，它的变量仅可取值0或1，这时的变量xi称为0—1变量，或称为二进制变量。0—1型整数规划中0—1变量作为逻辑变量(logicalvariable)，常被用来表示系统是否处于某一特定状态，或者决策时是否取某个方案。一、0—1型整数规划的典型应用问题例1：背包问题：一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量和重要性系数如表所示。设登山队员可携带的最大重量为25kg,试选择该队员所应携带的物品。序号1234567物品食品氧气冰镐绳索帐篷照相器材

4、通信设备重量/Kg55261224重要性系数201518148410解：引入0—1变量xi,xi=1表示应携带物品i，,xi=0表示不应携带物品i上述问题就是一个标准的0-1整数规划问题，解得：X*=(1,1,1,1,0,1,1)’Z*=81例2：集合覆盖和布点问题某市消防队布点问题。该市共有6个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15min内赶到现场。据实地测定，各区之间消防车行驶的时间见表，请制定一个布点最少的计划。地区1地区2地区3地区4

5、地区5地区6地区1地区2地区3地区4地区5地区6010162827201002432171016240122721283212015252717271501420102125140解：引入0—1变量xi,xi=1表示在该区设消防站，,xi=0表示不设解得：X*=(0,1,0,1,0,0)’Z*=2二、特殊约束的处理1.矛盾约束：建模时，有时会遇到相互矛盾的约束，而模型只能两者取一或，例如下面两个约束先不等式同向处理，原式可化为：，再引入一个0－1变量y,及一个很大的正数M，y=0时，(5)与(1)相同，(6

6、)自然满足，实际上不起作用y=1时，(6)与(2)相同，(5)自然满足，实际上起作用对于形似，可以用以下一对约束代替约束同向处理，改为引入0—1变量后，2.多中选一的约束模型希望在下列几个约束中，只能有一个约束有效：引入n个0－1整数变量yi,i=1,2,…,n.则上式可改写为：yi=0时，（2）自然满足，此时约束不起作用yi=1时，约束起作用。而和式保证了在0—1整数变量中有一个且也只有一个取值1，其余取0值。若希望有k个约束有效，只需将(3)改为3、某市为方便学生，拟在新建的7个居民小区增设若干所学校。

7、已知各备选校址代号及其能覆盖的居民小区编号如表1所示，问要覆盖所有居民小区至少应建多少所学校？对应的校址代号是哪些？表1备选校址ABCDEF小区编号1，5，71，2，51，3，52，4，53，64，6解：对每一个学校定义一个变量1，当某居民小区可由第j个学校负责＝0，当某居民小区不可由第j个学校负责则对于第1个小区：对于第2个小区：对于第3个小区：对于第4个小区：对于第5个小区：对于第6个小区：对于第7个小区：Minz=解得：=3例2　　有两个相互排斥的约束条件或。为了统一在一个问题中，引入变量，则上述约束

8、条件可改写为：其中是充分大的数。例3　约束条件或可改写为3.1.3关于固定费用的问题（FixedCostProblem）在讨论线性规划时，有些问题是要求使成本为最小。那时总设固定成本为常数，并在线性规划的模型中不必明显列出。但有些固定费用（固定成本）的问题不能用一般线性规划来描述，但可改变为混合整数规划来解决，见下例。例5某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定的生产方式投资高（选购自动化程度