Mathematics Test - 24

Explanation:

Graphical method of Linear programming:

• Objective function: It is the function which we need to optimise i.e. either maximize or minimize.
• Constraints: These are the limited resources within which we need to optimise our objective function.
• Feasible Solutions: All such solutions which can be worked out satisfying all constraints are called “feasible solutions” or shaded regions. 
• Optimum Solution: Optimum means either maximum or minimum. The optimum solution is the best of all feasible solutions.

Steps in the Graphical method:

• Identify the problem and define decision variable, objective function and constraints.
• Draw a graph that includes all the constraints and identify the common feasible region.
• Every corner point of the common feasible region represents a feasible solution.
• Find out the point within a feasible region that optimises the objective function. This point is the optimal solution to the problem.

Example:

Maximize z = 6x + 10y

Subject to x ≤ 4

y ≤ 6

3x + 2y ≤ 18

x ≥ 0, y ≥ 0

Z(0) = 0 + 0 = 0 ⇒ feasible solution

Z(A) = Z(4, 0) = 6 × 4 + 0 = 24 ⇒ feasible solution

Z(B) = Z(4, 3) = 6 × 4 + 10 × 3 = 54 ⇒ feasible solution

Z(C) = Z(2, 6) = 2 × 6 + 6 × 10 = 72 ⇒ optimal solution

Z(D) = Z(0, 6) = 0 + 6 × 10 = 60 ⇒ feasible solution

Explanation

The standard form of linear programming problem(LPP) is

Objective Function (Max or Min) Z = c₁x₁ + cx + ………….+cx  (1)

Subjected to constraints,

a₁₁x₁ + a₁₂x₂ + ------------------------ + a_1nx_n ≤ or ≥ b₁

a₂₁x₁  + a₂₂x₂ + ------------------------ + a_2nx_n ≤ or≥ b₂      (2)

_.

_.

a_m1x₁ + a_m2x₂ + -------------------------- + a_mnx_n ≤ or≥ b_m

And x₁, x_{2,…………….}x_n ≥ 0    (3)

x_1,x₂,-------------------- x_n are called decision variables.

c_{1 ,}c_{2 -------------------------------} c_n   are called cost factors.

Any set X {x_1,x_2, --------------x_n}of variables are called a feasible solution of the LPP problem If satisfies the set of constraints (2) and non-negativity constraints(3).                                                             

Explanation:

Simplex method:

• The simplex method is the most popular method used for the solution of Linear Programming Problems (LPP).
• The Simplex method is a search procedure that shifts through the set of basic feasible solutions, one at a time until the optimal basic feasible solution is identified.
• It can be used for two or more variables as well (always advisable for more than two variables to avoid lengthy graphical procedure).
• The simplex method is not used to examine all the feasible solutions.
• It deals only with a small and unique set of feasible solutions, the set of vertex points (i.e. extreme points/corner points) of the convex feasible space that contain the optimal solution.
• All the resource values or constraints should be non-negative.
• All the inequalities of the constraint should be converted to equalities with the help of slack or surplus variables.

Explanation:

Maximize z = 60X1 + 50X2

Subject to:

X1 + 2X2 ≤ 40

\(\frac{X_1}{40}\;+\;\frac{X_2}{20}\leq1\)

3X1 + 2X2 ≤ 60

\(\frac{X_1}{20}\;+\;\frac{X_2}{40}\leq1\)

X1,X2 ≥ 0

Graphical representation:

The feasible point are (0, 0), (20, 0), (0, 20), and (10, 15)

Max (0, 0) = 0

Max (20, 0) = 60 × 20 ⇒ 1200

Max (0, 20) = 50 × 20 ⇒ 1000

Max (10, 15) = (60 × 10) + (50 × 15) ⇒ 1350

∴ the given LPP has unique optimal solution.

Explanation:

• Linear programming (LP) in industrial engineering is used for the optimization of our limited resources when there is a number of alternate solutions possible for the problem. The real-life problems can be written in the form of a linear equation by specifying the relation between its variables.  
• The general LP problem calls for optimizing a linear function for variables called the "objective function" subjected to a set of linear equations and inequalities called the constraints or restriction.
• A redundant constraint is a constraint that can be removed from a system of linear constraints without changing the feasible region.
• While solving a linear programming model, if a redundant constraint is added, then there will be no effect on the existing solution​.

​Additional Information

• Consider the following linear inequality constraints:

x = x₁ and y = x₂

