Linear Programming · Lesson 1 of 4

Modeling Decisions with Linear Programming

“Turn a choice about limited resources into variables, constraints, and a quantity to optimise.”

Learning Objectives

• Explain how linear programming selects a best feasible plan. • Choose decision variables and state their meanings and units. • Translate limits into linear constraints and non-negative restrictions. • Build and interpret a linear objective function. • Check a proposed plan against every restriction.

Choosing a best plan

A shopkeeper may have enough money for several different combinations of goods, but some combinations use too much space and others earn less profit. Mathematics can organise these choices. We first describe which plans are allowed, then identify which allowed plan best meets the goal.

Consider a dealer who buys tables and chairs. A table costs ₹2,500 and earns ₹250 profit; a chair costs ₹500 and earns ₹75 profit. The dealer has ₹50,000 to invest and room for at most 60 items. Assume every purchased item can be sold, so the profit estimates apply to all items bought.

Definition

Optimisation

Optimisation means finding a maximum or a minimum: the largest profit, the smallest cost, or the least use of a resource among the choices that satisfy the stated conditions.

Having a goal is not enough to determine the answer. Buying more goods may increase profit, but the money and storage limits prevent unlimited purchases. These competing requirements are the reason we need a model rather than a single multiplication.

Example — Compare three buying plans

Problem
Compare buying only tables, buying only chairs, and buying 10 tables with 50 chairs.

1.Only tables: the money permits $50000/2500 = 20$ tables. These fit in storage, and the profit is $20 (250) = 5000$ rupees.
2.Only chairs: the money permits $50000/500 = 100$ chairs, but only 60 can be stored. The allowed purchase is therefore 60 chairs, earning $60 (75) = 4500$ rupees.
3.A mixed purchase of 10 tables and 50 chairs costs $10 (2500) + 50 (500) = 50000$ rupees and occupies $10 + 50 = 60$ spaces.
4.Its profit is $10 (250) + 50 (75) = 6250$ rupees. It beats both single-item plans, but comparing three plans alone does not prove that it is the best of all allowed plans.

Plan	Investment	Items stored	Profit
20 tables, no chairs	₹50,000	20	₹5,000
No tables, 60 chairs	₹30,000	60	₹4,500
10 tables, 50 chairs	₹50,000	60	₹6,250

Variables and restrictions

A mathematical model gives a name to each choice and turns every limit into a statement that can be checked. Define the variables before writing equations; otherwise a correct-looking expression can describe the wrong quantities.

Definition

Decision variables

Decision variables represent the quantities whose values we are free to choose. Here $x$ is the number of tables and $y$ is the number of chairs bought.

The total investment is the cost of the tables plus the cost of the chairs. The phrase “at most” allows spending the whole budget or less, so its inequality points towards the upper limit. The storage condition counts items, not rupees.

Investment and storage constraintsLaTeX

2500 x + 500 y \leq 50000, x + y \leq 60

The first expression measures rupees; the second counts pieces of furniture. Dividing the investment inequality by the positive number 500 gives the equivalent restriction below.

Simplified investment constraintLaTeX

5 x + y \leq 100

Dividing every term by a positive number preserves the direction of the inequality.

Negative purchases have no meaning in this situation. We therefore include restrictions that keep both variables non-negative. A value of zero is allowed: the dealer may choose not to buy one type of item.

Non-negative restrictionsLaTeX

x \geq 0, y \geq 0

These restrictions place the graphical model in the first quadrant, including its axes.

Definition

Constraints

Constraints are the equations, inequalities, or other stated restrictions that a decision must satisfy. A plan is allowed only when every constraint holds simultaneously.

Example — Translate a resource condition

Problem
A workshop has 24 hours available. Each table requires 3 hours and each chair requires 1 hour. Write the time restriction using the same decision variables.

1.The time spent on $x$ tables is $3 x$ hours. The time spent on $y$ chairs is $y$ hours.
2.The combined time is therefore $3 x + y$ hours. Available time is an upper limit, so the restriction is $3 x + y \leq 24$ .
3.The coefficients refer to time per item. This is a separate workshop situation; it is not an extra condition to add to the dealer's original model.

The quantity to optimise

The constraints describe what is possible. A different expression describes what we want to improve. For the dealer, profit depends on the number of each item bought, with each item contributing its stated profit independently.

Definition

Linear objective function

A linear objective function has the form $Z = a x + b y$ , where $a$ and $b$ are fixed coefficients. The task states whether its value is to be maximised or minimised.

