Review of Linear Programming Model

Introduction:

Linear Programming (LP) is a powerful mathematical technique used to optimize the allocation of limited resources among competing activities. It finds applications in various fields, such as operations research, economics, logistics, and supply chain management. In this review, we will explore the key components of the Linear Programming model, including problem formulation, graphical solution, special cases, and duality in LP.

1. Problem Formulation:

The Linear Programming model involves identifying an objective function to maximize or minimize, subject to a set of linear constraints. The general form of an LP problem can be expressed as follows:

Objective function: Z = c₁x₁ + c₂x₂ + ... + cₙxₙ

Subject to the constraints:

a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁

a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂

...

aₘ₁x₁ + aₘ₂x₂ + ... + aₘₙxₙ ≤ bₘ

Where:

- Z is the objective function to be either maximized or minimized.

- x₁, x₂, ..., xₙ are decision variables representing the quantities to be determined.

- c₁, c₂, ..., cₙ are coefficients of the decision variables in the objective function.

- aᵢⱼ represents the coefficients of the decision variables in the ith constraint.

- bᵢ represents the right-hand side (RHS) values of the ith constraint.

- m is the number of constraints.

2. Graphical Solution:

For problems with two decision variables (x and y), a graphical method can be used to find the optimal solution. The constraints define a feasible region, which is a bounded area in the coordinate plane satisfying all the constraints simultaneously. The objective is to find the point within this region that optimizes the objective function.

Steps for graphical solution: a. Plot the constraints on the coordinate plane, shading the feasible region. b. Identify the corner points (vertices) of the feasible region. c. Evaluate the objective function at each corner point. d. Select the corner point that yields the optimal value of the objective function.

3. Special Cases:

a. Infeasible Problem: If the feasible region is empty (no intersection of constraints), the problem is infeasible, meaning no solution exists that satisfies all the constraints simultaneously.

b. Unbounded Problem: If the feasible region is unbounded in a particular direction, the objective function can be infinitely increased or decreased, indicating an unbounded solution.

c. Degeneracy: In some LP problems, the optimal solution is found at a non-unique corner point due to redundant constraints or when more than two constraints intersect at a single point.

4. Duality in LP:

The concept of duality is fundamental in Linear Programming. Given an LP problem in its standard form, there is an associated dual problem, which provides valuable insights and information about the original problem.

For the primal (standard) problem:

Maximize Z = c₁x₁ + c₂x₂ + ... + cₙxₙ

Subject to:

a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁

a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂

...

aₘ₁x₁ + aₘ₂x₂ + ... + aₘₙxₙ ≤ bₘ

x₁, x₂, ..., xₙ ≥ 0

The dual problem is:

Minimize W = b₁y₁ + b₂y₂ + ... + bₘyₘ

Subject to:

a₁₁y₁ + a₂₁y₂ + ... + aₘ₁yₘ ≥ c₁

a₁₂y₁ + a₂₂y₂ + ... + aₘ₂yₘ ≥ c₂

...

a₁ₙy₁ + a₂ₙy₂ + ... + aₘₙyₘ ≥ cₙ

y₁, y₂, ..., yₘ ≥ 0

Here:

• W is the objective function of the dual problem.
• y₁, y₂, ..., yₘ are the dual variables corresponding to the constraints of the primal problem.
• c₁, c₂, ..., cₙ are the coefficients of the decision variables in the objective function of the primal problem.

The duality theorem states that the optimal solution to the dual problem provides a lower bound for the optimal solution of the primal problem, and vice versa.

Conclusion:

Linear Programming is a versatile optimization technique with broad applications in real-world problem-solving. Its problem formulation, graphical solution for two variables, handling of special cases, and the duality concept make it a valuable tool for decision-making and resource allocation.