# S.O.S. Mathematics CyberBoard

Your Resource for mathematics help on the web!
 It is currently Mon, 27 May 2013 03:55:13 UTC

 All times are UTC [ DST ]

 Page 1 of 1 [ 5 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Need help with analytical algorithm for solving 2 Eq setsPosted: Mon, 8 Mar 2010 15:37:21 UTC
 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

 Post subject: Posted: Mon, 8 Mar 2010 15:58:33 UTC
 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

 Post subject: Very interesting & seems toughPosted: Fri, 12 Mar 2010 06:35:01 UTC
 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

 Post subject: Re: Very interesting & seems toughPosted: Mon, 15 Mar 2010 02:01:45 UTC
 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

 Post subject: The methods are complicatedPosted: Thu, 18 Mar 2010 05:52:43 UTC
 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.

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

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 5 posts ]

 All times are UTC [ DST ]

#### Who is online

Users browsing this forum: No registered users

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

Search for:
 Jump to:  Select a forum ------------------ High School and College Mathematics    Algebra    Geometry and Trigonometry    Calculus    Matrix Algebra    Differential Equations    Probability and Statistics    Proposed Problems Applications    Physics, Chemistry, Engineering, etc.    Computer Science    Math for Business and Economics Advanced Mathematics    Foundations    Algebra and Number Theory    Analysis and Topology    Applied Mathematics    Other Topics in Advanced Mathematics Other Topics    Administrator Announcements    Comments and Suggestions for S.O.S. Math    Posting Math Formulas with LaTeX    Miscellaneous