R中的非线性离散优化 [英] Nonlinear discrete optimization in R
问题描述
我有一个简单的(确实标准的经济学)非线性约束的离散最大化问题在R中解决,有麻烦。我找到了问题的解决方案(非线性最大化;离散最大化),但不是所有问题的并集。
这里是问题。消费者想购买三种产品(凤梨,香蕉,饼干),知道价格,预算为20欧元。他喜欢品种(即,如果可能,他想拥有所有三个产品),他的满意度在消耗量上减少(他喜欢他的第一个曲奇方式比他的100)。
他希望最大化的功能是
当然,由于每个都有价格,并且他的预算有限,他在
我想要做的是找到最佳购买清单(N ananas,M香蕉,K饼干)满足约束。
如果问题是线性的,我只需使用linprog :: solveLP()。但目标函数是非线性的。
如果问题是一个连续的问题,它将是一个简单的解析解决方案。
问题是离散和非线性,我不知道
这里是一些玩具数据。
df < - data.frame(rbind(c(ananas,2.17),c(banana,0.75),c(cookie,1.34)))
names(df) c(product,price)
我想要一个优化程序
任何提示?
1)没有软件包这可以通过暴力来完成。使用 df
从问题输入,确保 price
是数字(这是 df
),并为每个变量计算最大数字 mx
。然后创建变量计数的网格 g
,并计算每个和相关目标的
给予 total
gg
。现在按照目标的降序排序 gg
,并采用满足约束的那些解。 head
将显示前几种解决方案。
.numeric(as.character(df $ price))
mx< - ceiling(20 / price)
g< - expand.grid(ana = 0:mx [1],ban = 0: mx [2],cook = 0:mx [3])
gg < - transform(g,total = asmatrix(g)%*%price,objective = sqrt(ana * ban * cook))
best< - subset(gg [order(-gg $ objective),],total <= 20)
给予:
>头(最好)#第一行是最好的,第二行是次最好等
ana ban cook总目标
1643 3 9 5 19.96 11.61895
1929 3 7 6 19.80 11.22497
1346 3 10 4 19.37 10.95445
1611 4 6 5 19.88 10.95445
1632 3 8 5 19.21 10.95445
1961 2 10 6 19.88 10.95445
2)dplyr 这也可以使用dplyr包来很好地表达。使用 g
和价格
:
library(dplyr)
g%>%
mutate(total = c(as.matrix(g)%*%price),objective = sqrt(ana * ban * cook ))%>%
过滤器(总< = 20)%>%
arrange(desc(objective))%>%
top_n(6)
给予:
按目标选择
ana ban cook总目标
1 3 9 5 19.96 11.61895
2 3 7 6 19.80 11.22497
3 3 10 4 19.37 10.95445
4 4 6 5 19.88 10.95445
5 3 8 5 19.21 10.95445
6 2 10 6 19.88 10.95445
I have a simple (indeed standard in economics) nonlinear constrained discrete maximisation problem to solve in R and am having trouble. I found solutions for parts of the problem (nonlinear maximisation; discrete maximisation) but not for the union of all the problems.
Here is the problem. A consumer wants to buy three products (ananas, banana, cookie), knows the prices and has a budget of 20€. He likes variety (i.e., he wants to have all three products if possible) and his satisfaction is decreasing in the amount consumed (he likes his first cookie way more than his 100th).
The function he wishes to maximise is
and of course since each has a price, and he has a limited budget, he maximises this function under the constraint that
What I want to do is to find the optimal buying list (N ananas, M bananas, K cookies) that satisfies the constraint.
If the problem were linear, I would simply use linprog::solveLP(). But the objective function is nonlinear. If the problem were of a continuous nature, ther would be a simple analytic solution to it.
The question being discrete and nonlinear, I do not know how to proceed.
Here is some toy data to play with.
df <- data.frame(rbind(c("ananas",2.17),c("banana",0.75),c("cookie",1.34))) names(df) <- c("product","price")
I'd like to have an optimization routine that gives me an optimal buying list of (N,M,K).
Any hints?
解决方案1) no packages This can be done by brute force. Using
df
from the question as input ensure thatprice
is numeric (it's a factor in thedf
of the question) and calculate the largest numbermx
for each variable. Then create gridg
of variable counts and compute thetotal
price of each and the associatedobjective
givinggg
. Now sortgg
in descending order of objective and take those solutions satisfying the constraint.head
will show the top few solutions.price <- as.numeric(as.character(df$price)) mx <- ceiling(20/price) g <- expand.grid(ana = 0:mx[1], ban = 0:mx[2], cook = 0:mx[3]) gg <- transform(g, total = as.matrix(g) %*% price, objective = sqrt(ana * ban * cook)) best <- subset(gg[order(-gg$objective), ], total <= 20)
giving:
> head(best) # 1st row is best soln, 2nd row is next best, etc. ana ban cook total objective 1643 3 9 5 19.96 11.61895 1929 3 7 6 19.80 11.22497 1346 3 10 4 19.37 10.95445 1611 4 6 5 19.88 10.95445 1632 3 8 5 19.21 10.95445 1961 2 10 6 19.88 10.95445
2) dplyr This can also be nicely expressed using the dplyr package. Using
g
andprice
from above:library(dplyr) g %>% mutate(total = c(as.matrix(g) %*% price), objective = sqrt(ana * ban * cook)) %>% filter(total <= 20) %>% arrange(desc(objective)) %>% top_n(6)
giving:
Selecting by objective ana ban cook total objective 1 3 9 5 19.96 11.61895 2 3 7 6 19.80 11.22497 3 3 10 4 19.37 10.95445 4 4 6 5 19.88 10.95445 5 3 8 5 19.21 10.95445 6 2 10 6 19.88 10.95445
这篇关于R中的非线性离散优化的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!