1

I have a question about the formulation of a LP involving fulfilling orders of a vending machine.

We have a vending machine which dispenses medicine to its patients. We assume that we have a list of data showing us what each patient is demanding. Each patient will demand multiple medicines, thus the assumption is that if we cannot fulfill their entire order then they will leave and never come back (they buy nothing). Given that we are trying to maximize the number of orders fully fulfilled under a certain # of items in the vending machine (constraint) how can we model this LP? In the data we know for each patient what different items they are demand (ex. customer 1 demands SKU 1, 3, 6 and customer 2 demands SKU 1, 8, 9).

Calvin P
  • 11

1 Answers1

0

Looks like there are $n$ different items.

$m$ Customers seems to ask either $0$ or $1$ of these per order. So we can model orders by $m$ vectors $$ u_i \in \{ 0, 1 \}^n $$ The machine has limited supplies $b \in \mathbb{Z}^n$, where $b \ge 0$.

We can model a decision which orders to fulfill as vector $$ x \in \{ 0, 1 \}^m $$ where $x_i$ models if we fulfill the $i$-th order or not.

The number of orders is $$ c^\top x $$ with $c = (1, \dotsc, 1)^\top \in \{0, 1 \}^m$.

This gives the integer linear program $$ \max_{x \in \{0, 1\}^m} \left\{ c^\top x \mid A x \le b \right\} $$ where $A = (u_1, \dotsc, u_m) \in \{ 0, 1 \}^{n \times m}$.

Note: Funny, my next answer to a seemingly unrelated problem is nearly the same.

Community
  • 1
mvw
  • 34,562