Decision-makers ever want to develop a theoretical account that can see real-life state of affairss with multiple aims such as net income maximization, cost minimisation, maximization of production capacity etc. which are conflicting in nature. In present scenario there is no individual aim or end for any organisation. Now a yearss higher precedences are given the accomplishment of the ends such as public relationship, labour relationship, etc. Goal scheduling is a 1 technique used to deduce a best possible solution of a multi-objective optimisation job. It is considered as a farther extension of additive scheduling. Goal scheduling is foremost emerged as an issue for insolvable or impracticable additive scheduling jobs.

## A POINT OF ORIGIN OF GOAL PROGRAMMING

A. Charnes, W.W.Cooper and Ferguson ( 1955 ) on executive compensation gave the basic thought of GP harmonizing to Romero ( 1992, p.2 ) . While the term end programming did non look in this 1955 article, this paper did show a forced arrested development thought that embodies the divergence minimising attack inherent in GP. Harmonizing to Romero ( 1992 ) , it was non until Charnes and Cooper ‘s 1961 additive programming text edition, Management Models and Industrial Applications of Linear Programming that the term end scheduling appeared. It was presented as an extension of additive scheduling ( LP ) .

In the Charnes and Cooper ( 1961, pp. 215-221 ) book, end scheduling was suggested for usage in work outing insolvable LP jobs ( e.g. impracticable LP jobs ) .

## Concept OF GOAL PROGRAMMING

As GP is derived from LP, the GP theoretical account can be found by repeating the LP theoretical account, its premises and patterning notation. See the canonical signifier of LP:

capable to:

for one = 1, . . . , m

xj a‰? 0 for J = 1, . . . , n ( 1.1 )

where

xj = nonnegative determination variables or terra incognitas for J = 1, . . . , n

cj = cost associated with each unit of their several determination variable for part to the nonsubjective map, Z for J = 1, . . . , n

aij = coefficients that represent the per unit use by xj of the right-hand-side coefficient of Bi for i= 1, 2, . . . , m and J = 1, 2, . . . , n

This LP theoretical account consists of a individual aim or end of minimising the nonsubjective map or Z map. Here, the nonsubjective map is capable to a set of m restraints with n determination variables required to be non negative.

The LP theoretical account in ( 1.1 ) allows the possibility of positive divergence ( called excess in Linear Programming nomenclature ) from the right-hand-side coefficients in the theoretical account, since the amount of the merchandises in the left-hand-side can be greater-than or equal to any Bi. It is besides true that LP theoretical account can allow negative divergence ( called slack in Linear Programming nomenclature ) from Bi. Any LP theoretical account can include greater-than or equal-to and less-than or equal-to types of restraints.

In an LP theoretical account, the mathematical demands represented by the restraints must be satisfied in order to hold a executable solution. Therefore, when one or more restraints of an LP theoretical account finds itself outside or in struggle with the country of executable solutions, we have an impracticable solution. Such restraints are called as difficult restraints.

Charnes and Cooper ( 1961 ) suggested in their text edition that each restraint in a LP theoretical account can be considered as a separate map, called a functional. These functional are considered as single aims or ends to be attained where Bi are the set of aims or ends that must be satisfied in order to hold a executable solution. Therefore, end agencies objective in concurrence with the aspiration degree, where, Bi besides called as aspiration degree. If we subtract bi from both sides of an equality restraint, we can show the functional as the absolute value of an LP restraint, or:

( 1.2 )

As it is non ever possible to accomplish every end to the extent the determination shaper desires, GP helps to make a satisfactory degree of multiple aims. Therefore, the modern director attempts to “ satisfise ” or “ come every bit near as possible ” to the set ends because of which GP is frequently cited as a satisficing based technique.

Charnes and Cooper ( 1961, p. 217 ) illustrated how that divergence from ends bing in impracticable LP job could be minimized by puting the variables stand foring divergence straight in the nonsubjective map of the theoretical account. This allows multiple ( and sometimes conflicting ) ends to be expressed in a theoretical account that will allow a solution to be found. Multiple and at odds ends are considered as a separating characteristic to depict how a GP theoretical account differs from an LP theoretical account.

Basic premises of end scheduling are:

Non-negative variables

Conditionss of certainty

Variables are independent

Limited resources

GP consists of System restraints and Goal restraints. System restraints are:

Concerned with resources

Can non be violated

Physical

For illustration, figure of labour hours available for fabrication

Goal restraints are:

Concerned with the mark values

Can be changed/modified

For illustration, desire to accomplish a certain degree of net income.

The general end programming theoretical account can be expressed as follows:

Capable to the additive restraints:

Goal restraints:

System restraints:

With, , xj a‰? 0, for one = 1, … , m ; for J = 1, … , n ( 1.3 )

Where there are thousand ends, P system restraints and n determination variables

Z = nonsubjective map

aij = the coefficient associated with variable J in the ith end

xj = the jth determination variable

Bi = the associated right manus side value

= negative deviational variable from the ith end ( underachievement )

= positive deviational variable from the ith end ( overachievement ) .

Both overachievement and underachievement of a end can non happen at the same time. Hence, either one or both of these variable must hold a zero value ; that is,

## .

Both variables apply for the non-negativity demand as to all other additive scheduling variables ; that is,

## .

The divergence variables are related to the functional algebraically where:

Table 1 shows three basic options to accomplish assorted ends:

## Table 1: Procedure for accomplishing a end

## Minimize

## Goal

## If end is achieved

Minimize the underachievement

Minimize the overachievement

Minimize both under- and overachievement

EXAMPLE 1: Suppose a steadfast manufactures two merchandises which yield net income of Rs. 50 and Rs. 70 per unit, respectively.Each type A merchandise requires 2 hours to fabricate and each type B merchandise requires 4 hours to fabricate. The hebdomadal handiness of labour hr is limited to 360 hours. The natural stuff required to fabricate type A merchandise is 5 kilogram /unit and for type B is 6 kg/unit with the entire handiness of 2000 kilogram of natural stuff. Explicate it as a end scheduling job.

If net income maximization is the chief nonsubjective i.e. merely one nonsubjective map so linear programming can be used to happen the optimum solution. Thus the LPP is formulated as

