如何求两线性函数的最小差值？

fjn6869930

Z=aX-bY（a,b为常量，X，Y为整数且存在一定范围）求Z的最小值？

lhempire

从方程上看,它是三维空间当中的一个平面, x和y限定范围后,得到的是一个空间的平行四边形
z最小,就是平行四边形的空间包围盒的最低点上
既然是一个线性关系,极值都发生在边界上,用x和y范围的四个边界点计算出z就是了

zhangjk

这是最简单的线性规划(LP)问题,可以用许多方法来求解,例如"作图法"解决.

fjn6869930

还是不明白

muscle1

只要判断一下a和b的符号吧，如果a是小于等于0的，取X的最大植，否则X取最小值；如果b是小于等于0的，取Y的最小植，否则Y取最大值.这样得到的Z值肯定是最小的。

muscle1

就是说Z是由aX和-bY两部分组成的，如果两部分都取得最小值的话，Z的值肯定是最小的，而在一定范围内两部分的最小值是很好求的，就是上面的了。

suny00059

运行于Linux的代码：

#include <iostream>

using namespace std;

int main()
{
        int a,b;
        int X_min,X_max;
        int Y_min,Y_max;
        int Z;
        int X,Y;
        int doonce=0;

        cout<<"Input a,b"<<endl;
        cin >> a >> b;
        cout<<"Input X_min,X_max"<<endl;
        cin >> X_min >> X_max;
        cout<<"Input Y_min,Y_max"<<endl;
        cin >> Y_min >> Y_max;
       
        for (X=X_min;X<=X_max;X++)
        {
                for (Y=Y_min;Y<=Y_max;Y++)
                {
                        if (doonce==0)
                        {
                                Z = a*X - b*Y;
                                doonce = 1;
                        }
                        if (Z < (a*X - b*Y))
                        {
                                Z = a*X - b*Y;
                        }
                }
        }
        cout<<"The min of a*X - b*Y = "<<Z<<endl;
        return 0;
}

suny00059

我忘了加绝对值

suny00059

对了那个小于号改成大于号，不然就是求最大值了

fjn6869930

Z=aX-bY（a,b为常量，实数，X，Y为整数且存在一定范围）求|Z|的最小值？
前面是忘了加绝对值，这个题是难在求|Z|的最小值？

如果只求Z的最小值，就如lhempire的答案，即ax的最小值减by的最大值。

感谢suny00059的程序，事实上我在做案例中，X，Y可能是一个较大的范围，也可能需要同时在一个实数的集合中选取两个或者两个以上的数作为a，b来运算，所以用穷举法可能会导致数量级的计算时间，现想找到一个可以找到最小或者接近最小|Z|的思路。