# Recitation 1

Problem 1: Solve the system of equations:

\begin{aligned}x_1 + 2x_2 - x_3 &= 6 \\ 3x_1 + 8x_2 + 9x_3 &= 10 \\ 2x_1 - x_2 + 2x_3 &= -2 \end{aligned}

Comment: Use Gaussian elimination on the associated augmented matrix.

Problem 2: Solve graphically: maximize $z = 3x_1 + x_2$ subject to $2x_1 + x_3 \le 6, x_1 + 3x_2 \le 9, x_1 \ge 0, x_2 \ge 0$.

Solution: The red lines are related to the first two constraints. The reddish area is the feasible domain. The dashed blue lines are level lines on which $z=3,6,9$ respectively. From the graph, $z=9$ is maximized by $x_1 = 3, x_2 = 0$.

Problem 3: Solve graphically (should have non-unique solutions): maximize $z=4x_1 + x_2$ subject to $8x_1 + 2x_2 \le 16, 5x_1 + 2x_2 \le 12, x_1 \ge 0, x_2 \ge 0$.

Solution: The red lines are related to the first two constraints. The reddish area is the feasible domain. The dashed blue lines are level lines on which $z=4,8$ respectively. From the graph, $z=8$ is maximized by points between $A$ and $B$.

Problem 4: (A knapsack example) NASA must make a decision regarding which experiments should be flown on a deep-space probe that can accommodate a total payload of 140 pounds. A panel of experts has assigned numerical values to each of the experiments. The assigned values and the weights of the experiments are shown in the table. Formulate the linear programming problem that determines which experiments should be selected for the probe in order to achieve the greatest total value.

Experiment Weight Value
1 35 60
2 45 70
3 55 80
4 42 90
5 35 50

Solution: We want to maximize the total value $60x_1 + 70x_2 + 80x_3 + 90x_4 + 50x_5$, where $x_i$ is a variable that can assume only a 1 or a 0 depending on whether or not the item is on the probe. Those variables are subject to the total payload of 140 pounds, that is, $35x_1 + 45x_2 + 55x_3 + 42x_4 + 35x_5 \le 140$.