Maximize net income, Z = 50×1 + 70×2

Subject to

2×1 + 4×2 & lt ; = 360 ( Labor hours )

5×1 + 6×2 & lt ; = 2000 ( Raw stuff )

x1, x2 & gt ; = 0

where

x1 = Number of units of type A merchandise manufactured

x2 = Number of units of type B merchandise manufactured

Now, suppose the direction is non interested in maximising net income but instead want a certain net income degree of say 10,000 as desirable to accomplish under the given restraints. Then, for this it is required to explicate a end programming job in which we want to happen the merchandise mix that achieves this end every bit near as possible under the given restraints.

Let

d1- = underachievement of the net income end of Rs. 10,000

d1+ = overachievement of the net income end of Rs. 10,000

Now we province the end programming theoretical account as:

Minimize Z = d1- + d1+

Subject to

50×1 + 70×2 +d1- – d1+ = 10,000 ( Profit end )

2×1 + 4×2 & lt ; = 360 ( Labor hours )

5×1 + 6×2 & lt ; = 2000 ( Raw stuff )

x1, x2, d1- , d1+ & gt ; = 0

## Extension to every bit of import ends

In the above illustration, see the undermentioned ends each holding equal importance i.e. equal precedence.

## Goal 1: To avoid underachievement of the net income end

## Goal 2: To minimise overtime of the labour hours available

## Goal 3: To to the full use the natural stuff available

To specify the end scheduling job for the above status, see the undermentioned deviational variables:

d1- = underachievement of the net income end of Rs. 10,000

d1+ = overachievement of the net income end of Rs. 10,000

d2- = underachievement of available labour hours

d2+ = overachievement of available labour hours

d3- = underachievement of available natural stuff

d3+ = overachievement of available natural stuff

The new nonsubjective map and restraints for the end scheduling job are:

Minimize Z = d1- + d2+ + d3-

Subject to

50×1 + 70×2 +d1- – d1+ = 10,000 ( Profit end )

2×1 + 4×2 +d2- – d2+ = 360 ( Labor hours )

5×1 + 6×2 +d3- – d3+ = 2000 ( Raw stuff )

x1, x2, d1- , d1+ , d2- , d2+ , d3- , d3+ & gt ; = 0

## COMPARISON OF LINEAR PROGRAMMING AND GOAL PROGRAMMING

Linear programming attempts to maximise or minimise the nonsubjective map say net income maximization or cost minimisation whereas in end programming divergences between ends and what can be achieved within the given set of restraints are to be minimized.

Linear programming involves central values or Numberss which are the footing of computations expressed in exact sum i.e. net income or loss. Goal scheduling allows for an ordinal solution as practically talking direction is unable to stipulate the cost or public-service corporation of a end or a subgoal but upper or lower bounds may be stated for each end or a subgoal. Here, director is required to put precedence of attainment of each end or subgoal and rank them in ordinal sequence for determination analysis.

## LEXICOGRAPHIC GOAL PROGRAMMING MODEL

In a determination doing state of affairs, the ends set by direction can be achieved merely at the disbursal of other ends. For this to carry through it is necessary to set up a hierarchy of importance among the declared ends so that higher precedence ends are considered first and are satisfied followed by lower-priority ends. Therefore before work outing a end scheduling job, the ends need to be ranked. Lexicographic end scheduling is besides called the preemptive or non-Archimedean end programming theoretical account ( Ignizio, 1985 ) . In precedence end scheduling, the aims can be divided into different precedence categories or k ranks ( P1, P2aˆ¦ ) . Here it is assumed that no two ends have equal precedence. Here, P ‘s are non given existent values, but this is a method to bespeak that one end is more of import than the other. These precedence factors have the relationship Pj & gt ; & gt ; & gt ; nPj+1 ( j=1,2, aˆ¦k ) where & gt ; & gt ; & gt ; means is “ really much greater than ” and n is really big. This indicates nevertheless big Ns may be, generation of precedence with Ns can non do nPj+1 greater than Pj. This means that precedence ranking is absolute i.e. the P1 end is so much more of import than the P2 end and P2 end will ne’er be attempted until the P1 end is achieved to the greatest extent possible.

The above theoretical account can be restated as:

Capable to the additive restraints:

Goal restraints:

System restraints:

With di+ , di- , xj a‰? 0, for one = 1, … , m ; for J = 1, … , n ( 1.4 )

Where there are thousand ends, P system constaints, k precedence degrees and n determination variables

Z = nonsubjective map

aij = the coefficient associated with variable J in the ith end

xj = the jth determination variable

Bi = the associated right manus side value

= negative deviational variable from the ith end ( underachievement )

= positive deviational variable from the ith end ( overachievement ) .

Pk = the precedence factor of the kth end.

Here, the difference between equations ( 1.3 ) and ( 1.4 ) is the precedence factor in the nonsubjective map.

The nonsubjective map of a end programming theoretical account may dwell of nonhomogeneous units of step, such as Rs. , Kg, lbs, dollar, instead than one type of unit. To get the better of this, if the unwanted divergence variables are assumed to be additive and dissociable so it will presume the signifier

where United Kingdom is the discriminatory weight associated with the minimisation of unwanted deviational variable, at kth precedence degree. vk is the discriminatory weight associated with the minimisation of unwanted deviational variable, at kth precedence degree. Division by Bi is a per centum standardization invariable associated with ith end which in bend is necessary to scale all the ends onto the same units of measuring.

In the above illustration let the undermentioned precedences are assigned:

Precedence 1 is attached to the accomplishment of end 1, precedence 2 to accomplishment of end 3 and precedence 3 to accomplishment of end 2.

Then, the pre-emptive end scheduling job is formulated as:

Minimize Z =P1 d1- + P2 d3- + P3 d2+

Subject to

50×1 + 70×2 +d1- – d1+ = 10,000 ( Profit end )

2×1 + 4×2 +d2- – d2+ = 360 ( Labor hours )

5×1 + 6×2 +d3- – d3+ = 2000 ( Raw stuff )

x1, x2, d1- , d1+ , d2- , d2+ , d3- , d3+ & gt ; = 0

