Posts Tagged: "Linear Programming"

Initial basic feasible solution of a transportation problem can be obtained by any of the following methods:

1. North–west corner rule

The major advantage of the north–west corner rule method is that it is very simple and easy to apply. Its major disadvantage, however, is that it is not sensitive to costs and consequently yields poor initial solutions. The steps involved in determining an initial solution using north–west corner rule are as follows:

Step1. Write the given transportation problem in tabular form (if not given).

Step2. Go over to the north-west corner of the table. Suppose it is the (i, j)^th cell.

Step3. Allocate min (a_i, b_j) to this cell. If the min (a_i , b_j) = a_i, then the availability of the i^th origin is exhausted and demand at the j^th destination remains as b_j-a_i and the i^th row is deleted from the table. Again if min (a_i, b_j) = b_j, then demand at the j^th destination is fulfilled and the availability at the i^th origin remains to be a_i-b_j and the j^th column is deleted from the table.…

The basic steps of the transportation method are:

1. To set up the transportation table.

2. Examine whether total supply equals total demand. If not, introduce a dummy row/column having all its cost elements as zero and Supply/Demand as the (+ive) difference of supply and demand.

3. To find an initial basic feasible solution. An initial BFS for a TP with m sources and n destinations must include m+n–1 basic variables. This initial solution may or may not be optimal. Thus, the initial solution in the transportation method serves the same purpose as the initial solution in the simplex method. There are a few methods to find the initial solution. The widely used methods for finding a initial solution are:

4. To obtain an optimal solution by making successive improvements to initial basic feasible solution until no further decrease in the transportation cost is possible. An optimal solution is one where there is no other se of transportation routes that will further reduce the total transportation cost. Thus, we have to evaluate each unoccupied cell in the transportation table in terms of an opportunity of reducing total transportation cost.…

Operations Research approach of problem solving

Optimization is the act of obtaining the best result under any given circumstance. In various practical problems we may have to take many technical or managerial decisions at several stages. The ultimate goal of all such decisions is to either maximize the desired benefit or minimize the effort required. We make decisions in our every day life without even noticing them. Decision-making is one of the main activity of a manager or executive. In simple situations decisions are taken simply by common sense, sound judgment and expertise without using any mathematics. But here the decisions we are concerned with are rather complex and heavily loaded with responsibility. Examples of such decision are finding the appropriate product mix when there are large numbers of products with different profit contributions and production requirement or planning public transportation network in a town having its own layout of factories, apartments, blocks etc. Certainly in such situations also decision may be arrived at intuitively from experience and common sense, yet they are more judicious if backed up by mathematical reasoning. The search of a decision may also be done by trial and error but such a search may be cumbersome and costly.…

Transportation problem is a particular class of linear programming, which is associated with day-to-day activities in our real life and mainly deals with logistics. It helps in solving problems on distribution and transportation of resources from one place to another. The goods are transported from a set of sources (e.g., factory) to a set of destinations (e.g., warehouse) to meet the specific requirements. In other words, transportation problems deal with the transportation of a single product manufactured at different plants (supply origins) to a number of different warehouses (demand destinations). The objective is to satisfy the demand at destinations from the supply constraints at the minimum transportation cost possible. To achieve this objective, we must know the quantity of available supplies and the quantities demanded. In addition, we must also know the location, to find the cost of transporting one unit of commodity from the place of origin to the destination. The model is useful for making strategic decisions involved in selecting optimum transportation routes so as to allocate the production of various plants to several warehouses or distribution centers.

Suppose there are more than one centers, called ‘origins’ , from where the goods need to be transported to more than one places called ‘destinations’ and the costs of transporting or shipping from each of the origin to each of the destination being different and known.…

We see that the primal and the dual of linear programming are related mathematically, we can now show that they are also related in economic sense. Consider the economic interpretation of the duality of linear programming — first for a maximisation problem and then for a minimisation problem.

The maximisation problem: Consider the following linear programming problem.

The optimal solution to this problem dives production of 18 units of Xi and 8 units of x2 per week. It yields the maximum prof of a Rs. 1000,

Maximise Z = 40x₁ + 35x₂, Subject to

2x₁ + 3X₂ < or = 60, Raw materials constraint per week.

4x₁ + 3X₂ < or = 96, Capacity constraint per week.

x₁,x₂ > or = 0

The optimal solution to this problem gives production of 18 units of x₁ and 8 units of x₂ per week. It yields the maximum profit of a Rs. 1000.

Now, to rent the facilities of the firm for one week, the firm has 60 kg of raw material and 96 capacity hours. If we let y_l represent the rent per kg of raw material and y₂ the rent per capacity hour, the firm would receive a total rent equal to 6Oy₁ + 96y₂.…