资源描述：
《运筹学概论第5章整数规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第5章整数规划在求解线性规划问题时，得到的最优解可能是分数或小数，但许多实际问题要求得到的解为整数才行。这种要求线性规划有整数解的问题,称为整数规划(IntegerProgramming)或简称IP。第一节整数规划的数学模型及解的特点引例某厂拟用火车装运甲、乙两种货物集装箱，每箱的体积、重量、可获利润以及装运所受限制如下：货物集装箱体积(米3)重量(百斤)利润(百元)甲5220乙4510托运限制2413问两种货物各装运多少箱，可使获得利润最大？此例可解得x1=4.8,x2=0，凑整为x1=5,x2=0，这就破坏了条件(2)
2、，因而不是可行解；如截断小数变为x1=4,x2=0，这当然满足所有约束条件，但不是最优解，因为对x1=4,x2=0有z＝80，而对x1=4,x2=1（也是可行解）有z＝90。因此要专门研究整数规划的解法。设甲、乙两种货物装运箱数分别为x1和x2。显然，x1、x2都要求为整数,于是可建立整数规划模型如下：Maxz＝20x1+10x2(1)5x1+4x2≤24(2)2x1+5x2≤13(3)x1,x2≥0(4)x1,x2为整数(5)整数规划的数学模型分类：若要求所有xj的解为整数，称为纯整数规划若要求部分xj的解为整数，称为混
3、合整数规划注意几点：对应没有整数解要求的线性规划称之为松弛问题整数规划的解是可数个的，最优解不一定发生在极点整数规划的最优解不会优于其松弛问题的最优解第二节0-1整数规划0-1型整数规划是整数规划的一种特殊形式，它的变量xj仅取值0或1。这种只能取0或1的变量称为0-1变量或二进制变量。下面通过一个例子说明一下：例:篮球队需要选择5名队员组成出场阵容参加比赛。8名队员的身高及擅长位置如下：出场阵容应满足如下条件：（1）只能由一名中锋出场；（2）至少一名后卫；（3）如1号和4号均上场，则6号不出场；（4）2号和8号至少有一个
4、不能出场。问：应选择哪些队员出场，使队员平均身高最高。试建立数学模型。队员12345678身高1.921.901.881.861.851.831.801.78位置中锋中锋前锋前锋前锋后卫后卫后卫建立模型如下所示：引入0-1变量xi（i=1,2,…,7）,令1,当第i个队员被选用,xi=0,当第i个队员没被选用。（i=1,2,…,8)Maxz=(c1x1+c2x2+…+c8x8）/5x1+x2+…+x8=5x1+x2=1x6+x7+x7≥1x2+x8≤1xi=0或1,i=1,2,…,8于是建立下列模型:x1+x4+x6≤2课
5、堂练习某钻井队要从10个可供选择的井位中确定5个钻井探油，使总的钻探费用最少。若10个井位的代号为s1－s10，相应的钻探费用为c1－c10，并且井位选择应满足以下条件：1)s1，s4，s5，s10井位中最多选择两个。2)s2，s8，s9井位中最少选择一个3)如s3和s5都选择，则s8不选择4)s6号和s7井位至少有一个不选择建立该问题的数学模型。第三节指派问题指派问题的标准形式及其数学模型匈牙利解法求解指派问题一般的指派问题有n项任务，恰好n个人承担，第i人完成第j项任务的花费(时间或费用等)为cij，如何指派使总花费最
6、省？一、指派问题的标准形式及其数学模型指派问题的系数矩阵如下：Cij的含义可以不同，如费用、成本、时间等。系数矩阵C中，第i行中各元素表示第i人做各事的费用；第j列各元素表示第j事由各人做的费用。为建立标准指派问题的数学模型，引入n×n个0—1变量：指派问题的数学模型可写成如下页形式：若派第i人做第j事0若不派第i人做第j事（ij=1，2,…，n）第j项工作由一个人做第i人做一项工作指派问题的每个可行解，可用矩阵表示如下：矩阵X中，每行各元素中只有1个元素为1,其余各元素等0；每列各元素中也只有1个元素为1,其余各元素等0
7、。指派问题有n！个可行解。例1有一份中文说明书，需译成英、日、德、俄四种文字。分别记作E、J、G、R。现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种的说明书所需时间如下表。问应指派何人去完成何工作，使所需总时间最少？指派问题的数学模型如下：已知条件可用系数矩阵（效率矩阵）表示为：其可行解也可用每行仅有一个1，每列也仅有一个1的矩阵表示，如：匈牙利解法的关键是利用了指派问题最优解的如下性质：若从指派问题的系数矩阵C的某行（或某列）各元素分别减去一个常数k，得到一个新的矩阵C’，则以C’和C为系数矩阵的两个指派问题有相
8、同的最优解。（系数矩阵的变化并不影响数学模型的约束方程组，而只是目标函数值减少了常数k，所以最优解不变）二、匈牙利法解题步骤1955年，库恩利用匈牙利数学家康尼格的关于矩阵中独立零元素的定理，提出了解指派问题的一种算法，称为匈牙利解法。-2-4-9-7若某行(列)已有0元素，那就不必再减了。例1的计算为
