线性规划标准型和整数线性规划最优解的两个注记

作者：孟香惠; 施保昌^*; 胡新生

来源：应用数学, 2019, 32(02): 466-470.

DOI：10.13642/j.cnki.42-1184/o1.2019.02.044

• 线性规划
• 标准型
• 整数线性规划
• 松弛问题
• 最优解

本文研究线性规划标准型的基本假设所蕴含的一些性质,并探讨整数线性规划最优解和其松弛问题最优解的关系.首先,分别讨论四种情形下线性规划最优解的性质,即无约束线性规划问题、仅有非负约束的线性规划问题、仅有等式约束的线性规划问题,以及标准线性规划问题系数矩阵的列向量有为零的情形等.然后,构造两族二维整数线性规划,其松弛问题的最优解与其(整数)最优解"相距甚远".

• 单位
  华中科技大学; 深圳广播电视大学