Wikipedia:Reference desk/Archives/Mathematics/2006 November 13

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 13

Practical Application: Linear Programming

Hello,

I start a job tomorrow where I have to travel to stores and make sure that all Intuit products are on the shelf and looking organized. I have 14 stores, a starting destination and an ending destination. I have calculated the times (in minutes) it takes to go from each point to every other point. I must hit all 14 stores in 4 days. I do not get paid until I reach the first store (from the starting point), and I am off the clock once I finish my last store.

I took a class a few years ago that taught me how to solve this problem, but essentially I would like to minimize the amount of time for each of these 4 routes and minimize the amount of "off the clock driving" I do. I do not want to do more than 4 stores in any day.

Can anyone give me any guidance in this matter? For reference, I posted the times between all points here

Thanks --Yoyoceramic 03:17, 13 November 2006 (UTC)

That link doesn't work, it asks for a username and password. Can you post the data directly here ? StuRat 03:22, 13 November 2006 (UTC)

Sure, I also fixed it above.. http://www.trinitywiki.com/ROUTES.htm thanks --Yoyoceramic 03:23, 13 November 2006 (UTC)

This looks like a homework problem to me. But giving you the benefit of a doubt, I'd have to point out that the time between stops won't be fixed, but will vary by traffic, which will depend on the time of day. This, and other intangible constraints, like wanting to be near a good restaurant at lunch time, will make any calculations rather useless. Just chart out a "reasonable" path, then tweak it to account for traffic, etc., until you get to the best solution. Also, I'd want to see them listed on a map to come up with the initial path. StuRat 03:28, 13 November 2006 (UTC)

Also, I don't understand why your start and end locations are apparently different. You would want to find the four stores closest to the start location, and go to each of those first on each of the four days. Similarly, you would want to find the four locations closest to the end location, and go to those last on each of the four days. From there, I'd go with trial-and-error to find the next closest stores from those 8, and finally link them all together into a single path. StuRat 03:31, 13 November 2006 (UTC)

Thank you for giving me the benefit of the doubt, but to clarify, this is not a homework problem (although I can see why you might think that). You can find more about the Intuit Flexforce program I am apart of here: http://www.collegecentral.com/elon/BulletinDetail.CFM?MessageID=23173&UnivCode=ELO.

• Also, here is the map of the locations --Yoyoceramic 03:38, 13 November 2006 (UTC)

• The reason the Start and End are different is because I will start from my home each day and end up at my school (see map)--Yoyoceramic 03:38, 13 November 2006 (UTC)

I get "this collection no longer exists" when I look at the map. StuRat 04:00, 13 November 2006 (UTC)

Sorry about that, I don't know why that happened. Try this one

I still don't see any locations marked on the map. StuRat 04:10, 13 November 2006 (UTC)

Akk yeah sorry - I'm working on that - I am trying to figure out how to share it out... give me a minute --24.174.142.137 04:12, 13 November 2006 (UTC)

One way is to take a screen grab and post that to Wikipedia. StuRat 04:18, 13 November 2006 (UTC)

Here's one series of routes I've come up with that's "pretty good". You will likely want to tweak it to make it better:

            STOPS           TIME
       ----------------  -----------
Day 1:  6 - 11 - 1           36
Day 2:  8 - 10 - 9 -  2      62
Day 3: 13 - 12 - 3           44
Day 4:  7 -  4 - 5 - 14      47

StuRat 04:07, 13 November 2006 (UTC)

Thanks for the suggestion. Here is a map. 2 is a southern outlier, and the other numbers I drew on there because some flags overlap each other. --Yoyoceramic 04:21, 13 November 2006 (UTC)

OK, using that map I came up with this plan:

            STOPS            TIME
       -----------------  -----------
Day 1:  6 -  2 -  1           54
Day 2:  8 - 10 - 12 -  7      48
Day 3: 13 -  9 -  3           43
Day 4: 11 -  4 -  5 - 14      49

This plan makes the number of miles driven each day more consistent. StuRat 05:26, 13 November 2006 (UTC)

The problem is more like a variation on the Travelling salesman problem, which is much harder than linear programming. The best I've found is this:

            STOPS         TIME
       -----------------  ----
