Example 1.2.1 (A product mix). A company makes two components, \(C_1\) and \(C_2\). Each \(C_1\) needs Rs. 10 of budget, \(3\) hours of machine time and \(2\) hours of assembly; each \(C_2\) needs Rs. 40, \(2\) hours and \(3\) hours. In each period Rs. 4000 of budget, \(2000\) machine hours and \(1400\) assembly hours are available. The components sell for Rs. 30 and Rs. 70 and cost Rs. 10 and Rs. 40 to make. With \(x_1\), \(x_2\) the numbers made, the profit per unit is \(30 - 10 = 20\) and \(70 - 40 = 30\), and the model is \[ \begin {aligned} \text {maximise } & Z = 20x_1 + 30x_2 \\ \text {subject to } & 10x_1 + 40x_2 \leq 4000 \quad \text {(budget)}, \\ & 3x_1 + 2x_2 \leq 2000 \quad \text {(machine)}, \qquad 2x_1 + 3x_2 \leq 1400 \quad \text {(assembly)}, \\ & x_1, x_2 \geq 0 . \end {aligned} \] The solution (Software 1.4.1) is to make \(400\) of \(C_1\) and none of \(C_2\), for a profit of Rs. 8000, using the whole budget and leaving \(800\) machine hours and \(600\) assembly hours idle: the budget, not the capacity, is the binding constraint.

Example 1.2.2 (Assigning inspectors). At least \(2000\) pieces a day must be inspected in an \(8\)-hour day. There are \(9\) Grade 1 inspectors, who check \(40\) pieces an hour with \(97\%\) accuracy and are paid Rs. 5 an hour, and \(11\) Grade 2 inspectors, who check \(30\) pieces an hour with \(95\%\) accuracy at Rs. 4 an hour. Each error costs the company Rs. 3. The hourly cost of a Grade 1 inspector, wages plus errors, is \(5 + 3 \times 40 \times 0.03 = 8.60\), and of a Grade 2 inspector \(4 + 3 \times 30 \times 0.05 = 8.50\); per day these are \(68.8\) and \(68\). With \(x_1\), \(x_2\) the numbers assigned, \[ \text {minimise } 68.8x_1 + 68x_2 \quad \text {subject to}\quad 320x_1 + 240x_2 \geq 2000, \quad 0 \leq x_1 \leq 9, \quad 0 \leq x_2 \leq 11 . \] The LP solution is \(x_1 = 6.25\), \(x_2 = 0\), at Rs. 430: Grade 1 inspectors cost \(68.8/320 = 0.215\) per piece against \(68/240 = 0.283\). But inspectors are whole people, and divisibility fails; the best whole assignment is not \(7\) Grade 1 inspectors (Problem 1.5.1). We return to this in the section on integer programming.

Example 1.2.3 (Production planning over time). Demand for a product over four months is \(100\), \(150\), \(200\) and \(120\) units. Each month up to \(140\) units can be made in regular time at Rs. 10 each and up to \(40\) more in overtime at Rs. 14; units carried from one month to the next cost Rs. 2 each to store; there is no initial stock. With \(R_t\), \(O_t\) the regular and overtime production and \(I_t\) the stock at the end of month \(t\) (\(I_0 = 0\)), the model is \begin {gather*} \text {minimise } \sum _{t = 1}^4(10R_t + 14O_t + 2I_t) \\ \text {subject to}\quad I_{t - 1} + R_t + O_t - I_t = d_t, \quad 0 \leq R_t \leq 140, \quad 0 \leq O_t \leq 40, \quad I_t \geq 0 . \end {gather*} The balance equations, one per month, are the typical structure of dynamic models: what comes in equals what goes out. The optimal plan (Software 1.4.2) uses regular time fully in the first three months and builds stock ahead of the peak, at total cost Rs. 5960; overtime is used only in the peak month, because storing a regular unit for one month (\(10 + 2 = 12\)) is cheaper than overtime (\(14\)), but storing it for three months (\(10 + 6 = 16\)) is not.

Example 1.2.4 (Blending). A feed company makes two cattle mixes from wheat and barley: Fertilex, two parts wheat to one of barley, and Multiplex, one part wheat to two of barley. Wheat costs Rs. 1.50 a kilogram, with \(1000\) kg available this month, and barley Rs. 1.25, with \(1200\) kg available. Fertilex sells for Rs. 1.80 and Multiplex for Rs. 1.70 a kilogram. With \(x_1\), \(x_2\) the kilograms of each mix made, the wheat used is \(\frac 23x_1 + \frac 13x_2 \leq 1000\), that is \(2x_1 + x_2 \leq 3000\), and the barley used is \(\frac 13x_1 + \frac 23x_2 \leq 1200\), that is \(x_1 + 2x_2 \leq 3600\). The profit per kilogram is \(1.80 - (\frac 23\cdot 1.50 + \frac 13\cdot 1.25) = 0.383\) for Fertilex and \(1.70 - (\frac 13\cdot 1.50 + \frac 23\cdot 1.25) = 0.367\) for Multiplex. (In a published version of this example the barley constraint appears as \(x_1 + 2x_2 \leq 36\,000\), a slip of a factor ten that changes the answer: always check the arithmetic of a formulation against the original data.)