Here is the problem I'm trying to solve:

"A company makes three products, named product A, product B and product C. The company has 4 available workers, and the workers have different rates as they work on each of the three products. Also, because of the nature of their contracts, the workers charge a different amount depending on which product they are working on. The time it takes for worker i to make on product of time A, B or C, and the amount they charge depending on the product, are summarized in the two tables given.

Table 1: Time in minutes it takes Worker i to make one unit of product j.

Table 2: Amount paid by company for one hour of Worker i when working on product j.

(I'm not able to create the actual tables here, but it's pretty easy to get an idea of what the tables structure is from the table descriptions above)

Suppose each worker works for 40 hours each week. Due to the company’s commitments to existing customers, the company must produce at least 100 units of product A, 150 units of product B and 100 units of product C. Write a linear program that will tell the company how to assign each worker in order that the demand for each widget is met, and cost to the company is minimized.

Thus, you must state what are the decision variables, and then what is the vector corresponding to the objective function, the matrix corresponding to the constraints, etc."

I've spent hours trying to formulate this as a linear program and the only approach that I could think of was to minimize the total cost by making it of the form min CX where each element of C i.e. C(i)(j) denotes the amount worker i charges to work on product j per unit time and each element of X i.e. X(i)(j) denotes the total time worker i spends working on product j. But this is obviously not the right approach as C and X are supposed to be vectors. I've tried searching for problems that might be similar to this but couldn't find any.


2 Answers 2


You're on the right track. You can squash the $C$ and $X$ matrices into vectors. For instance, suppose that you have two workers and three products, so that $C$ and $X$ are 2x3 matrices. Let $c=(C_{11}, C_{12}, C_{13}, C_{21}, C_{22}, C_{23})$ and let $x = (X_{11}, \dots, X_{23})$. Now you have vectors.


Let consider a planning time period made of 1 week. Every worker works 8 hours per day and 5 days per week, so that the amount available of time for working per week is equal to $40$ hours $= 2,400$ minutes. Let introduce $4 \cdot 3 = 12 $ positive integer variables designated as $x_{i,j}$ where $i=1,2,3,4$ and $j=1,2,3$.

$x_{i,j}$ represents the quantity of j-th product made by i-th worker, clearly it should be a positive integer.

$a_{i,j}$ is time in minutes taken by Worker i to make one unit of product j.

$b_{i,j}$ is cost paid by company for one hour of Worker i when working on product j

We want to meet the weekly demand of the three products, spending as minimum as possible.

The objective function can be properly formulated as

$ \min \sum_{i=1}^4 \sum_{j=1}^3 (a_{i,j}/60) \cdot b_{i,j} \cdot x_{i,j} $

subject to $\left\{ \begin{array}{l} \sum_{i=1}^4 x_{i,1} \geq 100 \\ \sum_{i=1}^4 x_{i,2} \geq 150 \\ \sum_{i=1}^4 x_{i,3} \geq 100 \\ \sum_{j=1}^3 a_{1,j} x_{1,j} \leq 2,400 \\ \sum_{j=1}^3 a_{2,j} x_{2,j} \leq 2,400 \\ \sum_{j=1}^3 a_{3,j} x_{3,j} \leq 2,400 \\ \sum_{j=1}^3 a_{4,j} x_{4,j} \leq 2,400 \\ x_ij \in N \forall i=1,2,3,4 \forall j=1,2,3 \\ \end{array} \right. $

$ \sum_{i=1}^4 x_{i,j} \geq c_j $ designates the constraint on weekly demand for j-th product where $c_j $ is the demand for j-th product.

$ \sum_{j=1}^3 a_{i,j} x_{i,j} $ is the working time spent by i-th worker, so $ \sum_{j=1}^3 a_{i,j} x_{i,j} \leq 2,400 $ designates the constraint on the total amount of minutes available for i-th worker in one week.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .