运筹学第一部分 规划论学习总结

一、线性规划（LP）

1.1线性规划的基本概念

线性规划；目标函数，约束条件；可行解，可行域；最优解，最优值；

1.2 用图解法解两个变量的LP

知识要点：

1） 图解法解LP的目的是理解LP的几何性质，不是为了求解，因为它只适用

于简单的LP。

图解法最适合两个决策变量的LP（约束可以是等式或不等式）。对于一个变量的LP，图形在一维直线上，过分简单；对于三个变量的LP，图形在三维空间，过于复杂。

图解法的基本步骤：

依次画出适合各约束的区域。重点是会画直线方程的图像。对不等式约束，再判断是直线划分的哪一个半平面。

找出适应各个约束的公共区域，即LP的可行域。

对于目标函数，画出几条等值线，并判断等值线的值上升的方向。 平移目标函数等值线，找出使目标函数最优的点，即LP的最优解。若找不到最优点，为无界解。 2） 3） （1） （2） （3） （4）

重点或难点：画对应直线方程的直线，注意斜率的符号。

1.3线性规划的图解法的灵敏性分析，对偶价格（影子价格）。

1.4有关LP的基本定理：

线性规划问题的可行域非空时（除无可行解时），其可行域是凸集。（它是有界或无界的凸多边形）

如果线性规划问题有最优解，则一定有一个可行域的顶点对应一个最优解；（一定可以在其顶点达到，但不一定只在其顶点达到，有时在两顶点的连线上得到，包括顶点）

1.5 可行域与最优解及相互之间的关系：

可行域： 空集 非空 （ 有界、 无界）

最优解： 唯一最优解 无穷多最优解 无界解

1.6线性规划的标准化

1）松弛量：对一个“?” 约束条件中，没有使用完的资源或能力的大小称为松弛量（松弛或空闲能力）；加上一个松弛量

2）约束方程左边为“?”约束条件。

3)右边的常量Bj ?0时，两边都要乘以-1。

4)当变量XK <0时，可令XK= - XK, , XK, >0

5)当变量XK为无约束时，可令XK= XK,- XK,,，其中， XK, , XK,, ?0。

6)令z,=-z，把求min z问题改求为max z, ，即可得到该问题的标准型。

1.7线性规划的计算机解法

（1）Excel求解线性规划问题

规划求解的主要步骤：

设置目标单元格－目标函数，需要最大化（或最小化）的单元格；

设置可变单元格－自变量，需要决定的数目；

约束－约束条件，可通过添加、修改、删除来灵活修改；

要注意，使用线性规划模型，需要修改选项，选中采用线性模型和假定非负。

（2）Lindo_w

注意事项:

1) 基本程序架构lindo是这样的：

MAX 目标函数表达

ST

变量约束1

变量约束2

变量约束3

END

求解一个问题，送入的程序必须以MIN或MAX开头，以END 结束；然后按Ctrl + S（或按工具栏中的执行快捷键）进行求解；

2)低版本的LINDO要求变量一律用大写字母表示；

3) 目标函数及各约束条件之间一定要有"Subject to (ST) "分开. 其中字母全部大写；

4) 变量名不能超过８个字符.

在LINDO命令中，约束条件的右边只能是常数，不能有变量；

5) 变量与其系数间可以有空格,不能有任何运算符号(如乘号"*"等).

6) 要输入<=或>=约束，相应以<或>代替即可.

7) 一般LINDO 中不能接受括号"()"和逗号",", 例:400(X1+X2) 需写成400X1+400X2;10,000 需写成10000.

8) 表达式应当已经过简化。不能出现 2X1+3X2-4X1,而应写成-2X1+3X2. LINDO对目标函数的要求，每项都要有变量，例如，LINDO不认识MIN 2000-X+Y，要改为MIN –X+Y；

9)在LINDO中使用!构造注释语句

10)英文输入,M.

结果解释：

“LP OPTIMUM FOUND AT STEP 6”表示LINDO在（用单纯形法）６次迭代或旋转后得到最优解。

“OBJECTIVE FUNCTION VALUE 1)933400.0”表示最优目标值为933400。 “VALUE”给出最优解中各变量的值。

