第一章 绪论 山大刁在筠 运筹学讲义

第一章 绪论

教学重点：运筹学的主要内容和模型

教学难点：随机规划模型

教学课时：2学时

主要教学环节的组织：在课堂教学中，通过对运筹学发展历史的回顾，引出运筹学的主要内容、特点和发展趋势，再通过实例的讲解，使学生对运筹学模型有一个大致的了解。

第一节 运筹学的概况

1、运筹学的发展与由来。

2、运筹学的性质与特点。

3、运筹学的主要内容。

4、运筹学的发展趋势。

第二节 运筹学中的数学模型

线性规划模型

例 某饲养场所用的混合饲料由n 种配料组成，要求所使用的混合饲料必须含有m 种不同的营养成分，且每一份混合饲料中第i 种营养成分的含量不能低于i b 个单位。已知每单位的第

j 种配料中所含第i 种营养成分的量为ij a ，每单位的第j 种配料的价格为j c 。问在保证营养的条件下,应如何选择配方方案使混合饲料的费用最小?

变量：用变量j x 表示每份混合饲料中第

j 种配料的含量，即所含此配料的数量。

受限制条件：

1. 已知每单位的第j 种配料中所含第i 种营养成分的量为

ij a ，每一份混合饲料中第i 种营养成分的含量不能低于i b 个单位.

m ,,2,1i ,b x a i n 1j j ij =≥∑

=. 2. 变量j x 非负，即.n ,2,1j 0x j =≥，

费用函数：∑==n

1j j j x c f

目标：费用达到最小

模型

∑==n

1j j j x c f min

?????=≥=≥∑=n ,,2,1j ,0x m ,,2,1i ,b x a ..j i n 1j j ij t s 随机规划模型

设计者要设计一个水库，使水库的容量C 在满足限制条件下最小，以使其造价最省。

首先，为防止洪灾，在一年中第i 个季节水库应空出一定的容量i v 以保证洪水注入。因为洪水不一定年年有，洪水量的大小也会有变化，因此，比较合理的约束条件应为以较大的概率i α保证水库容纳洪水，即，

(),1,2,3,4i i i P C s v i α-≥≥ =

其中i s 为第i 个季节初水库的储水量.

其次，水库在每一个季节应能保证一定的放水量i q .由于考虑随机因素，要求满足这一条件的概率不小于某一个数2α，即

2(),1,2,3,4i i P x q i α≥≥ =

其中i x 为第i 个季节的可放水量.

同样，为保护水库的安全和水生放养，一般还要求水库保持最小储水量min s ，即

min 3()1,2,3,4i P s s i α≥≥, =

另外，表示放水量和储水量的,i i x s 不能是负数，即

0,01,2,3,4i i x s i ≥≥ =

综上：

2min 3min ..()()()0,0,1,2,3,4i i i i i i i i C s t P C s v P x q P s s x s i ααα ?? -≥≥?? ≥≥?? ≥≥?? ≥≥ =?

网络优化模型

设某公司准备派n 个工人12,,,n x x x ，去做n 件工作12,,,n y y y .已知工人

j x 去做工作j y 的效率为(,1,2,,)ij w i j n = .现问：如何确定一个分派工人去工作的方案，使得工人的工作效率达到最大？这个问题通常为最优分派问题。

我们可以将最优分配问题转化为网络的最大权对集（对应网络如下图），然后再回到最优分派问题中去，从而得到最优分配方案，这种分析法通常称为网络分析法。

教学计划

数学规划以线性规划和整数规划为教授重点，组合优化部分主要讲网络优化，随机优化讲授排队论和对策论，其它部分作为选讲内容。

教学方法

以授课为主，案例分析相结合。讲课中主要培养用最优化方法解决实际问题的能力。

考核内容

理论方法----笔试

应用能力----案例分析

平时成绩----考勤、作业

运筹学知识点

运筹学知识点： 绪论 1.运筹学的起源 2.运筹学的特点 第一章线性规划及单纯形法 1.规划问题指生产和经营管理中如何合理安排，使人力、物力等各种资源得到充分利用，获得最大效益。 2.规划问题解决两类问题：一是给定一定数量的人力、物力等资源，研究如何充分利用，以发挥其最大效果；二是已给定计划任务，研究如何统筹安排，用最少的人力和物力去完成。 3.规划问题的数学模型包含三个组成要素：决策变量、目标函数（单一）、约束条件（多个）。 线性规划问题的数学模型要求：决策变量为可控的连续变量，目标函数和约束条件都是线性的。 4.线性规划问题的标准形式：目标函数为极大、约束条件为等式、决策变量为非负、变量为非负 5.划标准型时添加的松驰变量、剩余变量和人工变量 6.理解可行解、最优解、基、基解、基可行解等概念，且掌握各类解间的关系 7.用图解法理解线性规划问题的四种解的情况：无穷多最优解、无界解、无可行解、唯一最优解 8.用图解法只有解决两个变量的决策问题 9.线性规划问题存在可行解，则可行域是凸集。 10.线性规划问题的基可行解对应线性规划问题可行域的顶点。 11.线性规划问题的解进行最优性检验：当所有的检验数小于等于零时为最优解；尤其当检验数小于零时（即不等于零）有唯一最优解；当某个非基变量检验数为时，有无穷多最优解；当存在某个检验数大于零且对应的系数又小于等于零时，有无界解。 12.单纯形法的计算过程，可能出计算题 13.入单纯形表前首先要化成标准形式。 14.确定换出变量时根据θ值最小原则，且要求公式中对应的系数大于零。 15.当线性规划中约束条件为等式或大于等于时，划为标准型后，系数矩阵中又不包含单位矩阵时，需要添加人工变量构造一个单位矩阵作为基。 16.人工变量的系数为足够大的一个负值，用—M代表 17.一般线性规划问题的数学建模题（生产计划问题、人才资源分配问题、混合