## Leaden GOAL PROGRAMMING MODEL

Leaden end scheduling is used for direct comparing of aims. The weighting of deviational variables at the same precedence degree shows the comparative importance of each divergence. Charnes and Cooper ( 1977 ) stated the leaden end programming theoretical account as:

Capable to the additive restraints:

Goal restraints:

System restraints:

With di+ , di- , xj a‰? 0, for one = 1, … , m ; for J = 1, … , n ( 1.5 )

Where wi+ and wi- are non-negative invariables stand foring the comparative weight to be assigned to the several positive and negative divergence variables. The greater the weight the greater the assigned importance to minimise the several divergence variable to which the relation weight is attached. This theoretical account is a non-preemptive theoretical account that seeks to minimise the sum weighted divergence from all ends stated in the theoretical account.

While Ijiri ( 1965 ) had introduced the thought of uniting pre-emptive precedences and weighting, Charnes and Cooper ( 1977 ) suggested the end programming theoretical account as:

Capable to the additive restraints:

Goal restraints:

System restraints:

With di+ , di- , xj a‰? 0, for one = 1, … , m ; for J = 1, … , n ( 1.6 )

See the undermentioned discriminatory weights attached to the old job and so stand for this state of affairs as a leaden end plan with the discriminatory weights and precedences given:

## Goal

## Goal description

## Preference weight

## 1

To avoid underachievement of the net income end

5.0

## 2

To minimise overtime of the labour hours available

3.0

## 3

To to the full use the natural stuff available

2.0

The leaden end scheduling job is defined as:

Minimize Z =P1 ( 5.0 d1- ) + P2 ( 3.0d3- ) + P3 ( 2.0d2+ )

Subject to

50×1 + 70×2 +d1- – d1+ = 10,000 ( Profit end )

2×1 + 4×2 +d2- – d2+ = 360 ( Labor hours )

5×1 + 6×2 +d3- – d3+ = 2000 ( Raw stuff )

x1, x2, d1- , d1+ , d2- , d2+ , d3- , d3+ & gt ; = 0

## GRAPHICAL SOLUTION OF GOAL PROGRAMMING PROBLEMS:

Graphic method is used for work outing a two determination variables job. Following procedural stairss are employed after the job has been formulated for work outing the end scheduling job.

Measure 1: Plot all the structural or system or difficult restraints and place the executable part. In instance no such restraint exists, the executable part is where x1 and x2 are both non-negative.

Measure 2: Plot the consecutive lines matching to the end restraints. For this, set the deviational variables in the end restraints equal to zero and plot the resulting equation labeling the deviational variables.

Measure 3: Choose the point or points which best satisfy the highest precedence end for placing the top-priority solution.

Measure 4: Move to the following highest precedence end and find the best solution ( s ) in such a mode that this “ best ” solution does non degrade the solution ( s ) already achieved for higher precedence ends.

Measure 5: Repeat measure 4 until all the precedence degrees are investigated.

Measure 6: Identify the optimal point and analyse it in footings of grades of end attainment.

The intent of graphical method is to exemplify the construct of end programming solutions instead than a general technique for work outing end scheduling jobs. Therefore, graphical method is recommended for jobs affecting two structural variables.

EXAMPLE 2: A company manufactures two merchandises wirelesss and transistors. Harmonizing to past experience, production of either a wireless or a transistor requires an norm of one hr in the works. The works has a normal production capacity of 40 hours a hebdomad. The selling section studies that the maximal figure of wirelesss and transistors that can be sold are 24 and 30 severally for a hebdomad because of limited gross revenues chance. The gross border from the sale of a wireless is Rs. 80 and that from transistor is Rs. 40. The company has established the undermentioned ends and has assigned them precedences arranged in order of their importance as follows:

First, company wants to avoid any underutilization of normal production capacity.

Second, company wants to sell as many wirelesss as possible. Since the gross border from the sale of wireless is twice the sum from transistor, company has twice every bit much desire to accomplish gross revenues for wireless as for transistor.

Third, company wants to minimise the overtime operation for the works every bit much as possible.

Formulate the job as a end scheduling job and happen the optimal solution utilizing graphical method.

Solution: Formulation of end scheduling job:

Let

x1, x2 = Number of wirelesss and transistors manufactured, severally.

d1- = Underachievement of normal operation hours

d1+ = Overachievement of normal operation hours

d2- = Underachievement of gross revenues end for wireless

d2+ = Overachievement of gross revenues end for wireless

d3- = Underachievement of gross revenues end for transistor

d3+ = Overachievement of gross revenues end for transistor

Then the given job is formulated as a end scheduling job defined as follows:

Minimize Z = P1 d1- + 2 P2 d2- + P2 d3- + P3 d1+

Subject to

x1 + x2 + d1- – d1+ = 40

x1 + d2- – d2+ = 24

x2 + d3- – d3+ = 30

x1, x2, d1- , d1+ , d2- , d2+ , d3- , d3+ a‰? 0

## SOLUTION USING GRAPHICAL METHOD

Measure 1: Taking the deviational variables equal to zero in each restraint, secret plan all the end equations, as shown in the figure. Then associate pointers with each line to stand for underachievement or overachievement of the end.

Measure 2: Identify top precedence end: Unwanted deviational variable in precedence 1 is d1- . Puting d1- = 0 ( minimal value ) , the executable part is the shaded part as shown in the graph stand foring d1+ . Any point in this shaded part satisfies the first end to be achieved.

Measure 3: Identify 2nd precedence end: In the 2nd precedence end, underachievement of the figure of units sold of each wireless and transistor is to be minimized with higher importance given to selling of wireless as compared to transistor. For this set, d2- = 0. Similarly, the mark of gross revenues end of transistors to 30 is attained by puting d3- = 0. Therefore, the 2nd precedence ends are attained or satisfied at the point P with x1= 24, x2 =30 in the executable part of the top precedence.

