运筹学复习整理（保准管用）

1. 简答题

（1） 运筹学的工作步骤

提出和形成问题：即要弄清问题的目标，可能的约束，问题的可控变量以及相关的参数，搜集相关资料；

建立模型：即把问题中可控变量，参数，目标与约束之间的关系用模型表示出来；

求解：用各种手段将模型求解，解可以是最优解，次优解，满意解。复杂模型的求解需用计算机，解得精度要求可有决策者提出；

解的检验：首先检查求解步骤和程序有无错误，然后检查解是否反映现实问题；

解的控制：通过控制解的变化过程决定对解是否做一定的改变； 解的实施：是指将解用到实际中必须考虑的实际问题，如向实际部门讲清解的用法，在实施中可能产生的问题和修改。

（2）

退化产生原因及解决办法

单纯形法计算中用θ规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。 勃兰特规则：

1.选取cj-zj＞0中下标最小的非基变量xk为换入变量，即k=min(j｜cj-zj＞0)

2.当按θ规则计算存在两个和两个以上最小比值时，选取下标最小的基变

量为换出变量。

（3）对偶问题的经济解释

Z??cjxj??biyi??j?1i?1nm?Z?bi?yi? 这说明yi是右端项bi每增加一个单位对目标函数Z的贡献。 ? 对偶变量yi在经济上表示原问题第i种资源的边际价值。

? 对偶变量的值yi*所表示的第i种资源的边际价值，称为影子价值。

1

若原问题的价值系数Cj表示单位产值，则yi称为影子价格； 若原问题的价值系数Cj表示单位利润，则yi称为影子利润。

影子价格不是资源的实际价格，而是资源配置结构的反映，是在其它数据相对稳定的条件下某种资源增加一个单位导致的目标函数值的增量变化。

（4）分枝定界法步骤

a) 先求出整数规划相应的LP(即不考虑整数限制)的最优解， b) 若求得的最优解符合整数要求，则是原IP的最优解； c) 若不满足整数条件，则任选一个不满足整数条件的变量来构造新的约束，在原可行域中剔除部分非整数解。

d) 然后，再在缩小的可行域中求解新构造的线性规划的最优解，这样通过求解一系列线性规划问题，最终得到原整数规划的最优解。

（5）树的性质

一个无圈的连通图称为树。 1 树至少有两个悬挂点。

2 一个图为树的充要条件是：不含圈，边数比点数少1. 3 一个图为树的充要条件是：连通，边数比点数少1. 4 一个图为树的充要条件是：任两点之间恰有一条链。

2. 建模题

（1）线性规划建模：

目标函数max(min)z?c1x1?c2x2???cnxn约束条件a11x1?a12x2????a1nxn?(?,?)b1a21x1?a22x2????a2nxn?(?,?)b2???????(1.2)(1.3)2

(1.1)am1x1?am2x2????amxn?(?,?)bmx1,x2,??,xn?0（2）目标规划建模：

最好等于：min d--d+

最好不大于：min d+ 最好不小于：min d-

?K minZ?Pk?Lk(w?kld??w??lkldl) k?1l?1 绝对约束2,...,m ?naijxj?(?,?)bii?1,j?1

?n c?kjxj?dk?d?k?E*kk?1,2,...,K

j?1非负性约束

x?j,dk,d?k?0j?1,2,...,n

目标的重要程度不同，用优先等级因子Pk来表示第k等级目标。优先等级因子Pk是正的常数，Pk>>Pk+1 。

同一优先等级下的目标的相对重要性，赋以不同的加权系数w

（3） 整数规划模型

Max (min) Z = Σcjxj s.t.Σaijxj? bi(i=1,2,…m) xj? 0且部分或全部是整数

3

目标约束 3. 证明题

（1）证明可行域为凸集

为了证明满足线性规划问题的约束条件

?Pxjj?1nj?b,xj?0,j?1,2,?,n的所有点(可行解)组成的集合是凸集，只要证明D中任意两点连线上的点必然在D内即可。 设 ?1??1??1??1?T

??X????x??,x??,?,x???X?x1,x2,?,xn122222nT是D内的任意两点；X(1)≠X(2)。 则有n

Pjx?j1??b,x?j1??0,j?1,2,?,n

j?1 n Pjx?j2??b,x?j2??0,j?1,2,?,nj?1

令 X=(x1，x2，…，xn)T为x(1),x(2)连线上的任意一点，即 (1)(2)X=αX+(1-α)X (0≤α≤1)

X的每一个分量是xj??x?j1??(1??)x?j2?，将它代入约束条件， 得到nn

Pjxj?Pj?x?j1??1??x?j2? j?1j?1 nnn?1??2? ??Pjxj?Pjxj??Pjx?j2?j?1j?1j?1

??b?b??b?b

???????????又因 x?j1?,x?j2??0,??0,1???0，所以xj≥0，j=1,2,…,n。 由此可见X∈D，D是凸集。 证毕。

（2）证明无界解的判定

构造一个新的解X(1)，它的分量为

x?1??b'??a'

iii,m?k???0??1?xm?k??j?m?1,?,n,并且j?m?k1?x??0;j因σm+k＞0，所以对任意的λ＞0都是可行解，把x(1)代入目标函数内得

4

z=z0+λσm+k；

因σm+k＞0，故当λ→+∞，则z→+∞，故该问题目标函数无界。

（3）证明弱对偶性

设原问题是maxz?CX;AX?b;X?0 因X是原问题的可行解，所以满足约束条件,即 AX?b 若Y是对偶问题的可行解，将Y左乘上式，得到 YAX?Yb 原问题的对偶问题是:min??Yb;YA?C;Y?0 因Y是对偶问题的可行解，所以满足YA?C 将X右乘上式,得到YAX?C. 于是得到CX?YAX?Yb证毕.

4. 计算题

（1） 标准型，单纯行法计算

c j?c1?cmcm?1?cn ????????? CBXBbx1?xmxm?1?xn c1x1b11?0a1,m?1?a1n c2x2b20?0a2,m?1a2n ??????? cmxmbm0 ?1am,m?1?amn mm ?z??mcibi0?0cm?1??ciai,m?1?cn??ciain

i?1i?1i?1

?i?1?2?m5

?

本文来源：https://www.bwwdw.com/article/g6w2.html