Matrix form of lp problems
Matrix Form of LP Problems
Matrix form writes a linear program compactly using vectors and matrices.
It is essential for standard form, basic feasible solutions, and simplex.
Scalar Form
A linear program can be written as:
\[\min c_1x_1+c_2x_2+\cdots+c_nx_n\]subject to:
\[a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n \le b_1\] \[a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n \le b_2\] \[\vdots\] \[a_{m1}x_1+a_{m2}x_2+\cdots+a_{mn}x_n \le b_m\] \[x\ge 0\]Matrix Objects
Define:
\[x= \begin{bmatrix} x_1\\ x_2\\ \vdots\\ x_n \end{bmatrix}\] \[c= \begin{bmatrix} c_1\\ c_2\\ \vdots\\ c_n \end{bmatrix}\] \[b= \begin{bmatrix} b_1\\ b_2\\ \vdots\\ b_m \end{bmatrix}\]and:
\[A= \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{bmatrix}\]Then:
\[A\in\mathbb{R}^{m\times n}\] \[x,c\in\mathbb{R}^n\] \[b\in\mathbb{R}^m\]Compact LP Form
The scalar problem becomes:
\[\min c^Tx\]subject to:
\[Ax\le b\] \[x\ge 0\]For maximization:
\[\max c^Tx\]subject to:
\[Ax\le b\] \[x\ge 0\]Row Interpretation
The $i$-th row of $A$ corresponds to the $i$-th constraint.
If:
\[A_i=(a_{i1},a_{i2},\ldots,a_{in})\]then the $i$-th constraint is:
\[A_ix\le b_i\]or:
\[a_{i1}x_1+a_{i2}x_2+\cdots+a_{in}x_n\le b_i\]Column Interpretation
Let:
\[A=[A_1\ A_2\ \cdots\ A_n]\]Then:
\[Ax=x_1A_1+x_2A_2+\cdots+x_nA_n\]Each column $A_j$ describes how decision variable $x_j$ contributes to every constraint.
This column view is very important for simplex.
Example
Consider:
\[\max x_1+x_2\]subject to:
\[x_1+2x_2\le 10\] \[2x_1+x_2\le 16\] \[-x_1+x_2\le 3\] \[x_1,x_2\ge 0\]Here:
\[c= \begin{bmatrix} 1\\ 1 \end{bmatrix}\] \[A= \begin{bmatrix} 1 & 2\\ 2 & 1\\ -1 & 1 \end{bmatrix}\] \[b= \begin{bmatrix} 10\\ 16\\ 3 \end{bmatrix}\]So the problem is:
\[\max c^Tx\]subject to:
\[Ax\le b,\qquad x\ge 0\]Mixed Constraint Signs
A general LP may contain all three types:
\[Ax\le b\] \[Gx\ge h\] \[Ex=f\]For example:
\[\begin{cases} x_1+x_2\le 6\\ -2x_1+x_2\le 2\\ x_1-x_2\le 3 \end{cases}\]can be written as:
\[A= \begin{bmatrix} 1 & 1\\ -2 & 1\\ 1 & -1 \end{bmatrix}, \qquad b= \begin{bmatrix} 6\\ 2\\ 3 \end{bmatrix}\]Standard Form
The standard form used for simplex is:
\[\min c^Tx\]subject to:
\[Ax=b\] \[x\ge 0\]In this form:
- all constraints are equalities
- all variables are nonnegative
- the objective is minimization
Inequalities are converted into equalities using slack or surplus variables.
Dimension Check
For:
\[Ax=b\]the dimensions must match:
\[A\in\mathbb{R}^{m\times n}\] \[x\in\mathbb{R}^n\] \[b\in\mathbb{R}^m\]Then:
\[Ax\in\mathbb{R}^m\]so the equation is meaningful.
For:
\[c^Tx\]we need:
\[c,x\in\mathbb{R}^n\]Then:
\[c^Tx\]is a scalar.
Key Takeaway
Matrix form is the clean language of linear programming.
It turns many separate equations into one compact expression:
\[\min c^Tx\]subject to:
\[Ax=b,\qquad x\ge 0\]Exam checkpoint
For formulation questions, show variables, objective, constraints, sign restrictions, and units. Do not solve unless the question asks for a solution.