运筹学规划问题的一种基于知识的树状表示法_胡祥培

第29卷　第3期1997年6月

哈尔滨工业大学学报

JOU RNA L O F HA RBI N I NST I T U T E OF T ECHN O LOGY

Vol .29,No .3June 1997

收稿日期:1996-11-11

胡祥培,男1962年生,副教授;哈尔滨工业大学管理学院(150001)＊国家自然科学基金(79400006)、中国博士后基金、辽宁省博士科研起动基金、哈工大科研基金(961090-196)资助项目

运筹学规划问题的一种基于知识的树状表示法＊

胡祥培　钱国明　胡运权

(管理学院)

摘　要　根据运筹学实际问题的特点,引入人工智能与知识工程的知识表示理论,提出了一种基于知

识的描述运筹学规划问题的树状表示法,设计建立了智能化的问题描述支持系统,在微机上实现了一个投资问题的知识表示。

关键词　运筹学;问题表示;知识工程;人工智能分类号　O221.3/TP 18

近几年,国内外学者对运筹学问题的知识表

示研究较为活跃,具有代表性的学术观点和方法有:T .P .Liang [1]提出的以实体(entity )—属性(attribute )—子属性(subattribute )所构成的层次

体系表示问题的方法、汪时萍[2]

等提出的基于语义模型的问题描述语言SM -IPDL 等,这些基于知识的问题表示方法与人们习惯的自然语言表示法相比,在问题可辨识性、问题描述结构的可扩性、信息搜索与处理效率、知识推理效率等方面确有较大进步,但它们的可操作性与问题输入的人机界面有待于进一步改进,辨识与推理效率也需进一步提高,目前它们还难以恰当描述运筹学实际应用问题中涉及的图表及函数等符号型知识。为此,本文结合运筹学规划问题的特点,利用人工智能与知识工程理论,提出一种在计算机中描述实际应用问题的树状表示法。

1　运筹学规划问题的树状表示法

1.1　问题描述与树状表示法

规划论是运筹学的主要分支,规划论的应用领域比较广泛,其实际应用问题的形式可能多种多样,但这些问题的实质可以归结为:在一定的人财物力限制下,寻求问题的目标达到最优或者达到目标的差距尽可能的小。实际应用问题的信息可以划分为问题目标信息、约束条件信息等多个信息侧面,每一信息侧面又可分为若干个信息单

元,……,如此妯分下去,可以把实际问题的信息归结成为一种层次化的树状结构。正是由于运筹学问题的信息具有这种层次化的树状结构特征,本文采用一种层次化、结构化的问题描述来表示运筹学实际问题。这种将实际应用问题归结为树状的逻辑结构,并按此结构把实际问题表示为计算机可执行程序的方法称之为问题的树状表示法。

运筹学规划问题的问题描述树之结构如图1所示:

图1　运筹学规划问题的问题的问题描述树

Fig .1　T he problem describing -tree fo r pro gramming

problem in O R

图1所示的问题描述树由节点和边两部分构成。点是描述问题的信息单元,这种信息单元按层次关系依次为问题、信息侧面、语句段、语句子段、…子句。子句是描述动态规划应用问题的基本信息单元,若干条子句构成一个语句子段,若干个语句子段形成一个语句段,若干语句段组成一个信息侧面,所有信息侧面组合成一个完整的问题,这些信息单元之间呈现出层次化、结构化的特征。问题描述树的叶节点—子句描述的是实际问题的数据信息。叶节点以外的树干描述的是实际问题的结构信息。由于不同类型问题之问题描述树的树干及相应节点的名称是不同的,因此,这一树干描述的问题结构信息就为实际问题的识别创造了条件。此外,描述树的边表示父节点与子节点之间的隶属关系。这种隶属关系为知识化数学模型生成过程中的信息快速搜索与推理创造了条件。可见,上述问题描述树在问题可辨识性、问题描述结构的可扩性、信息搜索与处理效率、知识推理效率等方面具有较为明显的优势,并具有描述表格数据、决策树图形及数据、数学函数的能力。

当然,问题描述树反映的还只是问题有关信息的一种逻辑结构,以此结构描述的具体应用问题还需要用具体的计算机语言加以描述才便于在计算机内实现存储,形成一个可执行程序。由于Prolog语言的结构化和模块化程度很高,比较适合把问题描述树所代表的实际应用问题表述成计算机程序语言编写的可执行程序,因此本文将采用Turbo Prolog语言描述运筹学应用问题的原始信息,形成按一定组织结构组合的子句(clauses)集,此子句集构成的可执行程序由于是一种描述相应问题原始信息的语言模型,故可称之为问题的信息模型。下面以一个投资问题为例,阐述用树状表示法予以描述的过程及其内容。

1.2　树状表示法应用举例

(例1)投资决策问题:某公司准备投入3千万元资金对所属3个工厂进行技术改造,投资金额分为0、1、2、3千万元四种额度,经测算得知,每个工厂的投资额与技术改造之后每年新增的效益如下表所示(表1):

问如何在3个工厂之间进行投资分配,使得总的年新增收益值最大?

表1　投资与年新增效益表 单位:千万元

Ta ble1　Investment and its newannual efficency 工厂

投资额

0123工厂1 00.51.22.0

工厂2 00.41.32.2

工厂3 00.61.41.8

这一投资问题的静态数学模型如下:

max　z=?

3

i=1

f i(x i)(1)

S.t.:?

3

i

=1

x i≤3(2)

