If in any situation where a linear function is to be maximized subject to given constraints which are less than a positive integer and the variables to maximize are non negative then these can be solved and there exists a feasible solution.
In addition, it can also solve a minimization of a linear function by transforming it to a maximizing problem if the variables are non negative and the constrains are also non negative and can be converted to more than a positive figure.
If these conditions are not satisfied then there is not feasible solution or the system of linear equations do not have a feasible solution due to the inability to solve for all variables and there is no optimal solution for the linear system of equations according to the concepts of matrix algebra.
The method to solve or maximize a linear function subject to constrain is solved for more than two variables are by a method called simplex method. This method is based on the principles and concepts of matrix algebra by concerting the system of linear equations in to an augmented matrix form and by pivoting system of row and columns and in a sequential manner and get all negative amounts in the row of objective function. If the equations cannot get negative function then it cannot have any feasible optimum solution to the linear system of equation.
If a problem is of two non negative variables in linear function then it can be solved graphically. As well, sensitivity test can be performed to see the variation of the optimum solution by manipulating one variable and keep others constant so as to identify which variable affect the system of equation greatly and explore the percentage variation of that critical factor or possibility of that factor increasing to that amount considered.
Simplex method can be used for production planning to identify which, mix of products maximize profit subject to constraints. That is in production planning. As well, it also can be used to solve allocation problems to minimize cost or the production mix which will minimize cost rather than maximizing profit and in transportation problems to allocate routes to demand centers from supply sites in such a way to minimize cost.
Graphical method to solve optimal linear function.
Say a producer of two products X and Y wants to maximize profit where the profit margin is 0.5 and 0.8 respectively. In addition, it has two production departments and 1 unit of X uses 1.5 labor hours and in the other department it takes 2.5 labor hours. The other product takes 1.3 labor hours and in the other department it takes 2.8 labor hours and the maximum labor hours in the first department is 450 labor hours and in another it is 520 labor hours. What is the optimal level of production if any to this producer?
Step 1
Formulate the system of linear equation assuming they are equal
Objective function equation
Profit = 0.5 x + 0.8 y
Subject to constraints
Department 1
1.5 x+ 1.3 y = 450
Department 2
2.5 x + 2.8 y = 520
Step 2
Draw the objective function and the constraint function in one graph and shade the inequality section to determine the optimum feasibility area not shaded. Then draw parallel lines to the objective function through all the intersections of these constraint lines and see which is further from the origin or examine there exist more than one point or areas not coming in the intersection and separate from the intersections which will indicate the feasibility of more than one solution to the problem. The furthest point from the origin is the optimum solution if there exist one. Otherwise there is no optimum solution.
Step 3
Prove it is an optimal solution by examining other points algebraically by showing it is the maximum point and if any other combination will produce less than that. Or apply simplex method to arrive at a solution and check they are the same.
Graphical Presentation of the above problem
In the above diagram one can see the profit line y1- profit when you move parallel it can cut the const-2 at 208 and 300. However when it is further at 300 it cannot satisfy the other constraint and there fore it is not a feasible solution. But when it is 208 it satisfies the other constraint function. At this point the profit is maximized and other points give a lesser profit value because the profit function will move left and this is a lower level profit function. There fore the one solution is X = 208 and Y =0.
When x=208 and y=0 profit = 0.5*208 + 0.8*0 = 104
Say a combination of x=200 y=0 the profit is 0.5*200+0.8*0 =100. That is any parallel line left wards will have lower profit level. That is X=208 and Y=0 is the optimal solution. It can be seen in the above diagram the constraint co-efficient will affect the slope of the lines and there fore the intersection of the constraint lines and it affects the optimum solution or the infeasibility of an optimum solution.
