Practice: The Matrix Form of a Linear Program

(a) Order and assembly. Variables $x_1,x_2,x_3$ are litres of products A, B, C per shift. Constraints ordered: whole milk, skimmed milk, line time, contract.

$A$ is $4\times 3$: four constraints, three variables. The program is $max{c}^{\mathsf{T}}x$ subject to $Ax\le b$, $x\ge 0$; as a minimisation, $min(-c{)}^{\mathsf{T}}x$ with the value negated on the way out.

(b) Row 3 and column 2. Row 3 is $(2,3,1)$ with $b_3=2400$:

the line-time limit in minutes per shift. Column 2 is $(0.3,0.7,3,0{)}^{\mathsf{T}}$: one litre of product B uses 0.3 L whole milk, 0.7 L skimmed, 3 minutes of line time, and appears in the contract row with coefficient zero because the contract concerns product C only.

(c) What the relation asserts. Four scalar inequalities holding simultaneously, one per row. A plan failing any single row is infeasible, whatever the others do and whatever the totals are.

(d) The contract. It is a lower bound, $x_3\ge 200$, and the form takes $\le$ rows, so it is negated on both sides to $-x_3\le -200$: the row $(0,0,-1)$ with right-hand side $-200$. Entering it as $(0,0,1)$ with $200$ would assert a ceiling of 200 litres rather than a floor, which is a different program that happens to parse.

A check worth doing. Take $x=(500,200,300{)}^{\mathsf{T}}$. Then $Ax=(0.6(500)+0.3(200)+0.5(300),0.4(500)+0.7(200)+0.5(300),2(500)+3(200)+300,-300{)}^{\mathsf{T}}=(510,490,1900,-300{)}^{\mathsf{T}}$, and every entry is at most the corresponding entry of $b$, so the plan is feasible. Contribution is $0.45(500)+0.30(200)+0.38(300)=225+60+114=399$.

(a) Row reading. Row 2 is $(1,2,2)$ with $b_2=90$: the plan uses $x_1+2x_2+2x_3$ labour hours, and at most 90 are available.

(b) Column reading. Column 1 is $(2,1,4{)}^{\mathsf{T}}$: one unit of product 1 consumes 2 machine hours, 1 labour hour and 4 kg of material. It is that product's resource profile across all three constraints.

(c) Both evaluations. By rows:

By columns:

The same vector, because the two are groupings of one set of nine multiplications.

(d) Which reading answers which question. The second colleague asks about a specific plan, which is a row question: form $Ax$ and compare entrywise with $b$. The first asks what combinations the resources permit, which is a column question: the reachable totals are the combinations $x_1{A}_1+x_2{A}_2+x_3{A}_3$ with $x\ge 0$, and the constraint is that this combination stay under $b$.

The other reading does not answer each question because of what it hides. A row mixes all three products into one number, so it cannot isolate what one product contributes. A single column says nothing about whether a plan is allowed, because feasibility depends on every constraint at once and a column is one activity across all of them.

Fault 1: the third constraint has the wrong direction. The description sets a floor, $x_1+x_2+x_3\ge 20$. Entered as row $(1,1,1)$ with $b_3=20$ under $Ax\le b$, it asserts a ceiling of 20 units. The feasible set is now bounded where the description bounded it below, and plans meeting the requirement are excluded. Correct it by negating both sides: row $(-1,-1,-1)$ with right-hand side $-20$.

Fault 2: the feasibility claim uses the wrong relation. $Ax\le b$ is three scalar inequalities holding at once, not a comparison of totals. At $x=(0,0,45{)}^{\mathsf{T}}$,

Row 1 gives , so the point is infeasible on the machine-hours constraint. The totals happen to compare the other way, $405$ against $390$, but that comparison decides nothing either way.

What is correct. The first two rows and their right-hand sides match the description, and the column order is consistent across rows: column 3 is $(3,5,1{)}^{\mathsf{T}}$, which is product 3's profile as stated.

The general lesson. Both faults produce a well-formed object. Nothing in the arithmetic reports them; translating each row back into the sentence it came from reports the first, and reading the relation entrywise reports the second.