运筹学复习题精选 .pdfVIP

1线性规划可行域的形状是多边形，而且是“凸”形的多边形。

2最优解在边界位置获得，而且是在某个顶点获得。

3标准型式特点：max型、等式约束、非负约束

4可行解：满足全部约束条件的解，记为X。

5最优解：可行解中最优的，记为X*。

6基本可行解(基可行解)：非负的基本解。

7对偶最优解的经济解释—资源的影子价格

8影子价格反映了资源的稀缺性，影子价格越高，则越稀缺。

9影子价格＞市场价格，则应买进该资源；影子价格＜市场价格，则应卖出该资源；资源C

的影子价格为0，则表明有剩余。

10Y*=(y1*,y2*,„„，ym*）为DP的最优解，则yi*表示LP某资源bi变化1个单位

对目标产生的影响，称yi*为bi的影子价格

11松弛问题：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数

规划问题的松弛问题。

12分支定界法就是将B的可行域分成子区域（称为分支方法）的方法，通过减小最优值的

上界和增大最优值的下界最终得到最优值。

13动态规划是一种将实际问题分解为更小的、相似的子问题，并存储子问题的解而避免计

算重复的子问题，以解决最优化问题的方法策略。

14适合于用动态规划方法求解的只是一类特殊的多阶段决策问题，即具有“无后效性”的

多阶段决策过程。指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策

所决定，与系统的历史无关。

15图是由点和边构成的，记为G=(V，E)，点表示研究对象，边表示研究对象之间的特定关

系；分为无向图，记为G=(V，E)，和有向图，记为D=(V，A)。

16图的每条边都有一个表示一定实际含义的权数，称为赋权图，记为D=(V，A，C)。

17关键路线：自始至终全部由关键工作组成的线路，或线路上总的工作持续时间最长的线

路为关键线路。

18等待的服务规则又可分为：先到先服务（FCFS）后到先服务（LCFS）随机服务（RAND）

带有优先权的服务（PS）

19例2（M/M/C/N/∞/LCFS）表示：到达间隔为负指数分布，服务时间也为负指数分

布，C个服务台，系统容量为N，顾客源无限，后到先服务。

20排队系统一般有三个基本组成部分：输入过程、排队规则、服务机构。

21边数=顶点数–1。

填空

1如图1所示，对于平面中的某LP的约束集合，其可行解为OGEDHO所围阴影区域，基本解为所在

直线及坐标轴的交点A、B、C、D、E、F、G、H、O以及GF延长线与纵轴交点共10个点，

基本可行解为O、H、D、E、G共5个点。

。

2线性规划问题有可行解，则必有基可行解。

选择

1下列关于线性规划最优解的论述中，其中不正确的是（c）。

A、线性规划的最优解满足所有约束条件

B、线性规划的最优解是使目标函数达到最优值的可行解

C、线性规划的最优解必然是基本可行解

D、线性规划的最优解可能不是唯一的

2对于线性规划问题，下列说法正确的是（D）

A、线性规划问题可能没有可行解

B、在图解法上，线性规划问题的可行解区域都是“凸”区域

C、线性规划问题如果有最优解，则最优解可以在可行解区域的顶点上到达

D、上述说法都正确

3若线性规划问题的最优解不唯一，则在最优单纯形表上（B）。

B、非基变量检验数必有为零

4线性规划问题最终解的情形有（C）

A、可行解、最优解、基本解和无解。B、可行解、基本可行解、基本解和最优解。

C、最优解、退化解、多重最优解和无解。D、最优解、退化解、多重解和无界解。

判断

1线性规划模型中增加一个约束条件，可行域的范围一般将缩小；减少一个一般将扩大。（√）

2LP问题的每一个基解对应可行域的一个顶点。(×)

线性规划问题的每一个基本可行解对应可行域的一个顶点。（√)

3若LP问题的可行域可伸展到无限，则该问题一定具有无界解。(×)

4一个动态规划问题若能用权图表达时，节点代表各阶段的状态，各条边代表了可

行的方案选择。（√）

5xj的检验数表示变量xj增加一个单位时目标函数值的改变量（√)

6对偶问题有可行解，则原问题也有可行解。(×)

7若某种资源的影子价格为零，则该资源一定有剩余(×)

8后续工序是紧后工序(×)

9直接成本与工程