a linear programming problem are called constraints . The conditions x ≥ , y ≥ are called non-negative restrictions. In the above example, the set of inequalities ( ) to ( ) are constraints . Optimisation problem A problem which seeks to maximise or minimise a linear function (say of two variables x and y ) subject to certain constraints as determined by a set of linear inequalities is called an optimisation problem .
Linear programming problems are special type of optimisation problems. The above problem of investing a LINEAR PROGRAMMING given sum by the dealer in purchasing chairs and tables is an example of an optimisation problem as well as of a linear programming problem. We will now discuss how to find solutions to a linear programming problem. In this chapter, we will be concerned only with the graphical method.
. . Graphical method of solving linear programming problems In Class XI, we have learnt how to graph a system of linear inequalities involving two variables x and y and to find its solutions graphically. Let us refer to the problem of investment in tables and chairs discussed in Section .
. We will now solve this problem graphically. Let us graph the constraints stated as linear inequalities: x + y ≤ x + y ≤ x ≥ y ≥ The graph of this system (shaded region) consists of the points common to all half planes determined by the inequalities ( ) to ( ) (Fig . ).
Each point in this region represents a feasible choice open to the dealer for investing in tables and chairs. The region, therefore, is called the feasible region for the problem. Every point of this region is called a feasible solution to the problem. Thus, we have, Feasible region The common region determined by all the constraints including non-negative constraints x , y ≥ of a linear programming problem is called the feasible region (or solution region) for the problem.
In Fig . , the region OABC (shaded) is the feasible region for the problem. The region other than feasible region is