OPERATION RESEARCH

.GRAPHICAL METHOD OF LINEAR PROGRAMMING

.LINEAR PROGRAMMING –SIMPLEX METHOD

Dr. K .VANITHEESWARI, Ph.D.,

Assistant Professor,

PG and Research Department of Commerce

C.P.A College, Bodinayakanur

Introduction to Linear Programming

• Linear Programming is a special and versatile technique which can be applied to a variety of

Management problems .Advertising,Distribution, Investment, Production, Refinery Operations, and Transportation analysis.

​

• The linear programming is useful not only in industry and business but also in
• non-profit sectors such as Education, Government, Hospital, and Libraries.

​

​

Graphical Analysis of Linear Programming

​

​

• This section shows how a two-variable linear programming problem is solved graphically, which is

illustrated as follows:

​

​

Problem 1.

Consider the product mix problem discussed in section 2.2

Maximize

30x1 + 40x2

Subject to:

3x1 + 2x2 ≤ 600

3x1 + 5x2 ≤ 800

5x1 + 6x2 ≤ 1100

x1≥ 0, x2 ≥ 0

From the first constraints 3x1 + 2x2 ≤ 600, draw the line 3x1 + 2x2 = 600 which passes through the point

(200, 0) and (0, 300). This is shown in the following graph as line 1.

In this problem the objective function is 30x1 + 40x2. Let be M is a parameter, the graph 30x1 + 40x2 = M is a group of parallel lines with slope – 30/40. Some of these lines intersects the feasible region and contains many feasible solutions, whereas the other lines miss and contain no feasible solution. In Observe that the line 30x1 + 40x2 = M passes through the point D, which is the intersection of the lines 3x1 + 5x2 = 800 and 5x1 + 6x2 = 1100 and has the coordinates x1 = 170 and x2 = 40. Since D is the only feasible solution on this line the solution is unique. The value of M is 6700, which is the objective function maximum value. The optimum value variables are x1 = 170 and X2 = 40

LINEAR PROGRAMMING – SIMPLEX METHOD

The basic of simplex method is explained with the following linear programming problem.

PROBLEM 1

Maximize 60x1 + 70x2

Subject to:

2x1 + x2 ≤ 300

3x1 + 4x2 ≤ 509

4x1 + 7x2 ≤ 812

x1, x2 ≥ 0

From this equation

2x1+s3=300-x2

But x1=0.

Hence, in order that s3≥0 300-x2≥0 i.e.

x2≤300

Similarly consider the second equation i.e. 3x1 + 4x2 + s4 = 509

• Similarly consider the third equation i.e. 4x1 + 7x2 + s5 = 812
• From this equation 4x1+s5=812-7x2
• But x1=0
• . Hence, in order that s5≥0 812-7x2≥0 i.e. x2≤812/7
• Therefore the three equation lead to x2≤300, x2≤509/9, x2≤812/7 Thus x2=Min (x2≤300, x2≤509/9, x2≤812/7)
• it means x2=Min (x2≤300/1, x2≤509/9, x2≤812/7)=116 Therefore x2=116 If x2=116, you may be note from the third equation 7x2+s5=812 i.e. s5=0
• Thus, the variable s5 becomes non-basic in the next iteration. So that the revised values of the other two basic variables are S3=300-x2=184 S4=509-4*116=45 Refer to Table 1, we obtain the elements of the next Table i.e. Table 2

Let CB1, CB2, Cb3 be the coefficients of the basic variables in the objective function. For example in Table 2 CB1=0, CB2=0 and CB3=70. Suppose corresponding to a variable J, the quantity zj is defined as zj=CB1, Y1+CB2, Y2j+CB3Y3j. Then the z-row can also be represented as Zj-Cj

For example: z1 - c1 = 10/7*0+5/7*0+70*4/7-60 = -140/7 z5 – c5 = -1/7*0-4/7*0+1/7*70-0 = 70/7

1. Now we apply rule (1) to Table 2. Here the only negative zj-cj is z1-c1 = -140/7 Hence x1 should become a basic variable at the next iteration.

MBA-H2040 Quantitative Techniques for Managers 44 Note that zj – cj ≥ 0 for all j, so that the objective function can’t be improved any further. Thus, the objective function is maximized for x1 = 691/5 and x2=118/5 and The maximum value of the objective function is 9944.

THANK YOU