[Date Index]
[Thread Index]
[Author Index]
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/
Prev by Date:
**Re: Problem with Maximize and conditions.**
Next by Date:
**Re: Problem with Maximize and conditions.**
Previous by thread:
**Problem with Maximize and conditions.**
Next by thread:
**Re: Re: Problem with Maximize and conditions.**
| |