Problem 1
A linear program maximizes $Z = 40x + 30y$ subject to a feasible region whose corner points include (0,0), (10,0), (8,10), and (0,14). Using the fact that a linear program's optimal solution always occurs at a vertex of the feasible region, evaluate Z at each vertex to find the maximum value.
- A400, at vertex (10,0), the vertex with the largest x-value
- B560, at vertex (0,14), the vertex with the largest y-value
- C620, at vertex (8,10)correct
- D1,000, summing the Z-values of all four vertices
Show the solution
A linear program's objective function, being linear, cannot have an interior maximum over a convex polygonal feasible region — its extreme value is guaranteed to occur at one of the region's corner points (vertices), which is exactly why solving a linear program reduces to checking a short list of vertices rather than searching the entire continuous region. Evaluating Z at each vertex: $Z(0,0) = 40(0)+30(0) = 0$. $Z(10,0) = 40(10)+30(0) = 400$. $Z(8,10) = 40(8)+30(10) = 320+300 = 620$. $Z(0,14) = 40(0)+30(14) = 420$. The largest value is 620, at vertex (8,10). Notice this optimal vertex is neither the one with the largest single coordinate nor an obvious guess — it's the specific combination where the objective function's own weighting (40 per unit of x versus 30 per unit of y) best matches the feasible region's shape, which is precisely why evaluating every vertex explicitly, rather than guessing which one 'looks best,' is the reliable way to solve a linear program by the corner-point method.
Problem 2
In Operations Research and Mathematical Programming, optimization models are categorized based on the mathematical properties of their objective functions and decision variable constraints. Match each industrial problem description to its appropriate mathematical programming classification.
Show the solution
**Step 1: Understand Mathematical Programming Model Classifications** From the FE Reference Handbook (Operations Research & Industrial Modeling): 1. **Nonlinear Programming (NLP):** Applies when either the objective function or at least one constraint contains nonlinear mathematical terms (e.g., quadratic octane blending curves, exponential chemical kinetics). 2. **Binary Integer Programming (BIP):** A specialized subset of Integer Linear Programming where decision variables are constrained to binary values $x_j \in \{0, 1\}$, widely used in capital budgeting, location selection, and fixed-charge problems. 3. **Linear Programming (LP):** Optimization problems where both the objective function and all structural constraints are linear functions of continuous decision variables ($x_j \ge 0$). 4. **Goal Programming (GP):** An extension of Linear Programming designed for multi-criteria decision-making with multiple conflicting, prioritized goals, using deviational variables ($d_i^+, d_i^-$) to minimize deviations from target goals. **Step 2: Decoy Analysis** - *Dynamic Programming (DP)* solves sequential/multi-stage decision problems via Bellman's principle of optimality. - *Markov Decision Process (MDP)* models stochastic sequential decisions with memoryless state transitions. Conclusion: - Chemical blending with quadratics $\implies$ **Nonlinear Programming (NLP)** - Facility site selection $\implies$ **Binary Integer Programming (BIP)** - Resource allocation with linear terms $\implies$ **Linear Programming (LP)** - Multi-criteria staffing goals $\implies$ **Goal Programming (GP)**
Problem 3
Two competing express freight carriers engage in competitive pricing for a major logistics contract. The payoff matrix representing the net profit gain (in millions of dollars) for Player 1 (Row Player) against Player 2 (Column Player) is given by: $$\begin{pmatrix} 4 & 1 \\ 2 & 5 \end{pmatrix}$$ Row Player can choose Strategy 1 with probability p_1 and Strategy 2 with probability (1 - p_1). Column Player chooses Strategy 1 with probability q_1 and Strategy 2 with probability (1 - q_1). What is the value of the game (V) and the optimal mixed strategy probability p_1* for Player 1 under von Neumann's Minimax Theorem?
- A2.00 game value with Player 1 optimal strategy p = (1.00, 0.00)
- B4.00 game value with Player 1 optimal strategy p = (0.33, 0.67)
- C3.00 game value with Player 1 optimal strategy p = (0.50, 0.50)correct
- D1.50 game value with Player 1 optimal strategy p = (0.25, 0.75)
Show the solution
**Step 1: Test for Pure Saddle Point (Minimax = Maximin)** From the FE Reference Handbook (Operations Research / Game Theory): - Row minima: $$\min(4, 1) = 1, \quad \min(2, 5) = 2 \implies \text{Maximin} = \max(1, 2) = 2$$ - Column maxima: $$\max(4, 2) = 4, \quad \max(1, 5) = 5 \implies \text{Minimax} = \min(4, 5) = 4$$ Since $\text{Maximin} (2) \ne \text{Minimax} (4)$, no pure saddle point exists. The optimal solution requires mixed strategies. **Step 2: Formulate Player 1 Expected Payoffs** Let $p_1$ be the probability of Player 1 choosing Row 1, and $p_2 = 1 - p_1$ for Row 2: - If Player 2 plays Column 1: $$E_1(p_1) = 4 p_1 + 2(1 - p_1) = 2 p_1 + 2$$ - If Player 2 plays Column 2: $$E_2(p_1) = 1 p_1 + 5(1 - p_1) = 5 - 4 p_1$$ **Step 3: Solve for Optimal Mixed Strategy p_1*** By the principle of indifference, Player 1 equates expected payoffs across both columns: $$2 p_1 + 2 = 5 - 4 p_1$$ $$6 p_1 = 3 \implies p_1^* = \frac{3}{6} = 0.50$$ $$p_2^* = 1 - 0.50 = 0.50$$ **Step 4: Compute Game Value (V)** Substitute $p_1^* = 0.50$ into either expected payoff equation: $$V = 2(0.50) + 2 = 1.00 + 2.00 = 3.00$$ *(Verification with $E_2$: $V = 5 - 4(0.50) = 5 - 2 = 3.00$).* *(Similarly, for Player 2: $4 q_1 + 1(1 - q_1) = 2 q_1 + 5(1 - q_1) \implies 3 q_1 + 1 = 5 - 3 q_1 \implies 6 q_1 = 4 \implies q_1^* = 2/3, q_2^* = 1/3$).* Conclusion: The solution is **3.00 game value with Player 1 optimal strategy p = (0.50, 0.50)** (Option C).