Really annoying dynamic programming problem Watch

BrightStarXXXpa
Badges: 0
Rep:
?
#1
Report Thread starter 7 years ago
#1
An artist has been commissioned to paint four portraits, each painting requires at least one day, and he has seven days to paint them all in. There are no fractions of a day allowed, and obviously he has to spend at least one day on each portrait, (and therefore he can't spend more than 4 days any one of them).
The longer he spends on a painting the more money he will receive for it.
Thus for portrait ONE he gets £120 for one day's effort, £150 for two, £165 for three and £200 for four. The revenues on the other portraits are similar but not exacly the same. You probably get the idea.
Now, this is a dynamic programming problem, which I thought I had no problems with, but I cannot see how to model it. If stage 1 is "nbr of days spent on portrait ONE", and so on, then I seem to get in a mess around stage 3 since how long you can spend on portrait THREE sepends on how long you spent on the first two portraits in horribly complicated ways.
Anyway, has anybody got a clue how I should model it? What will be the states and the stages?
Thanks in advance.
0
reply
msmith2512
Badges: 1
Rep:
?
#2
Report 7 years ago
#2
You have 7 days and 4 portraits what are the options for the time spent on each portrait?

What is the pay-off for each extra day spent on a portrait?
0
reply
ghostwalker
  • Study Helper
Badges: 16
#3
Report 7 years ago
#3
Does it need to be a dynamic programming model?

I can see a 0-1 integer programming model.
0
reply
BrightStarXXXpa
Badges: 0
Rep:
?
#4
Report Thread starter 7 years ago
#4
(Original post by msmith2512)
You have 7 days and 4 portraits what are the options for the time spent on each portrait?

What is the pay-off for each extra day spent on a portrait?
Thanks for your reply. For the portraits you have to spend at least one day on each one but can't spend more than 4 on any one (otherwise you can't spend at least one day on each one!) There are no other time restrictions.

The payoffs are similar (but not identical) to those I wrote for portrait one.
0
reply
BrightStarXXXpa
Badges: 0
Rep:
?
#5
Report Thread starter 7 years ago
#5
(Original post by ghostwalker)
Does it need to be a dynamic programming model?

I can see a 0-1 integer programming model.
Can you give me a hint? I can't see anything that's not very complicated..
0
reply
ghostwalker
  • Study Helper
Badges: 16
#6
Report 7 years ago
#6
(Original post by BrightStarXXXpa)
Can you give me a hint? I can't see anything that's not very complicated..
It's not complicated, but does involve a lot of variables, and constraints (would suit a computer).

For the j'th day's effort on painting i, we assign the variable x_{ij} which will take values in \{0,1\} depending on whether we don't, or do, work the j'th day on painting i.

Since there are 4 paintings and we can spend up to 4 days on any one, we have a total of 16 variables.

Object function and all except one of the sets of contraints are straight forward.
The only "interesting" set is how to ensure that you can't do, for example, work day 3 of a particular painting, if you haven't worked day 1 and day 2.
I'll let you discover a method (it is simple), but can post further on that if you need. There's a hint in the spoiler.

Spoiler:
Show

For any given painting, we can consider the 4 days in order. In effect we have a function we can graph. That graph has a particular characteristic.


Edit: For a dynamic programming method, follow msmith2512, and there is a good example here.
0
reply
msmith2512
Badges: 1
Rep:
?
#7
Report 7 years ago
#7
(Original post by BrightStarXXXpa)
Thanks for your reply. For the portraits you have to spend at least one day on each one but can't spend more than 4 on any one (otherwise you can't spend at least one day on each one!) There are no other time restrictions.

The payoffs are similar (but not identical) to those I wrote for portrait one.
These weren't questions - I had read your post. They are hints at how to think about doing the question. The key to this problem is understanding the benefit to the artist of doing each extra days work on a painting - possibly at the expense of working on a different portrait.

Of course the playoffs are similar but different. The whole point of the question is to work out the most advantageous order to utilise these similar but different payoffs.
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

University open days

  • University of Bristol
    Undergraduate Open Afternoon Undergraduate
    Wed, 23 Oct '19
  • University of Exeter
    Undergraduate Open Day - Penryn Campus Undergraduate
    Wed, 23 Oct '19
  • University of Nottingham
    Mini Open Day Undergraduate
    Wed, 23 Oct '19

Have you made up your mind on your five uni choices?

Yes I know where I'm applying (152)
59.61%
No I haven't decided yet (58)
22.75%
Yes but I might change my mind (45)
17.65%

Watched Threads

View All