运筹学课程设计

时间：2024.3.31

HUNAN UNIVERSITY

运筹学课程设计

报告

课程题目整数线性规划及应用

学生姓名

学生学号

专业班级

指导老师

目录

摘要-------------------------------------------------------------1

一、整数规划概述 ---------------------------------------------------2

1分支定界法----------------------------------------------------- 3

2 割平面法-------------------------------------------------------4

3 0-1整数规划的数学模型------------------------------------------4

3.1 0-1规划隐枚举法---------------------------------------------5

3.2指派问题的匈牙利方法-----------------------------------------6

二、整数规划问题的LINGO求解----------------------------------------7

1般整数规划的解法-----------------------------------------------7

2一般0-1规划的解法----------------------------------------------8

三、整数规划应用----------------------------------------------------9

1一般整数规划问题实例分析（人力资源分配问题）--------------------9

2 0-1整数规划的实例分析（消防站问题、背包问题）--------------------11

四、总结-----------------------------------------------------------20

参考文献-----------------------------------------------------------21

摘要

运筹学主要研究经济活动和军事活动中能用数量来表达的有关策划、管理方面的问题。它以整体最优为目标，从系统的观点出发，力图以整个系统最佳的方式来解决该系统各部门之间的利害冲突。对所研究的问题求出最优解，寻求最佳的行动方案，所以它也可看成是一门优化技术，提供的是解决各类问题的优化方法。运筹学作为一门用来解决实际问题的学科，在处理千差万别的各种问题时，一般有以下几个步骤：确定目标、制定方案、建立模型、制定解法。其目的是根据实际问题的具体要求，通过定量的分析与运算，对资源运用、规划及其相关决策等问题作出综合最有的合理安排，以使有限的资源发挥更大的效益或作用。

LINGO可以用于求解非线性规划，也可以用于一些线性和非线性方程组的求解等，功能十分强大，是求解优化模型的最佳选择。其特色在于内置建模语言，提供十几个内部函数，可以允许决策变量是整数（即整数规划，包括 0-1 整数规划），方便灵活，而且执行速度非常快。在运筹学的研究中，LINGO如见扮演着重要的角色。一般地，使用LINGO 求解运筹学问题可以分为以下两个步骤来完成：

1）根据实际问题，建立数学模型，即使用数学建模的方法建立优化模型；

2）根据优化模型，利用LINGO 来求解模型。主要是根据LINGO软件，把数学模型转译成计算机语言，借助于计算机来求解。

本文主要研究整数规划，建立整数规划数学模型，运用LINGO软件求解整数规划的最优解，从而获得最优方案。因此，整数规划的模型对研究运筹学问题有重要的意义。

关键词：运筹学整数规划 LINGO 最优解 0-1整数规划

一、整数规划概述

整数规划是指一类要求问题中的全部或一部分变量为整数的数学规划。是近三十年来发展起来的、规划论的一个分支.。整数规划问题是要求决策变量取整数值的线性规划或非线性规划问题。一般认为非线性的整数规划可分成线性部分和整数部分，因此常常把整数规划作为线性规划的特殊部分。在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求解答必须是整数。例如，所求解是机器的台数，工作的人数或装货的车数等。为了满足整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解，所以应该有特殊的方法来求解整数规划。

整数规划是从1958年由R.E.戈莫里提出割平面法之后形成独立分支的，30多年来发展出很多方法解决各种问题。解整数规划最典型的做法是逐步生成一个相关的问题，称它是原问题的衍生问题。对每个衍生问题又伴随一个比它更易于求解的松弛问题（衍生问题称为松弛问题的源问题）。通过松弛问题的解来确定它的源问题的归宿，即源问题应被舍弃，还是再生成一个或多个它本身的衍生问题来替代它。随即，再选择一个尚未被舍弃的或替代的原问题的衍生问题，重复以上步骤直至不再剩有未解决的衍生问题为止。目前比较成功又流行的方法是分枝定界法和割平面法，它们都是在上述框架下形成的。

整数线性规划中如果所有的变量都限制为非负整数，就称为纯整数线性规划或全整数线性规划；如果仅一部分变量限制为整数，则称为混合整数规划。整数规划的一种特殊情形是0-1规划，它的变量的取值仅限于0和1。整数规划的一个著名问题---指派问题就是0-1规划问题。目前所流行的求解整数规划的方法，往往只适用于整数线性规划.本文我们主要讨论整数线性规划问题.

整数线性规划一般模型：

s.t

