Operations Research Lecture 1: Linear …

1 Operations Research Lecture 1: Linear Programming Introduction notes taken by Kaiquan Xu@Business School, Nanjing University 25 Feb 2016. 1 Some Real Problems Some problems we may meet in practice or academy: Production Planning Given a manufacturer plans to produce two types of products: I and II, the required matireials (A & B) and equipment for producting one product are list in Table 1. The profits for Product I and II are 2$ and 3$. The question is: how to make product planning, so the manufacturer can get the maximum profit. Table 1: Example: Product Planning. Product I Product II Available Resources equipment 1 2 8. matireial A 4 0 16. matireial B 0 4 12. Let x1 and x2 be as the numbers of Product I and II to be produced. Under the constraints of the resources, the variables should satisfy the following conditions: x1 + 2x2 8.

2 4x1 16. 4x2 12. The profit z can be represented as z = 2x1 + 3x2 . This problem can be described as the following math model: max z = 2x1 + 3x2. x1 + 2x2 8. 4x1 16. 4x2 12. x1 , x2 0. Load Balancing Problem For n processors with loaded work, distribute the new work such that the lightest-loaded processor has as heavy a load as possible. pi = current load of processor i = 1, 2, ..n, L = additional total load to be distributed, Pn xi = fraction of additional load L distributed to processor i, with xi 0 and i=1 xi = 1, 1. = minimum of final loads after distribution of workload L. We can formulate this problem as follows: max . x, . e p + xL. eT x = 1. x 0. Where e = {1, 1, .., 1}T. Resource Allocation Produce m types of products, by using n resources.

3 Each unit of product i yields ci dollars in revenue, whereas each unit of resource j costs dj dollars. One unit of product i requires Aij units of resource j to manufacture, and a maximum of bj units of resource j are available How to allocate resources to product products to maximize the profit? yi = the number of unites of product i xj = the number of units of resource j consumed We have max z = cT y dT x x,y x = AT y x b x, y 0. noindent Where the jth equation of x = AT y is xj = A1j y1 + A2j y2 + .. + Amj ym Approximation& Fittting In Economy, Finance, Marketing and other fields, we need to analyze the factors influecing some metrics, or make some predictions. For example, GDP prediction in Figure 1. These are approximation and fitting problems.

4 Figure 1: GDP Prediction 2. Given m data points (ai , bi ), i = 1, .., m, where ai <n and bi <, build a model that predicts the value of b from the vector a. A Linear model b = aT x is a popular one. We should choose a model that explains the avaiable data as best as possible, a model that results in small residuals (Figure 2). One possible way is to mimimize the largest residual, that is to minimize max bi aT. i x i Figure 2: Approximation& Fitting The following is an equivalent Linear programming formulation: min z bi aT. i x z i = 1, .., m, bi + aTi x z i = 1, .., m, here, the decision variables being z and x. An alternative formulation is to adopt the cost criterion m X. bi aT. i x i=1. The corresponding formulation is min z1 + .. + zm bi aT.

5 I x zi i = 1, .., m, bi + aTi x zi i = 1, .., m, m (bi aT 2. P. In practice, the quadratic cost criterion i x) is often adopted ( least square fit ), which will be discussed i=1. in the later chapters. Pattern Classification Credit risk management is a typical Pattern Classification problem. A sample data of credit card application: 3. Figure 3: Credit Card Application In classification problems, given two sets of points in the space of n dimensions Rn , find a hyperplane that separate these two set as accurately as possible. Let's see how to use Linear programming to find the separating hyperplane. The hyperplane is defined by a vector Rn and a scalar . Ideally, each point t in the first set satisfies T t , and one in the second set satisfies T t.

6 To guard against a trivial answer ( = 0 and 6= 0, the conditions are trivially satisfied), we enforce the stronger conditions T t + 1 for points in the first set, and T t 1 for points in the second set. Figure 4: Pattern Classification Let M to be m n matrix, whose ith row contains the n components of the ith points in the first set. Similarly construct k n matrix B from the points in the second set. The violations of the condition T t + 1 for the point in the first set are measured by a vector y, which is defined by y (M e) + e (here y 0 and e = (1, 1, .., 1)T Rm ). Similarly, for the points in second set, the violations are measured by z defined by z (B e) + e (z 0, e Rk ). The average violation on the first set is eT y/m and on the second set is eT z/k.

7 The classification is formulated as follows: 4. min eT y/m + eT z/m , ,y,z y (M e) + e z (B e) + e (y, z) 0. Figure 5: Classifier with Linear Programming 2 Linear Programming (LP). General Form n Given a cost vector c = (c1 , .., cn )T , we seek to minimize (maximize) a Linear cost function cT x =. P. ci xi over all i=1. n-dimensional vector x = (x1 , .., xn )T , subject to a set of Linear equality and inequality constraints. min c1 x1 + c2 x2 + .. + cn xn a11 x1 + a12 x2 + .. + a1n xn b1. a21 x1 + a22 x2 + .. + a2n xn b2.. am1 1 x1 + am1 2 x2 + .. + am1 n xn bm1. a11 x1 + a12 x2 + .. + a1n xn b01. a21 x1 + a22 x2 + .. + a2n xn b02.. am2 1 x1 + am2 2 x2 + .. + am2 n xn b0m2. a11 x1 + a12 x2 + .. + a1n xn = b001. a21 x1 + a22 x2 + .. + a2n xn = b002.

8 Am3 1 x1 + am3 2 x2 + .. + am3 n xn = b00m3. x1 , x2 , .., xn ( )0. 5. min cT x aT. i x bi i M1. aT. i x bi i M2. aT. i x = bi i M3. xj 0 j N1. xj 0 j N2. The variable x1 , .., xn are called decision variables, a vector x satisfying all of the constraints is called a feasible solution. ct x is called the objective function, a feasible solusion x? that minimizes the objective function (that is, cT x? cT x for all feasible x) is called an optimal solution. If we can find a feasible solution x whose cost is less than any real number, we say that the optimal cost is (unbounded below, the problem is unbounded). Reduction to standard form The standard form of a Linear programming(LP) problem is min c1 x1 + c2 x2 + .. + cn xn a11 x1 + a12 x2 +.

9 + a1n xn = b1. a21 x1 + a22 x2 + .. + a2n xn = b2.. am1 x1 + am2 x2 + .. + amn xn = bm x1 , x2 , .., xn 0. A general Linear programming problem can be transformed into an equivalent problem in standard form: . a) Elimination of free variables: Given an unrestricted variable xj , replace it by x+ +. j xj , where xj 0, xj 0. Pn b) Elimination of inequality constraints: Given an inequality constraint of the form aij xj ( )bi , introduce a j=1. new variable si and convert the constrain as n X. aij xj + si ( si ) = bi ; si 0. j=1. here, si is called as a slack variable Example 1. The Linear programming problem min 2x1 + 4x2. x1 + x2 3. 3x1 + 2x2 = 14. x1 0. can be converted into the stardard form . min 2x1 + 4x+ 2 4x2. + . x1 + x2 x2 x3 = 3.

10 3x1 + 2x+ 2 2x2 = 14. + . x1 , x2 , x2 , x3 0. 6. 3 References 1. Dimitris Bertsimas, John N. Tsitsiklis. Introduction to Linear Programming, Athena Scientific, 2. Michael C. Ferris, Olvi L. Mangasarian, Stephen J. Wright. Linear Programming with Matlab, SIAM, 2007. 7.