Notes from Toppers

Linear Programming

Introduction

  • Introduction to linear programming:
  • Linear programming is a method for solving optimization problems that involve linear functions.
  • It is used in a wide variety of applications, including economics, business management, and engineering.
  • Graphical method of solving linear programming problems:
  • The graphical method is a simple method for solving linear programming problems involving two variables.
  • It involves graphing the constraints and objective function and finding the point of intersection that gives the optimal solution.

Linear Programming

  • Standard Form to a Canonical form:

  • The standard form of a linear programming problem is a mathematical representation of the problem that is used for solving it using the simplex method. It is used for converting real-world applications to mathematical representations that can be easily solved.

  • Solving linear programming problems using simplex method:

  • The simplex method is an iterative method for solving linear programming problems.

  • It starts at a feasible solution and moves to adjacent feasible solutions until it reaches the optimal solution.

  • Duality in Linear Programming:

  • Duality in linear programming refers to the relationship between a linear programming problem and its dual problem.

  • The dual problem is formed by interchanging the roles of the variables and constraints in the original problem.

Special Cases of Linear Programming Problems

  • Transportation problems:

  • Transportation problems are linear programming problems that involve the transportation of goods from one location to another.

  • The objective is to minimize the transportation cost while satisfying the demand at each destination.

  • Assignment problems:

  • Assignment problems are linear programming problems that involve assigning tasks to people or resources.

  • The objective is to minimize the total cost or time required to complete the tasks.

  • Travelling salesman problem:

  • The travelling salesman problem is a linear programming problem that involves finding the shortest route for a salesperson who visits a set of cities and returns to the starting city.

  • The objective is to minimize the total distance traveled by the salesperson.

Applications of Linear Programming

  • In economics and business management:

  • Linear programming is used in economics to solve problems such as resource allocation, production planning, and capital budgeting.

  • It is also used in business management to solve problems such as inventory control, scheduling, and facility location.

  • In the optimization of production and distribution:

  • Linear programming is used in the optimization of production and distribution systems.

  • It is used to determine the optimal production levels, the optimal distribution routes, and the optimal inventory levels.

  • In the design of transportation systems:

  • Linear programming is used in the design of transportation systems.

  • It is used to determine the optimal routes for transportation vehicles, the optimal schedules, and the optimal number of vehicles.

  • In the planning of resource allocation:

  • Linear programming is used in the planning of resource allocation.

  • It is used to determine the optimal allocation of resources to different projects or activities.

Mathematical Concepts Used in Linear Programming

  • Linear inequalities:

  • Linear inequalities are mathematical expressions that involve linear functions.

  • They are used to represent the constraints in linear programming problems.

  • Convex sets:

  • Convex sets are sets that have the property that any two points in the set can be connected by a straight line that lies entirely within the set.

  • Convex sets are important in linear programming because the feasible region of a linear programming problem is a convex set.

  • Hyperplanes:

  • Hyperplanes are flat, multi-dimensional surfaces that divide space into two half-spaces.

  • Hyperplanes are important in linear programming because they are used to represent the constraints in linear programming problems.

  • Simplexes:

  • Simplexes are polytopes that have n + 1 vertices in n dimensions.

  • Simplexes are important in linear programming because the feasible region of a linear programming problem is a simplex.

Solving Techniques for Linear Programming

  • The graphical method:

  • The graphical method is a simple method for solving linear programming problems involving two variables.

  • It involves graphing the constraints and objective function and finding the point of intersection that gives the optimal solution.

  • The simplex method:

  • The simplex method is an iterative method for solving linear programming problems.

  • It starts at a feasible solution and moves to adjacent feasible solutions until it reaches the optimal solution.

  • The revised simplex method:

  • The revised simplex method is a variant of the simplex method that is more efficient for solving large-scale linear programming problems.

  • It involves using a different set of pivot rules to select the variables that enter and leave the basis.

  • Duality theory:

  • Duality theory is a mathematical theory that relates a linear programming problem to its dual problem.

  • Duality theory can be used to solve linear programming problems by solving their dual problems.

Extensions and Generalizations of Linear Programming

  • Nonlinear programming:

  • Nonlinear programming is a generalization of linear programming that allows for nonlinear functions in the objective function and/or the constraints.

  • Nonlinear programming problems are more difficult to solve than linear programming problems, but they can be used to model a wider range of real-world applications.

  • Integer programming:

  • Integer programming is a generalization of linear programming that requires the variables to be integers.

  • Integer programming problems are more difficult to solve than linear programming problems, but they can be used to model a wider range of real-world applications.

  • Dynamic programming:

  • Dynamic programming is a technique for solving optimization problems that involve multiple stages.

  • Dynamic programming can be used to solve linear programming problems by breaking them down into a sequence of smaller problems that can be solved more easily.

  • Game theory:

  • Game theory is a branch of mathematics that studies the interactions between decision-makers.

  • Game theory can be used to solve linear programming problems by modeling the interactions between the decision-makers as a game.



Table of Contents