它的求解往往较为复杂，现在公认的几种解法有分支定界法、割平面法和完全枚举法。但随着计算机技术的发展，求解整数规划问题已经不是难事，如Lingo和Lindo等软件都可以十分轻松的进行求解。下面对部分解法进行介绍和探讨。

1.分支定解法

对有约束条件的最优化问题（其可行解为有限数）的可行解空间恰当地进行系统搜索，这就是分枝与定界内容.通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界.在每次分枝后，凡是界限不优于已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路.。分枝定界法可用于解纯整数或混合的整数规划问题。在二十世纪六十年代初由Land Doig和Dakin等人提出.由于这方法灵活且便于用计算机求解，所以现在它已是解整数规划的重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等.设有最大化的整数规划问题A，与它相应的线性规划为问题B，从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数的上界，记作；而A的任意可行解的目标函数值将是的一个下界.分枝定界法就是将B的可行域分成子区域再求其最大值的方法.逐步减小和和增大，最终求到。

用分枝定界法求解整数规划（最大化）问题的步骤为：

开始，将要求解的整数规划问题称为问题A，将与它相应的线性规划问题称为问题 B。

A、解问题B可能得到以下情况之一：

(a).B没有可行解，这时A也没有可行解，则停止。

(b).B有最优解，并符合问题A的整数条件，B的最优解即为A的最优解，则停止。

(c).B有最优解，但不符合问题A的整数条件，记它的目标函数值为.。

B、用观察法找问题A的一个整数可行解，一般可取试探，求得其目标函数值，并记作.以表示问题A的最优目标函数值；这时有

C、进行迭代

第一步：分枝，在B的最优解中任选一个不符合整数条件的变量，其值为，以[示小于的最大整数.构造两个约束条件

将这两个约束条件，分别加入问题B，求两个后继规划问题.不考虑整数条件求解这两个后继问题.。定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界.从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界，若无可行解，=0。

第二步：比较与剪枝，各分枝的最优目标函数中若有小于者，则剪掉这枝，即以后不再考虑了.若大于，且不符合整数条件，则重复第一步骤.一直到最后得到为止。得最优整数解?

2.割平面法

用割平面法求解整数规划的基本思路是：先不考虑整数约束条求松弛问题的最优解，如果获得整数最优解，即为所求，运算停止。如果所得到最优解不满足整数约束条件，则在此非整数解的基础上增加新的约束条件重新求解。这个新增加的约束条件的作用就是去切割相应松弛问题的可行域，即割去松弛问题的部分非整数解(包括原已得到的非整数最优解)，而把所有的整数解都保留下来，故称新增加的约束条件为割平面。当经过多次切割后，就会使被切割后保留下来的可行域上有一个坐标均为整数的顶点，它恰好就是所求问题的整数最优解。即切割后所对应的松弛问题，与原整数规划问题具有相同的最优解。

割平面法的基本步骤：

A、先不考虑变量的取整约束，用单纯形法求解相应的线性规划问题，如果该问题没有可行解或最优解已是整数则停止，否则转下步。在求解相应的线性规划时，首先要将原问题的数学模型进行标准化。这里的“标准化”有两个含义：第一是将所有的不等式约束全部转化成等式约束，这是因为要采用单纯形表进行计算的缘故。第二是将整数规划中所有非整数系数全部转换成整数，这是出于构造“切割不等式”的需要。

B、求一个“切割不等式”及添加到整数规划的约束条件中去，即对上述线性规划问题的可行域进行“切割”，然后返回步骤1。

3.0-1整数规划的数学模型

如果整数规划中的所有决策变量仅限于取0或1两个值，则称此问题为0-1整数规划，简称0-1规划。其变量称为0-1变量，或二进制变量。相应的决策变量的取值约束变为或1，等价于，且为整数。0-1?线性规划的一般模型为：

s.t.

3.1 0-1规划隐枚举法

0-1整数规划模型的解法一般为显枚举法（穷举法）或隐枚举法。穷举法指的是对决策变量的的每一个0或1值，均比较其目标函数值的大小，以从中求出最优解。这种方法一般适用于决策变量个数n较小的情况，当n较大时，由于n个0、1的可能组合数为，故此时即便用计算机进行穷举来求最优解，也几乎是不可能的。求解0-1整数规划问题的解法均是隐枚举法或称为部分枚举法．隐枚举法是增加了过滤条件的一类穷举法。在个可能的变量组合中, 往往只有一部分是可行解.。只要发现某个变量组合不满足其中的某一约束条件时, 就不必要检验其它的约束条件是否可行。若发现一个可行解, 则根据它的目标函数值可以产生一个过滤条件(Filtering constraint), 对于目标函数值比它差的的变量组合就不必再去检验它的可行性（类似分支定界法中的定界。实际上，隐枚举法是一种特殊的分支定界法）。在以后求解过程中, 每当发现比原来更好的可行解, 则依次替代原来的过滤条件 (可减少运算次数, 较快地发现最优解)。

例求解下述0-1整数规划问题：

求解过程如下：

所以，最优解为（x1，x2，x3)=(1,0,1)，最优值为8。

