Convex Optimization - Linear Programming

Methodology

Linear Programming also called Linear Optimization, is a technique which is used to solve mathematical problems in which the relationships are pnear in nature. the basic nature of Linear Programming is to maximize or minimize an objective function with subject to some constraints. The objective function is a pnear function which is obtained from the mathematical model of the problem. The constraints are the conditions which are imposed on the model and are also pnear.

From the given question, find the objective function.

find the constraints.

Draw the constraints on a graph.

find the feasible region, which is formed by the intersection of all the constraints.

find the vertices of the feasible region.

find the value of the objective function at these vertices.

The vertice which either maximizes or minimizes the objective function (according to the question) is the answer.

Examples

Step 1 − Maximize $5x+3y$ subject to

$x+yleq 2$,

$3x+yleq 3$,

$xgeq 0 :and :ygeq 0$

Solution −

The first step is to find the feasible region on a graph.

Clearly from the graph, the vertices of the feasible region are

$left ( 0, 0 ight )left ( 0, 2 ight )left ( 1, 0 ight )left ( frac{1}{2}, frac{3}{2} ight )$

Let $fleft ( x, y ight )=5x+3y$

Putting these values in the objective function, we get −

$fleft ( 0, 0 ight )$=0

$fleft ( 0, 2 ight )$=6

$fleft ( 1, 0 ight )$=5

$fleft ( frac{1}{2}, frac{3}{2} ight )$=7

Therefore, the function maximizes at $left ( frac{1}{2}, frac{3}{2} ight )$

Step 2 − A watch company produces a digital and a mechanical watch. Long-term projections indicate an expected demand of at least 100 digital and 80 mechanical watches each day. Because of pmitations on production capacity, no more than 200 digital and 170 mechanical watches can be made daily. To satisfy a shipping contract, a total of at least 200 watches much be shipped each day.

If each digital watch sold results in a $$2$ loss, but each mechanical watch produces a $$5$ profit, how many of each type should be made daily to maximize net profits?

Solution −

Let $x$ be the number of digital watches produced

$y$ be the number of mechanical watches produced

According to the question, at least 100 digital watches are to be made daily and maximaum 200 digital watches can be made.

$Rightarrow 100 leq :xleq 200$

Similarly, at least 80 mechanical watches are to be made daily and maximum 170 mechanical watches can be made.

$Rightarrow 80 leq :yleq 170$

Since at least 200 watches are to be produced each day.

$Rightarrow x +yleq 200$

Since each digital watch sold results in a $$2$ loss, but each mechanical watch produces a $$5$ profit,

Total profit can be calculated as

$Profit =-2x + 5y$

And we have to maximize the profit, Therefore, the question can be formulated as −

Maximize $-2x + 5y$ subject to

$100 :leq x:leq 200$

$80 :leq y:leq 170$

$x+y:leq 200$

Plotting the above equations in a graph, we get,

The vertices of the feasible region are

$left ( 100, 170 ight )left ( 200, 170 ight )left ( 200, 180 ight )left ( 120, 80 ight ) and left ( 100, 100 ight )$

The maximum value of the objective function is obtained at $left ( 100, 170 ight )$ Thus, to maximize the net profits, 100 units of digital watches and 170 units of mechanical watches should be produced.