Linear Programming

LINEAR PROGRAMMING

Description also available in video format (attached below), for better experience use your desktop.

INTRODUCTION

1. BASIC CONCEPT

• Linear Programming is a mathematical technique used for optimization — i.e., maximizing or minimizing a linear objective function, subject to a set of linear constraints (inequalities or equations).
• Used in resource allocation, cost minimization, and profit maximization problems.

Key Features

• Objective function must be linear.
• Constraints (limitations) must also be linear.
• Decision variables must be non-negative.

Applications in Healthcare

• Optimal staff scheduling.
• Budget allocation for departments.
• Optimal use of operation theatres.

2. FORMULATION OF A LINEAR PROGRAMMING PROBLEM

1. Identify the decision variables
• What are you trying to decide? (e.g., number of nurses, beds, machines, etc.)
2. Construct the objective function
• Usually to maximize profit or minimize cost.
3. Write the constraints
• Resources (time, money, space, staff, etc.)
4. Add non-negativity restrictions:
• x₁, x₂, ..., xₙ ≥ 0

3. GRAPHICAL METHOD

• Applicable when there are two variables only (x and y).

Steps

1. Convert each inequality constraint into an equation and draw the lines on a graph.
2. Identify the feasible region (area satisfying all constraints).
3. Identify the corner points of the feasible region.
4. Evaluate the objective function at each corner point.
5. The point that gives the maximum (or minimum) value is the optimal solution.

Note: For unbounded feasible regions, sometimes no optimal solution exists.

4. SIMPLEX METHOD

• Used for solving LP problems with more than two variables.
• A systematic, tabular method to find the optimal solution.

Steps (Simplified):

1. Convert inequalities into equations using slack/surplus variables.
2. Construct the initial simplex tableau.
3. Identify the pivot column (most negative in bottom row) – entering variable.
4. Identify the pivot row – leaving variable (minimum ratio test).
5. Perform row operations to make pivot element = 1 and other column values = 0.
6. Repeat until all bottom-row values (Z-row) are non-negative → Optimal solution reached.

Advantage: Can handle complex problems efficiently.

5. DUALITY IN LINEAR PROGRAMMING

• Every linear programming problem (called Primal) has a corresponding Dual problem.
• The solution to one provides insights into the other.

Primal-Dual Relationship:

Primal Problem	Dual Problem
Maximize Z	Minimize W
Subject to ≤	Subject to ≥
Decision variables	Constraints
Constraints	Decision variables

Importance:

·       Helps to understand shadow prices (value of one additional unit of a resource).

·       Used in sensitivity analysis.

·       Linear Programming is a powerful tool for decision-making, especially in hospital administration, finance, operations, and logistics.

·       Understanding both the graphical and simplex methods along with duality gives a well-rounded ability to solve real-world resource optimization problems.

Video Description

·       Don’t forget to do these things if you get benefitted from this article

o   Visit our Let’s contribute page https://keedainformation.blogspot.com/p/lets-contribute.html

o   Follow our  page

o   Like & comment on our post

·