Linear Programming MCQ: Explanations and Examples

Ans. (3) linear programming

Explanation: The Graphical Method, Simplex Method, and Transportation Method are optimization techniques for linear programming problems. Graphical Method visualizes the feasible region and objective function on a graph to find optimal solutions. Simplex Method uses algebraic operations to iteratively find the optimal solution. Transportation Method is used to allocate resources efficiently from sources to destinations.

Ans. (3) Artificial variable is present in basis

Explanation: A Simplex problem is considered infeasible when there is no solution that satisfies all the constraints of the problem. This can occur when the constraints are conflicting and cannot be simultaneously satisfied, or when there is no solution that satisfies the non-negativity constraints (i.e., all variables must be non-negative). In this case, the simplex algorithm will not be able to find a feasible solution and will terminate with an infeasibility message.

Ans. (2) Change in right hand side of feasible region

Explanation: Linear programming feasibility is if a solution meets all restrictions. Feasible problems have solutions. Infeasibility occurs when no solution meets all requirements.

Changes in limitations or objective function can affect feasibility. If a new requirement makes it impossible to develop a solution that meets all constraints, the problem becomes infeasible. However, removing a constraint may make the challenge doable.

Changing the objective function might also affect feasibility. The task is viable if the new objective function solves all restrictions. The task becomes infeasible if the new objective function yields a solution that violates all restrictions.

Ans. (4) 9

Explanation: In a transportation problem with m supply points and n demand points

Number of constraints = m + n 

Number of variables = m × n 

Number of equations = m + n - 1 

Calculation:

Given:

m = 4, n = 5

Number of constraints = m + n = 4 + 5 = 9

Ans. (3) Unrestricted in sign

Explanation: 

• For every linear programming problem, there is a unique related linear programming problem with the same data that describes and solves the original problem.
• In Duality, the goal is to find a Transpose matrix of the Primal problem that was given to us at the start.
• It is done by switching the order of the rows and columns. The answer to both problems will be the same in the end.

Ans. (3) Transportation problem

Explanation: VAM solves transportation challenges. Penalty cost determines the initial possible transportation problem solution in this iterative procedure.

VAM finds a plausible transportation problem solution, which can be enhanced utilizing the northwest corner rule, minimal cost technique, or stepping stone method. The approach assigns penalty charges to each unused transportation table cell and fills the cell with the lowest penalty cost.

VAM is beneficial for transportation problems with many supply and demand points or complicated pricing comparisons. The northwest corner rule and minimum cost approach can be replaced by the easy-to-implement method.

Vogel's Approximation Method solves transportation difficulties by finding an initial workable solution.

Ans. (1) (60, 0)

Explanation: After setting each constraint to zero, we get the equations of lines on cartesian coordinates.

When we compare the inequality with (0,0) and shade the common area, we get the following for the feasible region:

Ans. (4) Unbounded

Explanation: The mathematical optimization technique Simplex solves linear programming issues. The algorithm iteratively determines the optimal solution by picking a pivot column (the column with the largest negative value in the objective function row) and a pivot row (the row with the smallest positive ratio of the right-hand side value to the pivot column entry). The pivot element updates the tableau, a matrix representation of the linear programming problem.

The Simplex algorithm cannot discover a solution if all pivot column entries are negative or zero. Two scenarios:

• All pivot column items are negative: If all items in the pivot column are negative, the ratio will be negative or zero regardless of the pivot row. No suitable Simplex solution can be discovered.
• The pivot column is empty: If the pivot column has zero entries, the objective function is flat and the algorithm cannot determine which direction to travel to enhance the result. This solution is unbounded or infeasible. More testing is needed to decide.

The Simplex technique terminates and cannot find a feasible solution in either scenario. The problem may require a different optimization algorithm or approach.

Ans. (1) Constraints

Explanation: 

Objective function: 

• Objective functions are linear functions of two or more variables that must be minimized or minimized under specific constraints. 
• Decision variables are objective function variables.

Constraints:

• Linear constraints limit variables in a linear programming problem. 
• The ultimate objective function solution must satisfy these limitations.

Ans. (1) first quadrant

Explanation: The region represented by x ≥ 0 and y ≥ 0 is the non-negative quadrant of the Cartesian plane. It is a region in which both x and y are greater than or equal to zero. This region is also referred to as the first quadrant. The non-negative quadrant is a commonly used region in linear programming problems as it represents the feasible region in which the variables must be non-negative.

Ans. (2) function to be optimized

Explanation: Optimization problem's mathematical purpose. The objective function incorporates numerous variables and coefficients to reflect the decision-goal. In a production context, the aim function may be to maximize profit or minimize cost, taking into consideration resources used, input prices, and product prices. The variable values that optimize the objective function within the limitations of the linear programming problem are the solution.

Ans. (1) Constraint

Explanation: A linear programming problem's constraints limit the variables and set the conditions for a feasible solution. Linear inequalities or equations limit the optimization problem's variables' values. In production, restrictions may include resource limits, output levels, and quality control. An optimal linear programming solution must meet all requirements.

Ans. (3) Feasible solution

Explanation: A feasible solution in linear programming is:

• A set of values for the decision variables in the problem.
• Satisfies all the constraints in the problem.
• Meets the non-negativity condition, which requires that the values of the decision variables be greater than or equal to zero, unless otherwise specified.
• A valid solution, but not necessarily the optimal solution.
• The starting point for finding the optimal solution, which optimizes the objective function.

Ans. (3) 16

Explanation: To find the maximum value of Z = 3x + 4y subject to the constraints x + y ≤ 4, x ≥ 0 and y ≥ 0, you can use the simplex method or graphical method of linear programming.

Using the graphical method, you can plot the constraints as lines in a two-dimensional plane and find the feasible region, which is the set of points that satisfies all the constraints. The feasible region for this problem is a triangle, and the maximum value of Z = 3x + 4y will occur at the vertex of the feasible region that has the highest value of Z.

After finding the feasible region, you can calculate the value of Z for each vertex and select the one with the maximum value. In this case, the maximum value of Z is 12, and it occurs when x = 0 and y = 4.

So, the maximum value of Z = 3x + 4y subject to the constraints x + y ≤ 4, x ≥ 0 and y ≥ 0 is 12.

Ans. (3) 37 at (4, 5)

Explanation: To maximize: z = 3x + 5y

Given subject to, 

x + 4 ≤ 24

3x + y ≤ 21

x + y ≤ 9, x ≥ 0, y ≥ 0

Consider, 

x + 4y = 24 …(1)

3x + y = 21 …(2)

x + y = 9 …(3) 

On solving equation (1) and (2), we get

y = 51/11

Form equation (1), 

x = 60/11

Therefore, (x,y) = (60/11, 51/11) 

And z = 3x + 5y = 435/11 = 39.54 

Now, 

On solving equation (2) and (3), we get 

x = 6 

From equation (3), 

y = 3

Therefore, (x,y) = (6,3) 

And z = 3x + 5y = 33

Now, 

On solving equation (1) and (3), we get 

y = 5 

From equation (3), 

x = 4 

Therefore, (x,y) = (4,5)

And z = 3x + 5y = 37