数学的实践与认识
數學的實踐與認識
수학적실천여인식
MATHEMATICS IN PRACTICE AND THEORY
2011年
11期
82-90
,共9页
李裕梅%连晓峰%徐美萍%曹显兵
李裕梅%連曉峰%徐美萍%曹顯兵
리유매%련효봉%서미평%조현병
整数规划%割平面法%割平面方程的构造%四个关键点
整數規劃%割平麵法%割平麵方程的構造%四箇關鍵點
정수규화%할평면법%할평면방정적구조%사개관건점
割平面法是求解整数规划问题常用方法之一.用割平面法求解整数规划的基本思路是:先用单纯形表格方法去求解不考虑整数约束条件的松弛问题的最优解,如果获得的最优解的值都是整数,即为所求,运算停止.如果所得最优解不完全是整数,即松弛问题最优解中存在某个基变量为非整数值时,就从最优表中提取出关于这个基变量的约束等式,再从这个约束式出发构造一个割平面方程加入最优表中,再求出新的最优解,这样不断重复的构造割平面方程,直到找到整数解为止.主要研究以下四个关键点:一是研究从最优表中提取出的、关于基变量的约束等式出发,通过将式中的系数进行整数和非负真分数的分解,从而得到一个小于等于0的另外一个不等式的推导过程;二是总结出从小于等于0的那个约束不等式出发构造割平面方程的四种方法;三是分析构造割平面方程的这四种方法相互之间的区别和联系;四是探讨割平面法的几何意义.通过对这四个方面的分析和研究,对割平面法进行透彻的剖析,使读者能够全面把握割平面法.
割平麵法是求解整數規劃問題常用方法之一.用割平麵法求解整數規劃的基本思路是:先用單純形錶格方法去求解不攷慮整數約束條件的鬆弛問題的最優解,如果穫得的最優解的值都是整數,即為所求,運算停止.如果所得最優解不完全是整數,即鬆弛問題最優解中存在某箇基變量為非整數值時,就從最優錶中提取齣關于這箇基變量的約束等式,再從這箇約束式齣髮構造一箇割平麵方程加入最優錶中,再求齣新的最優解,這樣不斷重複的構造割平麵方程,直到找到整數解為止.主要研究以下四箇關鍵點:一是研究從最優錶中提取齣的、關于基變量的約束等式齣髮,通過將式中的繫數進行整數和非負真分數的分解,從而得到一箇小于等于0的另外一箇不等式的推導過程;二是總結齣從小于等于0的那箇約束不等式齣髮構造割平麵方程的四種方法;三是分析構造割平麵方程的這四種方法相互之間的區彆和聯繫;四是探討割平麵法的幾何意義.通過對這四箇方麵的分析和研究,對割平麵法進行透徹的剖析,使讀者能夠全麵把握割平麵法.
할평면법시구해정수규화문제상용방법지일.용할평면법구해정수규화적기본사로시:선용단순형표격방법거구해불고필정수약속조건적송이문제적최우해,여과획득적최우해적치도시정수,즉위소구,운산정지.여과소득최우해불완전시정수,즉송이문제최우해중존재모개기변량위비정수치시,취종최우표중제취출관우저개기변량적약속등식,재종저개약속식출발구조일개할평면방정가입최우표중,재구출신적최우해,저양불단중복적구조할평면방정,직도조도정수해위지.주요연구이하사개관건점:일시연구종최우표중제취출적、관우기변량적약속등식출발,통과장식중적계수진행정수화비부진분수적분해,종이득도일개소우등우0적령외일개불등식적추도과정;이시총결출종소우등우0적나개약속불등식출발구조할평면방정적사충방법;삼시분석구조할평면방정적저사충방법상호지간적구별화련계;사시탐토할평면법적궤하의의.통과대저사개방면적분석화연구,대할평면법진행투철적부석,사독자능구전면파악할평면법.
