LINEAR PROGRAMMING

(BGM6DSE1B3)

1

INTRODUCTION TO OPERATIONS RESEARCH

Structure

​

• Introduction

​

• Origin and Definitions of Operations Research

​

• Scope of Operations Research

​

• Advantages of Operations Research

​

• Limitations of Operations Research

​

• Convex Set

​

• Check Your Progress

​

• Summary

​

• INTRODUCTION

Operations Research (O.R.) is a discipline that provides scientific methods for the purpose of solving real life problems that helps us in determining the best utilization of limited resources. Here we study about optimization techniques. In everyday life, we observe many situations of optimization around us. For example, suppose we want to maximize the profit or minimize the cost then maximization of the profit or minimization of cost is the optimization of profit/cost. In O.R., we obtain the optimal solution for decision making problems with the help of optimization techniques. This chapter contains origin, definitions and scope of Operations Research. In this unit, we also discuss the concept of convex sets.

• Objectives. The objective of these contents is to get familiar reader with Operations Research. After studying this unit, reader should be able to define/describe the following concepts like:

2

Operations Research Techniques

• What is Operations Research?
• Origin of Operations Research.
• Scope of operation research.
• Convex Set.

1.2. ORIGIN AND DEFINITIONS OF OPERATIONS RESEARCH

Origin: Operations Research came into existence and gained prominence during the World War II in Britain with the establishment of team of scientists to study the strategic and tactical problems of various military operations. Scientists of different disciplines were part of this team, their research on military operation soon find applications in other fields also. Now, it was started applying in the fields of industry, trade, agriculture, planning and various other fields of economy and named as

'Operations Research'. Hence the scientific methods and techniques of Operations Research became equally useful for the planners, economists, administrators, irrigation or agricultural experts and statisticians etc. The use of Operations Research has not limited to the Britain only. Many countries of the world had started using O.R. India was one of the few first countries who started using O. R. Regional Research Laboratory located at Hyderabad was the first Operations Research unit established in India during 1949. With the opening of this unit Operations Research in India came into existence. At the same time one more unit was set up in Defence Science Laboratory. In 1955, Operations Research Society of India was formed. Today, O.R. became a professional discipline and studied as a popular subject in Management institutes and school of Mathematics.

Definitions:

Operations Research can be defined simply as combination of two words operation and research where operation means some action applied in any area of interest and research imply some organized process of getting and analysing information about the problem environment. However, many scientists or experts has been defined O.R. in various ways but the opinions about the definitions of it have been changed according to the growth of the subject. So before defining O.R. it is important to see few definitions of it.

1. O.R. is a scientific method of providing executive departments with a quantitative basis for decisions regarding the operations under their control.

-Morse and Kimbal (1946)

2. O.R. is a scientific method of providing executive with an analytical and objective basis for decisions.

-P.M.S. Blackett (1948)

3. O.R. is the application of scientific methods, techniques and tools to problems involving the operations of system so as to provide these in control of the operations with optimum solutions to the problem.

-Churchman, Acoff, Arnoff (1957)

4. O.R. is a management activity pursued in two complementary ways one-half by the free and bold exercise of commonsense untrammeled by any routine, and other half by the application of a repertoire of well-established pre created methods and techniques.

-Jagjit Singh (1968)

Introduction to Operations Research 3

On the basis of all above opinions, Operations Research can be defined in more general and comprehensive way as:

“Operation research is a branch of science which is concerned with the application of scientific methods and techniques to decision making problems and with establishing the optimal solutions".

1.3. SCOPE OF OPERATIONS RESEARCH

Scope of O.R. is very wide in today’s world as it provides better solution to various decision-making problems with great speed and efficiency. Areas where methods/models developed in Operations Research can be applied are given here under:

1. In Agriculture:

With the explosion of population and consequent shortage of food, every country is facing the problem of optimum allocation of land to various crops in accordance with the climatic conditions, optimum distribution of water from different resources. Problems of agriculture production under various restrictions can be solved by applications of Operations Research techniques.

2. In Defence Operations:

Since Second World War operation research have been used for Defence operations with the aim of obtaining maximum gains with minimum efforts.

3. In Finance:

In these modern times, government of every country or every organisation wants to introduce such type of planning/policies regarding their finance and accounting which optimize capital investment, determine optimal replacement strategies, apply cash flow analysis for long range capital investments, formulate credit policies, credit risk. Techniques developed in O.R. can be applied for attaining above said things.

4. In Marketing:

A Marketing Administrator has to face many problems like production selection, formulation of competitive strategies, distribution strategies, selection of advertising media with respect to cost and time, finding the optimal number of salesmen, finding optimum time to launch a product. All such problems can be overcome using Operations Research Techniques.

5. In Personnel Management:

Every organization wants to make selection of personnel on minimum salary. It needs to find the best combination of workers in different categories with respect to costs, skills, age and nature of jobs. It also needs to frame recruitment policies, assign jobs to machines or workers.

6. In LIC:

Operations Research Techniques can be fruitfully applied in LIC offices as it enables the policy makers to decide the premium rates for various modes of policies.

7. In Research and Development:

In determination of the areas of concentration of research and development. It also helps in project selection.

4 Operations Research Techniques

O.R. helps in solving many other problems faced by public as well as private sectors such as the ones in economic and social planning, management of natural resources, energy, housing pollution control, waiting lines and administrative problems, insurance policies and many more.

• ADVANTAGES OF OPERATIONS RESEARCH

Following are certain advantages of Operations Research (OR):

• Operations Research helps decision –maker to take better and quicker decisions. It helps decision

–maker to evaluate the risk and results of all the alternative decisions. So, it improves the quality of decisions and makes the decisions more effective.

• Operation Research helps, in preparing future managers as it provides in-depth knowledge about a particular action.
• Operations Research develop models, which provides logical and systematic approach for understanding, Solving and controlling a problem.
• Operations research reduces the chances of failure as it provides many alternatives for one problem, which helps the management to choose the best decision. Even managers can evaluate the risks associated with each solution and can decide whether they want to go with the solution or not.
• It helps users in optimum use of resources. For example, linear programming techniques in Operations Research suggest most effective methods and efficient ways of optimality.
• It helps in finding the limitations and scope of an activity.
• Using this information, he can measure the performance of employees and can compare it with the standard performance. It modifies mathematical solutions before these are applied. Managers may accept or modify the mathematical solutions obtained using Operations Research techniques.
• It helps suggest alternative solutions for the same optimum profit if the management wants so.
• LIMITATIONS OF OPERATIONS RESEARCH
• Formulation of mathematical models may take into account all possible factors for defining a real- life problem and hence is difficult. As a result, the help of computers is required for the large number of cumbersome computations for such problems. This discourages small companies and other organisations from using O.R. techniques.
• Unquantifiable factors: Some problems may involve a large number of intangible factors such as human emotions, human relationship, etc. which cannot be quantified. Hence, the best solution cannot be determined for such problems because such factors have to be excluded.
• Dependence on experts: A specialist, who may be a mathematician or a statistician, is needed to understand the formulation of models, find solutions and recommend their implementation. Managers, who deal with such problems, may not have such specialisation. Managers, who deal with such problems, may not have such specialisation and hence the results may not be optimal.
• Model is abstraction of real-life situations and not the reality.
• Assumptions need to be made about the nature and importance of some factors in order to construct an Operation Research model.

Introduction to Operations Research

5

• A reasonably good solution without the use of Operation Research may be preferred by the management as compared to a slightly better solution provided by using Operation Research since it is very expensive in terms of time and money.

In the next chapter onwards, we shall introduce various O.R. techniques for obtaining optimal and feasible solutions. Before studying these techniques, you must familiar with some important basic concepts like convex sets and basic feasible solutions. Now, we will discuss these concepts.

• CONVEX SET

A region or a set K is convex if and only if for any two points on the set K, the line segment connecting these points lies entirely in K. Mathematically, . (x₁ , y₁ ) ∈ K .

(λx₁ + (1− λ)x₂ , λ y₁ + (1− λ) y₂ ) ∈ K ,0 ≤ 𝜆 ≤ 1

Where (𝜆𝑥₁ + ⁽1 − 𝜆⁾𝑥₂, 𝜆𝑦₁ + (1 − 𝜆)𝑦₂ ) gives all the points which lie on the line segment joining (𝑥₁, 𝑦₁) and (𝑥₂, 𝑦₂).

Example of a Convex Set

• Example.

Consider the region enclosed by OPQR. Let us denote it by K. It is convex as the line segment joining any two points in this region lies wholly within it. As an example, let us take two points A (1, 3) and B (4, 1).

Then all points on the line segment joining A and B are given by

(𝜆(1) + ⁽1 − 𝜆⁾4, 𝜆(3) + ⁽1 − 𝜆⁾(1) ) = (𝜆 + 4 − 4𝜆, 3𝜆 + 1 − 𝜆)

= (4 - 3𝜆, 1 + 2𝜆), 0 ≤ 𝜆 ≤ 1.

Here 𝜆 = 0 gives the point Q (4, 1) and 𝜆 = 1 gives the point P (1, 3). Other points on the line segment AB are given by

= (4 - 3 𝜆, 1 + 2 𝜆), where 0 <𝜆 < 1

P(5,0)

Fig. 1.1

O(0,0)

B(4,1)

A(1,3)

R(0,4)

Q(2,4)

6

Operations Research Techniques

For example, let us take 𝜆=0.1, 0.3, 0.5, 0.7, 0.9; then the corresponding points (after substituting the values of 𝜆 = 0.1, 0.3, 0.5, 0.7, 0.9) are;

(4 – 3(0.1), 1 + 2(0.1)), (4-3× 0.3, 1 + 2 × 0.3), (4- 3× 0.5, 1 + 2 × 0.5), (4-3× 0.7, 1 + 2 × 0.7), (4-3×

0.9, 1 + 2 × 0.9)

i.e., (3.7,1.2), (3.1 ,1.6), (2.5,2), (1.9, 2.4), (1.3, 2.8)

All these points clearly lie on the line and also in the region K.

Similarly, all other points on the line segment AB also lie inside the region K. Hence, the line segment AB lies in K.

Therefore, K is convex in this example.

Example of Non-Convex Set

1.6.2. Example.

Fig. 1.2

Consider the shaded region in Fig. 1.2, clearly the line segment joining two points do not lie wholly in the region and hence this is an example of non-convex set.

1.6.3. Example. Show that the set T = {(x, y): 𝑥² + 𝑦² ≤ 1} is a convex set.

Solution: Let us take any two points A (𝑥₁, 𝑦₁) and B (𝑥₂, 𝑦₂) in Fig. 1.3 such that:

𝑥² + 𝑦² ≤ 1, And𝑥² + 𝑦² ≤ 1.

1 1 2 2

Fig. 1.3

Now, the line segment joining A and B is the set

{𝜆𝑥₁ + ⁽1 − 𝜆⁾𝑥₂, 𝜆𝑦₁ + ⁽1 − 𝜆⁾𝑦₂: 0 ≤ 𝜆 ≤ 1}. Let 𝑢₁ = 𝜆𝑥₁ + (1 − 𝜆)𝑥₂, 𝑢₂ = 𝜆𝑦₁ + (1 − 𝜆)𝑦₂

(𝑥₁, 𝑦₁) .

. (𝑥₂, 𝑦₂)

Introduction to Operations Research

7

Therefore, all points on the line segment AB are given by (𝑢₁, 𝑢₂). Now, the line segment AB lies wholly in T if

1 2

𝑢² + 𝑢² ≤ 1

1 2

Since 𝑢² + 𝑢² = [𝜆𝑥₁ + (1 − 𝜆)𝑥₂]² + [𝜆𝑦₁ + (1 − 𝜆)𝑦₂]²

=𝜆²𝑥² + (1 − 𝜆)²𝑥² + 2𝜆⁽1 − 𝜆⁾𝑥₁𝑥₂ + 𝜆²𝑦² + (1 − 𝜆)²𝑦² + 2𝜆(1 − 𝜆)𝑦₁𝑦₂

1 2 1 2

= 𝜆^2[𝑥² + 𝑦^2] + (1 − 𝜆)^2[𝑥² + 𝑦^2] + 2𝜆⁽1 − 𝜆⁾[𝑥₁𝑥₂ + 𝑦₁𝑦₂]

1 1 2 2

We have

1 2

𝑢² + 𝑢² ≤ 𝜆² + (1 − 𝜆)² + 2𝜆⁽1 − 𝜆⁾[𝑥₁𝑥₂ + 𝑦₁𝑦₂]

...(1)

1 2 1 2

Now consider (𝑥₁𝑥₂ + 𝑦₁𝑦₂)² = 𝑥²𝑥² + 𝑦²𝑦² + 2𝑥₁𝑥₂𝑦₁𝑦₂

1 2 1 2 1 2 2 1 1 2 2 1

= 𝑥²𝑥² + 𝑦²𝑦² + 𝑥²𝑦² + 𝑥²𝑦² − 𝑥²𝑦² − 𝑥²𝑦² + 2𝑥₁𝑥₂𝑦₁𝑦₂

1 1 2 2

= (𝑥² + 𝑦²)(𝑥² + 𝑦²) − 𝑥₁𝑦₂⁽𝑥₁𝑦₂ − 𝑥₂𝑦₁⁾ − 𝑥₂𝑦₁⁽𝑥₂𝑦₁ − 𝑥₁𝑦₂⁾

1 1 2 2

= (𝑥² + 𝑦²)(𝑥² + 𝑦²) − ⁽𝑥₂𝑦₁ − 𝑥₁𝑦₂⁾²

≤ ⁽𝑥₂𝑦₁ − 𝑥₁𝑦₂⁾ ≤ 1

⇒ ⁽𝑥₁𝑥₂ + 𝑦₁𝑦₂⁾ ≤ 1

∴ From (1) and (2), we have

1 2

𝑢² + 𝑢² ≤ 𝜆² + ⁽1 − 𝜆⁾² + 2𝜆⁽1 − 𝜆⁾

Or

1 2

𝑢² + 𝑢² ≤ [𝜆 + (1 − 𝜆)]²

1 2

⇒ 𝑢² + 𝑢² ≤ 1

∴ T is convex set.

1.6.4. Example. Show that the set T = {(x, y): 0 ≤ y ≤ 5 when 0 ≤ x ≤ 2 and 3 ≤ y ≤ 5 when 2 ≤ x ≤ 7} is not a convex set.

Solution: Let us take two points A (1, 1) and B (5, 4) in the given region S.

8

Operations Research Techniques

Now, all the points on the line segment AB are given as

{ 𝜆𝑥₁ + ⁽1 − 𝜆⁾𝑥₂, 𝜆𝑦₁ + ⁽1 − 𝜆⁾𝑦₂, 0 ≤ 𝜆 ≤ 1}

= { 𝜆(1) + ⁽1 − 𝜆⁾5, 𝜆(1) + ⁽1 − 𝜆⁾4, 0 ≤ 𝜆 ≤ 1}

= {5-4𝜆 ,4 − 3𝜆, 0 ≤ 𝜆 ≤ 1}

2

Let us take one of these points and put 𝜆 = ¹. So, the point is

(5-4× ¹ , 4-3× ¹ ) = (5-2, 4-³ ) = (3, 2.5)

2 2 2

This point is on the line, but does not belong to the given set T since for y = 2.5, x should lie between 0 and 2 but here it is 3. Therefore, the given set is not convex.

1.6.5. Extreme Points of a convex set

A point (x, y) in a convex set K is called an extreme point if it is not possible to locate two distinct points in or on K so that the line joining them will include (x, y).

Mathematically, a point (x, y) is an extreme point of a convex set if it cannot be expressed as a convex combination of any two points (𝑥₁, 𝑦₁) and (𝑥₂, 𝑦₂) [for (𝑥₁, 𝑦₁) ≠ (𝑥₂, 𝑦₂)] in the set such that

𝑥 = 𝜆𝑥₁ + (1 − 𝜆)𝑥₂ and 𝑦 = 𝜆𝑦₁ + (1 − 𝜆)𝑦₂ , 0<𝜆 < 1

Remark:

1. The vertices of the polygons, which are convex sets, are the extreme points.
2. Every point on the circumference of the region containing the portion in and on the circle is an extreme point.

1.6.6. IMPORTANT DEFINITIONS

Solution

A set of values of the decision variables which satisfy the constraints of the given LPP is said to be a solution of that LPP.

Feasible Solution

A solution in which values of decision variables satisfy all the constraints and non-negativity conditions of an LPP simultaneously is known as feasible solution.

Infeasible Solution

A solution in which values of decision variables do not satisfy all the constraints and non-negativity conditions of an LPP simultaneously is known as infeasible solution.

Basic solution

Suppose there are m equations representing constraints (limited available resources) containing m + n variables in an allocation problem. The solution obtained by setting any n variables equal to zero and solving for the remaining m variables and the remaining n variables are non – basic variables.

𝑛

The maximum number of possible basic solutions is given by the formula 𝐶^𝑚+𝑛

Introduction to Operations Research 9

For example, if there are 2 equations in 3 variables, then the maximum number of possible basic solutions is

2

𝐶³ =

3!

2! ⁽3 − 2⁾!

= 3.

Basic Feasible Solution

A basic solution for which all the basic variables are non – negative is called the basic feasible solution. Further basic feasible solution are of two types:

Degenerate Solution

A basic feasible solution is known as degenerate if value of at least one basic variable iszero.

Non-Degenerate Solution

A basic feasible solution is known as non- degenerate if value of all basic variables are non-zero and positive.

Optimum Basic Feasible Solution

A basic feasible solution which optimizes i.e. maximise or minimise the objective function value of the given LPP is called optimum basic feasible solution.

Unbounded Solution

A solution in which value of the objective function of the given LPP increase/decrease indefinitely is called an unbounded solution.

1.6.7. Example. Determine all the basic feasible solutions of the equations: 2𝑥₁ + 6𝑥₂ + 2𝑥₃ + 𝑥₄ = 3

6𝑥₁ + 4𝑥₂ + 4𝑥₃ + 6𝑥₄ = 2

Solution: Here the maximum number of possible basic solutions is

2

𝐶⁴ =

2! 2! 2 × 2

4! 4 × 3 × 2

= = 6

We obtain as follows:

Setting 𝑥₁ = 0, 𝑥₂ = 0, we have 2𝑥₃ + 𝑥₄ = 3 and 4𝑥₃ + 6𝑥₄ = 2

⇒ 𝑥₃ = 2, 𝑥₄ = −1

Setting 𝑥₁ = 0, 𝑥₃ = 0, we have 6𝑥₂ + 𝑥₄ = 3 and 4𝑥₂ + 6𝑥₄ = 2

1

⇒ 𝑥₂ = ₂ , 𝑥₄ = 0

Setting 𝑥₁ = 0, 𝑥₄ = 0, we have 6𝑥₃ + 2𝑥₃ = 3 and 4𝑥₂ + 4𝑥₃ = 2

1

⇒ 𝑥₂ = ₂ , 𝑥₃ = 0

10

Operations Research Techniques

