运筹学线性规划模型及目标规划模型

第一节目标规划实例与模型
看起来有 点繁～ 有点 ‘烦’… … …★
因此其目标规划的数学模型： minz=p1d1++p2(d2-+d2+)+p3d3s.t 2x1+x2≤11 x1-x2+d1--d1+=0 x1+2x2+d2--d2+=10 8x1+10x2+d3--d3+=56 x1,x2≥0,di-,di+≥0，i=1,2,3
第一节目标规划实例与模型
(5)目标函数—准则函数 目标函数是由各目标约束的正负偏差变量及其相应 的优先级、权因子构成的函数，且对这个函数求极小值， 其中不包含决策变量xi.因为决策者的愿望总是希望尽可能 缩小偏差，使目标尽可能达到理想值，因此目标函数总是 极小化。有三种基本形式：
第一节目标规划实例与模型
第一节目标规划实例与模型
(4)优先级与权因子 多个目标之间有主次缓急之分，凡要求首先达到的目 标，赋于优先级p1,要求第2位达到的目标赋于优先级 p2,…设共有k0个优先级则规定 p1>>p2>>p3……Pk0>0 P1优先级远远高于p2,p3，只有当p1级完成优化后，再考 虑p2,p3。反之p2在优化时不能破坏p1级的优先值，p3级 在优化时不能破坏p1,p2已达到的优值 由于绝对约束是必须满足的约束，因此与绝对约束相 应的目标函数总是放在p1级
第一节目标规划实例与模型
该问题的决策目标是： （1）总利润最大； （2）尽可能少加工； （3）尽可能多销售电扇； （4）生产数量不能超过预销售数量。 （5）绝对目标约束。所谓绝对目标约束就是必须要严格 满足的约束。绝对目标约束是最高优先级，在考虑较低 优先级的目标之前它们必须首先得到满足。

凸集的数学定义:设K为n维欧氏空间的一个点集，若K中任意两个 点X1和X2连线上的所有点都属于K，即“X =αX1+(1-α) X2 ∈ K(0≤a ≤ 1)”，则称K为凸集。设X(x1，x2，…，xn)，X1(u1， u2，...，un)，X2(v1，v2，…，vn)，如图1一5所示，“X =αX1+(1α) X2 ∈ K(0≤a ≤ 1)”的证明思路如下:
下一页 返回
图解法步骤：
（1）建立坐标系； （2）将约束条件在图上表示； （3）确立满足约束条件的解的范围； （4）绘制出目标函数的图形 （5）确定最优解
用图解法求解下列线性规划问题
max z 2x1 3x2
4x1 0x2 16
s.t
10xx11
4x2 2x2
12 8
x1, x2 0
1. 1.1问题举例
(1)生产计划问题。 生产计划问题是典型的已知资源求利润最大化的问题，对于此类
问题通常有三个假设:①在某一计划期内对生产做出的安排;②生产 过程的损失忽略不计;③市场需求无限制，即假设生产的产品全部 卖出。
下一页 返回
1.一般线性规划问题的数学模型
例1 用一块连长为a的正方形铁皮做一个容 器，应如何裁剪，使做成的窗口的容积为最 大？
解：设 x1, x2分别表示从A,B两处采购的原油量（单
位：吨），则所有的采购方案的最优方案为：
min z 200x1 290x2
0.15x1 0.50x2 150000
s.t
0.20x1 0.50x1
0.30x2 0.15x2
120000 120000
x1 0, x2 0
1. 1线性规划问题与模型
也可以写成模型(1-6)和模型(1-7)的形式，其中模型(1-7)较为常用。

2
7.1 运输问题模型
1.运输问题模型概述
运输问题是一类特殊的线性规划模型，该模型的建立最 初用于解决一个部门的运输网络所要求的最经济的运输路线
和产品的调配问题，并取得了成功.然而，在实际问题的应
用中，除运输问题外，许多非运输问题的实际问题一样可以 建立其相应的运输问题模型，并由此而求出其最优解.下面
们将列举一些模型范例，以说明这个事实.
27
0—1型整数规划的数学模型为：
m a x (m in ) z c 1 x 1 c 2 x 2
a 1 1 x1 a 1 2 x 2 a x a 22 x 2 21 1 s.t. a x a x m2 2 m1 1 x1 , x 2 ,
x ij 1 0
ij
( i , j 1, 2 ,..., n )
，
指派第 i 人完成第 不指派第
j 项任务 j 项任务
i 人完成第
数学模型为：
min Z
n

c ij x ij
x ij 1 i 1 n s .t . x ij 1 j 1 x 0或 1 ij
25
4.整数规划的求解方法 （1）分枝定界法－可求纯或混合整数线性规划。 （2）割平面法－可求纯或混合整数线性规划 （3）隐枚举法－求解“0-1”整数规划：①过滤隐枚举法 ；②分枝隐枚举法。 （4）匈牙利法－解决指派问题（“0-1”规划特殊情形） （5）蒙特卡洛法－求解各种类型规划。 这里不一一介绍，感兴趣的同学再去查找相关资料。
8
m
n
(7.1.1)
m
当然，在实际问题的应用中，常出现产销不平衡的情 形，此时，需要把产销不平衡问题转化为产销平衡问题来进

