Linear algebra application in linear programming

Application to linear programming
Linear programming is used for arithmetical calculations such as maximizing and minimizing
of a certain quantity under some various constraints. Most of the problems in day-to-day life
we have to consider maximizing and minimizing. But rather than simple analytical problems
there will be some other advance problems, that have to consider many number of constraints
simultaneously. Such problems, linear programming can be used as a guiding tool.
Problems that can contains any number of variables and also many number of constraints. If
these constraints are interrelated with linearly, can be applied linear algebraic concepts. In the
world of science and also industrial related problems can be solved or can get optimal
solution with the help of this technique.
As an approach we can get two variable geometric problem. In generally we can get any two
variables that are subjected to series of constraints. As an instance, let’s get 𝑧 = 𝑎𝑥 + 𝑏𝑦,
where a and b are constants. We have given that maximize or minimize z, that subjected to
following constraints.
𝑎1 𝑥 + 𝑏1 𝑦 (≤)(≥)(=) 𝑐1
𝑎2 𝑥 + 𝑏2 𝑦 (≤)(≥)(=) 𝑐2
𝑎3 𝑥 + 𝑏3 𝑦 (≤)(≥)(=) 𝑐3
𝑎 𝑛 𝑥 + 𝑏 𝑛 𝑦 (≤)(≥)(=) 𝑐 𝑛
and also, 𝑥 ≥ 0, 𝑦 ≥ 0. Here that equations that show above could have only one symbol
among them. These problem-solving method is going similarly with the genetic algorithm
problems. In genetic algorithms, basically the logic is implemented using randomly generated
values and then check the constraints. Then get the values of z. And also after calculations,
use penalty values and optimize the penalty values.
Here the main function, that is the equation or constraint containing, z is the objective
function. We are trying to get optimal solution for z as our final goal. The values that satisfy
all constraints are called as feasible solutions, and also the region that feasible values are
spread out is called as feasible region. If the problem has many number of constraints, we
cannot put each and every value and check the satisfaction. So that when we can find a
region that contains satisfactory values, will cause to reduce the calculation effort.
Here we are going to focus on linearly related variables, but when we have problems such as
nonlinear related, have to look another solving methods. As an example, genetic algorithm is

a one programming concept that can use to develop nonlinear programming and get
optimized solution. Another method is neural networks. These are quite high-end
programming concepts, that are more developed than linear programming. Because of the
advance, these concepts can be used to implement the artificial intelligence problem solving
logics also.
Let’s focus on linear programming. 𝑎1 𝑥 + 𝑏1 𝑦 = 𝑐1is an equation of a straight line that
contain in xy plane. 𝑎1 𝑥 + 𝑏1 𝑦 ≤ 𝑐1 𝑜𝑟 𝑎1 𝑥 + 𝑏1 𝑦 ≥ 𝑐1 are represent half side of the plane.
If there is a constraint that contains inequality symbol, that means that region is contained
many lines. With regarding many constraints, we can get bounded region, that means the
region is enclosed with sufficient constraints. Another type is unbounded region. That implies
that the region is cannot be exactly determined. There can be feasible regions that has no
constraints points, means empty feasible region. Also, extreme points are the points that are
boundary points intersection of the straight-line sections.
There are some theorems that will guided us to the successful answers that are satisfy all
constraint points. These theorems said that,
“If the feasible region of a linear programming problem is nonempty and bounded, then the
objective function attains both a maximum and minimum value and these occur at extreme
points of the feasible region. If the feasible region is unbounded, then the objective function
may or may not attain a maximum or minimum value; however, if it attains a maximum or
minimum value, it does so at an extreme point.”
we can get an example and try to solve.
A candy manufacturer has 130 pounds of chocolate-covered cherries and 170 pounds of
chocolate-covered mints in stock. He decides to sell them in the form of two different
mixtures. One mixture will contain half cherries and half mints by weight and will sell for
$2.00 per pound. The other mixture will contain one-third cherries and two-thirds mints by
weight and will sell for $1.25 per pound. How many pounds of each mixture should the
candy manufacturer prepare in order to maximize his sales revenue?
Let’s get approach to this question. For the simplicity we can call A the mixture of half
cherries and half mints, and B the mixture which is 1/3 cherries and 2/3 mints. X be the
number of pounds of A to be prepared and y the number of pounds of B to be prepared. With
that we can build our objective function.
𝑧 = 2𝑥 + 1.25𝑦

The total number of pounds of cherries in both mixture is
1
2
𝑥 +
1
3
𝑦
The total number of pounds of mints used in both mixtures is
1
2
𝑥 +
2
3
𝑦
Using that data, we can derive constraints as shown in bellow,
1
2
𝑥 +
1
3
𝑦 ≤ 130
1
2
𝑥 +
2
3
𝑦 ≤ 170
Using given data
𝑥 ≥ 0
𝑦 ≥ 0
To solve the question, we can use linear programming technique as mentioned above. After
that we have to define feasible region. That have to define feasible region first.
Here we can see that the feasible region is bounded. The optimal solution can be found at the
extreme points as shown in the graph. So that to evaluating the objective function, we can get
the values as follows.

As shown in the table, we can see, largest value for z is 520.0 and the optimal solution is
(260,0). So that manufacture can get maximum sae of $520 when he produces 260 pounds of
mixture A and none of mixture B.
This example is taken out from the website, the link is mentioned in the reference region.
That is a simple problem that can be solved using linear programming. We can say the
equations can be solved easily without aid of any computer programme. But we have to
remember, these methods can be implemented to higher accuracy needed and more number
of constrained problems, that we cannot even think about the feasible region. And also, the
problem is get more complex when the feasible region is un-bounded.
Algorithm making and computer coding methods are varying from people to people, because
all of them looking for the problem in different angles. And also deriving equations will be
different. So that we have to improve our own method to solve these types of equations.
References
Application to linear programming. (n.d.). Retrieved from Applications of linear algebra:
http://aix1.uottawa.ca/~jkhoury/app.htm
ANTON, H. and C. RORRES. Elementary Linear Algebra: Applications Version, 8th ed. New York: John
Wiley & Sons, Inc., 2000.

Linear algebra application in linear programming

Recommended

More Related Content

What's hot (20)

Similar to Linear algebra application in linear programming (20)

More from Lahiru Dilshan (20)

Recently uploaded (20)

Linear algebra application in linear programming