Question 2 of 9: LP Formulation — Survey Company Bid
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
National Exams — December 2017 — 98-Ind-A1 Operations Research. Three-hour, open-book exam (any non-communicating calculator permitted); the paper totals 180 marks across 9 questions (each worth 20) and only 100 marks are required, so a candidate would normally answer 5 — all nine are solved below for completeness.
Reference texts: Hillier & Lieberman, Introduction to Operations Research (11th ed., McGraw-Hill) — linear programming formulation & the simplex method (ch. 3–4), duality & sensitivity analysis (ch. 6), network optimization models (ch. 9), deterministic dynamic programming (ch. 11), integer programming (ch. 12), Markov chains (ch. 16), decision analysis (ch. 15), queueing theory (ch. 17); Nahmias, Production and Operations Analysis (7th ed.) — EOQ with and without planned shortages, the newsvendor (single-period) model (ch. 4–5).
Question 2: LP Formulation — Survey Company Bid (20 marks)
Given. Four interview types with unit cost: day-personal $2.00, day-telephone $1.00, night-personal $2.10, night-telephone $1.20. Requirements: (a) ≥300 personal interviews; (b) ≥500 night interviews (personal or telephone); (c) telephone interviews are ≥60% of the day interviews; (d) ≥1000 total interviews.
Find. Define the decision variables and set up (but do not solve) the LP model that minimizes total interview cost.
Approach. Split interviews into the four cells of the day/night × personal/telephone cost table, translate each of the four English requirements literally into one linear constraint on those four variables, and minimize the weighted-cost objective.
Decision variables (number of interviews of each type, all continuous and non-negative — a candidate would typically round up to integers when bidding, but the model itself is a pure LP):
$x_1$ = day, personal; $x_2$ = day, telephone; $x_3$ = night, personal; $x_4$ = night, telephone.
Requirement (a) — at least 300 personal interviews (personal happens in both day and night):
$$x_1+x_3\ge300$$
Requirement (b) — at least 500 night interviews (either type, at night):
$$x_3+x_4\ge500$$
Requirement (c) — of the DAY interviews, telephone is at least 60%. Day interviews total $x_1+x_2$; telephone-day interviews are $x_2$, so $x_2\ge0.6(x_1+x_2)$, which rearranges to:
$$0.4x_2\ge0.6x_1 \;\Longrightarrow\; x_2\ge1.5x_1$$
Requirement (d) — at least 1000 total interviews (all four cells):
$$x_1+x_2+x_3+x_4\ge1000$$
Objective — minimize total interview cost using the given per-interview costs, subject to Steps 2–5 and non-negativity:
$$\boxed{\min Z=2.00x_1+1.00x_2+2.10x_3+1.20x_4}$$
subject to $x_1+x_3\ge300$, $x_3+x_4\ge500$, $x_2-1.5x_1\ge0$, $x_1+x_2+x_3+x_4\ge1000$, $x_1,x_2,x_3,x_4\ge0$. Per the question, this model is formulated but not solved.