运筹学模型的类型运筹学模型是指通过数学方法来描述和解决复杂问题的一种工具。

根据问题的性质和要求，运筹学模型可以分为以下几种类型：1. 线性规划模型（Linear Programming Model，简称LP）：线性规划是一种优化问题，它的目标是在满足一些约束条件下，使某个线性函数取得最大或最小值。

线性规划模型广泛应用于生产调度、资源分配、物流运输等领域。

2. 整数规划模型（Integer Programming Model，简称IP）：整数规划是线性规划的扩展，它要求决策变量只能取整数值。

整数规划模型常用于生产调度、排产计划、网络设计等问题。

3. 非线性规划模型（Nonlinear Programming Model，简称NLP）：非线性规划是一种优化问题，它的目标函数和约束条件都可以是非线性的。

非线性规划模型广泛应用于经济学、金融学、工程学等领域。

4. 动态规划模型（Dynamic Programming Model，简称DP）：动态规划是一种优化方法，它将一个复杂问题分解为若干个子问题，并逐步求解这些子问题。

动态规划模型常用于生产调度、资源分配、投资决策等问题。

5. 排队论模型（Queuing Theory Model，简称QT）：排队论是一种研究等待线性的数学理论，它可以用来描述和分析顾客到达、服务时间、系统容量等因素对系统性能的影响。

排队论模型广泛应用于交通运输、通信网络、医疗卫生等领域。

6. 决策树模型（Decision Tree Model，简称DT）：决策树是一种分类和回归的方法，它可以将一个问题分解为若干个子问题，并逐步求解这些子问题。

决策树模型常用于金融风险评估、医学诊断、市场营销等领域。

总之，不同类型的运筹学模型适用于不同的问题领域和求解目标，选择合适的模型可以帮助我们更好地解决实际问题。

史新峰
西安邮电大学 现代邮政学院
Xi'an post and telecommunications university modern post College
第一章 线性规划与单纯形法
1.1线性规划问题及模型 运 筹 学
主要内容
01 线性规划问题
运
02 线性规划模型及特征
筹
学
一 线性规划问题
二 线性规划模型
2.线性规划模型的一般形式
运 筹 学
二 线性规划模型
简写式
运 筹 学
n
max（或 min）Z c j x j j 1
s.t.
n
aij x j
(或 ，)bi
j1
xj 0
i 1,，m j 1,, n
二 线性规划模型
运向量式 筹 学
max（或 min ） Z CX
星期 需要人数 星期 需要人数
运
一
300
五
480
筹
二
300
六
600
学
三
350
日
550
四
400
应如何安排每天的上班人数，使商场总的营业员最少。
一 线性规划问题
在上班 周 周 周 周 周 周 周 一二三四五六日
开始上班
周一
周二
运
周三
筹
周四
学
周五 周六
周日
一 线性规划问题
解：设xj(j=1，2，…，7)为休息2天后星期一到星
期日开始上班的营业员，则这个问题的线性规划模型为
min Z x1 x2 x3 x4 x5 x6 x7
x1 x4 x5 x6 x7 300
x1

目标规划
(Goal programming)
目标规划概述 目标规划的数学模型
目标规划的图解法 目标规划的单纯形法
一、目标规划概述
目标规划是在线性规划的基础上，为适应经济管理 中多目标决策的需要而逐步发展起来的一个分支。
（一）、目标规划与线性规划的比较
1、线性规划只讨论一个线性目标函数在一组线性约束 条件下的极值问题；而目标规划是多个目标决策，可求 得更切合实际的解。
（二）、目标规划的基本概念
例题4—1
线性规划模型为：
maxZ = 8x1 + 10 x2 2x1 + x2 ≤11 ①
x1 +2x2 ≤10 ②
x1, x2≥0 X*=(4,3)T Z*=62
目标函数的地位突出，约束条件是必须严 格满足的等式或不等式，是绝对化的“硬约 束”，此种问题若要求太多时，很容易相互矛 盾，得不到可行解。如根据市场情况再加以下 要求：
目标值之间的差异,记为 d 。 正偏差变量：表示实现值超过目标值的部分，记为 d
＋。 负偏差变量：表示实现值未达到目标值的部分，记为
d－。
在一次决策中，实现值不可能既超过目标值又未达到 目标值，故有 d＋× d－ ＝0,并规定d＋≥0, d－≥0
当完成或超额完成规定的指标则表示：d＋≥0, d－＝0 当未完成规定的指标则表示： d＋＝0, d－≥0 当恰好完成指标时则表示： d＋＝0, d－＝0 ∴ d＋× d－ ＝0 成立。
后面乘任意大的数还是小。必须“满足”第一级才能 “满足”第二级，依次类推。
权系数ωlk ：区别具有相同优先因子的两个目标的 重要性差别，决策者可视具体情况而定。 （优先因子和权系数的大小具有主观性和模糊性，它 不是运筹学本身的问题，主要是决策人自身的经验， 可用专家评定法给以量化。）

