一道《运筹学》作业题引发的思考.docx

一道运筹学作业题引发的思考 打开文本图片集 摘要：当线性规划问题的可行域有界时，线性规划问题的最优解肯定是基可行解之一。此时，单纯形法等价于在线性规划问题的多面体形态的可行域的顶点之间的逐步寻优。可是，可行域有界的先决条件间或会被遗忘。本文是作者在运筹学教学中，由一道作业题以及习题解答中遇到了这种遗忘后的一点思索。 关键词：线性规划；基可行解；可行域；最优解 中图分类号：O221.1 文献标记码：A 文章编号：1674-932435-0210-02 一、问题来源 在运筹学1的习题1.3，和运筹学2的习题2.3中，题目这样描述：“在下面的线性规划问题中找出满意约束条件的全部基解。指出哪些是基可行解，并代入目标函数，确定哪一个是最优解。” 从题目描述1-2上看，只要找出全部基可行解，再将全部基可行解代入目标函数进行比较，就可以在基可行解中找到最优解。而各个版本的相关习题解答3-8也都是这样给出解答的。 可是，这种在基可行解中找寻最优解的做法只有在满意“可行域有界”的先决条件下才是正确的1-2，9。 下面我们来分析原问题的可行域是否有界。 二、可行域有界性的检验 由4个决策变量和2个线性约束方程知，原问题的可行域位于4维空间中的一个2维子空间上。 1.原问题的等价变换。 将原问题中的等式约束进行行变换后，可化为如下的等价约束， 利用原问题的等价约束，可在原问题的目标函数中消去决策变量x1，x4，化为如下等价的目标函数， 2.原问题的等价问题的可行域图示。 从原问题的等价问题的不等式约束可看出，原问题的可行域可描述在如图1所示的2维平面O-x2x3上。 由图1可看出，原问题的可行域是无界的。因此，通过将基可行解代入目标函数不肯定能找到最优解。 3.原问题可行域无界的进一步分析。 事实上，由等价约束可看出，对于随意的正数x3，x1=6.8+3.1x3，x2=0，x4=1.4+1.3x3，都是原问题的可行解。此时，原问题的目标函数为，z=23.4+19.3x3。 当x3趋于正无穷时，目标函数z=23.4+19.3x3趋于正无穷。原问题是有无界解的线性规划问题。 三、结论 所以，对于可行域无界且有无界解的原问题，即使求出了全部的基可行解，并通过比较这些基可行解所对应的目标函数值，找到了其中的最大值。但这个取有限值的最大值所对应的基可行解却肯定不是原问题的最优解。因为，原问题是有无界解的优化问题。 以上关于这道作业题的分析说明，在运用先找出全部基可行解，然后再通过比较来找寻线性规划问题最优解这种方法之前，肯定要推断线性规划问题的可行域是否有界。否则，当可行域无界时，通过基可行解来找寻最优解的方法可能会失效。 参考文献： 1甘应爱，田丰，李维铮，等.运筹学M.第3版.北京：清华高校出版社，2022：44. 2运筹学教材编写组.运筹学M.第4版.北京：清华高校出版社，2022：55. 3周华任.运筹学解题指导M.北京：清华高校出版社，2022：9-11. 4罗荣桂.运筹学同步辅导与考研指南M.武汉：华中科技高校出版社，2022：9-10. 5张晋东，孙胜利.运筹学全程导学及习题全解M.北京：中国时代经济出版社，2022：5-6. 6边文思，焦艳芳.运筹学同步辅导及习题全解M.北京：中国水利水电出版社，2022：7-10. 7周华任，刘常昱，陈玉金，等.运筹学全程学习指导与习题精解M.清华第4版.南京：东南高校出版社，2022：5-7. 8陈志平，徐宗本.计算机数学计算困难性理论与NPC、NP难问题的求解M.北京：科学出版社，2003：3. 9Frederick S. Hillier，Gerald J. Lieberman. Introduction to Operations ResearchM.McGraw-Hill Education，2022. 第4页 共4页第 4 页 共 4 页第 4 页 共 4 页第 4 页 共 4 页第 4 页 共 4 页第 4 页 共 4 页第 4 页 共 4 页第 4 页 共 4 页第 4 页 共 4 页第 4 页 共 4 页第 4 页 共 4 页