Question

Find the dual to the following primal problem: $$ \begin{aligned} \text { Maximize } \quad z &=x_{1}+1.5 x_{2} \\ \text { subject to: } \quad 2 x_{1}+3 x_{2} & \leq 25 \\ x_{1}+x_{2} & \geq 1 \\ x_{1}-2 x_{2} &=1 \\ x_{1}, x_{2} & \geq 0 \end{aligned} $$

Short answer

The dual problem to the given primal problem is: $$ \begin{aligned} \text{Minimize} \quad w &= 25y_1 - y_2 + y_3 - y_4\\ \text{subject to:} \quad 2y_1 - y_2 + y_3 - y_4 &\geq 1\\ 3y_1 - y_2 - 2y_3 + 2y_4 &\geq 1.5\\ y_1, y_2, y_3, y_4 &\geq 0 \end{aligned} $$

Step-by-step solution

Identify the primal objective function and constraints

: The primal problem is given as: Maximize: \(z = x_1 + 1.5x_2\) Subject to: 1. \(2x_1 + 3x_2 \leq 25\) 2. \(x_1 + x_2 \geq 1\) 3. \(x_1 - 2x_2 = 1\) 4. \(x_1, x_2 \geq 0\)

Write the dual problem

: In order to find the dual problem, we will need to rewrite the primal problem with its constraints in the form "\(\leq\)" or "\(\geq\)" and assign dual variables for each constraint. For constraint 1, it is already in "\(\leq\)" form. For constraint 2, multiply by -1 to obtain the equivalent "\(\leq\)" form: \(-x_1 - x_2 \leq -1\) For constraint 3, we first need to write it in "\(\leq\)" and "\(\geq\)" forms. We have: - \(x_1 - 2x_2 \leq 1\) - \(-x_1 + 2x_2 \leq -1\) For constraint 4, this one is a non-negativity constraint, so we don't need to assign dual variables for it. Now we have the primal problem in a more suitable form for finding the dual: Maximize: \(z = x_1 + 1.5x_2\) Subject to: 1. \(2x_1 + 3x_2 \leq 25\) 2. \(-x_1 - x_2 \leq -1\) 3. \(x_1 - 2x_2 \leq 1\) 4. \(-x_1 + 2x_2 \leq -1\) 5. \(x_1, x_2 \geq 0\) Now assign dual variables to the constraints (1 to 4): \(y_1, y_2, y_3, y_4\) respectively. The dual problem will have the following form: Minimize: \(w = 25y_1 - y_2 + y_3 - y_4\) Subject to: 1. \(2y_1 - y_2 + y_3 - y_4 \geq 1\) 2. \(3y_1 - y_2 - 2y_3 + 2y_4 \geq 1.5\) 3. \(y_1, y_2, y_3, y_4 \geq 0\) The dual problem is: $$ \begin{aligned} \text{Minimize} \quad w &= 25y_1 - y_2 + y_3 - y_4\\ \text{subject to:} \quad 2y_1 - y_2 + y_3 - y_4 &\geq 1\\ 3y_1 - y_2 - 2y_3 + 2y_4 &\geq 1.5\\ y_1, y_2, y_3, y_4 &\geq 0 \end{aligned} $$

Key concepts

Primal and Dual Problem

The concept of a primal and a dual in linear programming centers on having two distinct but closely related optimization problems. The primal problem in this context refers to the original problem that is attempting to maximize or minimize an objective function subject to a set of constraints. For students to understand this duality concept, let's take the exercise as an example where the objective was to maximize the function given by \( z = x_1 + 1.5x_2 \) within the constraints provided.

In linear programming, every primal problem has an associated dual problem, which is derived from the primal. The dual problem, on the other hand, looks at the inner workings of the original constraints to form a new optimization issue. Essentially, if the primal deals with the resources (inputs), the dual deals with the values (prices or costs of resources). In the given exercise's dual, the objective is to minimize \( w = 25y_1 - y_2 + y_3 - y_4 \), under a different set of constraints. It's crucial to understand that solutions of dual problems provide deep insights into the primal problems, such as the optimal allocation of resources.

Constraint Transformation

When converting a primal problem to its dual, one of the core steps is to transform the constraints accordingly. This process, known as constraint transformation, adheres to specific rules depending on the type of inequality (\( \leq, \geq, = \)) and whether we are maximizing or minimizing the objective function. For example, in our exercise, the primal problem constraints underwent transformation to a format suitable for the dual problem. The second primal constraint \( x_1 + x_2 \geq 1 \) was multiplied by -1 to flip the inequality and convert to the form \( -x_1 - x_2 \leq -1 \).

Moreover, an equation constraint in the primal is represented by two inequality constraints in the dual, as demonstrated by the split of the equation \( x_1 - 2x_2 = 1 \) into two separate inequalities. These transformations are essential for creating the structure of the dual problem whereby the dual variables can be properly assigned and related to the new dual constraints.

Objective Function

The objective function in linear programming is the function that we are trying to optimize—either to maximize or to minimize. In the primal problem, the objective function was \( z = x_1 + 1.5x_2 \) which we aimed to maximize. The coefficients of the variables \( x_1 \) and \( x_2 \) reflect the contribution of each variable to the total value of the objective function.

For the dual problem, we derive a new objective function. The terms in this function are constructed from the constants on the right-hand side of the primal constraints, revealing the constraints' influence on the dual objective. Here, the dual objective \( w = 25y_1 - y_2 + y_3 - y_4 \) seeks to minimize the costs associated with the constraints. Understanding how to formulate and interpret this objective is crucial for grasping the interplay between the primal and dual problems and how they provide insights into the value of resources in the primal problem.

Dual Variables

The dual variables play a significant role when formulating the dual problem. They can be thought of as 'shadows' of the primal constraints, representing the worth or price of these constraints in the dual problem. In the step-by-step solution provided for the exercise, each of the primal problem's constraints was paired with a corresponding dual variable: \( y_1, y_2, y_3, \) and \( y_4 \).

Each of these dual variables is associated with a particular constraint from the primal problem and carries the 'weight' of that constraint into the dual objective function. This is vividly seen in how the values 25, -1, 1, and -1 from the right-hand side of the primal constraints become the coefficients in the dual objective function. Moreover, these variables must satisfy new constraints of their own in the dual problem, which are constructed based on the coefficients from the inequalities of the primal problem. Reviewing the connections between primal constraints and dual variables deepens the understanding of the duality concept in linear programming.