运筹学模型的分类和类型运筹学是一门应用于决策制定和问题解决的学科，它通过数学模型和分析方法来优化资源的利用。

运筹学模型是在特定情境中描述问题和优化目标的数学表示。

根据问题的性质和优化目标的类型，运筹学模型可以被分类为多种类型。

在本文中，我将介绍一些常见的运筹学模型分类。

一、线性规划模型：线性规划模型是最基本的运筹学模型之一。

它的特点是目标函数和约束条件均为线性的。

线性规划模型常用于求解资源分配、生产计划、物流运输等问题。

通过线性规划模型，我们可以找到使资源利用最优化的决策方案。

某公司需要确定每种产品的生产数量，以最大化总利润，且需满足各种资源约束条件，这时可以使用线性规划模型进行求解。

二、整数规划模型：整数规划模型是在线性规划模型的基础上引入整数变量的扩展。

在某些情况下，问题的决策变量只能取整数值，这时就需要使用整数规划模型进行求解。

某物流公司需要确定车辆的调度方案，每辆车的装载量可以是整数，这时可以使用整数规划模型来求解最佳调度方案。

三、动态规划模型：动态规划模型是一种考虑时间因素的决策模型。

它通常用于求解多阶段决策问题。

动态规划模型通过将问题划分为多个阶段，并建立各阶段之间的转移方程，来寻找最优决策序列。

在项目管理中，我们需要确定每个阶段的最佳决策，以最小化总工期和成本，这时可以使用动态规划模型进行求解。

四、网络流模型：网络流模型是一种描述网络中资源分配和流量传输的模型。

它通常用于求解网络优化问题，如最小费用流问题、最大流问题等。

网络流模型中，节点表示资源或流量的源点、汇点和中间节点，边表示资源或流量的传输通道。

通过建立网络流模型，我们可以确定资源的最优分配方案，以及网络中的最大流量或最小成本。

在供应链管理中，我们需要确定货物从生产商到消费者的最佳流向，以最小化总运输成本，这时可以使用网络流模型进行求解。

五、排队论模型：排队论模型是一种描述排队系统的模型。

它通常用于评估系统性能指标，如平均等待时间、平均逗留时间等。

《运筹学》教案-目标规划数学模型第一章：目标规划概述1.1 目标规划的定义与意义1.2 目标规划与其他规划方法的区别1.3 目标规划的应用领域1.4 目标规划的发展历程第二章：目标规划的基本原理2.1 目标规划的基本假设2.2 目标规划的数学模型2.3 目标规划的求解方法2.4 目标规划的评估与决策第三章：目标规划的数学模型3.1 单一目标规划模型3.2 多目标规划模型3.3 带约束的目标规划模型3.4 动态目标规划模型第四章：目标规划的求解方法4.1 线性规划求解方法4.2 非线性规划求解方法4.3 整数规划求解方法4.4 遗传算法求解方法第五章：目标规划的应用案例5.1 生产计划目标规划案例5.2 人力资源规划目标规划案例5.3 投资组合目标规划案例5.4 物流配送目标规划案例第六章：目标规划的高级应用6.1 目标规划在供应链管理中的应用6.2 目标规划在项目管理中的应用6.3 目标规划在金融管理中的应用6.4 目标规划在能源管理中的应用第七章：目标规划的软件工具7.1 目标规划软件工具的介绍7.2 常用目标规划软件工具的操作与应用7.3 目标规划软件工具的选择与评估7.4 目标规划软件工具的发展趋势第八章：目标规划在实际问题中的应用8.1 目标规划在制造业中的应用案例8.2 目标规划在服务业中的应用案例8.3 目标规划在政府决策中的应用案例8.4 目标规划在其他领域的应用案例第九章：目标规划的局限性与挑战9.1 目标规划的局限性分析9.2 目标规划在实际应用中遇到的问题9.3 目标规划的发展趋势与展望9.4 目标规划的未来研究方向10.1 目标规划的意义与价值10.2 目标规划在国内外的发展现状10.3 目标规划在未来的发展方向10.4 对运筹学领域的发展展望重点和难点解析重点环节一：目标规划的数学模型补充和说明：在讲解目标规划的数学模型时，重点关注单一目标规划模型和多目标规划模型的构建。

