1. Introduction
Some linear programming problems aim not to increase something, but to reduce it. This could be cost, time, distance, material usage, or any quantity that we want to keep as small as possible. These are called minimization problems.
To think clearly about minimization, it helps to remember two pieces: a value we are trying to make as small as possible (the objective function), and a set of points that we are allowed to choose from (the feasible region). The best solution is the feasible point that gives the smallest value of the objective function.
2. Objective Function in Minimization Problems
The quantity being minimized is expressed by a linear formula called the objective function. It tells how the variables contribute to the total value, and the aim is to choose variable values that keep this total as low as possible.
2.1. Meaning of the Objective Function
A minimization objective function is usually written as:
\( Z = ax + by \)
Here:
- \(Z\) is the value we want to make as small as possible.
- \(x\) and \(y\) are decision variables.
- \(a\) and \(b\) are constants showing how much each unit of the variable contributes.
Our goal is to find a point \((x, y)\) inside the feasible region where the value of \(Z\) is minimal.
2.2. Standard Form
In general, the objective function in a minimization problem can be written as:
\( Z = c_1 x_1 + c_2 x_2 + \dots + c_n x_n \)
Each coefficient \(c_i\) tells how strongly the variable \(x_i\) adds to the quantity we want to minimize. Higher coefficients mean the variable increases the cost or value faster, so the constraints will decide how much of each variable is allowed.
3. Feasible Region in Minimization Problems
The feasible region is the set of all points that satisfy every constraint. Even if a point gives a low value of \(Z\), it cannot be chosen unless it lies inside this region. So minimization happens only over the feasible region, not the whole plane.
3.1. Allowed Choices for Minimization
In a minimization problem:
- Every point inside the feasible region is a valid choice.
- Points outside break at least one constraint and cannot be used.
The challenge is to locate the feasible point where the objective function takes its smallest value.
4. Minimizing a Linear Function Over a Region
Just like in maximization, the objective function \(Z = ax + by\) forms a family of parallel lines. As we shift these lines in the direction where \(Z\) decreases, the goal is to find the first point where the line touches the feasible region. That touching point gives the minimum value.
4.1. Direction of Decrease
Consider the line:
\( ax + by = Z_0 \)
If we move this line parallel to itself in the direction where its constant value decreases, the value of \(Z\) becomes smaller. We want to move it as far as possible in that direction until it just touches the feasible region.
4.2. Sliding the Objective Line
The geometric method is simple:
- Draw one trial line for some value of \(Z\).
- Slide the line in the direction of decreasing \(Z\).
- The last point where the line still touches the feasible region gives the minimum value of \(Z\).
This touching point is usually a corner point.
5. Corner Point Principle in Minimization
The same principle used for maximization applies to minimization: the optimum value of a linear function over a convex feasible region always occurs at a corner point.
5.1. Reason Behind the Principle
Inside the region, there is always a nearby point that gives an equal or smaller value of \(Z\). So the minimum cannot be in the interior unless the entire region gives the same value (a rare special case). The search naturally moves toward the boundary and then to the corner points.
5.2. Steps to Find the Minimum
The procedure is:
- Find all corner points of the feasible region.
- Compute the value of \(Z\) at each corner point.
- The point giving the smallest value is the solution.
This method is simple because the number of corner points is small, even though the feasible region contains infinitely many points.
6. When Does a Minimum Exist?
A minimum value of a linear objective function exists only under certain conditions. Understanding these makes it easier to see whether solving the problem is meaningful.
6.1. Bounded Feasible Region
If the feasible region is bounded and non-empty, then there will definitely be both a minimum and a maximum value of \(Z\). This is because the region is closed and finite.
6.2. Unbounded Feasible Region
If the feasible region is unbounded, the minimum may or may not exist. It exists only if the direction in which \(Z\) decreases is blocked by the constraints. If \(Z\) can decrease indefinitely while staying feasible, then no minimum exists.
7. Simple Example of a Minimization Problem
This small example shows the steps clearly without using heavy numbers. It illustrates how the minimum value appears at a corner point.
7.1. Formulating the Problem
Suppose the aim is to minimize:
\( Z = 3x + 2y \)
Subject to:
- \( x + y \ge 4 \)
- \( x \ge 1 \)
- \( y \ge 0 \)
The feasible region is the set of points that satisfy all these conditions at the same time.
7.2. Corner Points and Minimum Value
The boundary lines give three corner points:
- A: \((1, 3)\) from \(x = 1\) and \(x + y = 4\)
- B: \((4, 0)\) from \(y = 0\) and \(x + y = 4\)
- C: \((1, 0)\) from \(x = 1\) and \(y = 0\)
Now evaluate \(Z\) at these points:
- At A: \(Z = 3(1) + 2(3) = 9\)
- At B: \(Z = 3(4) + 2(0) = 12\)
- At C: \(Z = 3(1) + 2(0) = 3\)
The smallest value is \(Z = 3\) at point \((1, 0)\).
This point is therefore the solution to the minimization problem.