2
$\begingroup$

Seven types of chemicals are to be shipped in five trucks. There are three containers storing each type of chemical, and the capacities of the five trucks are 6, 4, 5, 4, and 3 containers, respectively. For security reasons, no truck can carry more than one container of the same chemical. Determine whether it is possible to ship all 21 containers in the five trucks.

$\endgroup$
0
$\begingroup$

Consider a complete bipirtite labeled graph with the five trucks in the first vertices part and the seven chemical types in the second vertices part. Call the labels $x_{i,j}$ for $i=1,\cdots,5$ and $j=1,\cdots,7$. The labels can take values $0$ or $1$ which means the edge is used or not, and being used means there exists one container of the chemical $j$ in the truck $i$. Now the rest of your constrains are $$\begin{array}{l} \sum_{j=1}^7x_{1,j}=6,\\ \sum_{j=1}^7x_{2,j}=4,\\ \sum_{j=1}^7x_{3,j}=5,\\ \sum_{j=1}^7x_{4,j}=4,\\ \sum_{j=1}^7x_{5,j}=3,\\ \sum_{i=1}^5x_{i,j}=3\;;\;\forall 1\leq j\leq 7. \end{array}$$ So you have 35 binary variables and 12 linear equations. Possibility of the task that you asked is equivalent with this system having a solution, furthermore the possible distributions of chemicals to the tracks are exactly determined by the solution set, and you can get the number of possible cases by the cardinal of this set.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Create a source node that has outgoing edges of capacity 3 to each of the 7 "chemical" nodes $C_1,...,C_7$ (as each chemical has 3 containers that must be transported). Create also 5 "truck" nodes $T_1,...,T_5$. For each of chemical nodes, add an outgoing edge of capacity 1 to each of the 5 truck nodes (as each truck can carry at most 1 container of the same chemical). Connect all truck nodes to a sink node with capacities 6, 4, 5, 4, and 3 (as each truck can carry at most so many containers). See below:

enter image description here

Find in this network a maximum flow using the Ford-Fulkerson or Edmonds-Karp algorithm. There are many possible flow assignments which solve this, but one in particular is the following:

  • All 3 containers of chemical 1 go to trucks $T_2, T_3, T_5$
  • All 3 containers of chemical 2 go to trucks $T_1, T_2, T_3$
  • All 3 containers of chemical 3 go to trucks $T_1, T_2, T_3$
  • All 3 containers of chemical 4 go to trucks $T_1, T_2, T_3$
  • All 3 containers of chemical 5 go to trucks $T_1, T_3, T_4$
  • All 3 containers of chemical 6 go to trucks $T_1, T_4, T_5$
  • All 3 containers of chemical 7 go to trucks $T_1, T_4, T_5$

This satisfies the constraints of each truck. $T_1$ carries 6/6 containers, $T_2$ carries 4/4 containers, $T_3$ carries 5/5 containers, $T_4$ carries 3/4 containers, and $T_5$ carries 3/3 containers.

| cite | improve this answer | |
$\endgroup$

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.