线性规ቤተ መጻሕፍቲ ባይዱ的某些特殊情况，例如网络流、多商品流量等问题， 都被认为非常重要，并有大量对其算法的专门研究。很多其他 种类的最优化问题算法都可以分拆成线性规划子问题，然后求 得解。
在历史上，由线性规划引申出的很多概念，启发了最优化理论 的核心概念，诸如“对偶”、“分解”、“凸性”的重要性及 其一般化等。同样的，在微观经济学和商业管理领域，线性规 划被大量应用于解决收入极大化或生产过程的成本极小化之类 的问题。
二、线性规划问题及其数学模型
2.1 问题的提出及模型建立
在生产管理和经营活动中经常提出一类问题，即如何合 理利用有限的人力、物力、财力等资源，以便得到更好 的经济效果。
例：某工厂在计划内要安排生产甲，乙两种产品，已知 成产单位产品所需的设备台时及A,B两种原材料的消耗， 如下表：
甲
设备
1
原材料A
Q2 (4,2)
Q1 4
Z=2x1+3x2
从图解法中直观地见到 ，当线性规划问题的可 行性域非空时，它是有 界或无界凸多边形。若 线性规划问题存在最优 解，它一定在有界可行 域的某个顶点得到；若 在两个顶点同时得到最 优解，则它们连线上的 任意一点都是最优解， 即有无穷多最优解。
x1
简单地说，这也算线性 规划的几何意义。
（3）都有一个要求达到的目标，它可以用决策变量及其 有关的价值系数构成的线性函数（称为目标函数）来表示。 按照问题的不同，要求的目标函数实现最大化或最小化。
满足以上三个条件的数学模型称为线性规划的数学模型。 其一般形式如下：
二、线性规划问题及其数学模型
一般形式：
目标函数： max(min) z = c1x1+c2x2+···+cnxn 满足约束条件： a11x1+a12x2+···+a1nxn≤(=, ≥)b1

目标：用料最少
一、 线性规划的数学模型
（一）线性规划数学模型
以上例子表明，线性规划问题具有以下特征： ①每一个问题都用一组未知变量（x1，x2，…，xn）表示某一规 划方案，其一组定值代表一个具体的方案，而且通常要求这些未 知变量的取值是非负的。
②每一个问题的组成部分：一是目标函数，按照研究问题的不同， 常常要求目标函数取最大或最小值；二是约束条件，它定义了一 种求解范围，使问题的解必须在这一范围之内。
二 线性规划的标准形式
（二）化为标准形式的方法
2.约束方程化为标准形式的方法
若第k个约束方程为不等式，即
ak1 x1 ak 2 x2 akn xn ()bk
引入松弛变量 x nk 0, K个方程改写为：
ak1 x1 ak 2 x2 akn xn () xnk bk
则目标函数标准形式为：
非负约束
xij 0(i 1,2,, m; j 1,2,, n)
mn
z
cij xij min
i1 j1
目标：总运费最小
一、 线性规划的数学模型
（一）线性规划模型之实例 资源利用问题 假设某地区拥有m种资源，其中，第i种资源在规
划期内的限额为bi(i=1，2，…，m)。这m种资源可用 来生产n种产品，其中，生产单位数量的第j种产品需 要 消 耗 的 第 i 种 资 源 的 数 量 为 aij(i=1 ， 2 ， … ， m ； j=1,2, …,n)，第j种产品的单价为cj(j=1，2， …，n)。 试问如何安排这几种产品的生产计划，才能使规划期 内资源利用的总产值达到最大?
一、 线性规划的数学模型
（一）线性规划模型之实例
资源利用问题
设第j种产品的生产数量为xj(j=1，2，…，n)，则上述资源问题就是：

《运筹学》教案-目标规划数学模型教案章节：一、引言教学目标：1. 理解目标规划数学模型的基本概念。

2. 掌握目标规划数学模型的建立方法。

教学内容：1. 目标规划数学模型的定义。

2. 目标规划数学模型的建立步骤。

教学方法：1. 讲授法：讲解目标规划数学模型的基本概念和建立方法。

2. 案例分析法：分析实际案例，让学生更好地理解目标规划数学模型。

教学准备：1. 教案、PPT、教学案例。

2. 投影仪、白板、教学用具。

教学过程：1. 引入新课：通过讲解目标规划数学模型的定义和应用领域，引发学生对该课题的兴趣。

2. 讲解基本概念：讲解目标规划数学模型的基本概念，包括目标、约束条件、优化方法等。

3. 讲解建立方法：讲解目标规划数学模型的建立步骤，包括明确目标、确定约束条件、选择优化方法等。

4. 案例分析：分析实际案例，让学生更好地理解目标规划数学模型。

5. 课堂练习：让学生运用所学的知识，解决实际问题，巩固所学内容。

6. 总结与展望：总结本节课的重点内容，布置课后作业，预告下一节课的内容。

教学评价：1. 课堂讲解的清晰度和准确性。

2. 学生参与案例分析和课堂练习的积极性和主动性。

3. 学生对目标规划数学模型的理解和应用能力。

教案章节：二、线性规划数学模型教学目标：1. 理解线性规划数学模型的基本概念。

2. 掌握线性规划数学模型的建立方法。

