I believe this is a linear algebra problem, but if not please let me know:

Say you have 4 suppliers. You want to order 4 different items. The 4 suppliers each have a different price for each item and charge shipping but only for orders under a given amount. How do you decide what to order from each supplier to get the lowest total cost including shipping?

Here is a Table of Sample Data. I need to buy all 4 items. I don't have to buy all the supplies from a single supplier.

          Supplier A    Supplier B    Supplier C     Supplier D
Item 1     $30             $40          $50             $60
Item 2     $40             $50          $60             $35
Item 3     $45             $60          $60             $65
Item 4     $90             $55          $35             $45
Shipping   $25             $20          $15             $10

Each Supplier offers free shipping for orders over $100

I tried each option and found a solution, but I'd like a way for a computer to answer the question so I can scale this to many items and many suppliers.

  • $\begingroup$ This is not a linear programming problem, since the cost is not a linear function of quantity ordered. Looks like a hard algorithmic problem similar to knapsack. $\endgroup$ – user147263 Dec 14 '14 at 0:45

The first action, which you have to do is to define the indices and the variables.


i: Index for the ith supplier.

$i \in \{1,2,3,4\}$

i=1 stands for supplier A, i=2 stands for supplier B, ...

j: Index for the jth item.

$j \in \{1,2,3,4\}$


$x_{ij}$: Amount of items j, which are bought at supplier i.

$x_{ij} \in \mathbb N_0$

$y_i$: $\begin{cases} 1, \text{if} \ c_i \leq 100 \\ 0, \text{if} \ c_i > 100 \end{cases}$

$c_i$: Costs of all items, which are bought at supplier i.


$t_i$: Shipping costs of supplier i.

$p_{ij}$: price of item j from supplier j.


An amount of $b_j$ items of category j have to be bought at least.

$\sum_{i=1}^4 x_{ij}\geq b_j \ \ \forall \ j$

Costs of the items, which are bought at supplier i

$\sum_{j=1}^4 p_{ij}\cdot x_{ij}=c_i \ \ \forall \ i$

objective function

The shipping costs are

$\sum_{i=1}^4 y_i\cdot t_ i$

The costs for the items are

$\sum_{i=1}^4 \sum_{i=1}^4 p_{ij}\cdot x_{ij}$


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.