Целочисленная оптимизация в Mathematica? - PullRequest
Новая
       25

Целочисленная оптимизация в Mathematica?

3 голосов
/ 26 марта 2011

У меня проблема с целочисленным программированием.У меня труба длиной 10м.Я хочу вырезать как можно больше кусков по 1,2 метра, а затем отрезать оставшуюся часть трубы на куски по 100 мм.Я должен оставить 100 мм для машины, чтобы захватить.Как я могу оптимизировать это в Mathematica?Я могу решить это как равенство, я думаю, но если я просто хочу получить ответ прямо.По сути, как можно больше y, тогда x: es.

Maximize[{x*100+y*1200, x*100+y*1200<9900},{x,y},Integers] просто дает мне график неравенстваИ да, я проверил инструкции на wolfram.

Ответы [ 5 ]

3 голосов
/ 26 марта 2011

Поскольку 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}}
1 голос
/ 26 марта 2011

Чтобы ответить на простой вопрос по номиналу, вместо того, чтобы сделать его игрушечным примером оптимизации, вот один из методов «объединения» числа. 

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
1 голос
/ 26 марта 2011

Решение Велизария - самый простой способ через 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

1 голос
/ 26 марта 2011

Используйте для x,y и т. Д. Значение >0 etc, и вы, наконец, сможете получить значение с помощью //N

Mathematica не предполагает, что вы находитесь в реальном мире!

0 голосов
/ 27 марта 2011 
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}}}}}}

Это начало, но это плохо, потому что мне нужно как-то лучше учитывать приоритет, и мне нужно закончить количество каждой трубы.Каким-то образом я думаю, что количество должно быть принято во внимание и в приоритетном порядке.

...