MATH 445/545 Homework 1: Due February 13th, 2014 Answer the following questions. Please include the questions with the solution. I do not want to see scrap work. 1. Only three brands of beer (beer1, beer2, and beer3) are available for sale in Metropolis. From time to time, people try one or another of these brands. Suppose that at the beginning of each month, people change the beer they are drinking according to the following rules: • 30% of the people who prefer beer 1 switch to beer 2. • 20% of the people who prefer beer 1 switch to beer 3. • 30% of the people who prefer beer 2 switch to beer 3. • 30% of the people who prefer beer 3 switch to beer 2. • 10% of the people who prefer beer 3 switch to beer 1. For i = 1, 2, 3, let xi be the number who prefer beer i at the beginning of this month and let yi denote the number who prefer beer i at the beginning of next month. Use matrix notation to relate x = (x1 x2 x3 )T and y = (y1 y2 y3 )T . Solution: Note that the following equations will hold for the rules given above: 0.5x1 + 0.0x2 + 0.1x3 = y1 People switch to beer 1 0.3x1 + 0.7x2 + 0.3x3 = y2 People switch to beer 2. 0.2x1 + 0.3x2 + 0.6x3 = y3 People switch to beer 3. where we needed to find the number of type over the course of the month. Let  0.5 A =  0.3 0.2 people that stayed loyal to any particular  0.0 0.1 0.7 0.3  . 0.3 0.6 and note that Ax = y. 2. Model each of the following decision making situations as a linear program (LP). For each LP clearly define your decision variables, objective function and constraints. (a) Suppose that the latest scientific studies indicate that cattle need certain amounts b1 , . . . , bm of nutrients N1 , . . . , Nm respectively. More over, these nutrients are currently found in n commercial feed materials F1 , . . . , F n as indicated by coefficients aij , i = 1, . . . , m, j = 1, . . . , n, that denote the number of units of nutrientNi per pound of feed material Fj . Each pound of Fj costs the rancher cj dollars. How can a rancher supply these minimal nutrient requirements to his prize bull while minimizing his feed bill? Solution: Linear Program: The goal of the problem is to minimize the cost of the bulls food while maintaining the bulls healthy diet. Let xj be the number of pounds that the farmer should purchase of commercial feed Fj where , j = 1, . . . , n. Thus the farmer wishes to minimize the following cost equation (where z denotes the farmers total cost): Minimize: z = c1 x 1 + c2 x 2 + . . . + cn x n = n X cj x j j=1 In order to meet the nutrient requirements the farmer needs to impose the following constrictions on his cost equation: a11 x1 a21 x1 a31 x1 .. . + a12 x2 + a22 x2 + a32 x2 .. . + a13 x3 + a23 x3 + a33 x3 .. . am1 x1 + am2 x2 + am3 x3 + . . . + a1n xn + . . . + a2n xn + . . . + a3n xn .. .. . . + . . . + amn xn ≥ b1 ≥ b2 ≥ b3 .. . ≥ bm where xj ≥ 0, j = 1, . . . , n Let x = [x1 , x2 , · · · , xn ]T , and c = [c1 , c2 , · · · , cn ]T . We can also denote [b1 , b2 , · · · , bm ]T by b, and coefficient matrix   a11 a12 a13 . . . a1n  a21 a22 a23 . . . a2n     a31 a32 a33 . . . a3n    by A.  .. .. .. ..  . .  . . . . .  am1 am2 am3 . . . amn Thus the farmer is minimizing z = cT x subject to, Ax ≥ b where xj ≥ 0, j = 1, . . . , n (b) Suppose that a small chemical company produces one chemical product which it stores in m storage facilities and sells in n retail outlets. The storage facilities are Page 2 located in different communities. The shipping costs from storage facility Fi to retail outlet Oj is cij dollars per unit of the chemical product. On a given day, each outlet Oj requires exactly dj units of the product. Moreover, each facility Fi has si units of the product available for shipment. The problem is to determine how many units of the product should be shipped from each storage facility to each outlet in order to minimize the total daily shipping costs. Solution: Linear Program: The goal of the problem is to minimize the cost of product shipping while maintaining product inventory and not overdrawing from supply. Let xij be the number of units of chemical shipped from facility Fi to retail outlet Oj , where i ∈ {1, . . . , m}, and j ∈ {1, . . . , n}. Let z denote the total cost of shipping. Thus, the chemical company wishes to optimize the following objective function, m X n X cij xij Minimize: z = i=1 j=1 In minimizing the above equation the company must meet the following constraints: P x11 + x21 + . . . + xm1 = Pm i=1 xi1 = d1 m x12 + x22 + . . . + xm2 = i=1 xi2 = d2 .. .. .. . . Pm. x = d x1n + x2n + . . . + xmn = n i=1 in That is each outletj requires dj of chemical where j ∈ {1, . . . , n}. Each Facility i also only has a limited supply of the chemical it can ship si where i ∈ {1, . . . , m}. Thus, the problem has the constrictions: Pn x1j ≤ s1 x11 + x12 + . . . + x1n = Pj=1 n ≤ s2 x21 + x22 + . . . + x2n = j=1 x2j .. .. .. . . Pn . xm1 + xm2 + . . . + xmn = x ≤ s m j=1 mj where xij ≥ 0 , i ∈ {1, . . . , m} and j ∈ {1, . . . , n} The notation of the problem can be simplified if matrix notation is used:   x11 x12 x13 · · · x1n  x21 x22 x23 · · · x2n     .. .. .. ..  = X . .  . . . . .  xm1 xm2 xm3 · · · xmn     d1 s1  d2   s2       ..  = d, and  ..  = s.  .   .  dn sm Page 3 Denote a column of 1’s that is k rows long by 1k and he linear program can now take the following form: Minimize: z = m X n X cij xij i=1 j=1 Subject to: X1n ≤ s X T 1m = d where all elements of X are greator than or equal to zero. (c) An investor has decided to invest a total of $50,000 among three investment opportunities: savings certificates, municipal bonds, and stocks. The annual return in each investment is estimated to be 7%, 9%, and 14%, respectively. The investor does not intend to invest her annual interest returns (that is, she plans to use the interest to finance her desire to travel). She would like to invest a minimum of $10,000 in bonds. Also, the investment in stocks should not exceed the combined total investment in bonds and savings certificates. And, finally, she should invest between $5,000 and $15,000 in savings certificated. The problem is to determine the proper allocation of the investment capital among the three investment opportunities in order to maximize her yearly return. Solution: Linear Program: The goal of the problem is to maximize the return on investment subject to several constraints. Let xc be the amount to be invested in savings certificates. Let xb be the amount to be invested in bonds, and Let xs be the amount to be invested in stocks. The goal of the problem is to now maximize the following return on investment objective function given by z: Maximize: z = .07xc + .09xb + .14xs The problem also has the following constraints, or is Subject to: xc + xb + xs = 50, 000 xb ≥ 10, 000 xs ≤ xb + xc 5, 000 ≤ xc ≤ 15, 000 with xs ≥ 0. This can be solved using LINDO and the following values are obtained (See Attached LINDO print out): Page 4 xc Solution xb xs = $5,000 = $20,000 = $25,000 (d) The owner of a small chicken farm must determine a laying and hatching program for 100 hens. There are currently 100 eggs in the hen house, and the hens can be used either to hatch existing eggs or to lay new ones. In each 10-day period, a hen can either hatch 4 eggs or lay 12 new eggs. Chicks that are hatched can be sold for 60 cents each, and every 30 days an egg dealer gives 10 cents each for the eggs accumulated to date. Eggs not being hatched in one period can be kept in a special incubator room for hatching in a later period. The problem is to determine how many hens should be hatching and how many should be laying in each of the next three periods so that total revenue is maximized. Solution: Linear Program: The goal of the problem is to maximize the total revenue over the next 30 day period subject to several constraints. Let Hhi be the number of hens hatching eggs in period i, i ∈ {1, 2, 3}. Let Hli be the number of hens laying eggs in period i, i ∈ {1, 2, 3}. Let Es0 be the number of eggs initially in storage (100 eggs). Let Esi be the number of eggs in storage at the end of period i, i ∈ {1, 2, 3}. The goal of the problem is to now maximize the profit made on the eggs and chicks produced by the chickens defined by the objective function z. That is: Maximize: z = .6 × 4 (Hh1 + Hh2 + Hh3 ) + .1Es3 Subject to: Hhi + Hli = 100 4Hhi ≤ Es(i−1) Es(i−1) − 4Hhi + 12Hli = Esi Hhi , Hli , Esi ≥ 0, where i ∈ {1, 2, 3} When the above program is optimized using LINDO(see the attached print out). After solving the following values are obtained: Hh1 Hh2 Hh3 Hl1 Hl2 H13 Es0 Es1 Es2 Es3 Page 5 = = = = = = = = = = 25 100 100 75 0 0 100 900 500 100 This is sensible, because the return from a hatched chicken is 60 cents, and that of an egg is only 10 cents. Thus, a Hen laying 12 eggs a period can generate $1.20 and a Hen hatching 4 eggs can generate $2.40. Additional Homework for MATH 545 1. Show that for any two matrices A and B, (AB)T = B T AT . Solution: Assume that A is an m × n matrix and B is an n × q matrix so that there product is defined. Thus, AB is an m × q matrix, and its transpose is a q × m matrix. We can also note that B T AT is the product q × n matrix and a n × m matrix resulting in again a q × m. So each side of the equality is of the same size. We now only need to show that the arbitrary element in row i and column j of (AB)T is the same as the row i column j element in B T AT . Denoting the entry in row i column j in a matrix M as Mi,j we can consider the following algebra: (AB)Ti,j = (AB)j,i n X Aj,k Bk,i = k=1 = = n X k=1 n X T ATk,j Bi,k T Bi,k ATk,j k=1 T = (B AT )i,j which concludes the proof. 2. The Gotham City Police Department employs 30 police officers. Each officer works 5 days per week. The crime rate fluctuates with the day of the week, so the number of police officers required each day depends on which day of the it is: Sunday, 18; Monday, 18; Tuesday, 24; Wednesday, 25; Thursday, 16; Friday, 21; Saturday, 28. The police department wants to schedule police officers to minimize the number whose days off are not consecutive. Formulate an LP that will accomplish this goal. Type Page 6 your LP into LINDO1 and compute the optimal number of officers that do not get consecutive days off. Solution: For i < j let xij be the number of workers who get day i and j off each week. Here i = 1 is Sunday, and i = 7 is Saturday. Thus x12 is the number of workers getting Sunday and Monday off, and x17 are the number of workers who get Saturday and Sunday off. The objective function is to maximize the following pairs: max z = x12 + x17 + x23 + x34 + x45 + x56 + x67 Subject to each day of the week we need the proper number of officers to have the day off. x12 + x13 + x14 + x15 + x16 + x17 x12 + x23 + x24 + x25 + x26 + x27 x13 + x23 + x34 + x35 + x36 + x37 x14 + x24 + x34 + x45 + x46 + x47 x15 + x25 + x35 + x45 + x56 + x57 x16 + x26 + x36 + x46 + x56 + x67 x17 + x27 + x37 + x47 + x57 + x67 = = = = = = = 12 12 6 5 14 9 2 Sunday Monday Tuesday Wednesday Thursday Friday Saturday All variables are non-negative. That is xij ≥ 0∀i, j ∈ 1, 7such thati < j. 1 Note LINDO is available in the class lab, as well as free to download for academic use. Page 7