Lesson 21 Lecture Notes

21.0.1 Sketching the Feasible Region

To solve a linear programming problem involving maximization, start by identifying the feasible region — the set of all possible solutions that satisfy the constraints.

21.0.1.1 Steps:

  1. Define the variables.
    • Assign \(x\), \(y\), etc., to represent the quantities in the problem.
  2. Write the system of inequalities.
    • These represent the constraints.
  3. Graph each inequality:
    • Convert to an equation to graph the boundary.
    • Use a solid line for \(\leq\) or \(\geq\), dashed for \(<\) or \(>\).
    • Shade the correct side of each line.
  4. Identify the feasible region:
    • The region where all shaded areas overlap.
    • It must also satisfy non-negativity constraints (e.g., \(x \ge 0\), \(y \ge 0\)).
  5. Label the corner (vertex) points of the feasible region.
    • These are typically found at the intersections of constraint lines.

21.0.2 Maximizing the Objective Function

Once the feasible region is identified and corner points are known, the objective function can be evaluated.

21.0.2.1 Steps:

  1. Write the objective function:

    • Usually in the form \(P = ax + by\), where \(a\), \(b\) are constants.

  2. Plug each corner point into the objective function to calculate \(P\).

  3. Compare the results:

    • The largest value is the maximum.
    • The smallest value is the minimum, if needed.

  4. State the optimal solution:

    • Report both the point \((x, y)\) and the maximum value \(P\).

21.1 Example

Maximize \(P = 3x + 5y\), subject to:

\[ \begin{align*} x + y &\le 4 \\ x &\le 2 \\ y &\le 3 \\ x, y &\ge 0 \end{align*} \]

Feasible Region:
- Graph constraints and find the overlapping area.

Corner Points:
- \((0,0), (0,3), (1,3), (2,2), (2,0)\)

Evaluate \(P\): - \(P(0,0) = 0\) - \(P(0,3) = 15\) - \(P(1,3) = 18\) - \(P(2,2) = 16\) - \(P(2,0) = 6\)

Maximum:
- At \((1,3)\), maximum \(P = 18\)

21.2 Practice Problems

Practice the techniques discussed in class and in the online videos by solving the following examples.

  1. Maximize: \[ \begin{aligned} \text{Maximize} \quad & Z = 40x_1 + 30x_2 \\ \text{Subject to:} \quad & x_1 + x_2 \leq 12 \\ & 2x_1 + x_2 \leq 16 \\ & x_1 \geq 0, \quad x_2 \geq 0 \end{aligned} \]

  2. Maximize: \[ \begin{aligned} Z &= 3x_1 + 2x_2 \\ \text{s.t.} \quad & 3x_1 + 2x_2 \leq 14 \\ & -x_1 + 2x_2 \leq 4 \\ & x_1 - x_2 \leq 3 \\ & x_1, x_2 \geq 0 \end{aligned} \]

  3. Maximize: \[ \begin{aligned} Z &= 3x_1 + 2x_2 \\ \text{s.t.} \quad & x_1 + x_2 \leq 4 \\ & x_1 - x_2 \leq 2 \\ & x_1 \leq 4,\quad x_2 \leq 4 \\ & x_1, x_2 \geq 0 \end{aligned} \]

  4. Maximize: \[ \begin{aligned} Z &= 5x_1 + 4x_2 \\ \text{s.t.} \quad & x_1 + 3x_2 \leq 18 \\ & x_1 + x_2 \leq 8 \\ & 2x_1 + x_2 \leq 14 \\ & x_1, x_2 \geq 0 \end{aligned} \]

  5. Maximize: \[ \begin{aligned} Z &= 5x_1 + 2x_2 \\ \text{s.t.} \quad & x_1 + x_2 \leq 40 \\ & 4x_1 + 2x_2 \leq 32 \\ & x_1 + x_2 \leq 12 \\ & x_1 + 4x_2 \leq 36 \\ & x_1, x_2 \geq 0 \end{aligned} \]

21.3 Self Assessment

Time yourself and try to solve the following within 20 minutes:

  1. Maximize: \[ \begin{aligned} Z &= 2x_1 + x_2 \\ \text{s.t.} \quad & x_1 + x_2 \leq 40 \\ & 3x_1 + x_2 \leq 90 \\ & x_1 + 2x_2 \leq 60 \\ & x_1, x_2 \geq 0 \end{aligned} \]

21.4 Lesson Checklist

This checklist is designed to help you keep track of what you need to work on. The main goal is to be aware of what you need to focus more attention on. Place an \(X\) in the appropriate box beside the skill below.

\[\begin{align*} &\textbf{Developing (D):} &&\textrm{You still need to work on this skill.}\\ &\textbf{Consistent (CON):} &&\textrm{You use the skill correctly most of the time.}\\ &\textbf{Competent (COM):} &&\textrm{You show mastery of the skill.} \end{align*}\]

Skill D CON COM
Sketch the feasible region of a linear programming problem.
Maximize a given objective function using appropriate corner points.