You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 98,157

This problem came up in another thread.

Three neighborhoods exist on a cartesian grid at (0,0), ( 0, 400 ) and ( 375, 0 ).

Each neighborhood has 2300, 2400 and 2250 people respectively. All the neighborhood people work at the same factory. The amazing thing is that the factory is located at a lattice point on the grid ( x and y are integers ). Also amazing is the fact that the factory is situated so that the total distance the 6950 people travel each day is a minimum ( by euclidean distance ). All we know is that the factory due to zoning laws must be 10 or more blocks from any neighborhood ( by manhattan distance ).

Where is the factory located?

It was solved using computer algebra. Let us see how it could have been solved using geogebra.

1) Draw point (0,0) and label it X2300. Give it a size 7 and color it blue.

2) Draw point (0,400) and label it Y2400. Give it a size 7 and color it blue.

3) Draw point (375,0) and label it Z2250. Give it a size 7 and color it blue.

4) Draw a point anywhere on the screen, label it P and give it size 7 and color it red.

5) Draw a line segment from Y2400 to P. It should be labeled a

6) Draw a line segment from X2300 to P. It should be labeled b

7) Draw a line segment from Z2250 to P. It should be labeled c

8) Enter in the input bar:

d=2400a + 2300b + 2250 c and press enter.

Move the red point around observing d. Try to find where d is smallest. You should settle around P(80.61,87.14). This is close to the minimum.

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

Hi bobbym,

I think this is slightly difficult to check if we don't know the answer beforehand.

The most significant digits are almost same, we have to try spiraling down to the correct point.

Perhaps, this can be automated by a script?

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense" - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 98,157

Hi gAr;

Yes, that is true, but you can get reasonably close by just watching d in the left hand columns.

We could use iteration to zero in on the answer. That is the problem, the equations can not be solved analytically even with a package. But using numerical techniques we might get as close as we need.

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

Yes, and I can't imagine how difficult a polygon instead of a triangle can be!

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense" - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 98,157

The problem that I took this one from was so artificial that one of the vertices was the answer. I mean he could solve it using a small inequality. I know solutions like that make students happy and look great in books. The fact is in the real world there might be a couple of hundred points. Often you have to settle on a solution that is good but maybe not the best.

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

Is this still in active research or is there any good approximation algorithm?

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense" - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 98,157

Fermat posed this problem with weights = 1 to Torricelli a long time ago. He solved it in a couple of ways. They were all geometric constructions. I feel the problem can be solved numerically but I can not find any analytical methods.

I also do not know of any algorithm to solve it. I would form the distance equations. Take the partial derivatives and set them to 0 and solve the system of equations numerically.

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

Okay.

I guess numerical solution is good enough for this problem. After all, numbers is what we need.

But I don't know the numerical solution either. Which are the derivatives to be considered to solve?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 98,157

Hi gAr;

These are the two partial derivatives set to 0. Mathematica can now solve them numerically. Sage must have a similar command.

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

Hi bobbym,

Ok, thanks.

Sage couldn't solve it. Is there any numerical method?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 98,157

Did you check for a numerical solver in Sage, all packages have them?

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

It may be having since there are so many packages, I haven't used it yet.

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 98,157

find_root is one command. Also

sage: import scipy seems to load a bunch of root finders.

But let me see what I can do with those equations by hand. Please hold on.

Okay do this, start with the first equation:

Subtract

from both sides. You get

Multiply both sides by

You get.

Divide through by:

-2300

You get:

Now you have x on the right by itself. Do the same moves with the second equation to get a y by itself on the right.

Do you follow up to here?

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

Hi bobbym,

Yes, followed till there.

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 98,157

If you look you will see that the two equations have been turned into two recurrences. They are just minus the subscripts.

Start the process by putting x = 1.0 and y = 1.0

Now run the next two equations 1 time:

Tell me what you get for x and y.

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

Hi bobbym,

After 30 iterations, I get (80.3416234530054, 86.8627875987953).

Wonderful!

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 98,157

It will get closer and closer because this one happens to converge. Sometimes they do not and you have to pull out a different x and y.

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

Hi bobbym,

Okay. Thanks!

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 98,157

Hi gAr;

You are welcome!

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

Offline

Pages: **1**