单位文秘网 2021-07-21 08:12:03 点击: 次
信息即该多胞形的全部顶点。虽然,在理论上我们已经知道有界不等式系统和多胞形的等价性,但是这个定理的证明本身并没有提供计算多胞形全部顶点的算法。而Danzig所提出的单纯形算法理论,提供了求解这些顶点坐标的理论工具。基于多面体顶点的基本定义,可以简单的得到结论:多胞形的顶点一一对应于任一定义在这个多胞形上线性规划的基本可行解。即:
求解给定线性不等式组对应多胞形的顶点问题等价于求解该多面体上线性规划基本可行解。
基于这个结论,可以得到如下多项式时间的多胞形顶点坐标求解算法:
Step1:对于给定的线性不等式组Ax≤b,考虑其增广矩阵,选取一组极大线性无关行向量组得到与原不等式组等价的不等式组■;
Step2:选取■全部的极大线性无关列向量组,对■的每一个极大线性无关列向量组■,其实是一个满秩的方阵,■即可求得一个基本可行解,即一个顶点的坐标。遍历所有这样的■,就可以求得全部顶点的坐标。
3.2找出目标函数下降(上升)方向,并以此为法方向绘制一条与可行域交集非空的初始等值线
目标函数的下降(上升)方向甚至是梯度方向都是容易求解的,因为目标函数的梯度正是目标系数向量。但是寻找初始与可行域交集非空的等值线则是一件复杂的事情。事实上,初始等值线的选取问题等价于如下问题:
找到■,使得线性不等式组{Ax≤b,cx=c0}解集非空,即寻找一个原线性规划的初始可行解。在运筹学中,两阶段法是用来构造求解初始可行解的常用手法。两阶段法简要如下:
Step1:将线性不等式组Ax≤b化成标准型中的等式组,每一个不等式添加非负的一个人工松弛变量变量;
Step2:构造新的目标函数,及最小化人工变量之和;
Step3:求解该线性规划,如求得的最优解的目标函数值为0,则该最优解为原问题的可行解;如目标函数值大于0,则原问题无可行解。
在求得初始可行解x0以后,即可选取cx=cx0为初始等值面。
3.3沿目标函数下降(上升)方向平移等值线(面),直至边界
在该步骤中,主要的难点在于如何判定等值面是否到达边界。一方面,由于移动的是等值面,故在图解算法过程中并不记录当前可行解的信息,所以单纯形算法所使用的检验系数判定方法难以奏效。另一方面,图解算法的移动行为非常近似于使用连续优化技巧的线性规划内点算法,所以三维图解法的边界判定算法可以借鉴连续优化的判定方法。
在连续优化中,通常并不严格计算一个点是否落在可行域边界上,而是通过完成判定是否落在可行域内,然后通过线搜索算法逐渐逼近最值点或边界点。对应到线性规划问题上,其实就是求解如下判定问题:
给定任意■,判断线性不等式组{Ax≤b,cx≤c0}解集上是否为空。
线性不等式组的解存在问题可以借助Farks引理来转换成线性等式组来处理。
Farks引理:令A是一个矩阵,b是一个向量。那么线性不等式组Ax≤b有解,当且仅当对于所有满足yA=0的行向量y,有yb≥0。
事实上,这里就相当于求解出yA=0的全部基本可行解,并逐一判断是否满足yb≥0。
到此为止,已经把LP图解法中每一个子问题推广到n维空间中(自然包括三维),并对每一个子问题给出了求解算法,藉此摆脱了原LP图解法的直观经验性描述而将其上升至了具有一般意义的数学算法。
三维LP图解法的演示算法的改进
这一章节主要研究三维LP图解的演示动画实现算法。对于动画演示,重点是体现等值面从初始位置连续移动至可行域边界的过程。由于在演示动画中,并不会显示具体的算法,所以为了提升算法的运算速度,我们可以对上文中的图解算法进行简化和改进。
仔细分析上文中的图解算法,发现初始等值面的选取(两阶段法的第一阶段)以及边界判定(不等式组解集是否为空)的计算量都至少等于一次同等规模的线性规划算法的计算量,对于动画演示来说,其实有相当一部分的运算是无意义的,所以针对动画演算,采取如下简化算法:
Step1:绘制可行域;
Step2:初始点选取。以-c为目标系数,求解线性规划,以求得的最优值作为初始等值面;
Step3:计算移动终止位置。以c为目标系数,求解线性规划,以求得的最优值作为等值面终止位置。
Step4:从初始位置开始,直至终止位置连续绘制等值面移动动画。
这样在整个过程中,step2和step3的运算量就压缩到了两次同规模线性规划算法的运算量,经过实验对比,在不改变动画演示效果的同时,可以极大地加快程序的运行速度。
基于MATLAB三维LP图解法演示系统的仿真与实现
借助MATLAB GUI设计并实现交互式的三维LP图解法演示系统。
首先,使用edit控件设计了参数读入界面。在演示系统中,我们默认的是考虑极大化问题,且可行域限制在第一卦限,即■。并且出于简化考虑,仅考虑三个变量和三个线性不等式约束。
在读入线性不等式以后,求出全部基本可行解,即求得可行域多胞形全部顶点坐标,通过MATLAB图形学工具箱自带的convhull,通过顶点坐标计算得到多胞形全部侧面的数据,再使用mergeCoplanarFaces函数,将共面的全部小多边形合并成大的侧面,最终完成可行区域的绘制。
等值面移动动画通过以下方法完成,对于处于最小值和最大值中间状态的任意一个等值面cx=c0,将可行域分割成两个部分{ax≤b,cx≥c0}以及{ax≤b,cx≤c0}两个相邻接的多面体,用不同的颜色绘制,以此标注等值面。
最后通过drawnow和pause命令生成动画,并实时显示当前可行解及其对应的目标函数值,当动画停止时所显示的即为最优解和最优值。
在此基础上,通过改变线性规划约束中的系数我们可以实现三维线性规划图解法的动态展示。
总结与展望
本文在掌握了二维线性规划图解法的基本原理、方法和步骤的基础上,对多维线性规划问题图解法的实现进行了理论分析,并且对三维线性规划的图解法利用MATLAB编程,编制了仿真模拟软件。该程序可以实现对三维LP模型中各参数在一定范围内的灵活设置,将三维线性规划问题优化的整个过程通过动态效果展示,界面编排合理,使用灵活方便,作为辅助教学软件能够使学生对线性规划问题的性质有更深的理解。同时基于对多维线性规划问题实质的分析,在三维图解法程序的基础上我们也很容易扩展到三维以上线性规划问题的图解法仿真模拟,未来的研究工作可以考虑设计一个通用程序,通过自由设置问题优化空间的维数实现各维数线性规划问题图解法的动态效果展示。
参考文献:
[1] Alexander Schrijver, Theory of Linear and Integer Programming, John Wiley and Sons. 1998.
[2] Frederick S. Hillier and Gerald J. Lieberman, Introduction to Operations Research, 8th edition. McGraw-Hill.
[3] 关玉昆 三维空间线性规划问题的图解法[J],辽宁大学学报, 1999,18卷1期。
[4] 邓先礼,最优化技术,重庆大学出版社,1998.
[5] 申卯兴,许进 求解线性规划的单纯形法的直接方法,计算机工程与应用,2007,30期,p94-96.
[6] 燕子宗,费浦生,万仲平. 线性规划的单纯形法及其发展,计算数学,2007,1期.
[7] JH. Mathews, KD. Fink. Numerical methods using MATLAB. 1999.
[8] 张志通. MATLAB教程,北京航空航天大学出版社,2006.
[9] 钱俊,吴金洪,程茗. 线性规划问题的MATLAB求解. 科技创新导报. 2011,25期,p158.
[10] 龙林川, 浅谈二变量线性规划问题的图解法. 科技信息,2012,25期,p138-139.
(作者单位:浙江省宁波市公安海警学院)
(责任编辑:单位文秘网) )地址:https://www.kgf8887.com/show-153-68545-1.html
上一篇:压缩机零部件经济订购批量模型分析
版权声明:
本站由单位文秘网原创策划制作,欢迎订阅或转载,但请注明出处。违者必究。单位文秘网独家运营 版权所有 未经许可不得转载使用