This paper utilizes a linear programming technique in solving the transportation problem of a beverage producing company in Nigeria with a view to minimizing the total transportation cost and obtaining an optimal schedule bearing in mind the present transportation policy of the company. This work became necessary because it was discovered that the transportation costing policies of the company under study were not based on results obtained from sophisticated mathematical modeling but from rule-of-thumb methods. Transportation cost data from the peak period in the year under study were analyzed and linear programming methods were employed in finding the routes that will optimize total transportation cost of the company. From the company’s data, two transportation matrices were formulated and analyzed with optimal solutions of N 8,889,000 and N 13,989,000 giving a cost reduction of N 6,363,586 and N 1,263,586 respectively when compared with the company’s present transportation cost of N 15,252,586. On the basis of this finding, this paper recommends that the company employs this model in making its policies.