Linear Programming

AI Learning Assistant

I can help you understand Linear Programming better. Ask me anything!

Summarize the main points of Linear Programming.

What are the most important terms to remember here?

Explain this concept like I'm five.

Give me a quick 3-question practice quiz.

Summary

Chapter 12: Linear Programming

Summary

Linear programming involves optimizing a linear function subject to constraints.
Example problem: A furniture dealer wants to maximize profit from tables and chairs.
Constraints include budget and storage limitations.
The graphical method is used to find feasible solutions.
The feasible region is defined by linear inequalities.
Optimal solutions occur at corner points of the feasible region.

Key Formulas/Definitions

Objective Function: Z = ax + by (where a, b are constants)
Constraints: Linear inequalities that restrict the values of x and y.
Feasible Region: The area defined by the constraints where solutions exist.
Optimal Solution: A point in the feasible region that maximizes or minimizes the objective function.

Learning Objectives

Define linear programming and its applications.
Formulate a linear programming problem mathematically.
Graphically solve linear programming problems.
Identify feasible and infeasible solutions.
Evaluate objective functions at corner points.

Common Mistakes/Exam Tips

Ensure all constraints are correctly represented as inequalities.
Remember that optimal solutions occur at corner points, not within the interior of the feasible region.
Check for non-negativity constraints on variables.

Important Diagrams

Graph of Feasible Region: Shows the area where all constraints are satisfied.
- Axes labeled X and Y.
- Lines representing constraints intersecting at corner points.
- Shaded area indicating the feasible region.
Table of Corner Points and Values: Lists corner points with corresponding values of the objective function Z.
- Example:
  Corner Point Corresponding value of Z
  (0, 0) 0
  (30, 0) 120
  (20, 30) 110
  (0, 50) 50

Learning Objectives

Understand the concept of linear programming and its applications.
Formulate a linear programming problem mathematically.
Identify and define the objective function and constraints in a linear programming problem.
Solve linear programming problems using the graphical method.
Determine the feasible region for a linear programming problem.
Identify corner points of the feasible region and evaluate the objective function at these points.
Apply the Corner Point Method to find optimal solutions in linear programming problems.
Recognize the significance of bounded and unbounded feasible regions in linear programming.

Detailed Notes

Chapter 12: Linear Programming

12.1 Introduction

Linear programming involves optimizing a linear objective function subject to constraints.
Example: A furniture dealer wants to maximize profit from tables and chairs.
- Investment: Rs 50,000
- Storage: Maximum of 60 pieces
- Costs: Table = Rs 2500, Chair = Rs 500
- Profits: Table = Rs 250, Chair = Rs 75

12.2 Linear Programming Problem and its Mathematical Formulation

12.2.1 Mathematical Formulation

Let:
- x = number of tables
- y = number of chairs
Constraints:
1. Investment: 2500x + 500y ≤ 50000 (or 5x + y ≤ 100)
2. Storage: x + y ≤ 60
3. Non-negativity: x ≥ 0, y ≥ 0
Objective function: Z = 250x + 75y (maximize)

12.2.2 Graphical Method of Solving Linear Programming Problems

Graph the constraints:
1. 5x + y ≤ 100
2. x + y ≤ 60
3. x ≥ 0
4. y ≥ 0
Feasible Region: The area that satisfies all constraints.
Feasible Solutions: Points within or on the boundary of the feasible region.
Infeasible Solutions: Points outside the feasible region.

Important Theorems

Theorem 1: Optimal values occur at corner points of the feasible region.
Theorem 2: If the feasible region is bounded, both maximum and minimum values exist at corner points.

Example of Corner Points and Values

Corner Point	Corresponding value of Z
(0, 0)	0
(30, 0)	120 (Maximum)
(20, 30)	110
(0, 50)	50

Conclusion

Linear programming is crucial for optimizing resources in various fields such as industry and management.

Exam Tips & Common Mistakes

Common Mistakes and Exam Tips in Linear Programming

Common Pitfalls

Misunderstanding Constraints: Students often misinterpret the constraints of the problem, leading to incorrect feasible regions.
Ignoring Non-negativity: Failing to apply the non-negativity constraints (x ≥ 0, y ≥ 0) can result in infeasible solutions.
Incorrect Graphing: Errors in plotting the inequalities can lead to an incorrect feasible region.
Not Evaluating All Corner Points: Students may overlook evaluating all corner points of the feasible region, which can lead to missing the optimal solution.
Assuming Unbounded Regions: Some students may incorrectly assume that an unbounded feasible region means there is no maximum or minimum value.

Tips for Success

Double-Check Constraints: Always verify that you have correctly identified and graphed all constraints.
Use the Corner Point Method: Familiarize yourself with the Corner Point Method to systematically find the optimal solution.
Evaluate All Vertices: Make sure to evaluate the objective function at all corner points of the feasible region to ensure you find the maximum or minimum value.
Practice Graphing: Regularly practice graphing systems of inequalities to improve accuracy and speed.
Understand the Problem Context: Read the problem carefully to understand what is being asked, especially in real-life applications.

Practice & Assessment

Multiple Choice Questions

