Problem 20 - Finite Mathematics and Applied Calculus

Question

$$ \begin{array}{rc} \text { Minimize } & c=2 s+2 t+3 u \\ \text { subject to } & s \quad+u \geq 100 \\ 2 s+t & \geq 50 \\ t+u \geq 50 & \\ s \geq 0, t \geq 0, u \geq 0 . \end{array} $$

Step-by-Step Solution

Answer

The minimum value of the objective function is 350, and this occurs when \(s = 0, t = 50, u = 50\).

Step 1: Introducing Slack Variables

To convert inequalities into equalities, we introduce slack variables, which represent the difference between the left-hand side and right-hand side of each constraint. Let's denote them by \(x_1, x_2, x_3\) for constraints 1, 2, and 3, respectively. Our constraints will now become: 1. \(s + u - x_1 = 100\) 2. \(2s + t - x_2 = 50\) 3. \(t + u - x_3 = 50\) Now, the objective function becomes: $$c = 2s + 2t + 3u + 0(x_1+x_2+x_3)$$

Step 2: Finding the Initial feasible solution

To find the initial feasible solution, we need to form the initial simplex tableau. For this, the coefficients of the decision variables \(s, t, u\) and slack variables \(x_1, x_2, x_3\) are put in the tableau along with the right-hand side of the constraints: $$\begin{array}{c|cccccc|c} & s&t&u & x_1& x_2 &x_3 & \\ \hline x_1 & 1 & 0& 1 & -1 & 0 & 0 & 100\\ x_2 & 2 & 1& 0 & 0 & -1 & 0 & 50\\ x_3 & 0 & 1& 1 & 0 & 0 & -1 & 50\\ \hline -Z & 2 & 2& 3 & 0 & 0 & 0 & 0\\ \end{array}$$

Step 3: Iteration 1 (Simplex method)

Now, we will use the simplex method to minimize the given objective function. First, we need to find the pivot column, which corresponds to the most negative coefficient in the row of \(-Z\). In this case, all coefficients are non-negative; therefore, we can skip iteration and directly find the solution.

Step 4: Finding the solution

Here, since there are no negative coefficients in the row of \(-Z\), the current solution is optimal, and we can find it as: \(s = 0\), \(t = 50\), \(u = 50\) Now substitute these values into the objective function: $$c = 2(0) + 2(50) + 3(50) = 200+150= 350$$ So, the minimum value of the objective function is 350, and this occurs when \(s = 0, t = 50, u = 50\).

Key Concepts

Linear Programming

Linear programming is a mathematical method used to find the best possible outcome in a given mathematical model whose requirements are represented by linear relationships. This technique is widely used in various fields such as economics, engineering, military, and transportation to maximize efficiency or minimize cost in operations.

Essentially, linear programming involves two main components – an objective function, which is the formula that needs to be minimized or maximized, and a set of constraints, which are the limitations or requirements expressed as linear inequalities or equalities. In the given exercise, the objective is to minimize the cost function, given by the equation
c = 2s + 2t + 3u, while satisfying several inequalities such as
s + u ≥ 100,
2s + t ≥ 50, and
t + u ≥ 50.

Slack Variables

Slack variables are a crucial concept in solving linear programming problems through methods like the simplex algorithm. They allow us to convert inequality constraints into equalities, which simplifies the computational process. Essentially, a slack variable is added to a less-than-or-equal-to (≤) constraint and subtracted from a greater-than-or-equal-to (≥) constraint.

For instance, in our original exercise, the constraints are expressed as inequalities, so we introduce slack variables (x_1, x_2, x_3) to turn them into equalities:

• s + u + x1 = 100 (for the first constraint),
• 2s + t + x2 = 50 (for the second constraint), and
• t + u + x3 = 50 (for the third constraint).

With these slack variables, we can proceed with the simplex method to find the optimal solution.

Feasible Solution

In linear programming, a feasible solution is any set of values for the decision variables that satisfies all of the problem's constraints. For a solution to be feasible, it must lie within the feasible region, which is the intersection of all the constraints on the graph. Importantly, these solutions must not violate any of the constraints, including the non-negativity restriction, where all variables must be zero or positive.

In the context of our exercise, a feasible solution would be a combination of the values for variables s, t, and u that meet all the given constraints and are greater than or equal to zero. Initially, the simplex tableau is set up with slack variables to identify a basic feasible solution. From there, additional iterations are performed to find the optimal feasible solution, which also minimizes or maximizes the objective function, depending on the problem's goal.

Objective Function

The objective function in a linear programming problem is a formula representing the goal that needs to be achieved, such as maximizing profit or minimizing costs. This function is subject to optimization, meaning we seek to find the values of the variables that will either make the objective function as large as possible (in maximization problems) or as small as possible (in minimization problems), within the constraints of the model.

In our given problem, the objective function is c = 2s + 2t + 3u, where s, t, u are the decision variables. The goal is to minimize c while complying with the constraints provided by the problem. The final step in the simplex method, after executing the necessary iterations, provides us with the values of these variables that minimize the objective function given the constraints.