当前位置：问答库＞考研试题

一、简答题

1． 简述目标规划单纯形法求解的基本思想。

【答案】第一步，建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K 行，置k=l; 第二步，检查该行中是否存在负数，且对应的前k 一1行的系数是零。若有负数取其中最小者对应的变量为换入变量，转第三步。若无负数。则转第五步;

第三步，按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别 的变量为换出变量;

第四步，按单纯形法进行基变换运算，建立新的计算表，返回第二步;

第五步，当k=K时，计算结束。表中的解即为满意解。否则置k=k+l，返回到第二步。 2． 试写出标准指派问题的线性规划问题。 【答案】

A ij 表示工作人员i 做工作j 时的工作效益 则得线性规划模型为:

3． 什么是可行流?

【答案】满足下列条件的网络流f 称为可行流 （l ）容量限制条件:对每一弧（v i ，v j ）对于起点Vs ，记对于终点V t ，记

（2）平衡条件 对于中间点，流出量=流入量，即对每个

式中，V （f ）称为这个可行流f 的流量，即发点的净输出量（或收点的净输入量）。 4． 简述求解整数规划分枝定界法的基本思想。

【答案】设有最大化的整数规划问题A ，与它对应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z*的上界，记作;

而A 的任意可行解的目标函数值将是z*的一个下界域（称为分支）的方法，逐步减小和增大

; 。分支定界法就是将B 的可行域分成子区

:， 最终求到z*。

二、计算题

5． 某人在未来四年中需要一辆汽车代步，一辆新车的购买价格为36000元，每年的使用和维护费用如表所示。在每年末，他可选择继续使用现有汽车或再买新车，若再买新车，他可将现有旧车折价出售，出售价格如 表所示。

（l ）试建立求解此四年间最佳购车计划的图论模型;

（2）试用图论方法确定什么样的购车策略（每年末继续使用旧车还是购买新车）才能使总费用最少? 该费 用为多少?

表 购车数据（单位：元）

【答案】

（1）构建图论模型，如图所示。

图

（2）最优方案为第二年末换新车，这样费用最少，具体为31500x2=63000元。 6． 用运输问题的表上作业法求解线性规划问题:

【答案】由题意，得到运价表为:

由此可得，该问题是个运输平衡问题。

第一步，用沃格尔法得到初始方案为

第二步，用位势法得到初始方案中非基变量的检验数为

从上述计算可得，所有非基变量的检验数均大于0，所以该初始方案就是最优方案。 即x ll =10，x 13=20，x 22=15，x 23=5 7． 试解二次规划

【答案】上述二次规划问题可改写为下列形式:

显然，目标函数为严格凸函数，并且

因为c 1，c 2小于0，引入人工变量z 1，z 2并在前面取负号，得到如下的线性规划模型:

解之得:

于是，