教学内容：1. 线性规划数学模型的定义。

2. 线性规划数学模型的建立步骤。

教学方法：1. 讲授法：讲解线性规划数学模型的基本概念和建立方法。

2. 案例分析法：分析实际案例，让学生更好地理解线性规划数学模型。

教学准备：1. 教案、PPT、教学案例。

2. 投影仪、白板、教学用具。

教学过程：1. 引入新课：通过讲解线性规划数学模型的定义和应用领域，引发学生对该课题的兴趣。

2. 讲解基本概念：讲解线性规划数学模型的基本概念，包括决策变量、目标函数、约束条件等。

3. 讲解建立方法：讲解线性规划数学模型的建立步骤，包括明确目标、确定决策变量、列出约束条件等。

线性规划与目标规划的异同和作用一、线性规划与目标规划（1）线性规划线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法。

一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。

线性规划模型的一般形式如下：在线性规划的数学模型中，方程（1）称为目标函数；（2）称为约束条件。

满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。

决策变量、约束条件、目标函数是线性规划的三要素。

在生产管理和经营活动中经常提出一类问题，即如何合理利用有限的人力、物力、财力等资源，以便达到最好的经济效果。

例． [生产计划安排问题]某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，单位产品的获利，如下表所示：产品Ⅰ产品Ⅱ资源限制设备 1 1 300台时原料A 2 1 400千克原料B 0 1 250千克单位产品获利50元100元问题：计划期内工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？解：设工厂在计划期内应安排生产产品ⅠX1件, 产品ⅡX2件。

所获利润为z元。

由题意得：Max z = 50 x1 + 100 x2x1 + x2 ≤ 300s.t. 2 x1 + x2 ≤ 400x2 ≤ 250x1 , x2 ≥ 0上例有这样的特征：（1）用一组变量表示某个方案，一般这些变量取值是非负的；（2）存在一定的约束条件，可以用线性等式或线性不等式来表示；（3）都有一个要达到的目标，可以用决策变量的线性函数来表示。

（2）目标规划目标规划（Goal programming）目标规划是线性规划的一种特殊应用，能够处理单个主目标与多个目标并存，以及多个主目标与多个次目标并存的问题。

目标规划的模型分为以下两大类： 1.多目标并列模型。

2.优先顺序模型。

目标规划在企业人力资源需求预测中的应用企业人力资源需求预测是人力资源管理是的一项重要工作，它可以帮助企业明确未来人力需求趋势，做好人才储备工作；同时也可以帮助企业合理预测未来各部门、各类职位人员的需求情况，做好企业的定岗定编工作。

满足
12X1 + 6X2 ≤ 600 X1≥0，X2 ≥0 使 max f(x)=7X1 + 5X2
3.合理配料模型
例1-5 用三种原料A1、A2、A3配制一种食品，要求该食品中 蛋白质、脂肪、碳水化合物和维生素的含量分别不低于150、 200、250、300个单位，这三种原料的单价及每单位原料所含各 种成份的数量如表1-6所示。问如何配制这种食品，使成本最低？
X2 = 18 maxf(x) = 2600
第三节
解的结构
线性规划的解有三种情况：有最优解、有解但无 最优解和无可行解。有最优解又有两种情况：有惟一 的最优解和有无穷多个最优解。 当线性规划的约束条件中出现矛盾约束时，即二 元一次不等式组无解时，线性规划问题无可行解。
在例2－1中，加一个约束条件： 求x1,x2
令f(x)=-f(x) ′ 则maxf(x)=-min[-f(x)] =-minf(x) ′
例1-14 将下列线性规划数学模型化为标准形式: 求 x1,x2,x3
2x1 +
x2 + x3
≤ 8
满足
x1
-
x2
x2
+
x3
≥ 3
3x1 -
– 2x3 ≤ -5
≥0,X3是自由变量
X1≥0，x2
使 maxf(x) = x1 – 2x2 + 3x3
解:令X3=X4-X5，其中X4≥0，X5≥0， 在第一个约束条件的左边加入一个松驰变量X6，化为等式； 在第二个约束条件的左边减去一个松驰变量X7，化为等式； 在第三个约束条件的左边加入一个松驰变量X8，化为等式； 并且等式两边同乘以-1； 将求 maxf(x) = X1 - 2X2 + 3X3 化为求

运筹学方法与模型运筹学是运用数学、统计学和计算机科学等专业知识和技术，以科学化的方法帮助人们做出最佳决策的学科。

运筹学研究的对象包括决策分析、优化算法、模拟系统、控制论以及信息论等多个方面。

方法。

1.数学方法：运筹学在问题解决中利用了大量数学原理和方法，如线性规划、非线性规划、统计分析、概率论等。

2.统计方法：运筹学在处理大量数据时应用的方法，如数据采集、整理、分析和解释等，让人们可以据此推断数据的趋势。

