摘要
本文研究线性规划标准型的基本假设所蕴含的一些性质,并探讨整数线性规划最优解和其松弛问题最优解的关系.首先,分别讨论四种情形下线性规划最优解的性质,即无约束线性规划问题、仅有非负约束的线性规划问题、仅有等式约束的线性规划问题,以及标准线性规划问题系数矩阵的列向量有为零的情形等.然后,构造两族二维整数线性规划,其松弛问题的最优解与其(整数)最优解"相距甚远".
In this paper,some properties contained in the basic assumptions of the linear programming in standard form are studied,and the relation between the optimal solution of integer linear programming and that of its relaxation problem is discussed.First,the properties of the optimal solution of linear programming under four conditions are discussed respectively,including the unconstrained linear programming,the linear programming with only non-negative constraint,the linear programming with only equality constraint,and the standard linear programming with at least one zero-valued column vector in coefficient matrix.Then,two classes of two dimensional problems of integer linear programming are constructed,and the optimal solutions of their relaxation problems are'far away'from their own(integer)optimal solution,respectively.
作者
孟香惠
施保昌
胡新生
MENG Xianghui;SHI Baochang;HU Xinsheng(Learning Center,Shenzhen Open University,Shenzhen 518001,China;School of Mathematics and Statistics,Huazhong University of Science and Technology,Wuhan 430074,China;Education Technology Center,Shenzhen Open University,Shenzhen 518001,China))
出处
《应用数学》
CSCD
北大核心
2019年第2期466-470,共5页
Mathematica Applicata
基金
深圳广播电视大学重点课题(SD17-001)
关键词
线性规划
标准型
整数线性规划
松弛问题
最优解
Linear programming
Standard form
Integer linear programming
Relaxation problem
Optimal solution
