Re: Problem with Maximize and conditions.
- To: mathgroup at smc.vnet.net
- Subject: [mg51053] Re: [mg51046] Problem with Maximize and conditions.
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Sun, 3 Oct 2004 05:47:19 -0400 (EDT)
- References: <200410020719.DAA26384@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
On 2 Oct 2004, at 16:19, Nacho wrote: > *This message was transferred with a trial version of CommuniGate(tm) > Pro* > Hello. > > I was trying to solve a problem with Mathematica 5 and I am getting > strange results. > > The problem is: > > Minimize x+y+z, with the condition that 1/20x+y+5z==100 and x,y,z are > Integers between 1 and 98 (inclusive). > > So I use: > > Minimize[{x+y+z, 1/20 x+y+5z\[Equal]100, x \[Element] Integers, > y \[Element] Integers, z\[Element]Integers, 0<x<99,0<y<99,0<z<99}, > {x,y, > z}] > > I have copied the text using "Plain text" option, I hope it's fine. > > This returns the same expression, I suppose that Mathematica cannot > resolve it. So I use NMinimize: > > NMinimize[{x+y+z, 1/20 x+y+5z\[Equal]100, x \[Element] Integers, > y \[Element] Integers, z\[Element]Integers, 0<x<99,0<y<99,0<z<99}, > {x,y, > z}] > > Now I get a result, but rather weird... > > \!\({25.`, {x -> 1, y -> 5, z -> 1899\/100}}\) > > The minimum of x+y+z is 25 but z is 1899/100 > 1899/100 is not a Integers, and the nearest Integer, 19, doesn't > satisfy 1/20x+y+5z==100, and also x+y+z is not 25 but 24.99 > > I don't know why Mathematica has returned a Real when I specified an > Integers. I suppose that it is related to the use of NMinimize. I > suppose that it considers that 18.99 is so near of 19 that it can be > considered an Integer. > > If you remove the condition of z being an Integer, the result changes, > so it is affecting. Also, if you ask for "1899/100 e Integers" it > returns False. > > So, does anybody know how to solve this? Ideally, I would like to know > why Minimize doesn't work (so I have to use NMinimize), but in any > case, how to solve the problem. > > Thanks! > > First, let us solve the problem. In[1]:= p = List @@ Apply[List, Reduce[{(1/20)*x + y + 5*z == 100, 0 < x < 99, 0 < y < 99, 0 < z < 99}, {x, y, z}, Integers], {1}] Out[1]= {{x == 20, y == 4, z == 19}, {x == 20, y == 9, z == 18}, {x == 20, y == 14, z == 17}, {x == 20, y == 19, z == 16}, {x == 20, y == 24, z == 15}, {x == 20, y == 29, z == 14}, {x == 20, y == 34, z == 13}, {x == 20, y == 39, z == 12}, {x == 20, y == 44, z == 11}, {x == 20, y == 49, z == 10}, {x == 20, y == 54, z == 9}, {x == 20, y == 59, z == 8}, {x == 20, y == 64, z == 7}, {x == 20, y == 69, z == 6}, {x == 20, y == 74, z == 5}, {x == 20, y == 79, z == 4}, {x == 20, y == 84, z == 3}, {x == 20, y == 89, z == 2}, {x == 20, y == 94, z == 1}, {x == 40, y == 3, z == 19}, {x == 40, y == 8, z == 18}, {x == 40, y == 13, z == 17}, {x == 40, y == 18, z == 16}, {x == 40, y == 23, z == 15}, {x == 40, y == 28, z == 14}, {x == 40, y == 33, z == 13}, {x == 40, y == 38, z == 12}, {x == 40, y == 43, z == 11}, {x == 40, y == 48, z == 10}, {x == 40, y == 53, z == 9}, {x == 40, y == 58, z == 8}, {x == 40, y == 63, z == 7}, {x == 40, y == 68, z == 6}, {x == 40, y == 73, z == 5}, {x == 40, y == 78, z == 4}, {x == 40, y == 83, z == 3}, {x == 40, y == 88, z == 2}, {x == 40, y == 93, z == 1}, {x == 60, y == 2, z == 19}, {x == 60, y == 7, z == 18}, {x == 60, y == 12, z == 17}, {x == 60, y == 17, z == 16}, {x == 60, y == 22, z == 15}, {x == 60, y == 27, z == 14}, {x == 60, y == 32, z == 13}, {x == 60, y == 37, z == 12}, {x == 60, y == 42, z == 11}, {x == 60, y == 47, z == 10}, {x == 60, y == 52, z == 9}, {x == 60, y == 57, z == 8}, {x == 60, y == 62, z == 7}, {x == 60, y == 67, z == 6}, {x == 60, y == 72, z == 5}, {x == 60, y == 77, z == 4}, {x == 60, y == 82, z == 3}, {x == 60, y == 87, z == 2}, {x == 60, y == 92, z == 1}, {x == 80, y == 1, z == 19}, {x == 80, y == 6, z == 18}, {x == 80, y == 11, z == 17}, {x == 80, y == 16, z == 16}, {x == 80, y == 21, z == 15}, {x == 80, y == 26, z == 14}, {x == 80, y == 31, z == 13}, {x == 80, y == 36, z == 12}, {x == 80, y == 41, z == 11}, {x == 80, y == 46, z == 10}, {x == 80, y == 51, z == 9}, {x == 80, y == 56, z == 8}, {x == 80, y == 61, z == 7}, {x == 80, y == 66, z == 6}, {x == 80, y == 71, z == 5}, {x == 80, y == 76, z == 4}, {x == 80, y == 81, z == 3}, {x == 80, y == 86, z == 2}, {x == 80, y == 91, z == 1}} This gives all the integer solutions of your set of equations. Now lets find which one ahs the minimum value: In[2]:= Ordering[x + y + z /. {ToRules[Reduce[{(1/20)*x + y + 5*z == 100, 0 < x < 99, 0 < y < 99, 0 < z < 99}, {x, y, z}, Integers]]}] Out[2]= {1, 2, 3, 4, 5, 20, 6, 21, 7, 22, 8, 23, 9, 24, 10, 39, 25, 11, 40, 26, 12, 41, 27, 13, 42, 28, 14, 43, 29, 15, 58, 44, 30, 16, 59, 45, 31, 17, 60, 46, 32, 18, 61, 47, 33, 19, 62, 48, 34, 63, 49, 35, 64, 50, 36, 65, 51, 37, 66, 52, 38, 67, 53, 68, 54, 69, 55, 70, 56, 71, 57, 72, 73, 74, 75, 76} This means its the first one. The values of the variables where the minimum was found are: p[[1]] {x == 20, y == 4, z == 19} The minimum value is: Plus @@ p[[1,All,2]] 43 So rather larger than 25. Now, as for the other part. Well, the methods used by Minimize are quite unable to dealwith integer problems and the methods used by NMinimize are, say, not terribly good. Basically you have to try to adjust various options in NMinimize and see if you can get a better result. One problem is, of course, that it is hard to know how "good' the answer you are getting is. The other problem is that the options used by NMinimize are not terribly well documented, so you have to do some guessing. By trying various options the best I have been able to do is NMinimize[{x + y + z, (1/20)*x + y + 5*z == 100, (x | y | z) $B":(B Integers, 0 < x < 99, 0 < y < 99, 0 < z < 99}, {x, y, z}, Method -> {"DifferentialEvolution", "ScalingFactor" -> 0, "PenaltyFunction" -> (100*(#1 - Floor[#1]) & )}] {42., {x -> 20, y -> 3, z -> 96/5}} which is not bad. but what really puzzles me is that giving NMinimize the correct solution as an initial point does not seem to help; NMinimize[{x + y + z, (1/20)*x + y + 5*z == 100, (x | y | z) $B":(B Integers, 0 < x < 99, 0 < y < 99, 0 < z < 99}, {x, y, z}, Method -> {"DifferentialEvolution", "ScalingFactor" -> 0, "PenaltyFunction" -> (100*(#1 - Floor[#1]) & ), InitialPoints -> {{20, 4, 19}}}] {42., {x -> 20, y -> 3, z -> 96/5}} ???? Andrzej Kozlowski Chiba, Japan http://www.akikoz.net/~andrzej/ http://www.mimuw.edu.pl/~akoz/
- Follow-Ups:
- Re: Re: Problem with Maximize and conditions.
- From: DrBob <drbob@bigfoot.com>
- Re: Re: Problem with Maximize and conditions.
- References:
- Problem with Maximize and conditions.
- From: ncc1701zzz@hotmail.com (Nacho)
- Problem with Maximize and conditions.