找到使成本函数最小化的组合

本文介绍了找到使成本函数最小化的组合的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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))