Linear Programming

Brief History of LP:-

* LP was developed to solve military logistics problems during World War II

* In 1947, George Dantzig developed a solution procedure for solving linear programming problems (Simplex Method)

* This method turned out to be so efficient for solving large problems quickly

* The simultaneous development of the computer technology established LP as an important tool in various fields

* Simplex Method is still the most important solution method for LP problems

* In recent years, a more efficient method for extremely large problems has been developed (Karmarkar’s Algorithm)

LP Problems:-

* A large number of real problems can be formulated and solved using LP. A partial list includes:

* Scheduling of personnel

* Production planning and inventory control

* Assignment problems

* Several varieties of blending problems including ice cream, steel making, crude oil processing

* Distribution and logistics problems

Typical Applications of LP:-

Aggregate Planning

Develop a production schedule which

* satisfies specified sales demands in future periods

* satisfies limitations on production capacity

* minimizes total production/inventory costs

Scheduling Problem

Produce a workforce schedule which

* satisfies minimum staffing requirements

* utilizes reasonable shifts for the workers

* is least costly

Product Mix (“Blending”) Problem

Develop the product mix which

* satisfies restrictions/requirements for customers

* does not exceed capacity and resource constraints

* results in highest profit

Logistics

Determine a distribution system which

* meets customer demand

* minimizes transportation costs

Marketing

Determine the media mix which

* meets a fixed budget

* maximizes advertising effectiveness

* Financial Planning

Establish an investment portfolio which

* meets the total investment...