Linear Programming 1 Overview

Linear Programming is a mathematical technique for maximizing or minimizing a linear function of several variables, such as output or cost

Subjects > Mathematics > Linear Programming 1

Before moving direct into the problems of Linear Programming 1, let's see what we need to know about Linear Programming.

Meaning of Linear Programming

Linear programming sometimes called Linear Optimization (LP) may be defined in various ways as follows:

  • Is a mathematical technique for maximizing or minimizing a linear function of several variables, such as output or cost
  • Is the simplest technique where we depict complex relationships through linear functions and then find the optimum points.
  • Is the method to achieve the best outcome (maximum or minimum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships.
  • Is the method to allocate scarce resources to competing activities in an optimal manner when the problem can be expressed using linear objective function and linear inequality constraints.

Common Terminologies used in Linear Programming

  1. Decision variables:
    Are the variables which will decide the output. They represent the ultimate solution.
  2. Objective function:
    It is defined as the objective of making decisions. For example "to make profit" is a objective function
  3. Constraints:
    Are restrictions or limitations on decision variables. They usually limit the value of the decision variables.
  4. Non-negativity restrictions:
    For all linear programs, the decision variables should always take non-negative values, which means the values for decision variables should be greater or equal to zero (0).

Process to formulate a Linear Programming problem

  1. Identify the decision variables
  2. Write the objective function
  3. Mention the constraints
  4. Explicitly state the non-negativity restrictions

For a problem to be a linear programming problem, the decision variables, objective function and constraints altogether have to be linear functions

Solutions of Linear Programming problem

Linear programming problems can be solved using different methods such as:

  • Graphical method
  • Using Open solver
  • Simplex method
  • Northwest Corner & least count method
The commonly used method is Graphical method, let's see how to solve using Graphical Method

How to solve LP problem using Graphical method ?

  1. If a linear programming problem P has a solution, then it must occurs at a vertex, or corner points of feasible region (set), S associated with the problem.
  2. Feasible region is the region where solutions are possible and likely to be achieved.
    It is bounded by corner points

  3. Suppose we are given a linear programming problem with a feasible set S and an objective function P = ax + by, then:
    • If S (feasible region) is bounded then P has both maximum and minimum values on S.
    • If S is unbounded and both a and b are non-negative, then P has a maximum value on S provided that the constraints defining S include x ≥ 0 and y ≥ 0.
  4. Method of Corners:
    • Graph the feasible set, S
    • Find exact coordinates of all corner points
    • Evaluate the objective function, P at each vertex.
    • The maximum (if it exists) is the largest value of P at a vertex
    • The minimum is the smallest value of P at a vertex.

You can learn more about Linear Programming 2 here

Now, let's move in. Solved Linear Programming questions.

Recommended Lessons

Before moving direct into the problems of Linear Programming 1, let's see what we need to know about Linear Programming.

Meaning of Linear Programming

Linear programming sometimes called Linear Optimization (LP) may be defined in various ways as follows:

  • Is a mathematical technique for maximizing or minimizing a linear function of several variables, such as output or cost
  • Is the simplest technique where we depict complex relationships through linear functions and then find the optimum points.
  • Is the method to achieve the best outcome (maximum or minimum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships.
  • Is the method to allocate scarce resources to competing activities in an optimal manner when the problem can be expressed using linear objective function and linear inequality constraints.

Common Terminologies used in Linear Programming

  1. Decision variables:
    Are the variables which will decide the output. They represent the ultimate solution.
  2. Objective function:
    It is defined as the objective of making decisions. For example "to make profit" is a objective function
  3. Constraints:
    Are restrictions or limitations on decision variables. They usually limit the value of the decision variables.
  4. Non-negativity restrictions:
    For all linear programs, the decision variables should always take non-negative values, which means the values for decision variables should be greater or equal to zero (0).

Process to formulate a Linear Programming problem

  1. Identify the decision variables
  2. Write the objective function
  3. Mention the constraints
  4. Explicitly state the non-negativity restrictions

For a problem to be a linear programming problem, the decision variables, objective function and constraints altogether have to be linear functions

Solutions of Linear Programming problem

Linear programming problems can be solved using different methods such as:

  • Graphical method
  • Using Open solver
  • Simplex method
  • Northwest Corner & least count method
The commonly used method is Graphical method, let's see how to solve using Graphical Method

How to solve LP problem using Graphical method ?

  1. If a linear programming problem P has a solution, then it must occurs at a vertex, or corner points of feasible region (set), S associated with the problem.
  2. Feasible region is the region where solutions are possible and likely to be achieved.
    It is bounded by corner points

  3. Suppose we are given a linear programming problem with a feasible set S and an objective function P = ax + by, then:
    • If S (feasible region) is bounded then P has both maximum and minimum values on S.
    • If S is unbounded and both a and b are non-negative, then P has a maximum value on S provided that the constraints defining S include x ≥ 0 and y ≥ 0.
  4. Method of Corners:
    • Graph the feasible set, S
    • Find exact coordinates of all corner points
    • Evaluate the objective function, P at each vertex.
    • The maximum (if it exists) is the largest value of P at a vertex
    • The minimum is the smallest value of P at a vertex.

You can learn more about Linear Programming 2 here

Now, let's move in. Solved Linear Programming questions.

Recommended Lessons