3.2 指派问题的匈牙利方法

指派问题的模型：一般地，有n项任务n个完成人，第i人完成第j项任务的代价为，为了求得总代价最小的指派方案，引入0-1?型变量，并令

则，问题数学模型为

s.t.

可见指派问题是0-1型整数规划的特例。

匈牙利算法的基本步骤为：

步骤1 对效益矩阵进行变换，使每行每列都出现0元素。

(1)从效益矩阵c中每一行减去该行的最小元素；

(2)再在所得矩阵中每一列减去该列的最小元素，所得矩阵记为D一(d.)..

步骤2将矩阵D中0元素置为1元素，非零元素置为0元素，记此矩阵为E。

步骤3确定独立1元素组。

(1)在矩阵E含有1元素的各行中选择1元素最少的行，比较该行中各1元素所在的列中1元素的个数，选择1元素的个数最少的一列的那个1元素；

(2)将所选的1元素所在的行和列清0；

(3)重复第2步和第3步，直到没有1元素为止，即得到一个独立1元素组。

步骤4 判断是否为最大独立1元素组。

(1)如果所得独立1元素组是原效益矩阵的最大独立1元素组(即1元素的个数等于矩阵的阶数)，则已得到最优解，停止计算。

(2)如果所得独立1元素组还不是原效益矩阵的最大独立1元素组，那么利用寻找可扩路的方法对其进行扩张，进行下一步。

步骤5 利用寻找可扩路方法确定最大独立1元素组。

(1)做最少的直线覆盖矩阵D的所有0元素；

(2)在没有被直线覆盖的部分找出最小元素，在没有被直线覆盖的各行减去此最小元素，在没被直线覆盖的各列加上此最小元素，得到一个新的矩阵，返回第2步。

二、整数规划问题的LINGO求解方法

LINDO是一种专门用于求解数学规划问题的软件包。它是一套设计用来帮助快速，方便和有效的构建和求解线性，非线性，和整数最优化模型的功能全面的工具。包括功能强大的建模语言，建立和编辑问题的全功能环境，读取和写入Excel和数据库的功能，和一系列完全内置的求解程序。 LINDO中包含的一种建模语言和许多常用的数学函数(包括大量概率函数)，可供使用者建立数学规划问题模型时调用。是求解优化模型的最佳选择。

1.一般整数规划的解法

一般的整数规划模型程序如下：

MODEL:

sets:

num_i/1..m/:b;

num_j/1..n/:x,c;

link(num_i,num_j):a;

endsets

data:

b=b(1),b(2),...b(m);

c=c(1),c(2),...c(n);

a=a(1,1),a(1,2),...,a(1,n),

a(2,1),a(2,2),...,a(2,n),

...

a(m,1),a(m,2),...,a(m,n);

enddata

[OBJ]max=@sum(num_j(j):c(j)*x(j));

@for(num_i(i):@sum(num_j(j):a(i,j)*x(j))<=b(i););

@for(num_j(j):x(j)>=0;);

@for(num_j(j):@GIN(x(j)););

END

2.一般0-1规划的解法

针对一般的规划模型编写LINGO程序，在这里假设目标函数为最大化问题，约束条件都为“小于等于”的情况．

具体程序如下：

MODEL

sets:

num_i/1..m/:b;

num_j/1..n/:x,c;

link(num_i,num_j):a;

endsets

data:

b=b(1),b(2),...,b(m);

c=c(1),c(2),...,c(n);

a=a(1,1),a(1,2),...,a(1,n),

a(2,1),a(2,2),...,a(2,n),

...

a(m,1),a(m,2),...,a(m,n);

enddata

[OBJ]max=@sum(num_j(j):c(j)*x(j));

@for(num_i(i):@sum(num_j(j):a(i,j)*x(j))<=b(i););

@for(num_j(j):@sumBIN(x(j)););

END

三、整数规划应用

1.一般整数规划问题实例分析

例人力资源分配问题

