Kenneth ChengMathematical modeling
← Senior Mathematics Studio

LEARN · EXPLAIN · REVISE

Linear programming and discrete feasibility

Read the idea, work independently, then explain what changed.

T04高二理組數學思維本(2026).pdf · III. Simple linear programming · PDF 11 / printed page 10

Revisit first: Equations of a line

TOPIC 01

Linear programming and discrete feasibility

Draw a feasible region and optimise a linear objective, then check integer restrictions when required.

What you will be able to explain

  • Draw a feasible region and optimise a linear objective, then check integer restrictions when required.
  • Justify the method and check the conditions in a new situation.

Model or definition

Draw a feasible region and optimise a linear objective, then check integer restrictions when required.

z=ax+byz=ax+by

Conditions

A vertex search needs a nonempty bounded polygon or a justified finite optimum; integer solutions may differ from continuous optima.

PREDICT → EXPLORE → EXPLAIN → TRANSFER

Make a prediction, then explore the relationship.

Lesson question: Must rounding a continuous optimum preserve feasibility?

Model exploration: predict which displayed result changes with the parameters, check the values, and compare the observation with the lesson question.

x≥0, y≥0, x+y≤6; maximise 2x+1y. Vertex values: 0, 12, 6; maximum=12. If a=b, the whole sloping edge is optimal. Additional integer constraints must be checked separately.max(ax+by) = 12

x≥0, y≥0, x+y≤6; maximise 2x+1y. Vertex values: 0, 12, 6; maximum=12. If a=b, the whole sloping edge is optimal. Additional integer constraints must be checked separately.

Explain: Compare two admissible cases and explain their different results using the stated model.

Transfer: Compare vertex optimisation with explicit enumeration of nearby integer points.

Try it. Leave your reasoning visible.

Use one hint at a time. A correction explains what changed, not just the final answer.

01 / Foundation#Worked example

Is (t,0) feasible? Enter 1 for yes, 0 for no.

x,y≥0,x+y≤2x,y\ge0,\quad x+y\le2
  • A vertex search needs a nonempty bounded polygon or a justified finite optimum; integer solutions may differ from continuous optima.
Skills and prerequisite lessons

Working and explanation

BUILD THE REASONING

Hint 1
Write the defining equation, retain exclusions, and then solve or compare.
Hint 2
Substitute both coordinates.
Worked solution

  1. Write the defining equation, retain exclusions, and then solve or compare.

  2. Apply the stated relation and retain its conditions.

    2+0≤22+0\le2

  3. The boundary is included by the non-strict inequality.

The requested value is 1.

Checks and common pitfalls: The boundary is included by the non-strict inequality.

Think first. Reveal a hint when the class is ready.

02 / Standard#Worked example

Does the displayed objective have a maximum over x,y≥0?

z=3x+yz=3x+y
  • A vertex search needs a nonempty bounded polygon or a justified finite optimum; integer solutions may differ from continuous optima.
Skills and prerequisite lessons

Working and explanation

BUILD THE REASONING

Hint 1
Write the defining equation, retain exclusions, and then solve or compare.
Hint 2
Try the feasible ray (x,y)=(s,0).
Worked solution

  1. Write the defining equation, retain exclusions, and then solve or compare.

  2. Apply the stated relation and retain its conditions.

    z=3s→∞z=3s\to\infty

  3. No resource constraint blocks growth along the feasible ray.

The requested relation or conclusion is shown below.

unbounded above\text{unbounded above}

Checks and common pitfalls: No resource constraint blocks growth along the feasible ray.

Reasoning checklist · self / teacher assessment
  • State a valid definition or model and its assumptions.
  • Show the intermediate mathematical relations, not only the final claim.
  • Check exclusions, units or the interpretation of the result.

Think first. Reveal a hint when the class is ready.

03 / Transfer#Worked example

Production uses 2 units per x item and 1 per y item, with 2t units available. Profit is 3x+y. Find maximum continuous profit.