(2, 4)

(3, 2)

(4, 1)

(5, 0)

Correct Answer: B

Solution:

Check each point against the constraints. For (3, 2):

x + 4y = 3 + 8 = 11 \leq 20

and

3x + 2y = 9 + 4 = 13 \leq 18

. Thus, (3, 2) satisfies all constraints.

Z = 20

Z = 22

Z = 24

Z = 26

Correct Answer: C

Solution:

Solve the system of equations:

x + 2y = 12

and

2x + y = 10

. Solving gives

x = 4

y = 4

. Substitute into the objective function:

Z = 3(4) + 4(4) = 12 + 16 = 28

x + y \leq 60

x - y \geq 0

2x + 3y \leq 100

x + 2y \geq 50

Correct Answer: A

Solution:

The constraint

x + y \leq 60

represents the maximum storage space for tables and chairs.

The maximum value of the objective function

The linear inequalities or equations that limit the values of the decision variables

The decision variables themselves

The method used to solve the linear programming problem

Correct Answer: B

Solution:

Constraints in linear programming refer to the linear inequalities or equations that restrict the values of the decision variables, such as

x \geq 0, y \geq 0

The conditions that the variables must be non-negative.

The linear inequalities or equations that restrict the values of the decision variables.

The function that needs to be maximized or minimized.

The method used to solve the problem.

Correct Answer: B

Solution:

Constraints are the linear inequalities or equations that restrict the values of the decision variables.

It represents the area where the objective function is minimized.

It represents the area where the objective function is maximized.

It represents all possible solutions that satisfy the constraints.

It represents the area where the constraints are violated.

Correct Answer: C

Solution:

The feasible region represents all possible solutions that satisfy the constraints of the linear programming problem.

Maximize

Z = 40x + 30y

Maximize

Z = 30x + 40y

Maximize

Z = 40x + 20y

Maximize

Z = 20x + 30y

Correct Answer: A

Solution:

The objective function is derived from the profit per unit of products A and B. Thus, the profit function to maximize is

Z = 40x + 30y

, where

x

and

y

are the number of units of products A and B, respectively.

G.B. Dantzig

L. Kantorovich

F.L. Hitchcock

G. Stigler

Correct Answer: B

Solution:

L. Kantorovich and T.C. Koopmans were awarded the Nobel Prize for their pioneering work in linear programming.

To find the maximum or minimum value of a linear function.

To solve quadratic equations.

To calculate the area under a curve.

To determine the roots of a polynomial.

Correct Answer: A

Solution:

An optimisation problem in linear programming seeks to maximise or minimise a linear function subject to certain constraints.

Objective function

Constraint

Feasible region

Decision variable

Correct Answer: A

Solution:

The objective function is the linear function that needs to be maximized or minimized in a linear programming problem.

The objective function is non-linear.

The constraints are linear.

Decision variables are non-negative.

It involves optimization of a linear function.

Correct Answer: A

Solution:

Linear programming problems are characterized by a linear objective function, linear constraints, and non-negative decision variables. A non-linear objective function is not a characteristic of linear programming.

The maximum value of the objective function

The linear inequalities or equations that restrict the values of the variables

The decision variables

The feasible region

Correct Answer: B

Solution:

Constraints are the linear inequalities or equations that restrict the values of the variables in a linear programming problem.

Variables that determine the outcome of the objective function

The constraints of the problem

The maximum value of the objective function

The feasible region

Correct Answer: A

Solution:

Decision variables are the variables that determine the outcome of the objective function in a linear programming problem.

They must be integers.

They must be non-negative.

They must be prime numbers.

They must be even numbers.

Correct Answer: B

Solution:

In linear programming, the variables are subject to non-negative restrictions, meaning they must be greater than or equal to zero.

Minimize

Z = 5x_{11} + 6x_{12} + 8x_{13} + 4x_{21} + 7x_{22} + 9x_{23}

Minimize

Z = 6x_{11} + 5x_{12} + 8x_{13} + 7x_{21} + 4x_{22} + 9x_{23}

Minimize

Z = 5x_{11} + 8x_{12} + 6x_{13} + 4x_{21} + 9x_{22} + 7x_{23}

Minimize

Z = 8x_{11} + 5x_{12} + 6x_{13} + 9x_{21} + 4x_{22} + 7x_{23}

Correct Answer: A

Solution:

The objective function represents the total transportation cost, which is the sum of the cost per unit from each warehouse to each store, multiplied by the number of units transported, denoted by

x_{ij}

where

i

is the warehouse and

j

is the store.

To find the maximum value of a quadratic function.

To find the minimum value of a non-linear function.

To solve a linear programming problem in a finite number of steps.

To graphically represent the feasible region.

Correct Answer: C

Solution:

The simplex method is an iterative procedure used to solve any linear programming problem in a finite number of steps.

Z = 3x + 5y

Z = 5x + 3y

Z = 5x + 2y

Z = x + y

Correct Answer: B

Solution:

The objective function is the function that needs to be maximised or minimised, which in this case is

Z = 5x + 3y

Graphical method

Simplex method

Dual method

Integer programming

