Really annoying dynamic programming problem

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.

Reply 1

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?

Reply 2

ghostwalker

Does it need to be a dynamic programming model?

I can see a 0-1 integer programming model.

(edited 11 years ago)

Reply 3

BrightStarXXXpa

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.

Reply 4

BrightStarXXXpa

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..

Reply 5

ghostwalker

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

Edit: For a dynamic programming method, follow msmith2512, and there is a good example here.

(edited 11 years ago)

Reply 6

msmith2512

Original post by BrightStarXXXpa

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.