1. Introduction
Linear programming is useful because many real situations involve choosing the best possible way to use limited resources. Whether the goal is to maximize profit, minimize cost, or plan schedules efficiently, linear programming gives a clean mathematical method to make the best choice among all allowed options.
To keep things simple, these notes show different kinds of real-life situations where linear programming fits naturally, along with small examples that make the ideas easy to visualise.
2. Resource Allocation
Many real-life problems involve distributing limited resources among different activities. Linear programming helps decide how much of each activity to perform while respecting limitations.
2.1. Basic Idea
Resources such as time, raw materials, labour, and money are usually limited. If different activities consume resources at different rates, we can write linear constraints to describe these limits. The aim is often to maximise output or minimise waste.
2.2. Small Example
Suppose two tasks, represented by \(x\) and \(y\), use resources as follows:
- Task \(x\) uses 2 units per item.
- Task \(y\) uses 3 units per item.
If the total available resource is 40 units, the constraint becomes:
\( 2x + 3y \le 40 \)
An objective such as maximising output or value determines the best combination of \(x\) and \(y\).
3. Profit Maximization in Production
Linear programming is often used to decide how much of each product to manufacture when there are limits on resources like machine time, workforce hours, or raw materials.
3.1. Concept
If two items give different profits per unit and require different amounts of limited resources, a linear programming model helps determine the product mix that yields the maximum total profit.
3.2. Illustrative Example
Suppose:
- Each unit of \(x\) gives a profit of 50.
- Each unit of \(y\) gives a profit of 30.
- Both use limited machine time.
Then the objective function becomes:
\( Z = 50x + 30y \)
Constraints come from machine-time limits or resource limits, and the solution gives the best production plan.
4. Cost Minimization
In many situations, the aim is to do a job at the lowest possible cost. Linear programming models these situations easily because costs often depend linearly on how much of each activity is done.
4.1. Idea Behind Cost Minimization
If each activity has a cost per unit and activities must satisfy certain requirements, a minimization model helps find the cheapest combination that meets all needs.
4.2. Example
Suppose we must produce at least 10 units of something, and we can choose between two methods:
- Method A costs 8 per unit.
- Method B costs 5 per unit.
If \(x\) and \(y\) are the quantities produced by A and B, we may have:
\( x + y \ge 10 \)
Cost function:
\( Z = 8x + 5y \)
The linear programming model finds the minimum cost combination of \(x\) and \(y\).
5. Diet and Nutrition Problems
This is a classic real-life usage of linear programming: choosing food items that meet nutritional requirements at minimum cost.
5.1. Basic Reason
Different foods contain different amounts of nutrients such as proteins, vitamins, and carbohydrates. If there are minimum requirements for each nutrient and the cost of each food is known, linear programming helps pick the cheapest possible combination.
5.2. Simple Illustration
Suppose food A contains:
- 3 units of nutrient 1
- 1 unit of nutrient 2
Food B contains:
- 1 unit of nutrient 1
- 2 units of nutrient 2
If the minimum required nutrients are:
\( 3x + y \ge 8 \)
\( x + 2y \ge 6 \)
where \(x\) and \(y\) are quantities of foods A and B. The cost expression is then minimized to find the best combination.
6. Scheduling and Assignment Problems
Linear programming can be used in workforce scheduling, machine assignment, time-table creation, and similar situations where tasks must be assigned fairly and efficiently.
6.1. Why Scheduling Fits LP
Scheduling usually involves constraints like:
- each task must be done once,
- workers have limited time,
- machines cannot work beyond capacity.
These can be written as linear constraints, and objective functions can be used to minimize total time or maximise productivity.
6.2. Example
Suppose a worker can handle at most 6 hours of work, and two tasks require different times:
- Task A takes 2 hours per unit (variable \(x\)).
- Task B takes 3 hours per unit (variable \(y\)).
The constraint becomes:
\( 2x + 3y \le 6 \)
With an objective function such as maximising completed tasks or minimising unused time, the linear programming model finds the best schedule.
7. Transportation and Supply Problems
When goods must be shipped from several sources to several destinations, the aim is usually to minimise total transport cost. Linear programming plays a major role in such supply chain problems.
7.1. The Core Idea
Each route has a cost per unit shipped. Each source has a limited supply, and each destination has a demand requirement. Linear constraints capture these limits, and a minimization objective finds the cheapest shipping plan.
7.2. Example Setup
If route 1 costs 4 per unit and route 2 costs 6 per unit, and the total supply and demand must balance, a cost function like:
\( Z = 4x + 6y \)
is minimized with constraints describing supply and demand. The LP model then finds the cheapest transport arrangement.
8. A Small Combined Example
To connect all the ideas, here is a small mixed example involving allocation, cost, and optimisation.
8.1. Problem Idea
Suppose:
- Two activities \(x\) and \(y\) consume resources.
- Each unit of \(x\) gives a value of 5 and each unit of \(y\) gives a value of 7.
- Resource limits restrict how big \(x\) and \(y\) can be.
Then:
\( Z = 5x + 7y \)
is the quantity to be maximized, with constraints like:
\( 2x + y \le 12 \)
\( x + 3y \le 15 \)
The solution gives the best real-life decision under the given limitations.