《运筹学导论》总结

时间：2023-08-07

　　给定目标和条件->选择最优方案->最优化技术作用； 1.辅助决策 2.提高决策效率 3.优化决策效果又称“又要马儿跑，又要马儿不吃草。”

　　目标-影响因素分析-确定类型-选择理论与方法-分析与设计-决策 1.凝练问题 2.注重思维 3.培养能力 4.开阔视野先修课程：高等数学、线性代数、概率与数理统计学习方式：实际联系、课堂听课、分组讨论、联系实际

　　线性规划、排队论、动态规划、图与网络分析、对策论、非线性规划（储存论、决策论）

　　什么是运筹学：最优化怎么学运筹学：重思维运筹学学什么：有点多

　　问题：是得过且过，还是宁缺毋滥？

　　线性规划问题：生产计划输运方案合理下料配料问题生产布局合理利用有限资源，得到最大效益

　　1.决策变量需决策的量 2.目标函数需优化的量，即与达到的目标 3.约束条件为实现优化目标受到的限制

　　以极大型、小于等于为例决策变量 $x_1,...,x_n$ 目标函数 $max z=c_1x_1+...+c_nx_n$ 约束条件 $a_{11}x_1+...+a_{1n}x_n \leq b_1$ ... $a_{m1}x_1+...+a_{mn}x_n \leq b_m$ $x_1,...x_n \ge 0$

　　1.做约束条件图形 2.做目标函数图形 3.求出最优解可行解满足全体约束的解，记为 $X$ 最优解可行解在最优的，记为 $X^*$ 可行解是可行域中的点，是可行方案最优解是可行域的角点，是最优方案解的类型： 1.唯一解 2.多重最优解 3.无解 4.无有限最优解

　　单纯形法流程图(图源自网络)

　　1.线性规划三要素决策变量、目标函数、约束条件 2.二维线性规划问题特殊解法-图解法约束图形-目标图形-求最优解 3.线性规划问题一般解法-单纯形法初始解-检验解-最优解

　　1.线性规划的对偶问题对偶问题模型、性质、经济解释 2.线性规划的灵敏度分析参数变化影响解的可行性/最优性 3.运输问题的表上作业法最小元素法、伏格尔法、闭回路法、位势法

　　问题：To be or not to be?

　　决策变量 $x_i$ —是否做第 $i$ 件事 $i=1,2...,n$ $x_i=\delta(x-i)$

　　n件事中至少做k件事—— $x_1+x_2+...+x_n \ge k$ n件事中必须做k件并只能做k件事—— $x_1+x_2+...+x_n=k$ 只在做了第i件事前提下才考虑是否做第j件事—— $x_j \le x_i$ n件事中最多做k件事—— $x_1+x_2+...+x_n \le k$ 做第j件事的充要条件是做第j件事—— $x_i=x_j$ 做第i件事的充要条件是不做第j件事—— $x_i=1-x_j$

　　例子一名旅行者在准备行装，最多携带总重量b，假设物品只能整件携带，每件物品规定“价值”，共有n件物品可选，第i件物品重量为 $b_i$ ，价值为 $c_i$ ,则携带哪些物品可使总价值最大? 决策变量 $x_i=\delta(x-i)$ ,i：带第i件物品目标函数 $max z=\sum_{i=1}^\infty c_ix_i$ $\sum_{i=1}^\infty b_ix_i \le b$ $x_i=0,1$ $i=1,...,n$

　　n项工作，由n个人承担每项工作只由一人承担每个人只承担一项工作 $c_{ij}$ ：第i人做第j项工作费用求总费用最低的方案

　　 $x_{ij}=\delta(i-j)$

　　 $max z=\sum_j \sum_i c_ij x_ij$

　　 $x_{i1}+x_{i2}+...+x_{ij}+...+x_{in}=1$ i=1,2,...,n 每个人有事做

　　 $x_{1j}+x_{2j}+...+x_{ij}+...+x_{nj}=1$ j=1,2,...,n 每件事有人做

　　 $x_{ij}=0,1$

　　人数与工作数不等的指派问题

　　n项工作，由m个人承担每项工作只由一人承担每个人只承担一项工作

