整数规划(数据模型与决策)

1 高纲1396

江苏省高等教育自学考试大纲

30447 数据、模型与决策

南京大学编

江苏省高等教育自学考试委员会办公室

2 I 课程性质、设置目的与要求

一、《数据、模型与决策》课程的性质

随着社会信息化水平的提高和科学管理意识的普遍增强，人们对如何从数据资料角度进行认识显示出越来越多的兴趣。数据资料本身并没有什么意义，关键是采用合适的方法对其进行分析和处理，只有这样才能探索客观现象发展变化的内在规律，从而更好地服务于管理决策的需要。

《数据、模型与决策》属于数量性质的课程，侧重于讲解数据资料的搜集、描述、分析和解释，以及管理决策方法和技术方面的知识。管理决策分为两类，一类是理性决策一类是行为决策。数据分析与决策模型中，不论是以不确定性为特征的统计决策，还是以确定性为特征的管理科学优化决策，和以策略互动为特征的博弈决策，都可以把它们归结为理性决策范畴。既然是理性决策，必然会要求建立某种决策准则，然后在既定的准则下通过度量来选择决策方案。这一过程一方面要对研究的问题进行结构化处理，另一方面也需要有相应的数据资料。前者是为了能够建立决策模型，后者则是帮助实现计算。有鉴于此，数据与模型在决策分析中的重要意义不言而喻。数据与模型除了共同服务于决策分析以外，两者之间也存在密切的关系。从应用的角度，统计方法比较强调实证性做法，统计分析与决策中，没有大量的、客观准确的数据资料，统计决策分析只能停留在纯理论的状态，无法形成具体的分析结论。管理运筹优化和博弈决策分析中，虽然不像统计分析那样，需要拥有充足的数据，但是必要的不可控因素比如模型中的有关参数，其数值资料就必须事先给以确定。尽管现在的企业一般都积累了大量的可供开发利用的数据资料，不过由于这样那样的原因，数据资料本身总会存在不系统、不充分、不完备的情况。因此，对于背景数据必须经过科学的编辑、处理、汇总和提炼，然后才能用于决策分析。对此，模型起着重要的转化作用，通过模型化处理，不仅能对数据的价值结构进行改造，而且还能对决策赋以深层次的分析。如同生产过程一样，数据资料好比“原料”，模型就如“机器”，把数据原料投入模型机器，经过模型机器的加工处理，最后就能得到输出结果“产品”，即管理分析和决策方案。

工厂1、2、3分别生产A、B产品的零件

A B 可用时间

工厂1 1 0 4

工厂2 0 2 12

工厂3 3 2 8

利润 300 500

– 变化1：增加A、B产品的准备成本，分别为700和1300

– 变化2：A、B的数量限制在整数范围。

案例1：

产量x1、x2，A和B是否生产y1、y2

Max z=300x1+500x2-700y1-1300y2

X1<=4

2x2<=12

3x1+2x2<=18

X1<=99y1

X2<=99y2

X1、x2为非负整数

y1、y2为0-1整数

包含互斥产品

两种产品具有相同的用户，是互相竞争的。因此，管理层决定不同时生产两种产品，而是只能选择其中的一种。

案例2：

A和B是否生产y1、y2；产量x1、x2。

Max z=300x1+500x2

X1<=4

2x2<=12

3x1+2x2<=18

Y1+y2=1

X1<=99y1

X2<=99y2

Y1、y2为0-1整数

X1、x2为非负数

加入二选一约束

公司最近新建了一个与工厂3类似的新厂，因此，新厂也可以生产两种产品。但是出于管理上的原因，管理层决定只在工厂3、4中选择一个工厂生产，同时要获得最大利润。

单位产品的生产时间 可用时间

A B

工厂1 1 0 4

工厂2 0 2 12

工厂3 3 2 18

工厂4 2 4 28

单位利润 300 500

案例3：

产量x1、x2；工厂3或4是否生产y1、y2

X1<=4

2x2<=12

3x1+2x2<=18+99y2

1

甲乙公司不合作即竞争下所争取到的不同名专业推广者所建立的不同动态规划模

