Question 2 of 10: LP Formulation — Survey-Company Interview Bid
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
National Exams — May 2019 — 17-Ind-A1 Operations Research. Three-hour, open-book exam (any non-communicating calculator permitted); the paper totals 175 marks across 10 questions and only 100 marks are required, so a candidate would normally answer a subset — all ten are solved below for completeness.
Reference texts: Hillier & Lieberman, Introduction to Operations Research (11th ed., McGraw-Hill) — linear programming & the simplex method (ch. 3–4), duality & sensitivity analysis (ch. 6), dynamic programming (ch. 11), network optimization & CPM/PERT project crashing (ch. 9–10), queueing theory incl. finite-source (machine-repair) models (ch. 17), decision analysis & the value of information (ch. 15–16), Markov chains (ch. 16), Monte Carlo simulation (ch. 20). Nahmias, Production and Operations Analysis — deterministic EOQ inventory models with and without planned shortages.
Given. Four interview types (personal/telephone × day/night) at the costs tabulated above; requirements: ≥300 personal interviews overall, ≥500 night interviews overall, day telephone interviews ≥60% of all day interviews, ≥1000 total interviews.
Find. Decision variables and the complete LP model (objective + constraints) for minimum-cost bidding. Do not solve.
Approach. Define one decision variable per (type, time) combination, translate each of the four bullet requirements into a linear constraint, and minimize total interview cost.
Decision variables (number of interviews of each kind, all in units of interviews):
$x_{PD}$ = personal interviews, day; $x_{PN}$ = personal interviews, night; $x_{TD}$ = telephone interviews, day; $x_{TN}$ = telephone interviews, night.
Objective — minimize total interview cost:
$$\min Z = 2.00x_{PD} + 2.10x_{PN} + 1.00x_{TD} + 1.20x_{TN}$$
Constraint (a) — at least 300 personal interviews (day + night, personal):
$$x_{PD}+x_{PN}\ge 300$$
Constraint (b) — at least 500 night interviews (personal + telephone, night):
$$x_{PN}+x_{TN}\ge 500$$
Constraint (c) — of the day interviews, ≥60% are by telephone. Day interviews total $x_{PD}+x_{TD}$, of which telephone must be at least 60%:
$$x_{TD}\ge 0.6\,(x_{PD}+x_{TD})\ \Longrightarrow\ 0.4x_{TD}-0.6x_{PD}\ge 0\ \Longrightarrow\ \boxed{x_{TD}\ge 1.5\,x_{PD}}$$
Constraint (d) — at least 1000 total interviews and non-negativity:
$$x_{PD}+x_{PN}+x_{TD}+x_{TN}\ge 1000,\qquad x_{PD},x_{PN},x_{TD},x_{TN}\ge 0$$