　　 $c_{ij}$ ：第i人做第j项工作费用求总费用最低的方案

　　m项工作，由n个人承担每项工作只由一人承担每个人只承担一项工作

　　 $c_{ij}$ ：第i人做第j项工作费用求总费用最低的方案

　　设m个人中的第k个人可同时做r件事，第k个人视为r个人（t个人做同一件事费用系数相等）

　　 $min$ 问题——>第k个人一定不能做第t件事——>费用系数 $c_{kt}$ 充分大

　　 $max$ 问题——>第k个人一定不能做第t件事——>费用系数 $c_{kt}$ 充分小

　　1.0-1整数规划数学模型 0-1变量 2.0-1整数规划建模投资/背包/选址/固定费用/指派

　　1.整数规划解法割平面法、分支定界法 2.指派问题解法匈牙利算法、最大化问题转化

　　问题：小孩子才做选择，成年人当然是全都要？多目标问题: 决策者有若干目标值,实现目标有先后顺序目标规划: 在给定资源条件下，求偏离目标值最小的方案

　　正偏差变量：第i个目标的决策值超出其目标值部分，记作 $d_i^+$

　　负偏差变量：第i个目标的决策值不足其目标值部分，记作 $d_i^-$

　　三种情况： (1)决策值超过目标值

　　 $d_i^+>0,d_i^-=0$ (2)决策值等于目标值

　　 $d_i^+=d_i^-=0$ (3)决策值未达目标值

　　 $d_i^+$ =0, $d_i^-$ <0 注意 $d_i^+$ , $d_i^-$ 至少一个为零，所以 $d_i^+*d_i^-=0$

　　为达到目标要求的指标值，应使 $d_i^+$ , $d_i^-$ 尽可能小三种情况： (1)超过目标值

　　 $min z$ = $f(d_i^-)$ (2)等于目标值

　　 $min z$ = $f(d_i^-,d_i^+)$ (3)决策值未达目标值

　　 $min z$ = $f(d_i^+)$ eg: $min z$ = $d_1^-$ + $d_2^+$ + $d_2^-$ + $d_2^+$

　　优先因子 $p_k$ ：表达不同目标的重要性度

　　 $p_1\gg p_2\gg ...\gg P_n$

　　权系数 $\omega _j$ ；区分在同一优先级别中不同目标的重要程度（数字）, 数字越大表明该目标越重要

　　绝对约束：必须严格满足的等式约束和不等式约束目标约束达到此目标值时允许发生正或负偏差，将约束条件右端项视为追求的目标值目标函数+偏差变量——>目标约束绝对约束+偏差变量——>目标约束

　　eg.产品对原料单耗不变，原料可补给，求总产值为2000万元及A产品产量为400吨的生产计划，A产量要先达到要求，其次考虑产值。

　　 $x_1$ + $d_2^-$ - $d_2^+$ =400 0.4 $x_1$ +0.5 $x_2$ $\le$ 180 0.2 $x_1$ +0.3 $x_2$ $\le$ 100

　　 $x_1,x_2,d_i^-,d_i^+$ $\geq 0,i=1,2$

　　目标函数： $min z=\sum_{l=1}^L p_l \sum_{k=1}^K (\omega_{ik}^-d_k^- +\omega_{ik}^+d_k^+)$

　　目标约束： $\sum_{i=1}^n c_{ki}x_i+d_k^- -d_k^+=g_k,k=1,...,K$

　　最对约束： $\sum_{i=1}^n a_{ij}x_i \le(=,\ge)b_j,j=1,...,m$

　　非负约束： $x_i\ge0,i=1,...n d_k^+,d_k^-\ge0,k=1,...,K$

　　eg.某工厂生产A、B两种产品，有关数据如下表。若资源可补充，且A、B计划产量分别是4、5.确定一个生产方案，依次满足目标要求。

　　 $p_1$ ：产品数量不得超过计划指标

　　 $p_2$ ：加班时间最少

　　 $p_3$ ：利润达到最高指标

　　 $p_4$ ：设备利用率不超过最高指标