Setting 𝑥₂ = 0, 𝑥₃ = 0, we have 2𝑥₁ + 𝑥₄ = 3 and 6𝑥₁ + 6𝑥₄ = 2

8 7

⇒ 𝑥₁ = ₃ , 𝑥₄ = − ₃

Setting 𝑥₂ = 0, 𝑥₄ = 0, we have 2𝑥₁ + 2𝑥₃ = 3 and 6𝑥₁ + 4𝑥₄ = 2

7

⇒ 𝑥₁ = −2, 𝑥₄ = ₂

Setting 𝑥₃ = 0, 𝑥₄ = 0, we have 2𝑥₁ + 6𝑥₂ = 3 and 6𝑥₁ + 4𝑥₂ = 2

1

⇒ 𝑥₁ = 0, 𝑥₂ = ₂

Thus, all basic solutions of the given system of equations are;

1 8 7 7 1

2 2 3 3 2 2

(0, 0, 2, -1), (0, ¹ , 0, 0), (0, , 0, 0) , ( , 0, 0, − ) , (−2, 0, , 0) , (0, , 0, 0).

1

2

Here (0, , 0, 0) is repeated thrice and hence the basic solutions are

1 8 7 7

2 3 3 2

(0, 0, 2, -1),(0, , 0, 0) , ( , 0, 0, − ) , (−2, 0, , 0)

.

1

2

Of these solutions, the basic feasible solution is (0, , 0, 0) as in the other solutions, all decision variables

are not positive.

​

1.6.8. Exercises.

​

1 Find all basic solutions for the system of simultaneous equations:

2𝑥₁ + 3𝑥₂ + 4𝑥₃ = 5 and 3𝑥₁ + 4𝑥₂ + 5𝑥₃ = 6.

(Hint. The maximum number of possible basic solutions is

2

𝐶³ =

3!

2! ⁽3 − 2⁾!

= 3.

And no feasible solution)

2 Determine all the basic feasible solutions of the system of equations:

3𝑥₁ + 5𝑥₂ + 𝑥₃ = 15and 5𝑥₁ + 2𝑥₂ + 𝑥₄ = 10.

Further, discuss that whether the solution is degenerate or non-degenerate.

2

2!2! 2×2

(Hint. The maximum number of possible basic solutions will be C⁴ = ^4! = ^4×3×2 = 6.

And the possible solutions are

19 19

(0, 0, 15, 10), (0, 3, 0, 4), (0, 5, -10, 0), (5, 0, 0, -15), (2, 0, 9, 0) and (⁵⁰ , ⁴⁵ , 0, 0).)

Introduction to Operations Research

11

1.7. CHECK YOUR PROGRESS

1. Explain the concept and scope of Operations Research.
2. Explain the advantages and disadvantages of Operations Research.
3. Define the followings:

(i)

(ii)

(iii)

Feasible solution

Degenerate solution

Extreme points of a convex set.

1.8. SUMMARY

In this chapter, we have introduced Operations Research, its scope, advantages and limitations. We have observed that Operations Research is a very powerful method of getting the best out of limited resources. It finds applications in almost every field. Here, we explain concept of convex sets which is another important concept. We study feasible solution, basic solution, and basic feasible solution of a system of equations less in number than the number of decision variables. Such solutions are required to be obtained for finding out optimal solution of the given LPP.

2

LINEAR PROGRAMMING PROBLEMS

Structure

​

• Introduction

​

• Linear Programming Problem (LPP)

​

• Mathematical Formulation of LPP

​

• Graphical Method

​

• Canonical and Standard Form of LPP

​

• Check Your Progress.

​

• Summary

​

2.1. INTRODUCTION

In 1947, George Dantzig and his associates, while working with the US Air Force during World War II, developed this technique, primarily for solving military logistics problems. They observed that a large number of military programming/planning problems could be formulated as maximizing/minimizing a linear form of profit/cost function whose variable were restricted to values satisfying a system of linear constraints. In chapter 1, We have already discussed the concept of optimization and explained the basic feasible solution of linear programming problem.

In this chapter, we study linear programming problems (LPP), their mathematical formulation, objective function concept and graphical method. We use graphical method mainly for solving problems involving two variables. Linear programming can be applied to a variety of problems such as production, transportation, advertising and problems in public and private organizations, e.g., business, industry,

Simplex Method and Duality in Linear Programming

13

hospitals, libraries as also in education. In order to solve linear programming problems, we need to convert them into a canonical or standard form.

• Objectives. The objective of these contents is to provide some important concepts/results to the reader like:
• Linear programming problems, it’s applications and limitations.
• Mathematical formulation of linear programming problem.
• Graphical Method
• Canonical and Standard form of an LPP
• LINEAR PROGRAMMING PROBLEM (LPP)

We have already familiar with the concept of optimization. A mathematical programming is an optimization technique by which the maximum or minimum value of a function is determined under certain conditions. Mathematical programming in which constraints are expressed as linear equalities / inequalities is called linear programming.

We first introduce three basic components essential for the development of LP theory.

Decision Variables: The variables in terms of which the problem is defined.

Objective Function: A function which is to be maximised or minimised subject to the given constraints/limitations.

Constraints: There are always certain limitations on the use of resources that limit the degree to which an objective can be achieved. These limitations are known as constraints or restrictions. Constraints must be represented as linear equalities or inequalities in terms of decision variables.

Every organisation, big or small wants to find the best allocation of resources in order to optimize the objective function. We can use linear programming only if the following conditions are satisfied:

• Objective function should be well defined
• Objective function can be expressed as a linear function of the decision variables.
• There should be finite number of constraints and can be expressed as linear equalities or inequalities in terms of variables.
• Decision variables should be non- negative.
• Advantages and Limitations of an LPP

Linear programming methods are used in many fields including business and industry by almost all their departments such as production, marketing, finance etc. it’s some advantages are

• Helps in attaining the optimum use of resources i.e. maximise profit and minimise costs
• Improve the quality of decisions

There are many more advantages. In spite of having many advantages and wide areas of applications, there are some limitations as well. Following are certain limitations of linear programming:

• We can apply linear programming method only if relationships are linear.

14

Operations Research Techniques

• While solving LPP, it is possible that we will get non-integral values even for those decision variables which have only integral values.
• Constraints in the linear programming methods are written assuming all parameters are known and should be constant. However, in real problems, sometimes these are neither known nor constant.
• LP deals with the problems having single objective, whereas in real-life, there are many situations where we have to achieve multi-objectives.

• MATHEMATICAL FORMULATION OF LPP

In our daily life, there are many real-life situations where LP problems may arise and for using LPP methods/techniques to find a solution of such situations, it becomes necessary to present the given word problem into mathematical form correctly. The steps of mathematical formulation of LPP are summarized as follows:

• Identify the decision variable of the given problem.
• Formulate the objective function, which is to be maximised or minimised, as a linear function of the decision variables.
• Formulate the constraints and express them as linear inequalities or equalities in terms of decision variables.
• Introduce non-negative restrictions as negative values of the decision variables do not have any valid physical interpretation.

The steps of mathematical formulation of LPP are explained with the help of an example.

2.3.1. Example. A small-scale industry manufactures two products P and Q which are processed in a machine shop and assembly shop. Product P requires 2 hours of work in a machine shop and 4 hours of work in the assembly shop to manufacture while product Q requires 3 hours of work in the machine shop and 2 hours of work in the assembly shop. In one day, the industry cannot use more than 16 hours of machine shop and 22 hours of assembly shop. It earns a profit of rupees 3 per unit of product P and rupees. 4 per unit of product Q. Give a mathematical formulation of the problem as to maximise profit.

Solution: let x and y be the number of units of product P and Q, which are to be produced. Here x and y are the decision variables. Suppose Z is the profit function.

Since one unit of product P and one unit of product Q gives the profit of rupees 3 and rupees 4, respectively, the objective function is

Maximize Z =3x +4y

The requirement and availability in hours of each of the shops for manufacturing the products are tabulated as follows:

Simplex Method and Duality in Linear Programming

15

Total hours of machine shop required for both types of product = 2x+3y Total hours of assembly shop required for both types of product =4x+2y Hence, the constraints as per the limited available resources are:

2x+3y ≤ 16 and 4x+2y ≤ 22

Since the number of units produced for both P and Q cannot be negative, the non-negative restrictions are: x ≥ 0, y ≥ 0

Thus, the mathematical formulation of the given problem is:

Maximise Z = 3x + 4y Subject to the constraints

2x + 3y ≤ 16

4x + 2y ≤ 22

And non-negative restrictions x ≥ 0, y ≥ 0

2.3.2. Exercise. A company produces two types of items P and Q that require gold and silver. Each unit pf type P requires 4g silver and 1g gold while that od type Q requires 1g silver and 3g gold. The company produces 8g silver and 9g gold. If each unit of type P brings a profit of rupees 44 and that of type Q rupees 55, determine the number of units of each type that the company should produce to maximise the profit.

Answer. Let Z be the profit function. The mathematical formulation of the given problem is Max. Z = 44x + 55y

Subject to the constraints:

4x + y ≤ 8,

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

• GRAPHICAL METHOD

The graphical method is used to solve simple linear programming problems having two decision variables. For solving LPPs involving more than two decision variables, we use another method called simplex method. We discuss it in chapter 3.

The steps of graphical method for solving an LPP are as follows:

• Plot the graph corresponding to the given constraints.
• Determine the region for each given constraint.
• Determine the feasible region.
• Determine corner/extreme points.
• Examine corner/extreme points.

16 Operations Research Techniques

The following example explains steps of Graphical method.

2.4.1. Example.

The graphs are plotted for the equalities corresponding to the given inequalities for constraints as well as