“SLACK OR SURPLUS”给出松弛变量的值。上例中SLK 2= 第二行松弛变量＝０（模型第一行表示目标函数，所以第二行对应第一个约束）

“REDUCE COST”列出最优单纯形表中判别数所在行的变量的系数，表示当变量有微小变动时，目标函数的变化率，其中基变量的reduce cost 值应为０，对于非基变量Ｘj相应的reduce cost值表示Ｘj增加一个单位（此时假定其他非基变量保持不变）时目标函数减小的量（max 型问题）。

“DUAL PRICE”（对偶价格）列出最优单纯形表中判别数所在行的松弛变量的系数，表示当对应约束有微小变动时，目标函数的变化率，输出结果中对应每一个约束有一个对偶价格。若其数值为Ｘ，表示对应约束中不等式右端项若增加一个单位，目标函数将增加Ｘ个单位（max 型问题）。

灵敏度分析：如果做敏感性分析，则系统报告当目标函数的费用系数和约束右端项在什么范围变化（此时假定其他系数保持不变）时，最优基保持不变。报告中INFINITY表示正无穷

1.8线性规划建模案例

人力资源分配问题

生产计划问题

套裁下料问题

投资问题

配料问题

二、单纯形法

1） 单纯形法引入――运用简单例子，简单介绍单纯形法的基本思路。

2） 介绍单纯形方法

（1） 初等行变换

（2） 迭代，旋转元，顶点到相邻顶点；

（3） 换入变量的确定：非基变量检验数大于零

（4） 换出变量的确定：最小比值法则（避免出现基变量为负的情形）

（5） 判断最优：所有检验数非正

（6） 判断无界解：有非基变量，检验数为正，对应该变量的单纯形表中的

系数都非正。

（7） 没有初始单位矩阵时，加人工变量，用两阶段法求解。若第一阶段结

束时，有人工变量为正，可判断无解。

3）表格单纯形法

三、对偶理论

1. 对偶规划的性质：

若原规划求最大，对偶规划求最小：

1）对称性：对偶规划的对偶为原规划。

2）弱对偶定理：原规划任意可行解的目标函数值小于等于对偶规划可行解的目标函数值。

3）对偶定理：若x*和y*分别是原规划和对偶规划的可行解，则x*和y*是最优解的充要条件是它们对应的目标函数值相等。

4）互补松弛定理：若x*和y*分别是原规划和对偶规划的最优解，则原问题松弛变量取值和相应的对偶规划变量乘积为0，对偶问题松弛变量取值和相应的原规划变量乘积为0（注：其逆也成立）。

2. 影子（对偶）价格

影子（对偶）价格――资源增加1个单位，目标函数的改变。

影子价格的应用

(2)影子价格表明资源增加对总效益产生的影响

3. 任一线性规划的对偶问题的写出

对称形式的对偶问题写出

非对称形式的对偶问题写出 (1)影子价格是对现有资源实现最大效益时的一种估价

四、运输问题

1）供求平衡

2）供大于求

3）供不应求

4）转运问题

5）运输问题的表上作业法简介

五、整数规划

1、整数规划问题的提出与模型类型

2、分枝定界法介绍

3、0-1整数规划介绍

4、0-1建模

（1） 投资选址问题

（2） 固定成本问题

（3） 任务指派问题

（4） 背包问题

（5） 相互排斥的约束条件

（6） 折扣问题

第二篇：运筹学考试总结

运筹学：

1、  线性规划：是求一组非负变量，在满足一组以线性等式或线性不等式所表示的限制条件下，使一个线性函数取得最优值，称这类问题为线性规划（Linear Programming），简称LP。

2、  LP标准型：maxz=

 s.t．其中x_j为决策变量，z为目标函数，a_ij为技术系数，b_i为资源系数，c_j为价值系数。

3、满足约束条件的任一解称可行解，所有可行解组成的集合称可行域。使目标函数取得最优值的可行解称为最优解，记作X^**，最优解对应的目标函数值称为最优值。记作Z^*.

