NON LINEAR PROGRAMMING Prof. Stephen Graves In a linear program, the constraints are linear in the decision variables, and so is the objective function. In a non linear program, the constraints and/or the objective function can also be non linear function of the decision variables. Example: Gasoline Blending: The qualities of a blend are determined by the qualities of the stocks used in the blend. An optimization is to determine the volume of each input stock in each blend so that the objective function is optimized subject to the output blends satisfying their quality specifications, stock availability constraints, and blend demand constraints. The decision variables are xij denoting the amount of stock i in blend j. For the most part the constraints can be written as linear functions; but some of the quality constraints are non linear: Distillation Blending: Djk = bk + ck * ln [ Σi ( Sik * VFij) ] where Djk is the k th distillation point for blend j. Sik is the k th distillation point for stock i. VFij is the volume fraction of stock i in blend j and is equal to xij/ (Σi xij) and bk and ck are constants. 15.066J Summer 2003 82Octane Blending: OCTjk = ak{ Σi ( bi * bi * VFij) - Σi (c i * VFij)2 } + dk{ Σi ( ei * VFij) - Σi (f i * VFij)2 }2 + gk Σi { ( hi * VFij) - ( ji * ki * VFij * VFij)} where OCTjk are the various octane indices for blend j. For both Djk and OCTjk the optimization problem would have simple upper bounds and lower bounds for each blend and for each quality index. Thus the constraints for the formulation would include: jijiijifor each stock i: where is the availability of stock ifor each blend j: x where is the requirement for blend jfor each combination i, j, we define : Vplus upper bouij i ijjijijxA ARRxx≤≥=∑∑∑nds and lower bounds on the distillation points and octane levels for each blend 15.066J Summer 2003 83Example: Site Location; given customer locations (xi, yi), find the location (X, Y) that minimizes the weighted distances from the customer to the central warehouse (or minimizes the maximum distance to an emergency vehicle location). The distance from customer i to the warehouse is di and is typically a non-linear function of the decision variables (xi, yi), and (X, Y). To wit, we might have ()()22ii iii idxXyYordxXyY=−+−=−+− We then have an objective:1 NiiiMin w d=∑ subject to constraints on the decision variables. Example: Determine the production quantities for each family of car (luxury, intermediate, mid size, compact, subcompact) that maximizes net revenue subject to production capacity constraints, fleet fuel mileage constraints. (Haas, SM thesis, 1977) Decision variables are qi and pi, which denote the quantity and price for each car family. We then need to assume a relationship between price and quantity, e.g., linear supply-demand function: where aiiiqabp=−i)i and bi are positive constants. The objective of the model is non-linear, to maximize profits: () ( iii iiiiiMax q p C q p C×−= ×−∑∑ where Ci equals the cost per unit for car from family i. We would have linear capacity constraints: for each resource type j: where is the amount of available respource of type j,and is the per unit consumption of resource j to produce a unit of car i.ij i j jiijRq K KR≤∑ We also have a non-linear fleet fuel mileage constraint; the fleet fuel mileage is computed as the harmonic average, and needs to exceed some target, say 30 mpg: 121212...30...nnnqq qmpgqqqmpg mpg mpg+++≥+++ where mpgi is the miles per gallon for car family i. 15.066J Summer 2003 84Example: Flow in Pipes - In designing a network of pipes, say, for a chemical processing facility, you might be given the network topology (nodes and edges), the desired flow inputs at supply points, desired flow outputs at consumption points, and inlet pressures at supply points. The decision variables are the size of pipes (diameter) needed to connect the nodes of the network. The problem is to determine for each edge of the network, the diameter of the pipe and the flow rate on that edge. We define the variables: qj is the flow rate on edge j, dpj is the pressure drop across edge j, and dj is the diameter of edge j. There are flow balance constraints at each node of the network (i.e., flow into the node = flow out of the node), and constraints on the external flow inputs and outputs. For each edge, the flow rate is a non-linear function of the diameter of the pipe and the drop in pressure across the edge, e.g., : qj2 = c dpj dj5 where c is a constant, and the drop in pressure across an edge equals the difference in the node potentials. The objective would be to minimize the cost of the pipes, which depends on the diameters chosen. 15.066J Summer 2003 85Example: Robot Motion Planning (taken from LFM thesis, Evaluation of a New Robotic Assembly Workcell Using Statistical Experimental Techniques and Scheduling Procedures by Erol Erturk, 1991) The problem is to determine the velocity and acceleration for a new robot assembly system for a given displacement of length d. The objective is to minimize time, subject to a constraint on placement accuracy. We assume the robot accelerates at a constant rate of acceleration until it reaches its peak velocity, then will travel at its peak velocity, until it must decelerate also at a linear rate. Then the time (in seconds) to travel a distance d is: Travel time = T = v/a + d/v where a is the acceleration and deceleration rate (inch/sec2), and v is the peak velocity (inch/sec) . The accuracy (in mils) of the placement depends upon the acceleration rate and the peak velocity and has been found empirically to be given by: 0.022 0.0079 - 0.0002Aaccuracy v a v a==+ × The optimization is then to minimize T, subject to a constraint on accuracy A, as well as upper bounds on acceleration (a) and velocity (v). 15.066J Summer 2003 86Example: Design parameters for coil spring (from Rajan Ramaswamy’s thesis, Computer Tools for Preliminary Parametric Design, Ph. D., LFM 1993) The coil spring is used to provide a clamping force in an indexing mechanism. Hence, it must deliver a specified force while satisfying constraints on compressed length, geometry and material. The objective is to find the lightest feasible design, i. e., minimize mass. The following equations come from Mark’s handbook for