Operation Research

 Introduction of Operations research

During the Second World War, British leaders ask scientist and engineers to analyze several military problems, the deployment of Radar and the management of Convoy bombing and mining operations. The applications of mathematics and the scientific methods to military operations was called operations research or management science means a scientific approach to decision making, which seeks to determine how best is to design and operate a system, usually under conditions requiring the allocation of scarce resources.

History of operations research

Along the history, is feculent to find collaboration among scientists armies officer with this same objective, ruling the optimal decision in battle in fact that many experts consider the start of operational research in the third century B.C.

Leonardo Da Vinci tool part in 1503, like engineer in the war against paisa due to he knew techniques to accomplish bombardments, to construct ships, armored vehicles, cannons, catapults, and another war like machines.

Thomas Edison made use of operational research, contributing in the antisubmarine war, with his greats ideas, like shields against torpedo for the ships.

States decide supplying the city or else by means of escorted convoys (that would be able to give rise to new confrontation) or by means of airlift, choused, starting the Luftbrucke (airlift) at 25^th June in 1948. This went another from the problems in which worked the SCOOP group, in December of that same year, could carry 4500 daily tons and after studies of Research Operations optimized the supplying to get to the 8000-9000 daily tons in March of 1949. This cipher was the same that would have been transported for terrestrial means, for that the Soviet decided to suspend the blockage at May 12, in 1949.

After Second World War, the order of United States’ resources (USA) (energy, armaments, and all kind of supplies) took opportune to accomplish it by models of optimization, resolved intervening liner programming.

At the same time that the doctrine of Operation Research is being developed, the techniques of computation and computers are also developing, thanks to them the rime of resolution of the problems decreased.

The first result of these techniques was given at the year 1952, when a SEAC computer from was used National Bureau of Standards in way to obtain the problem’s solution. The success at the resolution time was so encouraging that was immediately used for all kind of military problems, like determining the optimal height which should fly the planes to locate the enemy submarines, monetary founds management for logistics and armament, including to determine the depth which should send the charges to reach the enemy submarines in way to cause the causalities bigger number, that was translated in a increase I five times in Air Force’s efficacy.

During the 50’s and 60’s decade, grows the interest and developing of Operational Research, due to its applications in the space of commerce and the industry. Take for example, the problem of the calculation of the optimal transporting plan of send of constructions to the works of edification of the city o Moscow, which had 10 origins points and 230, destiny. To resolve it was used and Sterna Computer, that tool 10 days in the month of June of 1958, and such solution contributed a reduction of the 11% of the expenses in relation to original costs.

Previously, this problem were presented in a discipline knew as Research Companies or Analysis Companies, that did not have so effective methods like the developed during Second World War (for example the Methods). No war applications Operations Research there are so as you want imagine, with problems like nutrition of cattle raising, distribution of field of cultivation in agriculture, goods transports, location, personnel’s distribution, and nets, queue problems, graphics etc.

Definition of Operation Research

Operations Research is the applications of scientific methods by Interdisciplinary teams to problems involving the control of organized (man-machine) systems so as to provide solutions which nest serve the purpose of the organization as whole topics. As operation is a large subject so many definitions of operations research have been suggested from time to time. Some of the widely accepted definitions are:

 According to Mores and Kimball:

Operations research is a scientific method of providing executive departments with a quantitative basis for decisions regarding the operation under their control.

According to E.L. Arnoff and M.j. Netzrog:

Operation research is the systematic method oriented study of the basic structure, characteristic, functions and relationships of an organization to provide the executive with a sound, scientific and quantitative basis for decision making.

Scopes of Operation Research:

Whenever there is a problem for optimization, there is scope for the application operations researches. It has wide scope in the social, economic and industrial problems of today.

Such as

1. Industrial Management
2. Defense Operations
3. Developing and Development Economics
4. Agricultural Sector
5. Business and Society

Operations Research is a problem solving and decision making science. In the areas of management where OR techniques have been successfully applied are:

1. Production and Facility Planning
2. Procurement
3. Marketing
4. Finance
5. Personnel

Complexity of operations:

In a big industry the numbers of factors influencing a decision have increased. For example consider a factory schedule which has to take into account

1. Customer demand
2. Requirement of raw materials
3. Equipment capacity and possibility of equipment failure
4. Restrictions on manufacturing process

How Operations Research Works:

Operations Research, like all scientific research, is based on scientific methodology, which proceeds along the following lines:

1. Formulating the problem
2. Constructing a model to represent the system under study
3. Deriving a solution from the model
4. Testing the model and the solution derived from it
5. Establishing controls over the solutions
6. Putting the solution to work, i.e. Implementation.

 Models in Operations Research:

A model, as used in operations research, is defined as an idealized representation of the real life situation. It represents one or a few aspects of reality. Diverse items such a map, a multiple activity chart an auto biography PERT (Program Evaluation and Review Technique) network breakeven equation, balance sheet etc. are all models because each one of them represents a few aspects of the real life situation. A map for instance, represents the physical boundaries but normally ignores the height of the various places above the sea level.

 Symbolical or Mathematical Models:

Symbolic models employ a set of mathematical symbols (letters, numbers, etc.) to represent the decision variables of the system, under study. These variables are related together by mathematical equations which describe the properties of the system. A solution of the model is then, obtained by applying well developed mathematical techniques. In symbolic models are used wherever possible, not only because they are easier to manipulate but also because they yield more accurate results. Most of the lecture, therefore, is devoted to the formulation and solution of these mathematical models.

