Linear Programming

1. Transportation Problem: Optimal Shipping Plan

A logistics company supplies goods from three warehouses (W1, W2, W3) to four retail stores (S1, S2, S3, S4). The transportation cost per unit from each warehouse to each store is given in the table below. Each warehouse has a limited supply, and each store has a demand requirement. The goal is to minimize the total transportation cost.

To / From	S1	S2	S3	S4	Supply
W1	4	3	6	5	250
W2	2	5	3	4	300
W3	7	6	4	3	400
Demand	200	200	250	300	-

Decision Variables

Let \(x_{ij}\) be the number of units transported from warehouse \(iii\) to store \(j\).

Objective Function

Minimize total transportation cost:

\(Z = 4x_{11} + 3x_{12} + 6x_{13} + 5x_{14} + 2x_{21} + 5x_{22} + 3x_{23} + 4x_{24} + 7x_{31} + 6x_{32} + 4x_{33} + 3x_{34}\)

Constraints

Supply Constraints

• \(x_{11} + x_{12} + x_{13} + x_{14} \leq 250 \quad \text{(Warehouse W1)}\)
• \(x_{21} + x_{22} + x_{23} + x_{24} \leq 300 \quad \text{(Warehouse W2)}\)
• \(x_{31} + x_{32} + x_{33} + x_{34} \leq 400 \quad \text{(Warehouse W3)}\)

Demand Constraints

• \(x_{11} + x_{21} + x_{31} = 200 \quad \text{(Store S1)}\)
• \(x_{12} + x_{22} + x_{32} = 200 \quad \text{(Store S2)}\)
• \(x_{13} + x_{23} + x_{33} = 250 \quad \text{(Store S3)}\)
• \(x_{14} + x_{24} + x_{34} = 300 \quad \text{(Store S4)}\)

Non-Negativity Constraints: \(x_{ij} \geq 0 \quad \text{for all } i, j\)

Answer

from scipy.optimize import linprog

# Cost coefficients
c_transport = [4, 3, 6, 5, 2, 5, 3, 4, 7, 6, 4, 3]  

A_transport = [  # Coefficients for constraints (Supply + Demand)
    [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],  # W1 supply
    [0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0],  # W2 supply
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1],  # W3 supply
    [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0],  # S1 demand
    [0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0],  # S2 demand
    [0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0],  # S3 demand
    [0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],  # S4 demand
]

b_transport = [250, 300, 400, 200, 200, 250, 300]  # Supply & Demand constraints
bounds_transport = [(0, None)] * 12  # Non-negativity

res_transport = linprog(
    c_transport, 
    A_ub = A_transport[:3], 
    b_ub = b_transport[:3], 
    A_eq = A_transport[3:], 
    b_eq = b_transport[3:], 
    bounds = bounds_transport, 
    method='highs')
res_transport

        message: Optimization terminated successfully. (HiGHS Status 7: Optimal)
        success: True
         status: 0
            fun: 2850.0
              x: [ 5.000e+01  2.000e+02  0.000e+00  0.000e+00  1.500e+02
                   0.000e+00  1.500e+02  0.000e+00  0.000e+00  0.000e+00
                   1.000e+02  3.000e+02]
            nit: 6
          lower:  residual: [ 5.000e+01  2.000e+02  0.000e+00  0.000e+00
                              1.500e+02  0.000e+00  1.500e+02  0.000e+00
                              0.000e+00  0.000e+00  1.000e+02  3.000e+02]
                 marginals: [ 0.000e+00  0.000e+00  1.000e+00  1.000e+00
                              0.000e+00  4.000e+00  0.000e+00  2.000e+00
                              4.000e+00  4.000e+00  0.000e+00  0.000e+00]
          upper:  residual: [       inf        inf        inf        inf
                                    inf        inf        inf        inf
                                    inf        inf        inf        inf]
                 marginals: [ 0.000e+00  0.000e+00  0.000e+00  0.000e+00
                              0.000e+00  0.000e+00  0.000e+00  0.000e+00
                              0.000e+00  0.000e+00  0.000e+00  0.000e+00]
          eqlin:  residual: [ 0.000e+00  0.000e+00  0.000e+00  0.000e+00]
                 marginals: [ 4.000e+00  3.000e+00  5.000e+00  4.000e+00]
        ineqlin:  residual: [ 0.000e+00  0.000e+00  0.000e+00]
                 marginals: [-0.000e+00 -2.000e+00 -1.000e+00]
 mip_node_count: 0
 mip_dual_bound: 0.0
        mip_gap: 0.0

Interpretation

• The minimum total transportation cost is $2,850.

• Optimal shipment plan:

  • From W1 to S1: 50 units
    
  • From W1 to S2: 200 units
    
  • From W1 to S3 & S4: 0 units
    
  • From W2 to S1: 150 units
    
  • From W2 to S2: 0 units
    
  • From W2 to S3: 150 units
    
  • From W2 to S4: 0 units
    
  • From W3 to S1 & S2: 0 units
    
  • From W3 to S3: 100 units
    
  • From W3 to S4: 300 units

• Shadow prices (dual values) for demand constraints:

  • S1 = $4, meaning if demand at S1 increases by 1 unit, total cost increases by $4.
  • S2 = $3, meaning an extra unit at S2 increases cost by $3.
  • S3 = $5, meaning an extra unit at S3 increases cost by $5.
  • S4 = $4, meaning an extra unit at S4 increases cost by $4.

