Problem 1 (3 points, Exer. 14 (a) in Linear Programming Exercises): An illumination problem. We consider an illumination system of m lamps, at positions ll, - - - , lm E R2, illuminating it at patches. The patches are line segments; the i-th patch is given by [0%, \"vi-+1], where '01, - - - , on\" 6 R2. The variables in the problem are the lamp powers 101,- -- , pm, which can vary between 0 and 1. C C lamp 3' p I} ' f a -. / To '.l0.U Ir .3 15+] 1." l '1 patch 1' The illumination at (the midpoint of) patch i is denoted by Ii. We will use a simple model for the illumination: m L- = Z (Igjpj, (133' = {IE2 max{cos 935, 0}, j=1 where i33- denotes the distance between lamp 3' and the midpoint of patch 15, and 91-5; denotes the angle between the upward normal of patch i and the vector from the midpoint of patch i to lamp 3', as shown in the gure. This model takes into account \"self-shading\" (i.e., the fact that a patch is illuminated only by lamps in the halfspace it faces) but not shading of one patch caused by another. Of course we could use a more complex illumination model, including shading and even reections. This just changes the matrix relating the lamp powers to the patch illumination levels. The problem is to determine lamp powers that make the illumination levels close to a given desired illumination level Ides, subject to the power limits 0 S pg- 3 1. Suppose we use the maximum deviation exp) = k 3113,\" In: Ideal (1) as a measure for the deviation from the desired illumination level. Write the illumination problem using this criterion as a linear programming