S.O.S. Mathematics CyberBoard

Your Resource for mathematics help on the web!
It is currently Tue, 29 Jul 2014 13:53:25 UTC

All times are UTC [ DST ]




Post new topic Reply to topic  [ 5 posts ] 
Author Message
PostPosted: Mon, 8 Mar 2010 15:37:21 UTC 
Offline
S.O.S. Newbie

Joined: Mon, 8 Mar 2010 14:37:24 UTC
Posts: 4
Folks this is the first time I am posting on this forum so please forgive any deviation from the application of forum policy.

I am trying to program a mathematical model in VBA but am not quite sure how to arrive at some of the stages.

The Model
I have to determine a set of numbers {n} with "An", a set of coefficients, that can be stochastic but adhere to the following constraints:

{n} can only belong to the following set:
=> n = {1, 2, 3, ... 8}

and An is the set of whole numbers
=> An = 0, 1, 2, 3, 4, ...

Target Constraint 1 = Eh
Target Constraint 2 = Pd


Find a possible combination of the Sum of Products where:

=> sum(An x n) = Eh & sum(An) = Pd

such that entropy is maximized. I.E. select the combination with maximum count of non-zero coefficients.

=> count(An) = MAXIMUM-POSSIBLE

Most solvers I have attempted use numerical techniques (e.g. Simplex method) but I need to find a way to solve it analytically.

Any suggestions?

I'll give examples in subsquent posts


Last edited by maxq on Mon, 8 Mar 2010 16:08:46 UTC, edited 1 time in total.

Top
 Profile  
 
 Post subject:
PostPosted: Mon, 8 Mar 2010 15:58:33 UTC 
Offline
S.O.S. Newbie

Joined: Mon, 8 Mar 2010 14:37:24 UTC
Posts: 4
Example Computation 1:

Eh = 128
Pd = 18

sum(An x n) = 128
sum(An) = 18

Take empty {Bn} as the set to optimize and arrive at the "ideal" set {An}

Eh = 128 (Power of 2? Yes)

Iteration 1
Eh = 64 + 64 = (8 x 8) + (8 x 8)
=> Bn = {8, 8}, n = {8}, sum(Bn) = 8, count(Bn) = 2
Comment: sum(Bn) < Pd - Keep Going

Iteration 2
Eh = 64 + 32 + 32 = (8 x 8) + (8 x 4) + (8 x 4)
=> Bn = {8, 4, 4}, sum(Bn) = 16, count(Bn) = 3
Comment: sum(Bn) < Pd & sum(An) increased => Keep Going

Iteration 3
Eh = 64 + 32 + 32 = (8 x 8) + (8 x 4) + (4 x 4) + (4 x 4)
=> Bn = {8, 4, 4, 4}, sum(Bn) = 20, count(Bn) = 4
Comment: sum(Bn) > Pd & sum(Bn) increased => Try Changing "n" for smallest divisible Product

Iteration 4
Eh = 64 + 32 + 16 + 16 = (8 x 8) + (4 x 4) + (4 x 4) + (2 x 8)
=> Bn = An = {8, 4, 4, 2}, n = {8, 4, 4, 8}, sum(Bn) = 18, count(Bn) = 5
Comment: sum(Bn) = Pd [STOP]


Example Computation 2:

Eh = 135
Pd = 21

sum(An x n) = 135
sum(An) = 21

Take empty {Bn} as the set to optimize and arrive at the "ideal" set {An}

Eh = 135 (Power of 2? No)

Get R + 2^Q = 135 => r = 7 & Q = 7 => Eh = 7 + 128

Iteration 1
Eh = 7 + 128 = (1 x 7) + (8 x 8) + (8 x 8)
=> Bn = {7, 8, 8}, sum(Bn) = 23, count(Bn) = 3
Comment: sum(Bn) > Pd, sum(Bn) = 23 > Pd, count(Bn) = 3