3.计算机方法:运筹学借助计算机技术，使用计算机建模和仿真技术，将复杂的问题转化为简单的研究对象，并求解其最优解。

4.运筹思想：运筹学旨在找到最优策略，其思想是在各种因素和条件的制约下，达到最佳结果的决策。

这是一个重要的应用范畴。

模型。

1.线性规划模型：这是一种基本的运筹学模型，它通过建立一系列线性等式或不等式来描述形式化问题。

通过优化算法求解，找到最优解。

2.整数规划模型：整数规划模型是在线性规划的基础上，加上整数限制条件的扩展。

为求解整数规划问题，需要使用各种启发式算法、分枝限界法等。

3.随机规划模型：随机规划模型是在考虑风险或不确定性因素的情况下，寻找最优策略的模型。

4.动态规划模型：动态规划模型是用于描述决策过程的数学模型。

通过建立方程组，求解最优决策方案，它广泛应用于生产、库存、资源分配问题等领域。

总结。

运筹学作为一门独立的学科，旨在建立数学模型，找到最优决策方案。

在现代企业管理和科学研究中，它的应用越来越广泛。

运筹学所涉及的方法和模型丰富多样，它不断的激发着人们通过科学的手段来寻找最佳解决方案的创新思维。

解：设 x1， x2 分别表示甲乙产品的产量，则相应的线性 规划模型为： max z 2 x1 3 x2
2 x1 2 x2 12 x1 2 x2 8 s.t . 4 x1 16 4 x2 12 x1 , x2 0
它的最优解为: x1 =4, x2 =2, z =14
3. 对所有的目标函数建立约束方程，并入原来的约束条 件中，组成新的约束条件；
4. 引入目标的优先等级和加权系数；建立使组合偏差最 小的目标函数。
1.确定目标函数的期望值 每一个目标函数希望达到的期望值(或目标值、理想值)。
根据历史资料、市场需求或上级部门的布置等来确定。 2.设置偏差变量，用来表明实际值同目标值之间的差异。
解：设 x1, x2 分别表示彩色和黑白电视机的产量。该问 题的目标规划模型为：
min z P1d1 P2d 2 P3 (2d 3 d4 )
x1 x2 d1 d1 40 x1 x2 d 2 d 2 50 s.t . x1 d3 d3 24 x d d 2 4 4 30 x , x , d , d 0 ( i 1, 2, 3, 4) 1 2 i i
P1 ：企业利润目标； P2 ：甲、乙产品的产量尽可能达到1∶1的要求；
P3 ：设备A、B尽量不超负荷工作，在第三优先级中，设备A的重 要性是设备B的三倍。
min z P1d1 P2 (d 2 d2 ) 3 P3 (d 3 d3 ) P3d 4
4 x1 16 (1) (2) 4 x2 12 2 x 3 x d d 12 (3) 2 1 1 1 (4) x1 x2 d 2 d 2 0 2 x 2 x d d (5) 2 3 3 12 1 x 2x d d 8 (6) 1 2 4 4 x , x 0, d , d i i 0 ( i 1, 2, 3, 4) 1 2