Measure 4: Identify 3rd precedence end: In the 3rd precedence end, overachievement of the normal operation hours, d1+ is to be minimized. Obviously, d1+ = 0 at all points on the line section AB, at which top precedence end is satisfied. But 2nd precedence end is non achieved at any point on the line section AB. We can non accomplish the 3rd end without giving the 2nd end. Therefore, first two end are satisfied and 3rd end is non satisfied. Puting d2- = 0, d3- = 0, x1= 24, x2 =30, we get, d2+ = 0, d3+ = 0.

Substituting the value of x1 and x2 in first end restraint with d1- = 0, we get,

d1+ = 14.

Hence, the company should bring forth 24 wirelesss and 30 transistors per hebdomad, so that the first two ends are to the full achieved and in the 3rd end the overtime operation of the works is minimized to 14 hours per hebdomad.

EXAMPLE 3: Solve the undermentioned end programming job utilizing graphical method.

Minimize Z = 2P1 d1+ + 3 P1 d2+ + P2 d3- + P3 d4+

Subject to

x1 + x2 + d1- – d1+ = 10

x1 + d2- – d2+ = 4

5×1 + 3×2+ d3- – d3+ = 56

x1 + x2 + d4- – d4+ = 12

x1, x2, d1- , d1+ , d2- , d2+ , d3- , d3+ , d4- , d4+ a‰? 0

The graphical solution to the above job is given below.

We foremost get down with first precedence degree. The solution infinite fulfilling the set of precedence one is indicated in the graph with both d1+ and d2+ set to zero with accomplishment of 2nd end considered foremost holding higher weight followed with accomplishment of first end.

Next we attempt to fulfill precedence two without degrading the solution to level 1. However, d3- can non be set to zero as this would degrade the solution at precedence degree 1.

Further, we attempt to accomplish precedence degree 3 which attempt to minimise d4- by puting d4- = 0. Consequently the concluding solution is given by:

x1= 4, x2 =6, d1- = 0, d1+ =0, d2- = 0, d2+ = 0, d3- = 18, d3+ = 0, d4- = 2, d4+ = 0

## MODIFIED SIMPLEX METHOD APPLIED TO GOAL PROGRAMMING PROBLEMS

In this subdivision we present an algorithm to work out a additive end programming theoretical account, based on the well known simplex method used to work out additive scheduling job. Therefore, simplex method used to work out end scheduling job is similar to that for a additive scheduling job in the modified signifier. Following stairss are involved for work outing a end scheduling job by modified simplex method:

Measure 1: Establishing the Initial tabular array: Concept the initial simplex tabular array in the same mode as for additive scheduling job with the coefficients of the determination variables and the deviational variables placed in the appropriate columns. Besides, compose the preemptive precedence ends P1, P2, . . . , in xB column, get downing from underside to the top with the first precedence, P1 placed at the underside and the least precedence placed at the top.

Measure 2: The preemptive precedence factors with weights attached with the deviational variables in the nonsubjective map Z will stand for cj values as there is no net income maximization or cost minimisation in the nonsubjective map in end scheduling jobs. Here we try to minimise the divergences from the end every bit much as possible, by minimising the deviational variables through the usage of preemptive precedence factors and different weights attached with the deviational variables in the nonsubjective map.

Measure 3: Trial of optimality: As different ends are measured in different units, compute the values of Zj and cj – Zj individually for each of the precedence ends P1, P2, . . . , . Zj and cj – Zj are computed in the same mode as in the usual simplex method of additive scheduling job. Therefore,

cj – Zj = ( cj – cB column ) T. ( jth column )

and Zj = ( cB column ) T. ( xB column )

The optimality standard Zj or cj – Zj is a matrix of size K x N, where K represents the figure of preemptive precedence degrees and N is the figure of variables including both determination and deviational variables.

For optimality trial, look into the c1 – Z1 row for the top precedence P1 ; J =1. If all cj – Zja‰? 0 in the P1 row or there is zero in P1 row in xB column, so top precedence end P1 is said to be achieved.

In instance at least one of these entries is negative in P1 row and there is no nothing in P1 row in xB column, so the end P1 is non achieved and can be improved farther. For this proceed to the following measure.

Measure 4: To find the come ining variable: The variable in the column matching to the largest or most negative c1 – Z1 value in the P1 row is considered as the come ining variable. In instance of a tie, see the following lower precedence degree. The column matching to the largest negative value in the lower precedence row, out of the columns in which there is a tie in c1 – Z1 row, is selected as the entrance variable.

Measure 5: To find the surpassing variable: The procedure is the same as we do in simplex method in additive scheduling job. The variable corresponding to the minimal non-negative value in the row known as cardinal row, obtained by spliting the values in the xB column by the corresponding positive values in the column called as cardinal column is selected as the surpassing variable.

The intersection component of the cardinal row and cardinal column is called as the cardinal component.

Measure 6: Follow the same stairss farther as in simplex method in additive scheduling job where we cut down the cardinal component to 1 and with its aid all other elements in the cardinal column are reduced to 0 giving us new reduced matrix.

For this matrix, once more determine Zj or cj – Zj for each of the precedence ends P1, P2, . . . , . Again do the optimality trial. If all the entries in P1 row are positive so first end is achieved. Besides, here values in xB column in P1 row will be zero to demo that first end is to the full achieved.

If at least one of these entries is negative in P1 row and there is no nothing in P1 row in xB column, so the end P1 is non achieved. In this instance once more repeat measure 4, 5 and 6.

Measure 7: After accomplishing end placed at P1 precedence, continue to accomplish the following precedence end P2 in the same mode discussed above. The end P2 can non be improved or achieved farther if there is positive entry in row P1 below the most negative entry in row P2.

Continue this procedure until the lowest precedence end is to the full achieved or achieved to the nearest satisfaction.

For clear apprehension of the above discussed method see the illustration of illustration 2 discussed supra.

Minimize Z = P1 d1- + 2 P2 d2- + P2 d3- + P3 d1+

Subject to

x1 + x2 + d1- – d1+ = 40

x1 + d2- – d2+ = 24

x2 + d3- – d3+ = 30

x1, x2, d1- , d1+ , d2- , d2+ , d3- , d3+ a‰? 0

Taking x1 = x2 = d1+ = d2+ = d3+ = 0, we get d1- =40, d2- = 24, d3- = 30 which is the get downing basic executable solution. Calculating modified simplex method, we get,

