Examples from Geometric Programming

Duffin, Peterseon, Zener. (1967)


In [2]:
import gpkit
import gpkit.interactive

Transporting Gravel

Suppose that 400 cubic yards of gravel must be ferried across a river. Suppose that the gravel is to be shipped in an open box of length $t_1$, width $t_2$, and height $t_3$. The sides and bottom of the box cost \$10 per square yard and the ends of the box cost \$20 per squared yard. The box will have no salvage value and each round trip of the box on the ferry will cost 10 cents. What is the minimum cost of transporting the 400 cubic yards of gravel?


In [3]:
# transporting gravel across a river:
#   how large of a box should be used / how many trips should be taken?

V1 = gpkit.Variable("V_1", 400, "cubic yards", "volume of gravel to transport")

l = gpkit.Variable("l", "yards", "box length")
w = gpkit.Variable("w", "yards", "box width")
h = gpkit.Variable("h", "yards", "box height")

c_sides = gpkit.Variable("c_{sides}", 10, "1/yard^2", "cost of box sides and bottom")
c_ends = gpkit.Variable("c_{ends}", 20, "1/yard^2", "cost of box ends")
c_ferry = gpkit.Variable("c_{ferry}", 0.10, "-", "cost of ferry trip")

A_end = w*h
A_side = l*h
A_bottom = w*l

total_cost = c_ferry*V1/(l*w*h) + c_ends*2*A_end + c_sides*(2*A_side + A_bottom)

gp = gpkit.GP(total_cost)
sol = gp.solve()
print sol.table()


Using solver 'cvxopt'
Solving for 3 variables.
Solving took 0.0517 seconds.
              |
         Cost :  100     
              | 
              | Variables
          V_1 : 400       [yd**3] volume of gravel to transport
     c_{ends} : 20        [1/yd**2] cost of box ends
    c_{ferry} : 0.1       cost of ferry trip
    c_{sides} : 10        [1/yd**2] cost of box sides and bottom
            h : 0.5       [yd] box height
            l : 2         [yd] box length
            w : 1         [yd] box width
              |
              | Constant sensitivities
          V_1 : 0.4       volume of gravel to transport
     c_{ends} : 0.2       cost of box ends
    c_{ferry} : 0.4       cost of ferry trip
    c_{sides} : 0.4       cost of box sides and bottom
              |

As above, except to facilitate handling of the box it is required that its height be 1 yard.


In [4]:
gp.sub(h, 1)
sol = gp.solve()
print sol.table()


Using solver 'cvxopt'
Solving for 2 variables.
Solving took 0.0091 seconds.
              |
         Cost :  107     
              | 
              | Variables
          V_1 : 400       [yd**3] volume of gravel to transport
     c_{ends} : 20        [1/yd**2] cost of box ends
    c_{ferry} : 0.1       cost of ferry trip
    c_{sides} : 10        [1/yd**2] cost of box sides and bottom
            h : 1         [yd] box height
            l : 1.43      [yd] box length
            w : 0.717     [yd] box width
              |
              | Constant sensitivities
          V_1 : 0.365     volume of gravel to transport
     c_{ends} : 0.269     cost of box ends
    c_{ferry} : 0.365     cost of ferry trip
    c_{sides} : 0.365     cost of box sides and bottom
            h : 0.173     box height
              |

Now instead of setting the height, it is required that the sides and bottom of the box are made from scrap material. Only four square yards of this scrap material are available.


In [5]:
A_scrap = gpkit.Variable("A_{scrap}", 4, "yards^2", "scrap material available")

gp = gpkit.GP(c_ferry*V1/(l*w*h) + c_ends*2*A_end,
              [2*A_side + A_bottom <= A_scrap])
gp


Out[5]:
$$\begin{array}[ll] \text{} \text{minimize} & 2w h c_{ends} + \frac{c_{ferry} V_1}{w l h}\mathrm{\left[ - \right]} \\ \text{subject to} & A_{scrap} \geq 2l h + w l \\ \text{substituting} & A_{scrap} = 4 \\ & V_1 = 400 \\ & c_{ends} = 20 \\ & c_{ferry} = 0.1 \\ \end{array}$$

In [6]:
print gp.solve().table()


Using solver 'cvxopt'
Solving for 3 variables.
Solving took 0.00784 seconds.
              |
         Cost :  60      
              | 
              | Variables
    A_{scrap} : 4         [yd**2] scrap material available
          V_1 : 400       [yd**3] volume of gravel to transport
     c_{ends} : 20        [1/yd**2] cost of box ends
    c_{ferry} : 0.1       cost of ferry trip
            h : 0.5       [yd] box height
            l : 2         [yd] box length
            w : 1         [yd] box width
              |
              | Constant sensitivities
    A_{scrap} : -0.667    scrap material available
          V_1 : 0.667     volume of gravel to transport
     c_{ends} : 0.333     cost of box ends
    c_{ferry} : 0.667     cost of ferry trip
              |

Designing a three-sided fence

One side of an open field is bounded by a straight river. How would you put a fence around the other three sides of a rectangular plot to enclose an area as great as possible with a length of fence not greater than $L$?


In [7]:
L = gpkit.Variable("L", 1, "yards", "total fence length")

l = gpkit.Variable("l", "yards", "plot side parallel to river")
w = gpkit.Variable("w", "yards", "plot side perpendicular to river")

A_plot = l*w

gp = gpkit.GP(1/A_plot, [2*w + l <= L])
sol = gp.solve()
print sol.table()


