Linear programs

Introduction to Linear Programs

• Linear programs are mathematical models representing optimization problems.
• The objective function, which is to be maximized or minimized, is a linear equation.

The Linear Program Components:

• Decision Variables: The unknowns to be determined.
• Objective Function: The function to be maximized or minimized.
• Constraints: The restrictions on the values of the decision variables.

Formulating a Linear Program

• Identify the decision variables in the problem.
• Formulate the objective function in terms of the decision variables.
• Identify and formulate the constraints in terms of the decision variables.

Solving a Linear Program

• Linear programs can be solved using various methods, including graphical methods, simplex method, and computational algorithms.
• An optimal solution to a linear program is a setting of decision variables that maximizes or minimizes the objective function, subject to the constraints.

Feasible Region and Optimal Solutions

• The feasible region is the set of all possible solutions that satisfy all constraints.
• An optimal solution lies within the feasible region and gives the best possible value for the objective function.
• If the feasible region is empty, there are no possible solutions, and the linear program is said to be infeasible.

Limitations of Linear Programs

• Linear programs assume proportionality and additivity in the objective function and constraints, which might not always be realistic.
• The divisibility assumption that decision variables take any value (including fractional), might not always be applicable.