Problem 1 (10 pt.) A company wishes to transport fresh products from m factories to warehouses. Supplies at factories are sj, j = 1,...,m, and demands at warehouses are di, i = 1,...,n. The cost of transportation from j to i is c. In addition, the factories need to refrigerate fresh products during transportation. Unit cost of refrigeration is rij on route (i,j). The cost of refrigeration for each factory should not exceed Rj, j=1,...,m. Formulate the LP model to minimize the total cost, i.e., transportation and refrigeration. Derive the dual problem using Lagrangian relaxation and discuss the interpretation of the dual variables.

Fig: 1