Measure 1: Formulation of initial tabular array:

## Bacillus

## cB

## cj

## 0

## 0

## P1

## P3

## 2P2

## 0

## P2

## 0

## Minimum ratio ( xB/xi )

## xB

## x1

## x2

## d1-

## d1+

## d2-

## d2+

## d3-

## d3+

## d1-

## P1

40

1

1

1

-1

0

0

0

0

40

## d2-

## 2P2

24

1

0

0

0

1

-1

0

0

24a†’

## d3-

## P2

30

0

1

0

0

0

0

1

-1

## –

## cj-Zj

## P3

0

0

-1

0

1

0

0

0

0

## P2

78

-2

-1

0

0

0

2

0

1

## P1

40

-1

0

0

1

0

0

0

0

## a†‘

Measure 2: cj row is written at he exceed of the tabular array.

Measure 3: Trial of optimality: Here compute cj-Zj ; a?ˆ J = 1, 2, . . . , 8

C1-Z1 = 0 – ( P1, 2P2, P2 ) . ( 1, 1, 0 ) T = -P1-2P2

C2-Z2 = 0 – ( P1, 2P2, P2 ) . ( 1, 0, 1 ) T = -P1-P2

C3-Z3 = 0 – ( P1, 2P2, P2 ) . ( 1, 0, 0 ) T = 0

C4-Z4 = 0 – ( P1, 2P2, P2 ) . ( -1, 0, 0 ) T = P3 + P1

C5-Z5 = 0 – ( P1, 2P2, P2 ) . ( 0, 1, 0 ) T = 0

C6-Z6 = 0 – ( P1, 2P2, P2 ) . ( 0, -1, 0 ) T = 2P2

C7-Z7 = 0 – ( P1, 2P2, P2 ) . ( 0, 0,1 ) T = 0

C8-Z8 = 0 – ( P1, 2P2, P2 ) . ( 0, 0, -1 ) T = P2

Note: – All the entries in the columns matching to vectors in the footing are zero. So, we compute cj-Zj for columns matching to non-basic variables merely.

## Z = cBxB = ( P1, 2P2, P2 ) . ( 40, 24, 30 ) T = 40P1 + 78P2

Measure 4: The most negative entry in top precedence P1 is -1 in the first column. Therefore, x1 is the incoming variable and calculating the lower limit ratio, xB/xi, d2-

Is the surpassing variable. Thus the cardinal component is a21.

Measure 5: Here cut downing all the elements in cardinal column equal to nothing with the aid of cardinal component, we obtain the following decreased tabular array as:

## Bacillus

## cB

## cj

## 0

## 0

## P1

## P3

## 2P2

## 0

## P2

## 0

## Minimum ratio ( xB/xi )

## xB

## x1

## x2

## d1-

## d1+

## d2-

## d2+

## d3-

## d3+

## d1-

## P1

16

0

1

1

-1

-1

1

0

0

16a†’

## x1

## 0

24

1

0

0

0

1

-1

0

0

## –

## d3-

## P2

30

0

1

0

0

0

0

1

-1

30

## cj-Zj

## P3

0

0

0

0

1

0

0

0

0

## P2

30

0

-1

0

0

2

0

0

1

## P1

16

0

-1

0

1

0

-1

0

0

## a†‘

Here once more calculating cj-Zj for columns matching to non-basic variables merely as all entries in the columns matching to basic variables will be zero, we get,

C2-Z2 = 0 – ( P1, 0, P2 ) . ( 1, 0, 1 ) T = -P1-P2

C4-Z4 = P3 – ( P1, 0, P2 ) . ( -1, 0, 0 ) T = P3 + P1

C5-Z5 = 2P2 – ( P1, 0, P2 ) . ( -1, 1, 0 ) T = 2P2 + P1

C6-Z6 = 0 – ( P1, 0, P2 ) . ( 1, -1, 0 ) T = -P1

C8-Z8 = 0 – ( P1, 0, P2 ) . ( 0, 0, -1 ) T = P2

The most negative entry in top precedence P1 is -1 in the 2nd column. Therefore, x2 is the incoming variable and calculating the lower limit ratio, xB/xi, d1- is the surpassing variable. Thus the cardinal component is a12.

## Z = cBxB = ( P1, 0, P2 ) . ( 16, 24, 30 ) T = 16P1 + 30P2

Measure 6: Repeating the above stairss of cut downing all the elements in cardinal column equal to nothing with the aid of cardinal component, we obtain the following decreased tabular array as:

## Bacillus

## cB

## cj

## 0

## 0

## P1

## P3

## 2P2

## 0

## P2

## 0

## Minimum ratio ( xB/xi )

## xB

## x1

## x2

## d1-

## d1+

## d2-

## d2+

## d3-

## d3+

## x2

## 0

16

0

1

1

-1

-1

1

0

0

## –

## x1

## 0

24

1

0

0

0

1

-1

0

0

## –

## d3-

## P2

14

0

0

-1

1

1

-1

1

-1

14a†’

## cj-Zj

## P3

0

0

0

0

1

0

0

0

0

## P2

14

0

0

1

-1

1

1

0

1

## P1

0

0

0

1

0

0

0

0

0

## a†‘

Here once more calculating cj-Zj for columns matching to non-basic variables merely as all entries in the columns matching to basic variables will be zero, we get,

C3-Z3 = P1 – ( 0,0, P2 ) . ( 1, 0, -1 ) T = P1 + P2

C4-Z4 = P3 – ( 0,0, P2 ) . ( -1, 0, 1 ) T = P3 – P1

C5-Z5 = 2P2 – ( 0,0, P2 ) . ( -1, 1, 1 ) T = P2

C6-Z6 = 0 – ( 0,0, P2 ) . ( 1, -1, -1 ) T = P2

C8-Z8 = 0 – ( 0,0, P2 ) . ( 0, 0, -1 ) T = P2

Since all the entries in P1 row are a‰? 0, so end at precedence foremost is achieved to the full. Now we proceed to accomplish end P2 without impacting the accomplishment of end P1.

## Z = cBxB = ( 0, 0, P2 ) . ( 16, 24, 14 ) T = 14P2

