Rice as a staple food consumed by almost all Indonesia people every day, an adequate supply of rice is needed to meet the needs of the community. Perum Bulog as a government company engaged in food distribution, one of which is rice, plays an important role in the management of rice food stocks. During the rice distribution process, Perum Bulog Sub Divre Medan incurred transportation costs with a large amount. To solve these problems, companies need to use the right methods. One of the methods that can be used for distribution problems is the transportation method. There are two steps to solving transportation problems: the initial solution and the optimal solution. The initial solution uses the Total Opportunity Cost Matrix-Modified Extremum Difference Method (TOCM-MEDM) and the optimal solution with the MODI method. The purpose of this study is to minimize transportation costs at Perum Bulog Sub Divre Medan.  The results of the study show that the use of TOCM-MEDM costs Rp. 151. 103,050 and after the optimization test with MODI it was reduced to Rp. 141,635,000 so that the company could save transportation costs up to 9%, from the initial cost of Rp. 154,847,000 to Rp. 141,635,000. In short, by using the Total Opportunity Cost Matrix-Modified Extremum Difference Method (TOCM-MEDM), the first solution and optimal solution of the MODI Method is the right method to minimize the operational costs of rice distribution in Perum Bulog Sub Divre Medan.