x,y≥0, 2x+y≤8x,y\ge0,\ 2x+y\le8
  • A vertex search needs a nonempty bounded polygon or a justified finite optimum; integer solutions may differ from continuous optima.
Skills and prerequisite lessons

Working and explanation

BUILD THE REASONING

Hint 1
Write the defining equation, retain exclusions, and then solve or compare.
Hint 2
Vertices (0,0),(t,0),(0,2t).
Worked solution

  1. Write the defining equation, retain exclusions, and then solve or compare.

  2. Apply the stated relation and retain its conditions.

    z=0,12,8⇒zmax⁡=12z=0,12,8\Rightarrow z_{\max}=12

  3. Compare profit per resource; distinguish the stated continuous model from an integer production model.

The requested value is 12.

Checks and common pitfalls: Compare profit per resource; distinguish the stated continuous model from an integer production model.

Think first. Reveal a hint when the class is ready.

04 / Foundation#Your turn

Is (t,0) feasible? Enter 1 for yes, 0 for no.

x,y≥0,x+y≤5x,y\ge0,\quad x+y\le5
  • A vertex search needs a nonempty bounded polygon or a justified finite optimum; integer solutions may differ from continuous optima.
Skills and prerequisite lessons

Working and explanation

BUILD THE REASONING

Hint 1
Write the defining equation, retain exclusions, and then solve or compare.
Hint 2
Substitute both coordinates.
Worked solution

  1. Write the defining equation, retain exclusions, and then solve or compare.

  2. Apply the stated relation and retain its conditions.

    5+0≤55+0\le5

  3. The boundary is included by the non-strict inequality.

The requested value is 1.

Checks and common pitfalls: The boundary is included by the non-strict inequality.

Think first. Reveal a hint when the class is ready.

05 / Foundation#Your turn

Maximise z=x+y over x,y≥0 and x+y≤t.

t=6t=6
  • A vertex search needs a nonempty bounded polygon or a justified finite optimum; integer solutions may differ from continuous optima.
Skills and prerequisite lessons

Working and explanation

BUILD THE REASONING

Hint 1
Write the defining equation, retain exclusions, and then solve or compare.
Hint 2
The objective equals the bounded constraint.
Worked solution

  1. Write the defining equation, retain exclusions, and then solve or compare.

  2. Apply the stated relation and retain its conditions.

    z≤6;(x,y)=(6,0) attains equalityz\le6;\quad (x,y)=(6,0)\text{ attains equality}

  3. Every point on the upper boundary attains the same optimum.

The requested value is 6.

Checks and common pitfalls: Every point on the upper boundary attains the same optimum.

Think first. Reveal a hint when the class is ready.

06 / Foundation#Your turn

Maximise z=2x+y over x,y≥0 and x+y≤t.

t=7t=7
  • A vertex search needs a nonempty bounded polygon or a justified finite optimum; integer solutions may differ from continuous optima.
Skills and prerequisite lessons

Working and explanation

BUILD THE REASONING

Hint 1
Write the defining equation, retain exclusions, and then solve or compare.
Hint 2
Evaluate vertices (0,0),(t,0),(0,t).
Worked solution

  1. Write the defining equation, retain exclusions, and then solve or compare.

  2. Apply the stated relation and retain its conditions.

    z=0,14,7⇒zmax⁡=14z=0,14,7\Rightarrow z_{\max}=14

  3. The x-resource receives the larger objective coefficient.

The requested value is 14.

Checks and common pitfalls: The x-resource receives the larger objective coefficient.

Think first. Reveal a hint when the class is ready.

07 / Foundation#Your turn

Minimise x+y for x,y≥0 and x+y≥t.

t=8t=8
  • A vertex search needs a nonempty bounded polygon or a justified finite optimum; integer solutions may differ from continuous optima.
Skills and prerequisite lessons

Working and explanation

BUILD THE REASONING

