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 realworld 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, multidimensional surfaces that divide space into two halfspaces.

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 largescale 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 realworld 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 realworld 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 decisionmakers.

Game theory can be used to solve linear programming problems by modeling the interactions between the decisionmakers as a game.