x i=0,1,2,3(3)式中:x i是第i个工厂的投资额,f i(x i)是第i个工厂的投资额为x i时获得的年新增收益值。

下面采用树状表示法描述这一投资问题:

例1所述的投资问题之问题描述树如图2所示:

图2　投资问题的问题描述树结构图

Fig.2　T he structure o f problem describing-tree

for a investment problem

由于用树状表示法描述投资问题所形成的语言模型—信息模型是一种基于问题描述树逻辑结构的可执行程序,因此,信息模型就具有与问题描述树类似的模型结构—程序结构。图2所示的问题描述树所对应的信息模型的结构如图3所示:

·

9

·

第3期胡祥培等:运筹学规划问题的一种基于知识的树状表示法

图3　投资问题信息模型结构图(程序结构图)

Fig .3　T he structure of message model (program )for a investment problem

图3所示的投资问题信息模型结构可以用

Turbo Prolog 语言的表谓词进行描述,形成该投资问题信息模型的结构信息,它为知识化数学模型生成过程中的信息模型之识别奠定了基础。计算机可以依据不同应用问题在信息模型结构及每一侧面、语句段名称的不相同来识别问题的类型,并采用相应的方法生成知识化数学模型。此外,例1所示的投资问题信息模型各语句段的数据信息可用一阶谓词表示,parag raph of invest -ment stage 的内容为stage (3):parag raph of investment kind 的内容为:investment kinds (4);parag raph of investment number 的内容为:total investment (3),kinds invest -ment (1,0),…kinds investment (4,3);para -g raph of investment profits 的内容为:profit (1,0,0),profit (1,1,0.5),…profit (3,3,1,8);parag raph of problem object 的内容为object (“max ”),其中谓词kind investment (Kings ,Investment )表示某种投资方案的投资金额,谓词profit (Stage ,Investment ,Profits )表示某阶段某一投资额对应的利润。

投资问题信息模型(语句程序)结构信息语句在识别实际应用问题之后,可以由计算机自动生成;其数据信息语句在用户输入实际应用问题的数据之后,由相应的生成模块予以生成。这些工作可以通过设计建立“问题描述支持系统”来实现。

2　树状表示法的实现—问题描述支

持系统

问题描述支持系统负责完成从问题域的确定、问题辨识、启发式问题输入操作窗口的生成直到生成信息模型的问题处理过程。该系统的系统

结构如图4所示[3]:

图4　运筹学规划问题描述支持系统的结构图F ig .4　T he structure of problem description suppo rt

system fo r prog ramming problem in OR

运筹学规划问题的问题描述支持系统的处理流程图如图5所示:

图5　运筹学规划问题的问题描述支持系统的处理流程图Fig .5　T he flow —chart of problem descriptio n suppor t

system for programming in OR

·

10·哈　尔　滨　工　业　大　学　学　报第29卷

在问题描述支持系统中,问题描述知识库是用产生式规则按照层次化、模块化结构组织起来的一种规则库,它在问题辨识、操作窗口及启发引

导信息的生成、信息模型的生成过程中起着十分关键的作用,是本文提出的树状表示法在问题输入及信息模型生成过程中产生智能的源泉。上述问题描述支持系统可以用Turbo Prolog 语言设计和实现,作者在AS T486微机上实现了投资问题和一类服务网点布局问题在计算机中的描述过程。

3　结论

(1)根据运筹学规划论应用问题的特点,引入

人工智能与知识工程的知识表示理论,提出了一种基于知识的描述运筹学规划问题的树状表示法,这一表示法具有良好的问题可辨识性和问题描述结构的可扩性,具有较高的信息搜索与处理效率、辩识与推理效率,并具有描述表格数据、决

策树图形及数据、数学函数的基本能力。

(2)问题描述支持系统为树状表示法在计算机中的实现提供了手段,可以帮助不熟悉运筹学知识的用户较方便地输入和描述问题。问题描述知识库是问题描述过程中使用知识和具有智能的源泉。

参

考

文

献

1　Liang T P .Analogical Reasoning and Case -based Lear n -ing in M odel M anagement Sy stem ,Decision Suppor t sy s -tem ,1993,9(10):137～160

2　汪时萍,张国庆,李心丹。基于语义模型的智能型问题描述语言。决策与决策支持系统,1993,3(3):214～2213　Hu Xiang pei ,et al .A Research on Intelligent M odeling

Suppo rt System fo r Dy namic Prog ramming M odel ,Pro -ceedings of ′96I nterna tio nal Conferenceon M anagement Science &Engineering ,Harbin Institute of Technology Press ,1996.591～597

A Knowledge -based Tree -like Representation for Programming Problems

in Operations Research

Hu Xiangpei Qian Guoming Hu Y unquan

(M anangement School )

Abstract According to the property of realistic problems in Operations Research and applying the theo -ries of know ledge representation in Artificial Intelligence as well as Know ledge Engineering ,this paper presents a knowledge -based tree -like representation to describe program ming problems in Operations Re -search .An intelligent problem description support system has been desig ned and set up .The know ledge representation fo r an investmen problem has been realized in a microcom puter .

Key word Operations research ;problem representation ;know ledge engineering ;artificial intelligence

·

11·第3期胡祥培等:运筹学规划问题的一种基于知识的树状表示法

胡运权运筹学第七章习题解

