Jimbo Enterprises produces $n$ products. Each product can be produced in one of $m$ machines. Let $t_{ij}$ be the time in hours needed to produce one unit of product $i$ on machine $j$. For month $k$, the number of hours available on machine $j$ is $h_{kj}$. Customers are willing to buy up to $d_{ik}$ of product $i$ in month $k$ at the unit cost of $c_{ik}$. Formulate a Linear Program that Jimbo can use to maximize the revenue by selling the products for the next $p$ months.

I need help making a formulation for this Linear Program.



Let $x_{ijk}$ be the units of product $i$ produced on machine $j$ in month $k$.

This can be folded into a vector of dimension $N = n\,m\,p$.

Cost function: $$ c^\top x = \sum_{i=1}^n \sum_{j=1}^m \sum_{k=k_0}^{k_0 + p - 1} c_{ik} x_{ijk} $$


1.) Available production time on machine $j$ for month $k$: $$ \sum_{i=1}^n t_{ij} x_{ijk} \le h_{kj} \quad (j \in \{ 1, \dotsc, m \}, k \in \{ k_0, \dotsc, k_0 + p -1 \}) $$ These are $m \, p$ inequalities.

2.) Demand for month $k$: $$ \sum_{j=1}^m x_{ijk} \le d_{ik} \quad (i \in \{1, \dotsc, n\}, k \in \{ k_0, \dotsc, k_0 + p -1 \}) $$ These are $n \, p$ inequalities.

Depending on what form your problem should be, you might need to add constraints $x_{ijk} \ge 0$ and introduce slack variables, if you need equalities instead of inequalities.

If "unit cost $c_{ik}$" means that this is the revenue for product $i$ in month $k$ (and not the production cost), then one maximizes the cost function. Otherwise one would need additional information.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.