2
$\begingroup$

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:

enter image description here

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I see. Just to confirm the example I have is in the form $\mathbf{A} \mathbf{x} \leq \mathbf{b}$ with $ \mathbf{A} = \begin{bmatrix} 7 & 3 \\ 1 & 3 \\ 2 & 3 \end{bmatrix} $ and $ \mathbf{b} = \begin{bmatrix} 300 \\ 200 \\ 250 \end{bmatrix} $, with the cost vector being $\mathbf{c^T} = \begin{bmatrix} 25 & 15 \end{bmatrix}$, correct? Thanks for the help and the links to Linear Programming and Simplex Algorithm -- always great to be given a pointer to next places for reasearch :) $\endgroup$ – MeyCJey Jan 4 '17 at 20:29
  • 1
    $\begingroup$ @MeyCJey $\mathbf{A}$ would have to be $\mathbf{A} = \left[ \begin{array}{c c} -7 & -3 \\ -1 & -3 \\ 2 & 3 \end{array} \right]$, I think, since the direction of the first two inequalities is reversed. $\endgroup$ – VHarisop Jan 4 '17 at 20:38
  • $\begingroup$ Of course, silly mistake by me, the same should probably be done with $\mathbf{b}$ making it $ \mathbf{b} = \begin{bmatrix} -300 \\ -200 \\ 250 \end{bmatrix}$. Thanks for pointing that out. $\endgroup$ – MeyCJey Jan 4 '17 at 20:46
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.