7.3某厂每月生产某种产品最多600件，当月生产的产品若未销出，就需贮存（刚入库的产品下月不付存储费）月初就已存储的产品需支付存储费，每100件每月1000元。已知每100件产品的生产费为5千元，在进行生产的月份工厂支出经营费4千元，市场需求如表7-19所示，假定1月初及4月底库存量为零，试问每月应生产多少产品，才能在满足需求条件下， 解： 设阶段变量：k=1,2,3 状态变量：k x 第k 个月初的库存量 决策变量：k d 第k 个月的生产量 状态转移方程：1k k k k x x r d 阶段指标：(,)k k k k v x d c d 由于在4月末，仓库存量为0，所以对于k=4阶段来说有两种决策： 5+4=9 40x 4()f x = 1 41x 对K=3 334()54()f x x f x K=2

解得：第一个月生产500份，第二个月生产600份，第三个月生产0份，第四个月生产0份。 7.4某公司有资金4万元，可向A ，B ，C 三个项目投资，已知各项目不同投资额的相应效益值如表7-20所示，问如何分配资金可使总效益最大。 表 7-20 解： 设阶段变量k ，{ }4,3,2,1∈k ，每一个项目表示一个阶段;

状态变量S k，表示可用于第k阶段及其以后阶段的投资金额； 决策变量Ｕk，表示在第k阶段状态为S k下决定投资的投资额； 决策允许集合：0≤Ｕk≤S k 状态转移方程：S k+1=S k-Ｕk; 阶段指标函数：V k(S kＵk)； 最优指标函数：f k(S k)=max{ V k(S kＵk)+ f k+1(S k+1)} 终端条件：f4(x4)=0； K=4, f4(x4)=0 k=3, 0≤Ｕ3≤S3 k=2, 0≤Ｕ2≤S2 k=1, 0≤Ｕ1≤S1 所以根据以上计算，可以得到获得总效益最大的资金分配方案为（1，2，1）.

《运筹学》习题线性规划部分练习题及答案.doc

《运筹学》线性规划部分练习题 一、思考题 1． 什么是线性规划模型，在模型中各系数的经济意义是什么？ 2． 线性规划问题的一般形式有何特征？ 3． 建立一个实际问题的数学模型一般要几步？ 4． 两个变量的线性规划问题的图解法的一般步骤是什么？ 5． 求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？ 6． 什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。 7． 试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。 8． 试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。 9． 在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？ 10．大M 法中，M 的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问题呢？ 11．什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续第二阶段？ 二、判断下列说法是否正确。 1． 线性规划问题的最优解一定在可行域的顶点达到。 2． 线性规划的可行解集是凸集。 3． 如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。 4． 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。 5． 线性规划问题的每一个基本解对应可行域的一个顶点。 6． 如果一个线性规划问题有可行解，那么它必有最优解。 7． 用单纯形法求解标准形式（求最小值）的线性规划问题时，与0 >j σ对应的变量都可以被选作换入变量。 8． 单纯形法计算中，如不按最小非负比值原则选出换出变量，则在下一个解中至少有一个基变量的值是负的。 9． 单纯形法计算中，选取最大正检验数k σ对应的变量k x 作为换入变量，可使目 标函数值得到最快的减少。 10． 一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。 三、建立下面问题的数学模型 1． 某公司计划在三年的计划期内，有四个建设项目可以投资：项目Ⅰ从第一年到 第三年年初都可以投资。预计每年年初投资，年末可收回本利120% ，每年又可以重新将所获本利纳入投资计划；项目Ⅱ需要在第一年初投资，经过两年可收回本利150% ，又可以重新将所获本利纳入投资计划，但用于该项目的最大投资额不得超过20万元；项目Ⅲ需要在第二年年初投资，经过两年可收回本利160% ，但用于该项目的最大投资额不得超过15万元；项目Ⅳ需要在第三年年初投资，年末可收回本利140% ，但用于该项目的最大投资额不得超过10万元。在这个计划期内，该公司第一年可供投资的资金有30万元。问怎样的投资方案，才能使该公司在这个计划期获得最大利润？ 2．某饲养场饲养动物，设每头动物每天至少需要700克蛋白质、30克矿物质、 100克维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量及单 价如下表2—1所示：

运筹学第七章动态规划