运筹学模型（一）本章重点：线性规划基础模型、目标规划模型、运输模型及其应用、图论模型、最小树问题、最短路问题复习要求：1. 进一步理解基本建模过程，掌握类比法、图示法以及问题分析、合理假设的内涵.2. 进一步理解数学模型的作用与特点.本章复习重点是线性规划基础模型、运输问题模型和目标规划模型. 具体说来，要求大家会建立简单的线性规划模型，把实际问题转化为线性规划模型的方法要掌握，当然比较简单. 运输问题模型主要要求善于将非线性规划模型转化为运输规化模型，这种转化后求解相当简单. 你至少把一个很实际的问题转化为用表格形式写出的模型，至于求解是另外一回事，一般不要求. 目标模型一般是比较简单的线性规模模型在提出新的要求之后转化为目标规划模型. 另外，关于图论模型的问题涉及到最短路问题，具体说来用双标号法来求解一个最短路模型. 这之前恐怕要善于将一个实际问题转化为图论模型. 还有一个最小数的问题，该如何把一个网络中的最小数找到. 另外在个别场合可能会涉及一笔划问题.1. 营养配餐问题的数学模型m i Z n =C 1x 1+C 2x + C n x n⎧a 11x 1+a 12x 2+ +a 1n x n ≥b 1, ⎪⎪a 21x 1+a 22x 2+ +a 2n x n ≥b 2, ⎪ s ⋅t⋅⎨⎪a x +a x + +a x ≥b , m 22mn n m ⎪m 11⎪⎩x j ≥0(j =1, 2, , n或更简洁地表为m i Z n =∑C x jj =1n j⎧n ⎪∑a ij x j ≥b i ⎪j =1s ⋅t ⋅⎨⎪x ≥0(i =1, 2, , m j ⎪j =1, 2, , n ⎩其中的常数C j 表示第j 种食品的市场价格，a ij 表示第j 种食品含第i 种营养的数量，b i 表示人或动物对第i 种营养的最低需求量.2. 合理配料问题的数学模型有m 种资源B 1，B 2，…，B m ，可用于生产n 种代号为A 1，A 2，…，A n 的产品. 单位产品A j 需用资源B i 的数量为a ij ，获利为C j 单位，第i 种资源可供给总量为b i 个单位. 问如何安排生产，使总利润达到最大？设生产第j 种产品x j 个单位（j =1，2，…，n ），则有m a Z x =C 1x 1+C 2x 2+ +C n x n⎧a 11x 1+a 12x 2+ +a 1n x n ≤b 1, ⎪⎪a 21x 1+a 22x 2+ +a 2n x n ≤b l , ⎪ s ⋅t⋅⎨⎪a x +a x + +a x ≤b , m 22mn n m ⎪m 11⎪⎩x j ≥0(j =1, 2, , n或更简单地写为m a z x =∑Cj =1n j x j⎧n ⎪∑a ij x j ≤b i ⎪j =1 s ⋅t ⋅⎨i =1, 2, , m ⎛⎫⎪x ≥0 j =1, 2, , n ⎪⎪⎪j ⎝⎭⎩3. 运输问题模型运输问题也是一种线性规划问题，只是决策变量设置为双下标变量. 假如问题具有m 个产地和n 个销地，第i 个产地用A i 表示，其产量为a i （i =1，2，…，m ），第j 个销地用B j 表示，其销量为b j （j =1，2，…，n ），从A i 运往B j 的运价为c ij ，而写成为∑a i =1m i =∑b j =1n j 表示产销平衡. 那么产销平衡运输问题的一般模型可以min Z =∑∑c ij x iji =1j =1m n⎧n ⎪∑x ij =a i ⎪j =1⎪⎪m s ⋅t ⋅⎨∑x ij =b j ⎪i =1⎪⎛i =1, 2, , m ⎫⎪x ij ≥0 j =1, 2, , n ⎪⎪⎪⎝⎭⎩4. 目标规划模型某工厂生产代号为Ⅰ、Ⅱ的两种产品，这两种产品都要经甲、乙两个车间加工，并经检验与销售两部门处理. 已知甲、乙两车间每月可用生产工时分别为120小时和150小时，每小时费用分别为80元和20元，其它数据如下表表4-1工厂领导希望给出一个可行性生产方案，使生产销售及检验等方面都能达标.问题分析与模型假设经与工厂总经理交谈，确定下列几条：p 1：检验和销售费每月不超过4600元；p 2：每月售出产品I 不少于50件；p 3：两车间的生产工时充分利用（重要性权系数按两车间每小时费用比确定）；p 4：甲车间加班不超过20小时；p 5：每月售出产品Ⅱ不少于80件；p 6：两车间加班总时数要有控制（对权系数分配参照第三优先级）.模型建立设x 1，x 2分别为产品Ⅰ和Ⅱ的月产量，先建立一般约束条件组，依题设50x 1+30x 2≤4600x 1≥50 售出量x 2≥80 2x 1+x 2≤120 两车间总工时x 1+3x 2≤150+ 设d 1表检验销售费偏差，则希望d 1达最小，有p 1d 1+, 相应的目标约束为 5x 1+30x 2+d 1--d 1+ = 4600； --达最小，有p 2d 2, 相应的目标约束 d 2表产品I 售量偏差，则希望d 2-+x 1+d 2-d 2=50,以d 3、d 4表两车间生产工时偏差，则由于充分利用，故希望d 320=4：1，有--p 3(4d 3+d 4 . 相应的目标约束应为 --达最小，考虑到费用比例为80：, d 4-+-+=150， -d 42x 1+x 2+d 3-d 3=120和x 1+3x 2+d 4以d 5表甲车间加班偏差，则有+-+d 3+d 5-d 5=20， p 4d 5+, 相应目标约束为以d 6表产品Ⅱ售量偏差，则希望d 6达最小，有相应约束为-+x 2+d 6-d 6=80.++++表示，考虑到权系数，有p6(4d 3+d 4, 其目标约束由于利用超生+d 4- 最后优先级p 6可利用d 3产工时，已在工时限制中体现，于是得到该问题的目标规划模型为---+-++m i z n =p 1d 1++p 2d 2+p 3(4d 3+d 4 +p 4d 5+p 5d 6+p 6(4d 3+d 4 ⎧50x 1+30x 2+d 1--d 1+⎪-+x 1+d 2-d 2⎪⎪-+2x +x +d -d 1233⎪⎪-+s ⋅t ⋅⎨x 1+3x 2+d 4-d 4⎪+-+d +d -d 355⎪⎪x 2+d 6--d 6+⎪-+⎪⎩x 1, x 2≥0, d l , d l≥0=4600=50=120=150=20=80(l =1, 2, , 65. 最小树问题一个图中若有几个顶点及其边的交替序列形成闭回路，我们就说这个图有圈；若图中所有连顶点间都有边相接，就称该图是连通的；若两个顶点间有不止一条边连接，则称该图具有多重边. 一个图被称为是树意味着该图是连通的无圈的简单图. ．在具有相同顶点的树中，总赋权数最小的树称为最小树.最小树的求法有两种，一种称为“避圈法”，一种是“破圈法”，两法各具优缺点，它们具有共同的特征——去掉图中的圈并且每次都是去掉圈中边权较大的边.6. 最短路问题的数学模型最短路问题一般描述如下：在一个图（或者说网络）中，给定一个始点v s 和一个终点v t ，求v s 到v t 的一条路，使路长最短（即路的各边权数之和最小）.狄克斯屈（E.D.Dijkstra ）双标号法该法亦称双标号法，适用于所有权数均为非负（即一切w ij ≥0 w ij 表示顶点v i 与v j 的边的权数）的网络，能够求出网络的任一点v s 到其它各点的最短路，为目前求这类网络最短路的最好算法.该法在施行中，对每一个点v j 都要赋予一个标号，并分为固定标号P （v j ）和临时标号T （v j ）两种，其含义如下：P （v j ）——从始点v s 到v j 的最短路长；T （v j ）——从始点v s 到v j 的最短路长上界.一个点v j 的标号只能是上述两种标号之一. 若为T 标号，则需视情况修改，而一旦成为P 标号，就固定不变了.开始先给始点v s 标上P 标号0，然后检查点v s ，对其一切关联边（v s ，vj ）的终点v j ，给出v j 的T 标号w ij ；再在网络的已有T 标号中选取最小者，把它改为P 标号. 以后每次都检查刚得到P 标号那点，按一定规则修改其一切关联边终点的T 标号，再在网络的所有T 标号中选取最小者并把它改为P 标号. 这样，每次都把一个T 标号点改为P 标号点，因为网络中总共有n 个结点，故最多只需n -1次就能把终点v t 改为P 标号. 这意味着已求得了v s 到v t 的最短路.狄克斯屈标号法的计算步骤如下：1°令S ={v s }为固定标号点集，=V \{v s }为临时标号点集，再令P (v i =0，v t ∈S ； 2°检查点v i ，对其一切关联边（v i ， vj ）的终点v j∈，计算并令 min{T (v j , P (v i +w ij }⇒T (v j3°从一切v j∈中选取并令 min{T (v j }=T (v r ⇒T (v r 选取相应的弧（v i ， vr ）. 再令 S {v r }⇒S , \{v r }⇒=∅，则停止，P (v j 即v s 到v j 的最短路长，特别P (v t 即v s 到v t 的最短路长，而已选出 4°若的弧即给出v s 到各点的最短路；否则令v r ⇒v i ，返2°. 注意：若只要求v s 到某一点v t 的最短路，而没要求v s 到其他各点的最短路，则上述步骤4°可改为 4°若r = t 则结束，P (v r 即为所求最短路长；否则令v r ⇒v i ，返2°.。

一、线性规划与目标规划(1)线性规划线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一 个重要分支 ,它是辅助人们进行科学管理的一种数学方法。

普通地，求线性 目标函数在线性约束条件下的最大值或者最小值的问题，统称为线性规划问 题。

线性规划模型的普通形式如下：在线性规划的数学模型中， 方程 (1) 称为目标函数； (2) 称为约束条件。

满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。

决策变量、约束条件、目标函数是线性规划的三要素。

在生产管理和经营 活动中时常提出一类问题，即如何合理利用有限的人力、物力、财力等资 源，以便达到最好的经济效果。

例． [生产计划安排问题]某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产， 已知生产单位产品所需的设备台时及 A 、B 两种原材料的消耗、资源的限制， 单位产品的获利，如下表所示：产品Ⅱ1 1 1 100 元问题：计划期内工厂应分别生产多少单位Ⅰ、Ⅱ产品才干使工厂获利最多？ 解： 设工厂在计划期内应安排生产产品ⅠX1 件, 产品ⅡX2 件。

所获利润为 z 元。

设备 原料A 原料B单位产品获利产品Ⅰ1 2 0 50 元资源限制 300 台时 400 千克 250 千克由题意得：Max z = 50 x1 + 100 x2x1 + x2 ≤ 300s.t. 2 x1 + x2 ≤ 400x2 ≤ 250x1 , x2 ≥ 0上例有这样的特征：(1)用一组变量表示某个方案，普通这些变量取值是非负的；(2)存在一定的约束条件，可以用线性等式或者线性不等式来表示；(3)都有一个要达到的目标，可以用决策变量的线性函数来表示。

(2)目标规划目标规划(Goal programming) 目标规划是线性规划的一种特殊应用，能够处理单个主目标与多个目标并存，以及多个主目标与多个次目标并存的问题。

目标规划的模型分为以下两大类： 1.多目标并列模型。

2.优先顺序模型。