运筹学考试重点及模拟题

1，max z = -2x1+3x2-6x3

3x14x26x322xx2x11123s.t. 的对偶规划是 其对应的对偶规划的解（影子价格）为

x3x2x5231xj0(j1,2,3)2，以下四个约束条件中至少满足两个：

5x13x242x5x312  试用0-1变量来表示此要求

x3x7213x1x253，某钻井队要从10个可供选择的井位中确定5个钻井探油，问：怎样选择，才能使钻探费用最小？已知10个井位的代号为sj(j=1,2,3……,10),相应的钻探费用为cj(j=1,2,……，10),并且井位选择上须满足以下限制条件： ⑴ 或选择s1和s7，或选择s8 ⑵ 选择了s3或s4就不能选s5，反之亦然 ⑶在s5,s6,s7,s8中最多只能选两个 试建立此问题的0-1规划模型

4,图的概念： 非空点集V与连接点的某个线集E的二元组为图

多重边，多重图，简单图，度（次）d(v),孤立点，悬挂点， 定理：设G为简单图，则d(v)<=p-1(p为点） 设G为任何图，则

d(v)2q

vV 设G为任何图，则其奇点个数必为偶数 点边相连成为一条链

各边不相同，成为简单链，各点不同，成为初等链 初等链一定是简单链

连通图（任意两点间至少存在一条链）

一笔画成=G为简单链=无几点，或者只有两个奇点且为此链的起始端 子图，部分子图，真子图，生成子图，支持子图（连接所有点，并保持连通性）

无圈的连通图称为树

含圈的图G连通的充分必要条件为G有支撑树 G=（V，E，W）为赋权图

总权最小的树称为最小支撑树

弧集{aij=(vi,vj) viv1,vjv1}称为分离vs与vt 的一个截集 ，S=（V1，

v1）和值为截量，记为，c(s)

最小截集=最大流

图为Euler 图的充分必要条件为G连通且恰有两个奇点

Euler 链指G中存在含有所有边的简单链，Euler圈就是闭合的Euler链（与邮递员问题相通，不走回头路，但起始点又要求相同） 5，证明：如下序列不可能是某种简单图的次的序列 ⑴7654321 ⑵ 7654331 ⑶6654331 ⑷6554321 6，邮递员问题 5 5 6 10 4 求解此赋权图的中国邮递员问题 8 3 7，最小生成树：（从权最短的边找起，直到连接了所有的点） 8，网络图，时间参数问题，工序总时差，工序单时差

二，灵敏度分析

设有线性规划

Max z= x1+2x2+x3

2x1x2x322xx5x6123 s.t.

4xxx6123xj0(j1,2,3)分析在下列各种情况下，最优解是否发生改变，若改变并求出变化后的最优解 ⑴ c1=1变为c1*=8 ⑵c2=2变为c2*=4 ⑶b3=6变为c3*=3 ⑷a21=2变为a21*=1

三，求解下列运输问题 Ai Cij Bj A1 A2 A3 bj B1 B2 B3 B4 a i 15 14 26 10 10 12 16 11 11 21 27 23 100 120 80 80 90 130 140

四，最小分配问题

四项工作要甲乙丙丁四人去完成，每项工作只允许一个人完成，每个人只完成其中一项工作，已知每个人完成各项工作所需时间如表所示，问，应如何分配，才能使所需总时间最少？ 人员 1 2 3 4 成绩 工作 甲 乙 丙 丁 15 18 21 24 19 23 22 18 26 17 16 19 19 21 23 17 五，用扩展单纯形法求解目标规划

Minf= P1(d1-)+P2(d2+)+P3(8d3- + 5d4-) x1x2d1d1100x1x2d2d290 s.t.xd13d380

x2d4d455x1,x20;di,di0(i1,2,3,4)+ P4 (d1+)

六，求下列各图从v1到各点的最短路 ⑴ v3 V4 2 4 3 4 6 v1 1 v6 v7

6 3

3 4 7 v8 v5 1

v2 3 v5 4 v8 4 5 2 2 2 2 7 ⑵ v1 6 v4 v6 2 v9 5 8 v11 4 5 1 2 3 4 3

v3 6 v7 5 v10

v2

七，生成树法决策

某书店希望订购新出版的一部书籍，据以往经验，新书的销售数可能为50，100，150，200册，已知每册书定价40元，售价60元，剩书处理价20元，试分别用悲观准则，乐观准则，均等准则和后悔准则来确定该书的订购数量

然后书店统计过去销售规律如表所示，试用决策树法进行决策 需求量 比例（%） 50 20 100 40 150 30 200 10

八，求解矩阵对策

11 2004143021 