1. 2x +1y ≤ 8,
2. 4x + 0y ≤ 15,
3. 1x + 3y ≤ 9,
4. 1x + 2y ≤ 14,
5. 1x ≤ 4, 
6. 1x + 1y ≤ 5,

where, x + y ≤ 0

Methods for Identification of Redundant Constraints 

Many methods are available in the literature to identify the redundant constraints in linear programming problems. In this paper, the following five methods are discussed and compared

1.  Bounds method 
2.  Linear programming method
3.  Deterministic method
4.  Stojkovic and Stanimirovic method
5.  Heuristic method

Calculation

Given

Objective function

Maximize, Z = X₁ + 2X₂

Constraints

X₁ ≤ 2  ................. (1)

X₂ ≤ 2  ................. (2)

X₁ + X₂ ≤ 2 ................... (3)

Non neagative constarints

X₁, X₂ ≥ 0

The above equations can be written as,

\(\frac{{{X_1}}}{2} \le 1\left( 4 \right)\)

\(\frac{{{X_2}}}{2} \le 1\left( 5 \right)\)

\(\frac{{{X_1}}}{2} + \frac{{{X_2}}}{2} \le 1\left( 6 \right)\)

Plot the above equations on X₁ – X₂ graph and find out the solution space.

Now, find out the value of the objective function at every extreme point of solution space.

Z_o = 0 + 2 × 0 = 0

Z_A = 0 + 2 × 2 = 4

Z_B = 2 + 2 × 0 = 2

Since the value of the objective function is maximum at A. There A (0, 2) is the optimal solution.

CONCEPT:

• We will formulate the constraints depending on the availability of the resources.

Explanation:

Let the number of the product of P! and P2 types are x1  and x2.

For non-negativity constraints,

 x1  ≥ 0 and x2. ≥ 0 

The maximum used material of M1 type is 70 so,

⇒ 2x1 + 3x2 ≤ 70      ...(1) 

The maximum used material of M2 type is 50 so,

⇒ 2x1 + x2 ≤ 50      ...(2) 

The maximum used material of M3 type is 40 so,

⇒ 2x2 ≤ 40      ...(3) 

For Profit Maximization (As the unit prize is mentioned as 150 and 100 Rs per unit for P1 and P2 type)

⇒ max Z = 150x1 + 100x2 

So, the correct answer is option 2

Concept:

Draw the constraints to find the feasible region:

• To draw the inequalities, first, draw the equation form of the inequalities.
• Now check the region which we have to choose depending on the sign of inequality.
• To check which region we need to choose put (0,0) in both the inequality. and check whether this inequality is satisfying or not.
• If it is satisfying the inequality then take the region containing (0,0) else the opposite side of (0,0).

Calculation:

Given: 

The equations are plotted in the graph

As it is clear from graph that there is no point (x₁, x₂) which can lie in both regions, so there is no solution or infeasible solution.

Explanation:

Z_max = 3x₁ + 2x₂

Subjected to

x₁ ≤ 4               ___________(i)

x₂ ≤ 6               ___________(ii)

3x₁ + 2x₂ ≤ 18 ___________(iii)

and x₁, x₂ ≥ 0

Now the intersections of the lines are denoted by E, F

for E, 3x₁ + 2x₂ = 18

and x₂ = 6

So, 3x₁ + (2 × 6) = 18 ⇒ x₁ = 2 ⇒ E (2,6)

For F, 3x₁ + 2x₂ = 18

and x₁ = 4

⇒ (3 × 4) + 2x₂ = 18 ⇒ x₂ = 3 ⇒ F (4,3)

So the feasible points are (0, 0), (4, 0), (4, 3), (2, 6), (0, 6)

Z(0, 0) = 0

Z(4, 0) = 12

Z(4, 3) = (3 × 4) + (2 × 3) = 18

Z(2, 6) = (3 × 2) + (2 × 6) = 18

Z(0, 6) = 12

So the objective function has multiple solution.

Concept:

Referring to the graphs for given linear equations

The constraints x1 ≥ 0, x2 ≥ 0 and x1 + 2x2 ≤ 4 will be having feasible region.

The corner points of the feasible region will give the best feasible solution for the objective function.

Calculation:

Referring to the cornor points of feasible rergion,

The corner point of the feasible region are (0, 0), (0, 2) & (4, 0)

The value of the objective function at corner points,

⇒ Z (0,0) = 0,

⇒ Z (0,2) = 18

⇒ Z (4,0) = 12

∵ The maximum value of Z is at (0, 2)

⇒ Zmax = 18