五千年(敝帚自珍)

主题:【讨论】吃胡萝卜的驴的主人的烦恼 -- 独角兽

共:💬53 🌺43
全看分页树展 · 主题 跟帖
家园 哈哈,如果你很严肃地要最优方案的话

那只好上数学了。

胡萝卜最多3000颗,小毛驴顶多拉三趟。假设小毛驴拉三趟走过x1公里,拉两趟走过x2公里,拉一趟走过x3公里。所以有约束条件

x1 + x2 + x3 - 1000 = 0

显然 x1>=0,x2>=0,x3>=0

小毛驴拉三趟时消费的胡萝卜是 5x1 颗,所以

5x1 + x4 - 3000 = 0 (x4 >= 0)

小毛驴拉两趟时最多有胡萝卜不能超过2000颗

-5x1 + x5 + (3000 - 2000) = 0 (x5 >= 0)

它消费的胡萝卜是 3x2 颗,所以

5x1 + 3x2 + x6 - 3000 = 0 (x6 >= 0)

小毛驴拉一趟时最多有胡萝卜不能超过1000颗

-5x1 - 3x2 + x7 + (3000 - 1000) = 0 (x7 >= 0)

它消费的胡萝卜是 x3 颗,所以

5x1 + 3x2 + x3 + x8 - 3000 = 0 (x8 >= 0)

农夫的目标是尽可能多卖胡萝卜,他的目标函数是

max y = -5x1 - 3x2 - x3 + 3000

根据上述目标函数及约束条件,用单纯形法得最优解 (200,333.33,466.67,2000,0,1000,0,533.33)

然而,胡萝卜是整根的,所以x1、x2、x3必须取整数(也就是说这是一个整数规划问题)。在最优解附近用穷举法验算,得整数最优解x1=200,x2=333,x3=467。最终目标函数值为y=533

全看分页树展 · 主题 跟帖


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河