4、单存形法（SM）基本思想：从一个初始基可行解出发，每次选一个非基变量（入基变量）来取代一个基变量（出基变量），即把一个非基变量从0增加到某一正数，而把相应的一个基变量从一个正数变成0，以此达到改进目标函数值，经多次迭代，目标函数值逐步改进，最终得到最优解。注意：此法是有效的通用方法，解线性规划的图解法虽直观，但多于2个变量情况就不适用了。

5、决策者要了解在满足约束的条件下，什么价格得到最低利润，做到洽谈时心中有数，此价格称临界价格，如果等于临界价格，可生产产品销售，也可出售材料，获利相同。高于临界价格，宁可出售材料，比生产产品获利更大。低于临界价格，依然生产产品销售，比直接出售材料获利大。这个临界价格，在经济学上叫影子价格。

6、原规划与对偶规划：

例：maxz=3x₁+4x₂ 

 s.t.   _，写出对偶规划。（书P41`）

Key：minf=5y₁+15y₂

s.t.

较重要的性质：

（1）对偶规划的对偶是原规划。

（2）设X、Y为原规划与对偶规划的任一可行解，则恒成立z(X)≤f(Y).

（3）设X、Y各为原规划与对偶规划的一个可行解，且有z(X)=f(Y)，则X、Y必为最优解。

（4）原规划与对偶规划同有最优解，且两者最优值相等。

7、灵敏度分析的推广应用：1、增加新的变量2、增加新的约束条件（可能导致最优解恶化）

   灵敏度分析仅利用最优解对应的基阵B及数据a_ij（技术数据）、b_i（资源数据）、c_j（价值数据），经适当的运算，即可求得最优解适用的范围或求出新的最优解。

8、整数规划：通常，将变量全部或部分取整数的线性规划统称整数线性规划。简称整数规划。简记作IP。分为两类：纯整数规划和混合整数规划，纯整数规划中其变量只取0或1，称为0-1规划。分支定界法是求解一般整数规划的通用算法，既可用于纯整数规划，也可用于混合整数规划。

9、目标规划中目标函数基本形式有三种：

（1）达到期望值 要求正负偏差同时尽可能小，即minf=f(d^-+d⁺)

（2）低于期望值 要求正偏差尽可能小，即minf=f(d⁺)

（3）高于期望值 要求负偏差尽可能小，即minf=f(d^-)

10、无环且无多重边的图称为简单图。点v关联边的个数称为v的次或度，记作d（v）或deg（v），当d（v）=0，v称为孤立点，当d（v）=1，v称悬挂点，当d（v）为大于1的奇（偶）数，v是奇（偶）点。规定:v有一个环,v的次增加2.

11、图论的基本性质：书P126

(1)d（v）≤p-1(p个顶点)

(2)(q为边数)

(3)设G为任何图,则奇点个数必为偶数.

12、树：无圈得连通图，记作T。图G的支撑树T中，总权最小的树称为最小支撑树（生成树），简称最小树，记作T^*.

13决策六要素：决策者、决策目标、可行策略、自然状态、策略后果、策略评价。按决策环境分为确定型、风险型与不确定型。所谓不确定性决策就是决策者对环境完全不清楚的情况下进行决策。

14、对策的三要素：局中人、策略和赢得函数（支付函数）。描述对策结果的函数就称为赢得函数。其中策略：一局对策中，每个局中人都有若干供自己选择的可行方案，称为策略。

15、存在鞍点的条件：P208

    a_ij= a_ij =a_i*j*=v

  

计算题：

1、 运输问题（书P57）

(1) 西北角法（2）※最小元素法（找“1”）（3）差值法，三种方法任选一种。

注意：做题时建议用最小元素法，较简单！大量计算实践表明，最大差值法所得的初始方案往往优于其他方法得到的初始方案，从而减少迭代的次数。

2、 图解法求解有两个决策变量的线性规划问题（书P17）

注意：写明最有解X^*如：（x₁，x₂）^T和最优值z^*

3、 找最小生成树（避圈法即Kruskal算法和破圈法即Rosenstiehl算法）书P131

4、 悲观准则与乐观准则（书P180）

悲观准则是“坏中求好”的保守准则，最大最小准则。

乐观准则是“好中求好”的冒险准则，最大最大准则。

5、用优超原理求鞍点（书P209）