98. In a linear programming problem, if a constraint is inactive, then the unit worth of resource corresponding to that constraint is
Zero
A high value
Negative
undefined
Here is releated study material -
Introduction:- This type of optimization techniques are applicable to constrained problems of type- Minimize f(x), subject to g_{j} (x) <=0; j =1,2,….m h_{k}(x) =0; k =1,2,….p and
In the above type of problem, the function f(x), g_{j}(x) and h_{k}(x) are not necessarily linear, they may be Non-Linear. So it is not possible every time that we use the methods of LPP to solve the above problems. These methods are iterative methods and can be categorized in to two parts namely---
Direct Methods :- In these method the constraints will be handled in a explicit manner. Some of the direct methods are:- 1. Random Search Method 2. Heuristic Search Method 3. Complex Method 4. Objective and Constraint Approximate Method 5. Sequential Linear Programming Method 6. Sequential Quadratic Programming Method 7. Method of Feasible Directions 8. Generalized Reduced Gradient Methods Complex Method Mathematician Box has extended the simplex method for unconstrained optimization of type Minimize f(x) ------- (1) Subject to g_{j} <= 0; j=1,2,….,m ------(2) x_{i}^{(l)}<=x_{i}<=x_{i}^{(u)}; i=1,2,……,n ------- (3) where x_{i}^{(l)} = Lower bound of x_{i} x_{i}^{(l)} = upper bound of x_{i} This method can’t handle the Non-Linear equality constraints. As the basic idea in the simplex method was forming a sequence of geometrical figures, each having (n+1) vertices in an n-dimensional problem, In this method also, a sequence of geometric figures, each having k>=n+1 vertices being formed to find the constrained optimum point. Working Procedure:- Step-1 Find k>=n+1 point, each of which satisfies all ‘m’ constraints. We start with only one feasible point x_{1} and remaining (k-1) points are found one at a time, by using random numbers, generated between 0 and 1.as- x_{i,j} = x_{i}^{(l)} + r_{i,j}[x_{i}^{(u)} - x_{i}^{(l)}] ---- (4) i=1,2,….,n j = 1,2,….,k x_{i,j}-> i^{th} component of x_{j} r_{i,j} -> random number lying between 0 and 1 It is noted that points x_{2} , x_{3} ,------x_{k} are generated according to equation (4), satisfies the side constraints (3) but may not satisfy constraints(2). When the new point xj is found, find it satisfies (2), or not If x_{j} does not satisfies (2) then the trial point x_{j} is moved half way towards the centroid of remaining already accepted points. x_{1}, x_{2},-----x_{j-1}
If again this point x_{j} does not satisfy (2) then the process of moving half way towards the centroid x_{0} is continued until a feasible point x_{j} is found. Ultimately we find a feasible point x_{j} Example If the trial point x_{j}, violates any one of constraints of (2), then the new point x_{j}=x'_{j} is found as X'_{j} = (X _{0} + X_{j})/2 => a new point X'_{j} is halfway towards X_{0} If x’_{j} satisfies (2) then it is accepted to be the j^{th} vertex of the complex. If x_{j}’ violates any one constraints of (2) then new x_{j} = x_{j}^{2} can be found as X_{j}^{2} = (X_{0} + X_{j}')/2 The process of moving halfway towards the centroid x_{0} continued until a feasible point x_{j} is obtained Step2….Evaluate f(x) at each of the k points. If the vertex x_{n} is given largest value of the function, then the process of reflection is used to find a new point x_{r} as:- X_{r} = (1+ a)X_{n} - aX_{0} where a>=1(initially) and X_{0} is the centroid of all objects except X_{n} i.e.
Step3... Now check the feasibility of the point x_{r}. (a) If x_{r} is feasible and f(x_{r}) < f(x_{n}) then x_{n}is replaced by x_{r} and we move on to Step2. (b) If f(x_{r}) >=f (x_{n}), a new trial point x_{n} is found by reducing the value of x in (6). by a factor of 2.(i.e. new a = olda/2 ) and now tested for the satisfaction of f(x_{r})n). This process is continued until we have a x_{r} such that for which f(x_{r}) < f(x_{n}) and value of a become smaller then a small value E=10^{-6} (say) (c) If the point x_{r} is not obtained in any case such that f(x_{r}) < f(x_{n})then we discard the whole reflection process and start the new reflection process by taping x_{n}, which gives second largest value of function. Step4... If at any stage the point x_{r}, does not satisfy (2), then it is moved halfway towards the centroid unit it becomes feasible i.e. new X_{r} = (X_{0} + X_{r})/2 Step5... Each time the worst point xn of current complex is replaced by a new point x, so the complex get modified Convergence:- Now we will check the convergence of the process. This is said to be converged if the following will be satisfied a) The distance between any two vertices among x1, x2, …. Xk become smaller than a prescribed small value E1 b) The standard Deviation of the function values become sufficiently smaller i.e.
_{Where x is the centroid of all k vertices of the current complex and E2>0 is a specified small number. Important features: 1) As the derivatives of f(x) and gj(x) are not necessary, so computation are simple 2) Box was found the initial value of a = 1.3 satisfactory and also recoment k = 2n for n<=5, a lesser value of k can be taken for n>5. If k is not sufficiently large then complex collapse and flatten along the first encountered constrained boundary 3) Unless some boundary surface is encountered, the complex roles over and over again with expansion. 4) If the feasible reason is non convex, then there is no guarantee that the centroid of all feasible solutions is also feasible. If the centroid is not feasible, we can’t apply the above procedure to find the new point Xr> 5) If number of variables increases the efficiency of the method decreases 6) Method is not applicable for equality constraints Example 1: Minimize f(x) = (x1-1) 2 + (x2 – 1.5) 2 – 0.25 Subject to x1 + x2<=4 1<=x2<=3 0<=x1<=2 by complex method with x1 =}
_{ Sol: The problem is of two dimensions so the complex is considered to have k = 2n = 4 vertices. One of its vertices is}
_{ and other three vertices are chosen with the help of random numbers distributed between 0 and 1. Let the chosen numbers are r1,2 = 0.4, r1,3 = 0.6, r1,4 = 0.8 r2,2 = 0.5, r2,3= 0.7, r2,4 = 0.9 The six co-ordinates of these three vertices corresponding to k = 2,3 4 are computed by – Xi,j= xi (l) + ri,j [xi(u) – xi (l)] ; i = 1,2 j = 1,2,3,4 Here x1(l) = 0, x1(u) = 2 And x2(l) = 0, x2(u) = 2 So x1,2 = x1(l) + r1,2[x1(u) - x1(l)] = 0.8 x1,3 = x1(l) + r1,3[x1(u) - x1(l)] = 1.2 x1,4 = x1(l) + r1,4[x1(u) - x1(l)] = 1.6 x2,2 = x2(l) + r2,2[x2(u) - x2(l)] = 2 x2,3 = x2(l) + r2,3[x2(u) - x2(l)] = 2.4 x2,4 = x2(l) + r2,4[x2(u) - x2(l)] = 2.8 Thus the initial complex consists of the vertices}
_{Because g(x) = x 1 + x2 <= 4 g(x 1) = 1.8 <= 4 g(x 2) = 2.8 <= 4 g(x 3) = 3.6 <= 4 g(x 2) = 4.4 > 4 because g(x) is not satisfied at x4 so it is replaced by a point which lying in the feasible region. Because the centroid x 0 = (x 1 + x 2 + x 3)/3 =}
_{ Hence new x 4 = x 4 (l) = (x 0 + x 4)/2 =}
_{and g(x 4 (l)) = 3.565 <= 4 so x 4 (l) lies in the feasible region. So taking x 4 = x 4 (l) as a vertex. So the initial complex has the points x 1 , x 2, x 3 and x 4 = x 1 1. Now because f(x 1) = 0 F(x 2) = 0.04 F(x 3) 0.60 And f(x 41) = 0.476725 Because f(x 3) gives maximum value and f(x 1) gives minimum value so let us take x n = x 3 and f(x n) 0.60 and x l = x 1 and f(x l) = 0 The centroid x 0 is obtained as - x 0 (x 1 + x 2 + x 41)/3 =}
_{ and f(x 0) = -0.15 Because f(x 0) < f(x n), which means that f(x ) is decreasing on the line x 3x 0. So let us find the point x r by reflection process as x r = (1+ a)x 0 - ax n Taking a = 1, so x r = 2x 0 - x n =}
_{ And f(x r) = -0.031944 As f(x r) is such that the x r is feasible and f(x r)< f(x n), so let us replace the point x n= x 3 by x r and hence two cases Case I – Let a = 0.1 then xr1 = 1.1x0 - 0.1xn Therefore xr1 =}
_{=}
_{ F(xr(1)) = - 0.17734206 Case II: Let a = 0.2 then- xr(2) = 1.2 x0 - 0.2 xn =}
_{And f(xr(2)) = -0.19591584 Similarly, Case III, a = 0.3 then f(xr(3)) = -0.20580734 Case IV, a = 0.4 then f(xr(4)) = -0.20701656 Case V, a = 0.5 then f(xr(5)) = -0.1995435 Method of feasible directions In the method of feasible direction basically we will choose a starting point, satisfying all the constraints and move to a better point according to iterative scheme x i+1 = x i + lS i ----(1) where: x i = standing point for i th iteration S i = direction of movement l = step length of the movement xi+1 = Final point at the end of ith iteration The value of l is always chosen such that xi+1 lies in feasible region. The search direction Si a) A small move in that direction violates no constraints b) The value of the objective function can be reduced in that direction As the decreasing trend by values of f continues upto x r (4) so let us replace the vertex x n = x 3 by x r (4). So the new complex will have vertices as- x 1 =}
_{ And f(x 1) = 0 x 2 =}
_{and f(x 2) = 0.04 x 3 = x r (4) =}
_{and f(x 3) = -0.207016 x 4 =}
_{and f(x 4) = 0.476725 vBecause f(x4) gives maximum value and f(x3) gives minimum value so let us take- xn = x4=}
_{and f(x 4) = 0.476725 xl = x3=}
_{and f(x l) = -0.20701656 Therefore centroid x 0 = (x 1 + x 2 + x 3)/3 =}
_{and f(x 0) = -0.19303 Because | f(x l) = f(x 0)| = 0.014 If the desired accuracy is above e = 0.01, then the above solution is accepted. The point x i+1 can be taken as the starting point for (i+1) th iteration and the entire procedure is repeated until a point is obtained such that no direction can be formed which satisfy both properties (a) and (b). A direction satisfying (a) only is called feasible direction, while a direction satisfying both (a) and (b) is called and usable feasible direction. This is the reason that these methods are known as methods of feasible directions. There are many ways of choosing usable feasible directions and hence there are a number of methods of feasible directions. i) A direction S is feasible at a point x i if it satisfies the relation- {d/d l[g j(x i + lS)]} l=0 = STÑgj(xi) <= 0 --------- (2) Where the equality sign holds true only if a constraint is linear or strictly concave }
question-answer-faq-2748