　　 $x_1$ + $d_1^-$ - $d_1^+$ =4

　　 $x_2$ + $d_2^-$ - $d_2^+$ =5 6 $x_2$ +7 $x_1$ + $d_3^-$ - $d_3^+$ =42 4 $x_1$ +9 $x_2$ + $d_4^-$ - $d_4^+$ =61 16 $x_1$ +7 $x_2$ + $d_5^-$ - $d_5^+$ =80 4 $x_1$ +10 $x_2$ + $d_6^-$ - $d_6^+$ =40

　　 $x_1,x_2,d_i^-,d_i^+\ge0$ i=1,...,6

　　1.偏差变量正偏差、负偏差 2.目标函数标函数，min、优先因子、权系数 3.绝对约束与目标约束硬/软约束、绝对约束可转目标约束

　　目标规划解法：图解法、单纯形法

　　问题：是今朝有酒今朝醉还是放眼未来好期待？

　　前后关联+链状结构+多阶段过=多过程决策过程目标寻找全过程最优方案

　　阶段变量k：原问题分成若干相互联系的子问题状态变量 $s_k$ ：每阶段初可能的情形或位置无后效性! 决策变量 $x_k$ (s): 每阶段状态确定后的抉择,即从该状态演变到下阶段某状态的选择决策集合 $D_k$ ( $s_k$ ) 状态转移: 由 $s_k$ 转变为 $s_{k+1}$ 的规律 $s_{k+1}=T_k(s_k,x_k)$

　　状态→决策→状态…… 决策序列在变化的状态中产生后部子策略 $P_{k,n}(s_k)$ : 阶段k至n的决策组成的序列{ $x_k(s_k).….x_n(s_n)$ } 策略 $P_{i,n}(s_1)$

　　阶段指标 $v_k=v_k(s_k,x_k)$ : k阶段状态下选定决策

　　 $x_k$ 后产生的效益动态规划最优解？最优策略 $P_{1,n}^*(s_1)$

　　动态规划最优值？最优指标函数 $f_1(s_1)$

　　 $f_k(s_k)$ =opt{ $v_k(s_k,x_k)+f_{k+1}(s_{k+1})$ }

　　 $f_{n+1}(s_n+1)$ =0 k=n,...,1

　　确定过程分段构造状态变量——》设置决策变量写出状态转移——》列出阶段指标列出指标函数——》写出基本方程逐段递推求解

　　Bellman最优性原理:如果 $P_{1,n}^*(s_1)$ 是最优策略，则对任意阶段k（1 是以s为起点的k至n子过程的最优策略

　　1.多阶段决策问题前后关联+链状+多阶段过程 2动态规划基本概念阶段变量+决策变量+状态变量+状态转移+后部子策略+阶段指标+指标函数+最优指标函数 3.基本方程

　　 $f_k(s_k)$ =opt{ $v_k(s_k,x_k)+f_{k+1}(s_{k+1})$ }

　　 $f_{n+1}(s_n+1)$ =0 k=n,...,1

　　1.动态规划应用机器负荷、资源分配、设备更新、系统可靠性、背包问题、生产计划、不确定性采购.… 2.状态变量取值及定义离散型、连续型、定义阶段初/末？ 3.动态规划顺序解法

　　 $f_k(s_k)$ =opt{ $v_k(s_k,x_k)+f_{k-1}(s_{k-1})$ }

　　 $f_{0}(s_0)$ =0 k=n,...,1

　　问题：是盘根错节有水平，还是大而化简显实力？

　　点（研究对象）+连线（研究对象的关系）=图

　　点（研究对象）+边（ $[v_i,v_j],[v_j,v_i]$ ）=无向图（ $G=(V,E)$ ）

　　点（研究对象）+弧（ $(v_i,v_j)$ ）=有向图（ $G=(V,A)$ ）

　　环：边的两个端点相同多重边：两个端点之间有两条以上的边简单图：无环无多重边的图多重图：一个无环、有多重边的图

　　有向图/无向图+权（ $w_{ij}$ ）=网络