Correct Answer: B

Solution:

G.B. Dantzig suggested the simplex method in 1947 as an efficient iterative procedure to solve linear programming problems.

x^2 + y^2 \leq 10

x + y \leq 60

\sin(x) + \cos(y) = 1

x^3 - y^3 = 0

Correct Answer: B

Solution:

A linear constraint is an inequality or equation where each term is either a constant or the product of a constant and a single variable. Therefore,

x + y \leq 60

is a linear constraint.

Z = 5x + 3y

3x + 5y \leq 15

x \geq 0

y \geq 0

Correct Answer: B

Solution:

A constraint is a linear inequality or equation that restricts the values of the decision variables. Here,

3x + 5y \leq 15

is a constraint.

Objective function is linear

Constraints are linear

Variables can take any real value

Variables are non-negative

Correct Answer: C

Solution:

In a linear programming problem, variables must be non-negative and satisfy linear constraints. They cannot take any real value.

2500x + 500y \leq 50000

250x + 75y \leq 50000

5x + y \leq 100

x + y \leq 60

Correct Answer: A

Solution:

The constraint

2500x + 500y \leq 50000

ensures that the total cost of tables and chairs does not exceed Rs 50,000.

x^2 + y^2 \leq 10

x + y \leq 60

x^3 - y^3 \geq 5

\sqrt{x} + \sqrt{y} \leq 8

Correct Answer: B

Solution:

Constraints in linear programming are linear inequalities or equations. Option b is a linear inequality.

x + y = 0

2x + 3y = 6

x - y = 4

3x + 2y = 12

Correct Answer: A

Solution:

The equation

x + y = 0

passes through the origin since when

x = 0

y = 0

, making the point (0, 0) a solution.

x + y \leq 60

5x + y \leq 100

x \geq 0, y \geq 0

Z = 250x + 75y

Correct Answer: C

Solution:

The constraints

x \geq 0, y \geq 0

ensure that the decision variables are non-negative.

Correct Answer: D

Solution:

The maximum value of

Z

is 9, which can be found by evaluating the objective function at the vertices of the feasible region.

(3, 3)

(4, 2)

(2, 4)

(5, 0)

Correct Answer: D

Solution:

Check each point against the constraints. For (5, 0):

3(5) + 0 = 15

and

5 + 2(0) = 5

, both satisfy. However, it is on the boundary, not outside. Re-evaluate the constraints for other points to determine the correct answer.

G.B. Dantzig

L. Kantorovich

F.L. Hitchcock

G. Stigler

Correct Answer: B

Solution:

L. Kantorovich is credited with formulating the first linear programming problem in 1941.

Z = 3750

Z = 4500

Z = 5000

Z = 5250

Correct Answer: B

Solution:

To find the maximum value of

Z

, we need to evaluate

Z = 250x + 75y

at the vertices of the feasible region. Solving the constraints, the vertices are

(0, 60)

(20, 40)

, and

(20, 0)

. Evaluating

Z

at these points gives

Z = 4500

(20, 40)

, which is the maximum value.

4500

1500

7500

3000

Correct Answer: B

Solution:

Substitute the vertex

(0, 60)

into the objective function:

Z = 250(0) + 75(60) = 4500

. However, the constraint

5x + y \leq 100

becomes

5(0) + 60 = 60 \leq 100

, which is valid. Therefore, the maximum value of

Z

at this vertex is 4500.

Z = 250x + 75y

Z = 75x + 250y

Z = 250x - 75y

Z = 75x - 250y

Correct Answer: A

Solution:

The objective function is Z = 250x + 75y, where x is the number of tables and y is the number of chairs.

It represents the set of all possible solutions that maximize the objective function.

It represents the set of all possible solutions that satisfy all constraints.

It represents the set of all possible solutions that minimize the objective function.

It represents the set of all possible solutions that violate at least one constraint.

Correct Answer: B

Solution:

The feasible region is the set of all points that satisfy all the constraints of a linear programming problem.

The cost of production

The total profit

The number of items produced

The total investment

Correct Answer: B

Solution:

In this context,

Z

represents the total profit, as it is a function of the profit per table and chair.

A linear function to be maximized or minimized

A set of constraints

The feasible region

The decision variables

Correct Answer: A

Solution:

The objective function in a linear programming problem is the linear function that needs to be maximized or minimized, such as

Z = 250x + 75y

in this case.

Correct Answer: A

Solution:

To find the maximum value of Z, solve the system of inequalities. The feasible region is bounded by the constraints. Evaluating the objective function Z at the vertices of the feasible region gives the maximum value of Z = 15.

3x + y \geq 30

x + 2y \geq 30

3x + 2y \geq 30

x + y \geq 30

Correct Answer: A

Solution:

The constraint for vitamin A is based on the requirement that the total vitamin A from both food sources must be at least

30

units. Thus,

3x + y \geq 30

, where

x

and

y

are the servings of Food 1 and Food 2, respectively.

It is a linear function.

It can have multiple variables.

It must always be maximized.

It is subject to constraints.

Correct Answer: C

Solution:

The objective function in linear programming can either be maximized or minimized, not just maximized.

