Linear Programming - Coursework Example

Linear programming 1. A The variables in a linear program are a set of quantities that need to be determined in order to solve the problem; i.e., the problem is solved when the best values of the variables have been identified. The variables are sometimes called decision variables because the problem is to decide what value each variable should take. Typically, the variables represent the amount of a resource to use or the level of some activity. 1. B Linear programming is a response to situations that require the maximization or minimization of certain functions which are subject to limitations. These limitations are called constraints. A decision variable is a quantity that the decision-maker controls. Essentially, linear programming is to optimize (maximize or minimize) an objective function (a linear function of several variables): In this case we take W to represent the number of 1000 batches produced of valley White and R to represent the number of 1000 batches produced of valley Red the our objective function is; Maximize Z (profit) = 12,000W+9,000R 1. C Since resources are scarce there are limitations on what can be achieved for example if materials and machine time are in short supply. Output therefore will be limited by the availability of these resources. In this case our limiting resources are: Storage space and processing time 4W + 8R ≤ 64 materials (grape tons) 5W +5R ≤ 50 cubic yards (storage space) 15W +8 R≤ 125 hours (processing time) 1 ≤ W, R ≤ 7 12,000W+9,000R ≤ $54,000 2. It is a Constrained Optimization Problems arise from applications in which there are explicit constraints on the variables. The constraints on the variables can vary widely from simple bounds to systems of equalities and inequalities that model complex relationships among the variables. Constrained optimization problems can be furthered classified according to the nature of the constraints for example it can either be a linear, or nonlinear problem. 3. Graphical solution of the model: The graph is in the first quadrant (W > 1, R >1) by virtue of the non-negativity constraints. The horizontal axis is assigned for W and R is assigned to the vertical axis; a coordinate is the ordered pair (W, R). Coordinate axis intercepts of the constraints: Line 1 constraint boundary: 4W + 8R = 64 When W = 0, R = 8; = (0, 8) When R = 0, W = 16; = (16, 0) Line 2 constraint boundary: 5W +5R = 50 When W = 0, R = 10; = (0, 10) When R = 0, W = 10; = (10, 0) Line 3 constraint boundary: 15W +8 R= 125 When W = 0, R = 15.6; = (0, 15.6) When R = 0, W = 8.3; = (8.3, 0) Graph all of the constraints Objective function: Z (profit) = 12,000W+9,000R B The feasible region is the unshaded region this is where the production is at optimum. C. R=7 5W +5R = 50 5W + 35 =50 W= 3 12,000(3) +9,000(7) =99,000 R = 7 15W +8 R= 125 15W + 56 =125 W = 4.6 12000(4.6) +9,000(7) = 118,200 4W + 8R = 64 15W +8 R= 125 9W = 61 W= 6.78, R = 4.6 12,000(6.78) + 9,000(4.6) = 122,760 W= 7 4W + 8R = 64 R= 4.5 12,000(7) +9,000(4.5) = 124,500 E. At point A the revenue realized is at maximum thus is the best point of production the profit generated is at maximum. All the constraints are within range at this point thus it is the corner containing the optimal solution. 4. Optimal solution and the optimal value R=7 5W +5R = 50 5W + 35 =50 W= 3 12,000(3) +9,000(7) =99,000 R = 7 15W +8 R= 125 15W + 56 =125 W = 4.6 12000(4.6) +9,000(7) = 118,200 4W + 8R = 64 15W +8 R= 125 9W = 61 W= 6.78, R = 4.6 12,000(6.78) + 9,000(4.6) = 122,760 W= 7 4W + 8R = 64 R= 4.5 12,000(7) +9,000(4.5) = 124,500 Optimal solution is (7, 4.5) with the optimal value of 124,500 5. An optimum point of production is the point where the units produced will yield the maximum profit within the limitations by the constraint. In this case at point A the total profit that can be realized is $124,500 this is the highest possible profit. To produce these profits we require 7 batches of valley wine White and 4.5 batches of valley wine Red. This means a total of 7,000 white wines and 4,500 Red wines. 6. The corner point evaluation method is used to determine the corner that would generate the most profits or maximize the objective function. In this method we take the all the corners coordinates and plug them in the objective and determine it which corner will maximize profit. D. R=7 5W +5R = 50 5W + 35 =50 W= 3 12,000(3) +9,000(7) =99,000 C. R = 7 15W +8 R= 125 15W + 56 =125 W = 4.6 12000(4.6) +9,000(7) = 118,200 B. 4W + 8R = 64 15W +8 R= 125 9W = 61 W= 6.78, R = 4.6 12,000(6.78) + 9,000(4.6) = 122,760 A. W= 7 4W + 8R = 64 R= 4.5 12,000(7) +9,000(4.5) = 124,500 6. B, The optimal solution in the case above is at point A this is because at point A the number of units produced yield the maximum returns to the organisation and optimal value to this problem is $124,500. Both the results in parts 4 and 6b are similar as it is at point A that profit is maximized. Both the formulas are used to calculate the maximization point of returns thus give a similar outcome. 7. A slack variable is a variable added to an equality constraint to transform the equality to equality. In linear programming it is used to transform the inequality where the linear combination is less than or equal to a given constraint in the former. If the slack variable is positive in a given state, the constraint is non-binding as it does not restrict the possible changes of the point. 4W + 8R = 64 /4 =16 15W + 56 =125/15 = 8 5W +5R = 50/5= 10 This means that we would end up using all the available processing time before we exhaust all the storage space and materials. We therefore have slack variables of both materials and storage space of 7 and 2 respectively. 8. Redundant constraints are those that do not affect the attainment of the maximum possible profit. In this case the redundant variable is the breakeven profits which will not affect the realization of any extra profits. 9. The optimal solution is not changed with change in the break even analysis. This is because breakeven profit is a redundant constraint. Thus not affecting the profitability level of the organisation, this is because all the possible production combination gives a much higher profit than $64,000. 10. The computer results and those done manually are similar as they all give the maximization corner that will yield the highest profit. All the formulas therefore can be used to solve for the best production point. 11. The best production combination is at 7 batches of white wine and 4.5 batches of Red wine. At this point the company will realize a total profit of $124,500. 12000 (7) + 9000 (4.5) = 124500 84,000+ 40,500 =124500 12. The ranges of feasibility are all possible production points that will realize a profit of more than $64,000. In this case all the corners are therefore feasible points of production. 13. For minimization problems, of a feasible solution to the original problem provides an upper bound for the associated problem referred to as the dual problem. Reference Dmitris Alevras and Manfred W. Padberg, Linear Optimization and Extensions: Problems and Solutions, University text, Springer-Verlag, 2001. (Problems from Padberg with solutions) Read More