　　以点为端点的边的个数，记d（v）弧立点：度为零的点悬挂点：度为1的点悬挂边：悬挂点的关联边奇点：度为奇数的点偶点：度为偶数的点定理1：所有顶点度数之和等于所有边数的2倍定理2：在任一图中，奇点的个数必为偶数

　　点 $v_i$ 出次 $d^+(v_i)$ :以 $v_i$ 为始点的边数点点 $v_I$ 入次 $d^-(v_i)$ :以 $v_i$ 为终点的边数次次=出次和入次之和所有顶点的入次之和=所有顶点的出次之和

　　 $G_1=(V_1,E_1)$

　　 $G_2=(V_2,E_2)$

　　 $V_2 \subseteq V_1,E_2 \subseteq E_1$ ——》 $G_2$ 是 $G_1$ 的子图

　　 $V_2=V_1,E_2 \subseteq E_1$ ——》 $G_2$ 是 $G_1$ 的支撑子图

　　链：由两两相邻的点及其相关联的边构成的点边序列简单链：链中所含的边均不相同初等链：所含的点均不相同圈：起点和终点相重合的链连通图：图中任意两点之间均至少有一条链路： $v_{i1},a_{i1},v_{i2},a_{i2},...,v_{i,k-1},a_{i,k-1},v_{i,k},a_{i,k})$

　　链中所有弧皆有 $a_{i,t}=(v_{i,t},v_{i,t+1})，t=1,2,...,k$

　　回路：起点和终点重合的路

　　权矩阵 $a_{ij}=w_{ij}\delta(x-(v_i,v_j))$

　　邻接矩阵： $a_{ij}=\delta(x-(v_i,v_j))$

　　 $(v_i,v_j) \subset E$

　　无圈+连通+图=树树：使图保持连通具有最少边数的图形树的性质： (1)树中任两点中有且仅有一条链 (2)树任删去一边则不连通 (3)边数=顶点数-1

　　 $G=(V,E)$ 支撑子图 $T=(V,E)$ 构成树，T为G的支撑树

　　求赋权图的支撑树，使其边的权和最小

　　按权值从小到大填边——》若出现圈删权值最大边——》填满n-1条边（n为顶点数）

　　在图中找圈——》删除权值最大边——》图中无圈

　　某公司拟铺设海上油管，要求将海上六口油井连通，仅1号油井与海岸相连，距离为5海里。已知，海上六口油井间的距离如下表1。试问，应如何铺设油管使铺设油管的总长最短？

　　解答海岸-1-2(-3-6)-4-5

　　点+连线=图树的定义树的性质图的支撑树最小支撑树：求赋权图的支撑树，使其边的权和最小解法：避圈法、破圈法

　　问题：是条条大道通罗马，还是终南捷径好通达？用最短路给出最短/省/方案最短路：

　　 $D=（V，A）$ 为连通图,求一条路 $\mu$ 从起点 $v_1$ 到终点 $v_n$ 所有路中总权值最小最短路问题算法（ $w_ij$ ≥0） Dijkstra基本思想：最短路的子路一定还是最短路 ( $\alpha,\beta$ )

　　 $\alpha:v_i$ 到当前点的最短路长

　　 $\beta$ ：最短路长中当前点的前接点反向追踪 $\beta$ 值得最短路

　　1.最短路问题多阶段、距离、成本、费用 2.网络优化问题关键点和连线的抽象

　　1.网络中心其余点到该中心点距离和最小 2.网络重心加权系数的中心法

　　问题：是集中精力办大事，还是事事上心求周全？

　　1.准备工作将整个工程分解为若干工序确定各工序的前后顺序（紧前、紧后）确定工序完成时间 $t=\frac{a+4m+b}{6}$

　　三点估计法：最乐观时间a、最可能时间m、最悲观时间b 2.绘图顺序按工序先后从左至右 3.图的结构节点（事项）：相邻工序的时间分界点，用 $i$ 表示。弧（箭线）： $i$ —> $j$ 表示工序； $i$

