Study guide
8.2 Linear Inequalities & Linear Programming
Pakistan ECAT Engineering Colleges Admission Test
Track your progress as you read
Finished sections get a check mark.
1 Chapter 1: ECAT Exam Structure, Scoring & Strategy
1.1 ECAT Exam Pattern, Scoring Scheme & UET Merit Aggregate 1.2 Time Management, Pacing & MCQ Problem-Solving Tactics
2 Chapter 2: Mathematics — Number Systems, Sets & Algebra
2.1 Real Numbers, Sets, Logic, Binary Operations & Groups 2.2 Complex Numbers, Modulus, Conjugates & De Moivre's Theorem 2.3 Matrices, Determinants, Inverses & Systems of Linear Equations 2.4 Quadratic Equations, Relations Between Roots & Factor/Remainder Theorems
3 Chapter 3: Mathematics — Sequences, Series & Combinatorics
3.1 Arithmetic, Geometric & Harmonic Progressions (AP, GP, HP) 3.2 Permutations, Combinations & Probability Distributions 3.3 Mathematical Induction & the Binomial Theorem
4 Chapter 4: Mathematics — Trigonometry & Trigonometric Equations
4.1 Fundamental Trigonometric Identities & Angle Addition Formulas 4.2 Graphs of Trigonometric Functions & Inverse Trigonometric Functions 4.3 Solutions of Triangles (Sine/Cosine Laws) & Trigonometric Equations
5 Chapter 5: Mathematics — Functions, Limits & Continuity
5.1 Real-Valued Functions, Types, Domains & Ranges 5.2 Limits of Functions, Indeterminate Forms & Squeeze Theorem 5.3 Continuity, Types of Discontinuity & Asymptotes
6 Chapter 6: Mathematics — Differential Calculus
6.1 Definition of Derivative, Power, Product, Quotient & Chain Rules 6.2 Derivatives of Trigonometric, Exponential & Logarithmic Functions 6.3 Implicit Differentiation, Parametric Equations & Higher-Order Derivatives 6.4 Tangents, Normals, Increasing/Decreasing Functions & Extrema
7 Chapter 7: Mathematics — Integral Calculus
7.1 Indefinite Integration Formulas & Integration by Substitution 7.2 Integration by Parts & Partial Fractions 7.3 Definite Integrals, Properties & Fundamental Theorem of Calculus 7.4 Area Under Curves & First-Order Differential Equations
8 Chapter 8: Mathematics — Analytic Geometry, Linear Programming & Vectors
8.1 Coordinates, Slopes, Straight Line Equations & Distances 8.2 Linear Inequalities & Linear Programming 8.3 Circle Equations, Tangents, Normals & Intersections 8.4 Conic Sections: Parabola, Ellipse & Hyperbola Characteristics 8.5 Vectors in 2D and 3D, Dot Product, Cross Product & Scalar Triple Product
9 Chapter 9: Physics — Measurements, Vectors & Equilibrium
9.1 Physical Quantities, SI Units, Errors & Dimensional Analysis 9.2 Vector Addition, Components, Scalar & Vector Products in Physics 9.3 Equilibrium Conditions, Torque & Rotational Equilibrium
10 Chapter 10: Physics — Kinematics, Dynamics & Energy
10.1 Kinematics: Displacement, Velocity, Acceleration & Motion Equations 10.2 Newton's Laws of Motion, Momentum, Impulse & Elastic Collisions 10.3 Projectile Motion: Trajectory, Height, Flight Time & Range 10.4 Work, Energy, Work-Energy Theorem, Conservative Forces & Power
11 Chapter 11: Physics — Circular Motion, Gravitation, Fluids & Oscillations
11.1 Uniform Circular Motion, Centripetal Force & Moment of Inertia 11.2 Gravitation, Escape Velocity, Satellites & Weightlessness 11.3 Viscosity, Drag Force, Equation of Continuity & Bernoulli's Principle 11.4 Simple Harmonic Motion (SHM), Pendulum, Mass-Spring & Resonance
12 Chapter 12: Physics — Waves, Optics, Optical Instruments & Thermodynamics
12.1 Waves, Speed of Sound, Standing Waves & Doppler Effect 12.2 Wave Theory of Light, Interference & Young's Double-Slit Experiment 12.3 Diffraction Grating, Resolving Power & Polarization of Light 12.4 Optical Instruments: Magnifiers, Microscopes, Telescopes, Spectrometer & Fibre Optics 12.5 Kinetic Theory of Gases, First Law, Heat Engines & Carnot Cycle
13 Chapter 13: Physics — Electrostatics, Current Electricity & Electromagnetism
13.1 Coulomb's Law, Electric Fields, Gauss's Law & Capacitors 13.2 Electric Current, Resistance, Ohm's Law, Kirchhoff's Rules & Potentiometer 13.3 Magnetic Fields, Ampere's Law, Faraday's Law, Lenz's Law & Transformers
14 Chapter 14: Physics — Alternating Current, Physics of Solids & Electronics
14.1 Alternating Current: RMS Values, Reactance, Impedance, Resonance & Power 14.2 Physics of Solids: Elasticity, Band Theory, Superconductors & Magnetic Materials 14.3 Electronics: p-n Junction, Rectifiers, Transistors, Op-Amps & Logic Gates
15 Chapter 15: Physics — Modern, Atomic & Nuclear Physics
15.1 Special Relativity, Mass–Energy Equivalence, Pair Production & Annihilation 15.2 Photoelectric Effect, Photons, Atomic Spectra, X-Rays & Nuclear Reactions 15.3 Lasers, Nuclear Reactors, Radiation Detectors, Dosimetry & Elementary Particles
16 Chapter 16: Chemistry — Basic Concepts, Atomic Structure, Bonding & States of Matter
16.1 Mole Concept, Stoichiometry, Limiting Reactants, Isotopes & Experimental Techniques 16.2 Atomic Structure, Bohr's Model, Quantum Numbers & Electronic Configurations 16.3 Chemical Bonding: Ionic, Covalent & Coordinate Bonds, VSEPR, Hybridization & MOT 16.4 Gas Laws, Ideal Gas Equation, Kinetic Molecular Theory & Real Gases 16.5 Liquids, Intermolecular Forces, Hydrogen Bonding & Crystal Lattices
17 Chapter 17: Chemistry — Energetics, Equilibrium & Kinetics
17.1 Enthalpy Changes, Calorimetry, Hess's Law & Born-Haber Cycle 17.2 Reversible Reactions, Equilibrium Constants (Kc, Kp), Le Chatelier & Ksp 17.3 Solutions, Concentration Units, Colligative Properties & Raoult's Law 17.4 Reaction Rates, Rate Equations, Order of Reaction & Activation Energy
18 Chapter 18: Chemistry — Periodic Trends, s-, p- & d-Block Elements & Electrochemistry
18.1 Periodic Trends: Atomic Radii, Ionization Energies & Electronegativities 18.2 Chemistry of s-Block and p-Block Elements (Groups I, II, III, IV, VII) 18.3 Groups V-A & VI-A: Nitrogen, Phosphorus, Oxygen & Sulphur Compounds 18.4 Transition Elements: Electronic Configurations, Complexes & Colors 18.5 Oxidation Numbers, Electrochemical Cells, Standard Potentials & Batteries
19 Chapter 19: Chemistry — Organic Chemistry & Reaction Mechanisms
19.1 Organic Functional Groups, IUPAC Nomenclature & Structural/Stereoisomerism 19.2 Aliphatic Hydrocarbons: Alkanes, Alkenes, Alkynes & Addition Reactions 19.3 Benzene: Electronic Structure, Resonance Stability & Electrophilic Substitution 19.4 Alkyl Halides (SN1/SN2), Grignard Reagents & Functional-Group Tests 19.5 Alcohols, Phenols & Ethers: Preparation and Reactions 19.6 Aldehydes, Ketones, Carboxylic Acids, Acid Derivatives & Amino Acids
20 Chapter 20: Chemistry — Macromolecules, Chemical Industries & Environment
20.1 Macromolecules: Polymers, Carbohydrates, Proteins, Lipids, Enzymes & Nucleic Acids 20.2 Chemical Industries in Pakistan & Environmental Chemistry
21 Chapter 21: English — Reading Comprehension, Vocabulary & Grammar
21.1 Reading Comprehension Strategies, Main Ideas, Inferences & Tone 21.2 Academic Vocabulary, Context Clues, Synonyms & Antonyms 21.3 Subject-Verb Agreement, Tenses & Grammatical Concord 21.4 Sentence Correction, Parallelism, Modifiers & Prepositions
8.2 Linear Inequalities & Linear Programming
Key Takeaways Explain This Topic AI
A linear inequality a x + b y ≤ c ax + by \le c a x + b y ≤ c represents a half-plane: draw the boundary line a x + b y = c ax + by = c a x + b y = c (solid for ≤ \le ≤ or ≥ \ge ≥ , dashed for < < < or > > > ) and test a point such as the origin to choose the side.
The feasible region of a system of linear inequalities is the intersection of their half-planes; when it is bounded it is a convex polygon whose corners are found by solving pairs of boundary equations.
The corner-point theorem: if a linear objective function z = p x + q y z = px + qy z = p x + q y has a maximum or minimum on a bounded feasible region, it occurs at a vertex of that region.
Formulating a linear programming problem means naming the decision variables, writing the constraints (including x ≥ 0 x \ge 0 x ≥ 0 , y ≥ 0 y \ge 0 y ≥ 0 ), and writing the objective function to maximize or minimize.
If two adjacent vertices give the same optimal value, every point on the edge joining them is optimal; an unbounded region may have no maximum.
Last updated: October 2026
Linear Inequalities & Linear Programming
Linear programming is the part of analytic geometry that turns straight lines into decision-making. A manufacturer with limited labour and material, a farmer with limited land and water, or a diet planner with a cost limit all face the same question: which combination of two quantities gives the best result while respecting every constraint? The tools are the straight-line skills from Section 8.1 plus a few new rules about inequalities.
- 1. Linear Inequalities in Two Variables
- A linear inequality in x x x and y y y has one of the forms
a x + b y < c , a x + b y ≤ c , a x + b y > c , a x + b y ≥ c ax + by < c, \quad ax + by \le c, \quad ax + by > c, \quad ax + by \ge c a x + b y < c , a x + b y ≤ c , a x + b y > c , a x + b y ≥ c
Its solution set is a half-plane : all points on one side of the boundary line a x + b y = c ax + by = c a x + b y = c .
Graphing Procedure
Draw the boundary line a x + b y = c ax + by = c a x + b y = c using its intercepts. Use a solid line for ≤ \le ≤ or ≥ \ge ≥ (boundary points are included) and a dashed line for < < < or > > > (boundary excluded).
Choose a test point not on the line, usually the origin ( 0 , 0 ) (0, 0) ( 0 , 0 ) .
Substitute it into the inequality. If the statement is true, shade the side containing the test point; otherwise shade the other side.
Example: Graph 2 x + 3 y ≤ 12 2x + 3y \le 12 2 x + 3 y ≤ 12 . The boundary 2 x + 3 y = 12 2x + 3y = 12 2 x + 3 y = 12 passes through ( 6 , 0 ) (6, 0) ( 6 , 0 ) and ( 0 , 4 ) (0, 4) ( 0 , 4 ) and is drawn solid. Testing ( 0 , 0 ) (0, 0) ( 0 , 0 ) gives 0 ≤ 12 0 \le 12 0 ≤ 12 , which is true, so the half-plane containing the origin (below and to the left of the line) is the solution region.
If the line passes through the origin, use another test point such as ( 1 , 0 ) (1, 0) ( 1 , 0 ) or ( 0 , 1 ) (0, 1) ( 0 , 1 ) .
Shortcut for Standard Forms
x ≥ 0 x \ge 0 x ≥ 0 is the right half-plane including the y y y -axis; y ≥ 0 y \ge 0 y ≥ 0 is the upper half-plane including the x x x -axis. Together they give the first quadrant , the usual non-negativity constraints.
For y ≤ m x + c y \le mx + c y ≤ m x + c , shade below the line; for y ≥ m x + c y \ge mx + c y ≥ m x + c , shade above it (when the inequality is solved for y y y ).
2. Systems of Inequalities and the Feasible Region
The solution of a system of linear inequalities is the intersection of the individual half-planes. In linear programming this common region is called the feasible region , and each point in it is a feasible solution .
The feasible region is always convex : the segment joining any two of its points lies entirely inside it.
When it is bounded, it is a convex polygon. Its corners are called vertices or corner points .
Each vertex is the intersection of two boundary lines, found by solving the two equations simultaneously.
A system may also have an empty feasible region (inconsistent constraints) or an unbounded one.
Example: Find the vertices of the region defined by x ≥ 0 x \ge 0 x ≥ 0 , y ≥ 0 y \ge 0 y ≥ 0 , x + y ≤ 6 x + y \le 6 x + y ≤ 6 , x + 2 y ≤ 8 x + 2y \le 8 x + 2 y ≤ 8 .
x + y = 6 x + y = 6 x + y = 6 meets the x x x -axis at ( 6 , 0 ) (6, 0) ( 6 , 0 ) .
x + 2 y = 8 x + 2y = 8 x + 2 y = 8 meets the y y y -axis at ( 0 , 4 ) (0, 4) ( 0 , 4 ) .
x + y = 6 x + y = 6 x + y = 6 and x + 2 y = 8 x + 2y = 8 x + 2 y = 8 intersect where y = 2 y = 2 y = 2 , x = 4 x = 4 x = 4 , so at ( 4 , 2 ) (4, 2) ( 4 , 2 ) .
The feasible region is the quadrilateral with vertices ( 0 , 0 ) (0, 0) ( 0 , 0 ) , ( 6 , 0 ) (6, 0) ( 6 , 0 ) , ( 4 , 2 ) (4, 2) ( 4 , 2 ) and ( 0 , 4 ) (0, 4) ( 0 , 4 ) . Check each vertex against every constraint: for example, ( 6 , 0 ) (6, 0) ( 6 , 0 ) gives 6 + 0 = 6 ≤ 8 6 + 0 = 6 \le 8 6 + 0 = 6 ≤ 8 in the second constraint, so it is feasible; the point ( 8 , 0 ) (8, 0) ( 8 , 0 ) , where x + 2 y = 8 x + 2y = 8 x + 2 y = 8 meets the x x x -axis, violates x + y ≤ 6 x + y \le 6 x + y ≤ 6 and is not a vertex.
- 3. Linear Programming: Objective Function and Corner-Point Theorem
- A linear programming problem asks for the maximum or minimum of a linear objective function
- z = p x + q y z = px + qy z = p x + q y
subject to linear constraints. The key result is:
Corner-Point Theorem: If the feasible region is bounded, the objective function attains both its maximum and its minimum at vertices of the region.
The reason is geometric: the lines p x + q y = k px + qy = k p x + q y = k for different k k k are parallel. Sliding such a line across the region, the last point it touches is always a corner (or a whole edge).
Corner-Point Method
Graph the constraints and identify the feasible region.
Find the coordinates of every vertex.
Evaluate z z z at each vertex.
The largest value is the maximum; the smallest is the minimum.
Continuing the example , maximize z = 3 x + 4 y z = 3x + 4y z = 3 x + 4 y over the region above:
- Vertex z = 3 x + 4 y z = 3x + 4y z = 3 x + 4 y
- ( 0 , 0 ) (0, 0) ( 0 , 0 ) 0 0 0
- ( 6 , 0 ) (6, 0) ( 6 , 0 ) 18 18 18
- ( 4 , 2 ) (4, 2) ( 4 , 2 ) 12 + 8 = 20 12 + 8 = 20 12 + 8 = 20
- ( 0 , 4 ) (0, 4) ( 0 , 4 ) 16 16 16
The maximum is z = 20 z = 20 z = 20 at ( 4 , 2 ) (4, 2) ( 4 , 2 ) ; the minimum is z = 0 z = 0 z = 0 at ( 0 , 0 ) (0, 0) ( 0 , 0 ) .
Special Cases
Multiple optima: if the objective line is parallel to an edge, both endpoints of that edge give the same optimal value, and so does every point between them. For z = x + y z = x + y z = x + y in the example, ( 6 , 0 ) (6, 0) ( 6 , 0 ) and ( 4 , 2 ) (4, 2) ( 4 , 2 ) both give z = 6 z = 6 z = 6 .
Unbounded region: a minimum may still exist (common in cost problems with ≥ \ge ≥ constraints), but a maximum may not. Check whether z z z can increase without limit along an unbounded edge.
4. Formulating a Linear Programming Problem
Word problems are converted into mathematics in four steps:
Decision variables: let x x x and y y y be the quantities to be decided.
Constraints: translate each resource limit into an inequality.
Non-negativity: add x ≥ 0 x \ge 0 x ≥ 0 and y ≥ 0 y \ge 0 y ≥ 0 .
Objective: write the quantity to maximize (profit, output) or minimize (cost, time).
Worked example: A workshop makes chairs and tables. A chair needs 2 hours of carpentry and 1 hour of polishing; a table needs 3 hours of carpentry and 3 hours of polishing. Each week 36 carpentry hours and 24 polishing hours are available. Profit is Rs. 500 per chair and Rs. 900 per table. How many of each should be made?
Variables: x x x chairs, y y y tables.
Constraints: 2 x + 3 y ≤ 36 2x + 3y \le 36 2 x + 3 y ≤ 36 (carpentry), x + 3 y ≤ 24 x + 3y \le 24 x + 3 y ≤ 24 (polishing), x ≥ 0 x \ge 0 x ≥ 0 , y ≥ 0 y \ge 0 y ≥ 0 .
Objective: maximize P = 500 x + 900 y P = 500x + 900y P = 500 x + 900 y .
Vertices: ( 0 , 0 ) (0, 0) ( 0 , 0 ) ; ( 18 , 0 ) (18, 0) ( 18 , 0 ) from 2 x = 36 2x = 36 2 x = 36 ; ( 0 , 8 ) (0, 8) ( 0 , 8 ) from 3 y = 24 3y = 24 3 y = 24 ; and the intersection of 2 x + 3 y = 36 2x + 3y = 36 2 x + 3 y = 36 with x + 3 y = 24 x + 3y = 24 x + 3 y = 24 , which gives x = 12 x = 12 x = 12 , y = 4 y = 4 y = 4 .
- Vertex P = 500 x + 900 y P = 500x + 900y P = 500 x + 900 y
- ( 0 , 0 ) (0, 0) ( 0 , 0 ) Rs. 0
- ( 18 , 0 ) (18, 0) ( 18 , 0 ) Rs. 9,000
- ( 12 , 4 ) (12, 4) ( 12 , 4 ) Rs. 6,000 + 3,600 = 9,600
- ( 0 , 8 ) (0, 8) ( 0 , 8 ) Rs. 7,200
The best plan is 12 chairs and 4 tables per week, for a profit of Rs. 9,600.
5. Quick Checks for MCQs
A vertex claimed in an answer option must satisfy every constraint; substituting it takes seconds and eliminates wrong options.
The optimum is never at an interior point for a linear objective.
Changing the objective function changes which vertex is optimal, but never the feasible region itself.
A strict inequality ( < < < ) excludes the boundary, so a "maximum" may not be attained; Intermediate problems normally use ≤ \le ≤ and ≥ \ge ≥ to avoid this.