Formulating Linear Programs in Standard Form

1. From Problem to Program: An Example

A linear program is a method for finding the best outcome (like maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Every LP has three core components:

• Decision Variables: The quantities you have control over and need to determine.
• Objective Function: A linear function of the variables that you want to maximize or minimize.
• Constraints: A set of linear inequalities or equalities that limit the values of your decision variables.

The best way to understand this is through an example. The following video provides an excellent walkthrough of formulating a political campaign problem as a linear program.

Let's recap the structure of the LP from the video.

• Problem: Win an election by securing a majority of votes in three different demographics, while minimizing total advertising spending.
• Decision Variables: The money spent on each of four campaign issues. Let's call them $x_1,x_2,x_3,x_4$. These are the values the campaign manager needs to decide.
• Objective Function: The goal is to minimize total spending. This is a simple linear function:
  $\text{Minimize }Z=x_1+x_2+x_3+x_4$
• Constraints:
  1. The spending must generate enough votes in each demographic. This gives us three "greater-than-or-equal-to" constraints, one for each demographic (urban, suburban, rural). For example, for the urban demographic:
     $-2x_1+8x_2+0x_3+10x_4\ge 50,000$
  2. The spending cannot be negative. This gives the non-negativity constraints:
     $x_1,x_2,x_3,x_4\ge 0$

This is a complete formulation of the problem as a linear program. The key takeaway is the process: identify what you can control (variables), what your goal is (objective), and what your limitations are (constraints).

2. The Standard Form of a Linear Program

The LP we just created is perfectly valid, but it's one of many possible structures. You can have minimization or maximization objectives, and constraints can be of the type $\le$, $\ge$, or $=$. To develop consistent theory and algorithms (like the Simplex method or duality proofs), it's useful to agree on a single, uniform structure called standard form.

While definitions of "standard form" can vary slightly between different fields, we will adopt the one commonly used in theoretical computer science and game theory.

As specified in the reading, our standard form is defined as follows:

1. Objective: The objective function must be a maximization.
2. Constraints: All functional constraints must be of the less-than-or-equal-to ($\le$) type.
3. Variables: All decision variables must be non-negative ($\ge 0$).

In matrix notation, this is written compactly as:

where $\mathbf{x}$ is the vector of decision variables, $\mathbf{c}$ is the vector of objective coefficients, $A$ is the matrix of constraint coefficients, and $\mathbf{b}$ is the vector of constraint bounds.

3. Converting any LP to Standard Form

The political campaign LP we formulated earlier is not in standard form because it involves a minimization objective and $\ge$ constraints. Fortunately, we can convert any LP into an equivalent one in standard form using a few simple algebraic rules.

The lecturer in the MIT video you watched earlier briefly mentions this. Let's formalize the conversion process.

Rule 1: Handling Minimization Objectives
A minimization problem can be converted to a maximization problem by negating the objective function. The optimal solution ${\mathbf{x}}^{\ast }$ remains the same.
$\min {\mathbf{c}}^T\mathbf{x}⟺\max (-{\mathbf{c}}^T\mathbf{x})$
For the campaign example, Minimize Z = x_1 + x_2 + x_3 + x_4 becomes Maximize Z' = -x_1 - x_2 - x_3 - x_4.

Rule 2: Handling Constraint Types

• A "greater-than-or-equal-to" constraint can be converted to $\le$ by multiplying the entire inequality by -1.
  ${\mathbf{a}}_i^T\mathbf{x}\ge b_i⟺-{\mathbf{a}}_i^T\mathbf{x}\le -b_i$
  The urban demographic constraint −2x_1 + 8x_2 + 10x_4 ≥ 50,000 becomes 2x_1 - 8x_2 - 10x_4 ≤ -50,000.

• An equality constraint can be replaced by two opposing inequalities.
  ${\mathbf{a}}_i^T\mathbf{x}=b_i⟺\{\begin{array}{l}{\mathbf{a}}_i^T\mathbf{x}\le b_i\\ {\mathbf{a}}_i^T\mathbf{x}\ge b_i\end{array}$
  The second inequality ($\ge$) would then be converted using the rule above.

Rule 3: Handling Variable Types

• Unrestricted variables: If a variable $x_i$ is "unrestricted in sign" (i.e., it can be negative), we can replace it everywhere with the difference of two new non-negative variables: $x_i=x_i^{\prime }-x_i^{\prime \prime }$, where $x_i^{\prime },x_i^{\prime \prime }\ge 0$. This trick allows any real value to be represented.
• Non-positive variables: If a variable $x_i$ must be non-positive ($x_i\le 0$), we can define a new non-negative variable $x_i^{\prime }=-x_i$ where $x_i^{\prime }\ge 0$, and substitute $-x_i^{\prime }$ for $x_i$ everywhere.

Example: Converting the Campaign LP

Let's apply these rules to convert the entire campaign LP into our standard form.

Original LP:

Conversion Steps:

1. Objective: Convert to maximization by negating the objective function.
   maximize -x_1 - x_2 - x_3 - x_4
2. Constraints: Convert all three $\ge$ constraints to $\le$ by multiplying by -1.
   • 2x_1 - 8x_2 - 0x_3 - 10x_4 ≤ -50000
   • -5x_1 - 2x_2 - 0x_3 - 0x_4 ≤ -100000
   • -3x_1 + 5x_2 - 10x_3 - 0x_4 ≤ -25000
3. Variables: The variables $x_1,x_2,x_3,x_4$ are already non-negative, so no change is needed.

Final Standard Form LP:

This LP is now perfectly aligned with our standard form and is ready for theoretical analysis, such as finding its dual, which is the topic of our next lesson.

Conclusion

In this lesson, we introduced the fundamentals of linear programming. We've learned how to dissect a problem into its core components—decision variables, objective, and constraints—and how to formalize them into a mathematical program.

Key Takeaways:

• A Linear Program (LP) consists of a linear objective function to be optimized, subject to a set of linear constraints.
• For consistency and theoretical purposes, we use a standard form: maximize objective, ≤ constraints, and non-negative variables.
• Any LP can be converted into standard form through a set of simple algebraic manipulations, such as negating the objective function or multiplying inequalities by -1.

Preview of the next lesson:

Now that we can formulate a problem as an LP in standard form (often called the primal program), we can explore one of the most elegant and powerful concepts in optimization: duality. In the next lesson, we will learn how to construct the dual program for any given primal LP. This relationship between a primal and its dual is the cornerstone of our eventual proof of the Minimax Theorem.