restrictions. That is, we first draw the straight lines. For example, suppose one of the given inequalities is 2x+3y ≤ 6. Then, we first plot the graph for the equation 2x+3y = 6, which is straight line. For this, we take any two points on it join them.

For example, for x = 0, y = 6/3 = 2 and for y = 0, x = 6/2 = 3. So, we get the straight line shown in fig. 2.1.

Fig.2.1

First, we determine the region corresponding to each inequality. Let us consider the inequality 2x+3y ≤ 6 again. We can find the region on the graph satisfied by this inequality by substituting x = 0 and y = 0 in it. We get

2(0) + 3(0) ≤ 6 => 0 ≤ 6

which is correct. So, it is the region containing the point (0, 0). Hence, half plane shown in Fig. 2.2 by shading the region starting from the line towards the point (0, 0) is the graph of the given inequality.

Fig.2.2

Simplex Method and Duality in Linear Programming

17

Had the given inequality been 2x+3y≥6, then we would have shaded the region on the opposite side of the line. This is because on putting x=0, y=0 in the inequality, we get

2(0) + 3(0) ≥ 6 => 0≥6

which is not correct. Thus, the point (0, 0) does not satisfy the inequality and hence does not lie in the region. Thus, graph for the inequality 2x-3y ≥ 6 would, therefore, be as shown in Fig. 2.3.

Fig.2.3

In this example, we have used the point (0, 0) to determine which half plane corresponds to the given inequality. However, you can take any other point. But using (0, 0) is far easier. If the right-hand side of the given inequality is zero, using the point (0, 0) in it is meaningless. For example, suppose the given inequality is 2x-3y≥0.The plot of 2x-3y=0 is given in fig. 2.4. It is straight line passing through the origin. Using the point (0, 0) in the inequality 2x-3y ≥ 0, we get 2(0)-3(0) ≥ 0, i.e., 0 ≥ 0. So, we cannot decide which half plane is the region of the given inequality. Therefore, in this case, we use any other point, say (2, 0), on putting x=2, y=0 in the given inequality, we get

2(2)-3(0) ≥ 0 and 4 ≥ 0

which is true. Therefore, the half plane containing (2, 0) is the required region as shown in Fig.2.4. 2x-3y=0 or 3y=2x or y=2x/3

Fig.2.4

18 Operations Research Techniques

After determining the regions for each inequality, we find their common region. This is the region where all the given inequalities and non-negative restrictions are satisfied. This common region is known as feasible region or the solution set or polygonal convex set.

Now, we determine each of the corner points (vertices) of the polygon obtained in step 3. This is done either by plotting graphs on graph paper or by solving the two equations of the lines intersecting at that point.

Evaluate the value of the objective function at each corner point and determine the extreme point of the feasible region that has optimum objective function value.

According to the feasible region, we have different types of solution.

1. If the feasible region is bounded. The maximum of the values obtained for the objective function at the corner points is the optimum value when the objective function is of maximization form. The point

corresponding to this maximum value give the required values of the decision variables. The minimum

of the values obtained for the objective function at the corner points is the optimum value when the objective function is of minimization form. The point corresponding to this minimum value give the required values of the decision variables.

2. If the feasible region is not bounded. Then either there are additional hidden conditions which can be used to bound the region or there is no solution to the problem.
3. If the same optimum value exists at two of the vertices, then there are multiple solutions to the problem. Suppose these are two points (𝑥₁ , 𝑦₁) and (𝑥₂ , 𝑦₂). Then other solutions are given by the point as follow:

[First ordinate of first point × t + First ordinate of second point × (1- t ) , Second ordinate of first point × t + Second ordinate of second point × (1 – t)] where t is any real number lying between 0 and 1.

For example, let the objective function be Z = 3x – y and let A (2,1) and B (3,4) be the points which give the same optimum value of the objective function, i.e., Z = 5. Then other solutions which give the same value of the objective function are:

(2 × t + 3 × (1 – t), 1 × t + 4 × (1 – t)) Or (2t + 3 – 3t, t + 4 – 4t)

Or (3 – t, 4 – 3t), 0 ≤ t ≤ 1

Here t = 0 gives the point (3, 4), which is the point B and t = 1 gives the point (2, 1), which is the point A. The real values of t between 0 and 1 give other points which give the same optimum solution. One such point other than A and B is

( 3 - ¹ , 4 – 3 × ¹ ) , t = ¹ , i.e. , ( ⁵ , ⁵ )

2 2 2 2 2

You can verify that Z = 5 at the point ( ⁵ , ⁵ ) .

2 2

2.4.2. Example. A company produces two types of items P and Q that require gold and silver. Each unit pf type P requires 4g silver and 1g gold while that od type Q requires 1g silver and 3g gold. The company produces 8g silver and 9g gold. If each unit of type P brings a profit of rupees 44 and that

Simplex Method and Duality in Linear Programming

19

of type Q rupees 55, determine the number of units pf each type that the company should produce to maximise the profit. What is the maximum profit?

Solution. Let x be the number of units of type P to be produced and y be the number of units of type Q to be produced. It is given that:

Let Z be the profit function. The mathematical formulation of the given problem is

Max. Z = 44x + 55y Subject to the constraints:

4x + y ≤ 8, x + 3y ≤ 9,

x ≥ 0, y ≥ 0.

First of all, we plot the graphs for the equations:

4x + y = 8, x + 3y = 9 , x = 0 , y = 0 .

Since these equations are of straight lines, only two points are sufficient to plot the graphs ( see fig.2.5). For the line 4x + y = 8, we take the following two points:

Similarly, for the line x + 3y = 9, we take

Now, plotting the above lines, we get fig.2.5.

20

Operations Research Techniques

Fig.2.5

Note that x = 0 is the y axis and y = 0 is the x axis.

For plotting the graph of the inequality 4x + y ≤ 8 we put (0, 0) In it. We get 0 ≤ 8, which is true. Therefore, starting from the line 4x + y ≤ 8, we shall shade towards origin. Similarly, for the graph x + 3y ≤ 9, we shall shade towards origin. For the graph x ≥ 0. we shall shade towards right side of x = 0 and for the graph y ≥ 0, the region above y = 0 will be shaded.

Thus, the regions for the inequalities are shown in fig.2.6.

Fig.2.6.

You can see from the figure 2.6 that the coordinates of A, B, and D are (0, 0), (2, 0) and (0,3) respectively. The coordinates of the point C are obtained by solving the equations 4x + y = 8 and x + 3y = 9 as it is the point of intersection of the two lines represented by them. the solution of equations 4x + y = 8 and x + 3y

= 9 is given as

Simplex Method and Duality in Linear Programming

21

​

x = ¹⁵ and y = ²⁸ 11 11

So the vertices of ABCD are A(0,0) , B(2,0) , C(¹⁵ , ²⁸ ) and D (0,3).

11 11

We now obtain the values of Z = 44x + 55y at each of the vertices of ABCD as follows: At A (0,0) , Z = 44(0) + 55(0) = 0

At B(2,0) , Z = 44(2) + 55(0) = 88

At C(¹⁵ , ²⁸ ) , Z = 44( ¹⁵) + 55(²⁸) = 60 + 140 = 200

11 11 11 11

At D (0,3), Z = 44(0) + 55(3) = 165

Thus, the value of Z is maximum at C (¹⁵ , ²⁸ ) and the optimum solution is Max.Z = 200 when x = ¹⁵ and

11 11 11

y = ²⁸ .

11

• Exercises.
1. Maximise Z = 6X + 3Y subjects to the constraints 2X + 5Y ≤ 120, 4X + 2Y ≤ 80, X ≥ 0 , Y ≥ 0.
2. Maximise z = 3𝐱_𝟏 + 2𝐱_𝟐 subjects to the constraints

𝐱_𝟏- 𝐱_𝟐 ≤ 1, 𝐱_𝟏+ 𝐱_𝟐 ≥ 3,𝐱_𝟏≥ 0 , 𝐱_𝟐 ≥ 0

• Maximise Z = 𝐱_𝟏+ 𝐱_𝟐 subjects to the constraints

𝐱_𝟏+ 𝐱_𝟐 ≤ 1, •3𝐱_𝟏+ 𝐱_𝟐 ≥ 3, 𝐱_𝟏≥ 0 , 𝐱_𝟐 ≥ 0

4. A company manufactures two products X and Y, each of which requires three types of processing. The length of time for processing each unit and the profit per unit are given in the following table:

How many units of each product should the company manufacture per day in order to maximise profit?

5. A company produces soft drinks and has a contract requiring that a minimum of 80 units of chemical A and 60 units of chemical B go into each bottle of the drink. The chemicals are ^{available in a prepared mix from two different suppliers. The supplier X}1 ^{has a mix of 4 units of A and 2 units of B that costs rupees 10, and the supplier X}2 ^{has a mix of 1 unit of A and 1 unit of B that costs rupees 4. How many mixes from the company X}1 ^{and company X}2 ^should the company purchase to honour contract requirement and yet minimise cost?

22 Operations Research Techniques

• CANONICAL AND STANDARD FORM OF AN LPP

After formulating a linear programming problem, our next step is to solve it. You have learnt that linear programming problems can be represented as problems of maximisation or minimisation with constraints such as ≤ , =, ≥ . In order to develop a standard procedure for solving LPPs, we need to convert them into well - known form. We now discuss the General LPP along with these two forms. The canonical form is especially used in the duality theory and the standard form is used to develop the general procedure for solving any linear programming problem. In order to understand these forms, you also need to learn about slack and surplus variable.

• General Linear Programming Problem

Let us formulate the general linear programming problem. Let Z be a linear function of n basic variables