Z = 250x + 75y

Z = 2500x + 500y

Z = 500x + 2500y

Z = 75x + 250y

Correct Answer: A

Solution:

The objective function is

Z = 250x + 75y

, where

x

and

y

represent the number of tables and chairs, respectively.

Constraints

Objective function

Feasible region

Decision variables

Correct Answer: A

Solution:

Constraints are the inequalities that restrict the values of the decision variables in a linear programming problem.

(4, 3)

(5, 5)

(8, 1)

(3, 2)

Correct Answer: B

Solution:

To determine if a point is in the feasible region, it must satisfy all constraints. The point

(5, 5)

does not satisfy the constraint

x - y \geq 2

since

5 - 5 = 0

, which is less than

2

Simplex method

Graphical method

Iterative method

Transportation method

Correct Answer: A

Solution:

G.B. Dantzig suggested the simplex method in 1947 as an efficient way to solve linear programming problems.

A function to be differentiated

A function to be integrated

A linear function to be maximized or minimized

A quadratic function to be solved

Correct Answer: C

Solution:

An objective function in linear programming is a linear function that needs to be maximized or minimized.

Newton's Method

Simplex Method

Euler's Method

Runge-Kutta Method

Correct Answer: B

Solution:

The Simplex Method, suggested by G.B. Dantzig, is an iterative procedure to solve linear programming problems.

A problem that involves maximizing or minimizing a non-linear function.

A problem that involves maximizing or minimizing a linear function subject to linear constraints.

A problem that involves solving quadratic equations.

A problem that involves finding the roots of a polynomial.

Correct Answer: B

Solution:

A linear programming problem involves finding the optimal value of a linear function subject to linear constraints.

Number of tables and chairs

Cost of tables and chairs

Profit per table and chair

Storage space for tables and chairs

Correct Answer: A

Solution:

In the objective function

Z = 250x + 75y

x

and

y

represent the number of tables and chairs.

Objective function

Constraint

Feasible region

Decision variable

Correct Answer: A

Solution:

The function to be maximised or minimised in a linear programming problem is called the objective function.

5x + y ≤ 100

x + y ≤ 60

Z = 250x + 75y

x, y ≥ 0

Correct Answer: C

Solution:

Constraints are the linear inequalities or equations that restrict the values of the decision variables. The objective function Z = 250x + 75y is not a constraint.

x + y \leq 0

x - y \leq 5

2x + 3y \leq 15

3x + y \leq 12

Correct Answer: A

Solution:

The constraint

x + y \leq 0

does not affect the feasible region since

x, y \geq 0

implies

x + y \geq 0

, making this constraint redundant.

Maximize

Z = 5x + 3y

subject to

3x + 5y \leq 15

5x + 2y \leq 10

x, y \geq 0

Maximize

Z = x^2 + y^2

subject to

x + y \leq 10

x, y \geq 0

Minimize

Z = \sqrt{x} + \sqrt{y}

subject to

x + y \leq 5

x, y \geq 0

Minimize

Z = e^x + e^y

subject to

x + y \geq 1

x, y \geq 0

Correct Answer: A

Solution:

Option A is a linear programming problem because it involves maximizing a linear function subject to linear constraints.

Z = 250x + 75y

Z = 2500x + 500y

Z = 50x + 60y

Z = 500x + 250y

Correct Answer: A

Solution:

The objective function is the linear function to be maximized, which in this case is the profit from tables and chairs: Z = 250x + 75y.

The area where all constraints are satisfied.

The area where the objective function is maximized.

The area where the decision variables are negative.

The area where the constraints are not satisfied.

Correct Answer: A

Solution:

The feasible region is the area where all constraints are satisfied.

Correct Answer: B

Solution:

Evaluate

Z

at each vertex of the feasible region. The maximum value occurs at the vertex where

Z

is greatest.

The objective function must be quadratic.

The constraints must be linear inequalities.

The decision variables must be integers.

The solution must be unique.

Correct Answer: B

Solution:

A linear programming problem requires that the constraints be linear inequalities or equations. The objective function must also be linear, but it is not required to be quadratic, and the decision variables do not need to be integers. The solution need not be unique.

Linear programming problems always have a unique solution.

The feasible region in a linear programming problem is always bounded.

Linear programming problems can have multiple optimal solutions.

The objective function in linear programming is always a quadratic function.

Correct Answer: C

Solution:

Linear programming problems can have multiple optimal solutions, especially when the objective function is parallel to a constraint boundary within the feasible region.

Correct Answer: B

Solution:

Substituting (5, 2) into

Z = 3x + 2y

, we get

Z = 3(5) + 2(2) = 15 + 4 = 19

L. Kantorovich

G.B. Dantzig

T.C. Koopmans

F.L. Hitchcock

Correct Answer: B

Solution:

G.B. Dantzig suggested the simplex method, which is an iterative procedure to solve linear programming problems.

x + 2y \leq 100

2x + y \leq 100

x + y \leq 100

2x + 2y \leq 100

Correct Answer: B

Solution:

The constraint for labor is derived from the total labor hours required for products X and Y. Since each unit of X requires