Limitations of Operations Research:

1. Mathematical models are applicable to only specific categories of problems.
2. Mathematical models which are essential of OR, do not take into account qualitative factors or emotional factors which are quit5e real. All influencing factors cannot be quantified, find no place in mathematical models.
3. Being a new field, generally there is a resistance from the employees to the new proposal.
4. Management which has to implement the advised proposals may itself offer a lot of resistance due to conventional thinking.
5. At the implementation stage, the decision cannot be governed by quantitative considerations alone.

Objectives of Operations Research:

The industrial growth has brought with it the need for division of management function within and organization. Thus every organization has met a number of functional units or departments, each performing a part of the whole job and for its successful working, developing its own policies and objectives.

These objectives though in the best interest of the individual department, may not be in the best interest of the organization as a whole. In fact, these objectives of the individual departments may be inconsistent and clashing with each other. In this Context reference was made in section with regard to the attitudes of the various departments of a business Organization towards its inventory policy.

The application of Operation research (OR) methods helps in making decisions in such complex situations. It combines the knowledge of various disciplines such as mathematics, statistics, economics, psychology and engineering and the combined effort of all these disciplines helps in analyzing the problem in finer details.

Two business realities a manager has to face are change and uncertainty. The market demand fluctuates, raw materials and spares become scarce, production on equipment fails or the change in Govt.’s policy may affect the company’s resources drastically or impose restrictions on the current manufacturing processes. Under such situations past experience can be a (though only a rough) guide. A knowledge of the past data and future trends can help the manager to assess the risk and accordingly make his decisions. OR can help him here. The statistician will analyze the past data and extrapolate it for near future. The accountability will be able to estimate the cost associated with any decision shale the engineer will assess the effect of changes in technology, quality of material, and availability of new types of machines.

To summaries, the objective of OR is to provide a scientific basis to the Managers of an organization for solving problems involving interaction of the components of the system by employing army approach by a team of scientists sawn from different disciplines ding a solution which is in the interest of the organization as a whole.

  Formulating the problem:

It is very essential that the problem at and be clearly defined. It is almost impossible to get the right answer from a wrong problem. The problem may be set out explicitly by the consumer, the sponsoring organization or may have to be formulated by the OR team. In OR it is not uncommon to start the study with tentative formulation of the problem.

This may be reformulating over and again during the study. Efforts should, however, be made to formulate the problem fairly elaborately before starting with the research. The problem formulation phase is generally lengthy, requiring considerable time and effort but it is quite.

Justified since, unlike other researches, OR is a search into the operations of a man-machine organization and must take into consideration the economics of the operations. In formulation a problem for OR study, analysis must be made of the four major components:

1. The environment
2. The decision maker
3. The objectives
4. Alternative course of action and constrains.

Out of the four components environment is most comprehensive since embraces and provides a setting for the other three. In general environment is the framework within which a system of organized activity I directed to attain the prescribed objectives or goals.

Simple method:

General Form of Liner Programming Problems: The general form of LPP is given by

            Maximize (Minimize)  z = c₁x₁ + c₂x₂ + c₃x₃ + ………. + c_nx_n

            Subject to, a₁₁x₁ + a₁₂x₂ + a₁₃x₃ +  ……………. + a_1nx_n ( ≤, =, ≥) b₁

                            a₂₁x₁ + a₂₂x₂ + a₂₃x₃ + ……………… + a_2nx_n (≤, =, ≥) b₂

                           —————————————————————————

                          ————————————————————————–

                        a_m1x₁ + a_m2x₂ + a_m3x₃ + ……………….. + a_mnx_n (≤, =, ≥) b_m

                                    x₁, x₂, x₃ ………………… x_n ≥ 0

The constants e_j ( j = 1, 2, 3 ….. n) are called cost coefficients; the constants b_i ( i = 1, 2, 3 ….. m) in the constraints are called stipulations and the constants a_ij (i = 1, 2, 3 …… m and j = 1, 2, 3 ….. n) are called structural coefficients.

Summation Form of Linear Programming Problems: The above formulation can be put in the following compact form by using summation

                        Maximize ( or Minimize)  Z =

Subject to,

                        And x_j ≥ 0, j = 1, 2, 3 ………….. n

 Matrix Form of LPP: The above formulation can be put in the matrix form

                                    Maximize ( or Minimize) Z = cx

                                                Subject to, Ax (≤, =, ≥)b

                                                            And x ≥ 0

where

where. A is called the coefficient matrix, x is called decision vector, b is requirement vector and c is the cost (price) vector of LPP.

Canonical Form of LPP: The Canonical form of LPP is defined as

                                    Maximize Z =

                                    Subject to  ≤ b_i   i = 1, 2, 3, ………., m

                                                and x1 ≥ 0, j = 1, 2, 3 ……….. n

The Characteristics of this form are

a)      Objective function is of maximization form

b)      All constraints are of the (≤) type, and

c)      All decision variables are non-negative.

  Example: Convert the LPP to Canonical form:

            Minimize Z  = 60x₁ + 40x₂

            Subject to,       30x₁ + 10x₂ ≥ 240

                                    10x₁ + 10x₂ ≤ 160

                                    20x₁ + 60x₂ = 480

                                                x₁, x₂ ≥ 0

Solution: The above LPP can be converted to the Canonical form as:

                                    Maximize G = -60x₁ – 40x₂

                                    Subject to – 30x₁ – 10x₂ ≤ -240

                                                    10x₁ + 10x₂ ≤ 160

                                                    20x₁ + 60x₂ ≤ 480

                                                    -20x₁ -60x₂ ≤ -480

                                                       x₁, x₂ ≥ 0

 Example:

Convert the following LPP to standard form:

                                                            Maximize        Z = 3x₁ + 2x₂

                                                            Subject to        2x₁ + x₂ ≤ 2

                                                                                    3x₁ + 4x₂ ≥ 12

                                                                                    x₁, x₂ ≥ 0

Solution: Introducing the slack and surplus variables, the standard form can be written as:

                        Maximize Z = 3x₁ + 2x₂

                        Subject to, 2x₁ + x₂ + s₁ = 2

                                    3x₁ + 4x₂ – s₂ = 12

                                    x₁, x₂, s₁, s₂ ≥ 0

Standard LPP in Matrix Form

Problem the following LPP in standard matrix form:

                        Maximize Z = 2x₁ + 3x₂

                        Subject to, x₁ + x₂ ≥ 5

                                        x₁ + 2x₂ = 7

                                        5x₁ – 2x₂ ≤ 9

                                       x₁, x₂ ≥ 0

First we consider the LPP in standard form:

Maximize z = 2x₁ + 3x₂ + 0x₃ – Mx₄ – Mx₅ + 0x₆

Subject to,

                        x₁ + x₂ – x₃ + x₄ + 0 + 0 = 5

                        x₁ + 2x₂ + 0 + 0 + x₃ + 0 = 7

                        5x₁ – 2x₂ + 0 + 0 + 0 + x₆ = 9

                        x₁, x₂, x₃, x₄, x₅, x₆ ≥ 0

where, x₃ is the surplus, x₆ is the slack and x₄ and x₅ are the artificial variable

Working rule for solving a liner programming problem by one phase simplex method:

# The matrix form of standard LPP is:

Maximize z = (2, 3, 0, -M, -M, 0)

                     where,

Thus we can say, X =    C = (2, 3, 0, -M, -M, 0)

A =

Step-1: Verify whether the objective function of the given problem is to be maximized or minimized. If it is to be minimized then we transfer it into a maximization problem by using Maximum z = – Minimum z.

Step-2: Verify whether all b_j ³ O. If any one of b_i is negative, then multiply the corresponding constraints by 1, to make all b_i ³ 0.

Step-3: Transfer all the constraints into equation by introducing slack and surplice variables.

Step-4: Add artificial variables if needed. Then given L.P.P. reduced to standard

form A x = b.

Step-5: Construct the simplex table.

Step-6: Compute the net evaluation z_j – c_j or, E_j – c_j by using the relations E_j – c_j by using the relations E_j – c_j = c_by₁ – c_j where y₁ = column of A.

Step-7: If each (E_j-c_j) ³ 0 then the initial basic feasible solution is an optimum basic feasible solution.

(i) If at least one E_j – c_j = 0 for a non-basic column vector and at least one y_ij is positive then by entering the vector in the basic, we get an alternative optimal basic feasible solution.

(ii) If at least one of E_j – c_j is equal to zero for a non-basic column vector and all y_ij ≤ 0 then we get an alternative non-basic optimal solution.

(iii) If E_j –c_j > 0 for all non-basic column vector then the problem has unique solution.

Step-8: If at least one of E_j – c_j is negative then proceed on the next step.

If there are more than one negative values of E_j – c_j then select the most negative of them.

 Let it be E_p – c_p for some j = p.

(i) If all y_ip ≤ 0 hen there is an unbounded solution.

(ii) If at least one of y_ip is positive then the corresponding vector y peters the basis.

(iii) If two or more decision variables are identical select any one of them.

(iv) If a decision variable and a slack variable are identical select any one of them.

(v) If a decision variable and a slack variable are identical select decision variable.

Step-9: Compute the ratios and select the minimum of them. Let the minimum of these ratios be , then the column vector y_k will leave the basis y_B. The element y_kp is known as leading element (or pivot element or key element).

Step-10: Convert the leading element to unity by dividing its row by the leading element itself and all other elements in its column to zero by using the relations.

 and

Step-11: Now go to he step-6 and repeat next step until either an optimum solution is obtained or there is an indication of an unbounded solution.

 The Canonical form of L.P. Problem:

The general L.P.P can be always put in following form called the canonical form

            Maximize

            S/t

The characteristics of this form are

            (a) All decent variables are non-negative

            (b) All constraints are of the type and

            (c) Objective function is of maximum type

Any L.P.P can be put in the canonical form by the use of some elementary transformations

(i) The maximization of a function is equivalent to the maximization of the negative experience of this function – . For example the liner objective function

            Minimize

is equivalent to

maximize, with  Therefore for all L.P.P the objective function can be expressed in the maximization form

(2) An inequality in one direction can be changed to an inequality in the direction by multiplying both sides of the inequality by (-1)

(3) An equation many be replaced by two inequalities in opposite directions .

(4) If decision variable is unrestricted it is expressed as the difference between two non-negative variables.

The Standard form of L.P.P

The characteristics of the standard form are

(i) All the constraints are expressed in the form of equations except the non-negativity constraints which remain inequalities

(2) The R.H.S of each constraints equation is non-negative

(3) All the decision variables are non-negative

(4) The objective function is of the maximization or minimization type

The inequality constraints are changed to equality constraints by adding or subtracting some variables known as slack variables (when added) and surplus variable (when subtracted)

Express the following L.P.P into standard form

            Minimize

            Slt

Solution: Introduction slack and surplus variables the problem in the standard form can be expressed as

                        Maxi

            S/t

