内容发布更新时间 : 2024/12/25 15:08:07星期一 下面是文章的全部内容请认真阅读。

19、简述线性规划模型主要参数（p11） （1）、价值系数：目标函数中决策变量前的系数为价值系数 （2）、技术系数：约束条件中决策变量前的系数 （3）、约束条件右边常数项

15、简述线性规划解几种可能的结果（情形）（ppt第二章39或89页）

（1）.有唯一最优解 (单纯形法中在求最大目标函数的问题时，对于某个基本可行解，所有δj≤0)

（2）.无可行解，即可行域为空域，不存在满足约束条件的解，也就不存在最优解了。

（3）.无界解，即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小，一般来说，这说明模型有错，忽略了一些必要的约束条件

（4）.无穷多个最优解，则线段上的所有点都代表了最优解

（5）退化问题，基变量有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，用图解法无退化解 1、简述单纯形法的基本思路（p70）

从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是,则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。

17、简述线性规划中添加人工变量的前提（p85）

在系数矩阵中直接找不到初始可行解，进而通过添加人工变量的方法来构造初始可行基，得出初始基本可行解

10、简述线性规划对偶问题的基本性质（p122）

（1）对称性（2）弱对偶性（3）强对偶性（4）最优性（5）互补松弛型

原函数与对偶问题的关系

1）求目标函数最大值的线性规划问题中有n 个变量 m个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有m个变量n个约束条件，其约束条件都为大于等于不等式。

2）原问题的目标函数中的价值系数为对偶问题中的约束条件的右边常数项，并

且原问题的目标函数中的第i个价值系数就等于对偶问题中的第i个约束条件的右边常数项。

3）原问题的约束条件的右边常数项为对偶问题的目标函数中价值系数。并且原问题的第i个约束条件的右边常数项就等于零对偶问题的目标函数中的第i个变量的系数。

4）对偶问题的约束条件的系数矩阵A是原问题约束矩阵的转置。 5、运输问题是特殊的线性规划问题，但为什么不用单纯形法求解

因为这类线性规划问题在结构上存在着特殊性,表上作业法根据运输问题的特点来设计的特殊的单纯形法，可以更加形象直观简单的解决运输问题。 9、简述表上作业法的基本步骤

（1）用最小元素法找出初始基可行解,也就是初始调运方案。对于有m个产地n个销地的产销平衡问题，则有m个关于产量的约束方程和n个关于销量的约束方程。由于产销平衡，其模型最多只有m+n-1个独立的约束方程，即运输问题有m+n-1个基变量。在m×n的产销平衡表上给出m+n-1个数字格，其相对应的调运量的值即为基变量的值。

（2）求各非基变量的检验数。

（3）用闭回路法来判别问题是否达到最优解。如已是最优解则停止计算，否则继续下一步。

（4）用闭回路法进行基变换，确定入基变量和出基变量，找出新的基本可行解。在表上用闭回路法调整。 11、简述指派问题的标准形式及数学模型（ppt或书上p179）

设n 个人被分配去做n 件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第i个人去做第j件工作的效率（时间或费用）为

Cij(i=1.2?n;j=1.2?n)并假设Cij ≥0。问应如何分配才能使总效率（时间或费用）最高？

12、简述分枝定界法的基本步骤

分枝定界法是先求解整数规划的线性规划问题。如果其最优解不符合整数条件，则求出整数规划的上下界，用增加约束条件的办法，把相应的线性规划的可行域分成子区域（称为分枝），再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界的距离，最后得整数规划的最优解。

基本思路：

1、先求出线性规划的解

2、确定整数规划的最优目标函数值z*初始上界和下界z 3、将一个线性规划问题分为两枝，并求解 4、修改最优目标函数上、下界

5、比较与剪枝 ：各分枝的目标函数值中，若有小于Z 者，则剪掉此枝，表明此子问题已经探清，不必再分枝了;否则继续分枝。

6、如此反复进行，直到得到Z＝Z*为止，即得最优解 X* 。 6、简述目标规划的目标函数主要类型及其数学表达式。

