查看完整版本: 为一道简单的数学题想破头了。。。

为一道简单的数学题想破头了。。。

现在有三个不同类型的 T- Shirt package，里面有小，中，大三种号的衬衫。

A类型：2小，5中， 3大
B类型：5小，8中， 2大
C类型：4小，6中，10大

现在必须整包发货，收货方必须最少收到45小，78中，52大。

同时，为了减少发货成本，请寻找A，B，C三者之和的可能最小值。（假设三者发货成本相同）

A，B，C,必须是正整数，可以为0

第二个要求，用矩阵解出并证明。。。

带约束的多元非线性规划问题哈

Min A+B+C

subject to

2A+5B+4C>=45

5A+8B+6C>=78

3A+2B+10C>=52

然后据此列出kuhn-Tucker conditions 求解。

[quote]原帖由 [i]Oskarlre[/i] 于 2007-11-5 02:11 PM 发表
现在有三个不同类型的 T- Shirt package，里面有小，中，大三种号的衬衫。

A类型：2小，5中， 3大
B类型：5小，8中， 2大
C类型：4小，6中，10大

现在必须整包发货，收货方必须最少收到45小，78中，52大。 ... [/quote]

[[i] 本帖最后由 mike 于 2007-11-5 02:36 PM 编辑 [/i]]

为什么需要类型A呢？每一种都比C包含得少。
使用A不产生任何得正效应。

整数规划... KKT不一定适用......

[quote]原帖由 [i]mike[/i] 于 2007-11-5 02:32 PM 发表
带约束的多元非线性规划问题哈

Min A+B+C

subject to

2A+5B+4C>=45

5A+8B+6C>=78

3A+2B+10C>=52

然后据此列出kuhn-Tucker conditions 求解。

[/quote]

整数规则，KKT不一定适用啊。 而且还要用矩阵证明。 因为必须正整数。 所以数学解80/21 可以是3，可以是4

那么A，B，C三者都各自可能有两种情况

在满足条件下的最小数combination如何求解？

嗯，这好像是传说中的knapsack problem。题目看似简单，解法好像可不简单。

我依稀记得是在随机过程的课程上讨论过一种解法。:han2:han2:han2

[quote]原帖由 [i]imac[/i] 于 2007-11-5 02:38 PM 发表
整数规划... KKT不一定适用......

[/quote]

If it is Knapsack problem, try dynamic programming

这是一个线性整数规划，所以解就在feasible set (opportunity set)的边界上的整点处

解法应该就是遍历所有如下形式的解

(A,B,C)是一组可行解，同时(A-1,B,C)，(A,B-1,C)，(A,B,C-1)都违反需求

我想应该是没有多项式时间算法的吧...

[quote]原帖由 [i]mike[/i] 于 2007-11-5 03:17 PM 发表
嗯，这好像是传说中的knapsack problem。题目看似简单，解法好像可不简单。

我依稀记得是在随机过程的课程上讨论过一种解法。:han2:han2:han2

[/quote]

LP有interior point method，ILP一般是NP-hard。:)

其实这些文章都只是在灌水而已... :) 只有你那句follow simplex method才对oskarlre有用，呵呵 :kuangxiao :kuangxiao

[[i] 本帖最后由 imac 于 2007-11-5 05:48 PM 编辑 [/i]]

编个程序把所有可能的情况都扫一遍，算出11 （0，6，5 或者 0，7，4）
不知道怎么证明。。。