Chapter:12

What are Linear Programming ?

A linear programming problem is one that is concerned with finding the optimal value of a linear function of several variables subject to the conditions that the variables are non- negative and satisfy a set of linear inequalities.

Angle Between Two Lines

  • Constraints : The linear inequalities or equations or restrictions on the variables of a linear programming problem are called constraints. The conditions x โ‰ฅ 0, y โ‰ฅ 0 are called non-negative restrictions.
  • Objective Function : Linear function Z = ax + by, where a, b are constants, which has to be maximized or minimized is called a linear objective function.
  • Optimisation : A problem which seeks to maximise or minimize a linear function subject to certain constraints as determined by a set of linear inequalities is called an optimization.
  • Different Types Of Linear Programming Problems : A few important linear programming problems are: (i) Diet problems (ii) Manufacturing problems (iii) Transportation problems

Graphical Method Of Solution For Problems In Two Variables

Step: 1โ†’Formulate the LP problem

Step: 2โ†’Construct a graph and plot the constraint lines.

Step: 3โ†’Determine the valid side of each constraint line.

Step: 4โ†’Identify the feasible solution region.

Step: 5โ†’Plot the objective function on the graph.

Step: 6โ†’Find optimum point.

Feasible And Infeasible Regions

The common region determined by all the constraints including the non-negative constraints x โ‰ฅ 0, y โ‰ฅ 0 of a linear programming problem is called the feasible region. The region other than feasible region is called an infeasible region.

Feasible And Infeasible Solutions

Points within and on the boundary of the feasible region represent feasible solutions of the constraint. Any point outside the feasible region is an infeasible solution.

Optimal Feasible Solutions

Any point in the feasible region that gives the optimal value (maximum or minimum) of the objective function is called an optimal solution.