整数规划规划论

整数规划的难度远大于一般线性规划

整数规划（integer programming）是一类在线性规划基础上加上整数变量的优化问题。与一般线性规划相比，整数规划问题更加困难，其求解过程相对复杂，通常需要使用特殊的算法和技巧来找到最优解。本文将从数学性质、计算复杂性以及求解方法三个方面来详细说明整数规划的难度。

首先，整数规划相对于一般线性规划来说，在数学性质上更加复杂。一般线性规划的约束条件和目标函数都是由实数变量表示，而整数规划则要求变量取整数值。这种要求使问题空间变得离散，整数规划的解空间无法通过连续域函数的方法进行分析。因此，在整数规划中，对解空间的搜索和优化更加困难。

此外，整数规划在计算复杂性上也较为高。根据计算复杂性理论，整数规划问题可以被归类为NP-hard问题，即在多项式时间内无法找到最优解。而一般线性规划问题可以在多项式时间内通过简单的算法得到最优解。因此，整数规划问题的复杂性限制了我们在求解过程中使用常规的算法，需要使用更加高效和特殊的算法来寻找最优解。

在求解整数规划问题时，需要利用整数变量取值离散的特性，设计相应的启发式搜索算法和剪枝策略。其中，分支定界（branch and bound）方法是求解整数规划问题的一种常见方法。该方法通过不断分割可行域，将原问题分解为若干个子问题，并使用界限函数来减少搜索空间。然后，再对子问题进行求解，直至找到整数规划问题的最优解。

此外，还有一些特殊类型的整数规划问题，如混合整数线性规划（mixed integer linear programming, MILP）、二次整数规划（quadratic integer programming）等，其求解难度更加复杂。这些问题中，目标函数和约束条件同时包含整数变量和连续变量，使得问题空间更加复杂，求解难度更高。

总结而言，整数规划相对于一般线性规划来说，难度远大于一般线性规划。这是由于整数规划在数学性质、计算复杂性以及求解方法等方面具有较高的难度和复杂性。为了解决整数规划问题，需要利用整数变量取值离散的特性，设计特殊的算法和技巧，提高求解效率。整数规划问题的困难性也激发了学者们的兴趣，产生了许多优化算法和理论，为复杂优化问题的求解提供了重要的理论和应用基础。接下来，我们将进一步探讨整数规划问题的困难之处，并介绍一些常用的求解方法。

-12- 整数线性规划理论

§1 概论

1.1 定义

规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。

1.2 整数规划的分类

如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类：

1o 变量全限制为整数时，称纯（完全）整数规划。

2o 变量部分限制为整数的，称混合整数规划。

1.3 整数规划特点

（i） 原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：

①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。

②整数规划无可行解。

例1 原线性规划为

21minxxz

0,0,5422121xxxx

其最优实数解为：45min,45,021zxx。LINGO1.lg4 LINGO11.lg4

③有可行解（当然就存在最优解），但最优解值变差。

例2 原线性规划为

21minxxz

0,0,6422121xxxx

其最优实数解为：23min,23,021zxx。

若限制整数得：2min,1,121zxx。LINGO2.lg4 LINGO21.lg4

（ii） 整数规划最优解不能按照实数最优解简单取整而获得。

1.4 求解方法分类：

（i）分枝定界法—可求纯或混合整数线性规划。

（ii）割平面法—可求纯或混合整数线性规划。

（iii）隐枚举法—求解“0-1”整数规划：

①过滤隐枚举法；

②分枝隐枚举法。

（iv）匈牙利法—解决指派问题（“0-1”规划特殊情形）。

（v）蒙特卡洛法—求解各种类型规划。

下面将简要介绍常用的几种求解整数规划的方法。

§2 分枝定界法

徐州工程学院

数理学院

案例分析报告

课程名称 运筹学及应用

案例分析题目 华南公司投资方案

专 业 信息与计算科学

班 级 13信计1

姓 名 李明军 陈翔 历晓雨 石宝 刘嘉炜 陈伟康

学 号 42 44 13 23 25 40

指导教师 赵建强

成绩等级

2015年 6 月 12 日

目 录

小组成员分工………………………………………………………………………1

一．问题描述………………………………………………………………………2

二．问题分析………………………………………………………………………2

三．模型建立………………………………………………………………………2

四．模型求解与程序设计…………………………………………………………3

五．结果分析………………………………………………………………………5

- 1 - 小组人员详细分工（3-6人）

学号 姓名 具体分工

42 李明军 统筹安排

13 厉晓雨 排版整理

44 陈翔 模型建立

23 石宝 模型求解

25 刘嘉炜 问题分析

40 陈伟康 软件应用 - 2 - 一．问题描述

华南投资公司在实施“九五”后三年及“十五”初期发展规划时，决定投资兴办产业，以增强发展后劲，投资总额为800万元，其中第一年(即1998年)350万元，第二年300万元，第三年150万元。投资方案有：

数学建模培训——整数规划

一、整数规划

1.实例

某建筑公司承包建两种类型住宅楼。甲种住宅楼每幢占地面积为320.2510m，乙种住宅楼每幢占地面积为320.410m。该公司已购进32310m的建筑用地。计划要求建甲种住宅楼不超过8幢，乙种住宅楼不超4幢。建甲种住宅楼一幢可获利10万元，建乙种住宅楼一幢可获利20万元。问应建甲、乙种住宅楼各几幢，公司获利最大？

model:

max=10*x1+20*x2;

0.25*x1+0.4*x2<3;

x1<8;

x2<4;

@gin(x1);@gin(x2);

end

2.整数规划的求解

Lingo程序中加入变量限制函数@gin(x)，表示x取值为整数。

二、经典的整数规划模型

1.指派问题

有一份中文说明书，需译成英、日、德、俄四种文字.分别记作E，J，G，R.现有甲乙丙丁四人，他们将中文说明书翻译成不同语种的说明书所需时间如表所示.问应指派何人完成何种工作，使所需总时间最少.

E J G R

甲 2 15 13 4

乙 10 4 14 15

丙 9 14 16 13

丁 7 8 11 9

解：Lingo程序

model:

sets:

worker/w1..w4/;

job/j1..j4/;

links(worker,job):c,x;

endsets

data:

c=@ole(datac.xlsx,cc);

enddata

min=@sum(links:c*x);

@for(worker(i):@sum(job(j):x(i,j))=1);

@for(job(j):@sum(worker(i):x(i,j))=1);

@for(links:@bin(x));

end 2.背包问题

一个旅行者外出旅行，携带一背包，装一些最有用的东西，共有n件物品供选择。已知每件物品的使用价值jc和重量ja，要求最多携带物品的重量为b，且每件物品要么不带，要么只能整件携带。问携带哪些物品使总使用价值最大？