> G ibjbjَ `]82,vl"$!^y
%uv%%%%%16J *>j CHAPTER 2
INTRODUCTION TO OPERATIONS RESEARCH
During World War II, British leaders ask scientists 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 (O.R) 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.
THE METHODOLOGY OF O.R
When Operations Research is used to solve a problem of an organization, the following seven step procedures should be followed:
[1] Formulate the problem
O.R analyst first defines the organizations problem. Defining the problem includes specifying the organizations objectives and the part of the organization that must be studied before the problem can be solved.
To illustrate the idea of problem formulation, suppose that a bank manager hires an Operations Research analyst to help the bank reduce the expenditures on tellers salaries while still maintaining an adequate level of customer service. After discussion with the manager of the bank, how might the analyst describe the banks objectives? Here are three possibilities:
The bank may want to minimize the weekly salary cost needed to ensure that the average time a customer waits in line is at most 3 minutes
The bank may want to minimize the weekly salary cost required to ensure that only 5% off all customers wait in the line more than 3 minutes for a teller.
The bank may be willing to spend up to RM 1000 per week on tellers salaries and minimize the average time a customer must wait in the line for a teller, given the salary constraint.
The analyst must also identify the aspects of the banks operations that effect the achievement of the bank objectives. For instance,
On the average, how many customers arrive at the bank each hour? The mo0re customers, the more tellers will be needed to provide adequate service.
On the average, how many customers can a teller serve per hour?
How does having customers waiting in a single line rather than in several tellers lines affect the achievement of the banks objectives?
If each teller has one line, will customers always join the shortest line? If one or another line becomes much longer, will customers jockey between lines?
[2] Observe the System
The analyst collects data to estimate the values of parameters that affect the organizations problem. These estimates are used to develop and evaluate a mathematical model of the organizations problem.
In our example, the analyst would collect data to estimate the following system parameters:
On the average, how many customers arrive each hour? Does the arrival rate of customers depend on the time of day?
On the average, how many customers can a teller serve in one hour? Does the speed with which a teller serves customers depend on the number of customers waiting in the line?
Do customers always join the shortest line? When at the end of a long line, do customers frequently switch to a shorter line?
[3] Formulate a Mathematical Model of the Problem
The analyst develops a mathematical of the problem. In our example, a mathematical model can be developed to predict the values of
Wq = Average time consumer waits in line
P = Probability that a customer will spend at least 3 minutes waiting in line based on knowing the following parameters:
( = Average no of customers arriving at the bank each hour
( = Average number of customers a teller can serve in an hour
s = Number of bank tellers
A mathematical model that yields an equation relating these four parameters to Wq, P would be an example of an analytic model. It can be shown that if there is only one teller, then under certain conditions
Wq = EMBED Equation.3 (1)
Thus, the knowing these parameters could use equation (1) to determine how well the system is controlling Wq. Many situations, however, are so complex that no analytic model exists. For example, if customer switch between lines, then in most situations there is no tractable mathematical equation that can be used to relate the four parameters to Wq or P. When no tractable analytic model exists, one must often develop a simulation model. Which enables the computer to approximate the behavior of the actual system.
[4] Verify the model and use it for Prediction
The analyst now tries to determine if the mathematical model developed in step [3] is an accurate representation of reality. To determine how the well the model fits reality, one determine how valid the model is for the current situation. For instance, in the bank example, suppose one believes the situation satisfies the conditions for which equation (1) is valid. Then current estimates of the parameters might be substitute into (1), and one would see how well (1) predict the observe values of Wq. If the model predictions of Wq and P are not close to the actual values, a new model is surly needed. In this case, one would return to either step [2] or [3] and develop a new model that better describes the actual situation.
[5] Select a suitable Alternative
Given a model and a set of alternatives, the analyst now choose the alternative that best meets the organizations objectives. In our bank example one might determine the employment policy that minimizes the weekly salary cost needed to ensure that the average customer waits in the line at most three minutes.
Sometimes the set not available alternatives is subject to certain restrictions or constraints. For example, suppose the bank can hire both fulltime tellers and parttime tellers. Assume that parttime tellers are less costly but work more slowly than fulltime tellers. One might want to minimize the average time a customer waits in line, subject to the following constraints:
At most RM 2000 per week can be sent on tellers salaries.
Parttime tellers can work at most one quarter of all hours worked each week.
In many situations, the best alternative may be possible or too costly to determine. For example a company considering purchasing a microcomputers might want to buy the one that best satisfies the following criteria:
Most economical computer
Ease of use
Most useful software available
Speed of operation
It is likely that no single computer will be the best with respect to all four criteria. Suppose three computers are under consideration. Computer A may be best with respect to criteria 1 and 3 and worst with respect to 2 and 4; computer B may be best with respect to criteria 2 and 4 but less good for the others; and computer C may be second best with respect to all criteria. Which computer would best meet the companys objectives? This is a difficult question that can be answered using the theory of Multiattribute decision making.
[6] Present the Results and Conclusions of the Study to the Organization
The analyst presents the model and recommendations from step [5] to the decisionmaking individual or group. In some situations, one might present several alternatives and let the organization choose the one that best meets its needs.
After presenting the result of OR study to the organization, the analyst may find that the organization doesnt approve the recommendations. This may result from incorrect definition of the organizations problems or from failure to involve the decisionmaker from the start of the project. In this case the analyst should return to step [1], [2], or [3].
[7] Implement and Evaluate Recommendations
If the organization has accepted the study, the analyst aids in implementing the recommendations. The system must constantly monitored to ensure that the recommendations are enabling the organization to meet the objectives. In the bank example, suppose the objective is to ensure at most 5% of customers wait for more than 3 minutes. Suppose that after the analysts suggestions are implemented, 80% of customers spend more than three minutes in the line. Then the banks objectives are clearly not being met, and the analyst should return to step [1], [2], or [3] and reexamine the model.
CHAPTER 2
LINEAR PROGRAMMING FORMULATION
Linear Programming (LP) is a tool for solving optimization problems. George Dantzig developed an efficient method, the simplex algorithm, for solving Linear Programming Problems. Some of the major application areas to which LP can be applied are:
1. Blending
2. Production planning
3. Oil refinery management
4. Distribution
5. Financial and economic planning
6. Manpower planning
7. Blast furnace burdening
8. Farm planning
DEFENITIONS:
MATHEMATICAL FORMULATION OF THE PROBLEM
PRODUCTION ALLOCATION PROBLEM
A manufacturer produces two types of models M1 and M2. Each M1 model requires 4 hours of grinding and 2 hours of polishing; whereas each M2 model requires 2 hours of grinding and 5 hours of polishing. The manufacturer has 2 grinders and 3 polishers. Each grinder works for 40 hours a week and each polisher works 60 hours a week. Profit on an M1 model is RM 3.00 and on M2 model is RM 4.00. Whatever is produce in a week is sold in the market. How should the manufacturer allocate his production capacity to the two types of models so that he may make the maximum profit in a week?
Let x1 be the number of M1 and M2 models that the manufacturer decided to produce per week. Then his weekly profit (in RM) is given by:
Z = 3x1 + 4x2
This is in the assumption that he has enough grinders and polishers capacity to produce these numbers of models.
Now, in order to produce these numbers of models, the total number of grinding hours needed per week is given by:
4x1 + 2x2
and the total number of polishing hours per week is given by:
2x1 + 5x2.
Since he does not have more than 80 hours of grinding and 180 hours of polishing, we must have:
4x1 + 2x2 ( 80
2x1 + 5x2 ( 180.
Also, it is not possible for the manufacturer to produce a negative number of models, it is obvious that we must also have
x1 ( 0 and x2 ( 0.
Hence the manufacturers allocation problem can be formulated as:
MEDIA SELECTION PROBLEM
The owner of metro sports wishes to determine how many advertisement to place in selected three monthly magazines A, B, and C. His objective is to advertise in such away that total exposure to principle buyers of expensive sports goods is maximized. Percentage of readers in each magazine is known. Exposure in any particular magazines is the number of advertisements placed multiplied by the number of principle buyers. The following data may be used:
Magazine A B CReaders100,00060,00040,000Principle buyers10%15%07%Cost per advertisement (RM)5,0004,5004,250
The budget amount is at most RM 100,000 for the advertisements. The owner has already decided that magazine A. should have no more than 6 advertisements and that B, and C each have at least 2 advertisements. Formulate an LP model for the problem.
Solution:
Let x1, x2, and x3 denote the desired number of insertions in magazines A, B, and C. Then the total exposure to principle buyers of the magazine is given by:
Z = 0.10 * 100,000 x1 + 0.15 * 60,000 x2 + 0.07 * 40,000 x3
The budging constraints is
5,000 x1 + 4,500 x2 + 4,250 x3 ( 100,000
and the advertisement constraints are
x1( 6, x2 ( 2, x3 ( 2.
Thus an LP model for Metro owners problem is :
Maximize
Z = 10,000 x1 + 9,000 x2 + 0.07 * 2,800 x3
Subject to the constraints
5,000 x1 + 4,500 x2 + 4,250 x3 ( 100,000
x1( 6, x2 ( 2, x3 ( 2.
x1, x2, x3 ( 0.
GRAPHIC SOLUTION METHOD
Let us return to the Production Allocation Problem. We obtained a mathematical formulation of the problem as follows:
Maximize
Z = 3x1 + 4x2
Subject to the constraints:
4x1 + 2x2 ( 80
2x1 + 5x2 ( 180.
x1, x2 ( 0.
A graphic solution of the problem:
X2
C
B
2x1 + 5x2 = 180
4x1 + 2x2 = 80
O A X1
Consider a set of rectangular Cartesian axes OX1X2 in the plane. Each point has coordinates of the type (x1,x2) and conversely every ordered pair (x1,x2) of real number determines a point in the plane.
It is clear that every point which satisfies the condition x1 ( 0 and x2 ( 0, lies in the first quadrant.
Similarly, since 4x1 + 2x2 ( 80 and 2x1 + 5x2 ( 180, the desired point (x1,x2) may be some where in the convex region OACB is bounded by the lines x2 = 0, x1 = 0, 4x1 + 2x2 = 80 and 2x1 + 5x2 = 180. This region is called the Solution Space for the given problem.
The four vertices of the convex region are:
O = (0,0), A = ( 20,0), B = (0,36), C = (2.5,35).
Will you be surprised if we tell you now that the solution to the manufacturers problem is:
x1 = 2.5, x2 = 35, and max Z = 147.5.
THE SIMPLEX ALGORITHM
The Simplex Method also called as Simplex Technique, or Simplex Algorithm is an alternative procedure for solving a linear programming problem in a finite number of steps.
For the solution of any LP problem by simplex algorithm, the existence of an initial basic feasible solution is always assumed. The steps for the computation of an optimum solution are as follows:
Step 1. Check whether the objective function of the given Lp problem is to be maximized or minimized. If it is to be minimized then we convert it into a problem of maximization using the result
Minimum Z =  Maximum (Z).
Step 2. Check whether all bi (i = 1,2,.,m) are nonnegative. If any of them is negative then multiply the corresponding inequation of the constraints by 1.
Step 3. Convert all the inequations of the constraints to equations by introducing slack and /or surplus variables in the constraints.
Step 4. Obtain an initial feasible solution to the problem in the form
XB = B1b
And put it in the first column of the simplex table.
C1C2C3CBYBXBY1Y2.YnCB1
CB2
:
CBmYB1
YB2
:
YBmXB1
XB2
:
XBmY11
Y21
:
Ym1Y12
Y22
:
Ym2.
.
.
.Y1n
Y2n
:
YmnZ0Z1 C1Z2 C2.Zn Cn
Step 5. Compute the net evaluations Zj Cj = CB Yj  Cj
If all (Zj Cj) ( 0 then the initial basic feasible solution XB is an optimum basic feasible solution.
If at least one (Zj Cj) ( 0 , proceed into the next step.
Step 6. If there are more than one negative Zj Cj , then choose the most negative of them. Let it be Zr  Cr for some j = r.
If all Yir ( 0, then there is unbounded solution to the given problem.
If at least one Yir ( 0, then the corresponding vector Yr enter the basis YB.
Step 7. Compute the ratios EMBED Equation.3 and chose the minimum of them. Let the minimum of these ratios be EMBED Equation.3 then the vector yk will level the basis yB. The common element ykr, which in the kth row and the rth column is known as the leading element (or pivotal element) of the table.
Step 8. Convert the leading element to unity by dividing its row by the leading element itself and all other elements in its column to zeroes by making use of the relations:
EMBED Equation.3 i = 1, 2, , m+1;i ( k
and EMBED Equation.3 j = 0,1, 2, , n.
Step 9. Go to step 5 and repeat the computational procedure until either optimum solution is obtained or there is indication of an unbounded solution.
SAMPLE PROBLEM
Use the simplex method to solve the following LP:
Maximize
Z = 7x1 + 5x2
Subject to the constraints
x1 + 2x2 ( 6
4x1 + 3x2 ( 12
x1,x2 ( 0.
Solution:
We observe that the given LP is that of maximizing the objective function subject to the given constraints in which the upper limits are nonnegative. The inequations of the constraints can be converted into equations by introducing slack variables x3 and x4.
x1 + 2x2 + x3 + 0 x4 = 6
4x1 + 3x2 + 0 x3 + x4 =12 (1)
then the new objective function is:
Z = 7x1 + 5x2 + 0.x3 + 0.x4
The set of equation (1) can be written as:
EMBED Equation.3 EMBED Equation.3 = EMBED Equation.3 ,Or AX = b
Clearly ((A) = 2 and since EMBED Equation.3 and EMBED Equation.3 are two linearly independent column vectors of A, we can take B = EMBED Equation.3 as anon singular basis submatrix of A. The basic variables are , therefore, x3 and x4 and an obvious basic feasible solution is
xB = B1b
= EMBED Equation.3 EMBED Equation.3 = EMBED Equation.3
i.e., xB = EMBED Equation.3 = EMBED Equation.3
corresponding to these basic variables, the matrix
Y = B1A
And the net evaluations zj cj = cB yj cj; are now computed, where cB is the matrix of costs corresponding to the basic variables in the objective function. Now, for this initial basic feasible solution
z = cB xB = 0
To see whether these exists some better basic feasible solution, we compute zjcj for the nonbasic variables x1 and x2 as follows:
Z1 c1 = cBy1 c1
= (0,0) EMBED Equation.3  7 = 7
z2 c2 = cBy2 c2
= (0,0) EMBED Equation.3  5 = 5
Thus the initial simplex table is
Table (1)
C = (7 5 0 0)
CB yBxBy1y2y3y4 0 y3x3 = 6 1 2 10 0 y4x4 = 12 4 3 01z = 075 00
Now, since more than one zj cj are negative, therefore we choose the most negative of these; 7, which lies in the column y1 will enter the basis yB.
To select the vector which should leave the basis yB, we compute EMBED Equation.3 EMBED Equation.3 and choose the minimum of these ratios, viz, 12/4 = 3. Thus the vector y4 leaves the basis. The leading common element is 4, which becomes the leading element for the next iteration. The leading element has been shown in the table in bold.
First Iteration:
Introduce y1 and drop y4 from yB. Convert the leading element to unity by dividing that row by 4 and all other elements of the column y1 to zero by using the relation given in Step 8. Compute again the net evaluation zjcj.
Table 2
C = (7 5 0 0)
CB yBxBy1y2y3y4 0 y3x3 = 3 0 5/4 11/4 7 y1x1 = 3 1 3/4 0 1/4 z = 21 01/4 07/4 It is apparent from the table that all new zjcj are nonnegative and hence an optimum solution has been reached. Thus an optimum basic feasible solution to the given LP is:
x1 = 3, x2 = 0; max z = 21.
ARTIFICIAL VARIABLE TECHNIQUES
There are many linear programming problems where slack variables cannot provide such a solution. To solve such problems, there are two methods:
Big MMethod
Twophase Method.
THE BIG MMETHOD
The Big MMethod or the method of penalties consists of the following steps:
Step 1. Express the linear programming problem in the standard form by introducing slack and /or surplus variables.
Step 2. Introduce nonnegative variable to the lefthand side of the constraints of (( or =) type. These variables are called artificial variables. The purpose of introducing these variables is just to obtain an initial basic feasible solution. However, addition of these artificial variables causes violation of the corresponding constraints. Therefore we would like to get rid of these variables. To achieve this, we assign a very large penalty M to these artificial variables in the objective function.
Step 3. Solve the modified LP by simplex method. At any iteration of the usual simplex method there can arise any one of the following three cases.
There is no vector corresponding to some artificial variable in the basis yB. We proceed to step 4.
There is at least one corresponding to some artificial variable in the basis yB at the zero level. The coefficient of M in each net evaluation zjcj in xB is zero. In such a case, the current basic feasible solution is a degenerate one. This is the case when an optimum solution to the given LP includes artificial variables and an optimum basic feasible solution.
At least one artificial vector is in the basis yB, but not at the zero level. The coefficient of M in each net evaluation zjcj is nonnegative, in this case, the given LP doesnt possess an optimum basic feasible solution, since M is involve in the objective function. In this case we say that the given problem has a Pseudo Optimum basic feasible solution.
Step 4. Application of simplex method is continue until either an optimum basic feasible solution is obtained or there is indication of unbounded solution.
SAMPLE PROBLEM
Use penalty method to
Maximize
Z = 3x1 + 2x2 + 3x3
Subject to the constraints
2x1 + x2 + x3 ( 2
3x1 + 4x2 + 2x3 ( 8
x1, x2, x3 ( 0.
Solution:
Let introduce the slack, surplus and artificial variables x4, x5, x6 ( 0
xB = [2 8]
Taking B = I2 as the basic submatrix.
Starting Table: The matrix yB = [y1, y2, , y6] and the evaluation zjcj, j = 1,2,,6 are computed by using the usual formula.
Table. 1
3 2 3 0 0 M
CB VBXBY1Y2Y3Y4Y5Y6 0 y422111 00 M y683420118M3M34M22M30M0
Table .2
3 2 3 0 0 M
CB VBXBY1Y2Y3Y4Y5Y6 2 y22 21 1 1 00 M y6050241145M+102M14M+2M0
Hence the coefficient of M in each zjcj is strictly nonnegative and one artificial vector appears in the basis yB at zero level. The optimum basic feasible solution is:
x1 = 0, x2 = 0, max. Z = 4.
TWOPHASE SIMPLEX METHOD
The twophase simplex method is an alternative method to solve a given LP in which some artificial variables are involved. In the first phase, the simplex method is applied to special constructed LP leading to a final simplex table that contains a basic feasible solution to the original problem.
Second phase, leads form the basic feasible solution determined by first phase to an optimum basic feasible solution if any, by application of simplex method.
SAMPLE PROBLEM
Use twophase simplex method to
Minimize
Z = 15/2 x1 3x2
Subject to the constraints
3x1 x2 x3 ( 3
x1 x2 + x3 ( 2
x1, x2, x3 ( 0.
Solution:
As usual, since the objective function is to be minimized, we convert it into that of maximization so that the problem becomes that of maximizing
Z* =  15/2 x1 + 3x2
Now by introducing surplus variable x4, x5 ( 0and artificial variables x6, x7 ( 0in the constraints of the given LP; an initial basic feasible solution to the problem is:
[x6, x7] = [ 3, 2] , with I2 as the basic matrix.
Phase 1. Assigning a cost 1 to the artificial variables x6 and x7 and cost 0 to all other variables, in the objective function.
Maximize
Z* = 0.x1 + 0.x2 + 0.x3 + 0.x4 0.x5 1.x6 1.x7
Starting table: After computing Y and the net evaluation zjcj, the initial simplex table is:
Table. 1
0000011CB YBXB Y1Y2Y3Y4Y5Y6Y71 y6331110101 y72111010154201100
First iteration: Introduce y1 and drop y6
Table. 2
0000011CB YBXB Y1Y2Y3Y4Y5Y6Y7 0 y1111/31/31/301/301 y7102/34/31/311/31102/34/31/314/30
Second iteration: Introduce y3 and drop y6.
Table. 3
0000011CB YBXB Y1Y2Y3Y4Y5Y6Y7 0 y15/411/201/41/41/41/4 0 y301/21 1/43/41/43/4 00000011
Now since all zjcj ( 0 and no artificial variable appears in the basis, therefore an optimum basic feasible solution has been attained. Therefore we proceed on to phase 2.
Phase 2. Here we consider the actual costs associated with the original variables. Then objective function, therefore is:
Z* =  15/2 x1 + 3x2 + 0.x3 + 0.x4 0.x5  ).x6.
We wish to maximize this new objective.
Starting table: Using the optimum simplex table of phase 1, the first simplex table of phase 2 is as follows:
15/23000CB YBXB Y1Y2Y3Y4Y515/2 y15/411/201/41/4 0 y33/401/21 1/43/475/80 3/4015/815/8
Since all zjcj ( 0, an optimum basic feasible solution has been attained. Hence an optimum basic feasible solution to the given LP is:
x1 = 5/4, x2 = 0, x3 = ; Min. Z = 75/8
PAGE
PAGE 1
A function f (x1, x2, , xn) is a Linear Function iff for some set of constants c1, c2, , cn, f(x1, x2, , xn) = c1x1 + c2x2 + + cnxn.
For any linear function f (x1, x2, , xn) and any number b, the inequalities f (x1, x2, , xn) ( b and f (x1, x2, , xn) ( b are Linear Inequalities.
A Linear Programming Problem (LP) is an optimization problem for which we do the following:
We attempt to maximize or minimize a linear function of the decision variables. The function that is to be maximized or minimized is called the Objective Function.
The values of the decision variables must satisfy a set of constraints. Each constraint must be a linear equation or linear inequality.
The Feasible Region for an LP is the set of all points satisfying all the LPs constraints and all the LPs sign restrictions.
For a maximization problem, an Optimal Solution to an LP is a point in the feasible region with the largest objective function value. Similarly, for a minimization problem, an optimal solution is a point in the feasible region with the smallest objective function value.
Find two real numbers, x1 and x2, such that
(i) 4x1 + 2x2 ( 80
2x1 + 5x2 ( 180.
x1, x2 ( 0.
And for which the expression (Objective function)
Z = 3x1 + 4x2
May be maximized.
=EF]
89"#[\_`stuv#5!""S$g$r$s$t$$%p&~&&&&&&&&&&&&jCJUmHj5CJUmH5CJ
56CJjCJEHUj=
CJUVmH
jCJU
jmCJ
jlCJCJH*5CJ>*
5>*CJCJB=>EF]^@ A e
$
&F
h$@&$=>EF]^@ A e
7w
SwolifGyz
vBC[\
U V
.
)*h
(7w
S67`b$h$
&F
h8$$
&F
h867`bVW}fg!"=>s !!wtqnk"qr
/ 0
X
FGijDEtu}rs F(VW}fg!"$
&F
h8$
&F
h8$$"=>s !!""S$T$U$V$W$X$Y$Z$[$\$]$^$_$`$a$b$c$$v$
$!""S$T$U$V$W$X$Y$Z$[$\$]$^$_$`$a$b$c$d$e$f$g$h$r$s$t$$$%%%%%%&7&X&o&p&}&~&&&}zwtq=X
!,c$d$e$f$g$h$r$s$t$$$%%%%%%&7&X&o&p&}&~&&&&&$$@$&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&2)3)))))?***~{xur
,&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&$&&&&&&'' '!')'*'v'w'D(E(_(`(8)9)L)M)S)T)))))****+++ +p+q+v+w+x+y+++++++,,,,,,,,,,g,h,r,s,t,,000000000000
1111#1$1%1&1Z1[1\1a1jCJUmH
jCJ
jCJCJH*CJ5CJ>*W&&&&&2)3)))))?*******++l+}+++,
,",#,$,$*****++l+}+++,
,",#,$,f,g,i,j,k,l,m,n,o,p,q,r,s,t,,,R.S.T.x.y.z......wsn
!"
Z[\]^_`abcdfg<=Pa*$,f,g,i,j,k,l,m,n,o,p,q,r,s,t,,,R.S.T.x.y.z...А%$$l4,"`$$$...............// /
/00x$$$lz,"'$$l4 z," $$............// /
/0000011/1V1W1p11111262H2I2a2b22222zwtqnkgpq
+,>WEpqisjkl
r
x
~
(000011/1V1W1p11111262H2I2a2b22222
333@3$$$$a1b1c1d1i1j1k1l111111111222222 2!2"2'2(2)2*2/202122292:2=2>2A2B2C2D2I2a2222233333333$3%3&3'3536393:3;3<3A3i3j3k3m3n3o33333333333333j5CJUmH
5CJH*5CJ>*
jCJ
jCJCJCJH*T2
333@3A3e3f3k3n3z33333333333446/6c66666677q8r849P9Q999x:y::::~{xur()pqwx=
`aFM <X,@3A3e3f3k3n3z33333333333446/6c66666677$$$333333333333324345464\4]4_4`444444444555555"5#5(5)5*5+5E5F5H5I5555555555555556/66666666q8r8y8Q9X9l9m999y::::::CJH*5>*
jCJ
jCJ
5CJH*5CJj5CJUmHCJCJH*R7q8r849P9Q999x:y::::;;;;
;;;;;;;`($$l4"gXI:+"$$$:;;;;
;;;;;;; ;#;(;+;,;0;4;6;:;>;B;D;H;L;P;R;V;Z;^;`;d;h;l;þ~ytohc^Y
":;;;; ;
;;;;;;;;;;;;; ;!;#;';(;);+;,;;/;1;3;7;:;;;=;?;A;E;H;I;K;M;O;S;V;W;Z;[;^;`;a;d;e;g;i;k;o;r;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;CJH*5CJ6
6CJH*6CJCJ\; ;#;(;+;,;0;4;6;:;>;B;D;H;L;P;R;V;Z;^;`;d;h;l;n;r;ۤ$$$lv gXI:+"$$l;n;r;w;;;;;;;;;;;;;;;;;;;W<<<==[==>>????@½wtqnkhe`%UV@
UV
456
=
B
I
P
S
TU
Y
[
_
c
h
m
r
w
{
}#r;w;;;;;;;;;;;;;;;f$$l`֞v gXI:+"$$$;;;;;W<<<==[==>>????@@@
$
&F
$
$
&F
$)$$l4$v gXI:+";;;<<.<0<i<j<n<o<q<r<<<<<<<<<===== =l=n=o=p=============>>1>2>3>4>F>G>^>_>u>w>>>>>>>>>>??
56CJCJH*jCJEHUjv_>
UVmHjCJEHUj_>
UVmH
jCJU
j>CJ
jCJ5CJ
j*5j6CJEHUj
b>
UVmHj6CJU
j6CJ6CJ
jCJUjCJEHUj`>
UVmHCJ@@@@@@@@AA,A@AJAKAOBPBrBBBBCCeCDDD)E\E]EhE6F7FGFFFFG*GUGwGGGGGG¿}xsn
]
`
~,`tu
U/0[y
4
^+@@@@@AA,A@AJAKAOBPBrBBBBCCeCDDD)E\E]EhE6F7F$BBBBBBBBBBBCC&C'C(C*C=C>C?C@CBCCCVCWCXCYCmCnCCCCCCCCCCCCCCCD D
DDZD[D¹zj^CJEHUjg>
UVmHjaCJEHUjg>
UVmHjbCJEHUjg>
UVmH
jrCJjbCJEHUj/g>
UVmHj
CJEHUjg>
UVmHj
CJEHUjf>
UVmH
jCJUCJH*CJ0[DaDbDDDDDDDDDDDDDDDDDDDDDDDDDE
EEEEE%E&E'E(EdEfEEEEEEEEEEEEE>F?FAFBFCFFFFFFFFFFѿѣjCJEHUjrCJEHUjh>
UVmHjrCJEHUjrCJEHUj/g>
UVmHjhCJEHUjg>
UVmH
jCJUCJH*CJH*CJ@7FGFFFFG*GUGwGGGGGGGGGGHHHHH!H"H$$lzJ$$$$FFFFFFFFFFFFGG G
GGGGG!G"G#G$G(G)G4G5GHGIGJGKGwGGGGGGGGGGGGGGGG
HHHH?H@HBHDHIHLHHHHHHHHH4I5IBICIVIWIjGw>
UVmH5CJj#CJEHUj_k>
UVmHj!CJEHUjj>
UVmH
jCJUCJCJH*GGGGGGHHHHH!H"HAHIHLHOHRHTHUHVH\H_HbHeHgHhHiHIaJbJsJSKTK\KKKK}zwtqkhc^
?
!
$
'
*
1
PQ
T
W
Z$"HAHIHLHOHRHTHUHVH\H_HbHeHgHhHiHIaJbJsJSKL$'$$l$zJ$$lzJ$$WIXIYIZI[InIoIpIqIIIbJsJ~JJJJJJJJMKNKPKQKTK\KKKKKKKKKKKKKKKKKKKLL!L#L'L(L}L~LLLMM
MMMMM=MMNNONPNWNNNOOCOXOYO
56CJ
jCJ>*5>*5CJCJH*j&CJEHUjxw>
UVmHCJ
jCJUj%CJEHUKSKTK\KKKKKKKKKKKKKKLL L'L*L/L2L7L8L9L`$$lzJ$$$KKKKKKKKKKKLL L'L*L/L2L7L8L9LALDLHLKLOLPLLMM=M>MMMMM~{xrolf^[1C
P
67U
"
%
*

4
RS
X
[
`
c
j
#9LALDLHLKLOLPLLMM=M>MMMMMMMNNONPN
$
&F
$'$$l$zJ$$MMMNNONPNNNPPXQYQQ*STT.U/U?U@UWUXUaUvUUUUUUU,V=V>VeVVVVW7W:W=W@WCWFWIWLWMWgWiWkWmWoWqWtWvWwWWWWWWWWWWWWWWWWW
3
,+,
/0HPNNNPPXQYQQ*STT.U/U?U@UWUXUaUvUUUUUUU,V=V>V$$
&F$YOPPQQRRMRNRPRQRVRWRZS[SSSSSgTiTwTTT0U@UXUaUhUiUnUoUtUuUUUUUUUUUUUUUUUUUUUUUUUUUUV V"V$V&V(V)V/V1V=V>VJVKVVVVVVVVVVVVVVVW jH* jH*5>*5
56CJ6CJCJH*5CJCJV>VeVVVVW7W:W=W@WCWFWIWLWMWgWiWkWmWoWqWtWvWwWWըՠ$$lh
V4,"$$$W"W#W5W7W8W:W;WW@WAWCWDWFWGWIWJWLWeWgWkWmWWWWWWWWXXXXXXXXXXX!X"X$X%X'X?XAXjXkXXXXXXXYYDYEYFYNYOYbY{YYD[E[S[U[v[[[[[[[[[[[[[[[[[[[[ jH*55>*>*
5CJH*5CJCJH*CJYWWWWWWWWWWWWWWWWWWWWx$)$$l(h
V4,"$$lh
V4,"$$WWWWWWXXXXX!X$X'X(XAXCXFXHXKXNXQXSXTXlXnXqXsXvXyXX~XXXXXXXXXXXXDYaYbY{YYZD[E[T[U[u[[[[[[[[[\\\K]]^
^>^^^^^^^^^^^^^^^^^^^^^^^^^^__
`WWXXXXX!X$X'X(XAXCXFXHXKXNXQXSXTXlXnXqXsXvXհլ$$lh
V,"$$$vXyXX~XXXXXXXXXXXXDYaYbY{YYd$)$$l(h
V,"$$lh
V,"$$YZD[E[T[U[u[[[[[[[[[\\\K]]^
^>^^^^^^^^$[[[[[[[[[[[[\\\\\\\\\\\\\\\K]M]P]S]T]U]i]j]]]]]]]^^^^!^"^(^)^/^0^5^6^<^=^x^y^{^^^^^^^^^^^^^^^^^^^^^^^^^^^_"_#_K_\_h_i_t_v_w______5H* jb^^^^^^^^^^^^^^^^^^^__ $$l ~ j:d^.,"+$$l4(j:d^.,"$__
_____$_&_(_+__/_2_4_6_7_8_;_>_@_B_D_F_H_J_K_L_v_w________________________________``
``````!`"`#`&`(`,`1`6`8`<`>`?`@`l`u`v`w`y`{`}```````````
b__
_____$_&_(_+__/_2_4_6_7_8_;_>_@_B_D_F_H_J_ۘP $$l ~ j:d^.,"$J_K_L_v_w________________+$$l4(j:d^.,"$*$$l* ~ j:d^.,"___________________````@`Q`]`^`i`j`l`v````````````````````````aCaDaFaGaHaIajbkbpbqbwbxb~bbbbbb8cKcLcNcOcRcScTcVcWcYcZc\c]c_c`cqcrccccccccc j5H*b_________________``
```ۼ"$$lL ~ j:d^.," $$l ~ j:d^.,"$````!`"`#`&`(`,`1`6`8`<`>`?`@`l`u`v`w`t*$$l* ~ j:d^.," $$l ~ j:d^.,"$w`y`{`}`````````````````` $$l ~ j:d^.,"+$$l4(j:d^.,"$````````````````aaa
aaaaaa a!a$a&a(a*a,a.a0a2a3a4aa[b\bbb%c&c'c(c.c0c2c4c6c7cNcRcUcXc[c^cacbcscwcyc~ccccccccccccccccccccccZddddddddd%e&e'e
``````````aaa
aaaaaa a!a$a&a(a*a,a.aL $$l ~ j:d^.,"$.a0a2a3a4aa[b\bbb%c&c'c(c.c0c2c4c6c7cNc$$l~ d^.*$$l* ~ j:d^.,"$NcRcUcXc[c^cacbcscwcyc~cccccccccccccccݤݬl$$l~ d^.$ccccccccZddddddddd%e&e'eeeee$h&`#$$$l~ d^.$cZd[d\dedfdmdndddddddddddddddddddddddddddddddddeee eeeeeeeee e!e"e#e$e%e'e?eCeDeGeHeNeOePetexeyee}eeeeeeeeeeeee
j6CJ5CJ
6CJH*6CJCJ0JmH0J
j0JU5H*5SeeeeeeeeeeffKgMgQg`gggghhhhhiiiiii!i"i'i(i)i*i1i2i5i6i7i8itiuizi}iiii
jCJ
jCJCJH*55CJCJ
j6CJ6CJ0'eeeeefffIgKgLgMgggghhhii0i
F$H<HAka> ۊcI2P/L֯K~z}Χ5'_Ź^ױ{4[`+(<·7Sľ8T7lo#_NóNPd&]$yL(/##toM;:zEU4eƗ5GI+W
9nh+̂]EH o!ja?!C3rpDdB
SA?2f,CsOdӈHBn`!:,CsOdӈH`@CPxQANAne7 h/0x6Ox GY+NUf*:ШJ6XQ$DV!vY场V`
M%<6$vc8B*#Mr%Ui7́z7 m<#振YpOH"_ds֟jAp eDwOѩW\S{e
)/}c{2ԶW$ޠ\,ki=2>DdB
SA?2p:4bKn`!p:4bKb`
JxJ@g&ib`YK=Y!`Դb
%Kk>7CY3
7lv~fP~ÇXDa3KQݿwDTP"DdB
SA?2܊T~lwdh n`!`܊T~lwd.xQN@} ?0E xh"E/jP&<ЕL,lH&8lw?>!0 +dH5dhdg軮Mu0 [5R {cvspu`*;
Y*nc_1wJZ{O@tϋLxPYމ7a _~NOa+FŌT?PO?dNUy㧦~Oab?Xg8UDY*Gy=o"K&DdB
,
SA?2[m9ul<n`!d[m9u:
2x]J@$m"PrV}=B@B[O9{sxhOғ
qwv&,ov?v`l@?Z!W$C\dZ%6Bp]E5l"Ċ_T$6u[`rR`.?<#xz^]n}UMЉnMY~UNߖӷW9
ϜLOg&Kͳy>CTc9.Zv
484:,tY]/8XWw`#;HF۩Ǩ
=msǓ4p1uOJDDdB

SA?2:A7gg%&b
n`!:A7gg%&@@ PVPxuJ@gfcB MKۓ*
hN
oCPA$= ^?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{}~Root EntryU F`<(> *>Data
l)WordDocumentTObjectPoolW ')> *>_1039911369F ')> ')>Ole
CompObjfObjInfo"%(+,/258;>ADGJMPSVY^abdefghiklmnopqs
FMicrosoft Equation 3.0DS EquationEquation.39q0mIyI
(")
FMicrosoft Equation 3.0DS EqEquation Native L_1040670472F ')> ')>Ole
CompObj
fuationEquation.39qޠmIyI
xBi
yir
,yir
*#0,i=1,2,...,m{}
FMicrosoft Equation 3.0DS EquationEquation.39qObjInfo
Equation Native
_1040670582F ')> ')>Ole
CompObjfObjInfoEquation Native \_1040670913 F ')> ')>@,I`oI
xBk
ykr
FMicrosoft Equation 3.0DS EquationEquation.39qވmIyI
Yij
=yOle
CompObjfObjInfoEquation Native ij
"ykj
ykr
yir
FMicrosoft Equation 3.0DS EquationEquation.39qXmIyI
Ykj
=ykj
ykr_1040671242F ')> ')>Ole
CompObjfObjInfoEquation Native t_10406724296F@*>@*>Ole
CompObj !f
FMicrosoft Equation 3.0DS EquationEquation.39qTmIyI
12104301()
FMicrosoft Equation 3.0DS EqObjInfo!#Equation Native $p_1040672518'$F@*>@*>Ole
&CompObj#%'fObjInfo&)Equation Native *_1040672559)F*>*>uationEquation.39qtI`oI
x1
x2
x3
x4
[]
FMicrosoft Equation 3.0DS EquationEquation.39qOle
CompObj(*.fObjInfo+0Equation Native 1P44ItI
612[]
FMicrosoft Equation 3.0DS EquationEquation.39q0mIyI
10_1040672667"1.F@*>@*>Ole
3CompObj/4fObjInfo06Equation Native 7L_10406726863F@*>@*>Ole
9CompObj24:f[]
FMicrosoft Equation 3.0DS EquationEquation.39q0IqI
01[]ObjInfo5<Equation Native =L_1040672762,@8F*>*>Ole
?CompObj79@fObjInfo:BEquation Native CX_1040673003=F*>*>
FMicrosoft Equation 3.0DS EquationEquation.39q<mIyI
1001()
FMicrosoft Equation 3.0DS EquationEquation.39qOle
ECompObj<>FfObjInfo?HEquation Native IhLmIyI
x3
x4
[]
FMicrosoft Equation 3.0DS EquationEquation.39q0mIyI
14_1040673534;JBF*>*>Ole
KCompObjACLfObjInfoDNEquation Native OL_1040673631GF*>*>Ole
QCompObjFHRf[]
FMicrosoft Equation 3.0DS EquationEquation.39q0I$}I
23[]ObjInfoITEquation Native UL_1040676679EOLF*>*>Ole
WCompObjKMXfObjInfoNZEquation Native [$_1040676728QF *> *>
FMicrosoft Equation 3.0DS EquationEquation.39qmIyI
FMicrosoft Equation 3.0DS EquationEquation.39qOle
\CompObjPR]fObjInfoS_Equation Native `ވtIuI
xBi
yi1
,yi1
*#0,i=1,2{}Oh+'0`
(
4@HPX
CHAPTER 2 HAPUnitelenitNormal.dotIT Faculty2 FMicrosofj̢:QFn`!>R.DdB
2
SA
?2i*a]0TMĄEn`!=*a]0TMĄɺhxcdd`` @bD"L1JE`xX,56~) M@ jpC0&dT20 `g11W&@\F\BsAJ~AJ,o(#ށWῆ_C,@wd++&1l q#e.;
lx7d6```CI)$5!k`uADdB
6
SA? 2g_#4&J<*Cn`!;_#4&J<*Ժh xcdd`` @bD"L1JE`xX,56~) M@ jpC0&dT20 `g11W&@\F\BsAJ~AJ,o(#ށWῆ_C,@wd++&18@]?]v2$C(o78lC}&#RpeqIj.C;l@
DdB
:
SA?
2t"M@4Nԙ[Pn`!H"M@4Nԙ[`\x]JA]Mr xX+4"D80K享}Tzel4 znagcŶvJ$⪪dңC[_;*kBlxe:[Tk:/oFm
EůI,F<̳%:5Ӧ9ϣU*+uN'r=X~:'qdSrBI.W]w03$:$Q
I\g)Ru~G~oV[zA0_,\I
DdB
;
SA?2t"M@4Nԙ[Pn`!H"M@4Nԙ[`\x]JA]Mr xX+4"D80K享}Tzel4 znagcŶvJ$⪪dңC[_;*kBlxe:[Tk:/oFm
EůI,F<̳%:5Ӧ9ϣU*+uN'r=X~:'qdSrBI.W]w03$:$Q
I\g)Ru~G~oV[zA0_,\IDdB
<
SA?2jR.R.DdB
=
SA?
2jR.R.DdB
A
SA
?2QA0?&_n`!WQA0?&@ `\%xuJ@gfWkӀA(P<*bU
Zߡ_BIA(Y&
$Yބ($d6qY2ۄnѬ.%a/yē86pee/ʊnW+Ep>wO}R~k}ZI&QQ~>"Uz<,XUG([k)
^tfo
Q;=WxR.DdB
F
SA?2gqp[zrK C!n`!;qp[zrK h xcdd`` @bD"L1JE`xX,56~) M@ jpC0&dT20 `g11W&@\F\B̋AJ~AJ,o(#ށWῆ_C,@wd++&18B]?]v$(o78lC}&#RpeqIj.C;@DdB
J
SA?2era5F5ltA#n`!9ra5F5lthx]AjPFA(W](e3x0n`9u6oT"U˲TnU39wO\ծFi!IeN$H4I2Η1pP瑋?
5i,F8ʓ&JA6d,
YU~ߕn,1%qoE2%"U;hc7uKn<O}@hDdTB
L
SA?28PN/7%n`!8PN/7 ȽXJtxcdd``a!0
ĜL 312Ec21BUs30)0)0Qcgb P#7T
obIFHeA*CTf0 PeDdlB
Q
SA ?22tԺ+`n4M/'n`!2tԺ+`n4MXh`\xJ@g&ۯ`
)*xR>L+>B/=Dc*zU۸_.RĄM
BGeWAr)"9+rD}e)dNGXH$Asȣk>@/hM[fp"WAV@y4%˩^ ;\#s]fO4ߠOWlǚCʧW
or_g>m[+1IyHlx\4J.M>No[rF9THZ,^HlwR"mx$=VEzWy~O\c6yPݶϰϹ@ƚ>
O՜.+,D՜.+,Lhp
Universiti Telekom Sdn Bhd.(a
CHAPTER 2Title 6>
_PID_GUIDAN{972BE30BE68D11D481FA00805FF740C9}
FMicrosoft Word Document
MSWordDocWord.Document.89q
[$@$NormalmH 4@4 Heading 1$@&5CJ8@8 Heading 2$$@&5CJ4@4 Heading 3$$@&CJ<@< Heading 4$@@&5CJ:@: Heading 5$$@&
5>*CJ<A@<Default Paragraph Font.B@. Body Text$CJ, @,Footer
!&)@&Page Number.P@".Body Text 2CJ<C@2<Body Text Indent $pDR@BDBody Text Indent 2 $ 5$3De$3De&a13:;?B[DFWIYOW[_cei7BILOTUXY[^dflqz{"c$&&$,.0@37;r;;@7F"HSK9LPN>VWWvXY^_J__`w``.aNccei8:<=?ACEFHKMPRSWZ]_acegijkmoprstvwxy}!&*.2:l;@GKMW_`'ei9;>@DGJNQV\`bhnu_su999:1:3:;;;;;;?&?(?)?=???B?V?X????????@
@@@@@@@@@@@AAA%A'ABC C4CHCJCBEVEXEZEnEpEe::::::::::::::::::::!!t8@,(
Z
SXX?
Z
SXX?
Z
SXX?
Z
SXX?
Z
SXX?
Z
SXX?
NB
SDNB
SDHB
CDHB
CDNB
SD
NB
SDNB
@
SD B
S ?~"""""g(k/l/n/////eH2x!tHox!tHx!OtHx!tHpx!tHG(#G
t
8
^t
xx tX( t(H ztxt(~(.t x(t
%&(7
9
Z\ 44k5m5o5p5(7*76797D7G7R7U7777799999999:4:5:9:::=:;;;;;;;;;;;;?A?W?Y?[?]????????@@@@@@@@@@@@A&A(A)A6AAAAAAAAAAAAA=B?BB
CCC
CC4CKCLCMCNCOCCCDDDDBEYEoEtEuE{EEEGGSSSS``````````a#ae
eee" , v w hi@
f#g#&&((/2Y[.!.8.:.4/6///3060F1I1>2D22222v5{5
77#7'7r7v7w7{7777777s8v8889a:;;;;==.=0=R>T>>>?d?H@M@@@@@@@)A6AAA9B:BBCCC*CTCCCEEIIQQQQRR.R0RRRRSSSDUFUWWWWXXOYQY^^Z`\`````````HaKa0e2eeeUnitele2C:\WINDOWS\TEMP\AutoRecovery save of CHAPTER 2.asdUniteleA:\CHAPTER 2.docUniteleA:\CHAPTER 2.docUnitele5C:\WINDOWS\DESKTOP\Operations Research1\CHAPTER 2.docUnitele5C:\WINDOWS\DESKTOP\Operations Research1\CHAPTER 2.docUnitele5C:\WINDOWS\DESKTOP\Operations Research1\CHAPTER 2.docUnitele5C:\WINDOWS\DESKTOP\Operations Research1\CHAPTER 2.docUnitele5C:\WINDOWS\DESKTOP\Operations Research1\CHAPTER 2.doc
IT FacultyC:\My Documents\CHAPTER 2.doc
IT Faculty+C:\My Documents\Chapter2.Simplex Method.doc6oE"~P+m3ԋ2x3 <; G~RNXVQ SVvS]DY{^о\hho(.hho(.0o(.hh5o(.0o(.hho(.hho(.0o(.0o(.0o(()hho(.2x3VvS]VQ<;P+m3 SGE"6oRNY{^@XteP@GTimes New Roman5Symbol3&Arial"1h
W
W
O(!0a CHAPTER 2Unitele
IT Faculty