Integer programs solvable as LP Sommer gentry November 18.2003 Transportation problem Sources and sinks connected by links Objective: Minimize shipment cost 地 pittsburgh Detroit 40 widgets 20 widgets Baltimore Atlant 20 widgets 30 widget Denver 15 widgets 75 widgets S9 50 widgetsInteger programs solvable as LP Sommer Gentry November 18, 2003 Transportation problem • • 50 widgets Baltimore Detroit Atlanta Denver Pittsburgh Boston Houston 20 widgets 30 widgets 75 widgets 40 widgets 20 widgets 15 widgets $9 $7 $4 Sources and sinks connected by links Objective: Minimize shipment cost