The dealer’s profitLaTeX

Z = 250 x + 75 y

Here

Z

is profit in rupees,

x

counts tables, and

y

counts chairs. The coefficients are profit per item, not purchase cost.

Example — Write the complete model

Problem
Formulate the dealer's problem as a linear programming problem.

1.Choose $x$ tables and $y$ chairs as the decision variables.
2.Maximise the profit $Z = 250 x + 75 y$ . The word “maximise” is part of the model because it states the direction of the goal.
3.Impose $5 x + y \leq 100$ for investment and $x + y \leq 60$ for storage.
4.Include $x \geq 0$ and $y \geq 0$ . All four restrictions must hold together; satisfying the budget alone is insufficient.

Definition

Linear programming problem

A linear programming problem seeks the maximum or minimum of a linear objective function subject to linear constraints and the stated restrictions on its variables. “Programming” here means planning a course of action.

Linearity means that contributions add in fixed proportions. For example, doubling the number of tables doubles their cost and their contribution to profit. Expressions such as $x y$ or $x^{2}$ do not have this form and are not part of the linear models studied here.

Counting items and drawing regions

Furniture counts must ultimately be whole numbers. The graphical method first studies the continuous region described by the inequalities. In this example its optimal point has whole-number coordinates, so it directly gives a valid purchase. Do not round an arbitrary graphical answer and assume that the rounded plan is feasible or optimal.

Checking a proposed decision

Before asking whether a plan is best, check whether it is allowed. Substitute the proposed values into each restriction separately. A single failed condition is enough to reject a plan.

Example — An affordable plan can still fail

Problem
Is buying 5 tables and 60 chairs permitted? Is buying 25 tables and 40 chairs permitted?

1.For $(5, 60)$ , the simplified investment total is $5 (5) + 60 = 85 \leq 100$ . It costs ₹42,500, so it fits the budget.
2.However, it requires $5 + 60 = 65$ storage spaces, exceeding 60. The plan is not allowed.
3.For $(25, 40)$ , the investment total is $5 (25) + 40 = 165 > 100$ and the item count is $25 + 40 = 65 > 60$ . This plan fails both limits.
4.Always test all restrictions rather than guessing from one quantity or from the appearance of a plan.

Cost and profit use different coefficients

The budget uses ₹2,500 per table and ₹500 per chair. The objective uses ₹250 and ₹75. Reusing purchase prices as profit coefficients would solve a different problem.

Planning beyond a shop

Linear programming became especially useful for organising scarce resources during the twentieth century. Kantorovich and Hitchcock worked on allocation and transportation problems; Stigler studied a minimum-cost diet problem. Dantzig introduced the simplex method in 1947, extending solution methods beyond two-variable graphs. Kantorovich and Koopmans received the 1975 economics Nobel Prize for work on optimal resource allocation. Computers now make much larger models practical in industry, commerce, and management.

Quick check

In the dealer’s model, what does the variable $y$ represent?

Quick check

Which condition expresses “at most 60 items” when $x$ and $y$ count the two items?

Quick check

Which is the dealer’s objective function?

Quick check

Why does the chairs-only plan contain 60 chairs rather than 100?

Quick check

Which proposed plan satisfies both $5 x + y \leq 100$ and $x + y \leq 60$ , with $x, y \geq 0$ ?

Practice Problems

Explain the difference between a decision variable, a constraint, and an objective function using the furniture dealer.
Calculate the cost, storage use, and profit for 12 tables and 35 chairs. Is this plan allowed?
A dealer proposes 15 tables and 30 chairs. Identify every restriction it satisfies or violates.
Write a linear inequality for 4 hours per item of type A and 2 hours per item of type B when at least 20 hours of work must be completed. Define your variables.
A product earns ₹40 profit and another earns ₹25 profit. Write the profit objective and explain why maximising sales revenue is not automatically the same task.
Create a two-variable planning situation with one resource limit. State the variables, units, goal, and non-negative restrictions.

Key Takeaways

Decision variables describe the choices; constraints describe allowed plans. An objective function measures the quantity to maximise or minimise. Translate words and units carefully, and include every restriction. A plan must be feasible before its profit or cost can be considered optimal.

Start of chapter

Next · Lesson 2

Feasible Regions and Corner-Point Solutions

Choosing a best plan

Variables and restrictions

The quantity to optimise

Checking a proposed decision

Quiz

Practice Problems

Key Takeaways