Using solver 'cvxopt'
Solving for 2 variables.
Solving took 0.0083 seconds.
              |
         Cost :  8       
              | 
              | Variables
            L : 1         [yd] total fence length
            l : 0.5       [yd] plot side parallel to river
            w : 0.25      [yd] plot side perpendicular to river
              |
              | Constant sensitivities
            L : -2        total fence length
              |

Cutting a rectangular beam from a log

The stiffness of a rectangular beam is proportional to the product of its width with the cube of its depth. Find the dimensions of the stiffest beam that can be cut from a circular cylindrical log of radius $R$.


In [8]:
R = gpkit.Variable("R", 1, "inches", "log radius")

d = gpkit.Variable("d", "inches", "beam depth")
w = gpkit.Variable("w", "inches", "beam width")

gp = gpkit.GP(1/(w*d**3), [(d/2)**2 + (w/2)**2 <= R**2])
sol = gp.solve()
print sol.table()


Using solver 'cvxopt'
Solving for 2 variables.
Solving took 0.00883 seconds.
              |
         Cost :  0.192   
              | 
              | Variables
            R : 1         [in] log radius
            d : 1.73      [in] beam depth
            w : 1         [in] beam width
              |
              | Constant sensitivities
            R : -4        log radius
              |

Sheet-metal box

A square sheet of tin $L$ inches on a side is to be used to make an open-top box by cutting a small square of tin from each corner and bending up the sides. How large a square should be cut from each corner in order that the box shall have a volume as large as possible?


In [9]:
L = gpkit.Variable("L", 1, "inches", "tin sheet side length")

l = gpkit.Variable("l", "inches", "box length")
w = gpkit.Variable("w", "inches", "box width")
h = gpkit.Variable("h", "inches", "box height")

cx = gpkit.Variable("c_x", "inches", "corner cutout length in x dimension")
cy = gpkit.Variable("c_y", "inches", "corner cutout length in y dimension")

gp = gpkit.GP(1/(l*w*h),
              [L >= w + 2*cx,
               L >= l + 2*cy,
               cx >= h,
               cy >= h])
sol = gp.solve()
print sol.table()


Using solver 'cvxopt'
Solving for 5 variables.
Solving took 0.0111 seconds.
              |
         Cost :  13.5    
              | 
              | Variables
            L : 1         [in] tin sheet side length
          c_x : 0.167     [in] corner cutout length in x dimension
          c_y : 0.167     [in] corner cutout length in y dimension
            h : 0.167     [in] box height
            l : 0.667     [in] box length
            w : 0.667     [in] box width
              |
              | Constant sensitivities
            L : -3        tin sheet side length
              |

Ivan Petrovich's productivity

Ivan Petrovich is a brilliant student of psychology and mathematics. Unfortunately, after his second year of graduate study he had to take a year off to recoup his finances. He worked as a consultant to Z corporation, his recompense being strictly proportional to his productivity. After a thorough study of his productivity, Ivan concluded that his recompense would be

$ \$ 0.5 \tau_W^{1.5} \tau_S^{0.75} \tau_M^{0.1} $ per day,

where $\tau_W$, $\tau_S$, and $\tau_M$ are the hours spent each day in work, in sleep, and in listening to new classical records. Ivan was under strict doctor's orders to take at least three hours a day for his meals, during which he could, however, also listen to music. His only variable expense was the purchase of new records, which cost $ \$ 5 \tau_M $. Ivan therefore allotted his time to maximize

$ \$ 0.5 \tau_W^{1.5} \tau_S^{0.75} \tau_M^{0.1} - \$ 5 \tau_M $

subject, of course, to the condition

$ \tau_W + \tau_S + 3 \leq 24$.

How did Ivan allot his time?


In [10]:
tw = gpkit.Variable("\\tau_W", "-", "hours spent working")
ts = gpkit.Variable("\\tau_S", "-", "hours spent sleeping")
to = gpkit.Variable("\\tau_O", "-", "hours spent eating and/or listening")
tm = gpkit.Variable("\\tau_M", "-", "hours spent listening to music")
s = gpkit.Variable("s", "-", "savings accrued per day")

p = gpkit.Variable("p", 0.5, "-", "pay rate per unit productivity")
c = gpkit.Variable("c", 5, "-", "cost of new records, per hour")
te = gpkit.Variable("\\tau_E", 3 ,"-", "hours required to be spent eating")

gp = gpkit.GP( 1/s,
              [p*tw**1.5*ts**0.75*tm**0.1 >= s + c*tm,
               tw + ts + to <= 24,
               to >= tm,
               to >= te])
sol = gp.solve()
print sol.table()


Using solver 'cvxopt'
Solving for 5 variables.
Solving took 0.0106 seconds.
              |
         Cost :  0.00901 
              | 
              | Variables
       \tau_E : 3         hours required to be spent eating
       \tau_M : 2.47      hours spent listening to music
       \tau_O : 3         hours spent eating and/or listening
       \tau_S : 7         hours spent sleeping
       \tau_W : 14        hours spent working
            c : 5         cost of new records, per hour
            p : 0.5       pay rate per unit productivity
            s : 111       savings accrued per day
              |
              | Constant sensitivities
       \tau_E : 0.357     hours required to be spent eating
            c : 0.111     cost of new records, per hour
            p : -1.11     pay rate per unit productivity
              |

Import CSS for nbviewer

If you have a local iPython stylesheet installed, this will add it to the iPython Notebook:


In [11]:
from IPython import utils
from IPython.core.display import HTML
import os
def css_styling():
    """Load default custom.css file from ipython profile"""
    base = utils.path.get_ipython_dir()
    styles = "<style>\n%s\n</style>" % (open(os.path.join(base,'profile_default/static/custom/custom.css'),'r').read())
    return HTML(styles)
css_styling()


Out[11]: