|
|
NExS Linear Programming Plug-In Manual
ContentsIntroductionThe lp plug-in lets you solve linear-programming problems using the NExS spreadsheet. lp adds two new functions to your spreadsheet: @CONSTRAINT for specifying linear constraints, and @LP for specifying the locations of your adjustable variables, the objective function you are trying to minimize or maximize, and the constraints. An Example: Feeding the DogThe use of lp is best shown by example. Suppose your dog, Ralphy, has a nutritional deficiency. You want to find the cheapest combination of four different dog foods (brands W, X, Y, and Z) that will give him at least the minimum daily requirement of vitamins A, D, E, and K. But you also want to make sure he doesn't get fat from eating too much food. The spreadsheet for this problem is in dog.xs3. You can view the spreadsheet
using the command nexs &. Once the spreadsheet is active, you must go under
the Connections menu and allow NExS to Accept Connections. Then you must
issue the command lp & to start the linear-programming plug-in which will
connect itself to your NExS spreadsheet. Finally, use the File Within the spreadsheet, the nutritional value of each dog food is given in the range of cells (B5..E8). For example, a pound of dog food W contains 2.2 grams of vitamin A, 1.4 grams of vitamin D, 2.3 grams of vitamin E, and 12.0 grams of vitamin K. (I'm no nutritionist. I suspect doses like these would kill almost anything!) The minimum amount of each vitamin that Ralphy needs is listed in the column of cells (F5..F8). The calories in each pound of dog food are listed in cells (B9..E9) and the number of calories Ralphy should get each day is stored in cell F9. The cost per pound of each type of dog food is stored in the row of cells (B10..E10). You must find the amount of each type of dog food you need to buy to satisfy Ralph's vitamin and caloric requirements while minimizing the cost. Assume these amounts are stored in cells (B11..E11). The cost of a particular mix of dog foods is calculated in cell B13 as @DOT(B11..E11,B10..E10). This is just the sum of the products for the weight of each type of dog food that will be purchased multiplied by the cost of each pound of dog food. The weights are subject to certain constraints. First of all, you have to purchase the
right amount of food to give Ralphy exactly the right number of calories each
day. This constraint is recorded in cell G9 as @CONSTRAINT(@DOT(B9..E9,B11..E11),``='',F9,``''). The first argument to the @CONSTRAINT function calculates the left-hand side
(LHS) of the constraint. The third argument calculates the right-hand side (RHS) of the
constraint. The second argument is a string that specifies the type of constraint. In this
case, it is an equality constraint. Thus, B9*B11+C9*C11+D9*D11+E9*E11 must sum to the number of calories stored in cell F9. The constraints on the nutritional value for any combination of dog foods are stored in
cells (G5..G8). For example, the constraint in cell G5 is @CONSTRAINT(@DOT(B$11..E$11,B5..E5),``>='',F5,``'') which means the sum of the amounts of each dog food multiplied by the amount of vitamin A in each food must be greater than or equal to Ralphy's minimum requirement for vitamin A. Now that the problem has been set up, you can use the @LP function to solve it. The function is stored in cell B14 as @LP(``MIN'',B13,B11..E11,G5..G11). The first argument specifies whether you want to minimize or maximize your objective function. The second argument lists the cell where the function you want to optimize can be found. The range where the adjustable variables are found is in argument three. The final argument gives the range in which the problem's constraint functions are stored. When the dog.xs3 sheet was opened, you probably saw that there was already a solution calculated by the @LP function. This solution uses 0.8 pounds of dog food W and 0.3 pounds of dog food Y, and none of dog foods X and Z to supply all of Ralphy's vitamin needs. We can check that by observing the results returned by the @CONSTRAINT\ functions in cells (G5..G8): they all show either >= (indicating the amount of a particular vitamin provided by this diet exceeds the minimum requirement) or =>= (meaning the amount of a particular vitamin exactly equals the minimum requirement). Also, the @CONSTRAINT function shows == in cell G9 meaning the proposed diet gives Ralphy exactly 1600 calories a day. Finally, the @LP function returns a 0, meaning it has found an optimal solution. The minimized cost of this optimal solution is listed in cell B13\ as $3.87/day. If you change any of the problem's parameters, the @LP function will recalculate the amounts of each dog food in the mix and come up with a new optimum solution. For instance, if you changed the price of dog food Z from $6 to $2 (maybe you got a coupon!), then the best mix of foods is 0 pounds of W, 0.3 pounds of X, 0.2 pounds of Y, and 0.4 pounds of Z with a total cost of $3.34/day. When you changed the price in cell E10, you saw the values in the spreadsheet
changing for several seconds as the new solution was calculated. If you want to change
several parameters and don't want the solution recalculated each time one is changed, then
select Manual recalculation under the Options Linear Programming Function DescriptionHere are detailed descriptions of what each new function does. @CONSTRAINTSyntax: @CONSTRAINT(LHS,OP,RHS,S) LHS = any valid NExS cell expression that results in a numeric result. OP = any of the strings ``='', ``=='', ``<='', ``=<'', ``>='', or ``=>''. RHS = any valid NExS cell expression that results in a numeric result. S = ``SLACK'' causes the @CONSTRAINT function to return the amount of slack in the constraint. If the value returned is positive or zero, then the constraint is satisfied. If the value is negative, then the constraint is not satisfied. S = ``'' causes the @CONSTRAINT to return a string indicating whether the constraint is satisfied or not. If the constraint operator is ``='', then the string ``=='' is returned if the equality is satisfied, and ``!='' if not. If the constraint operator is ``>='', then the string ``>='' is returned if the inequality is more than satisfied (i.e., slack is positive), the string ``=>='' is returned if the inequality is exactly satisfied (i.e., slack is zero) and ``!>='' if the constraint is not satisfied (i.e., slack is negative). If the constraint operator is ``<='', then the string ``<='' is returned if the inequality is more than satisfied (i.e., slack is positive), the string ``=<='' is returned if the inequality is exactly satisfied (i.e., slack is zero) and ``!<='' if the constraint is not satisfied (i.e., slack is negative). Examples: @CONSTRAINT(A3/2,``<='',5,``SLACK'') = 1 when A3=8. @CONSTRAINT(A3/2,``=='',5,``'') = ``!='' when A3=8. @CONSTRAINT(A3/2,``>='',5,``'') = ``=>='' when A3=10. @LPSyntax: @LP(M,F,V,C) M = either of the strings ``MIN'' or ``MAX'' depending upon whether the objective function is to be minimized or maximized, respectively. F = any valid NExS cell expression that returns a numerical result. V = a range of cells whose values affect the value of the F expression in a linear fashion C = a range of cells containing @CONSTRAINT functions that constrain the values of the V variables in a linear fashion. @LP will ignore any cells in range C which do not contain @CONSTRAINT functions. The @LP returns 0 if it finds an optimal solution to the linear programming problem expressed by the objective function F, constraints C, and variables V. The optimum values of the variables are returned in the original range of cells C. If no optimum exists, then @LP returns a -1. If the optimum value of the objective function is unbounded (either positive or negative infinity), then @LP returns a 1. Examples: See the previous section. |