𝑋₁,𝑋₂, 𝑋₃,..., 𝑋_𝑛, which is to be maximised (or minimised). We write the problem as

Maximise (or minimise) Z = 𝐶₁𝑋₁ + 𝐶₂𝑋₂ + 𝐶₃𝑋₃ + ... +𝐶_𝑛𝑋_𝑛.... (1)

where 𝐶₁, 𝐶₂, 𝐶₃, ... , 𝐶_𝑛 are known constant termed as cost coefficients of basic variables.

Let (𝑎_𝑖𝑗) be an m×n real matrix of m×n constants 𝑎_𝑖𝑗’s and let {𝑏_1,, 𝑏₂, … , 𝑏_𝑚} be a set of constants such that

The linear function Z in equation (1) is called the objective function. The set of inequalities given in (2) is called constraints of a general LPP and the set of inequalities given in (3) are known as non – negative restrictions of a general LPP.

2.5.2. Slack and Surplus Variables

In general, if any linear programming problem, we have a constraint of the type

𝑎₁₁𝑥₁ + 𝑎₁₂𝑥₂ + ... + 𝑎_1𝑛𝑥_𝑛 ≤ 𝑏₁ where 𝑏₁≥ 0

Then this inequality can be converted into an equation by adding one non – negative variable 𝑠₁ to the left-hand side. This new variable is called a slack variable and the constraints are transformed into the following equation:

𝑎₁₁𝑥₁ + 𝑎₁₂𝑥₂ + ... + 𝑎_1𝑛𝑥_𝑛 + 𝑠₁ = 𝑏₁ where 𝑠₁≥ 0, 𝑏₁≥ 0

Thus, a non – negative variable subtracted from the left – hand side of less than or equal to (≤) type of a constraint that converts it into an equation is called a slack variable. The values of this

Simplex Method and Duality in Linear Programming

23

variable can be interpreted as the amount of unused resource.

Similarly, if in any linear programming problem, we have a constraint of the type

𝑎₁₁𝑥₁ + 𝑎₁₂𝑥₂ + ... + 𝑎_1𝑛𝑥_𝑛≥ 𝑏₁

Then this inequality can be converted into an equation by subtracting one non –negative variable 𝑠₁ from the left-hand side. This new variable is called a surplus variable. The value if this variable can be interpreted as the amount over and above the required minimum level.

Canonical Form

The characteristics of the canonical form are:

1. Objective function should be of maximization form. If it is given in minimization form, it should be converted into maximization form.
2. All the constraints should be of “≤ ” type, except for non- negative restrictions. Inequality of “ ≥ ” type, if any, should be changed to an inequality of the “ ≤ ” type.
3. All variables should be non-negative. If a given variable is unrestricted in sign (i.e., positive, negative or zero), it can be written as a difference of two non-negative variables. Suppose x is unrestricted in sign, then x can be written as x= 𝑥^′- 𝑥^′′ where 𝑥^′ ≥ 0, 𝑥^′′ ≥ 0.

2.5.3. Example. Express the following LPP in Canonical form:

Minimize Z = 2𝑥₁ + 𝑥₂ + 4𝑥₃ Subject to the constraints:

- 2𝑥₁ + 4𝑥₂≤ 4

𝑥₁ + 2𝑥₂ + 𝑥₃ ≥ 5 2𝑥₁ + 3𝑥₃≤ 2

𝑥₁,𝑥₂ ≥ 0 and 𝑥₃ is unrestricted in sign

Solution: Here, the objective function is of the minimisation form. We rewrite it in the maximisation form as follows:

Minimise Z = 2𝑥₁ + 𝑥₂ + 4𝑥₃

Thus, we have to maximise -Z = -2𝑥₁ - 𝑥₂ - 4𝑥₃. So the problem becomes, Maximise 𝑍^′= -2𝑥₁ - 𝑥₂ - 4𝑥₃. where 𝑍^′ = -Z

Now the second constraints is of the type “≥”. Hence to convert it into type “≤”, we multiply the inequality by -1 and write

- 𝑥₁ - 2𝑥₂ - 𝑥₃≤ -5

Other constraints are already in the desired form. But 𝑥₃is unrestricted in sign. So, we write

𝑥₃ = 𝑥^′ − 𝑥^′′ , where 𝑥^′ ≥ 0, 𝑥^′′≥ 0.

3 3 3 3

24

Operations Research Techniques

The canonical form of the given problem, therefore, is

3 3

Maximise 𝑍^′= -2𝑥₁ - 𝑥₂ – 4(𝑥^′ − 𝑥^′′), where 𝑍^′ = -Z

Subject to the constraints:

- 2𝑥₁ + 4𝑥₂≤ 4

3 3

- 𝑥₁ - 2𝑥₂ – (𝑥^′ − 𝑥^′′)≤ -5

3 3

2𝑥₁ + 3(𝑥^′ − 𝑥^′′)≤ 2

3 3

𝑥₁ ≥ 0,𝑥₂ ≥ 0, 𝑥^′ ≥ 0, 𝑥^′′ ≥ 0

Standard Form:

The characteristics of the Standard Form are:

1. The objective function should be in the maximization form as we explained in canonical form.
2. The right-side element of each constraint should be non- negative. If it is negative, we multiply the inequality by -1.
3. All constraints should be expressed in the form of equations, except for the non- negative restrictions by augmenting slack or surplus variables.

2.5.4. Example. Express the following LPP in the standard form:

Minimise Z = 2𝑥₁+ 𝑥₂ + 4𝑥₃ subject to the constraints:

-2𝑥₁ + 4𝑥₂ ≤ 4

𝑥₁ + 2𝑥₂ + 𝑥₃ ≥ 5 2𝑥₁ + 3𝑥₃ ≤ -2

𝑥₁ ≥ 0, 𝑥₂ ≥ 0, 𝑥₃ ≥ 0.

Solution: The objective function should be of maximization form, i.e. we have to Maximise Z’ = -2𝑥₁ - 𝑥₂ - 4𝑥₃ , where Z’ = -Z

subject to the constraints:

-2𝑥₁ + 4𝑥₂ ≤ 4

𝑥₁ + 2𝑥₂ + 𝑥₃ ≥ 5

-2𝑥₁ - 3𝑥₃ ≤ 2[ ∵ Right side should be non- negative]

𝑥₁ ≥ 0 , 𝑥₂ ≥ 0 , 𝑥₃ ≥ 0 .

Simplex Method and Duality in Linear Programming

25

Now the inequalities are to be converted to equations. Note that the first and third inequalities are of the type “less than or equal to (≤)”.

Therefore, a slack variable is to be added to the left side of each of these inequalities. The second inequality is of the type “more than or equal to (≥) ” . So, a surplus variable is to be subtracted from the left side of this inequality.

Thus, a standard form of the given LPP is

Max.Z’ = = -2𝑥₁ - 𝑥₂ - 4𝑥₃ + 0𝑠₁ + 0𝑠₂ + 0𝑠₃ , where Z’ = -Z subject to the constraints:

-2𝑥₁ + 4𝑥₂ + 𝑠₁ = 4

𝑥₁ + 2𝑥₂ + 𝑥₃ - 𝑠₂ = 5

-2𝑥₁ - 3𝑥₃ + 𝑠₃ = 2

𝑥₁ ≥ 0 , 𝑥₂ ≥ 0 , 𝑥₃ ≥ 0 , 𝑠₁ ≥ 0 , 𝑠₂ ≥ 0 , 𝑠₃ ≥ 0 .

2.5.5. Exercise.

1. Express the following LPP in
1. Canonical form
2. Standard Form Minimise Z = 𝑥₁ - 2𝑥₂ + 𝑥₃

subjects to the constraints:

2𝑥₁ + 3𝑥₂ + 4𝑥₃ ≥ -4

3𝑥₁ + 5𝑥₂+ 2𝑥₃ ≥ 7

𝑥₁ ≥ 0 , 𝑥₂ ≥ 0 , 𝑥₃ ≥ 0 .

2. Max. Z = 5x + 7y subjects to the constraints:

12x + 12y ≤ 840 => x + y ≤ 70

3x + 6y ≤ 300 => x + 2y ≤ 100

8x + 4y ≤ 480 => 2x + y ≤ 120 x ≥ 0 , y ≥ 0

26

Operations Research Techniques

Answer.

Fig.2.8.

The maximum value of Z is 410 at C(40,30) , i.e., at x = 40 , y = 30.

3. Minimise z = 10𝑥₁ + 4𝑥₂ subjects to the constraints

4𝑥₁ + 𝑥₂ ≥ 80

2𝑥₁ + 𝑥₂≥ 60

𝑥₁≥ 0 , 𝑥₂ ≥ 0

Answer.

Fig.2.9.

Simplex Method and Duality in Linear Programming

27

The maximum value of Z is 260 at B (10,40), i.e. 𝑥₁ = 10 and 𝑥₂ = 40.

Note: Had the objective function been of maximization form, the problem would have the unbounded solution. This is because the values of 𝑥₁ and 𝑥₂ could be increased beyond any limit, which would result in higher value of Z with no upper bound.

​

• CHECK YOUR PROGRESS

​

• What is linear programming? What are its major advantages and limitations?

​

• What is meant by feasible solution of an LP problem?

​

• SUMMARY

In this chapter, we introduced the concept of LPP and explain how these are formulated mathematically. We define objective function and graphical method of obtaining optimum value which is used to solve linear programming problems having two decision variables. Here, we study about feasible region/ solution set in detail. Also, we discuss canonical and standard form of an LPP as to solve LPP we need to convert them into a canonical or standard form.

3

SIMPLEX METHOD AND DUALITY IN LINEAR PROGRAMMING

