An inequality-constrained linear optimization problem in two variables

Question

I have been doing an exercise in optimization. Once I got through the text-to-math part I've derived the following cost function, whose value is to be minimised:

$$ C(x, y) = 25x + 15y $$ I have also got the following constraints: $$ y \geq -7/3x + 100 $$

$$ y \geq -1/3 x + 200/3 $$

$$y \leq -2/3 x + 250/3 $$

Graphing the three constraints:

It's clear that the solution set of the system of inequalities will be the triangle made by the three lines.

Now, I know one way to solve the the optimization problem: all lines of constant cost will have the form: $$ C(x, y) = c_1 \implies 25x + 15y = c_1 $$ $$ y = -5/3x + C $$ For some arbitrary constant $C$.

Seeing that the slope of the constant cost function has slope less negative than the blue line we can see that the minimum to be found, i.e. smallest $C$ that satisfies the constraints, will be the point where blue and red line intersect. Using that knowledge it is easy to find the minimal x and y.

This solution feels very unsatisfying, however. First, it's an optimization problem and I haven't done any Calculus. Second, it relies heavily on graphing and visualizing the problem. Third, I cannot see how would I be to generalize the solution to similar problems. How would I go about solving the problem without doing all the drawing and then visually inspecting said drawing?

Answer 1

This problem is an instance of Linear Programming, where both the objective function and the constraints are linear ($\mathbf{A} \mathbf{x} \leq 0$) or affine ($\mathbf{A} \mathbf{x} \leq \mathbf{b}$).

The fundamental theorem of Linear Programming states that the solution to a linear program, if it exists, will be found on (at least) one of the vertices of the polygon (or polytope) designated by the constraints. A solution might not exist in the case of unbounded feasible regions, for example.

In your example, you can find those vertices by looking for intersections of the lines / constraints, and then look at the value of the objective function at each vertex, since the feasible region is a closed convex polygon. A methodical way to solve linear programs is the Simplex Algorithm, which begins traversing the feasible region at a vertex of the feasible region, walking across edges to find the minimum/maximum.

Answer 2

We have the inequality-constrained linear program (LP)

$$\begin{array}{ll} \text{minimize} & 25 x + 15 y\\ \text{subject to} & 7 x + 3y \geq 300\\ & \,\,\,x + 3y \geq 200\\ & 2 x + 3y \leq 250\end{array}$$

Introducing (nonnegative) slack variables $s_1, s_2, s_3 \geq 0$

$$\begin{array}{ll} \text{minimize} & 25 x + 15 y\\ \text{subject to} & 7 x + 3y - s_1 = 300\\ & \,\,\,x + 3y - s_2 = 200\\ & 2 x + 3y + s_3 = 250\\ & s_1, s_2, s_3 \geq 0\end{array}$$

Introducing nonnegative variables $x_{+}$ and $x_{-}$, $y_{+}$ and $y_{-}$ such that $x = x_{+} - x_{-}$ and $y = y_{+} - y_{-}$, we obtain an equality-constrained LP with nonnegativity constraints on all $7$ variables

$$\begin{array}{ll} \text{minimize} & \mathrm c^{\top} \mathrm x\\ \text{subject to} & \mathrm A \mathrm x = \mathrm b\\ & \mathrm x \geq 0_7\end{array}$$

Note that $\mathrm A \mathrm x = \mathrm b$ is an underdetermined linear system of $3$ equations in $7$ unknowns. Thus, it defines a $d$-dimensional hyperplane in $\mathbb R^7$, where $d \geq 4$. Hence, the feasible region of the LP is the intersection of this hyperplane with the nonnegative orthant $(\mathbb R_0^+)^7$. Selecting only $3$ columns, we obtain a determined system whose solution is $0$-dimensional. In total, there are

$$\binom{7}{3} = 35$$

possible selections. We are only interested in those selections that lead to nonnegative solutions.

Let us use brute-force. Using NumPy,

from numpy import *
from itertools import combinations
from sys import float_info


# define the LP
A = array([[7, -7, 3, -3,-1, 0, 0],     # constraint matrix
           [1, -1, 3, -3, 0,-1, 0],
           [2, -2, 3, -3, 0, 0, 1]])
b = array([300, 200, 250])              # constraint vector
c = array([25,-25, 15,-15, 0, 0, 0])    # cost vector


# extract dimensions of A
(m,n) = A.shape


# generate all m-combinations of the columns
combos = map(list,list(combinations(range(n), m)))


solutions = []
for combo in combos:

    # extract m columns to build a square matrix
    A_square = A[:,combo]

    # check if square matrix is regular (if so, solve linear system)
    if abs(linalg.det(A_square)) > float_info.epsilon:

        # solve (square) linear system
        x_square = linalg.solve(A_square, b)

        # build solution vector
        x = zeros(n)
        x[combo] = x_square

        # check if solution is nonnegative (if so, append it to list)
        if (x_square >= 0).all():
            solutions.append( (x, dot(c,x)) )


print "The nonnegative solutions are \n"
for sol in solutions:
    print "(Solution, Cost) = ", (list(sol[0]), sol[1])

min_sol = min(solutions, key = lambda t : t[1])
print "\nThe minimal nonnegative solution is \n"
print "(Solution, Cost) = ", (list(min_sol[0]), min_sol[1])

which produces the following output:

The nonnegative solutions are 

(Solution, Cost) =  ([50.000000000000036, 0.0, 49.999999999999986, 0.0, 200.0000000000002, 0.0, 0.0], 2000.0000000000007)
(Solution, Cost) =  ([10.0, 0.0, 76.666666666666671, 0.0, 0.0, 40.00000000000005, 0.0], 1400.0)
(Solution, Cost) =  ([16.666666666666668, 0.0, 61.1111111111111, 0.0, 0.0, 0.0, 33.333333333333371], 1333.3333333333333)

The minimal nonnegative solution is 

(Solution, Cost) =  ([16.666666666666668, 0.0, 61.1111111111111, 0.0, 0.0, 0.0, 33.333333333333371], 1333.3333333333333)

Note that the $3$ nonnegative solutions correspond to the $3$ vertices of the feasible region in $\mathbb R^2$, a triangle. The minimal solution is

$$(x^*, y^*) = \left(\frac{150}{9}, \frac{550}{9}\right)\approx (16.67, 61.11)$$

whose cost is $\frac{4000}{3} \approx 1333.33$.