Measure 7: In P2 row, most negative value is -1 in column corresponding to variable d1+ in the above tabular array. Therefore, d1+ is the incoming variable and calculating the lower limit ratio, xB/xi, d3- is the surpassing variable. Thus the cardinal component is a34.

Reducing the above tabular array as done in simplex method, we get,

## Bacillus

## cB

## cj

## 0

## 0

## P1

## P3

## 2P2

## 0

## P2

## 0

## Minimum ratio ( xB/xi )

## xB

## x1

## x2

## d1-

## d1+

## d2-

## d2+

## d3-

## d3+

## x2

## 0

30

0

1

0

0

0

0

1

-1

## x1

## 0

24

1

0

0

0

1

-1

0

0

## d1+

## P3

14

0

0

-1

1

1

-1

1

-1

## cj-Zj

## P3

14

0

0

1

0

-1

1

-1

1

## P2

0

0

0

0

0

2

0

1

0

## P1

0

0

0

1

0

0

0

0

0

Here once more calculating cj-Zj for columns matching to non-basic variables merely as all entries in the columns matching to basic variables will be zero, we get,

C3-Z3 = P1 – ( 0,0, P3 ) . ( 0, 0, -1 ) T = P1 + P3

C5-Z5 = 2P2 – ( 0,0, P3 ) . ( 0, 1, 1 ) T = 2P2- P3

C6-Z6 = 0 – ( 0,0, P3 ) . ( 0, -1, -1 ) T = P3

C7-Z7 = P2 – ( 0,0, P3 ) . ( 1, 0, 1 ) T = P2 – P3

C8-Z8 = 0 – ( 0,0, P3 ) . ( -1, 0, -1 ) T = P3

## Z = cBxB = ( 0, 0, P3 ) . ( 30, 24, 14 ) T = 14P3

Here all cj-Zj a‰? 0 in P1 and P2 rows and 0, 0 in xB column. Therefore, the precedence ends P1 and P2 are to the full achieved. Now consider P3 row. Here all cj-Zj are non non-negative, and most negative entries are -1 and -1 in this row. But no farther betterment is possible as below -1 and -1, there are positive entries in the higher precedence order. Therefore, the optimum solution of the end scheduling job is

x1 = 24, x2 = 30, d1+ = 14, d1- =0, d2+ = 0, d2- = 0, d3+ = 0, d3- = 0

Here, foremost two precedences P1 and P2 are achieved to the full while precedence end P3 is non achieved to the full.

EXAMPLE 4: A maker produces two merchandises A and B. Each merchandise requires clip in two production sections. Product A requires 20 hours in section 1 and 10 hours in section 2. Merchandise B requires 10 hours in section 1 and 10 hours in section 2. Production clip is limited to 60 hours in section 1 and 40 hours in section 2. Contribution to net incomes for the two merchandises in Rs. 40 and Rs. 60, severally. Minimal net income degree to be achieved is Rs. 1000. Management ends are to maximise net income and to fabricate 2 units of each merchandise. Management considers the divergence of Re. 1 from the net income end equal to one unit divergence from the merchandise end. Explicate the above job as end scheduling job and work out it utilizing modified simplex method.

Solution: The end scheduling job is formulated as:

Minimize Z = d1- + d2- + d3-

Subject to

20×1 + 10×2 a‰¤ 60

10×1 + 10×2 a‰¤ 40

40×1 + 80×2 + d1- – d1+ = 1000

x1 + d2- – d2+ = 2

x2 + d3- – d3+ = 2

x1, x2, d1- , d1+ , d2- , d2+ , d3- , d3+ a‰? 0

where,

x1, x2 = Number of units of merchandise A and B manufactured, severally.

d1- = Underachievement of net income end

d1+ = Overachievement of net income end

d2- = Underachievement of units manufactured of merchandise Angstrom

d2+ = Overachievement of units manufactured of merchandise Angstrom

d3- = Underachievement of units manufactured of merchandise B

d3+ = Overachievement of units manufactured of merchandise B

Introducing slack variables S1 and S2, we get,

Minimize Z = d1- + d2- + d3-

Subject to

20×1 + 10×2 + S1 a‰¤ 60

10×1 + 10×2 + S2 a‰¤ 40

40×1 + 80×2 + d1- – d1+ = 1000

x1 + d2- – d2+ = 2

x2 + d3- – d3+ = 2

x1, x2, d1- , d1+ , d2- , d2+ , d3- , d3+ , S1, S2a‰? 0

Initial basic executable solution is given by

x1 = x2 = d1+ = d2+ = d3+ = 0, d1- =1000, d2- = 2, d3- = 2, S1 = 60, S2 = 40

Following the same stairss as in the above illustration, modified simplex method is shown in the undermentioned tabular array:

## Bacillus

## cB

## cj

## 0

## 0

## P1

## P3

## 2P2

## 0

## P2

## 0

## 0

## 0

## Minimum ratio ( xB/xi )

## xB

## x1

## x2

## d1-

## d1+

## d2-

## d2+

## d3-

## d3+

## S1

## S2

## S1

## 0

60

20

10

0

0

0

0

0

0

1

0

6

## S2

## 0

40

10

10

0

0

0

0

0

0

0

1

4

## d1-

## 1

1000

40

80

1

-1

0

0

0

0

0

0

1000/80

## d2-

## 1

2

1

0

0

0

1

-1

0

0

0

0

## –

## d3-

## 1

2

0

1

0

0

0

0

1

-1

0

0

2a†’

## cj-Zj

## 5000

## -41

## -81

## a†‘

## 0

## 1

## 0

## 1

## 0

## 1

## 0

## 0

## S1

## 0

60

20

0

0

0

0

0

-10

10

1

0

4

## S2

## 0

40

10

0

0

0

0

0

-10

10

0

1

2a†’

## d1-

## 1

840

40

0

1

-1

0

0

-80

80

0

0

10.5

## d2-

## 1

2

1

0

0

0

1

-1

0

0

0

0

## –

## x2

## 0

2

0

1

0

0

0

0

1

-1

0

0

## –

## cj-Zj

## 842