某个中型百货商场对售货人员（周工资200元）的需求经统计如上表，为了保证销售人员充分休息，销售人员每周工作5天，休息2天。问应如何安销售人员的工作时间，使得所配售货人员的总费用最小？

模型假设：

（1）每天工作8小时，不考虑夜班的情况；

（2）每个人的休息时间为连续的两天时间；

（3）每天安排的人员数不得低于需求量，但可以超过需求量

因素：

不可变因素：需求量、休息时间、单位费用；

可变因素：安排的人数、每人工作的时间、总费用；

方案：确定每天工作的人数，由于连续休息2天，当确定每个人开始休息的时间就等于知道工作的时间，因而确定每天开始休息的人数就知道每天开始工作的人数，从而求出每天工作的人数。

变量：每天开始休息的人数，

约束条件

（1）每人休息时间2天，自然满足。

（2）每天工作人数不低于需求量，第天工作的人数就是从第天往前数5天内开始休息的人数，所以有约束：

（3）变量非负约束：

目标函数：总费用最小，总费用与使用的总人数成正比。由于每个人必然在且仅在某一天开始休息，所以总人数等于

模型：

用LINGO计算：

model:

min=200*x1+200*x2+200*x3+200*x4+200*x5+200*x6+200*x7;

x2+x3+x4+x5+x6>=12;

x3+x4+x5+x6+x7>=15;

x1+x4+x5+x6+x7>=12;

x1+x2+x5+x6+x7>=14;

x1+x2+x3+x6+x7>=16;

x1+x2+x3+x4+x7>=18;

x1+x2+x3+x4+x5>=19;

@gin(x1);@gin(x2);@gin(x3);@gin(x4);@gin(x5);@gin(x6);@gin(x7);

End

运行结果如下：

Global optimal solution found.

Objective value: 4400.000

Objective bound: 4400.000

Infeasibilities: 0.000000

Extended solver steps: 0

Total solver iterations: 4

Variable Value Reduced Cost

X1 7.000000 200.0000

X2 0.000000 200.0000

X3 8.000000 200.0000

X4 0.000000 200.0000

X5 4.000000 200.0000

X6 0.000000 200.0000

X7 3.000000 200.0000

Row Slack or Surplus Dual Price

1 4400.000 -1.000000

2 0.000000 0.000000

3 0.000000 0.000000

4 2.000000 0.000000

5 0.000000 0.000000

6 2.000000 0.000000

7 0.000000 0.000000

8 0.000000 0.000000

注：（1）该问题本质上是个整数规划问题，放松的线性规划的最优解是个整数解，所以两规划等价。

（2）定义整数变量用函数@gin(x1)……@gin(x7);

2.0-1整数规划的实例分析

例消防站问题（教材课后习题6.4）

某城市的消防总站将全市划分为11个防火区，现有4个消防站，图4-11给出的是该城市各防火区域和防火站的示意图，其中1,2,3,4，表示消防站1，2，…11表示防火区域，根据历史资料证实，各消防站可在事先规定允许的时间内对所负责的区域内的火灾予以扑灭，图中没有虚线连接的就表示不负责，现在总部提出：能否减少消防站的数目，仍能保证负责各地区的防火任务？如果可以的话，应该关闭哪个？

解：根据题意，用xi表示第i个消防站的关系的打开关闭情况

xi=1；第i个消防站不关闭

Xi=0；第i个消防站关闭

用y代表第i个消防站到第j个防火区域的到达情况，0表示不可达，1表示可达，Y=[1,1,1,1,0,1,1,1,0,0,0;

　　1,1,0,1,0,0,0,1,1,0,0;

　　0,0,0,1,1,1,0,0,0,0,1;

　　0,0,0,0,0,1,1,1,1,1,1;]

则问题可归结为0—1整数规划模型。

min z=sum x（i）;

St ： x（i）*y（i，j）>=1；j=1,2,3...11

x（i）<=3；

X=0或1

利用LINGO求解：

model:

sets:

n_i/1..4/:x;

n_j/1..11/;

link(n_i,n_j):y;

endsets

data:

y=1,1,1,1,0,1,1,1,0,0,0,1,1,0,1,0,0,0,1,1,0,0,0,0,0,1,1,1,0,0,0,0,1,0,0,0,0,0,1,1,1,1,1,1;

enddata

[obj]min=@sum(n_i(i):x(i));

@for(n_j(j):@sum(n_i(i):x(i)*y(i,j))>=1;);

@for(n_j(j):@sum(n_i(i):x(i))<=3;);

