Maximization Problems

The objective function is usually written in a linear form such as:

\( Z = ax + by \)

Here:

• \(Z\) is the quantity to be maximized (profit, production, etc.).
• \(x\) and \(y\) are decision variables.
• \(a\) and \(b\) are constants showing how strongly each variable contributes.

A larger value of \(Z\) means a better solution, as long as \(x\) and \(y\) still satisfy all constraints.

For maximization, the objective function is usually written in a neat linear form:

\( Z = c_1 x_1 + c_2 x_2 + \dots + c_n x_n \)

Each coefficient \(c_i\) shows how much one unit of \(x_i\) increases \(Z\). If all \(c_i\) are non-negative, increasing variables (within the constraints) generally increases \(Z\).

Every point \((x, y)\) in the plane falls into one of two categories:

• It satisfies all constraints and is therefore feasible.
• It breaks at least one constraint and is therefore not feasible.

In a maximization problem, even if a point gives a very large value of \(Z\), it cannot be chosen if it is not feasible.

For a given objective function, the direction of increase can be understood by looking at one particular line:

\( ax + by = Z_0 \)

If I move this line in a certain direction (keeping it parallel), the value of \(Z\) increases. In a graph, the goal is to push this line as far as possible in that direction while it still touches the feasible region.

On the picture of the feasible region:

1. Draw one line for a convenient trial value of \(Z\).
2. Shift this line parallel to itself in the direction where \(Z\) increases.
3. The last point of contact between the line and the feasible region gives the maximum value of \(Z\).

This last contact point is always at the boundary of the region, usually at a corner point.

If the feasible region is non-empty, closed, and convex, and the objective function is linear, then any maximum value of the objective function (if it exists) occurs at a corner point of the feasible region.

This means there is no need to check every point in the region. Checking only the corner points is enough.

Inside a convex region, for any interior point there are nearby points that give slightly higher or lower values of \(Z\). A true maximum cannot stay strictly inside unless the entire boundary gives the same value.

Therefore, the search naturally moves to the boundary, and finally to the corner points where boundary lines meet. That is why the usual method is:

1. Find all corner points of the feasible region.
2. Compute \(Z\) at each of them.
3. Pick the corner point where \(Z\) is largest.

If the feasible region is bounded (completely enclosed and finite) and non-empty, then a linear objective function will have both a maximum and a minimum value on that region.

In this case, the procedure is straightforward: find all corner points and select the one where \(Z\) is largest.

If the feasible region is unbounded, the situation is more delicate. The region may extend infinitely in some directions. In such a case:

• Sometimes the maximum still exists if \(Z\) does not increase along the unbounded directions.
• Sometimes there is no maximum because \(Z\) can increase without limit along some path in the region.

So for unbounded regions, even after checking corner points, it is necessary to be sure that \(Z\) cannot be made arbitrarily large while staying feasible.

Suppose there are two activities represented by \(x\) and \(y\). The aim is to maximize:

\( Z = 5x + 4y \)

Subject to the constraints:

• \( x + y \le 6 \)
• \( x \le 4 \)
• \( x \ge 0, \; y \ge 0 \)

All these constraints together create a feasible region in the first quadrant.

The corner points of the feasible region can be found by intersecting boundary lines:

• Point A: \((0, 0)\)
• Point B: \((4, 0)\) from \(x = 4, y = 0\)
• Point C: intersection of \(x = 4\) and \(x + y = 6\), giving \((4, 2)\)
• Point D: intersection of \(x + y = 6\) with \(x = 0\), giving \((0, 6)\)

Now compute \(Z\) at each corner point:

• At A: \(Z = 5(0) + 4(0) = 0\)
• At B: \(Z = 5(4) + 4(0) = 20\)
• At C: \(Z = 5(4) + 4(2) = 20 + 8 = 28\)
• At D: \(Z = 5(0) + 4(6) = 24\)

The largest value is \(Z = 28\) at the point \((4, 2)\). So the maximum of \(Z\) occurs at this corner point.

This small example shows the usual pattern: find the feasible region, list the corner points, and evaluate \(Z\) at each one to locate the maximum.