1

hour and each unit of Y requires

2

hours, the constraint is

x + 2y \leq 100

Constraint function

Objective function

Feasible function

Decision function

Correct Answer: B

Solution:

The function that needs to be maximized or minimized in a linear programming problem is called the objective function.

The variables that are used to express the objective function.

The constants in the constraints.

The coefficients of the objective function.

The number of constraints in the problem.

Correct Answer: A

Solution:

Decision variables are the variables that are used to express the objective function and are subject to the constraints of the linear programming problem.

The feasible region is bounded.

The feasible region is unbounded.

The feasible region is a single point.

The feasible region does not exist.

Correct Answer: A

Solution:

The constraints form a bounded polygon in the first quadrant, thus the feasible region is bounded.

The set of all possible solutions that satisfy the objective function.

The set of all possible solutions that satisfy all constraints.

The set of solutions that maximize the objective function.

The set of solutions that minimize the objective function.

Correct Answer: B

Solution:

The feasible region is the set of all possible solutions that satisfy all the constraints of a linear programming problem.

Z = 250x + 75y

x + y \leq 60

x \geq 0, y \geq 0

5x + y \leq 100

Correct Answer: A

Solution:

The objective function is the linear function that needs to be maximized or minimized. In this case, it is

Z = 250x + 75y

Correct Answer: B

Solution:

The dealer can buy at most 60 pieces. If he buys 1 chair, he has Rs 500 left for tables, which means he can buy 19 tables (Rs 2500 each).

A method to graphically solve linear equations.

An iterative procedure to solve linear programming problems.

A way to find the maximum of quadratic functions.

A technique to solve differential equations.

Correct Answer: B

Solution:

The simplex method, introduced by G.B. Dantzig, is an iterative procedure used to solve linear programming problems efficiently in a finite number of steps.

They represent the constraints of the problem.

They are constants in the objective function.

They are the variables that need to be determined to optimize the objective function.

They define the feasible region of the problem.

Correct Answer: C

Solution:

Decision variables are the variables that need to be determined in a linear programming problem to optimize the objective function. They are subject to the constraints of the problem.

The maximum or minimum value of the objective function

The variables to be optimized

The linear inequalities or equations that restrict the values of the variables

The graphical representation of the solution

Correct Answer: C

Solution:

Constraints are the linear inequalities or equations that restrict the values of the variables in a linear programming problem.

Correct Answer: C

Solution:

Substitute the values of

x = 3

and

y = 1

into the objective function:

Z = 5(3) + 3(1) = 15 + 3 = 18

20 tables

10 tables

15 tables

25 tables

Correct Answer: B

Solution:

To maximize profit, the dealer should calculate the profit per unit cost for tables and chairs. Profit per unit cost for a table is Rs 250/2500 = 0.1, and for a chair is Rs 75/500 = 0.15. However, due to storage constraints, buying 10 tables (Rs 25,000) and 50 chairs (Rs 25,000) maximizes the profit within the budget and space limits.

Correct Answer: C

Solution:

If he buys 10 tables, he spends Rs 25,000. He has Rs 25,000 left, which allows him to buy 50 chairs (Rs 500 each). However, he can only store 60 items in total, so he can buy 20 chairs.

(2, 3)

(4, 1)

(0, 4)

(3, 2)

Correct Answer: B

Solution:

To check feasibility, substitute each point into the constraints. For

(4, 1)

x + 2y = 4 + 2(1) = 6 \leq 8

and

3x + 2y = 3(4) + 2(1) = 14 \leq 12

is false. For

(2, 3)

x + 2y = 2 + 2(3) = 8 \leq 8

and

3x + 2y = 3(2) + 2(3) = 12 \leq 12

is true. For

(0, 4)

x + 2y = 0 + 2(4) = 8 \leq 8

and

3x + 2y = 0 + 2(4) = 8 \leq 12

is true. For

(3, 2)

x + 2y = 3 + 2(2) = 7 \leq 8

and

3x + 2y = 3(3) + 2(2) = 13 \leq 12

is false. Therefore,

(2, 3)

is the correct feasible solution.

The set of all possible solutions that maximize the objective function.

The set of all points that satisfy the constraints of the problem.

The area under the curve of the objective function.

The region where the objective function is minimized.

Correct Answer: B

Solution:

The feasible region in a linear programming problem is the set of all points that satisfy the constraints of the problem. It is the region where the potential solutions lie.

(0, 0)

(3, 0)

(0, 3)

(1, 2)

Correct Answer: D

Solution:

The point (1, 2) satisfies both constraints: 3(1) + 5(2) = 13 ≤ 15 and 5(1) + 2(2) = 9 ≤ 10, making it a feasible solution.

Z = 26

Z = 24

Z = 20

Z = 18

Correct Answer: A

Solution:

Substitute the vertex (2, 6) into the objective function:

Z = 4(2) + 3(6) = 8 + 18 = 26

100

-50

-300

Correct Answer: A

Solution:

The maximum value of

Z

is 100 at the corner point

(0, 5)

(40, 20)

(60, 30)

(30, 40)

(50, 25)

Correct Answer: C

