
LP Problem Formulation Process and Its Applications To formulate an LP problem, I recommend using the following guidelines after reading the problem statement carefully a few times. Any linear program consists of four parts: a set of decision variables, the parameters, the objective function, and a set of constraints. In formulating a given decision problem in mathematical form, you should practice understanding the problem (i.e., formulating a mental model) by carefully reading and re-reading the problem statement. While trying to understand the problem, ask yourself the following general questions: 1. What are the decision variables? That is, what are controllable inputs? Define the decision variables precisely, using descriptive names. Remember that the controllable inputs are also known as controllable activities, decision variables, and decision activities. 2. What are the parameters? That is, what are the uncontrollable inputs? These are usually the given constant numerical values. Define the parameters precisely, using descriptive names. 3. What is the objective? What is the objective function? Also, what does the owner of the problem want? How the objective is related to his decision variables? Is it a maximization or minimization problem? The objective represents the goal of the decision-maker. 4. What are the constraints? That is, what requirements must be met? Should I use inequality or equality type of constraint? What are the connections among variables? Write them out in words before putting them in mathematical form. Learn that the feasible region has nothing or little to do with the objective function (min or max). These two parts in any LP formulation come mostly from two distinct and different sources. The objective function is set up to fulfill the decision-maker’s desire (objective), whereas the constraints which shape the feasible region usually comes from the decision-maker’s environment putting some restrictions/conditions on achieving his/her objective. The following is a very simple illustrative problem. However, the way we approach the problem is the same for a wide variety of decision-making problems, and the size and complexity may differ. The first example is a product-mix problem.
Graphical Solution Method Procedure for Graphical Method of Solving LP Problems: 1. Is the problem an LP? Yes, if and only if: All variables have power of 1, and they are added or subtracted (not divided or multiplied). The constraint must be of the following forms ( ?, ?, or =, that is, the LP-constraints are always closed), and the objective must be either maximization or minimization. For example, the following problem is not an LP: Max X, subject to X ? 1. This very simple problem has no solution. 2. Can I use the graphical method? Yes, if the number of decision variables is either 1 or 2. 3. Use Graph Paper. Graph each constraint one by one, by pretending that they are equalities (pretend all ? and ?, are = ) and then plot the line. Graph the straight line on a system of coordinates on a graph paper. A system of coordinate has two axes: a horizontal axis called the x-axis (abscissa), and a vertical axis, called the y-axis (ordinate). The axes are numbered, usually from zero to the largest value expected for each variable. 4. As each line is created, divide the region into 3 parts with respect to each line. To identify the feasible region for this particular constraint, pick a point in either side of the line and plug its coordinates into the constraint. If it satisfies the condition, this side is feasible; otherwise the other side is feasible. For equality constraints, only the points on the line are feasible.5. Throw away the sides that are not feasible. After all the constraints are graphed, you should have a non-empty (convex) feasible region, unless the problem is infeasible. 6. Create (at least) two iso-value lines from the objective function, by setting the objective function to any two distinct numbers. Graph the resulting lines. By moving these lines parallel, you will find the optimal corner (extreme point), if it does exist. In general, if the feasible region is within the first quadrant of the coordinate system (i.e., if X1 and X2 ? 0), then, for the maximization problems you are moving the iso-value objective function parallel to itself far away from the origin point (0, 0), while having at least a common point with the feasible region. However, for minimization problems the opposite is true, that is, you are moving the iso-value objective parallel to itself closer to the origin point, while having at least a common point with the feasible region. The common point provides the optimal solution.
Classification of the Feasible Points: : The feasible points of any non-empty LP feasible region can be classified as, interiors, boundaries, or vertices. As shown in the following figure: The point B in the above two-dimensional figure, for example, is a boundary point of the feasible set because every small circle centered at the point B, however small, contains both points some in the set and some points outside the set. The point I is an interior point because the orange circle and all smaller circles, as well as some larger ones; contains exclusively points in the set. The collection of boundary points belonging to one set is called boundary line (segment), e.g. the line segment cd. The intersections of boundary lines (segments) are called the vertices, if feasible it is called the corner point. In three-dimensional space and higher the circles become spheres, and hyper-spheres. Know that, the LP constraints provide the vertices and the corner-points. A vertex is the intersection of 2-lines, or in general n-hyperplanes in LP problems with n-decision variables. A corner-point is a vertex that is also feasible.
|
No comments:
Post a Comment