张钧 刘小茂



摘要:當线性规划问题的可行域有界时,线性规划问题的最优解一定是基可行解之一。此时,单纯形法等价于在线性规划问题的多面体形状的可行域的顶点(线性规划问题的基可行解)之间的逐步寻优。可是,可行域有界的先决条件偶尔会被遗忘。本文是作者在《运筹学》教学中,由一道作业题以及习题解答中遇到了这种遗忘后的一点思考。
关键词:线性规划;基可行解;可行域;最优解
中图分类号:O221.1 文献标志码:A 文章编号:1674-9324(2016)35-0210-02
一、问题来源
在《运筹学(第三版)》[1]的习题1.3(1),和《运筹学(第四版)》[2]的习题2.3(1)中,题目这样描述:“在下面的线性规划问题中找出满足约束条件的所有基解。指出哪些是基可行解,并代入目标函数,确定哪一个是最优解。”
从题目描述[1-2]上看,只要找出所有基可行解,再将所有基可行解代入目标函数进行比较,就可以在基可行解中找到最优解。而各个版本的相关习题解答[3-8]也都是这样给出解答的。
可是,这种在基可行解中寻找最优解的做法只有在满足“可行域有界”的先决条件下才是正确的[1-2,9]。
下面我们来分析原问题(1)的可行域是否有界。
二、可行域有界性的检验
由4个决策变量和2个线性约束方程知,原问题(1)的可行域位于4维空间中的一个2维子空间上。
1.原问题的等价变换。
将原问题(1)中的等式约束进行行变换后,可化为如下的等价约束,
利用原问题(1)的等价约束(2),可在原问题(1)的目标函数中消去决策变量x1,x4,化为如下等价的目标函数,……p>
教育教学论坛 2016年35期