## -41

## 0

## 0

## 1

## 0

## 1

## 81

## -81

## a†‘

## 0

## 0

## S1

## 0

20

10

0

0

0

0

0

0

0

1

-1

## d3+

## 0

2

1

0

0

0

0

0

-1

1

0

1/10

## d1-

## 1

680

-40

0

1

-1

0

0

0

0

0

-8

## d2-

## 1

2

1

0

0

0

1

-1

0

0

0

0

## x2

## 0

4

1

1

0

0

0

0

0

0

0

1/10

## cj-Zj

## 682

## 39

## 0

## 0

## 1

## 0

## 1

## 0

## 0

## 0

## 8

Since all cj-Zj a‰? 0, hence, this is an optimum solution with

x1 = 0, x2 = 4, d1+ = 0, d1- =680, d2+ = 0, d2- = 2, d3+ = 2, d3- = 0, S1 = 20, S2 = 0

Therefore, production end of merchandise A is missed by 2 and net income end is missed by Rs. 680.

EXAMPLE 5: A steadfast produces two merchandises P and Q, which yield a part border of Rs. 120 and Rs. 90 per unit, severally. The house has a limited capacity in the two sections where these merchandises need treating. The handiness and demands are given below:

## Department

## Processing clip ( hours )

## Daily Availability ( hours )

## Merchandise P

## Merchandise Q

## I

6

3

90

## Two

3

6

72

The direction of the house has specified the undermentioned ends:

## Goal

## Precedence

Achieve a day-to-day gross revenues of at least 13 units of merchandise P

P1

Produce a product-mix to do a day-to-day net income of at least Rs. 1950

P2

Achieve a day-to-day gross revenues of at least 5 units of merchandise Q

P3

Formulate the job as a end scheduling job and happen the optimal solution.

Solution: The end scheduling job is formulated as:

Minimize Z = P1 d2- + P2d1- + P3d3-

Subject to

6×1 + 3×2 a‰¤ 90

3×1 + 6×2 a‰¤ 72

120×1 + 90×2 + d1- – d1+ = 1950

x1 + d2- – d2+ = 13

x2 + d3- – d3+ = 5

x1, x2, d1- , d1+ , d2- , d2+ , d3- , d3+ a‰? 0

where,

x1, x2 = Number of units of merchandise P and Q manufactured, severally.

d1- = Underachievement of net income end

d1+ = Overachievement of net income end

d2- = Underachievement of units manufactured of merchandise P

d2+ = Overachievement of units manufactured of merchandise P

d3- = Underachievement of units manufactured of merchandise Q

d3+ = Overachievement of units manufactured of merchandise Q

Introducing slack variables S1 and S2, we get,

Minimize Z = P1 d2- + P2d1- + P3d3-

Subject to

6×1 + 3×2 + S1a‰¤ 90

3×1 + 6×2 +S2a‰¤ 72

120×1 + 90×2 + d1- – d1+ = 1950

x1 + d2- – d2+ = 13

x2 + d3- – d3+ = 5

x1, x2, d1- , d1+ , d2- , d2+ , d3- , d3+ , S1, S2a‰? 0

Initial basic executable solution is given by

x1 = x2 = d1+ = d2+ = d3+ = 0, d1- =1950, d2- = 13, d3- = 5, S1 = 90, S2 = 72

Following the same stairss as in the above illustration, modified simplex method is shown in the undermentioned tabular array:

## Bacillus

## cB

## cj

## 0

## 0

## P2

## 0

## P1

## 0

## P3

## 0

## 0

## 0

## Minimum ratio ( xB/xi )

## xB

## x1

## x2

## d1-

## d1+

## d2-

## d2+

## d3-

## d3+

## S1

## S2

## S1

## 0

90

6

3

0

0

0

0

0

0

1

0

90/6

## S2

## 0

72

3

6

0

0

0

0

0

0

0

1

72/3

## d1-

## P2

1950

120

90

1

-1

0

0

0

0

0

0

1950/120

## d2-

## P1

13

1

0

0

0

1

-1

0

0

0

0

13a†’

## d3-

## P3

5

0

1

0

0

0

0

1

-1

0

0

## –

## cj-Zj

## P3

5

0

1

0

0

0

0

0

1

0

0

## P2

1950

-120

-90

0

-1

0

0

0

0

0

0

## P1

13

-1

## a†‘

0

0

0

0

1

0

0

0

0

## S1

## 0

12

0

3

0

0

-6

6

0

0

1

0

2a†’

## S2

## 0

33

0

6

0

0

-3

3

0

0

0

1

11

## d1-

## P2

390

0

90

1

-1

-120

120

0

0

0

0

390/120

## x1

## 0

13

1

0

0

0

1

-1

0

0

0

0

## –

## d3-

## P3

5

0

1

0

0

0

0

1

-1

0

0

## –

## cj-Zj

## P3

5

0

-1

0

0

0

0

0

1

0

0

## P2

390

0

-90

0

1

120

-120

0

0

0

0

## P1

0

0

0

0

0

1

0

## a†‘

0

0

0

0

## d2+

## 0

2

0

## A?

0

0

-1

1

0

0

1/6

0

4a†’

## S2

## 0

27

0

9/2

0

0

0

0

0

0

-1/2

1

6

## d1-

## P2

150

0

30

1

-1

0

0

0

0

-20

0

5

## x1

## 0

15

1

## A?

0

0

0

0

0

0

1/6

0

30

## d3-

## P3

5

0

1

0

0

0

0

1

-1

0

0

5

## cj-Zj

## P3

5

0

-1

0

0

0

0

0

1

0

0

## P2

150

0

-30

0

1

0

0

0

0

20

0

## P1

0

0

0

## a†‘

0

0

1

0

0

0

0

0

## x2

## 0

4

0

1

0

0

-2

2

0

0

1/3

0

## S2

## 0

9

0

0

0

0

9

-9

0

0

-2

1

## d1-

## P2

30

0

0

1

-1

60

-60

0

0

-30

0

## x1

## 0

13

1

0

0

0

1

-1

0

0

0

0

## d3-

## P3

1

0

0

0

0

2

-2

1

-1

