运筹学知识点整理
1、运筹学研究的基本特点及步骤?
基本特点：多学科交叉、模型化（定量）、最优化 运筹学的工作步骤：
1、提出与表达问题。2、建立模型。3、求解。 4、解的检验。 5、解的分析。 6、解的实施。
2、线性规划问题的特点?
• • • •
目标明确：要解决的问题的目标可以用数值 指标反映。Z=ƒ(x1 … xn ) 线性式，求Z 极大或极小
多种方案：对于要实现的目标有多种方案可 选择 资源有限：有影响决策的若干约束条件
线性关系：约束条件及目标函数均保持线性关系
3、线性规划的数学模型共同特征及标准形式?
（1）共同特征：决策变量：向量
决策人要考虑和控制的因素非负
约束条件：线性等式或不等式
目标函数：Z=ƒ(x1 „ xn) 线性式，求Z 极大或极小 （2）标准形式 A 一般型 Max Z =c 1x 1+c 2x 2+ +c n x n
⎧a 11x 1+a 12x 2+ +a 1n x n =b 1
⎪a x +a x + +a x =b
2112222n n 2⎪⎪
⎨
⎪a x +a x + +a x =b
m 22mn n m ⎪m 11
⎪ ⎩x 1, x 2, , x n ≥0
其中bi >=0 (i=1,2,„,m) B 矩阵型
C 向量型
4、线性规划问题解的概念：可行解、最优解、基本解、基本可行解?
（1）可行解：满足约束条件的变量值
（2）最优解：使目标函数取得最优值的可行解 （3）基本解：对应于基B ，X=
为AX=b的一个解。
，称基B 为可行基。
（4）基本可行解：基B ，基本解X=若
5、线性规划问题解的性质？
A 、课本上（几何意义） （1）凸集
（2）凸组合
（3）极点
B 、PPT 上 （1）若(LP)问题有可行解，则可行解集(可行域) 是凸集(可能有界，也可能无界) 。 （2）基本可行解的个数是有限的，对应于极点的个数是有限的。 （3） (LP)问题的基本可行解
可行域的极点。
（4） 若(LP)问题有最优解，必可以在基本可行解(极点) 达到。
6、图解法及线性规划解结果的几种形式?PPT2-3
有解：唯一最优解、无穷多解；无解：无有限最优解、无可行解
7、单纯形算法的基本思想，单纯形的计算步骤，如何在单纯形表中去判断问题具有唯一的最优解、无穷多最优解、无界解？
根据问题的标准型, 从可行域中某个基本可行解(顶点) 开始，转换到另一个基本可行解(顶点) ，并使得每次的转换，目标函数值均有所改善，最终达到最大值时就得到最优解。
（4）确定换入变量（5）换基迭代
唯一最优解
无穷多最优解
无可行解
7、如果线性规划的标准形式变化为目标函数极小minZ ，则单纯形计算时如何判断已得到最优解？PPT2-5P55
检验数全部大于或等于0
8、在确定初始可行基时，什么情况下要在约束条件中增添人工变量？
（重找不到初始可行基来回答）
9、在两阶段法中，如何根据第一阶段的计算结果来判断第二阶段的计算是否需要继续进行？PPT2-5,p66
第一阶段：解辅助问题
当进行到最优表时，①、若 w =0, 则得到原问题的一个基本可行解，转入第2阶段。 ②、若 w >0, 则判定原问题无可行解。
10、举例说明生产和生活中应用线性规划方面，并对如何应用进行必要的描述。PPT2-1，P1,7
市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划) 生产计划制定(合理下料，配料，“生产计划、库存、劳力综合”) 库存管理(合理物资库存量，停车场大小，设备容量) 运输问题
财政、会计(预算，贷款，成本分析，投资，证券管理) 人事(人员分配，人才评价，工资和奖金的确定) 设备管理(维修计划，设备更新)
城市管理(供水，污水管理，服务系统设计、运用)
11、根据线性规划的原问题写出对偶问题？PPT3-1
两模型的对应关系：
（1）两问题的系数矩阵互为转置
（2）一个问题的变量个数等于另一个问题的约束条件个数 （3）一个问题的右端常数是另一个问题的目标函数的系数
（4）一个问题的目标函数为极大化，约束条件为“=”类型
12、对偶问题解的性质？PPT3-1，P28。课本P40
1) 、对偶问题的对偶问题是原问题。 2) 、弱对偶定理 3）最优性 4）无界性 5）对偶定理 6) 互补松弛性
13、对偶问题的最优解？
原问题的单纯形表中，原问题的松弛变量的检验数对应于对偶问题的决策变量，符号相反
原问题的决策变量的检验数对应于对偶问题的松弛变量，符号相反 例
:
14、对偶单纯形法的运算步骤？p44较为易懂 思路：(max 型)
单纯形法： ①找基B ，满足B-1b ≥0，但 C - CBB-1 A不全≤ 0，（即检验数）。
②迭代→保持B-1b ≥0，使C -CBB-1 A≤ 0，即CBB-1 A≥ C
对偶单纯形法：①找基B ，满足C - CBB-1 A≤ 0，但B-1b 不全≥0
②迭代→保持C -CBB-1 A≤ 0，使B-1b ≥0
对偶单纯形法基本步骤 max 型(min 型)
(1)、作初始表，要求全部
≤ 0 (≥0)
(2)、
判定：全≥0，停。否则，取令第 l 行的XBl 为换出变量. (3)、确定换入变量
① 若x l行的alj 全≥0 ，停，原问题无可行解。 ② 若x l 行的alj 有alj
xk
为换入变量
(4)、以alk 为主元，换基迭代* 关于①的解释：第 l 个方程(B-1 b)l= xil +∑ alj xj
即
某xj 从0 ，xil 不能变>0 ②为保持σj ≤ 0 ，即对偶解可行性 例题:求解下列线性规划
minw=45y1+80y2 +90y3→max(-w)=-45y1-80y2 -90y3 y1 +2y2 +y3 ≥ 4 →-y1 -2y2 -y3+y4=-4 y1 +y2 + 3y3 ≥ 5 →-y1 -y2 - 3y3 +y5=- 5
y1 … y3 ≥
15、如何从原问题的单纯形表中找出对偶问题的解？
原问题的解看表的左侧，其中基变量对应的值就是b 对应的列，非基变量等于零；对偶问题的解看表的下侧检验数行，原问题变量对应的检验数为对偶问题松弛变量的值乘以-1，原问题松弛变量的检验数为对偶问题变量的值乘以－1。 (见13题例题)
16、对偶解的经济含义？
经济解释：
w=Yb=(y1 … ym ) bi ： 第 i 种资源的数量 yi ：对偶解
= b1 y1 + b2 y2 + … + bm ym
bi 增加 bi , 其它资源数量不变时, 目标函数的增量
yi ：反映bi 的效益(成本)
14小题例中y1 =7/2, 当A 资源数增加1个单位时，工厂可增加利润7/2个单位。 应用
情况① 某资源对偶解>0，该资源有利可图，可增加此种资源量；某资源对偶解为0，则不增加此种资源量。
情况② 直接用影子价格与市场价格相比较，进行决策，是否买入该资源。 情况③ 利用影子价格，通过分析新产品使用资源的经济效果，以决定新产品是否应该投产
17、灵敏度分析需要研究和解决的问题？PPT3-2(增加约束条件的不在重点范围内）
18、目标规划的数学模型同一般线性规划数学模型的相同和异同之点？
原材料价格上涨，超计划要高价购买，所以要严格控制。在原材料严格控制的基础上考虑：
(1)、市场情况，产品Ⅰ销售量下降，产品Ⅰ的产量不大于产品Ⅱ的产量。 (2)充分利用设备，不希望加班。
(3)尽可能达到并超过利润计划指标56千元。
表格为不同点
相同点：都有决策变量、目标函数和约束条件
19、目标规划模型的建立及求解？
建模：(1)、设定约束条件。(目标约束、绝对约束)
(2)、规定目标约束优先级。(3)、建立模型 求解：PPT4-2图解法;4-3单纯形法
20、分枝定界法求解问题的主要思想和主要步骤？PPT5-2，p3
21、割平面法的基本思路及如何建立割平面？PPT5-2，p17
割平面法是通过生成一系列的平面割掉非整数部分来得到最优整数解的方法。
割平面法的基本思路是：
当得到的解不满足取整约束时，就设法在问题上增加一个约束条件，把包含这个非整数解的一部分可行域从原来的可行域中割除，但不割掉任何一个整数可行解。这个新增加的约束条件就称为割平面。
用割平面法解例题： 求解以下的线性规划 Max z = x1 + x2
- x1 + x2 = 0
表中解为非整数解， 所以为建立割平面，首先考虑非整数解中余数最大的基变量，此例中x1、 x2的余数均为3/4，不妨选取x2 ： x2 +3/4 x3 +1/4 x4 =7/4
现将各系数分成整数和非负分数两部分，从而可得： (1+0)x2+(0+3/4) x3+(0+1/4) x4 =(1+3/4) 将整数部分的变量移至等式右端有：
3/4 x3 +1/4 x4 =3/4+（1- x2 ） 非负整数解 (1- x2)为整数，左端非负故有： 3/4 x3 +1/4 x4 =3/4+非负整数 从而：
3/4 x3 +1/4 x4 >=3/4 或 x2
表3（最终单纯形表）
22、0-1整数规划模型的建立？PPT5-2，p25
常见：背包问题、工厂选址问题、项目投资问题、产品成本问题、非此即彼的决策条件。
一般形式如下：
m ax Z =∑C i =1n i X i ⎧n ⎪∑a i X i ≤b ⎨i =1⎪Xi =0或或1 1⎩
23、要对一个问题决策，具备的几个条件？
（1）性质和目标明确
（2）至少有2个以上的行动方案
（3）不同方案得失（经济损益值）可计算
（4）决策环境（确定、完全不确定、大致概率）
24、随机型决策和风险型决策的方法？
——随机型决策（不确定性决策，概率未知p217）
（1）等概率准则（等可能）
（2）乐观主义决策准则（最大最大）
（3）悲观主义决策准则（最小最大）
（4）乐观系数准则（折衷）
（5）后悔值准则（最小机会损失）
——风险型决策（概率已知）其特点见p220。考点如下:
（1）期望值决策原则
（2）决策树法（会看决策树p223）
（3）贝叶斯法（p225）