(2) Express the following L.P.P in the standard form

(1) If there are m equality constraints and m + n is the number of variables a start for the optimal solution is made by putting n unknowns ( out of m + n unknowns) equal to zero and then solving for the ‘m’ equals in remaining m unknowns ; provided that the solution exists and is unique.

The n zero variables are called non-basic variables and the remaining m variables are called basic variables which form basic solution. If the solution yields all non-negative basic variables, it is called basic feasible solution; otherwise it is infeasible. This step reduces the number of alternatives for the optional solution form infinitive to a finite number whose maximum limit can be

The resulting number of alternative solution is still too large to be computationally feasible and is reduced by the 2nd condition

(2) We know that in a liner programming problem all the variables must be non-negative. Since the basic solution selected by condition (1) above are not necessaricty non-negative the number of alternatives can be further reduced by eliminating all infeasible basic solutions (solution having variables less than zero)

In the simple method this is achieved by starting with a basic solution which is non-negative . A condition called feasibility condition is then provided which ensures that the next basic solution to be selected from all the possible basic solutions is always feasible . This solution is called basic feasible solution. If all the basic variables are greater than zero , the solution is called non-degenerate ; if some of them are zero, the solution is called degenerate. A new basic feasible solution can be obtained from a previous one. By setting one of the m basic variables equal to zero and replacing it by a new non-basic variable. The basic variable set equal to zero is called a “ baring variable” while the new one is called an ‘entering variable”.

(3) The entering variable can be so selected that it improved the value of objective function so that the new solution is better than the previous one. This is achieved by the use of another condition called optimality condition which select that entering variable which produces the largest per unit gain in there objective function. This procedure is repeated successively unit  no further improvement in value of the object function is possible. The final solution is then call an optimal basic feasible solution as simply optimal solution.

This is the solution which satisfies the objective function equation. The constraints as well as the non-negativity conditions. This is of course, true only if the objective function has a finite value

The for going discussion shows that simplex method procedure is principally a screening process since f eliminates the solutions that are not promising solutions for the optimal solution.

It will not be out of place to further elaborate a few important terms with reference to equations of the general linear programming problem.

 Introduction to the Simplex Method

Simple Method- An algebraic, iterative method to solve linear programming problems.

The simplex method identifies an initial basic solution (Corner point) and then systematic moves to an adjacent basic solution, which improves the value of the objective func Eventually, this new basic solution will be the optimal solution.

The simplex method requires that the problem is expressed as standard LP problem method on Standard Form). This implies that all the constraints are expressed as equation adding slack or surplus variables.

The method uses Gaussian elimination (sweep out method) to solve the linear simulate equations generated in the process.

Terminology:

 Solution: A solution is any specification of values for the decision variables.

Feasible solution: A feasible Solution is a solution for which all the constraints are satisfied

Feasible Region: The feasible region is the set of all feasible solution.

Optimal Solution: An optimal Solution is a feasible solution that has the most favorable value of the objective function.

Non Basic Variable: If there are m equality constraints and n number of variables we start for optimal solution by putting n-m unknown equal to zero. These m-n variables are called non basic variables.

Basic solution:  A Basic Solution is a solution of m basic variables when each non basic variable is set zero.

The maximum number of possible basic solutions for m equations and n unknowns is

Basic feasible solution: A Basic Feasible solutions is a solution for which all the variables are greater than or equal to zero

Non-degenerate basic feasible solution: If all the basic solutions are greater than zero then the solution is called non-degenerate solution.

 De-generate Solution: If one or more basic variables is (are) zero then the solution is called the De-generate solution.

Slack variables:

Consider an inequality of the form

            ≤ b_i (b_i ≥ 0); i = 1, 2, ………, m

This constraint is equivalent to the equality constraint,

+ y_i = b_i; i = 1, 2, ………, m.

Where yi ≥ 0 and is called the slack variable.

Surplus variables: In a liner programming problem, if the constraints are of the type (≥) and a variable is subtracted to the left hand side of the in equation it represent an equation.

 Mathematically: Consider a L.P.P.

Max or Min

Subject to ≥ b_j; j = 1, 2, 3 ……….. m

If the following form exist and s_j ≥ 0 then the non-negative variables s_j are called surplus variables.

Introduction to Linear Programming & Basic Theorems Max or Min,

Subject to

Problem : Find all the basic feasible solutions of the equations

Soultion: The given system of equations can be presented in the following maxim form

where

Since A is of order . We can take any of the following

 subs natives as our basic matrix B

The variables not associated with the first sub matrix are  and . The basic solution to the given system is obtained by setting  and solving the system

Also in each of the remaining there basic feasible solutions at least one of the basic variables is zero.

Problem: Show using matrix vector notation that the following system of loner equations has degenerate solutions.

Dual Simplex Method

Definition: Primal and Dual problems in L.P. The L.P model we develop for a situation is referred to as the primal problem.

 The dual Problem in a L.P defined directly and systematically form the original (Primal) L.P model. The two problems are so closely related that the optimal solutions of one problem automatically yields the optimal solution to the other.

Rules of correspondence between primal and dual:

(a)    If the primal contains n variables and m constraints, the dual will contain m variable and n constraints.

(b)   the maximization problem in the primal becomes the minimization problem in the dual and vice-versa.

(c)    The maximization problem has ‘≤’ type constraints while the minimization problem has ‘³’ type constraints.

(d)   The constants c₁, c₂ ……………, c_n in the objective function of the primal appear in the constraints of the dual.