目标规划的目标函数只能取极小形式，即minz=f(d+,d-)，共有如下三种形式：（1）,要求恰好等于目标值，即希望决策值超过和不足目标值的部分都尽可能小，因此由函数minz=f(d++d-)；（2），要求不超过目标值，允许达不到目标值，即希望决策值不超过目标值，也希望d+越小越好，因此有minz=f（d+）;(3)要求不低于目标值，允许超过目标值，即希望决策值不低于目标值，也希望d-越小越好，因此有minz=f(d-).

2、简述运筹学中背包问题的一般提法（p225）

对于N种具有不同重量和不同价值的物品，在携带物品总重量限制的情况下，决定这N种物品中每一种物品多少数量装入背包内，使得装入背包物品的总价值最大。

4、建立动态规划模型时，应定义状态变量，请说明状态变量的特点

第一,可知性,即各阶段的状态变量的取值能直接或间接的确定；第二,能够确切的描述过程的演变且满足无后效性.

7、简述动态规划数学模型要点（ppt第十章18 论述题增加阶段和阶段变量）

（1）分析题意，识别问题的多阶段特性，按时间或空间的先后顺序适当划

分为满足递推关系的若干阶段，对分时序的静态问题要认为赋予“时段”概念；

（2）正确选择状态变量，状态变量应具备两个特征：第一，可知性，即各阶段的状态变量的取值能直接或间接的确定；第二，能够确切的描述过程的演变且满足无后效性；

（3）根据状态变量和决策变量的含义，正确写出状态转移方程； （4）根据题意明确过程指标函数和最优指标函数以及第k阶段指标函数的含义，并正确列出基本方程。

3、简述著名的哥尼斯堡七桥难题及答案

河上有7座桥，将河中的两个岛和河岸连结，如图1所示。一个散步者能否一次走遍7座桥，而且每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著名的图论问题。

C A D

B

欧拉证明了这样的走法不存在。欧拉是这样解决问题的：既然陆地是桥梁的连接地点，不妨把图中被河隔开的陆地看成A、B、C、D4个点，7座桥表示成7条连接这4个点的线，如图2所示。

于是“七桥问题”就等价于图3中所画图形的一笔画问题了。每个点如果有进去的边就必须有出来的边，从而每个点连接的边数必须有偶数个才能完成一笔画。图3的每个点都连接着奇数条边，因此不可能一笔画出，这就说明不存在一次走遍7座桥，而每座桥只许通过一次的走法。 8、简述树定义及性质

树:连通且不含圈的无向图称为树。

性质：（1）树无圈，m=n-1.(2) 树连通，m=n-1.(3) 树无圈，但每加一条新边，则可得到惟一一个圈.(4) 树连通，但任舍一条边，图就不连通.(5) 树中任意两点之间有惟一一条链相连. 16、简述求最小生成树的方法

（1）避圈法：将图中的边按权由小到大排序；按排序由小到大选定n－1条边为止，选择时每选一条边应避免和已选的边构成圈，且所选边是未选边中的最小权边。

（2）破圈法：在给定的赋权的连通图上任选一个圈；在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）；如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第1步。

18、简述决策按环境分类（分为哪几种）（p389）

确定型决策：在决策环境完全确定的条件下进行

不确定型决策：在决策环境不确定的条件下进行，决策者对个自然状态发生的概率一无所知

风险型决策问题：在决策环境不确定的条件下进行，决策者对各自然状态发生的概率可以预先估计或计算出来［非程序化决策：］ 13、简述不确定型决策的决策方法（决策准则）（p389）

（1）最大最小准则（悲观准则），决策者从最不利的角度去考虑问题； （2）最大最大准则（乐观准则），决策者从最有利的角度去考虑问题； （3）等可能性准则，决策者把各自然状态发生的机会看成是等可能的; （4）乐观系数准则(折衷准则)，决策者取乐观准则和悲观准则的折衷； （5）后悔值准则（沙万奇准则），决策者从后悔的角度去考虑问题