Structure

​

• Introduction

​

• Simplex Method

​

• Artificial Variable Techniques

​

• Big-M Method

​

• Two-Phase Method

​

• Degeneracy

​

• Duality in Linear Programming

​

• Check Your Progress

​

• Summary

​

3.1. INTRODUCTION

In chapter 2, we have studied the graphical method of solving linear programming problems and learnt how to express a linear programming problem in canonical and standard forms. As we know that the graphical method can be used only to solve the problems involving two decision variables and most of the real-life problems when mathematically formulated have more than two variables. For more than two decision variables, methods based on the concept of slack or surplus variables are used.

Simplex Method and Duality in Linear Programming

29

In this chapter, first we shall discuss the Simplex method for solving the linear programming problems involving more than two decision variables. After learning the procedure of simplex method, we discuss artificial variable techniques (Big-M Method and Two-Phase Method) for solving LPP and in last we shall discuss the concept of degeneracy in linear programming.

• Objectives. The objective of these contents is to provide some important concepts/methods to the reader like:
• Simplex Method.
• Artificial Variable Techniques.
• Big-M and Two-Phase Method for Solving LPP Involving Artificial Variable(s).
• Degeneracy.

3.2. SIMPLEX METHOD

Simplex method was developed by G B Dantzig in 1947. The method is an iterative or step by step procedure by which one can obtained a new basic feasible solution from a given initial basic feasible solution. In this method, the value of the objective function improves with each solution and the optimum solution is achieved in a finite number of steps.

Suppose we have to optimize (maximiseor minimise) Z, a linear function of n basic variables

𝑋₁, 𝑋₂, … , 𝑋_𝑛. The LPP is written as:

Maximise Z = 𝐶₁𝑋₁ + 𝐶₂𝑋₂ + ⋯ + 𝐶_𝑛𝑋_𝑛

subject to the constraints:

𝑎₁₁𝑥₁ + 𝑎₁₂𝑥₂ + ⋯ + 𝑎_1𝑛𝑥_𝑛 ≤ 𝑏₁

𝑎₂₁𝑥₁ + 𝑎₂₂𝑥₂ + ⋯ + 𝑎_2𝑛𝑥_𝑛 ≤ 𝑏₂

∙ ∙ ∙ ∙

∙ ∙ ∙ ∙

𝑎_𝑚1𝑥₁ + 𝑎_𝑚2𝑥₂ + ⋯ + 𝑎_𝑚𝑛𝑥_𝑛 ≤ 𝑏_𝑚

… (1)

(2)

and 𝑥_𝑗 ≥ 0 for all j= 1,2, …, n … (3)

where the constants 𝐶₁, 𝐶₂, … , 𝐶_𝑛 are the cost coefficients of decision variables. Let (𝑎_𝑖𝑗) be m×n real matrix and {𝑏₁, 𝑏₂ , … , 𝑏_𝑚} be a set of constants.

The linear function Z gives in equation (1) is called the objective function. The set of inequalities gives in equation (2) is called constraints of LPP and the inequalities gives in equation (3) are known as non- negative restrictions of LPP (which means that all 𝑥_𝑗 values are non –negative)

Let us explain the step by step procedure for solving the LPP by the Simplex method.

Step 1: Convert the LPP into standard form by adding slack variables

We convert the given LPP into standard form by adding slack variables 𝑠₁, 𝑠₂, … , 𝑠_𝑚.

30

Operations Research Techniques

Maximise Z = 𝐶₁𝑋₁ + 𝐶₂𝑋₂ + ⋯ + 𝐶_𝑛𝑋_𝑛 + 0𝑠₁ + 0𝑠₂ + ⋯ + 0𝑠_𝑚

subject to the given constraints:

𝑎₁₁𝑥₁ + 𝑎₁₂𝑥₂ + ⋯ + 𝑎_1𝑛𝑥_𝑛 + 𝑠₁ = 𝑏₁

𝑎₂₁𝑥₁ + 𝑎₂₂𝑥₂ + ⋯ + 𝑎_2𝑛𝑥_𝑛 + 𝑠₂ = 𝑏₂

… (4)

∙

∙

∙

∙

∙

∙

∙

∙

… (5)

𝑎_𝑚1𝑥₁ + 𝑎_𝑚2𝑥₂ + ⋯ + 𝑎_𝑚𝑛𝑥_𝑛 + 𝑠_𝑚 = 𝑏_𝑚

and 𝑥_𝑗 ≥ 0 𝑎𝑛𝑑 𝑠_𝑖 ≥ 0 for all i =1, 2,…, m and j= 1,2, …, n

Step 2: Construct the initial simplex table.

The initial simplex table is formed as follows:

… (6)

Table 1: Initial Simplex Table

Step 3: Test for optimality

Calculate the values of 𝑐_𝑗 − 𝑧_𝑗 , the nature of the solution could be any one of the following:

1. If all 𝑐_𝑗 − 𝑧_𝑗 ≤ 0, the solution under test is optimal solution.
2. If at least one value of 𝑐_𝑗 − 𝑧_𝑗is positive and corresponding to the most positive

𝑐_𝑗 − 𝑧_𝑗 ,all the elements of the column 𝑋_𝑗are negative or zero, the solution under test is an unbounded solution.

3. Suppose at least one value of 𝑐_𝑗 − 𝑧_𝑗 is positive. Suppose the most positive value is, say 𝑐₃ − 𝑧₃and at least one entry in the column of 𝑋₃ is positive. Then the solution under test is not optimal.

Simplex Method and Duality in Linear Programming

31

Step 4: Select incoming variable to enter the basis

If the solution is not optimal then we look for most positive entry and it could be any of (𝑐_𝑗 − 𝑧_𝑗). In this case, we proceed as follows to obtain the optimal solution:

1. Let 𝑋_𝑟 be the variable which corresponds to the most positive value of 𝑐_𝑗 − 𝑧_𝑗. This variable is called the incoming variable.
2. The column to be entered is called the key or pivot column.

Step 5: Test for feasibility (variable to leave the basis)

After finding the incoming variable, we determine the outgoing variable. For this we proceed as follow:

1. We divide the value of the Quantity (Qty) column be the corresponding positive values in the column

𝑋_𝑟. These ratios are called Replacement Ratios (RR). Note that we do not consider the negative values in the column of 𝑋_𝑟 for calculating RR. Then we select the minimum RR. The basic variable corresponding to this value of the RR is called the outgoing variable. It is called outgoing variable because it is removed (goes out) from the next simplex table. The row selected in this manner is called key or pivot row.

2. The element that lies at the intersection of the key row and key column is called the key element or leading element or pivot element.

Step 6: Finding the new solution

1. We convert the key element to unity by dividing all entries in the row by the key element itself.
2. In the next step, we would like that the values of all other elements in the column corresponding to key element are zero. For this we carry out suitable operations on each row using the row containing the

key element.

Step 7: Repeat the procedure

Go to step 3 and repeat the procedure until all entries in the 𝑐_𝑗 − 𝑧_𝑗 are either negative or zero i.e. we repeat the procedure until either an optimal solution is obtained or there is an indication of unbounded solution.

The following example illustrate the simplex method:

3.2.1. Example. Maximise Z=3𝑥₁ + 2𝑥₂

subject to the constraints:

𝑥₁ + 𝑥₂ ≤ 4

𝑥₁ − 𝑥₂ ≤ 2

𝑥₁ ≥ 0, 𝑥₂ ≥ 0

Solution: Step 1: First we convert the given LPP into standard form by adding slack variables 𝑠₁ and 𝑠₂.

Maximize Z = 3𝑥₁ + 2𝑥₂ + 0𝑠₁ + 0𝑠₂

subject to the constraints:

32 Operations Research Techniques

𝑥₁ + 𝑥₂ + 𝑠₁ = 4

𝑥₁ − 𝑥₂ + 𝑠₂ = 2

𝑥₁, 𝑥₂, 𝑠₁, 𝑠₂ ≥ 0

Step 2: We now construct the initial simplex table (Table 2: Initial Simplex Table)

Note: Columns corresponding to the basic variables in initial simplex tables in the simplex method form an identity matrix. For example, in Table 2, the basic variables are 𝑠₁ and 𝑠₂ and their coefficients in the constraints form identity matrix.

The value of Z in column of Table2 is obtained from the equation Z=^∑ 𝑐_𝑗 𝑏_𝑗, j=1, 2

The values of 𝑧_𝑗′𝑠 are obtained from the equation

𝑖=1

𝑧_𝑗 = ^∑𝑚 𝑐_𝑖𝑎_𝑖𝑗, where m is the number of rows. In this example m=2

Next, we obtain 𝑐_𝑗 − 𝑧_{𝑗 ,} known as net-evaluations. These are 3,2,0,0.

Thus, the table takes the following form (Table3):

Table 3: Simplex Table

Simplex Method and Duality in Linear Programming

33

Step 3: Test for optimality

Since all 𝑐_𝑗 − 𝑧_𝑗 ≥ 0, therefore the current solution is not optimal.

Step 4: Now we select incoming and outgoing variable.

For this, we select the most positive value of 𝑐_𝑗 − 𝑧_{𝑗 ,}which is 3 in this case.

This corresponds to the variable 𝑥₁ which becomes the incoming variable. We shall enter it as a basic variable in the next simplex table.

Step 5: One of the variables 𝑠₁, 𝑠₂ will now be the outgoing variable which would be replaced by 𝑥₁. To find out which one of these variables (𝑠₁𝑜𝑟 𝑠₂) is the outgoing variable, we determine the replacement ratio (RR). Recall that RR for any row is obtained by dividing the value of Quantity column by the corresponding value of the Incoming variable for that particular row. For example, consider the first row in Table 3. The value of Quantity in the first row is 4 and the value of the incoming variable 𝑥₁ in this row is 1.

