整数规划模型

在许多线性规划模型中，变量取整数时才有意义.例如不可分解产品的数目，如汽车、房屋、飞机等，或只能用整数来记数的对象.这样的线性规划称为整数线性规划，简称整数规划，记为IP.整数规划分为两类：一类为纯整数规划，记为PIP，它要求问题中的全部变量都取整数；另一类是混合整数规划，记为MIP，它的某些变量只能取整数，而其他变量则为连续变量.整数规划的特殊情况是0－1规划，其变量只取0或者1.

例5-6　最佳组队问题

有一场由四个项目（高低杠、平衡木、跳马、自由体操）组成的女子体操团体赛，赛程规定：每个队至多允许10名运动员参赛，每一个项目可以有6名选手参加.每个选手参赛的成绩评分从高到低依次为：10至0.每个代表队的总分是参赛选手所得总分之和，总分最多的代表队为优胜者.此外，还规定每个运动员只能参加全能比赛（四项全参加）与单项比赛这两类中的一类，参加单项比赛的每个运动员至多只能参加三项单项.每个队应有4人参加全能比赛，其余运动员参加单项比赛.现某代表队的教练已经对其所带领的10名运动员参加各个项目的成绩进行了大量测试，教练发现每个运动员在每个单项上的成绩得分期望值如表5-5所示.请建立模型为该队排出一个出场阵容，使该队团体总分尽可能高.

表5-5　运动员各项目得分及概率分布表

【解题思路】

在解决问题时根据题目要求需要引入两个参变量X_ij和Q_i；

通过对题目的数学翻译，将每个约束用数学表达式形式呈现.每个队应有4人参加全能比赛.即每个队参加全能比赛的人有且仅有4名，.参加单项比赛的每个运动员至多参加三项单项，即不参加全能比赛的运动员最多只能参加三个单项，.参加全能比赛的选手要四项全参加，即.每个项目可以有6名选手参加，即每个项目的参赛选手不能超过6名，得.

E_ij表示表5-5中第i为运动员在第j项运动中的期望得分，当运队员i入选项目j时，E_ijX_ij表示她在该项目得分的期望值.于是该队团体总分可表示为，这就是在均值情况下该问题的目标函数，这个问题的0-1规划模型可写作：

用数学软件Lingo进行求解，得到结果为：Q₂=Q₈=Q₉=Q₁₀=1，X₁₃=X₃₄=X₄₂=X₄₃=X₅₂=X₅₄=X₆₁=X₇₁=1.即表示队员2，8，9，10参加全能比赛，队员1参加了项目3（跳马）的比赛，队员3参加了项目4（自由体操）的比赛，队员4参加了项目2（平衡木）和项目3（跳马）的比赛，队员5参加了项目2（平衡木）和项目4（自由体操）的比赛，队员6参加了项目1（高低杠）的比赛，队员7参加了项目1（高低杠）的比赛.以此阵容出赛能使该团队总分最高为224.7分，见表5-6.

表5-6　均值估计下的最佳阵容

例5-7　DVD在线租赁问题——CUMCM2005

随着信息时代的到来，网络成为人们生活中越来越不可或缺的元素之一.许多网站利用其强大的资源和知名度，面向其会员群提供日益专业化和便捷化的服务.例如，音像制品的在线租赁就是一种可行的服务.这项服务充分发挥了网络的诸多优势，包括传播范围广泛、直达核心消费群、强烈的互动性、感官性强、成本相对低廉等，为顾客提供更为周到的服务.

考虑如下的在线DVD租赁问题.顾客缴纳一定数量的月费成为会员，订购DVD租赁服务.会员对哪些DVD有兴趣，只要在线提交订单，网站就会通过快递的方式尽可能满足要求.会员提交的订单包括多张DVD，这些DVD是基于其偏爱程度排序的.网站会根据手头现有的DVD数量和会员的订单进行分发.每个会员每个月租赁次数不得超过2次，每次获得3张DVD.会员看完3张DVD之后，只需要将DVD放进网站提供的信封里寄回（邮费由网站承担），就可以继续下次租赁.表中列出了网站手上100 种DVD的现有张数和当前需要处理的1000 位会员的在线订单，如何对这些DVD进行分配，才能使会员获得最大的满意度？请具体列出前30位会员（即C0001～C0030）分别获得哪些DVD.

由于题目数据量非常大，本书没有给出该题的数据，而只是针对题目的一部分问题进行分析与讨论.同学们可以登录全国大学生数学建模竞赛网站（http：//www.mcm.edu.cn）下载相关数据.

【解题思路】

该问题是在一定约束条件下的最优化问题.现有100位会员已向网站提供订单，其中每位会员对各种DVD的偏爱程度都有所差异，同时又由于DVD的现有数量有限，无法满足每位会员都看到他们所偏爱的DVD种类.因此，为了兼顾会员和网站双方利益，本文应以满足会员的主观意愿为主，使会员获得最大的满意度，从而形成稳定的消费群体.综上所述，该问题归结为：网站尽量根据每位会员对各种DVD的不同偏爱度，找到一种最佳的分配方案.

网站越能满足会员的偏爱，会员的满意度就会越大，即会员的偏爱度与满意度成正比.又有偏爱度越小表示会员的偏爱程度越高，故会员的满意度β_ij与偏爱值α_ij成反比，即可用如下关系式表示：

其中，α_ij为题中所给的常数矩阵，表示第i位会员对第j种DVD的偏爱值.

该问题的目的就是分配当前的订单，使得这些顾客的满意度最大，可以用0-1规划模型来求解，定义0-1变量C_ij，C_ij为1时表示第i个顾客租到了第j种DVD，其值为0时表示没有租到相应的DVD.

会员租赁DVD满意度的目标函数为：.租赁给会员的每种DVD总张数不能超过现有DVD数量.每位会员每月租赁次数不得超过2次，每次获得3张DVD，则会员只能租到3张或6张DVD.因此.由上述分析得到如下的0-1 规划模型：

其中y_j表示现有DVD数量的限制，对于上述的模型，在用Lingo编程求解，得到分配方案为C_ij.前30 个会员租到DVD的情况如下表5-7所示.

表5-7　DVD分配表

在上述章节中介绍了线性规划的内容，但是线性规划建模有其局限性：线性规划要求所求解的问题必须满足全部的约束，而实际问题中并非所有约束都需要严格的满足；线性规划只能处理单目标的优化问题，而对一些次目标只能转化为约束处理.而在实际问题中，目标和约束是可以相互转化的，处理时不一定要严格区分；线性规划寻求最优解，而许多实际问题只需要找到满意解就可以了.为此将介绍目标规划模型与多目标规划模型以弥补线性规划的缺陷.