习题七7.1计算如图所示的从A 到E 的最短路线及其长度（单位：km ）： （1） 用逆推解法；2用标号法。 7.2 用动态规划方法求解下列问题 （1） max z ＝x 12x 2 x 33 x 1＋x 2＋x 3 ≤6 x j ≥0 （j ＝1,2,3） （2）min z ＝ 3x 12＋4x 22 ＋x 32 x 1x 2 x 3 ≥ 9 x j ≥0 （j ＝1,2,3） 7.3 利用动态规划方法证明平均值不等式： n n n x x x n x x x 12121)()( ≥+++ 设x i ≥0，i ＝1，2，…，n 。 7.4 考虑一个有m 个产地和n 个销地的运输问题。设a i （i ＝1，2，…，m ）为产地i 可发运的物资数，b j （j ＝1，2，…，n ）为销地j 所需要的物资数。又从产地i 到销地j 发运x ij 单位物资所需的费用为h ij （x ij ），试将此问题建立动态规划的模型。 7.5 某公司在今后三年的每一年的开头将资金投入A 或B 项工程，年末的回收及其概率如下表所示。每年至多做一项投资，每次只能投入1000万元。求出三年后所拥有的期望金额达到最大的投资方案。 投 资 回 收 概 率 A 0 0.4 2000 0.6 B 1000 0.9 2000 0.1 7.6 某公司有三个工厂，它们都可以考虑改造扩建。每个工厂都有若干种方案可供选择，各种方案的投资及所能取得的收益如下表所示(单位：千万元)。现公司有资金5千万元，问应如何分配投资使公司的总收益最大?

7.7 某厂准备连续3个月生产A种产品，每月初开始生产。A的生产成本费用为x2，其中x是A产品当月的生产数量。仓库存货成本费是每月每单位为1元。估计3个月的需求量分别为d1＝100，d2＝110，d3＝120。现设开始时第一个月月初存货s0＝0，第三个月的月末存货s3＝0。试问：每月的生产数量应是多少才使总的生产和存货费用为最小。 7.8 设有一辆载重卡车，现有4种货物均可用此车运输。已知这4种货物的重量、容积及价值关系如下表所示。 货物代号重量（吨）容积（立方米）价值（千元） 1 2 2 3 2 3 2 4 3 4 2 5 4 5 3 6 若该卡车的最大载重为15吨，最大允许装载容积为10立方米，在许可的条件下，每车装载每一种货物的件数不限。问应如何搭配这四种货物，才能使每车装载货物的价值最大。 7.9 某警卫部门有12支巡逻队负责4个仓库的巡逻。按规定对每个仓库可分别派2－4支队伍巡逻。由于所派队伍数量上的差别，各仓库一年内预期发生事故的次数如下表所示。试应用动态规划的方法确定派往各仓库的巡逻队数，使预期事故的总次数为最少。 巡逻队数预期事故次数仓库 1 2 3 4 2 18 38 14 34 3 16 36 12 31 4 12 30 11 25 7.10 （生产计划问题）根据合同，某厂明年每个季度末应向销售公司提供产品，有关信息见下表。若产品过多，季末有积压，则一个季度每积压一吨产品需支付存贮费0.2万元。现需找出明年的最优生产方案，使该厂能在完成合同的情况下使全年的生产费用最低。 季度j生产能力a j（吨）生产成本d j（万元/吨）需求量b j（吨） 1 30 15.6 20 2 40 14.0 25 3 25 15.3 30 4 10 14.8 15 （1）请建立此问题的线性规划模型。（提示：设第j季度工厂生产产品x j吨，第j季度初存贮的产品为y j吨，显然y1＝0）（2）请建立此问题的动态规划模型。（均不用求解）

运筹学中线性规划实例汇总

实验报告 课程名称：运筹学导论 实验名称：线性规划问题实例分析专业名称：信息管理与信息系统 指导教师：刘珊 团队成员：邓欣(20112111 蒋青青(20114298 吴婷婷(20112124 邱子群(20112102 熊游(20112110 余文媛(20112125 日期：2013-10-25 成绩：___________

1．案例描述 南部联盟农场是由以色列三个农场组成的联合组织。该组织做出了一个关于农场农作物的种植计划，如下： 每一个农场的农业产出受限于两个量，即可使用的灌溉土地量和用于灌溉的水量。数据见下表： 适合本地区种植的农作物包括糖用甜菜、棉花和高粱。这三种作物的差异在于它们每亩的期望净收益和水的消耗量不同。另外农业部门已经制定了南部联盟农场作物总亩数的最大配额，见下表： 作物的任何组合可以在任何农场种植，技术部门的任务是找出一个种植方案使南部联盟农场的净收益最大化。 2.建立模型 决策变量为Xi(i=1,2,……,9,表示每个农场每种作物的种植量。 MAX Z=1000(X1+X2+X3+750(X4+X5+X6+250(X7+X8+X9 约束条件： （1）每一个农场使用的土地 X1+X4+X7≤400

X2+X5+X8≤600 X3+X6+X9≤300 (2每一个农场的水量分布 3X1+2X4+X7≤600 3X2+2X5+X8≤800 3X3+2X6+X9≤375 (3每一种作物的总种植量 X1+X2+X3≤600 X4+X5+X6≤500 X7+X8+X9≤325 非负约束Xi≥0 , i=1,2, (9) 3.计算机求解过程 步骤1.生成表格 步骤2.输入数据

(完整word版)第二章运筹学 线性规划

第二章 线性规划 主要内容：1、线性规划问题及数学模型 2、线性规划问题的解及其性质 3、图解法 4、单纯形法 5、大M 法和两阶段法 重点与难点：线性规划数学模型的建立：一般形成转化为标准型的方法：单纯形法的求解步骤。 要 求：理解本章内容，掌握本章重点与难点问题；深刻理解线性规划问题的基本概念、基本性质，熟练掌握 其求解技巧；培养解决实际问题的能力。 §1 线性规划的数学模型及解的性质 一、数学模型（一般形式） 例 1 已知某市有三种不同体系的建筑应予修建，其耗用资源数量及可用的资源限量如下表，问不同体系的面积应各建多少，才能使提供的住宅面积总数达到最大？ 解：设三种体系的建筑面积依次为1x ,2x ,3x 万平方米， 则目标函数为 321max x x x z ++= 约束条件为 ?? ?? ???????=≥≤++≤≤++≤++≤++3,2,10 4005.335.41470021015000 180190110200025301211000 122137105 3211321321321j x x x x x x x x x x x x x x j 例2 某工厂要安排生产甲、乙两种产品。已知：

问：如何安排两种产品的生产数量，才能使总产值最高？ 解：设 21,x x 分别为甲、乙两种产品的生产量： 则目标函数为 21127m ax x x z += 约束条件为??? ??? ?=≥≤+≤+≤+2,1,03001032005436049112121j x x x x x x x j 从以上两例可以看出，它们都属于一类优化问题。它们的共同特征： ①每一个问题都有一组决策变量（n x x x 21,）表示某一方案；这组决策变量的值就代表一个具体方案。一般这 些变量的取值是非负的。 ②存在一定的约束条件，这些约束条件可以用一组线性等式或不等式来表示。 ③都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示；按问题的不同，要求目标函数实现最大化或最小化。 满足以上三个条件的数学模型称为线性规划的数学模型。其一般形式为： 目标函数 n n x c x c x c z +++= 2211m ax (m in) 约束条件 ()()()????? ????=≥=≥≤+++=≥≤+++=≥≤+++n j x b x a x a x a b x a x a x a b x a x a x a j m n mn m m n n n n ,,2,1,0,,,22112222212111212111 可行解：满足约束条件的一组决策变量，称为可行解。 最优解：使目标函数取得最大（小）值的可行解，称为最优解。 最优值：目标函数的最大（小）值，称为最优值。 二、标准型 （一）问题的标准形式： n n x c x c x c z +++= 2211ma x ????? ?? ??=≥=+++=+++=+++n j x b x a x a x a b x a x a x a b x a x a x a j m n mn m m n n n n ,,2,1,022112222212111212111

胡运权运筹学第七章习题解

某厂每月生产某种产品最多600件，当月生产的产品若未销出，就需贮存（刚入库的产品下月不付存储费）月初就已存储的产品需支付存储费，每100件每月1000元。已知每100件产品的生产费为5千元，在进行生产的月份工厂支出经营费4千元，市场需求如表7-19所示，假定1月初及4月底库存量为零，试问每月应生产多少产品，才能在满足需求条件下， 解： 设阶段变量：k=1,2,3 状态变量：k x 第k 个月初的库存量 决策变量：k d 第k 个月的生产量 状态转移方程：1 k k k k x x r d 阶段指标：(,)k k k k v x d c d 由于在4月末，仓库存量为0，所以对于k=4阶段来说有两种决策： 5+4=9 40x 4()f x = 1 41x 对K=3 334()54()f x x f x K=2

K=1时 d 5 解得：第一个月生产500份，第二个月生产600份，第三个月生产0份，第四个月生产0份。 某公司有资金4万元，可向A ，B ，C 三个项目投资，已知各项目不同投资额的相应效益值如表7-20所示，问如何分配资金可使总效益最大。 表 7-20

解： 设阶段变量k ，{ }4,3,2,1∈k ，每一个项目表示一个阶段; 状态变量S k ，表示可用于第k 阶段及其以后阶段的投资金额； 决策变量Ｕk ，表示在第k 阶段状态为S k 下决定投资的投资额； 决策允许集合：0≤Ｕk ≤S k 状态转移方程：S k+1=S k -Ｕk ; 阶段指标函数：V k (S k Ｕk )； 最优指标函数：f k (S k )=max{ V k (S k Ｕk )+ f k+1(S k+1)} 终端条件：f 4(x 4)=0； K=4, f 4(x 4)=0 k=3, 0≤Ｕ3≤S 3 k=2, 0≤Ｕ2≤S 2 k=1, 0≤Ｕ1≤S 1

《运筹学》第五章习题及答案

《运筹学》第五章习题及答案 《运筹学》第五章习题 1．思考题 （1）试述动态规划的“最优化原理”及它同动态规划基本方程之间的关系。（2）动态规划的阶段如何划分？ （3）试述用动态规划求解最短路问题的方法和步骤。 （4）试解释状态、决策、策略、最优策略、状态转移方程、指标函数、最优值函数、边界函数等概念。 （5）试述建立动态规划模型的基本方法。 （6）试述动态规划方法的基本思想、动态规划的基本方程的结构及正确写出动态规划基本方程的关键步骤。 2．判断下列说法是否正确 （1）动态规划分为线性动态规划和非线性动态规划。 （2）动态规划只是用来解决和时间有关的问题。 （3）对于一个动态规划问题，应用顺推法和逆推法可能会得到不同的最优解。 （4）在用动态规划的解题时，定义状态时应保证各个阶段中所做的决策的相互独立性。 （5）在动态规划模型中，问题的阶段等于问题的子问题的数目。（6）动态规划计算中的“维数障碍”，主要是由于问题中阶段数的急剧增加

而引起的。 3．计算下图所示的从A到E的最短路问题 4．计算下图所示的从A到E的最短路问题 5．计算从A到B、C、D的最短路线。已知各线段的长度如下图所示。 6．设某油田要向一炼油厂用管道供应油料，管道铺设途中要经过八个城镇，各 城镇间的路程如下图所示，选择怎样的路线铺设，才使总路程最短？

7．用动态规划求解下列各题 （1）．2 22211295m a x x x x x z-+-=； ?? ?≥≤+0,52 121x x x x； （2）． 3 3 221m a x x x x z= ?? ?≥≤++0,,6321 321x x x x x x； 8．某人外出旅游，需将3种物品装入背包，但背包重量有限制，总重量不超过 10千克。物品重量及其价值等数据见下表。试问每种物品装多少件，使整个背包的价值最大？ 913千克。物品重量及其价值的关系如表所示。试问如何装这些物品，使整个背包价值最大？

《运筹学》之线性规划 (2)

运筹学 线性规划基本性质

线形规划基本性质目录 线性规划（概论） 线性规划问题:生产计划问题 例1.1 生产计划问题（资源利用问题）例1.1生产计划问题分析 例1.1生产计划问题模型 例1.1生产计划问题表格描述 例1 .2 营养配餐问题 各种食物的营养成分表 各种食物的营养成分表（转置） 例1 .2 营养配餐问题求解 用于成功决策的实例 线形规划的一般模型:特点 线形规划的一般模型:数学模型线性规划问题隐含的假定 比例性假定 可加性假定 连续性假定 确定性假定 线形规划的图解法 线形规划解的可能结果 线形规划的标准形式1 线形规划的标准形式2 非标准型LP的标准化:目标函数 非标准型LP的标准化:约束函数1 非标准型LP的标准化:约束函数2 非标准型LP的标准化:决策变量 线形规划解的概念：可行解 线形规划解的概念：最优解 线形规划解的概念：基本解 线形规划解的概念：最优基本解 线形规划的应用模型 生产计划问题 生产计划问题：表格分析 生产计划问题：模型 产品配套问题 产品配套问题：工时分析 产品配套问题：配套分析 产品配套问题：模型 结束放映

线性规划（概论） 线形规划是研究解决有限资源最佳分配的运筹学方法，即如何对有限的资源做出最佳方式的调配和最有利的利用，以便最充分地发挥资源的效能去获得最佳经济效益。

线性规划问题:生产计划问题 1、如何合理使用有限的人力、物力和资 金，实现最好的经济效益。 2、如何合理使用有限的人力、物力和资 金，以达到最经济的方式，完成生产 计划的要求。

例1.1 生产计划问题（资源利用问题） 胜利家具厂生产桌子和椅子两种家具。桌子售价50元/张，椅子销售价格30元/把，生产桌子和椅子要求需要木工和油漆工两种工种。生产一张桌子需要木工4小时，油漆工2小时。生产一把椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？

运筹学--第七章 动态规划

１８９ 习题七7.1计算如图所示的从A 到E 的最短路线及其长度（单位：km ）： （1） 用逆推解法；2用标号法。 7.2 用动态规划方法求解下列问题 （1） max z ＝x 12x 2 x 33 x 1＋x 2＋x 3 ≤6 x j ≥0 （j ＝1,2,3） （2）min z ＝ 3x 12＋4x 22 ＋x 32 x 1x 2 x 3 ≥ 9 x j ≥0 （j ＝1,2,3） 7.3 利用动态规划方法证明平均值不等式： n n n x x x n x x x 12121)()( ≥+++ 设x i ≥0，i ＝1，2，…，n 。 7.4 考虑一个有m 个产地和n 个销地的运输问题。设a i （i ＝1，2，…，m ）为产地i 可发运的物资数，b j （j ＝1，2，…，n ）为销地j 所需要的物资数。又从产地i 到销地j 发运x ij 单位物资所需的费用为h ij （x ij ），试将此问题建立动态规划的模型。 7.5 某公司在今后三年的每一年的开头将资金投入A 或B 项工程，年末的回收及其概率如下表所示。每年至多做一项投资，每次只能投入1000万元。求出三年后所拥有的期望金额达到最大的投资方案。 投 资 回 收 概 率 A 0 0.4 2000 0.6 B 1000 0.9 2000 0.1 7.6 某公司有三个工厂，它们都可以考虑改造扩建。每个工厂都有若干种方案可供选择，各种方案的投资及所能取得的收益如下表所示(单位：千万元)。现公司有资金5千万元，问应如何分配投资使公司的总收益最大?

7.7 某厂准备连续3个月生产A种产品，每月初开始生产。A的生产成本费用为x2，其中x是A产品当月的生产数量。仓库存货成本费是每月每单位为1元。估计3个月的需求量分别为d1＝100，d2＝110，d3＝120。现设开始时第一个月月初存货s0＝0，第三个月的月末存货s3＝0。试问：每月的生产数量应是多少才使总的生产和存货费用为最小。 7.8 设有一辆载重卡车，现有4种货物均可用此车运输。已知这4种货物的重量、容积及价值关系如下表所示。 货物代号重量（吨）容积（立方米）价值（千元） 1 2 2 3 2 3 2 4 3 4 2 5 4 5 3 6 若该卡车的最大载重为15吨，最大允许装载容积为10立方米，在许可的条件下，每车装载每一种货物的件数不限。问应如何搭配这四种货物，才能使每车装载货物的价值最大。 7.9 某警卫部门有12支巡逻队负责4个仓库的巡逻。按规定对每个仓库可分别派2－4支队伍巡逻。由于所派队伍数量上的差别，各仓库一年内预期发生事故的次数如下表所示。试应用动态规划的方法确定派往各仓库的巡逻队数，使预期事故的总次数为最少。 巡逻队数预期事故次数仓库 1 2 3 4 2 18 38 14 34 3 16 36 12 31 4 12 30 11 25 7.10 （生产计划问题）根据合同，某厂明年每个季度末应向销售公司提供产品，有关信息见下表。若产品过多，季末有积压，则一个季度每积压一吨产品需支付存贮费0.2万元。现需找出明年的最优生产方案，使该厂能在完成合同的情况下使全年的生产费用最低。 季度j生产能力a j（吨）生产成本d j（万元/吨）需求量b j（吨） 1 30 15.6 20 2 40 14.0 25 3 25 15.3 30 4 10 14.8 15 （1）请建立此问题的线性规划模型。（提示：设第j季度工厂生产产品x j吨，第j季度初存贮的产品为y j吨，显然y1＝0）（2）请建立此问题的动态规划模型。（均不用求解） １９０

运筹学各章的题

《运筹学》各章的作业 ----复习思考题及作业题 第一章绪论 复习思考题 1、从运筹学产生的背景认识本学科研究的内容和意义。 2、了解运筹学的内容和特点，结合自己的理解思考学习的方法和途径。 3、体会运筹学的学习特征和应用领域。 第二章线性规划建模及单纯形法 复习思考题 1、线性规划问题的一般形式有何特征？ 2、建立一个实际问题的数学模型一般要几步？ 3、两个变量的线性规划问题的图解法的一般步骤是什么？ 4、求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？ 5、什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。 6、试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。 7、试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。 8、在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？ 9、大M 法中，M 的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问题呢？ 10、什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续第二阶段？ 作业题: 1、把以下线性规划问题化为标准形式： (1) max z= x1-2x2+x3 s.t. x1+x2+x3≤12 2x1+x2-x3≥ 6 -x1+3x2＝9 x1, x2, x3≥0 (2) min z= -2x1-x2+3x3-5x4 s.t x1+2x2+4x3-x4≥ 6 2x1+3x2-x3+x4＝12 x1+x3+x4≤ 4 x1, x2, x4≥0

运筹学-线性规划模型在实际生活中的应用

线性规划模型在实际生活中的应用 【摘要】线性规划在实际生活中扮演着很重要的角色，研究对象是计划管理工作中有关安排和估值的问题,其广泛应用于经济等领域，是实际生活中进行管理决策的最有效的方法之一。解决的主要问题是在给定条件下,按某一衡量指标来寻找安排的最优方案。本文通过对例题利用线性规划分析，如何合理的分配利用，最终找到最优解使企业利润最大，说明了线性规划在实际生活中的应用，而且对线性规划问题模型的建立，模型的解进行了分析，运用图解法和单纯形法解决问题。 【关键词】线性规划、建模、实际生活、图解法、单纯形法 前言：线性规划（Linear programming,简称LP）是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法。英文缩写LP。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。 在实际生活中，经常会遇到一定的人力、物力、财力等资源条件下，如何精打细算巧安排，用最少的资源取得最大的效益的问题，而这正是线性规划研究的基本内容，它在实际生活中有着非常广泛的应用．任何一个组织的管理者都必须对如何向不同的活动分配资源的问题做出决策，即如何有效地利用人力、物力完成更多的任务，或在预定的任务目标下如何耗用最少的人力、物力去实现目标。在许多情况下，大量不同的资源必须同时进行分配，需要这些资源的活动可以是不同的生产活动，营销活动，金融活动或者其他一些活动。随着计算技术的不断发展，使成千上万个约束条件和决策变量的线性规划问题能迅速地求解，更为线性规划在经济等各领域的广泛应用创造了极其有利的条件。线性规划已经成为现代化管理的一种重要的手段。本文运用常用的图解法和单纯形法解决利润最大化决

运筹学线性规划习题.doc

一、需要掌握的主要内容 1、单纯形法的计算过程 （1）确定初始基本可行解 （2）最优性检验； （3）基变换。 2、单纯形法的灵敏度分析 （1）最终单纯形表中，变量系数的灵敏度分析针对最优解不变时，判断其变化范围； （2）约束条件常数项b的灵敏度分析针对最优解不变时，判断其变化范围； （3）增加一个变量的灵敏度分析 首先，确定增加变量在初始单纯形表中的系数列P j ；然后，求出其对应在最终单纯形表 中的系数列P j ；最后求出σ j =C j -C B B-1P j 。 若σ j ≤0，则最优解不变；σ j ≥0，则继续进行基变换，直到求出最优解。 二、需要基本掌握的内容 1、解、基本解、可行解、基本可行解等基本概念； 2、利用单纯形法求解如何判断无可行解、无界解和无穷最优解等基本理论； 3、如何写出一个线性规划的对偶问题； 4、对偶单纯形法的基本思路和过程。 一、填空题 （1）线性规划模型中，松弛变量的经济意义是，它在目标函数中的系数是。 （2）设有线性规划问题：max z=CX AX≤b X≥0 有一可行基B，记相应基变量为X B ,非基变量为X N ，则可行解的定义为，基本可行 解的定义为，B为最优基的条件是。 （3）线性规划模型具有可行域，若其有最优解，必能在上获得。 二、选择题 1．线性规划一般模型中，自由变量可以用两个非负变量的（）代换。 A．和 B．差 C．积 D．商 2．满足线性规划问题全部约束条件的解称为（） A．最优解 B．基本解 C．可行解 D．多重解 3．当满足最优检验，且检验数为零的变量的个数大于基变量的个数时，可求得（） A．多重解 B．无解 C．无界解 D．退化解 4．原问题与对偶问题的（）相同。 A．最优解 B．最优目标值 C.解结构 D．解的分量个数 5.记线性规划原问题（p）max z=CX，对偶问题（D） min w=Yb AX≤b YA≥C

运筹学线性规划

1 人力资源分配的问题 例1.某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下： 设司机和乘务人员分别在各时间段开始时上班，并连续工作八小时，问该公交线路怎样安排 司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员? 分析：不同上班班次时段的司机和乘务人员数 （图见书） 解：设 xi 表示第i 班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。 ?? ? ??? ???? ? =≥≥+≥+≥+≥+≥+≥++++++=6,,2,1030205060 7060.6554433221616 54321 j x x x x x x x x x x x x x t s x x x x x x minZ j 且为整数 例2．一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？

解：设xi ( i = 1,2,…,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。 （图见书） ?? ? ??? ? ? ???? ?=≥≥++++≥++++≥++++≥++++≥++++≥++++≥++++++++++=7,6,,2,1028311925241528.432173217621765176547654365432543217654321 j x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x t s x x x x x x x minZ j 且为整数 约束条件：目标函数： 2 生产计划的问题 例3.某企业生产甲、乙、丙三种产品，每一产品均须经过A 、B 两道工序。A 工序有两种设备可完成，B 工序有三种设备可完成，除甲产品和乙产品的A 工序可随意安排外，其余只能在要求的设备上完成。加工单位产品所需工序时间及其他各项数据的费用有关资料见下表。试制订利润最大的产品加工方案。 （图见书） 解：用8个单下标变量分别表示3种产品在相应工序中的生产量，如表所示。 在约束条件中需考虑 x1+x2=x3+x4+x5 线性规划模型的目标函数为： max z=[(1.25-0.25)(x1+x2)+(2-0.35)(x6+x7)+(2.8-0.5)x8] - [0.05(5x1+10x6)+0.0321(7x2+9x7+12x8)+0.0625(6x3+8x6+8x7)+0.111857(4x4+11x8)+0.05×7x5] 即:max z=0.75x1+0.7753x2+0.65x6+0.8611x7+0.6844x8-0.375x3-0.4474x4-0.35x5 该问题线性规划模型为： max z= 0.75x1+0.7753x2+0.65x6+0.8611x7+0.6844x8-0.375x3-0.4474x4-0.35x5 ? ????? ??? ??=≥=---+≤≤+≤++≤++≤+8 ,,2,1004000770001144000886100012976000105..543215 8476387261 j x x x x x x x x x x x x x x x x x t s j 3 套裁下料问题 例4.现要做100套钢架，每套用长为2.9m,2.1m 和1.5m 的圆钢各一根。已知原料长7.4m ，问应如何下料使所用料最省？ 若用套裁，下面有几种套裁方案，都可以考虑采用

运筹学 线性规划在管理中的应用案例

第五章线性规划在管理中的应用 某企业停止了生产一些已经不再获利的产品，这样就产生了一部分剩余生产力。管理层考虑将这些剩余生产力用于新产品Ⅰ、Ⅱ、Ⅲ的生产。可用的机器设备是限制新产品产量的主要因素，具体数据如下表： 司的利润最大化。 1、判别问题的线性规划数学模型类型。 2、描述该问题要作出决策的目标、决策的限制条件以及决策的总绩效测度。 3、建立该问题的线性规划数学模型。 4、用线性规划求解模型进行求解。 5、对求得的结果进行灵敏度分析（分别对最优解、最优值、相差值、松驰/剩余量、对偶价格、目标函数变量系数和常数项的变化范围进行详细分析）。 6、若销售部门表示，新产品Ⅰ、Ⅱ生产多少就能销售多少，而产品Ⅲ最少销售18件，请重新完成本题的1-5。 解： 1、本问题是资源分配型的线性规划数学模型。 2、该问题的决策目标是公司总的利润最大化，总利润为： + + 决策的限制条件： 8x1+ 4x2+ 6x3≤500 铣床限制条件 4x1+ 3x2≤350 车床限制条件 3x1 + x3≤150 磨床限制条件 即总绩效测试（目标函数）为： max z= + + 3、本问题的线性规划数学模型 max z= + + S．T． 8x1+ 4x2+ 6x3≤500 4x1+ 3x2≤350 3x1 + x3≤150 x1≥0、x2≥0、x3≥0 4、用Excel线性规划求解模板求解结果：最优解（50，25，0），最优值：30元。 5、灵敏度分析

目标函数最优值为 : 30 变量最优解相差值 x1 50 0 x2 25 0 x3 0 .083 约束松弛/剩余变量对偶价格 1 0 .05 2 75 0 3 0 .033 目标函数系数范围 : 变量下限当前值上限 x1 .4 .5 无上限 x2 .1 .2 .25 x3 无下限 .25 .333 常数项数范围 : 约束下限当前值上限 1 400 500 600 2 275 350 无上限 3 150 （1）最优生产方案： 新产品Ⅰ生产50件、新产品Ⅱ生产25件、新产品Ⅲ不安排。最大利润值为30元。 （2）x3 的相差值是意味着，目前新产品Ⅲ不安排生产，是因为新产品Ⅲ的利润太低，若要使新产品Ⅲ值得生产，需要将当前新产品Ⅲ利润元/件，提高到元/件。 （3）三个约束的松弛/剩余变量0，75，0，表明铣床和磨床的可用工时已经用完，而车床的可用工时还剩余75个工时； 三个对偶价格，0，表明三种机床每增加一个工时可使公司增加的总利润额。 （4）目标函数系数范围 表明新产品Ⅰ的利润在元/件以上，新产品Ⅱ的利润在到之间，新产品Ⅲ的利润在以下，上述的最佳方案不变。 （5）常数项范围 表明铣床的可用条件在400到600工时之间、车铣床的可用条件在275工时以上、磨铣床的可用条件在到工时之间。各自每增加一个工时对总利润的贡献元，0元，元不变。 6、若产品Ⅲ最少销售18件，修改后的的数学模型是： max z= + + S．T． 8x1+ 4x2+ 6x3≤500 4x1+ 3x2≤350 3x1 + x3≤150 x3≥18 x1≥0、x2≥0、x3≥0 这是一个混合型的线性规划问题。 代入求解模板得结果如下： 最优解（44，10，18），最优值：元。 灵敏度报告： 目标函数最优值为 : 变量最优解相差值 x1 44 0 x2 10 0 x3 18 0 约束松弛/剩余变量对偶价格