Constrained optimization problem? Mats in a yoga studio

56 Views Asked by At

Suppose you had a yoga studio measuring $21 \times 13$ ft, and you want to fill it with yoga mats measuring $6 \times 2$ ft, under the constraint that yoga mat edges are at least $1$ ft apart from other yoga mat edges, and that all yoga mat edges are at least $0.5$ ft away from the nearest wall.

I did this in a silly geometric way, by rearranging rectangles like a puzzle and seeing how many I could fit in the studio. My best shot was $13$, and that is the correct answer apparently. The (horribly not-to-scale) sketch below shows the overall organization: The long edge of $6$ yoga mats should line both long sides of the yoga studio ($3$ mats on each side), and in the middle you can just fit $7$ mats (long side by long side).

I would like to approach this problem from a constrained optimization perspective. First, this would confirm that the optimal number of mats that would fit is $13$ (i.e., I wouldn't have to take the book's word for it), and second, I want to be able to approach geometric optimization problems like this routinely in a principled way, rather than resort to heuristics.

enter image description here

2

There are 2 best solutions below

1
On

This is NOT an approach via constrained optimization, but rather a way to confirm that the optimal value is indeed $13$. Hence I am not actually answering your question in full, but this is too long to fit in a comment.

Since the yoga mats must be $0.5$ ft from the walls and $1$ ft from each other, we can "expand" the yoga mats so they have an extra $0.5$ ft on each side.

Now these expanded yoga mats, with dimensions $3$ ft $\times\ 7$ ft and an area of $21$ ft$^2$, can stick to the walls and each other.

How many of these yoga mats can we fit? The maximum is precisely $\dfrac {21\times 13}{3\times 7} = 13.$

EDIT: I'm a little bit worried about the extra $0.5\times 0.5$ corners generated from this method. However in this case, they only contribute $1$ ft$^2$ for each mat, so the maximum remains $\left\lfloor \dfrac {21\times 13}{20}\right\rfloor = \lfloor 13.65\rfloor =13$.

0
On

Each mat requires a 0.5 ft border on each side. The required space for each mat is 21 sq ft. The yoga studio is $21\times 13$ sq ft.

If you have found a way to fit 13, it must be optimal, as you have no wasted space.