(e)    The variables in both problems are non negative.

 That is, the following correspondence rule may be applied:

(b) Requirement vector

(c) Co-efficient matrix

(d) Constraints with ³ sign

Relation

(e) (i^th) in equality

(f) (i^th) equality

Variable

(g) x_j ³ 0

(h) x_j unrestricted

(i) Finite optimal solution

(j) Unbounded solution(a) Objective function Max. z_D

(b) Price vector

(c) Transpose of the Co-efficient matrix.

(d) Constraints with ≤ sign

Variable

(e) w₁ ³ 0

(f) w₁ unrestricted in sign

Relation

(g) (j^th) inequality

(h) (j^th) constraint equation

(i) Finite optimal solution with equal value of objective function.

(j) No F.S. or unbounded solution.

General Proof: As the l-th constraint of the primal is an equation, therefore, the primal in the standard form can be written as

            Maximize, z = c₁x₁ + c₂x₂ + ………………………. + c_nx_n

            Subject to        a₁₁x₁ + a₁₂x₂ + …………. + a_1n x_n ≤ b₁

                       a₂₁x₁ + a₂₂x₂ + ………. + a_2nx_n ≤ b₂

                        ……………………………………………

                        a_k1x₁ + a_k2x₂ + …………… + a_knx_n ≤ b_k

                        – a_k1x₁ – a_k2x₂ …………….. – a_knx_n ≤ – b_k

                        a_k+1, ₁ x₁ + a_k+1, ₂ x₂ + ………. + a_k+1, _n. x_n ≤ b_k+1

                        ……………………………………………

                        a_m1 x₁ + a_m2 x₂ + ……………….. + a_mn x_n ≤ b_m

                        x₁, x₂, ……………, x_n ³ 0.

The dual of the above problem can be written as.

Minimize W = b₁y₁ + b₂y₂ + … + b_k(y’_k – y_k”) + b_k+1 y_k+1 … + b_my_m

Subject to

a₁₁y₁ + a₂₁y₂ + .. + a_k1(y_k’ – y_k”) + a_k+1 , ₁y_k+1+ …. + a_m1 y_m ³ c₁.

a₁₂y₁ + a₂₂y₂ + …. + a_k2 (y_k’ – y_k”) + a_k+1, ₂y_k+1 + …. + a_m2 y_m ³ c₂

…………………………………………………………………………

a_1ny₁ + a_2ny₂ + … + a_kn (y_k’ – y_k’) + a_k+1, _ny_k+1 + …. + a_mn y_m ³ c_n

Putting y_k’ – y_k” = y_k, the dual problem can be

writer as,

Minimize, W = b₁y₁ +b₂y₂ + ………. + b_ky_k + ….. + b_ny_m

Subject to

            a₁₁y₁ + a₂₁y₂ + …… + a_k1y_k + …… + a_m1y_m ³ c₁

            a₁₂y₁ + a₂₂y₂ + ……. + a_k2y_k + ……. + a_m2y_m ³ c₂

            ………………………………………………………

            a_1n y₁ +a_2ny₂ + …… + a_kny_k + ……….. + a_mn y_m ³ c_n

and y₁, y₂, ………. y_k-1, y_k+1, …….. y_m ³ 0, but yk is unrestricted is sign as y_k is expressed as the difference of two non-negative variables. y_k’ and y_k”

            Hence the theorem is proved.

Example-: Construct the dual of the problem

Maximize z = 3x₁ + 17x₂ + 19x₃

Subject to         x₁ – x₂ + x₃ ³ 3

                        – 3x₁ + 2x₃ ≤ 1

                        2x₁ + x₂ – 5x₃ = 1

                        x₁, x₂, x₃ ³ 0

Solution:

As the problem is of maximization, all constraints must be expressed in “≤” form

(a) First inequality of equality constraint is multiplied by (-1)

                                    i.e. –x₁ + x₂ – x₃ ≤ -3

(b) Third constraint of equality form is replaced by a pair of inequalities.

                                                2x₁ + x₂ – 5x₃ ≤ 1

                                       and   2x₁ + x₂ – 5x₃ ³ 1

                                                i.e. 2x₁ + x₂ – 5x₃ ≤ 1

                                       and  -2x₁ – x₂ + 5x₃ ≤ – 1

Thus, the given problem in symmetric form may be expressed as

Maximize        z = 3x₁ + 17x₂ + 19x₃

            Subject to        – x₁ + x₂ – x₃ ≤ -3

                                    -3x₁ + 2x₃ ≤ 1

                                    2x₁ + x₂ – 5x₃ ≤ 1

                                    – 2x₁ – x₂ + 5x₃ ≤ -1

                                    x₁,  x₂,  x₃ ³ 0

Let y₁, y₂, y₃’ and y₃” be the associated

non-negative dual variables. Then dual is

Minimize         W = -3y₁ + y₂ + y₃’ – y₃”

Subject to        -y₁ – 3y₂ + 2y₃’ – 2y₃” ³ 3

                        y₁                     + y₃’ – y₃” ³ 17

                        -y₁ + 2y₂ – 5y₃’ + 5y₃” ³ 19

Substituting y₃ = y₃’ – y₃” where y₃ is unrestricted in sign, the dual becomes.

Minimize W = – 3y₁ + y₂ + y₃

Subject to         – y₁ – 3y₂ + 2y₃ ³ 3

                           y₁                  + y₃ ³ 17

                           y₁, y₂ ³ 0, y₃  is unrestricted in sign.

Theorem: The dual of the dual is the primal.