@for(n_i(i):@bin(x(i));x(i)>=0;);

end

运行结果：

Global optimal solution found.

Objective value: 3.000000

Objective bound: 3.000000

Infeasibilities: 0.000000

Extended solver steps: 0

Total solver iterations: 0

Variable Value Reduced Cost

X( 1) 1.000000 1.000000

X( 2) 0.000000 1.000000

X( 3) 1.000000 1.000000

X( 4) 1.000000 1.000000

Y( 1, 1) 1.000000 0.000000

Y( 1, 2) 1.000000 0.000000

Y( 1, 3) 1.000000 0.000000

Y( 1, 4) 1.000000 0.000000

Y( 1, 5) 0.000000 0.000000

Y( 1, 6) 1.000000 0.000000

Y( 1, 7) 1.000000 0.000000

Y( 1, 8) 1.000000 0.000000

Y( 1, 9) 0.000000 0.000000

Y( 1, 10) 0.000000 0.000000

Y( 1, 11) 0.000000 0.000000

Y( 2, 1) 1.000000 0.000000

Y( 2, 2) 1.000000 0.000000

Y( 2, 3) 0.000000 0.000000

Y( 2, 4) 1.000000 0.000000

Y( 2, 5) 0.000000 0.000000

Y( 2, 6) 0.000000 0.000000

Y( 2, 7) 0.000000 0.000000

Y( 2, 8) 1.000000 0.000000

Y( 2, 9) 1.000000 0.000000

Y( 2, 10) 0.000000 0.000000

Y( 2, 11) 0.000000 0.000000

Y( 3, 1) 0.000000 0.000000

Y( 3, 2) 0.000000 0.000000

Y( 3, 3) 0.000000 0.000000

Y( 3, 4) 1.000000 0.000000

Y( 3, 5) 1.000000 0.000000

Y( 3, 6) 1.000000 0.000000

Y( 3, 7) 0.000000 0.000000

Y( 3, 8) 0.000000 0.000000

Y( 3, 9) 0.000000 0.000000

Y( 3, 10) 0.000000 0.000000

Y( 3, 11) 1.000000 0.000000

Y( 4, 1) 0.000000 0.000000

Y( 4, 2) 0.000000 0.000000

Y( 4, 3) 0.000000 0.000000

Y( 4, 4) 0.000000 0.000000

Y( 4, 5) 0.000000 0.000000

Y( 4, 6) 1.000000 0.000000

Y( 4, 7) 1.000000 0.000000

Y( 4, 8) 1.000000 0.000000

Y( 4, 9) 1.000000 0.000000

Y( 4, 10) 1.000000 0.000000

Y( 4, 11) 1.000000 0.000000

Row Slack or Surplus Dual Price

OBJ 3.000000 -1.000000

2 0.000000 0.000000

3 0.000000 0.000000

4 0.000000 0.000000

5 1.000000 0.000000

6 0.000000 0.000000

7 2.000000 0.000000

8 1.000000 0.000000

9 1.000000 0.000000

10 0.000000 0.000000

11 0.000000 0.000000

12 1.000000 0.000000

13 0.000000 0.000000

14 0.000000 0.000000

15 0.000000 0.000000

16 0.000000 0.000000

17 0.000000 0.000000

18 0.000000 0.000000

19 0.000000 0.000000

20 0.000000 0.000000

21 0.000000 0.000000

22 0.000000 0.000000

23 0.000000 0.000000

24 1.000000 0.000000

25 0.000000 0.000000

26 1.000000 0.000000

27 1.000000 0.000000

因为x1= x3=x4=1，x2=0；即应关闭2号消防站。

例背包问题

某人出国留学打点行李,现有3个旅行包,容积分别为1000ml、1500ml和2000ml,根据需要列出需带物品清单,其中必带物品7件,其体积分别为400、300、150、250、450、760、190(单位ml)。尚有10件待选物品,如果不带将在目的地购买,通过网络查询可以得知其在目的地的价格(单位$)。这些物品的容量及价格分别见下表,试给出一个合理的安排方案把物品放在三个旅行包里。

变量：对每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第i个物品是否放在第j个包裹中

约束：

（1）包裹容量限制：

（2）必带物品限制：

（3）选带物品限制：

目标函数：未带物品购买费用最小

模型：

s.t.

用LINGO计算：

model:

sets:

wps/wp1..wp17/: tj,jg;

bg/1..3/:r;

links(wps,bg): x;

Endsets

Min=@sum(wps(i):jg(i)*(1-x(i,1)-x(i,2)-x(i,3)));

