找到使成本函数最小化的组合 [英] Find the combination that minimizes a cost function

问题描述

我遇到了一个问题，我将感谢所有能够提供帮助的人.问题如下:

I am facing a problem and I would be grateful to anyone that could help. The problem is the following:

考虑我们有一个向量D = [D1;D2;D3;...;DN]和一组时间实例TI = {t1,t2,t3,...,tM}.向量D，Di的每个元素对应于TI的子集.例如，D1可能对应于时间实例{t1,t2,t3}和D2至{t2,t4,t5}.

Consider that we have a vector D = [D1;D2;D3;...;DN] and a set of time instances TI = {t1,t2,t3,...,tM}. Each element of vector D, Di, corresponds to a subset of TI. For example D1 could correspond to time instances {t1,t2,t3} and D2 to {t2,t4,t5}.

我想找到与TI的所有元素相对应的D元素的组合，而不会多次考虑其中的任何一个，同时将成本函数sum(Dj)最小化. Dj是向量D的元素，每个元素对应一组时间实例.

I would like to find the combination of elements of D that corresponds to all elements of TI, without any of these being taken into account more than once, and at the same time minimizes the cost function sum(Dj). Dj are elements of vector D and each one corresponds to a set of time instances.

让我举个例子.让我们考虑一个向量

Let me give an example. Let us consider a vector

D = [15;10;5;2;35;15;25;25;25;30;45;5;1;40] 

和一组

TI={5,10,15,20,25,30} 

每个D元素对应

{[5 15];[5 20];[5 25];[5 30];[5 15 20];[5 20 25];[5 15 30];[5 20 25 30];[10 15];[10 20];[10 25];[10 15 20];[10 15 20 25];[10 30]} 

分别例如D(1)= 15对应时间实例[5 15].

respectively, e.g. D(1)=15 corresponds to time instance [5 15].

该程序必须提出的解决方案是D(4)和D(12)的组合(即分别为2和1)具有最小的总和并对应于所有时间实例.

The solution that the procedure has to come up with is that the combination of D(4) and D(12), i.e. 2 and 1 respectively, has the minimum sum and correspond to all time instances.

我不得不提到该过程必须能够处理大向量.

I have to mention that the procedure has to be able to work with large vectors.

感谢您的每次尝试！

推荐答案

二进制权重向量x在每个D_i上赋予权重.

The binary weight vector x places a weight on each D_i.

让f = [D1; D2; ...; DN].

Let f=[D1;D2;...;DN].

A的第j列，A_j是二进制向量.

Column j of A, A_j is a binary vector.

如果D_j对应于Tk，则A_jk为1，否则为零.

A_jk is 1 if D_j corresponds to Tk, else is zero.

问题是:

min f^T*x  s.t.  A*x=1;

然后使用 bintprog 解决.

x = bintprog(f,[],[],A,ones(M,1))

这篇关于找到使成本函数最小化的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！