Proof: Let the primal problem is canonical form be

Maximize        z = c₁x₁ + c₂x₂ + ………  + c_nx_n

Subject to,       a₁₁x₁ + a₁₂x₂ + ………… + a_1nx_n ≤ b₁

                        a₂₁x₁ + a₂₂x₂ + ……….. + a_2nx_n ≤ b₂

                        ————————————————–

                        —————————————————

                        a_m1x₁ + a_m2x₂ + ……………… + a_mnx_n ≤ b_m

                        where x₁, x₂ …………….. x_n ≥ 0

Then the dual of this problem is

Minimize         w = b₁y₁ + b₂y₂ + ……….. + b_my_m

Subject to,       a₁₁y₁ + a₂₁y₂ + ………….. + a_m1y_m ≥ c₁

                        a₁₂y₁ + a₂₂y₂ + …………. + a_m2y_m ≥ c₂

                        ————————————————–

                        a_1ny₁ + a_2ny₂ + ………… + a_mny_m ≥ c_n

            y₁ ≥ 0, y₂ ≥ 0 …………….. y_m ≥ 0

Theorem: State and prove Weak Duality theorem in linear programming.

 Statement: Any feasible solution to the primal problem (P) has the value z less than or at best equal to the value W for any feasible solution to the dual problem (D).

                                    i.e     z ≤ W.

Proof: The general linear programming problem (Primal) involving n decision variables and m constraints in canonical form is given by relations.

(Primal) maximize    z = c₁x₁ + c₂x₂ + …….. + c_nx_n

Subject to                    a₁₁x₁ + a₁₂x₂ + ……….. + a_1nx_n ≤ b₁

                                    a₂₁x₁ + a₂₂x₂ + ……. + a_2nx_n ≤ b₂

                                    ——————————————                              ………. (i)

                                    ——————————————

                                    a_m1x₁ + a_m2x₂ + …………. + a_mn x_n ≤ b_m

            where             x₁. x₂, ……… x_n ≥ 0

            (Dual) Minimize   W = b₁y₁ + b₂y₂ + ……….. b_my_m

            Subject to        a₁₁y₁ + a₂₁y₂ + ………. + a_m1y_m ≥ c₁

                                    a₁₂y₁ + a₂₂y₂ + …………. a_m2y_m ≥ c₂

                                    ———————————————-                ………… (2)

                                    ———————————————-

                                    a_1ny₁ + a_2ny₂ + …………… a_mny_m ≥ c_n

            Where      y₁, y₂ ……. y_m ≥ 0

Multiplying the 1st inequality of (1) by y₁, the 2nd  inequality of (1) by y₂ etc. and add them all, we get,

 (a₁₁x₁y₁ + a₁₂x₂y₁ + ………… a_1nx_ny₁) + (a₂₁x₁y₂ + a₂₂x₂y₂ + ……….. + a_2nx_ny₂) + …….. + (a_m1x₁y_m + a_m2 x₂y_m + ………. + a_mnx_ny_m) ≤ b₁y₁ + b₂y₂ +

……….. b_my_m ;      ………… (3)

Similarly, multiplying the 1st inequality of (2) by x₁, the 2nd inequality by x₂ etc. and add them all. We get,

(a₁₁x₁y₁ +a₂₁x₁y₂ + ……… a_m1x₁y_m) + (a₁₂x₂y₁ + a₂₂x₂y₂ + ………. a_m2x₂y_m) + …… (a_inx_ny₁ + a_2nx_ny₂ + …….. + a_mnx_ny_m) ≥ c₁x₁ + c₂x₂ + ………. c_nx_n ; …………. (4)

Now the sums of on the left hand side of inequalities (3) and (4) are equal. Hence.

                        c₁x₁ + c₂x₂ + ….. + c_nx_n ≤ b₁y₁ + b₂y₂ + …….. + b_my_m

i.e.     z ≤ W.  (Proved the theorem).

Theorem: As the k-the m constraints of the primal is an equation, therefore, the primalin the standard form can be written as

Maximize                      z = c₁x₁ + c₂x₂ + …….. + c_nx_n

Subject to                    a₁₁x₁ + a₁₂x₂ + ……….. + a_1nx_n ≤ b₁

                                    a₂₁x₁ + a₂₂x₂ + ……. + a_2nx_n ≤ b₂

                                    ——————————————

                                    a_k1x₁ + a_k2x₂ + ……………. + a_knx_n ≤ b_k

                                    – a_k1 x₁ – a_k2x₂ ……….. –a_knx_n ≤ – b_k

                                    a_k+1, ₁ x₁ + a_k+1, ₂ x₂ + …….. + a_k+1, _n. x_n ≤ b_k+1

                                    ———————————————-

                                    a_m1 x₁ + a_m2 x₂ + ……………. + a_mn x_n ≤ b_m

                                    x₁, x₂, ……………………. , x_n ≥ 0.

The dual of the above problem can be written as.

Minimize W = b₁y₁ + b₂y₂ + .. + b_k(y’_k – y_k”) + b_k+1 y_k+1 …. + b_my_m

Subject to

a₁₁y₁ + a₂₁y₂ + .. + a_k1(y_k’ – y_k”) + a_k+1, ₁y_k+1 + …. + a_m1 y_m ≥ c₁.

a₁₂y₁ + a₂₂y₂ + ….. + a_k2(y_k’ – y_k”) + a_k+1, ₂y_k+1 + …. + a_m2y_m ≥ c₂

——————————————————————————-