@for(bg(j):@sum(wps(i):tj(i)*x(i,j))<=r(j));

@for(wps(i)|i #le# 7: @sum(bg(j):x(i,j))=1);

@for(wps(i)|i #gt# 7: @sum(bg(j):x(i,j))<=1);

@for(links(i,j):@Bin(x(i,j)););

data:

tj= 400 300 150 250 450 760 190 200 350 500 430 320 120 700 420 250 100;

jg= 0 0 0 0 0 0 0 15 45 100 70 50 75 200 90 20 30;

r=1000 1500 2000;

Enddata

End

运行结果如下：

Global optimal solution found.

Objective value: 200.0000

Objective bound: 200.0000

Infeasibilities: 0.000000

Extended solver steps: 32

Total solver iterations: 827

Variable Value Reduced Cost

TJ( WP1) 400.0000 0.000000

TJ( WP2) 300.0000 0.000000

TJ( WP3) 150.0000 0.000000

TJ( WP4) 250.0000 0.000000

TJ( WP5) 450.0000 0.000000

TJ( WP6) 760.0000 0.000000

TJ( WP7) 190.0000 0.000000

TJ( WP8) 200.0000 0.000000

TJ( WP9) 350.0000 0.000000

TJ( WP10) 500.0000 0.000000

TJ( WP11) 430.0000 0.000000

TJ( WP12) 320.0000 0.000000

TJ( WP13) 120.0000 0.000000

TJ( WP14) 700.0000 0.000000

TJ( WP15) 420.0000 0.000000

TJ( WP16) 250.0000 0.000000

TJ( WP17) 100.0000 0.000000

JG( WP1) 0.000000 0.000000

JG( WP2) 0.000000 0.000000

JG( WP3) 0.000000 0.000000

JG( WP4) 0.000000 0.000000

JG( WP5) 0.000000 0.000000

JG( WP6) 0.000000 0.000000

JG( WP7) 0.000000 0.000000

JG( WP8) 15.00000 0.000000

JG( WP9) 45.00000 0.000000

JG( WP10) 100.0000 0.000000

JG( WP11) 70.00000 0.000000

JG( WP12) 50.00000 0.000000

JG( WP13) 75.00000 0.000000

JG( WP14) 200.0000 0.000000

JG( WP15) 90.00000 0.000000

JG( WP16) 20.00000 0.000000

JG( WP17) 30.00000 0.000000

R( 1) 1000.000 0.000000

R( 2) 1500.000 0.000000

R( 3) 2000.000 0.000000

X( WP1, 1) 0.000000 0.000000

X( WP1, 2) 1.000000 0.000000

X( WP1, 3) 0.000000 0.000000

X( WP2, 1) 1.000000 0.000000

X( WP2, 2) 0.000000 0.000000

X( WP2, 3) 0.000000 0.000000

X( WP3, 1) 0.000000 0.000000

X( WP3, 2) 1.000000 0.000000

X( WP3, 3) 0.000000 0.000000

X( WP4, 1) 0.000000 0.000000

X( WP4, 2) 1.000000 0.000000

X( WP4, 3) 0.000000 0.000000

X( WP5, 1) 0.000000 0.000000

X( WP5, 2) 0.000000 0.000000

X( WP5, 3) 1.000000 0.000000

X( WP6, 1) 0.000000 0.000000

X( WP6, 2) 0.000000 0.000000

X( WP6, 3) 1.000000 0.000000

X( WP7, 1) 1.000000 0.000000

X( WP7, 2) 0.000000 0.000000

X( WP7, 3) 0.000000 0.000000

X( WP8, 1) 0.000000 -15.00000

X( WP8, 2) 0.000000 -15.00000

X( WP8, 3) 0.000000 -15.00000

X( WP9, 1) 0.000000 -45.00000

X( WP9, 2) 0.000000 -45.00000

X( WP9, 3) 0.000000 -45.00000

X( WP10, 1) 1.000000 -100.0000

X( WP10, 2) 0.000000 -100.0000

X( WP10, 3) 0.000000 -100.0000

X( WP11, 1) 0.000000 -70.00000

X( WP11, 2) 0.000000 -70.00000

X( WP11, 3) 0.000000 -70.00000

X( WP12, 1) 0.000000 -50.00000

X( WP12, 2) 0.000000 -50.00000

X( WP12, 3) 0.000000 -50.00000

X( WP13, 1) 0.000000 -75.00000

X( WP13, 2) 0.000000 -75.00000

X( WP13, 3) 1.000000 -75.00000

X( WP14, 1) 0.000000 -200.0000

X( WP14, 2) 1.000000 -200.0000

X( WP14, 3) 0.000000 -200.0000

X( WP15, 1) 0.000000 -90.00000

X( WP15, 2) 0.000000 -90.00000

X( WP15, 3) 1.000000 -90.00000

X( WP16, 1) 0.000000 -20.00000

X( WP16, 2) 0.000000 -20.00000

X( WP16, 3) 0.000000 -20.00000

X( WP17, 1) 0.000000 -30.00000

X( WP17, 2) 0.000000 -30.00000

X( WP17, 3) 1.000000 -30.00000

Row Slack or Surplus Dual Price

1 200.0000 -1.000000

2 10.00000 0.000000

3 0.000000 0.000000

4 150.0000 0.000000

5 0.000000 0.000000

6 0.000000 0.000000

7 0.000000 0.000000

8 0.000000 0.000000

9 0.000000 0.000000

10 0.000000 0.000000

11 0.000000 0.000000

12 1.000000 0.000000

13 1.000000 0.000000

14 0.000000 0.000000

15 1.000000 0.000000

16 1.000000 0.000000

17 0.000000 0.000000

18 0.000000 0.000000

19 0.000000 0.000000

20 1.000000 0.000000

21 0.000000 0.000000

所以，bag1中所放物品编号为7、4、17，bag2中所放物品编号为1,10,13,15，bag3中所放物品编号为2,3,4,5,6。

四、总结与心得

当老师说道要做一个自己感兴趣的课程设计的时候，真的是一点方向感都没有。上课学过的线性规划与目标规划、动态规划等在现实生活中各有运用，但对运算结果要求是整数的情况了解较少，曾听老师提到过整数规划，抱着好奇心开始了探索。经过一周的时间，运筹学课程设计终于完成了。

首先，我对整数规划有了一个比较全面的了解。从整数规划的历史发展，到求解方法的演变，最后广泛运用于实际生活中。可以看出整数规划受到很大的重视，它在生活中的运用时很多的，比如选课策略、消防站布线问题，最常见的就是指派问题了。面对一个整数规划问题，我们需要根据题目中的约束条件和目标函数建立合理的模型，根据模型的特点选择自己喜欢又高效的求解方法。通过本次课程设计，我更深刻的体会到了运筹学的思维及精髓，学会了运用运筹学的思维思考问题，即：应用分析、试验、量化的方法，对实际中的人、财、物等有限的资源进行统筹安排，对于整数规划模型更加有了深刻的认识，并且学会了建立相关模型求解实际问题，以得到想要的结果。并且在建立模型，求解模型的过程中也认识到了整数规划的重要性，它也应用到了生活的方方面面。

其次，LINGO软件的熟练使用是一大收获。上学期曾经学过《数学建模》，里面有涉及到线性规划的求解需要运用LINGO，但当时并没有深刻感受到它求解优化模型的便利，特别是对常见的线性规划。本次课程设计在使用LINGO软件求解的同时，使我更加熟练的掌握了LINGO软件，让我能更好的使用LINGO软件来求解实际问题。我也明白了，学东西不是要到需要的时候再去学，提前学习总是有好处的，最好学以致用。

这次的运筹学课程设计对于我来说是一次难得的实践机会，使平时学习的知识得到运用，了解一些解决实际生活中的问题的方法，课程设计对我来说不仅仅是知识的提升，更是一种品格的磨砺。通过这次运筹学课程设计，我发现自己的很多不足，自己知识的很多漏洞，包括运筹学和数学两个方面的。运筹学是一门深奥的学科，并且对解决实际问题是非常有效的，通过一个学期的短暂学习，学到了一些理论知识及解决方法，但这次课程设计却是我们专业课程知识综合应用的实践训练，很大程度的提高了我们的实战能力，把理论与实践结合起来，有助于我们理解所学的知识，完善所学知识中的漏洞。

最后，感谢老师的的辛勤付出与热心指导，希望运筹学在后能够很好地运用运筹学知识解决实际问题。

参考文献

[1] 《运筹学》教材编写组．运筹学．北京：清华大学出版社，2012.9．

[2] 胡运权．运筹学基础及其应用[M]．北京：高等教育出版社，2004．

[3] 谢金星. 薛毅．优化建模LINGO/LINDO软件[M]．北京：清华大学出版社，2005．

[4] 周华任．运筹学解题指导[M]．北京：清华大学出版社，2006．

[5]宋学峰．运筹学[M]．南京；东南大学出版社：2003．

更多相关推荐：

运筹学课程设计报告(完): 运筹学课程设计报告组别第三组设计人员设计时间20xx年6月25日20xx年7月6日1设计进度本课程设计时间分为两周第一周20xx年6月25日20xx年6月29日建模阶段此阶段各小组根据给出的题目完成模型的建立主...
运筹学课程设计心得: 运筹学课程设计心得每学期的课设都是我们再次收获知识的时刻特别喜欢那种将理论应用到实践中的感觉只有在课设的时候才觉得自己所学是有意义的总是会欣喜的看着自己经过努力而得出的成果只有那一瞬间才会感觉所有的努力和付出都...
运筹学课程设计报告: 长春工业大学课程设计报告课程设计名称运筹课程设计专业班级学生姓名指导教师20xx年7月12日课程设计任务书1运筹学课程设计报告组别第十八组设计人员设计时间20xx年6月27日20xx年7月12日1设计进度本课程...
运筹学课程总结: 运筹学学习总结古人云“运筹帷幄之中，决胜千里之外”，运筹学是20世纪三四十年代发展起来的一门新兴交叉学科，它主要研究人类对各种资源的运用及筹划活动，以期通过了解和发展这种运用及筹划活动的基本规律，发挥有限资源的…
运筹学课程设计报告模板: 宁波大红鹰学院信息工程学院课程设计报告课程名称项目名称姓名班级名称专业名称完成时间运筹学与数据分析实践炼油厂生产计划安排信息管理和信息系统20xx0225信息工程学院一问题的提出正文宋体小四单倍行距这是一个线性...
运筹学课程设计报告: 运筹学课程设计报告求解线性规划问题学校学院专业班级学号姓名MATLAB求解20xx1227空气污染问题某钢厂的钢铁生产对城市的空气造成污染是该城市的主要污染源钢厂主要有两个污染源生产铁的高炉和将生铁炼成钢的平炉...
运筹学课程设计报告: 长春工业大学课程设计报告课程设计名称运筹课程设计专业工商管理班级110508班学生姓名**指导教师**20**年12月20日课程设计任务书运筹学课程设计报告组别：第十二组设计人员：**设计时间：20**.12.…

运筹学课程设计: 运筹学课程设计报告班级工业工程111姓名潘樟兴指导老师范佳静时间目录一模型构造311变量设置312模型构建4121单期模型4122多期模型5二LINDO模型和求解结果621LINDO模型622LINDO求解结果...
运筹学课程设计: 附件一湖南工业大学课程设计资料袋学院系部学年第学期课程名称运筹学指导教师段卫龙职称副教授学生姓名刘玮专业班级数学与应用数学1201班学号12411300121学生姓名谢亮专业班级数学与应用数学1201班学号12...
运筹学课程设计: 摘要通过对基本情况的分析经过抽象和延伸建立起线材的合理利用即节约下料问题通用线形规划模型结合模型的特点对模型进行求解并进行讨论和分析将模型应用于案例的背景问题得出相应的最有决策方案并对方案进行灵敏度分析最后结合...
运筹学课程设计: 运筹学课程设计院系机械与汽车工程学院专业班级姓名学号一实验目的锻炼运用所学知识解决综合性问题的能力二实验原理本实验使用LINDO601进行操作LINDOLinearInteractiveandDiscreteO...
运筹学课程设计: 西昌学院红牌罐头课程分析设计第一作者凌志第二作者XXOO摘要企业的基本问题就是如何生存如何以有限的资源的利益的最大决策机构在其控制下的企业进行决策时需考虑约束条件的影响追求企业利益的最大化我们常运用直接分析法类...

热门关注

运筹学课程设计报告书---运输问题的表上作业法

运筹学课程设计

HUNAN UNIVERSITY

二、整数规划问题的LINGO求解方法

1.一般整数规划的解法

2.一般0-1规划的解法

三、整数规划应用

1.一般整数规划问题实例分析

例 人力资源分配问题

某个中型百货商场对售货人员（周工资200元）的需求经统计如上表，为了保证销售人员充分休息，销售人员每周工作5天，休息2天。问应如何安销售人员的 工作时间，使得所配售货人员的总费用最小？

参考文献

例人力资源分配问题

某个中型百货商场对售货人员（周工资200元）的需求经统计如上表，为了保证销售人员充分休息，销售人员每周工作5天，休息2天。问应如何安销售人员的工作时间，使得所配售货人员的总费用最小？