The significant increase of fuel consumption in Brazil has brought major challenges to the supply chain in the country. Over the last five years (2009- 2013), the Brazilian market for gasoline and diesel has increased 62.8 percent and 32.0 percent, respectively. However, investments in production and infrastructure have not kept up this growth, increasing the challenges. In the Northeast region of the country, which is supplied largely by coastal shipping, the infrastructure for the petroleum products movement falls short of what is needed bringing several inefficiencies to the supply chain and significantly increasing the costs involved in operations. To assess the supply of this region, a mathematical programming model was proposed which considers all the constraints that directly impact the supply gasoline and diesel, including identifying those constraints that are caused by other actors in the chain, such as insufficient costumer s tankage, draught restriction of ports and high occupancy rates of public ports, raising the cost of demurrage. To complement the analysis, alternative scenarios to allocate the distributor s investments efficiently were evaluated to minimize the costs of the supply chain. The proposed model was also used to discuss the service levels committed by Petrobras in meet the demand for gasoline and diesel at the region. The study had an approach to supply chain oriented for tactical planning, showing as an efficient tool to support decision making.