FlashcardU

Formulating a Linear Program

Formulating a linear program means turning a described decision problem into decision variables, a linear objective, and linear constraints. The hard part is not the algebra but the choices: what exactly is being decided, in what units, and which stated conditions are genuine restrictions rather than commentary.

Definition

A linear program consists of decision variables x 1 , … , x n , a linear objective c T x to be maximized or minimized, and finitely many linear constraints a i T x ≤ b i , a i T x ≥ b i , or a i T x = b i , together with any sign restrictions on the variables. Formulating one means choosing the variables and writing the objective and constraints so that the feasible points correspond exactly to the admissible decisions described.

Formal statement

max or min c T x subject to A x ≶ b and stated sign restrictions, where each row of A encodes one constraint and x is the vector of decision variables.

Assumptions and scope

  • Linearity is an assumption, not a fact about the situation. A quantity discount, a fixed set-up charge, or a product of two decisions is not linear, and forcing it into a linear program changes the problem being solved.

  • Divisibility is assumed: a linear program may return a fractional solution. If the decisions are genuinely indivisible, the correct model is an integer program.

  • Units must be consistent across a constraint. A row mixing hours with units produced is meaningless even though it is syntactically valid.

  • The objective must be a single linear expression. Two competing goals require either a weighted combination, chosen deliberately, or a different method.

Worked material

Contrast

Decision variables against quantities in the description

The most common formulation error is introducing a variable for something the description merely mentions. It produces a program that looks richer and is in fact broken.

Use the workshop problem again.

Incorrect. "Let a be units of A, b be units of B, p be the profit, and h be the machine hours used."

max p subject to p = 30 a + 20 b , h = 2 a + b , h ≤ 100 , a + b ≤ 80 , a ≤ 40 .

This is not wrong in the sense of having the wrong solutions. The defining equations pin p and h down exactly, so the feasible set projects correctly onto ( a , b ) . But two of its four variables are not decisions, and each one costs a constraint to define. The model has grown without saying anything new.

Correct.

max 30 a + 20 b subject to 2 a + b ≤ 100 , a + b ≤ 80 , a ≤ 40 , a , b ≥ 0 .

Where it becomes genuinely wrong. The same habit produces real errors when the introduced quantity is given a sign restriction it should not have, or when it is constrained twice. Writing p ≥ 0 above would silently forbid loss-making plans that the description permits. And if a learner writes both p = 30 a + 20 b and p ≤ 2000 from a stray sentence about a profit target, the program now caps profit rather than maximizing it.

The test to apply. For each proposed variable, ask: can the decision maker set this directly, without first setting something else? If the answer is no, it is determined by the real decisions, and it belongs in the objective or a constraint expression rather than in the variable list.

Common errors

Common misconception

Every number mentioned in the problem description should become a decision variable.

Related units

Connected

Learn this topic

Used in

Sources

Type to search.

Settings

Appearance

Interface density

Your record

Your progress is stored in this browser and nowhere else: an identifier, the answers you have given, the mastery states and review schedule derived from them, and the lesson you last opened. Clearing it makes you a new learner on this device. It cannot be undone, and it will not affect your appearance or density settings.

Focus timer

Focus--minutes remaining

Phase

Kept in this browser only, and used to label the session in your own history.

Today

Nothing recorded yet. Finish a focus session and it will appear here.

Settings

Focus sessions between long breaks.

Sessions you are aiming for in a day.

Notifications

Your history

Sessions are stored in this browser and nowhere else. They are not evidence and never reach your mastery record.