Iteration 2
Eh = (1 x 7) + (8 x 8) + (4 x 8) + (4 x 8)
=> Bn = {7, 8, 4, 4}, sum(Bn) = 23 > Pd, count(Bn) = 4

Iteration 3
Eh = 7 + 128 = (1 x 7) + (8 x 8) + (4 x 8) + (2 x 8) + (2 x 8)
=> Bn = {7, 8, 4, 2, 2}, sum(Bn) = 23 > Pd, count(Bn) = 5

Iteration 4
Eh = (1 x 7) + (4 x 8) + (2 x 8) + (2 x 8) + (4 x 8) + (2 x 8) + (2 x 8)
=> Bn = {7, 4, 2, 2, 4, 2, 2}, sum(Bn) = 23 > Pd, count(Bn) = 7 => sum doesn't change - try breaking up non divisible number

Iteration 5
Eh = (1 x 4) + (1 x 3) + (4 x 8) + (2 x 8) + (2 x 8) + (4 x 8) + (2 x 8) + (2 x 8)
=> Bn = {1, 1, 4, 2, 2, 4, 2, 2}, sum(Bn) = 18 < Pd, count(Bn) = 8 => Oops, try switching the factors starting with smaller one

Iteration 6
Eh = (1 x 4) + (3 x 1) + (4 x 8) + (2 x 8) + (2 x 8) + (4 x 8) + (2 x 8) + (2 x 8)
=> Bn = {1, 3, 4, 2, 2, 4, 2, 2}, sum(Bn) = 20 < Pd, count(Bn) = 8 => Oops, go back and try switching the other factor instead

Iteration 7
Eh = (4 x 1) + (1 x 3) + (4 x 8) + (2 x 8) + (2 x 8) + (4 x 8) + (2 x 8) + (2 x 8)
=> Bn = An = {4, 1, 4, 2, 2, 4, 2, 2}, n = {1, 3, 8, 8, 8, 8, 8, 8} sum(Bn) = 21 = Pd, count(Bn) = 8
GOT IT!!!


Top
 Profile  
 
PostPosted: Fri, 12 Mar 2010 06:35:01 UTC 
Offline
Senior Member

Joined: Sun, 31 Jan 2010 05:07:26 UTC
Posts: 88
What have you tried so far, analytically?

:?: I have an analytical method that may work. Do you have any knowledge of generating functions?


Top
 Profile  
 
PostPosted: Mon, 15 Mar 2010 02:01:45 UTC 
Offline
S.O.S. Newbie

Joined: Mon, 8 Mar 2010 14:37:24 UTC
Posts: 4
Generator wrote:
What have you tried so far, analytically?

:?: I have an analytical method that may work. Do you have any knowledge of generating functions?
I sure don't.. .and for methods, no I have not tried anything other than going through the two examples I put on the forum.


Top
 Profile  
 
PostPosted: Thu, 18 Mar 2010 05:52:43 UTC 
Offline
Senior Member

Joined: Sun, 31 Jan 2010 05:07:26 UTC
Posts: 88
The idea is that you define a recurrence relation. You'll learn about these if you're a computer science major, if you haven't already. Wikipedia talks about them here.

A good place to learn about how to set up the generating functions is Herbert Wilf's Generatingfunctionology, which is available for free download here.

Unfortunately, they can be a little complicated, especially for something like this, and could take a lot of time to learn/master. You may want to just consider going with computing the material as you have been, since it gets exceedingly complex to try to obtain a formula. Unless someone knows of an easier method...


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 5 posts ] 

All times are UTC [ DST ]


Who is online

Users browsing this forum: No registered users


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  
Contact Us | S.O.S. Mathematics Homepage
Privacy Statement | Search the "old" CyberBoard

users online during the last hour
Powered by phpBB © 2001, 2005-2011 phpBB Group.
Copyright © 1999-2013 MathMedics, LLC. All rights reserved.
Math Medics, LLC. - P.O. Box 12395 - El Paso TX 79913 - USA