-1/3

0

## cj-Zj

## P3

5

0

0

0

0

-2

2

0

1

1/3

0

## P2

150

0

0

0

1

-60

60

0

0

30

0

## P1

0

0

0

0

0

1

0

0

0

0

0

Note that in the above tabular array, there is negative entry -60 in P2 row. But it can non be farther improved as there is positive entry below this component in P1 row. Similarly, no farther betterment of P3 is possible because of positive entry in P1 row. Therefore, P2 and P3 can non be improved farther. Hence the optimum solution of the above end scheduling job is

x1 = 13, x2 = 4, d1+ = 0, d1- =30, d2+ = 0, d2- = 0, d3+ = 0, d3- = 1, S1 = 0, S2 = 9

Therefore, production end of merchandise P is achieved to the full placed at precedence P1. The 2nd precedence end P2 is missed by Rs. 30 and the last precedence end P3 is missed by 1 unit of merchandise Q.

## Test YOUR Understanding

## MULTIPLE COICE QUESTIONS

For using a GP attack, decision-maker must

Set marks for each of the ends

Assign preemptive precedence to each end

Assume that one-dimensionality exists in the usage of resources to accomplish ends

All of these

In GP job, ends are assigned precedences such that

Goals may non hold equal precedence

Higher precedence ends must be achieved before lower precedence ends

Goals of greatest importance are given lowest precedence

None of these.

In a GP job, deviational variables must fulfill the undermentioned features:

di+ – di- = 0

di+ + di- = 0

di- * di+ =0

none of these

## State whether the undermentioned statements are T ( True ) or F ( False )

Goal scheduling begins with the most of import end and continues until the accomplishment of less of import end.

Both the deviational variables related to a end – one of underachievement and the other of overachievement – can together presume positive values.

In the simplex method of end programming the variable to come in the solution-mix is selected with highest precedence row and most positive cj – zj value in it.

The multiple ends specified in a end scheduling job are normally conflicting and incommensurate.

One of the deviational variables in a end scheduling job for a end restraint must be equal to zero.

Penalty weights may be assigned to deviational variables related to different ends, in conformity with the comparative importance to the decision-maker.

The inequalities related to system restraints are stiff and those with end restraints are flexible.

## Exercise

What is end programming? State the difference between additive scheduling and end scheduling?

Why end scheduling is cited as a satisficing based technique?

What are deviational variables? How do they differ from determination variables in traditional LP jobs?

Differentiate between weighted and pre-emptive end programming jobs.

A company manufactures two types of merchandises, A and B. The merchandises are produced in three distinguishable stairss: milling, crunching and fuming. The agenda for machine hours and handiness of each type are as follows:

A ( hr ) B ( hr ) Availability ( hour/month )

Milling 3 2 1700

Crunching 2 1 1400

Fuming 1 3 1600

Net income part of each type of merchandise A and B is Rs. 600 and Rs. 800, severally. The company has three desirable ends of equal importance:

To minimise the idle clip in crunching

To minimise the idle clip in fuming

Making a monthly net income of Rs. 1,00,000.

Set up the job as a end programming theoretical account and happen the optimum solution.

A fabrication house produces two types of merchandises A and B. Harmonizing to past experience, production of either A or B requires an norm of 1 hr in the works. Because of limited market, it is reported that maximal figure of merchandises that can be sold of type A and B are 240 and 300 severally in a month. The works has a normal production capacity of 400 hours in a month. The net net income from the sale of merchandise A is Rs. 800 and from B is Rs. 400. The director of the house set the undermentioned ends arranged in the order of importance:

P1: Avoid underutilization of normal production capacity

P2: Sell maximum possible units of merchandises A and B. The director has twice every bit much desire to accomplish gross revenues for merchandise A as for merchandise B

P3: Minimize the overtime operation of the works every bit much as possible.

Formulate the job as the pre-emptive end scheduling job and work out it by graphical method.

A carpenter produces two merchandises, tabular array and chairs. Each merchandise must treat through two sections, A and B. Department A consists of 30 hours of production capacity per twenty-four hours, and section B consists of 60 hours of production capacity per twenty-four hours. Each unit of a tabular array requires 2 hours in section A and 6 hours in section B. Each unit of chair requires 3 hours in section A and 4 hours in section B. Management wants to find the day-to-day merchandise mix sing the undermentioned precedence degrees:

P1: Avoid underachievement of entire production of tabular array and chairs for 10 units.

P2: Avoid underachievement of production for 7 units of chairs.

P3: Avoid underachievement of production for 8 units of tabular arraies.

Formulate the above job as a end programming theoretical account and work out it utilizing graphical method.

A little pigment company manufactures two types of pigment, latex and enamel. In production, the company uses 10 hours of labour to bring forth 100 gallons of latex and 15 hours of labour to bring forth 100 gallons of enamel. The company has 40 hours of labour available each hebdomad, without engaging outside aid or necessitating overtime. Furthermore, each pigment generates a net income at the rate of $ 1.00 per gallon. The company has the following aims listed in diminishing precedence:

avoid the usage of overtime

accomplish a hebdomadal net income of $ 1000

green goods at least 700 gallons of enamel pigment each hebdomad

Formulate the above job as a pre-emptive end scheduling job and work out it utilizing modified simplex method.

10. An electronics company produces two types of telecasting sets, colour and black-and-white.A The production of a colour set requires 10 hours of skilled and 100 hours of unskilled labor.A The production of a black-and-white set requires 5 hours of skilled and 150 hours of unskilled labor.A The company has 100 hours of skilled labour and 1,500 hours of unskilled labour usually available per month for the production of telecasting sets.A The maximal figure black-and-white and colour sets that can be sold each month are 45 and 70, respectively.A The net income border from the sale of a colour set is $ 20, whereas it is $ 15 from a black-and-white set.A The company has set the undermentioned ends:

1. Avoid the complete use of skilled labour since it is difficult to obtain in the labour market.

2. Minimize the under use of unskilled labour.

3. Meet the demand every bit much as possible.

4. Limit over use of unskilled labour to 100 hours.

Formulate the above as a leaden end scheduling job and work out utilizing modified simplex method.