　　 $j$ 为工序的起点、终点。相邻弧：工序前后衔接关系，称紧前（后）工序。权：工序的完成时间。 4.绘图要求注意：图中不得有缺口、回路和多重边缺口：多个始点或多个终点的现象（应当只有一个始点和终点）回路：方向一致的闭合链处理方法：查找错误，重新画图多重边：两点间有多于一条的边处理方法：增加虚工序注意 1.不急于画出工序结束节点 2.节点编号采用“箭杆删除法”

　　1.两个工序A、B有相同的始点和终点 2.同时有多个起点（终点）

　　工程完工期：终点的最早开始时间事项开始时间

　　 $t_g(1)=0$

　　 $t_g(j)$ =max{ $t_E(i)+t(i,j)$ } j=2,3,...,n 关键工序：工序机动时间=零关键路径: $R(i,j)=0$ 的关键工序工序总时差：工序最晚开始时间一工序最早开始时间事项最晚开始时间：

　　 $t_L(n)=t_g(n)$

　　 $t_L(i)$ =min{ $t_L(j)-t(i,j)$ } (i=n-1,n-2,...,1)

　　完工期=终点最早开始时间关键工序=总时差为零的工序

　　问题：是集中精力办大事，还是事事上心求周全？

　　CPM工序时间确定 PERT工序时间及完工期随机

　　 $T \sim N(T_E,\sigma^2)$

　　绘制工程网络图—>确定关键线路—>初始计划方案—>网络计划优化考虑进度（工期优化）+合理利用资源（时间资源优化）+降低费用（时间费用优化）=优化目标

　　压缩关键工序时间，eg.改进技术、改进工艺、改进设备、保证人/物力非关键工序时差，eg.合理调度、抽调人/物力、支援关键工序采用交叉作业和平行作业，eg.相连几道工序交叉进行,将一道工序拆成几道平行进行如果出现两条关键路径，如何压缩工期？在两条关键路径上压缩同样的时间

　　1.计算工程每单位时间内所需资源量 2.作出初始资源需求曲线 3.进行资源均衡调整求得新的进度计划 4.评价工程进度计划对资源利用的均衡程度(通过方差评价)

　　优先安排关键工序所需要的资源利用非关键工序总时差，错开工序开始时间，错开资源负荷高峰根据计划规定适当延长项目的工期

　　工程成本费用=直接费用+间接费用

　　1.计算工序费用增加率 2.在网络计划图找出费用增加率最低的一项关键工序或一组关键工序作为缩短持续时间的对象注意：关键工序缩短后的值不能小于最短持续时间，不能成为非关键工序

　　3.计算相应的增加的总费用 4.考虑由于工期的缩短间接费用的变化，计算项目的总费用 5.重复以上步骤，直到获得满意的方客止

　　给定时间的求完工概率给定概率的求完工期

　　时间优化：注意关键路线变化资源优化：搞平均主义费用优化：关注直接费用率

　　问题：是有求必应坦荡荡，还是随机应变皆欢喜？

　　输入过程+排队规则+服务机构

　　1顾客的数量有限m？无限 $\infty$ ？ 2顾客到达的方式单个到达？成批到达？ 3顾客相继到达的间隔时间分布确定？随机？分布参数？独立？平稳？

　　即时制、等待制、混合制队列顾客中途退出？多列间相互转移？次序先/后到先服务随机/有优先权系统容量有限制等待时间有限制

　　1数目和排列单台？多台？并列？ 2服务方式单个/成批服务？ 3服务时间确定？随机？分布参数？独立？平稳？

　　排队模型（X/Y/Z/A/B/C） X：顾客到达时间间隔的分布 Y：服务时间的分布 Z：服务台个数 A：系统容量 B：顾客源数量 C：服务规则（可省略） eg. $(M/M/1/\infty/\infty/FCFS)$

　　到达时间间隔为负指数分布服务时间为负指数分布 1个服务台系统容量无限顾客源无限先到先服务

　　系统的状态n 系统中的顾客数系统的瞬态 $P_n(t)$ 考虑在时刻系统的状态为n的概率（难求难用）系统的稳态 $P_n$ ，系统的瞬态的极限 $lim_{n \to +\infty}P_n(t)$ (统计平衡状态的解)

　　队长: 系统中的顾客数n状态概率 $p_n$ 均值 $L_s$

