一道组合优化题

一、题目

设两个向量r和c，m和n是向量的下标，m和n是整数，满足如下条件：

1）0<r_1<r_2<...<r_n；

2）c_1>c_2>...>c_m>0；

3）0<m<n；

试问：r_1*c_1+r_2*c_2+...+r_m*c_n是所有的组合中最小的吗？如果是最小的，给出证明过程。

例如：

1）r_1,r_2,...,r_n等于1,2,...,n; 

2）c_1,c_2,...,c_m等于m,m-1,...,1；

3）n=5,m=3；

则方案1：r_1*c_1+r_2*c_2+...+r_m*c_n=3*1+2*2+1*3=10。

其他的组合方案，例如

3*2+2*1+1*3=11

3*2+2*3+1*1=13

3*1+2*3+1*2=11

3*3+2*1+1*2=13

3*3+2*2+1*1=14

可以看出方案1比其它的方案都要小。

二、组合优化

    组合优化是数学优化方法 Mathematical Optimization的一个子领域，与运筹学 Operations Research、算法理论 Algorithm Theory和计算复杂性理论 Computational Complexity有关。它在人工智能 Artificial Intelligence、机器学习 Machine Learning、拍卖理论 Auction Theory、软件工程 Software Engineering、应用数学 Applied Mathematics和理论计算机科学 Theoretical Computer Science等领域有着重要的应用。

    组合优化主要是从一个有限的对象集合中寻找一个最佳对象。在许多这样的问题中，穷举搜索 exhaustive search 是不易处理的。如果这些优化问题可行解集是离散的，或者可行解集可以化为离散的，那么可以在问题范围内进行运算，其目标是找到最优解。典型的问题是旅行商问题 Traveling Salesman Problem(“ TSP”)、最小生成树问题(“ MST”)和背包问题 Knapsack Problem。

    一些研究文献认为离散优化 Discrete Optimization 是由整数规划 Integer Programming和组合优化组成的（反过来由解决图结构的优化问题组成），尽管所有这些主题的研究文献都紧密地交织在一起。它通常涉及如何有效地分配用于寻找数学问题解决方案的资源的决策。

参考文献：

[1] https://swarma.org/?p=30960

原文始发于微信公众号（豆豆咨询）：一道组合优化题