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

一、证明题

1． 假设线性规划问题为:

其中，秩

运用单纯形算法求得的最优基可行解时，所有的非基变量检验数全都<0，试证明这时所得到的最优解必定 是线性规划问题（l ）的准最优解。

【答案】一般情况下，经过迭代后解变为

再将上式代入目标函数式，整理后得到

令

于是

再令

则 时，此时的解就为最优解。 这样当所有非基变量的检验数即

2． 证明:r （x ）二x12+x22是严格凸函数。

【答案】首先求导为（2x l ，2x 2:） 求海塞矩阵

为正定矩阵，所以f （x ）为严格凸函数

二、计算题

3． 求如图所示的中国邮递员问题。

图

【答案】按最短路线连接各奇点，如图所示。

由图可知，在图的每一条边上至多有一条重复边; 图中每圈上重复边的总权不大于该圈总权的一半。 所以任一欧拉圈就是最优邮递路线。

4． 某厂生产Ⅰ、Ⅱ、Ⅲ三种产品，其所需劳动力、原材料等有关数据如下:每件产品Ⅰ分别需要劳动力和 原材料6个小时和3公斤，每件产品Ⅱ分别需要劳动力和原材料为3小时和4公斤，每件产品m 分别需要劳动力 和原材料为5小时和5公斤; 拥有的劳动力和原材料总数分别为45小时和30公斤; 又知Ⅰ、Ⅱ、Ⅲ三种产品的 单件利润分别为3、1、4元。

要求:（l ）写出该厂获得最大的生产计划问题的线性规划模型并求出最优解;

（2）写出该线性规划问题的对偶问题，并求对偶问题的最优解;

（3）产品I 的利润在什么范围内变化时，上述最优计划不变?

（4）如果设计一种新产品W ，单件产品消耗劳动力8小时，原材料2公斤，每件可获利3元，问该产品是否值得生产?

（5）如果劳动力数量不变，原材料可以从市场购买，每公斤0.4元，问该厂是否购买原材料来扩大生产，以购买多少为宜?

【答案】（l ）设三种产品的产量分别为x l ，x 2，x 3。则可建立如下线性规划模型:

将上述线性规划模型化为标准型，并用单纯形法计算如表所示。