Linear Programming and Optimization
Formulation
Steps in Formulating the LP Problems:
- Define the objective. (min or max)
- Define the decision variables.
- Write the mathematical function for the objective.
- Write the constraints.
- Constraints can be in < , =, or > form.
subjected to:
Solved Example: 9131-01
As per one of the assumptions of linear programming problem in operation research, objective function and constraints are assumed to be:
A. Sinusoidal
B. Exponential
C. Linear
D. Circular
Correct Answer: C
Solved Example: 9131-02
In a Linear Programming problem, the restrictions or limitations under which the objective function is to be optimised are called:
A. Constraints
B. Objective function
C. Decision variables
D. None of the above
Correct Answer: A
Solved Example: 9131-03
In a Linear Programming Problem, the linear relations of the variables which are either to be maximized or minimized is called:
A. The decisions variables
B. The constraints functions
C. The variable function
D. The objective function
Correct Answer: D
Solved Example: 9131-04
In a transportation problem with 4 supply points and 5 demand points, how many number of constraints are required in its formulation?
A. 20
B. 1
C. 0
D. 9
Correct Answer: D
Solved Example: 9131-05
Any linear programming model must have all of the following properties EXCEPT:
A. The model must have structural constraints
B. The relationship between variables and constraints must be non-linear
C. The model must have an objective function
D. The model must have non-negativity constraint
Correct Answer: B
Solved Example: 9131-06
In order that linear programming techniques provide valid results:
A. Relations between factors must be linear (positive)
B. Relations between factors must be linear (negative)
C. Either (A) or (B)
D. Only one factor should change at a time, others remaining constant
Correct Answer: C
Solved Example: 9131-07
Which of the following conditions are necessary for applying linear programming?
A. There must be a well defined objective function.
B. The decision variables should be interrelated and nonnegative.
C. The resources must be in limited supply.
D. All of the above
Correct Answer: D
Solved Example: 9131-08
The mathematical technique for finding the best use of limited resources in an optimum manner is known as:
A. Operation research
B. Linear programming
C. Network analysis
D. Break-even analysis
Correct Answer: B
Solution
The graphical method is useful only for problems involving two decision variables and relatively few problem constraints. What happens when we need more decision variables and more problem constraints? We use an algebraic method called the simplex method
- Optimal solution(x*) is the best solution i.e. the value of x for which objective function(Z) is minimum or maximum.
- To find x*, simplex method must decide which component “enters” by becoming positive and which component “leaves” by becoming zero.
- This exchange is chosen so as to lower the total cost or to increase the profit.
Sdo, Public domain, via Wikimedia Commons
Solved Example: 9132-01
Consider the Linear Programming problem:
\[7X_1+ 6X_2 + 4X_3\]subject to:
\[X_1 + X_2 + X_3 \leq 5\] \[2X_1 + X_2 + 3X_3 \leq 10\] \[X_1 , X_2 , X_3 \geq 0\] (Solve by algebraic method).The number of basic solutions is:
A. 10
B. 7
C. 9
D. 8
Correct Answer: A
Solved Example: 9132-02
The graphical method is best suited for solving linear programming problems with _____ variables.
A. 5
B. 3
C. 4
D. 2
Correct Answer: D
Solved Example: 9132-03
Consider the given problem:
5x + y ≤ 100 ... (1)
x + y ≤ 60 ... (2)
x ≥ 0 ... (3)
y ≥ 0 ... (4)
If we solve the above linear equations by the graphical method of Linear Programming, then the following point ____ will not form the the boundary of the feasible region.
A. (60, 0)
B. (20, 0)
C. (0, 60)
D. (10, 50)
Correct Answer: A
Solved Example: 9132-04
Simplex method is the method used for:
A. Value analysis
B. Network analysis
C. Linear programming
D. Queuing theory
Correct Answer: C
Solved Example: 9132-05
A feasible solution to the linear programming problem should:
A. Satisfy the problem constraints
B. Optimize the objective function
C. Satisfy the problem constraints and non-negativity restrictions
D. Satisfy the non-negativity restrictions
Correct Answer: C
Interpretation
- Sensitivity analysis serves as an integral part of solving linear programming model & is normally carried out after the optimal solution is obtained.
- It determines how sensitive the optimal solution is to making changes in the original model.
- Sensitivity analysis allows us to determine how “sensitive” the optimal solution is to changes in data values.
- Sensitivity analysis is important to the manager who must operate in a dynamic environment with imprecise estimates of the coefficients.
- Sensitivity analysis allows him to ask certain what-if questions about the problem.
- Sensitivity analysis is used to determine how the optimal solution is affected by changes, within specified ranges, in:
- the objective function coefficients
- the right-hand side (RHS) values
Inductiveload, Public domain, via Wikimedia Commons
Solved Example: 9136-01
What is the interpretation of the shaded region in a Linear Programming Problems?
A. It is very important area
B. It will not satisfy the limitations
C. It will satisfy few constraints
D. It will satisfy all constraints
Correct Answer: D