1

1

Therefore, RR for the first row is ⁴ . For the second row, Quantity is 2 and value of 𝑥 is 1. Hence, RR is

² . RR is shown in the last column of the next simplex table (Table4).

1

The outgoing variable is the variable for which RR minimum. In Table 4, RR in the second row is minimum. It corresponds to 𝑠₂ and hence 𝑠₂ is the outgoing variable.

The element which lies at the intersection of the column of incoming variable (𝑥₁) and the row of the outgoing variable (𝑠₂) is called the key element. Here it is 1 and is enclosed by the rectangle as shown in

Table4. Incoming variable Key element

1

The objective function Z=0 at 𝑥₁ = 0 𝑎𝑛𝑑 𝑥₂ = 0 (since 𝑥₁ 𝑎𝑛𝑑 𝑥₂ do not appear in the column of basic variables, these are non-basic variables. The values of non-basic variables are taken as zero). This is the initial solution, which we shall improve.

Step 6: Now, we form the next simplex table to find the adjacent vertex, i.e., the improved solution. The steps for forming this table are explained below:

34 Operations Research Techniques

1. The initial simplex table (Table 4) has revealed that 𝑥₁ is an incoming variable which will enter in place of 𝑠₂, the outgoing variable. The cost coefficient of 𝑠₂will also be replaced by the cost coefficient of 𝑥₁ in “Profit / Unit” column. In this case its value is 3. Therefore, now the simplex table takes the form of Table 5. Other entries of the table will be filled up as explained in point (b).
2. Since 𝑥₁ has entered as a basic variable, the coefficients of 𝑥₁ along with 𝑠₁ should form an identity

matrix; i.e., the column corresponding to 𝑥₁ should be (⁰). Thus, we have to make the key element

1

unity and the other element zero. Note that it is already unity in this case (Table 4). Had it been any

number other than unity, we would have divided the row containing leading element by the leading element itself, excluding the elements of the column “Profit / Unit”. So, the table takes the form

Table 5: Simplex Table

c) Now, we have to make the other element in the column of key element (𝑥₁ ) zero. In this case, itsvalue is 1 (𝑎₁₁ = 1). For this, we multiply the row of the key element (excluding profit / unit) by negative of the element 𝑎₁₁ (in this case) and add it to the first row.

This row operation is shown below:

Thus, the sum of the rows is the new first row (excluding profit/ unit), which replaces the first row of Table5. We get Table 6 as follows:

Table 6: Simplex Table

Note: Now the matrix for the basic variables 𝑠₁ and 𝑥₁ in the Table 6 is the identity matrix.

Simplex Method and Duality in Linear Programming

35

d) Next, we calculate 𝑧_𝑗 and 𝑐_𝑗 − 𝑧_𝑗. The resulting simplex table is given below:

Table 7: Simplex Table

2

Here Z=6 at 𝑥₁ = 2 (see the value in the Quantity column) and 𝑥₂=0 (𝑥₂ being non-basic variable).

In Table 7, the incoming variable is 𝑥₂ corresponding to the most positive value of 𝑐_𝑗 − 𝑧_𝑗 = 5. The key element is 2. We find the RR by dividing the elements in the Quantity column by the corresponding elements in the column of the incoming variable 𝑥₂ and ignore the negative or zero values. So, in this case, there will be only one RR and that will be considered as minimum RR. This implies that 𝑠₁ is the outgoing variable. If none of the elements in the column of incoming variable is positive, then the given LPP has an unbounded solution and we will stop there.

Step 7: Repeat the procedure

1. For the next simplex table, 𝑥₂ will enter in place of 𝑠₁ as a basic variable and accordingly we shall write the cost coefficient of 𝑥₂ in the LPP as the value for the column of profit / unit, i.e.,2. The element 2 enclosed in a rectangle in Table 7 is the key element. So, we shall divide the row containing the key element by the key element itself, i.e., by 2, excluding the values in the column of profit / unit. Thus, we get Table 8:

Table 8: Simplex Table

36 Operations Research Techniques

Now the coefficients of 𝑥₂ 𝑎𝑛𝑑 𝑥₁ have to form an identity matrix, i.e., the column corresponding to 𝑥₂

should be (¹) . We have already made the key element unity. Now, to make the second element , (i.e., -

0

1) in its column as zero, we just add the first row corresponding to 𝑥₂, to the second row of Table 8

excluding the values in the column of profit / unit as follows:

We write the sum as above as the second row, excluded profit / unit as shown in Table 9. Then we obtain Z, 𝑧_𝑗, 𝑎𝑛𝑑 𝑐_𝑗 − 𝑧_𝑗 as explained in Step 1(iii) and (iv) and also in Step 2(c) . The complete resulting simplex table is given below:

Table 9: Simplex Table

Now, in Table 9 none of the net-evaluation, i.e., the values of 𝑐_𝑗 − 𝑧_𝑗 are positive. Therefore, the optimum solution is attained for 𝑥₁ = 3 𝑎𝑛𝑑 𝑥₂ = 1, the values of 𝑥₁ 𝑎𝑛𝑑 𝑥₂ in the Quantity column of Table 11.

At this stage, it is necessary to check whether any of the non-basic variables (other than those appearing in the first column, i.e., the column with caption “Basic Variables”, i.e., 𝑥₁ 𝑎𝑛𝑑 𝑥₂ in Table 9) has value 0 in the net-evaluation row. If “yes”, then the LPP has multiple optimum solutions. If “not”, then we stop here concluding that the unique solution. In this example, it is given by

Max. Z= 11 at 𝑥₁ = 3 𝑎𝑛𝑑 𝑥₂ = 1 (see the values in the Quantity column)

Note: It should be noted that in the initial simplex table (Table 2), 𝑐_𝑗 − 𝑧_𝑗 is same as 𝑐_𝑗. Also 𝑐_𝑗 − 𝑧_𝑗

corresponding to the column of unit matrix are always zero. So, there is no need to calculate them.

We discuss the case of multiple optimum solutions in the next example.

3.2.2. Example. Max. Z= 6x+3y Subject to the constraints:

2x + 5y ≤ 120

Simplex Method and Duality in Linear Programming

37

2x + y ≤ 40

x ≥ 0, 𝑦 ≥ 0

Solution: Rewriting the given LPP in the standard form, we have Max. Z = 6x +3y +0𝑠₁ + 0𝑠₂

subject to the constraints:

2x + 5y+ 𝑠₁ = 120

2x + y + 𝑠₂ = 40

x, 𝑦, 𝑠₁, 𝑠₂ ≥ 0

We form the initial simplex table (Table1) as explained in Example 1:

Table 1: Initial Simplex Table

2

Note from Table 1 that 𝑐_𝑗 − 𝑧_𝑗=6 is maximum for x and RR is minimum for 𝑠₂. Therefore, x is the incoming variable and 𝑠₂ is the outgoing variable. Then in the second simplex table, x will enter in place of 𝑠₂ as a basic variable. Profit / unit will be written accordingly. The key element is 2 and enclosed by the rectangle in Table 1. To make the key element unity, we divide the second row in Table 1 by 2 excluding the values of the column of profit / unit. So, we get Table 2 as follows:

Table 2: Simplex Table

Now, we have to make the other element in column of x zero so that the coefficients of

𝑠₁ and x form the identity matrix. So, we multiply the second row of Table 2 (excluding the elements in the column of profit /unit) by the negative of the element (𝑎_𝑖𝑗) in the row of 𝑠₁ and column of x in Table

1, i.e., by -2 and then add it to the first row of the Table 2 as follows

38

Operations Research Techniques

2 5 1 0

-2 -1 0 -1

First row of Table 2→ 120 Second row of Table 2→ -40 (on multiplying by -2)

Sum of the rows 80

0 4 1 -1

We also calculate Z, 𝑧_𝑗, 𝑎𝑛𝑑 𝑐_𝑗 − 𝑧_𝑗. So, the resulting completed simplex table is as follows:

Table 3: Simplex Table

As none of the net-evaluations is positive, the optimum solution is attained. The optimum solution is Max. Z = 120 when x = 20 (see the value in the Quantity column),

Y = 0 (since y is non-basic variable)

But we also note that the non-basic variable y has zero value in its net-evaluation row in Table 3. Therefore, the given LPP has multiple optimal solutions. To find another optimal solution, let us find another vertex at which Max. Z = 120.

So, another simplex table has to be formed. Here, instead of selecting the column corresponding to the most positive element in the net-evaluation row, we select the column of non-basic variable which has zero in the net-evaluation row, i.e., the column of y shown in Table 4.

Table 4: Simplex Table

Simplex Method and Duality in Linear Programming

39

Note that in Table 4, the key element is 4 and the minimum RR corresponds to 𝑠₁. So, 𝑠₁ is the outgoing variable and y is the incoming variable. We form the next simplex table (Table 5) following the steps explained for forming Table 3. The resulting simplex table (Table 5) is given as follows:

Table 5: Simplex Table

You should verify all entries of Table 5 before studying further. Note that for forming Table 5, we have first divided the first row by the value of key element to make the key element unity.

Then we obtain the second row of Table 5 as follows: Second row of Table 4→ 20 1 1/2 0 1/2

From the above simplex table (Table 5), we find that Max. Z = 120 at (10,20) also (see the value of x = 10, y = 20 in the Quantity column).

So, we have two vertices at which the maximum value of Z is the same, i.e., 120. So, the other solutions of the LPP are obtained as follows:

First ordinate of other solutions = t × (First ordinate of first /vertex)

+ (1-t)× (First ordinate of first / vertex) Second ordinate of other solutions = t × (Second ordinate of first /vertex)

+ (1-t)× (Second ordinate of first / vertex) So, the other solutions are given as

First ordinate = t × 10 + ⁽1 − 𝑡⁾ × 20 = 10𝑡 + 20 − 20𝑡 = 20 − 10𝑡

Second ordinate = t × 20 + ⁽1 − 𝑡⁾ × 0 = 20𝑡

The other solutions are (20-10t, 20t), 0≤ 𝑡 ≤ 1.

40

Operations Research Techniques

3.2.3. Exercises.

Solve the following LPPs by the Simplex method:

1. Maximise Z = 2𝑥₁ + 4𝑥₂

subject to the constraints:

𝑥₁ + 2𝑥₂ ≤ 5

𝑥₁ + 𝑥₂ ≤ 4

𝑥₁ ≥ 0, 𝑥₂ ≥ 0

Answer. Max. Z = 10 at the two vertices (0,5^⁄2 ) and (3, 1).Max. Z = 10at many other points also which are given as (3 – 3t, 1+3𝑡^⁄2 ), 0 ≤ 𝑡 ≤ 1.

2. Maximise Z = 100𝑥₁ + 60𝑥₂ + 40𝑥₃

Subject to the constraints:

𝑥₁ + 𝑥₂ + 𝑥₃ ≤ 100 10𝑥₁ + 4𝑥₂ + 5𝑥₃ ≤ 500

𝑥₁ + 𝑥₂ + 3𝑥₃ ≤ 150, 𝑥₁ , 𝑥₂ , 𝑥₃ ≥ 0

Answer. Z=22000/3 at 𝑥₁ = 100/3, 𝑥₂ = 200/3,𝑥₃ = 0

3.3. ARTIFICIAL VARIABLE TECHNIQUES

After converting the given LPP into standard form, sometimes we observe that some of the variables in the standard form are surplus variables and the corresponding column vectors do not provide unit vectors for the initial basis and hence the column which form unit (identity) matrix are missing in the initial simplex table. Such a situation is usually observed if the constraints equation(s) is (are) of the type “≥”. In order to have unit vectors in the basis, we introduce new type of variable (s) known as artificial variable(s). These are added to act as basic variable. They have no physical meaning and are used only to initiate the solution so that the simplex procedure may be adopted as usual till the optimal solution is obtained. The artificial variables are eliminated from the simplex table as and when they become non- basic variables. This technique is called the artificial variable technique for solving LPP. There are two methods for solving LPPs involving artificial variables.

1. Big-M or Method of Penalties or Charne’s Method
2. Two-Phase Method

3.4. BIG-M METHOD

Big-M Method is used for removing artificial variable(s) from the basis. It is also known as Penalty method or Charne’s Method. In this method, the objective function coefficients impose a huge and ^{henceunacceptable penalty. In case of maximisation, the objective function is modified by adding –MA}1^{, where M is arbitrary large and A}1 ^{is an artificial variable. If there are two artificial variables A}1^{and A}2, ^{then -MA}1^-MA2 ^{is added to the objective function. Similar treatment is done for more artificial variables.}

Simplex Method and Duality in Linear Programming

41

The logic behind taking the coefficient as –M is that we should never get the net-evaluation positive in the column of the artificial variable, i.e., the artificial variable should not enter again as a basic variable. ^{M is very big and hence adding –MA}1 ^{is the penalty to the objective function. Hence this method is called} penalty method. Though –M is big penalty, it does not affect the objective function. This is because the ^{value of artificial variable should come out to be zero so that –MA}1 ^{becomes zero. If the artificial variable} remains as a basic variable till the final simplex table, then its value in the quantity column should be zero for the solution of LPP to exist. Otherwise, if in the final simplex table, an artificial variable appears as a basic variable and is non zero, the LPP does not possess any feasible solution.

3.4.1. Example: Maximise Z = 𝑥₁ + 2𝑥₂

Subject to the constraints:

𝑥₁ − 𝑥₂ ≥ 3

2𝑥₁ + 𝑥₂≤ 10

𝑥₁ ≥ 0, 𝑥₂ ≥ 0

Solution: First we convert the given LPP in the standard form as follows: Max Z = 𝑥₁+ 2𝑥₂ + 0𝑠₁+ 0𝑠₂

Subject to the constraints

𝑥₁ − 𝑥₂ − 𝑠₁=3 2𝑥₁ + 𝑥₂ + 𝑠₂=10

𝑥₁ ≥ 0, 𝑥₂ ≥ 0, 𝑠₁ ≥ 0, 𝑠₂ ≥ 0

Now, let us try to form simplex table as follows:

Table 1: Simplex Table

^{We cannot form the initial simplex table with the variables x}1^{, x}2^{, s}1^{, s}2 ^{as there is only one variable s}2 ^{that has a column of unit matrix. Therefore, one more variable, i.e., artificial variable A}1^{(say) needs to} be introduced in the first constraints to get another column of unit matrix. Its coefficient in the objective function will be taken as –M.

Thus, the objective function is

Max. Z = 𝑥₁+ 2𝑥₂ + 0𝑠₁+ 0𝑠₂ − 𝑀𝐴₁

Subject to the constraints

42 Operations Research Techniques

𝑥₁ − 𝑥₂ − 𝑠₁ + 𝐴₁=3

2𝑥₁ + 𝑥₂ + 𝑠₂=10

𝑥₁ ≥ 0, 𝑥₂ ≥ 0,𝑠₁ ≥ 0, 𝑠₂ ≥ 0

The initial simplex table, therefore, is as follows (Table 2: Initial Simplex table)

^{Here, since M is big, 1+M is most positive and x}1 ^{is the incoming variable. The least replacement ratio is (3/1) which corresponds to A}1 ^{and hence it is the outgoing variable. Thus, the resulting simplex table is} as follows:

Table 3: Simplex Table

We obtain the second row (excluding profit/unit) in table 3 as follows:

Once the artificial variable is removed from the basic variable, there is no need to do any computational work for it.

Thus,we get the resulting simplex table.

Simplex Method and Duality in Linear Programming

43

Table 4: Simplex Table

The first row (excluding profit/unit) of Table4 is obtained as follows:

Since none of the net-evaluation is positive, the optimum solution is attained and is given by Max. Z=7 at 𝑥₁ = 13/3 and 𝑥₂ =4/3.

3.4.2. Exercises.

1. Minimize Z = 4𝑥₁ + 2𝑥₂

Subject to the constraints

3𝑥₁ + 𝑥₂ ≥ 27

𝑥₁ + 𝑥₂ ≥ 21

𝑥₁ + 2𝑥₂ ≥ 30

𝑥₁, 𝑥₂≥ 0

Answer. Max. Z^’ = ─48, i.e. Max. ─Z = ─48i.e. Min. Z = 48 when 𝑥₁ = 3, 𝑥₂ = 18

2. Maximise Z = 𝑥₁ + 2𝑥₂

Subject to the constraints:

𝑥₁ + 𝑥₂≤ 4

𝑥₁ + 𝑥₂≥ 6

𝑥₁, 𝑥₂≥ 0

Answer. No feasible solution.

44 Operations Research Techniques

3. Maximise Z = 10𝑥₁ + 2𝑥₂

Subject to the constraints:

-𝑥₁ + 𝑥₂≤ 2

𝑥₁ + 𝑥₂≥ 4

𝑥₁, 𝑥₂≥ 0

Answer. Unbounded solution.

• TWO-PHASE METHOD

The two-phase method provides an alternate procedure for removing artificial variables from the basis by which one can not only get initial basic feasible solution but also eliminate redundant equation existing among the constraints. It also terminates the iteration if a feasible solution of the problem is absent, for this the method is divided into two phases of iterations.

In the first phase, the process of eliminating artificial variable is performed so that we get a basic feasible solution of the LPP and the second phase is used to get the optimal solution. Since the process of finding the solution of an LPP is completed in two phases, this is called the two-phase method.

Remark: The basic feasible solution (if it exists) obtained at the end of phase I is used to start phase II. Rules for applying two-phase method are as follows:

• Assign a cost ‘-1’ to each artificial variable and a cost ‘0’ to all other variables (in place of their original cost) in the objective function.
• Solve the auxiliary problem by simplex method until either of the following three properties arise:

iii.

1. Max. Z* < 0 and at least one artificial vector appears in the optimum basis at a positive level. In this case not proceed to Phase II.
2. Max. Z* = 0 and at least one artificial vector appears in the optimum basis at zero level. In this case proceed to phase II.

Max. Z* = 0 and no artificial vector appears in the optimum basis. In this case also proceed to phase II.

The method is well explained by the following examples.

3.5.1. Example. Use two-phase simplex method to solve the problem: Min. Z = 𝑥₁ − 2𝑥₂ − 3𝑥₃

Subject to the constraints:

−2𝑥₁ + 𝑥₂ + 3𝑥₃ = 2 2𝑥₁ + 3𝑥₂ + 4𝑥₃ = 1

𝑥₁, 𝑥₂, 𝑥₃ ≥ 0

Solution. Max. Z = −𝑥₁ + 2𝑥₂ + 3𝑥₃

Subject to the constraints:

Simplex Method and Duality in Linear Programming

45

−2𝑥₁ + 𝑥₂ + 3𝑥₃ + 𝑎₁ = 2 2𝑥₁ + 3𝑥₂ + 4𝑥₃ + 𝑎₂ = 1

𝑥₁, 𝑥₂, 𝑥₃, 𝑎₁, 𝑎₂ ≥ 0