Solution:

Substitute each point into the constraints to check feasibility. For

(40, 20)

x + 2y = 40 + 2(20) = 80 \leq 120

x + y = 40 + 20 = 60 \geq 60

x - 2y = 40 - 2(20) = 0 \geq 0

. For

(60, 30)

x + 2y = 60 + 2(30) = 120 \leq 120

x + y = 60 + 30 = 90 \geq 60

x - 2y = 60 - 2(30) = 0 \geq 0

. For

(30, 40)

x + 2y = 30 + 2(40) = 110 \leq 120

x + y = 30 + 40 = 70 \geq 60

x - 2y = 30 - 2(40) = -50 \geq 0

is false. For

(50, 25)

x + 2y = 50 + 2(25) = 100 \leq 120

x + y = 50 + 25 = 75 \geq 60

x - 2y = 50 - 2(25) = 0 \geq 0

. Thus,

(30, 40)

is not in the feasible region.

Albert Einstein and Niels Bohr

L. Kantorovich and T.C. Koopmans

Marie Curie and Pierre Curie

John Nash and Paul Samuelson

Correct Answer: B

Solution:

L. Kantorovich and T.C. Koopmans were awarded the Nobel Prize in Economics in 1975 for their pioneering work in linear programming.

x + y ≤ 60

5x + y ≤ 100

x + y ≥ 60

5x + y ≥ 100

Correct Answer: A

Solution:

The constraint x + y ≤ 60 ensures that the total number of tables and chairs does not exceed 60.

Z = 250x + 75y

5x + y \leq 100

x

and

y

are non-negative

None of the above

Correct Answer: B

Solution:

The constraint

5x + y \leq 100

is one of the conditions that the variables must satisfy.

Z = 250x + 75y

Z = x^2 + y^2

Z = \sqrt{x} + \sqrt{y}

Z = \frac{x}{y}

Correct Answer: A

Solution:

A linear objective function is of the form

Z = ax + by

, where

a

and

b

are constants. Therefore,

Z = 250x + 75y

is a linear objective function.

Simplex method

Graphical method

Dual method

Matrix method

Correct Answer: B

Solution:

The graphical method is used to solve linear programming problems with two variables by representing constraints and objective functions on a graph.

(0, 0)

(2, 1)

(1, 2)

(3, 0)

Correct Answer: B

Solution:

The point

(2, 1)

satisfies both constraints

3x + 5y \leq 15

and

5x + 2y \leq 10

, making it a vertex of the feasible region.

Maximise

Z = 3x + 2y

subject to

x + 2y \leq 10

3x + y \leq 15

x, y \geq 0

Maximise

Z = x^2 + y^2

subject to

x + y \leq 10

x, y \geq 0

Minimise

Z = \frac{x}{y}

subject to

x + 2y \leq 8

x, y \geq 0

Maximise

Z = \sin(x) + \cos(y)

subject to

x + y \leq 5

x, y \geq 0

Correct Answer: A

Solution:

A linear programming problem involves maximising or minimising a linear objective function subject to linear constraints. Option A satisfies these conditions.

To find the optimal value of a linear function subject to constraints

To solve quadratic equations

To minimize the number of variables

To find the maximum number of solutions

Correct Answer: A

Solution:

The main goal of a linear programming problem is to find the optimal value (maximum or minimum) of a linear function subject to constraints.

The feasible region is always bounded.

The feasible region can be empty.

The feasible region contains all possible solutions to the problem.

The feasible region is always a convex set.

Correct Answer: D

Solution:

In linear programming, the feasible region is defined by a set of linear inequalities and is always a convex set. It may or may not be bounded, and it can be empty if no solutions satisfy all constraints. The feasible region does not necessarily contain all possible solutions, only those that satisfy the constraints.

True or False

Correct Answer: True

Solution:

In linear programming, 'programming' refers to creating a plan or strategy to achieve the optimal solution.

Correct Answer: True

Solution:

In linear programming, the objective function can be set to either maximize or minimize, depending on the problem's requirements.

Correct Answer: True

Solution:

Linear programming problems involve finding the optimal value (maximum or minimum) of a linear function subject to constraints.

Correct Answer: False

Solution:

The excerpt indicates that a linear programming problem can involve either maximizing or minimizing the objective function.

Correct Answer: False

Solution:

The term 'programming' in linear programming refers to the method of determining a particular plan or course of action, not computer programming.

Correct Answer: True

Solution:

In linear programming, decision variables are required to be non-negative as part of the problem's constraints.

Correct Answer: True

Solution:

The simplex method, introduced by G.B. Dantzig, is an iterative procedure used to solve linear programming problems in a finite number of steps.

Correct Answer: True

Solution:

Linear programming problems are indeed a type of optimization problem where the objective is to find the maximum or minimum value of a linear function, subject to linear constraints.

Correct Answer: True

Solution:

In a linear programming problem, the objective function is defined as a linear function of the decision variables.

Correct Answer: True

Solution:

The simplex method, introduced by G.B. Dantzig, is an iterative procedure used to solve linear programming problems.

Correct Answer: True

Solution:

Linear programming problems are concerned with finding the optimal value (maximum or minimum) of a linear function subject to constraints.

Correct Answer: False

Solution:

The simplex method is not a graphical method; it is an iterative procedure used to solve linear programming problems in a finite number of steps.

Correct Answer: False

Solution:

A feasible region in a linear programming problem can be unbounded, as shown in the diagram with the shaded area.

Correct Answer: True

Solution:

The feasible region, which represents all possible solutions to the constraints, can be unbounded as shown in the graph description.

Correct Answer: False

Solution:

Constraints in a linear programming problem can be linear inequalities or equations.

Correct Answer: True

Solution:

Constraints in a linear programming problem can be expressed as linear inequalities or equations, which restrict the values of the decision variables.

Correct Answer: True

Solution:

In linear programming problems, decision variables are required to be non-negative.

Correct Answer: False

Solution:

Linear programming problems have wide applicability in various fields such as industry, commerce, and management science, making them highly relevant in real-world scenarios.

Correct Answer: True

Solution:

G.B. Dantzig suggested the simplex method in 1947 as an efficient iterative procedure to solve linear programming problems.

Correct Answer: True

Solution:

With the advent of computers and necessary software, linear programming models can be applied to increasingly complex problems in many areas.

Correct Answer: False

Solution:

While the chapter discusses solving linear programming problems using the graphical method, there are other methods such as the simplex method.

Correct Answer: True

Solution:

In a linear programming problem, the constraints are expressed as linear inequalities or equations, which define the feasible region.

Correct Answer: True

Solution:

In linear programming, the constraints are defined as linear inequalities or equations that the decision variables must satisfy.

Correct Answer: True

Solution:

In linear programming, the term 'linear' indicates that all equations and inequalities involved are linear.

Correct Answer: True

Solution:

By definition, the objective function in a linear programming problem is a linear function.

Correct Answer: True

Solution:

Linear programming problems can involve maximizing or minimizing an objective function, as shown in the examples provided.

Correct Answer: True

Solution:

In linear programming, decision variables are required to be non-negative as part of the constraints.

Correct Answer: False

Solution:

An objective function in a linear programming problem can be either maximized or minimized, depending on the problem requirements.

Correct Answer: True

Solution:

L. Kantorovich and T.C. Koopmans were indeed awarded the Nobel Prize in Economics in 1975 for their pioneering work in linear programming.

Correct Answer: False

Solution:

In linear programming, 'programming' refers to determining a particular plan of action, not creating computer programs.

Correct Answer: False

Solution:

The objective function in a linear programming problem can be either maximized or minimized.

Correct Answer: False

Solution:

Linear programming problems have wide applicability in various fields such as industry, commerce, and management science.

Correct Answer: True

Solution:

Constraints in a linear programming problem can indeed be linear inequalities or equations that the decision variables must satisfy.

Correct Answer: True

Solution:

The excerpt mentions that in 1945, an English economist described a linear programming problem related to determining an optimal diet.

Correct Answer: True

Solution:

Linear programming problems require decision variables to be non-negative, as stated in the constraints.

Correct Answer: True

Solution:

The first linear programming problem was formulated in 1941 by L. Kantorovich and F.L. Hitchcock during World War II.

Correct Answer: False

Solution:

Linear programming problems can be solved using various methods, including the simplex method, not just the graphical method.

Correct Answer: True

Solution:

The simplex method, suggested by G.B. Dantzig in 1947, is indeed an iterative procedure for solving linear programming problems.

Correct Answer: False

Solution:

Linear programming problems have wide applicability in various fields such as industry, commerce, and management science, not just mathematics.

Correct Answer: False

Solution:

While the simplex method is a well-known method for solving linear programming problems, there are other methods available as well.

Correct Answer: True

Solution:

A linear programming problem can be formulated to either maximize or minimize a linear objective function, depending on the problem's requirements.

Correct Answer: True

Solution:

The excerpt explains that the term 'linear' implies that all the mathematical relations used in the problem are linear relations.

Correct Answer: True

Solution:

Linear programming problems are concerned with finding the optimal value (maximum or minimum) of a linear function subject to linear constraints.

Correct Answer: True

Solution:

The objective function in a linear programming problem is defined as a linear function of the decision variables, which needs to be maximised or minimised.

Correct Answer: True

Solution:

The term 'linear' in linear programming indicates that all the mathematical relations used in the problem are linear relations.

Correct Answer: False

Solution:

In linear programming, the objective function must be a linear function of the decision variables.

Correct Answer: False

Solution:

While the simplex method is a well-known and efficient method for solving linear programming problems, there are other methods available as well.

Correct Answer: False

Solution:

The feasible region can be unbounded, as shown in the graph where the shaded area represents an unbounded feasible region.

Correct Answer: True

Solution:

With advancements in computers and software, linear programming models can now be applied to solve complex problems across various fields.

Correct Answer: True

Solution:

The first linear programming problem was formulated in 1941 by L. Kantorovich and F.L. Hitchcock during World War II.

Correct Answer: True

Solution:

Linear programming problems are a special class of optimisation problems used to find maximum profit, minimum cost, or minimum use of resources.

