时间戳

首页 > 解决方案 > cvxpy，线性优化，以编程方式构建问题，目标是几个变量的总和

mathematical-optimization - cvxpy，线性优化，以编程方式构建问题，目标是几个变量的总和

问题描述

我有一个问题需要优化某些产品的分配。每个产品都有一个权重（基本上客户喜欢它的程度）和一个类别（有些客户不接受每种产品）

我的数据看起来像这样

prod_name, category, weight
name1,     c1,    10
name2,     c1,    5
name3,     c1,    1
name4,     c2,    8
name5,     c2,    7
name6,     c2,    6

我还有一张表说我们有不同类别的债务（与上表相同的类别）

category, debt
c1,    100
c2,    500

我想最大化 X*weight（在这种情况下是两个六维向量的点积），在 , 的约束下x1 + x2 + x3 = 100（或者，可以认为它是说对应于类别 1 的变量必须加起来债务在第一类）和x4 + x5 + x6 = 500

实际上，我有 800 个类别，所以我想以编程方式进行，但我不知道如何开始构建这个问题。

目标很简单

Xxx = cvx.Variable(len(R))
objective = cvx.Maximize(cvx.sum_entries(Xxx.T*R))

其中 R 只是作为 numpy 数组的“权重”列

但我不知道如何建立约束。另外，我想跟踪名称（也就是说，一旦我得到解决方案，我需要将解决方案数组的所有元素映射回 prod_name 列中的名称）

cvxpy 是否允许这些事情中的任何一个，还是我需要查看其他包？

标签： mathematical-optimizationlinear-programmingcvxpy

解决方案

据我了解，以下内容应该可以实现您的目标。请注意，解决方案似乎非常简单：只需最大化权重项的数量来偿还债务，而不考虑其他选择。

#!/usr/bin/env python3

import cvxpy

#The data from your original post
weights = [
  {"name":'name1', "cat":'c1', "weight":10},
  {"name":'name2', "cat":'c1', "weight": 5},
  {"name":'name3', "cat":'c1', "weight": 1},
  {"name":'name4', "cat":'c2', "weight": 8},
  {"name":'name5', "cat":'c2', "weight": 7},
  {"name":'name6', "cat":'c2', "weight": 6}
]

#The data from your original post
debts = [
  {"cat": 'c1', "debt": 100},
  {"cat": 'c2', "debt": 500}
]

#Add a variable to each item in weights
for w in weights:
  w['var'] = cvxpy.Variable()

#Add up all the weight variables from each category
weights_summed_by_cat = dict()
for w in weights:
  if w['cat'] in weights_summed_by_cat:
    weights_summed_by_cat[w['cat']] += w['var']
  else:
    weights_summed_by_cat[w['cat']] = w['var']

#Create a list of debt constraints from the summed weight variables
constraints = []
for d in debts:
  if d['cat'] in weights_summed_by_cat:
    constraints.append(weights_summed_by_cat[d['cat']]<=d['debt'])

#Don't allocate negative amounts
for w in weights:
  constraints.append(w['var']>=0)

#Create the objective function
obj = cvxpy.Maximize(cvxpy.sum([w['weight']*w['var'] for w in weights]))

#Create a problem instance
prob = cvxpy.Problem(obj, constraints)

#Solve the problem and catch the optimal value of the objective
val = prob.solve()

#Print optimal value
print("Final value: {0}".format(val))

#Print the amount assigned to each weight
for w in weights:
  print("Allocate {0} of {1}".format(w['var'].value, w['name']))

推荐阅读