• Marginals

  • W1 = $0, meaning increasing W1’s supply doesn’t impact cost.
  • W2 = -$2, meaning if W2’s supply increased, costs could reduce by $2 per unit.
  • W3 = -$1, meaning if W3’s supply increased, costs could reduce by $1 per unit.

2. Manufacturing Problem: Maximizing Profit (Product Mix)

A company produces two types of products (A and B) using two machines (M1 and M2). The processing time (in hours per unit) and the profit per unit are given below. The company has a limited number of available hours for each machine. The objective is to maximize profit.

Product	M1 Hours per unit	M2 Hours per unit	Profit per unit ($)
A	3	2	50
B	5	4	80

• Machine M1 has 600 hours available.
  
• Machine M2 has 500 hours available.

Decision Variables

Let \(x_1\) be the number of units of product A produced.
Let \(x_2\) be the number of units of product B produced.

Objective Function

Maximize profit: \(Z = 50x_1 + 80x_2\)

Constraints

Machine Time Constraints

• \(3x_1 + 5x_2 \leq 600 \quad \text{(M1 capacity)}\)
• \(2x_1 + 4x_2 \leq 500 \quad \text{(M2 capacity)}\)

Non-Negativity Constraints: \(x_1, x_2 \geq 0\)

Answer

c_profit = [-50, -80]  # Coefficients (negative for maximization)

A_profit = [  # Machine constraints
    [3, 5],   # M1 constraint
    [2, 4],   # M2 constraint
]

b_profit = [600, 500]  # Available hours
bounds_profit = [(0, None), (0, None)]  # Non-negativity

res_profit = linprog(
    c_profit, 
    A_ub = A_profit, 
    b_ub = b_profit, 
    bounds = bounds_profit, 
    method='highs')

res_profit

        message: Optimization terminated successfully. (HiGHS Status 7: Optimal)
        success: True
         status: 0
            fun: -10000.0
              x: [ 2.000e+02  0.000e+00]
            nit: 1
          lower:  residual: [ 2.000e+02  0.000e+00]
                 marginals: [ 0.000e+00  3.333e+00]
          upper:  residual: [       inf        inf]
                 marginals: [ 0.000e+00  0.000e+00]
          eqlin:  residual: []
                 marginals: []
        ineqlin:  residual: [ 0.000e+00  1.000e+02]
                 marginals: [-1.667e+01 -0.000e+00]
 mip_node_count: 0
 mip_dual_bound: 0.0
        mip_gap: 0.0

Interpretation

• Maximum Profit: $10,000.0

• Optimal production quantities:

200.0 units of Product A and 0.0 units of Product B

• Remaining capacities after allocating resources:

Machine M1: Residual = 0.0 (Fully utilized) Machine M2: Residual = 100.0 (Unused)

• Shadow price (dual value):

Machine M1 = 16.67, meaning that if we had one more hour of M1, the profit would increase by 16.67. Machine M2 = 0.0, meaning extra hours for M2 won’t increase profit

3. Manufacturing Problem: Minimizing Production Cost

A furniture company manufactures chairs and tables. The company has limited resources of wood and labor and wants to minimize the total production cost.

Product	Wood Required (cubic ft.)	Labor Required (hours)	Cost per unit ($)
Chair	5	2	30
Table	8	3	50

• Available wood: 800 cubic feet
  
• Available labor: 300 hours

Decision Variables

Let \(x_1\) be the number of chairs produced.
Let \(x_2\) be the number of tables produced.

Objective Function

Minimize cost: \(Z = 30x_1 + 50x_2\)

Constraints:

• \(5x_1 + 8x_2 \leq 800 \quad \text{(Wood availability)}\)
• \(2x_1 + 3x_2 \leq 300 \quad \text{(Labor availability)}\)

Non-Negativity Constraints: \(x_1, x_2 \geq 0\)

Answer

c_cost = [30, 50]  # Cost coefficients

A_cost = [  # Resource constraints
    [5, 8],  # Wood constraint
    [2, 3],  # Labor constraint
]

b_cost = [800, 300]  # Available resources
bounds_cost = [(0, None), (0, None)]  # Non-negativity

res_cost = linprog(
    c_cost, 
    A_ub = A_cost, 
    b_ub = b_cost, 
    bounds = bounds_cost, 
    method = 'highs')

res_cost

       message: Optimization terminated successfully. (HiGHS Status 7: Optimal)
       success: True
        status: 0
           fun: 0.0
             x: [ 0.000e+00  0.000e+00]
           nit: 0
         lower:  residual: [ 0.000e+00  0.000e+00]
                marginals: [ 3.000e+01  5.000e+01]
         upper:  residual: [       inf        inf]
                marginals: [ 0.000e+00  0.000e+00]
         eqlin:  residual: []
                marginals: []
       ineqlin:  residual: [ 8.000e+02  3.000e+02]
                marginals: [-0.000e+00 -0.000e+00]

Interpretation

The minimum production cost is $0.0, meaning that the optimal decision is not to produce any chairs or tables.

Optimal production quantities:

• Chairs: 0.0 units
• Tables: 0.0 units
• The company should not produce anything to achieve the lowest cost.

Remaining resources:

• Wood: 800.0 cubic feet unused
• Labor: 300.0 hours unused
• Since no production takes place, all resources remain unused.

Shadow prices for wood and labor are both 0.0, meaning that increasing available resources would not change the optimal solution.

• This suggests that there is no economic incentive to produce chairs or tables under the given cost structure.