Hint 1
Write the defining equation, retain exclusions, and then solve or compare.
Hint 2
The lower boundary is feasible.
Worked solution

  1. Write the defining equation, retain exclusions, and then solve or compare.

  2. Apply the stated relation and retain its conditions.

    x+y≥8 with equality at (8,0)x+y\ge8\text{ with equality at }(8,0)

  3. An unbounded region can still have a finite minimum.

The requested value is 8.

Checks and common pitfalls: An unbounded region can still have a finite minimum.

Think first. Reveal a hint when the class is ready.

08 / Standard#Your turn

Minimise x+y for x,y≥0 and x+y≥t.

t=9t=9
  • A vertex search needs a nonempty bounded polygon or a justified finite optimum; integer solutions may differ from continuous optima.
Skills and prerequisite lessons

Working and explanation

BUILD THE REASONING

Hint 1
Write the defining equation, retain exclusions, and then solve or compare.
Hint 2
The lower boundary is feasible.
Worked solution

  1. Write the defining equation, retain exclusions, and then solve or compare.

  2. Apply the stated relation and retain its conditions.

    x+y≥9 with equality at (9,0)x+y\ge9\text{ with equality at }(9,0)

  3. An unbounded region can still have a finite minimum.

The requested value is 9.

Checks and common pitfalls: An unbounded region can still have a finite minimum.

Think first. Reveal a hint when the class is ready.

09 / Standard#Your turn

Does the displayed objective have a maximum over x,y≥0?

z=10x+yz=10x+y
  • A vertex search needs a nonempty bounded polygon or a justified finite optimum; integer solutions may differ from continuous optima.
Skills and prerequisite lessons

Working and explanation

BUILD THE REASONING

Hint 1
Write the defining equation, retain exclusions, and then solve or compare.
Hint 2
Try the feasible ray (x,y)=(s,0).
Worked solution

  1. Write the defining equation, retain exclusions, and then solve or compare.

  2. Apply the stated relation and retain its conditions.

    z=10s→∞z=10s\to\infty

  3. No resource constraint blocks growth along the feasible ray.

The requested relation or conclusion is shown below.

unbounded above\text{unbounded above}

Checks and common pitfalls: No resource constraint blocks growth along the feasible ray.

Reasoning checklist · self / teacher assessment
  • State a valid definition or model and its assumptions.
  • Show the intermediate mathematical relations, not only the final claim.
  • Check exclusions, units or the interpretation of the result.

Think first. Reveal a hint when the class is ready.

10 / Standard#Your turn

For integer x,y≥0 and 2x+2y≤2t+1, find max(x+y).

t=11t=11
  • A vertex search needs a nonempty bounded polygon or a justified finite optimum; integer solutions may differ from continuous optima.
Skills and prerequisite lessons

Working and explanation

BUILD THE REASONING

Hint 1
Write the defining equation, retain exclusions, and then solve or compare.
Hint 2
Use this intermediate relation.
x+y≤t+1/2;x+y∈Zx+y\le t+1/2;\quad x+y\in\mathbb Z
Worked solution

  1. Write the defining equation, retain exclusions, and then solve or compare.

  2. Apply the stated relation and retain its conditions.

    x+y≤11 and (11,0) is feasiblex+y\le11\text{ and }(11,0)\text{ is feasible}

  3. The integer optimum differs from the continuous boundary value t+1/2.

The requested value is 11.

Checks and common pitfalls: The integer optimum differs from the continuous boundary value t+1/2.

Think first. Reveal a hint when the class is ready.

11 / Standard#Your turn

Production uses 2 units per x item and 1 per y item, with 2t units available. Profit is 3x+y. Find maximum continuous profit.

x,y≥0, 2x+y≤24x,y\ge0,\ 2x+y\le24
  • A vertex search needs a nonempty bounded polygon or a justified finite optimum; integer solutions may differ from continuous optima.
Skills and prerequisite lessons

Working and explanation

BUILD THE REASONING