a₁n_y1 + a_2ny₂ + …. + a_kn (y_k’ – y_k’) + a_k+1, _ny_k+1 + …. + a_mn y_m ≥ c_n

Putting y_k’ – y_k” = y_k, the dual problem can be

Written as,

Minimize, W = b₁y₁ + b₂y₂ + ……….. + b_ky_k + …………. b_my_m

Subject to

            a₁₁y₁ + a₂₁y₂ + ……. + a_k1y_k + ……… + a_m1y_m ≥ c₁

            a₁₂y₁ + a₂₂y₂ + …….. + a_k2y_k + ……… + a_m2y_m ≥ c₂

            —————————————————————-

a_1n y₁ + a_2ny₂ + ……….. + a_kn y_k + ……… + a_mny_m ≥ c_n

and y₁, y₂, ……… y_k-1, y_k+1, …….. y_m ≥ 0, but y_k is unrestricted in sign as y_k is expressed as the difference of two non-negative variables, y_k’ and y_k”.

            Hence the theorem is proved.

Theorem: State and prove Complementary slackness theorem.

Statement: Let x° and y° be feasible for the primal problem

(P) Maximize       z = cx

Subject to             Ax ≤ b

                             x ≥ 0

            and the dual problem (D) Minimize    W = by

                                                     Subject to    Ay ≥ c

                                                                            y ≥ 0    respectively.

Then x° and y° are optimal to their respective problems, if and

only if (y°A – c) x° + y° (b – Ax°) = 0

Proof: Let the column vector u = (u₁, u₂,  ………… u_m) ^T represents the slack-vector for the primal and the row vector

            V = ( v₁, v₂, ………. , v_n) be the surplus vector for the dual problem. Since x° and y° are feasible solutions.

            We have Ax° + u° = b;                        x°, u° ≥ 0 …………….. (i) since [Ax ≤ b,

                           y°A – v° = c;                         y°, v° ≥ 0 …………… (ii) since Ay ≥ c ]

            (u° and v° represent the valus of the slack variable u and v corresponding to the feasible solutions x° and y°)

            Multiplying equation (1) by y° and (2) by x°, we get.

                        y° Ax° + y°  u°  = y° b ……………. (iii)

            and       y° Ax° – v°x°    = cx° …………….. (iv)

            Subtraction (iv) from (iii), we obtain

            y°u° + v°x° = y°b – cx° …………… (v)

To prove this theorem, we have to show that x° and y° are optimal solutions to the primal and dual problems

            Iff v°x° + y°u° = 0 ………… (vi)

Part- 1. We will assume that x° and y° are optimal solutions.

Then by ‘main duality theorem’ cx° = y°b

            Then equation (v)         y° u° + v°x° = y°b – y°b

                                                 y°u° + v°x°  = 0

Part- 2. Let us suppose that equation (vi) is true.

Then equation (v) implies that y°b – cx° = 0

                                                 y°b = cx°

Since x° and y° are feasible solutions of primal and dual problem respectively. “By optimality criterion theorem”. x° and y° are the optimal solutions of respective problem.

            Now, (iii)  y°b – y°Ax° = y°u° …………. (vii)

            (iv)  y°Ax° – cx° = v°x° ………… (viii)

            Adding (vii) and (viii) we get

            (y° A – c) x° + (b – Ax°) y° = v° x° + u° y°

             (y° A – c) x° + (b – Ax°) y°= 0

            Hence the theorem is proved.

 Construct the dual of the following primal problem:

                                        Max z  = 5x₁ +12x₂ + 4x₃

                                     S/t,         x₁ + 2x₂ + x₃ ≤ 10

                                                  2x₁ – x₂ + 3 x₃ = 8

                                                            x_1, x_2,  x₃ ≥ 0.

Solution:

Primal L.P.P in equation form:

                                                Max Z = 5x₁ + 12 x₂ + 4 x₃

                                            S/t,              x₁ + 2x₂ + x₃ + x₄ = 10

                                                           2 x₁ – x₂ + 3x₃ + 0.x₄ = 8

                                                                 x_1,    x_2,    x_3,     x₄  ≥ 0

 Dual Problem:

                                         Min W     = 10y₁ + 8y₂

                                      S/t,                y₁ +2y₂ ≥5

                                                           2y₁ – y₂  ≥ 12

                                                            y₁ + 3y₂ ≥ 4

                               y₁  ≥ 0,       y₂ is unrestrictedly in sign.

 Problem: Construct the dual of the primal problem

                          Max  Z = 2x₁ + x₂ + x₃

                             S/t,        x₁ + x₂ + x₃ ≥ 6

                                      3x₁ – 2x₂  + 3x₃ = 3

                                     – 4x₁ + 3x₂ – 6x₃ = 1

                                           x_1,    x_2,         x₃ ≥ 0

Primal L.P.P in equation form:

Max Z = 2x₁ + x₂ + x₃ + 0.x₄

             S/t,        x₁ + x₂ + x₃ – x₄ = 6

                         3x₁ – 2x₂ + 3x₃ = 3

                       – 4x₁ + 3x₂ – 6x₃ = 1

                        x_1,        x_2,    x_3,     x_4,      ≥ 0

 Dual Problem:                                         Min W = 6y₁ + 3y₂ + y₃

              S/t,         y₁ + 3y₂ – 4y₃ ≥ 2

                            y₁ – 2y₂ + 3y₃  ≥ 1

                            y₁ + 3y₂ – 6y₃ ≥ 1

                            0 – y₁ + 0.y₂ + 0.y₃ ≥ 0

                                      – y₁ ≥ 0

                                        w₁ ≥ 0