　　排队长: 系统中正在排队等待的顾客数均值 $L_q$

　　队长=排队长+正被服务的顾客数

　　逗留时间一个顾客在系统中停留时间W均值 $w_s$

　　等待时间一个顾客在系统中排队等待时间均值 $w_q$

　　逗留时间=等待时间+服务时间

　　忙期服务机构连续繁忙的时间长度损失率由于顾客被拒绝使企业受到损失服务强度服务机构的繁忙程度

　　研究排队系统运行效率估计服务质量确定系统参数最优值评测排队系统结构是否合理研究设计排队系统

　　1.排队系统组成输入过程+排队规则+服务机构 2.排队系统指标人数、时间、强度 3.排队心理学从排队指标着手设计

　　问题：是只要我想，还是换位思考？

　　博弈现象：竞争的各方总是想用最好的策略击败对方，取得尽可能好的结果

　　局中人按规则考虑其他局中人采取策略集在策略集选取策略得到回报采取策略

　　局中人+策略+赢得函数=博弈

　　参与竞争的各方：人、集团有决策权的主体，不是参谋或从属人员二人博弈：两个局中人多人博弈：多个局中人是否结盟？

　　局中人所拥有的对付其他局中人的方案集合在静态博弈中，策略是一个独立的完整的行动不能是若干相关行动中的某一步局势：每个局中人的策略选择形成的策略组

　　一局博弈后各局中人的输赢得失赢得函数的取值与局中人选定的策略有关 “得失”是“局势”的函数

　　局中人是理性人理性人有一个很好定义的偏好面临给定约束条件下最大化自己的偏好理性的决策：换位思考，预测其他局中人的反应

　　完全信息博弈不完全信息博弈

　　静态博弈 ·局中人同时采取行动 ·互相保密情况下采取行动动态博弈 ·局中人采取行动有先后 ·后采取行动的人可观察到前人采取的行动

　　局中人甲、乙策略 $S_1$ ={ $\alpha_1,\alpha_2,...,\alpha_m$ }, $S_2$ ={ $\beta_1,\beta_2,...,\beta_n$ } 赢得函数 $a_{ij}=F(\alpha_i,\beta_j)$

　　G={ $S_1,S_2;A$ } 甲乙决策依据：从最不利的情形中，选择最有利的情时

　　甲决策取得收益最大最小原则 $max_i min_j a_{ij}$

　　乙决策避免损失最小最大原则 $min_j max_i a_{ij}$

　　如果 $max_i min_j a_{ij}$ = $min_j max_i a_{ij}$ = $a_{i^*j^*}$

　　最优策略 $(\alpha_{i^*},\beta_{j^*})$

　　博弈值 $V_G=a_{i^*j^*}$

　　问题：是精致利己，还是胸怀天下？

　　其他局中人不改变策略任何一方单独改变策略只能带来收益减少在二人零和博弈中，双方最优解是一种均衡解每个局中人的策略对其他局中人策略的最优反应在任何非合作有限博弈中至少存在一个纳什均衡

　　非合作有限博弈存在至少一个纳什均衡纳什均衡是每个局中人的策略对其他局中人策略的最优反应

　　联系决策背景选取聚点

　　1博弈基本概念模型三要素、基本假设、分类 2二人零和博弈局中人决策原则：换位思考、最大化偏好 3二人零和博弃最优纯策略收益矩阵存在鞍点 4.纳什均衡对其他局中人策略的最优反应，非合作有限博弈中存在 5.二人非零和博弈个人最优v.s.全局最优？ 6.多重纳什均衡联系决策背景确定聚点

　　1.策略的优超性化简矩阵，减少计算量 2.二人零和博弈混合策略多次博弈、交替使用策略/对策略有偏好局中人决策为线性规划问题（对偶） 3.二人非零和博弈混合策略通过建立线性规划模型求解最优混合策略通过期望收益相等关系求解收益矩阵为二阶的问题

　　使用专业的线性规划软件Lingo官方网站 https://www.lindo.com/ LINGO 可以用来求解线性，非线性和整数规划问题。 LINGO NL (LINGO2) 可以用来求解线性，非线性和整数规划问题。