第7章整数线性规划

《第7章整数线性规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章整数线性规划本章，我们将讨论这样一类问题，这类问题可以被构建成线性规划的模型，并且其中至少有一个变量是整数。这类问题称作整数线性规划问题。如果在这类问题中，既有整数变量，又有非整数变量，则我们将其称为混合整数线性规划。在应用整数线性规划时，经常要求变量等于0或1，这些变量称为0-1变量或二进制变量。如果所有变量均为0–1变量，我们称此类问题为0–1整数线性规划。整数变量（特别是0-1变量）可以使建模变得十分容易、灵活，从而使得线性规划的应用得到了广泛的普及。例如，专栏8-1介绍了新西兰航空公司如何使用0–1

2、整数规划来有效安排分配该公司的员工。专栏8-2中介绍了金属谷容器公司（VMC）如何通过混合整数规划来安排公司的啤酒铝质易拉罐的生产以及贝尔卡公司开发的混合整数规划模型是如何通过使用批量订货进而获得折扣的方法替客户节省开支的。在本章读者还将看到整数规划的其他一些应用的范例。本章的主要内容就是对整数线性规划的应用做详细介绍。首先，我们将讨论整数线性规划的不同分类。随后，我们将介绍整数线性的公式解法、图解法以及计算机解法。在第8.3节中，我们将讨论5个使用0–1变量的整数线性规划的应用实例：资金预算问题、固定成本问题、

3、分布系统设计问题、银行选址问题和市场份额最优化问题。在第8.4节中，我们将再举一个例子来说明使用0–1变量给规划带来的巨大灵活性和便利性。本章的附录将举例说明如何使用Excel电子表格来求解整数规划问题。整数规划提供建模灵活性的代价是：这种含有整数变量的问题通常比较难以求解。一盒含有上千个连续变量的线性规划问题，可以使用任何一种商业线性规划的解法进行求解。但是一个仅含有少于100个全整数变量的线性规划问题却极难解决。经验丰富的管理科学家能够分辨出哪些整数线性规划时容易求解的或者至少是合适去求解的。商用计算机软件包

4、，例如LINGO，CPLEX，Xpress-MP和PremiumSolver的商业版本都有强大的整数规划功能，并且整数规划的非常健全的开放资源软件包也是容易得到的。“管理科学家”和电子表格软件，例如Excel，可以用来处理小型整数线性规划。7.1整数线性规划的分类本章所研究的线性规划问题和前几章研究的问题的唯一区别是：在线性规划问题中，至少有一个变量是整数型的。如果所有变量均为整数．就称其为全整数线性规划。下面通过构建一个含有2个整数变量的全整型线性规划模型来说明：max2x1+3x2s.t．3x1+3X2≤12

5、x1+x2≤41x1+2x2≤6x1，x2≥0，且为整数请注意，如果去掉此模型中的“整数”一词，我们将得到我们所熟悉的双变量线性规划。去掉整数要求后得到的线性规称做整数线性规的LP松弛。如果只有一些变量是整数而非全部都是，则称做混合整数线性规划。下面是一个有两个变量的混合整数线性规划。max3x1+4x2s.t-1x1+2x2≤81x1+2x2≤122x1+1x2≤16x1，x2≥O，且x2为整数去掉“X2为整数”这个条件后，我们得到此混台整数线性规划的LP松弛。在某些应用软件中，整数变量只取0或1。这类规划被称

6、做0一1整数线性规划。读者可以在本章的后面部分中发现，使用0一1变量可以使线性规划很灵活、很容易求解。专栏7-2描述了如何用一个含有0一1变量的混合整数线性规划确定啤酒易拉罐的生产进度。生产线的换线用0一l变量来表示，而产量则用连续变量来表示。7.2全整数线性规划的图解法与计算机解法伊斯特伯恩房地产公司有200万美元可用于购买新的相赁财产。经过筛选．公司已将投资项目的方案减少为连体别墅和公寓楼。每套连体别墅售价282000美元，现有5套空置。每幢公寓楼售价400000美元，而且开发商可以根据伊斯特伯恩的需要数量建

7、房。伊斯特伯恩的财产经理每月可以有140小时用来处理这些新置的财产，其中，每套连体别墅预计每月要花4小时，每幢公寓楼预计每月40小时。扣除抵押偿还和经营成本后，年现金流量预计为：每套连体别墅10000美元：每幢公寓幢15000美元。伊斯特伯恩的股东想知道往保证年现金流量最大的要求下．购买连体别墅和公寓楼的数量。我们先定义决策变量如下：T—一连体别墅的数量；A——公寓楼的数量。现金流量(单位：1000美元)的目标函数为：max10T+l5A必须满足的3个约束条件是：282T+400A≤2000可用资金(单位：100

8、0美元)4T+40A≤140管理者的时间(小时)T≤5可得连体别墅变量T和A必须是非负的。而且，连体别墅和(或)公寓楼均不可以拆开购买。因此，T和A一定是整数型的。伊斯特伯恩房地产问题的模型即为如下全整数线性规划：max10T+15As.t．282T+400A≤20004T+40A≤140T≤5T，A≥0．且为整数7.2.1LP松弛的图解法现在我们去掉T和A为整数的条件，