Mathematica 中的整数优化？

Question

我有一个整数规划问题。我有一根10m长的管子。我想切出尽可能多的 1.2 米的片段，然后将管道的其余部分切成 100 毫米的片段。我必须留100毫米给机器抓取。我如何在mathematica中优化它？我想我可以把它作为一个等式来解决，但如果我只是想直接得到答案。 基本上，先有尽可能多的 y，然后是 x:es。

Maximize[{x*100+y*1200, x*100+y*1200<9900},{x,y},Integers] 只是给我一个不等式图。 是的，我已经检查过 Wolfram 的说明。

Answer 1

由于 9900 和 1200 都是 100 的倍数，因此算法就是

TotLen = 9900;
numberOf1200pieces = IntegerPart[TotLen/1200];
numberOf100pieces  = IntegerPart[(TotLen - 1200 numberOf1200pieces)/100];

Print["Number of 1200mm pieces: ", numberOf1200pieces];
Print["Number of 100mm pieces: ", numberOf100pieces];
Print["Leftover: ", 9900 - numberOf1200pieces 1200 - numberOf100pieces 100,"mm"];

Number of 1200mm pieces: 8
Number of 100mm pieces: 3
Leftover: 0mm

您也可以尝试：

Maximize[{x*100 + y*1200, x*100 + y*1200 == 9900}, {x, y}, Integers]
->{9900, {x -> 3, y -> 8}}

Answer 2

使用假设 x,y 等为 >0 等，您最终将能够使用 //N 获得一个值

Mathematica 不会假设您在现实世界中！

Answer 3

贝利撒留的解决方案是通过Maximize实现的最简单方法。然而，它需要将不平等改为平等，这并不反映你的意图。相反，使用 v.7，我会添加第二个条件

Maximize[{x*100 + y*1200, x*100 + y*1200 <= 9900, y > x > 0}, 
         {x, y}, Integers] -> {9900, {y -> 8, x -> 3}} 

新条件 (y > x > 0) 反映了您的意图，即首先选择较大的部分更好。另请注意，我将不等式 (<) 更改为 <=，因为您的除法正好为 9900。

Answer 4

为了从表面上回答这个简单的问题，而不是将其推断为优化的玩具示例，这里有一种“统一”数字的方法。

Floor[ FoldList[Mod, #, Most@#2] / #2 ] &[ 9900, {1200, 100} ]

---

贝利撒留暗示我的回答太天真了，我认为这可能是一种有效的方法，尽管对于更复杂的情况来说效率较低。考虑将 9950 分成长度 12、75 和 1200。

i = 9950;

While[x = Quiet@IntegerPartitions[i--, All, {12, 75, 1200}, 1]; x === {}]

x[[1]] // Tally

Answer 5

decideOrderOfProduction[itemsToProduce_] := 
 Map[#[[1]] &, Sort[itemsToProduce, #1[[2]] > #2[[2]] &]]
minimizeWaste[pipe1_, pipe2_] := {
  Maximize[{pipe1*x + pipe2*y, pipe1*x + pipe2*y <= 4900, 
    y >= x >= 0}, {x, y}, Integers]
  }
minimizeWaste[pipe_] := {
  Maximize[{pipe*x, pipe*x <= 4900, x >= 0}, x, Integers]
  }
planProduction[itemsToProduce_] := {
  productionOrder = decideOrderOfProduction[itemsToProduce];
  strategy = {};
  While[Length[productionOrder] >= 2,
   pipe1 = productionOrder[[1]];
   pipe2 = productionOrder[[2]];
   strategy = 
    Append[strategy, {pipe1, pipe2, minimizeWaste[pipe1, pipe2]}];
   productionOrder = Drop[productionOrder, 2];];
  If[Length[productionOrder] == 1,
   strategy = 
    Append[strategy, {productionOrder[[1]], Null, 
      minimizeWaste[productionOrder[[1]]]}]];
  strategy
  }


items = {{99, 1}, {200, 12}, {1200, 2}, {90, 5}, {70, 1200}};
decideOrderOfProduction[items]
planProduction[items]

{70, 200, 90, 1200, 99}

{{{70, 200, {{4900, {x -> 10, y -> 21}}}}, {90, 
   1200, {{4890, {x -> 1, y -> 4}}}}, {99, 
   Null, {{4851, {x -> 49}}}}}}

这是一个开始，但很糟糕，因为不知何故，我需要更好地考虑优先级，并且我需要完成每个管道的数量。不知何故，我认为金额也需要优先考虑。