课程：《运筹学（1）》
课程号：20250013
课序号：2授课老师：王焕刚。
授课学期：秋季学期。
基于材料：运筹学基础》，张莹著，清华大学出版社。
运筹学（1）》课件2024年秋，王焕刚。
编辑记录：第一次：
王诚，starlit@zzxy，自46，2024年1月。
完成手册初样，待完善、更正、补充。
目录。第1章线性规划的数学模型 1
1.1 标准型 1
1.2 线性规划标准型的基本假定， 基与解 2
1.3 基本定理 3
第2章单纯形法 3
2.1 普通单纯形法 3
2.2 退化问题的求解 4
2.3 改进单纯形法 4
第3章线性规划的对偶原理 5
3.1 对偶问题 5
3.2 对偶单纯型法 6
第4章灵敏度分析 6
4.1 改变价值向量c 6
4.2 改变限定向量b（变为b’） 6
4.3 改变初始约束矩阵的一列pj（变为pj’） 6
4.4 增加一个新约束 6
4.5 增加一个新变量 6
第5章整数规划 7
5.1 分枝定界法 7
5.2 求解0-1规划的隐枚举法 7
5.3 求解指派问题的匈牙利法 8
第6章目标规划 8
6.1 基本概念和数学模型 8
6.2 **法 10
6.3 序贯式算法 10
6.4 单纯型法 10
第7章非线性规划的基本概念和基本原理 11
7.1 数学模型和基本概念 11
7.2 凸函数和凸规划 11
7.3 无约束条件的极值条件 12
第8章单变量函数的寻优方法 12
8.1 **分割法 12
8.2 牛顿法 13
第9章无约束条件下变量函数的寻优方法 14
9.1 牛顿法 14
9.2 单纯型搜索法 14
9.3 最速下降法 14
第10章约束条件下多变量函数寻优 14
10.1 约束极值问题的最优性条件 14
10.2 罚函数法 16
第11章动态规划的基本概念和基本原理 18
11.1 基本概念和模型组成 18
11.2 基本原理和基本方程 18
11.3 递推方法 19
第12章确定性决策过程 19
12.1 生产与存储问题 19
12.2 资源分配问题（一维） 20
12.3 不定期最短路径问题 20
第13章图与网络分析 21
13.1 图与网络的基本知识（略） 21
13.2 最短路问题 21
13.3 最大流问题 21
第14章决策分析 23
14.1 概述 23
14.2 风险性决策 23
14.3 效用理论 24
14.4 不确定型决策 25
第15章对策论 27
15.1 概述 27
15.2 矩阵对策 27
第16章排队论 30
16.1 基本知识 30
16.2 生灭过程的稳态解 31
繁写形式及缩写形式：
变量≥0（假设n个）
约束条件是等式（假设m个）
目标函数求min
矩阵形式：其中。
a为约束条件的系数矩阵（m×n）
pj为矩阵a的第j列，系数列向量（xj）
b为限定向量（标准型中要求b≥0）
c为价值向量（成本或利润向量）
x为决策变量向量（标准型中要求x≥0）
max化为min
max(cx)=-min(-cx)]
约束不等式化为等式。
当左端≥右端：左端－剩余变量＝右端（剩余变量≥0）
当左端≤右端：左端＋松弛变量＝右端（松弛变量≥0）
剩余变量与松弛变量统称附加变量。
实质：增加维数，但在目标函数里附加变量权值设为0。
xk自由变量化为非负变量。
令。实质：增加维数，替代即可。
xj有上下界化为非负变量。
当xj≥uj（有下界）即xj－uj≥0，令xj’＝xj－uj（xj’≥0），用（xj’＋uj）代替xj；
当xj≤tj（有上界）即tj－xj≥0，令xj”＝tj－xj（xj”≥0），用（tj－xj）代替xj；
实质：变量的线性变换。
1、由全部约束条件作图求出可行域。
以x1为横轴，x2为纵轴；
2、作出一条目标函数的等值线。
化为x2为x1的一次函数的形式；
3、平移目标函数等值线，作图得最优点，最后再算出最优值。
一般使得等值线斜率最大。
如有解，通常为顶点或一条边，分别对应唯一最优解和无限最优解情况；
基：已知a 是约束条件的m×n 系数矩阵，其秩为m，若b是a 中m×m 非奇异子矩阵(即可逆矩阵， 有|b|≠0)，则称b 是线性规划问题的一个基，b是由a 中m个线性无关的系数列向量组成的；
只要是可逆的都可以做基。
基向量：b中一列pi (共m个) 基变量xi
非基向量：x中不是基向量的组成非基向量。
ax＝b ①
x≥0 ②min z ＝ cx ③
可行解：①+的解。
最优解：=可行解+③
基本解：令所有非基变量=0，求出的满足①的解。
基本可行解：=基本解+②(非负条件)
最优基本可行解：=基本可行解+③
退化的基本解：有基变量=0 的基本解。
退化的基本可行解。
退化的最优基本可行解。
一般这里假设不出现“退化”。
凸集：任两点连线于集合边界没有有限个交点。
顶点：该点不能用集合内的任意两个点的线性组合来表示，即该点不在任意两点连线上（不含端点）。
凸组合：两点连线上的任意一点，为该两点的凸组合。n维下即n个点的线性组合。
定理一：若线性规划问题存在可行域，则其可行域是凸集。
基本定理，实际应用中基本都满足。
定理二：线性规划问题的基本可行解对应于可行域的顶点。
在求解过程中关注顶点即可。
定理三：如果线性规划问题有有限最优解，则其目标函数最优值一定可以在可行域的顶点上达到。
如果存在两顶点都满足，则意味着该两点形成的边都满足，存在无限最优解。
1、 化为标准型。
将b化为非负，加入附加变量。
2、 构造初始可行基。
根据情况选定或构造初始可行基，然后列表，如表 2.1。
在标准型下，如果经过线性变换后，可以找到一组原变量满足初始可行基条件，即解得满足不等式且非负，则直接利用即可。如表 2.1中的x1，x2就可以直接作为初始可行基；
如果不满足，则引入人工变量，以m为罚因子在目标函数中体现，即大m法。
归根结底的目的是：取到一组基，它的系数为单位阵，它的值非负。以上两种方法目的都是这个。
表 2.13、 求出基本可行解（实际求解中不需要）
运筹学复习
有四项工作要甲 乙 丙 丁四个人去完成，每项工作只允许一个人去完成，每个人只完成其中一项工作。已知每个人完成各项工作的时间如下表所示，问应指派哪个人去完成哪项工作才能使总的消耗时间为最少？最优方案为 甲 工作1，乙 工作4，丙 工作3，丁 工作2例试将下面线性规划问题。min z x1 2x2 3x...
运筹学复习
运筹学 复习知识点。第二章 线性规划的 法。法的灵敏度分析。第四章 线性规划模型建立。人力资源分配问题。生产计划问题。套裁下料问题。连续性投资问题。第五章 单纯形法的 形式求解线性规划。人工变量法 大m法。线性规划解的几种特殊形式。第六章。单纯形表的灵敏度分析。求一个线性规划的对偶问题。利用对偶规划...
运筹学复习
1.网络计划。根据安排表画出网络图，并从网络图中找出关键路径。根据安排表画出网络图，并从网络图中找出关键路径。2.决策问题。1 挂历订购问题。挂历售价80元 本，成本50 本，若当年最后一天还有挂历没卖出，则剩余只能跳楼甩卖，卖价20元 本。根据往年情况，明年销售情况分别为 150,160,170,...