Correct Answer: True

Solution:

A linear programming problem seeks to maximise or minimise a linear function subject to constraints given by linear inequalities.

Linear Programming

AI Learning Assistant

Summary

Chapter 12: Linear Programming

Summary

Key Formulas/Definitions

Learning Objectives

Common Mistakes/Exam Tips

Important Diagrams

Learning Objectives

Learning Objectives

Detailed Notes

Chapter 12: Linear Programming

12.1 Introduction

12.2 Linear Programming Problem and its Mathematical Formulation

12.2.1 Mathematical Formulation

12.2.2 Graphical Method of Solving Linear Programming Problems

Important Theorems

Example of Corner Points and Values

Conclusion

Exam Tips & Common Mistakes

Common Mistakes and Exam Tips in Linear Programming

Common Pitfalls

Tips for Success

Practice & Assessment

Multiple Choice Questions

Q1.In a linear programming problem, if the objective function is Z=6x+2yZ = 6x + 2yZ=6x+2y and the constraints are x+4y≤20x + 4y \leq 20x+4y≤20, 3x+2y≤183x + 2y \leq 183x+2y≤18, x,y≥0x, y \geq 0x,y≥0, which of the following points is a feasible solution?

Correct Answer: B

Q2.For the linear programming problem: Maximise Z=3x+4yZ = 3x + 4yZ=3x+4y subject to x+2y≤12x + 2y \leq 12x+2y≤12, 2x+y≤102x + y \leq 102x+y≤10, x,y≥0x, y \geq 0x,y≥0, what is the value of ZZZ at the intersection of the lines x+2y=12x + 2y = 12x+2y=12 and 2x+y=102x + y = 102x+y=10?

Correct Answer: C

Q3.Which of the following is a constraint in the linear programming problem for maximizing Z=250x+75yZ = 250x + 75yZ=250x+75y?

Correct Answer: A

Q4.In the context of linear programming, what does the term 'constraints' refer to?

Correct Answer: B

Q5.In a linear programming problem, what are the constraints?

Correct Answer: B

Q6.What is the significance of the feasible region in a linear programming problem?

Correct Answer: C

Correct Answer: A

Q8.Which of the following historical figures was awarded the Nobel Prize for their work in linear programming?

Correct Answer: B

Q9.What is the primary goal of an optimisation problem in linear programming?

Correct Answer: A

Q10.In a linear programming problem, what is the term used for the mathematical expression that needs to be maximized or minimized?

Correct Answer: A

Q11.Which of the following is NOT a characteristic of a linear programming problem?

Correct Answer: A

Q12.In a linear programming problem, what does the term 'constraints' refer to?

Correct Answer: B

Q13.In the context of linear programming, what are 'decision variables'?

Correct Answer: A

Q14.In a linear programming problem, what are the conditions that the variables must satisfy?

Correct Answer: B

Correct Answer: A

Q16.In the simplex method, what is the primary goal?

Correct Answer: C

Q17.What is the objective function in the problem: Maximise Z=5x+3yZ = 5x + 3yZ=5x+3y subject to 3x+5y≤153x + 5y \leq 153x+5y≤15, 5x+2y≤105x + 2y \leq 105x+2y≤10, x,y≥0x, y \geq 0x,y≥0?

Correct Answer: B

Q18.Which method was suggested by G.B. Dantzig in 1947 for solving linear programming problems?

Correct Answer: B

Q19.Which of the following constraints would be considered a linear constraint?

Correct Answer: B

Q20.Which of the following is a constraint in the problem: Maximize Z=5x+3yZ = 5x + 3yZ=5x+3y subject to 3x+5y≤153x + 5y \leq 153x+5y≤15, 5x+2y≤105x + 2y \leq 105x+2y≤10, x≥0x \geq 0x≥0, y≥0y \geq 0y≥0?

Correct Answer: B

Q21.Which of the following is NOT a characteristic of a linear programming problem?

Correct Answer: C

Q22.Which of the following constraints represents the condition that the total investment should not exceed Rs 50,000?

Correct Answer: A

Q23.Which of the following is a constraint in a linear programming problem?

Correct Answer: B

Q24.Which of the following constraints forms a boundary line that passes through the origin in a linear programming problem?

Correct Answer: A

Q25.Which of the following constraints ensures non-negativity in a linear programming problem?

Correct Answer: C

Q26.If a linear programming problem has the objective function Z=5x+3yZ = 5x + 3yZ=5x+3y and constraints 3x+5y≤153x + 5y \leq 153x+5y≤15 and 5x+2y≤105x + 2y \leq 105x+2y≤10, what is the maximum value of ZZZ?

Correct Answer: D

Q27.In a linear programming problem, if the objective function is Z=9x+7yZ = 9x + 7yZ=9x+7y and the constraints are 3x+y≤153x + y \leq 153x+y≤15, x+2y≤10x + 2y \leq 10x+2y≤10, x,y≥0x, y \geq 0x,y≥0, which of the following points is not in the feasible region?

Correct Answer: D

Q28.Which of the following historical figures is credited with formulating the first linear programming problem?

Correct Answer: B