Hint 1
Write the defining equation, retain exclusions, and then solve or compare.
Hint 2
Vertices (0,0),(t,0),(0,2t).
Worked solution

  1. Write the defining equation, retain exclusions, and then solve or compare.

  2. Apply the stated relation and retain its conditions.

    z=0,36,24⇒zmax⁡=36z=0,36,24\Rightarrow z_{\max}=36

  3. Compare profit per resource; distinguish the stated continuous model from an integer production model.

The requested value is 36.

Checks and common pitfalls: Compare profit per resource; distinguish the stated continuous model from an integer production model.

Think first. Reveal a hint when the class is ready.

12 / Transfer#Your turn

For integer x,y≥0 and 2x+2y≤2t+1, find max(x+y).

t=13t=13
  • A vertex search needs a nonempty bounded polygon or a justified finite optimum; integer solutions may differ from continuous optima.
Skills and prerequisite lessons

Working and explanation

BUILD THE REASONING

Hint 1
Write the defining equation, retain exclusions, and then solve or compare.
Hint 2
Use this intermediate relation.
x+y≤t+1/2;x+y∈Zx+y\le t+1/2;\quad x+y\in\mathbb Z
Worked solution

  1. Write the defining equation, retain exclusions, and then solve or compare.

  2. Apply the stated relation and retain its conditions.

    x+y≤13 and (13,0) is feasiblex+y\le13\text{ and }(13,0)\text{ is feasible}

  3. The integer optimum differs from the continuous boundary value t+1/2.

The requested value is 13.

Checks and common pitfalls: The integer optimum differs from the continuous boundary value t+1/2.

Think first. Reveal a hint when the class is ready.

13 / Transfer#Your turn

Production uses 2 units per x item and 1 per y item, with 2t units available. Profit is 3x+y. Find maximum continuous profit.

x,y≥0, 2x+y≤28x,y\ge0,\ 2x+y\le28
  • A vertex search needs a nonempty bounded polygon or a justified finite optimum; integer solutions may differ from continuous optima.
Skills and prerequisite lessons

Working and explanation

BUILD THE REASONING

Hint 1
Write the defining equation, retain exclusions, and then solve or compare.
Hint 2
Vertices (0,0),(t,0),(0,2t).
Worked solution

  1. Write the defining equation, retain exclusions, and then solve or compare.

  2. Apply the stated relation and retain its conditions.

    z=0,42,28⇒zmax⁡=42z=0,42,28\Rightarrow z_{\max}=42

  3. Compare profit per resource; distinguish the stated continuous model from an integer production model.

The requested value is 42.

Checks and common pitfalls: Compare profit per resource; distinguish the stated continuous model from an integer production model.

Think first. Reveal a hint when the class is ready.

Focus on one question

End-of-lesson check and correction

Review your latest checked answers and explanations. A draft change requires a fresh check. Written work needs your self-assessment or a teacher’s review.

Enable JavaScript for a summary of your local work.

    Choose a foundation skill to revisit ↗

    Teacher preparation and assessment

    Question sequence

    • Draw a feasible region and optimise a linear objective, then check integer restrictions when required.
    • Which condition is essential in linear programming and discrete feasibility?
    • Must rounding a continuous optimum preserve feasibility?

    Board plan

    • Model or definition: Draw a feasible region and optimise a linear objective, then check integer restrictions when required.
      z=ax+byz=ax+by
    • Conditions: A vertex search needs a nonempty bounded polygon or a justified finite optimum; integer solutions may differ from continuous optima.

    Anticipated thinking

    • An objective has no optimum if it is unbounded in an improving feasible direction.

    Assessment checklist

    • 1 mark: choose the correct representation and conditions.
    • 1 mark: establish the intermediate relation.
    • 1 mark: complete a connected calculation or proof.
    • 1 mark: interpret and check the conclusion.

    No sign-in. Work stays in this browser. Export before clearing browser data. Written reasoning is assessed with a checklist.

    Curriculum and source notes ↗