型的组合方案如下：其中X 为可能竞争到的专业推广者人数，即动态规划模型中第一天的 2 专业推广者推

广能力的份数，Y 为第二天需要的专业推广者推广能力的份数，即第三天安排从事推广

工作的专业推广者的人数；Z 为第三天需要的专业推广者推广能力的份数，即第三天安排从事推广工作的专业推广者的人数；a 为x 名专业推广者累计从事培训工作出来的兼职推广者的批数（每批20 人），其中，有多种组合方案；甲公司雇佣这些兼职推广者均工作一天，从事推广工作，第二天辞退a −b批兼职推广员，其余的b批继续从事推广工作一天后辞退，即兼职宣传员总共最多雇佣2 天；cost 为花费的成本，即资金的使用数量；F 为不同方案下所达到的总推广效益。上表可以提供给甲公司做决策依据，根据效益的大小甲公司可以决策的目标方向顺序是从①--⑧，即不合作的情况下甲公司可以尽量争取到9 人，如若不行，考虑争取4 人。§5.4 0—1型整数规划模型

1、 0—1型整数规划模型概述

整数规划指的是决策变量为非负整数值的一类线性规划，在实际问题的应用中，整数规划模型对应着大量的生产计划或活动安排等决策问题，整数规划的解法主要有分枝定界解法及割平面解法（这里不作介绍，感兴趣的读者可参考相关书籍）。在整数规划问题中，0—1型整数规划则是其中较为特殊的一类情况，它要求决策变量的取值仅为0或1，在实际问题的讨论中，0—1型整数规划模型也对应着大量的最优决策的活动与安排讨论，我们将列举一些模型范例，以说明这个事实。

0—1型整数规划的的数学模型为：

目标函数 nnxcxcxczMinMax2211)(

约束条件为：

1 | 0 ) ,() ,() ,(22112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxa, , ,21

第一章（管理科学简介）

Ｐ５（１）管理科学介绍

管理科学本质：是对与定量因素有关的管理问题通过应用科学的方法进行辅助管理决策制定的一门学科．

管理科学发展过程：快速发展开始于２０世纪四五十年代

起初的动力来自于第二次世界大战

另一个里程碑是１９４７年丹捷格发明单纯形罚

更大的推动作用的是计算机革命的爆发

管理决策：管理者考虑管理科学对定量因素进行分析得出的结果后，再考虑管理科学以外的众多无形因素，然后根据其最佳判断做出决策

管理科学小组系统和考察时步骤：定义问题与收集数据——构件数学模型——从模型中形成对于一个问题进行求解的基于计算机的程序——测试模型并在必要时进行修正——应用模型分析问题以及提出管理建议——帮助实施被管理者采纳的小组建议

课后问题：

１．管理科学什么时候有了快速发展？ 快速发展开始于２０世纪四五十年代

２．商学院以外还广泛使用的对管理科学学科的叫法：运筹学

３．管理科学研究提供给管理者什么？

对问题涉及的定量因素进行分析并向开明的管理者提出建议

４．管理科学以哪些领域作为基础？科学领域：数学，计算机 社会领域：经济学

５．什么是决策支持系统？辅助管理决策制定的交互式基于计算机的系统

６．与管理问题有关的一般定量因素有哪些？生产数量，收入，成本，资源

Ｐ１１（２）一个例子：盈亏平衡分析

步骤：分析问题——建立模型——敏感性分析，电子表格模型提供上述三者了方便的途径

如果预测销售数量＜盈亏平衡点，Ｑ＝０

预测销售数量＞盈亏平衡点，Ｑ＝预测销售数量

敏感性分析目的：研究如果一个估计值发生了变化，将会给模型带来什么样的变化

Ｍｉｎ（ａ，ｂ）：取ａ，ｂ中的最小值

Ｉｆ（Ａ，ｂ，ｃ）：如果表达式Ａ为真，则值为ｂ，否则为ｃ

第二章（线性规划：基本概念）

Ｐ３１（３）在电子表格上建立恩德公司问题的模型

１．开始在电子表格上建立线性规划模型时需要回答的三个问题：