– y₁ + 0.y₂ + 0.y₃ ≥ 0

                    – y₁ ≥ 0

                     w₁ ≥ 0

          where w₁ = – y₁

\ Dual problem becomes,

          Min W = – 6w₁ + 3y₂ + y₃

            S/t,         – w₁ + 3y₂ – 4y₃ ≥ 2

                          – w₁ – 2y₂ + 3y₃ ≥ 1

                          – w₁ + 3y₂ – 6y₃ ≥ 1

                                      w₁ ≥ 0

            y₂,       y₃ are unrestricted in sign

Problem: Solve by dual simplex method the following problem.

                        Min Z = 2x₁ + 2x₂ + 4x₃

                         S/t,        2x₁ + 3x₂ + 5x₃ ≥ 2

                                      3x₁ + x₂ + 7x₃ ≤ 3

                                       x₁ + 4x₂ + 6x₃ ≤ 5

                                     x₁,     x₂,    x₃    ≥ 0.

Solution: The given minimization problem is converted. into maximization problem by writing

                        Max G   = – 2x₁ – 2x₂ – 4x₃

                                 S/t,   – 2x₁ – 3x₂ – 5x₃ ≤ – 2

                                          3x₁ + x₂ + 7x₃ ≤ 3

                                        x₁ + 4x₂ + 6x₃ ≤ 5

                                             x₁,    x₂,    x₃ ≥ 0

Introducing the slack variables S₁, S₂, S₃, we get

                 Max G = – 2x₁ – 2x₂ – 4x₃ +0.S₁ +0S₂ +0.S₃

                    S/t,       – 2x₁ – 3x₂ -5x₃ –S₁ = -2

                                 3x₁ + x₂ + 7x₃ + 0.S₁ + S₂ = 3

                                 x₁ + 4x₂ + 6x₃ + 0.S₁ + 0.S₂ + S₃ = 5

                                 x₁,      x₂,    x₃,      S₁,      S₂,     S₃  ≥ 0

Now express the above information’s in the simple tableau form:

                     Cj             – 2            – 2            – 4           0           0             0

   C_B             Basic           x₁            x₂             x₃          S₁          S₂           S₃            b

   0                S₁              -2            (-3)            -5          1            0             0      -2 ¬ key row

   0                S₃               1              4              6            0            0             1             5

   X                Ej              0              0              0              0           0             0            0

               Cj-Ej              -2             -2           -4               0           0              0

                                                     Key column

Basic intial solution is  (x₁, x₂, x₃, S₁, S₂, S₃ )

                                                      = ( 0, 0, 0, -2, 3, 5 )

                                                Which is infeasible since S₁ is –ve

As Cj-Ej are either negative or zero and b_i is negative the solution is optimal by infeasible.

As b = -2, the first new is key row.

Find the ratios of elements of Cj – Ej row to the element of key row.    [ Cj – Ej ¸ key row]

Since is the smallest ration, x₂ column is the key column and -3 is the key element.

As All Cj – Ej are negative or zero and all bi are positive, the solution given by the above tableau is optimal. The optimal solution is

                                    x₁  =   0,   x₂  =  ,    x₃  =  0

             \ Max G =

         =>  Min Z    =      Ans.

4.11.2 : problem : Write down the dual of the primal (P) and solve by using complementary slackness theorem.

(P) Maximize, z = x₁ + 2x₂ + 3x₃ + 4x₄

Subject            to        x₁ + 2x₂ + 2x₃ + 3x₄     £ 20

                           2x₁ + x₂ + 3x₃ + 2x₄  £ 20

                           x₁,   x₂,  x₃,  x₄  ³ 0

Solution:  The dual of the primal (P) is given as follows

(D) Minimize,              w = 20y₁ + 20y₂

Subject to                    y₁ + 2y₂ ³ 1

                                    2y₁ + y₂ ³ 2

                                    2y₁ + 3y₂ ³ 3

                                    3y₁ + 2y₂ ³ 4

                                    y₁, y₂ ³ 0

Now, we want to solve the dual problem (D) by using graphical method.

            y1 + 2y2 ³ 1                                        2y1 + y2 ³ 2

             ………. (i)                    ……..…. (ii)

            2y₁ + 3y₂ ³ 3                                       3y₁ + 2y₂ ³ 4

             ………. (iii)               ……….. (iv)

The graph is shaded in figure.

At A ,  W = 20,  + 20.0 = 30

At B ( 1,2, 0, 2), W = 20 ´ 1.2 + 20 ´ (0.2) = 24 + 4 = 28

At C (0, 2)   W = 40

Thus the optimal solution of dual is given at (1, 2, 0, 2)

With W_min = 28.

Now, introducing slack and surplus variable, the primal problem (P) and the dual problem (D) becomes

(P) Maximize,              z = x₁ + 2x₂ + 3x₃ + 4x₄

Subject to                    x₁ + 2x₂ + 2x₃ + 3x₄ + u₁ = 20

                                    2x₁ + x₂ + 3x₃ + 2x₄ + u₂ = 20

                                    x₁, x₂, x₃, x₄, u₁, u₂, ³ 0

(D) Minimize, w = 20y₁ + 20y₂

            Subject to        y₁ + 2y₂ – v₁ = 1

                                    2y₁ + y₂ – v₂ = 3

                                    3y₁ + 2y₂ – v₄ = 4

                                    y₁, y₂, v₁, v₂, v₃, v₄ ³ 0