Difference between revisions of "Walther MA279 Spring2016 topic11" - Rhea

Revision as of 12:22, 22 April 2016

Introduction

The allocation of scarce resources is a universal issue, and the goal is usually to do so in an optimal way. The ability to transport goods at an optimal cost is of particular interest to both businesses and individuals. Linear programming is a method of allocating resources in an optimal way; and it is one of the most widely used tools for decision making in manufacturing industries.

In the term linear programming, programming refers to mathematical programming. In this context, it refers to a process which allocates resources in the best possible (optimal) way; to minimize costs or to maximize profits. In linear programming, the resources to be allocated are known as decision variables. The criterion for choosing the best values of the decision variables is known as the objective function. Restrictions on the availability of resources form what is known as a constraint set.

The word linear indicates that the criteria for choosing optimal values of the decision variables can be described by a linear function of these variables; i.e., a function involving only the first powers of the decision variables, and no products of the variables. Thus the entire problem can be expressed in terms of straight lines, planes, or similar geometric figures. In addition to the linear requirements, there is a restriction of non-negativity; i.e., it is impossible to have negative resources.

One of the most important applications of linear programming has been in the physical distribution of products, commonly referred to as transportation problems. Essentially, the purpose is to minimize the cost of shipping goods from one location to another in such a way that the needs of each destination is met and each shipping location operates within its capacity.

History

Formulation & Mathematical Model of a Transportation Problem

The best way to go about understanding the mathematics behind the transportation problem is to think of a real-life example. Let’s say a clothing company has m warehouses, where the goods are produced. The company also has n outlet stores, where the goods will be sold. We know there exist m warehouses and n outlet stores, but we need to explicitly label each one. We label the warehouses as:

$ i=1,2,...,m $

And we label the outlet stores as:

$ j = 1, 2, ... , n $

Now this is where Supply and Demand come into play. The warehouses have a level of supply and the outlet stores have a level of demand that need to be met. We can define the supply of each warehouse as $ a_i $ and the demand of each outlet store as $ b_j $. Now, the question is what are we trying to calculate? In simplest terms, the transportation problem is an optimization problem. In our case, we want to get good from the warehouses to the outlet stores at minimum cost. Knowing this, and assuming that the cost of shipping is linear, we can define shipping cost from the i^th warehouse to the j^th outlet store as $ c_{ij} $. The last thing that needs to be defined is the number of units transported from the i^th warehouse to the j^th, which we can call $ x_{ij} $. Now, we have all of the terms we'll need to begin solving the problem.

A quick recap of what is written above:

• m and n are defined as the number of sources and the number of destinations, respectively (warehouses and outlet stores in our example)
• The goods produced at the i^th source is defined as $ a_i $
• The demand at the j^th destination is defined as $ b_j $
• $ c_{ij} $ is defined as the shipping cost when being shipped from i to j
• $ x_{ij} $ is defined as the number of units being shipped from source i to destination j

Note: $ x_{ij}\geq 0 $; you can’t have a negative number of units.

Now we need to ask, what do we do with all of these terms? The initial setup of the problem is actually fairly easy. Say, for example, we want to transport 2 shipments of 5 shirts from our warehouses to 2 outlet stores, where one shipment goes to one outlet store, and it costs $1 to ship each shirt. We know that it costs a total of $5 dollar per shipment (cost of shipment x number of units) and there are 2 shipments, so summing them, it’s $10 total. Fairly simple. Expressed mathematically, we can use sums to give ourselves a formula:

$ \sum_{i=1}^m \sum_{j=1}^n c_{ij}x_{ij} $

The goal is to minimize this equation. However, there are some constraints that exist. Let’s say the warehouse is again shipping 2 shipments of 5 shirts. However, the warehouse only has 8 shirts in-house. Can the warehouse ship its required 10 shirts? The obvious answer is no, since they only have 8 shirts available. So the first constraint is that units being shipped cannot exceed the supply available. Mathematically, this can be expressed as:

$ \sum_{j=1}^n x_{ij}\leq a_i; i=1,2,...,m $

There is a similar constraint for demand demand. However, the problem with the demand is not overselling products you don’t have. Instead, the issue is not having enough supply to meet the demand. This can be expressed as:

$ \sum_{i=1}^m x_{ij}\geq b_j; j=1,2,...,n $

To summarize, we want to minimize

$ \sum_{i=1}^m \sum_{j=1}^n c_{ij}x_{ij} $

With the constraints:

$ \sum_{j=1}^n x_{ij}\leq a_i; i=1,2,...,m $

$ \sum_{i=1}^m x_{ij}\geq b_j; j=1,2,...,n $

$ x_{ij}\geq 0, \forall i \in {1,2,...,m}, j \in {1,2,...,n} $

A conclusion we can draw from the information above is that the only way that the problem makes sense is if the supply exceeds or equals the demand. Otherwise the constraints would not be met, namely supply would not meet demand. Knowing that supply must equal or exceed demand, it’s safe to assume that any surplus can be ignored. Thus we can state the following: $ \sum_{j=1}^n = \sum_{i=1}^m b_j Which says that total supply and total demand should be equal. == Real Life Applications == == Example == == Conclusion == $