A-A+
考虑整数线性规划问题(整数线性规划问题) 设其中A b的元素均为有理数．试证：如果对应松弛问
问题详情
考虑整数线性规划问题(整数线性规划问题)，设其中A，b的元素均为有理数．试证：如果对应松弛问题(伴随问题)有可行解，但目标函数在可行域上无下界，则问题(整数线性规划问题)或者无可行解或者目标函数在可行解集上无下界．
参考答案
如果问题整数线性规划问题有可行解，设x(0)为其可行解．存在K={x|Ax=b，x≥0}的一个极射向y(0)，使cy(0)＜0．y(0)是方程组Ay=0，eTy=1的基解．由于A的元素均为有理数，可知y(0)的各分量亦为有理数．乘以适当倍数M(＞0)后使各分量都化为整数．记
