Low-Dimensional Linear Programming

Presentation by: Marc Lebovitz

Applications

Example 1: Production Problem (taken from Bertsimas and Tsitsiklis, p.7)

    A firm produces n different goods using m different raw materials.
    Let bi be the available amount of the ith raw material.
    Let xj be the amount of the jth good.
    The jth good requires aji units of the ith material and results in a revenue of cj per unit produced.
    How much of each good should we produce to maximize total revenue.

    We can formulate this problem as the following LP:
            objective function:        c1*x1 + ... + cn*xn
            constraints:                   a1i*x1 + ... + ani*xn <= bi        i=1...m
                                                    xj >= 0                                         j=1...n

    Let's put in some #s:
        2 goods: tricycles (good 1), and space shuttles (good 2)
            revenue for each: c1 = $1, c2 = $3
        2 raw materials: ranch dressing (material 1), and cheezy poofs (material 2)
            amount of each: b1 = 500 tons, b2 = 200 tons
        the goods require the following amounts of raw materials:
        tricycles: a11 = 4 ton, a12 = 1 ton
        space shuttles:    a21 = 5 tons, a21 = 0 tons
        objective function: 1*x1 + 3*x2
        constraints:             x4 + 5x2 <= 500
                                          x1 <= 200
                                          x1>=0, x2>=0

To maximize our revenue, we should produce 0 tricycles and 100 space shuttles.

Example 2: View Frustum Culling

Let the view frustum and polygon edges be the constraints.
Choose any objective function.
If a solution does not exist, ignore object in rendering.