Day 1:  3 -  9 -  2        49
Day 2:  7 -  8 - 10 - 12   51
Day 3: 11 - 14 -  4 -  5   44
Day 4: 13 -  6 -  1        29
                          ----
                          173

 --Lambiam^Talk 12:53, 13 November 2006 (UTC)

A solution with a shorter total:

            STOPS         TIME
       -----------------  ----
Day 1:  4 - 12 - 10 -  5   52
Day 2:  7 - 11 - 14        34
Day 3:  8 -  3 -  9 -  2   50
Day 4: 13 -  1 -  6        29
                          ---
                          165

Slightly longer, but more balanced:

            STOPS         TIME
       -----------------  ----
Day 1:  1 -  6 -  2        42
Day 2:  4 - 12 - 10        47
Day 3:  7 - 11 - 14 -  5   36
Day 4:  8 -  9 -  3 - 13   43
                          ---
                          168

 --Lambiam^Talk 22:25, 13 November 2006 (UTC)

The total time is low, but remember they don't get paid until the first stop and are off the clock after the last stop, so we want the first and last stop to be as close to the start and end points as possible. I weighted that even higher than keeping the time low (I'd actually prefer the on-the-clock time to be as high as possible). StuRat 22:29, 13 November 2006 (UTC)

As demonstrated above, the total driving time using a reasonable route (which I could draw just by looking at the map in under 1 minute) should be under 3 hours. Some tweaking and guessing and such could potentially save 10, may be even 30 minutes off the total driving time. Now a question: how much combined time did you spend trying to solve this problem, creating the maps and the tables, typing etc? I admit this may be fun to play with numbers, but so is this attempt to ridicule you. (Igny 22:41, 13 November 2006 (UTC))

I would like to thank everyone for their advice. I had my first run today. Since I did not check back on the wiki until now, I did the run:

            STOPS         TIME
        -----------------  ----
 Day 1:  3 -  10 -  5 - 1   53

Which actually took a little longer than anticipated, but I think the traffic premium is universal throughout all the routes. --Yoyoceramic 23:01, 13 November 2006 (UTC)--24.174.142.137 22:59, 13 November 2006 (UTC)

I don't believe the slow down due to traffic is the same. There tends to be more traffic on highways heading into the city in the morning rush hour, and on highways heading out of the city in the afternoon rush hour. Timing your trips so you are doing inventory during rush hour will also save you from suffering sitting in traffic at that time. Another factor I try to figure into my drives is avoided driving into the Sun, which means not heading east at sunrise and west at sunset. StuRat 00:02, 14 November 2006 (UTC)

Using as the main objective to minimize unpaid time (UT), the best I've found is:

            STOPS           UT   TIME
       -----------------    --   ----
Day 1:  7 - 11 -  1         21    33
Day 2:  8 -  3 -  9 -  2    23    50
Day 3: 13 - 12 - 10 -  6    21    49
Day 4: 14 -  4 -  5         31    42
                            --   ---
                            96   174

To find this, I dusted off some programs I had lying around. The data was entered by copy/paste. Some time went into formulating the objective function and constraints, but a similar amount into formatting the output.  --Lambiam^Talk 10:29, 14 November 2006 (UTC)

Most complex strategic game for two players

Which is the most complex or most difficult strategic game for two players. Maybe these are two questions. I'm talking about any game that actually exists, has a certain tradition and that is played by lay people. I don't mean a game that was just devised by mathematicians to set a record in complexity. The game should not use random elements like shuffled cards, dice or random starting positions either. Is it go? Is it chess? Is it something else? Thanks in advance! Pat 85.2.50.69 11:46, 13 November 2006 (UTC)

This is a pretty nebulous question. The rules of go and chess are both quite simple, though they allow for extraordinarily deep strategy. Will you consider games without complete information? ×Meegs 12:12, 13 November 2006 (UTC)

In terms of the computational complexity of games, specifically two-player games with perfect knowledge and no randomness such as chess, go, checkers, etc., there isn't much difference between games: most are known or believed to be either PSPACE-complete or EXPTIME-complete. The difference between these two complexity classes doesn't seem to have much to do with the difficulty of actual play, but depends more on whether there is a guaranteed short number of moves after which the game ends (e.g. in Othello or Hex each move fills up a board position) or whether the longest possible game is much longer in number of moves than the board size (true in Chess unless you impose the fifty move rule). But that doesn't mean they are all equally easy for a human or computer to play, and it doesn't tell you whether the difficulty in each games is more strategic or tactical. In terms of difficulty of programming a computer to play as well as a human, Go seems to be king; some have claimed that this is due to its high branching factor but I'm not convinced by that argument because gomoku has the same branching factor but is much easier for computers. I guess to give a better answer, I'd need to know what the purpose of the question is — Bragging rights? Estimate of number of years of study needed to master the game? Interest in writing computer programs for hard problems? Studying human intelligence? —David Eppstein 18:51, 13 November 2006 (UTC)

Thanks to both of you! I dont know much about math and didn't realize this was a cloudy question. Nah Mr. Eppstein I'm neither a programmer nor a neurologist. I suck at chess and don't even know the rules of go. I read somewhere that go was the most difficult game in the world and more complex than chess. I just asked out of curiosity and for no other purpose. Thanks again. Pat 83.77.223.48 11:41, 14 November 2006 (UTC)

See Go_ranks_and_ratings#Game_depth for a summary of a "scientific"/"objective" argument for believing that go is "deeper"/more "complex" than chess. The idea is that you can quantitatively compare player-rating scales between different games by using the observed probability that a (slightly) lower-ranked player will win against a higher-ranked one. Then you discover that the rating ladder for go is longer than the one for chess. (Do we have a better article on this anywhere?) —Blotwell 15:15, 14 November 2006 (UTC)

I don't think anyone has directly said it yet, but Go is still a more difficult problem for computer scientists than Chess (see our article on Computer Go). To my knowledge, there is no computer Go player anywhere near as good (in terms of who it can match) as the famous Deep Blue which was able to go toe-to-toe with the world champion in Chess. - Rainwarrior 17:31, 14 November 2006 (UTC)

What are amicable numbers good for?

Can anyone any application of amicable numbers?Mr.K. 21:56, 13 November 2006 (UTC)

There are no applications as far as I am aware. JoshuaZ 22:00, 13 November 2006 (UTC)

Why do you have a concept without function? You could also say that numbers like 45-54 or 68-86 are the Yin-Yang numbers. But why would someone introduce a new useless concept? Mr.K. 22:07, 13 November 2006 (UTC)

Recreational mathematics. Some people like numbers, they like to play with them, so they figure some trivia just to keep themselves busy and entertained. Lots of interesting and arguably important fields in mathematics started out like that (like the study of tessellations)... In any case, it can't hurt, and it's always fun to play around with these concepts. ☢ Ҡi∊ff⌇↯ 22:17, 13 November 2006 (UTC)

Can you give an application of ballet, fire breathing, or Rubik's cube?  --Lambiam^Talk 22:37, 13 November 2006 (UTC)

Fitness, attracting members of the opposite sex, and driving yourself completely batty, respectively. - Braveorca 05:14, 14 November 2006 (UTC)

Well, now I understand why I can never hang on to a girl: I do ballet to attract members of the opposite sex and Rubik's cube for fitness... Joe 07:44, 14 November 2006 (UTC)

May we conclude that it was the fire breathing that drove you batty?  --Lambiam^Talk 10:32, 14 November 2006 (UTC)

I still don´t get the point of why do you have an invented concept. The problem is not the useful (useful=material) application of it, but the function of the concept within the science. And can someone answer me what about the yin-yang numbers? Should I start an article with them? Mr.K. 11:59, 14 November 2006 (UTC)

The truth is that it's not really a point of "why", but of "why not"? These concepts weren't described out of need, but out of curiosity. They may not play any significant role, but they are interesting as numerical curiosities. Simply that. You gotta keep in mind, though, that playing with numbers may reveal interesting and useful patterns, as it has before....

About your yin-yang numbers, you could write an article about them, but it would most likely get deleted. ;) ☢ Ҡi∊ff⌇↯ 12:31, 14 November 2006 (UTC)

There is a certain group of numbers of which only a handful have ever been proven to exist. So what do they call them? Well, it's obvious - normal numbers. Work that out if you can. JackofOz 05:27, 15 November 2006 (UTC)