linear programming problem vehicle

78 Views Asked by At

I have a problem in which there are 4 ships available to transport people from 3 different bases back to a main base.

1.Vehicle 1 has a capacity of 50, can make 6 round trips and is allowed to visit bases 1 and 2.

2.Vehicle 2 has a capacity of 75, can make 4 round trips and is allowed to visit bases 2 and 3.

3.Vehicle 3 has a capacity of 100, can make 4 round trips and is allowed to visit bases 1 and 3.

4.Vehicle 4 has a capacity of 150, can make 2 round trips and is allowed to visit all 3 bases.

There are 350, 400, 350 people to collect from the 3 bases respectively.

1

There are 1 best solutions below

0
On BEST ANSWER

Let $p_b$ be the number of people at base $b$. Let $c_i$ be the capacity of ship $i$.

Let binary decision variable $x_{ijk}$ indicate whether ship $i$ uses route $j$ in trip $k$. Let nonnegative integer decision variable $y_{ijkb}$ be the number of people served at base $b$ on that trip.

The problem is to minimize $\sum_{i,j,k} d_j x_{ijk}$ subject to \begin{align} \sum_{i,j,k} y_{ijkb} &\ge p_b &&\text{for all $b$} \tag1 \\ \sum_b y_{ijkb} &\le c_i x_{ijk} &&\text{for all $i,j,k$} \tag2 \\ \sum_j x_{ijk} &\le 1 &&\text{for all $i,k$} \tag3 \end{align}

Constraint $(1)$ covers all people at base $b$. Constraint $(2)$ enforces both the capacity of ship $i$ and the logical implication $y_{ijkb} > 0 \implies x_{ijk} = 1$. Constraint $(3)$ enforces at most one route per ship and trip.