Question

Suppose that we have 2 factories and 3 warehouses. Factory I makes 40 widgets. Factory II makes 50 widgets. Warehouse A stores 15 widgets. Warehouse B stores 45 widgets. Warehouse C stores 30 widgets. It costs \(\$ 80\) to ship one widget from Factory I to warehouse A, \(\$ 75\) to ship one widget from Factory \(\mathrm{I}\) to warehouse \(\mathrm{B}, \$ 60\) to ship one widget from Factory I to warehouse C, \(\$ 65\) per widget to ship from Factory II to warehouse A, \(\$ 70\) per widget to ship from Factory II to warehouse \(\mathrm{B}\), and \(\$ 75\) per widget to ship from Factory II to warehouse \(\mathrm{C}\). 1) Set up the linear programming problem to find the shipping pattern which minimizes the total cost. 2) Find a feasible (but not necessarily optimal) solution to the problem of finding a shipping pattern using the Northwest Corner Algorithm. 3) Use the Minimum Cell Method to find a feasible solution to the shipping problem.

Short answer

In this linear programming problem, we aim to minimize shipping costs between two factories and three warehouses, considering production and storage constraints. After defining the variables \(x_1, x_2, x_3, y_1, y_2, y_3\) to represent the number of widgets transported between factories and warehouses, we form the objective function \(Z = 80x_1 + 75x_2 + 60x_3 + 65y_1 + 70y_2 + 75y_3\). We then establish constraints based on factory output and warehouse capacities as well as non-negativity constraints. For feasible solutions, we employ the Northwest Corner Algorithm, which starts at the top-left cell and allocates widgets based on capacity and demand, and the Minimum Cell Method, which identifies the cell with the minimum cost in the transportation table and assigns as many widgets as possible. Online tools or software can help provide exact numerical solutions using these algorithms.

Step-by-step solution

Define Variables

Let's denote the number of widgets transported from Factory I to warehouse A, B, and C as \(x_1, x_2, x_3\) respectively, and from Factory II to warehouse A, B, and C as \(y_1, y_2, y_3\) respectively.

Objective Function

Our goal is to minimize the total cost. This is represented by the objective function as follows: Minimize \(Z = 80x_1 + 75x_2 + 60x_3 + 65y_1 + 70y_2 + 75y_3\)

Constraints

Based on the information given, the constraints of the problem can be formulated as: 1) Production Constraints(Factory output capacity): Factory I: \(x_1 + x_2 + x_3 \leq 40\) Factory II: \(y_1 + y_2 + y_3 \leq 50\) 2) Storage Constraints(Warehouse capacity): Warehouse A: \(x_1 + y_1 \geq 15\) Warehouse B: \(x_2 + y_2 \geq 45\) Warehouse C: \(x_3 + y_3 \geq 30\) 3) Non-negativity Constraints: All \(x\) and \(y\) must be \(\geq 0\) Phase 2: Feasible Solutions using Northwest Corner Algorithm and Minimum Cell Method

Northwest Corner Algorithm

The steps involved in the Northwest Corner Algorithm are as follows: 1) Start with the top-left cell of the allocation matrix. Allocate as many widgets as possible to that cell, based on the capacity of Factory I and the demand of Warehouse A. Update remaining supply and demand. 2) Proceed to the next cell in the north-to-south then west-to-east direction and repeat the process. Also update remaining supply and demand. 3) The process ends when the total supply from the factories equals the total demand from the warehouses.

Minimum Cell Method

The steps involved in the Minimum Cell Method are: 1) Identify the cell with the minimum cost in the transportation table. 2) Assign as many widgets as possible to that cell without exceeding the supply or demand. Update the remaining supply or demand accordingly. 3) Cross out the row or column of the used-up resource, then, recompute the penalties for each row and column. 4) Move to the next cell with the minimum cost and repeat the process. 5) Stop the process when all the supplies and demands are exhausted. To find the exact numerical answers using the Northwest Corner Algorithm and Minimum Cell Method, use an online tool or software that has capabilities to solve integer linear programming problems.

Key concepts

Transportation Problem

Transportation problems are a specific type of linear programming issue. They focus on optimizing the logistics of distributing products from multiple sources to various destinations. Imagine you have factories producing goods and warehouses storing them before they hit the market.
This type of problem helps determine the most cost-effective way to transport goods to meet demands without exceeding the production capacity of each factory. In our scenario, two factories must ship widgets to three warehouses, each with distinct storage needs and shipping costs.
Transportation problems aim to minimize costs while ensuring every warehouse receives enough widgets, and no factory overproduces.

Objective Function

The objective function in a transportation problem represents the goal of minimizing total costs. In linear programming, the objective function is usually expressed as a linear equation.
Consider the function: \[ Z = 80x_1 + 75x_2 + 60x_3 + 65y_1 + 70y_2 + 75y_3 \] Here, each term represents the shipping cost per widget from a specific factory to a warehouse. Our mission is to reduce the overall shipping expenses by choosing how many widgets to send from each factory to each warehouse.
Solving the objective function by finding the values of the variables \(x_1, x_2, x_3, y_1, y_2, y_3\) minimally fulfills the condition of minimal costs across all transport routes.

Constraints

Constraints in linear programming define the limits within which solutions must work. For transportation problems, they ensure all demands and supplies are addressed correctly.
We distinguish between two types of key constraints:

• Factory Output Constraints: These constraints make sure no factory sends more widgets than it can produce. For Factory I, the sum of all shipments must be less than or equal to 40 widgets.
• Warehouse Storage Constraints: These constraints verify that each warehouse receives the required amount of widgets. For instance, Warehouse A must store at least 15 widgets.

Additionally, we have non-negativity constraints, ensuring shipments (\(x\) and \(y\)) cannot be negative. All constraints together guide the feasible solutions.

Northwest Corner Algorithm

The Northwest Corner Algorithm provides an easy way to find an initial solution to the transportation problem. Begin at the top-left corner of a supply-demand matrix (think of this as northwest) and assign widgets to meet the warehouse's demand or exhaust the factory's supply.
Follow these steps:

• Start at the top-left of the matrix and fill as much as possible in that cell.
• Adjust the demand and supply, then move either down or right until values are zeroed out in a column or row.
• Continue this process until the entire matrix is allocated without exceeding any limits.

This approach doesn't ensure the lowest cost solution but gives a feasible starting point for refinement.

Minimum Cell Method

The Minimum Cell Method is another technique for finding feasible shipments. It prioritizes the least expensive shipping options first, helping to further optimize cost.
Procedure:

• Identify the smallest cost cell not yet used and allocate widgets up to the remaining capacity or demand.
• Update the capacity or demand, disabling any rows or columns fully utilized.
• Repeat for the next least expensive cell.

By favoring the cheapest options first, this method tends to lead to a more economical initial solution than the Northwest Corner Method, often getting closer to the ultimate minimum cost setup.