Contois Carpets is a small manufacturer of carpeting for home and office installations. Production capacity, demand, production cost per square yard (in dollars), and inventory holding cost per square yard (in dollars) for the next four quarters are shown in the network diagram below.

A network diagram between 10 nodes is shown. The left-hand side of the graph shows the "Production Nodes" and list Beginning Inventory, Quarter 1 Production, Quarter 2 Production, Quarter 3 Production, and Quarter 4 Production; these nodes are assigned the numbers, 1, 2, 3, 4, and 5 respectively. The right-hand side of the graph shows "Demand Nodes" and list Quarter 1 Demand, Quarter 2 Demand, Quarter 3 Demand, Quarter 4 Demand, and Ending Inventory; these nodes are assigned the numbers, 6, 7, 8, 9, and 10 respectively. Each production node is assigned a "Production Capacity" value and each demand node is assigned a "Demand" value as follows.

1. Beginning Inventory: 50
2. Quarter 1 Production: 600
3. Quarter 2 Production: 300
4. Quarter 3 Production: 500
5. Quarter 4 Production: 400

6. Quarter 1 Demand: 400
7. Quarter 2 Demand: 500
8. Quarter 3 Demand: 400
9. Quarter 4 Demand: 400
10. Ending Inventory: 100

The arcs connecting production nodes to demand nodes are called "Production (arcs)," and are each assigned a "Production Cost Per Square Yard" value. The arcs connecting demand nodes to demand nodes are each assigned an "Inventory Cost per Square Yard" value. The following list contains each arc and the value associated.

• Beginning Inventory Quarter 1 Demand: 0
• Quarter 1 Production Quarter 1 Demand: 2
• Quarter 2 Production Quarter 2 Demand: 5
• Quarter 3 Production Quarter 3 Demand: 3
• Quarter 4 Production Quarter 4 Demand: 3

• Quarter 1 Demand Quarter 2 Demand: 0.25
• Quarter 2 Demand Quarter 3 Demand: 0.25
• Quarter 3 Demand Quarter 4 Demand: 0.25
• Quarter 4 Demand Ending Inventory: 0.25

Develop a linear programming model to minimize cost. (Let

x_ij

be the number of square yards of carpet which flows from node i to node j.)

Min

s.t.

Beginning Inventory Flow:

Quarter 1 Production Flow:

Quarter 2 Production Flow:

Quarter 3 Production Flow:

Quarter 4 Production Flow:

Quarter 1 Demand Flow:

Quarter 2 Demand Flow:

Quarter 3 Demand Flow:

Quarter 4 Demand Flow:

Ending Inventory Flow:

x_ij 0 for all i, j.

Solve the linear program to find the optimal solution (in dollars).

(x₁₆, x₂₆, x₃₇, x₄₈, x₅₉, x₆₇, x₇₈, x₈₉, x₉₁₀) = (---) with cost $ .