• Author / Uploaded
• muhammadtaimoorkhan

Citation preview

Group Members Kazim Shaheen BBA-I Nabeel Saleh BBA-I Naeem Bhatti BBA-I Umair BBA-I Shabir Jan BBA-II Saqib BBA-III Usman Saeed BBA-III

Linear Programming • LP Models – Linear OF and Constraints • Programming refers to modeling and solving a problem mathematically. • Helps management to decide how to make the most effective use of an organization’s resources. • Resources - machinery, labor, money, time, warehouse space, raw material and energy .

In LP The

term

linear

describes

the

proportionate relationship

of two or more variables. Thus, a given change in one variable will always cause a resulting proportional change in another variable.

LP • LP - step-by-step iterative process. • Each step – improve the solution until the "best answer“ or • No feasible answer exists.

Mathematical Modeling OR Formulation

Components of Model • Three Basic Components – Decision Variables – Objective Function – Constraints

Objectives • Maximize – Profit, Return Rate and Reliability. • Minimize – Cost, Loss, energy Consumption

Format of Model • Maximize/Minimize (Objective Function ) Subject to Constraints (equalities,inequalities)

Constraints 1. Limitations of Funds 2. quantity of raw materials available, 3. the level of demand for the products, 4. the equipment productive Capacity

Time Period A further element is the time period being used. The duration may be either long term or short term. Although time is an important element, it is one that has flexibility so that the time horizon may be changed as long as the restrictions are compatible with the periods under consideration.

Non Negative Constraints • Some elements which will remain non negative. e.g – Cricket Stadium – Buses in transport – Furniture ( Like Chairs) etc.

Feasible Solution • Any solution that satisfy all the constraints of the model constitute a feasible solution.

Example 1 • The Decent China Company produces two products daily; plates and mugs. The company has limited amounts of two resources used in the production of these products. i.e. clay and labor. Given these limited resources, the company desires to know how many plates and mugs are required to produce each day, in order to Maximize the profit

Cont… Products Labor Clay Hrs/unit lbs/unit

Profit Rs / unit

Plates

1

4

4

Mugs

2

3

5

Maximum 40 hours of labor and 120 pounds of clay available each day for production

Decision Variables Let

X1 = the number of plates to produce   X2 = the number of mugs to produce

Objective Function Total profit, Z, can be expressed as

  Maximize Z = 4X1 + 5X2

Model Constraints • 1X1 + 2X2 < 40 hours • 4X1 + 3X2 < 120 pounds

Non Negative Constraints A final restriction is that the number of plates and mugs produced be either zero or a positive value, since it would be impossible to produce negative items. These restrictions are referred to as nonnegative constraints and are expressed mathematically as   X1 > 0, X2 > 0

Final Model The complete LP model for this problem will be Maximize Z = 4X1 + 5X2 subject to 1X1 + 2X2 < 40 4X1 + 3X2 < 120 X1, X2 > 0

Solution X1 X2

= 24 plates = 8 mugs and profit Z = Rs. 136.

Example 2 • The Reddy Mikks Company produces both interior and exterior paints from two raw materials, M1and M2. The following table provides the basic data of the problem: Tons of raw mat./ ton of Exterior paint Interior paint R.Mat. M1

6

4

Max. daliy avalblty(tons) 24

R. Mat. M2

1

2

6

Prft/ton ($1000)

5

4

Example2 Cont… A market survey indicates that the daily demand for interior paint cannot exceed that of exterior paint by more than one 1 ton. Also the maximum daily demand of interior paint is 2 tons. Reddy Mikks wants to determine the optimum product mix of interior and exterior paints that maximizes the total daily profit.

Example2

Cont…

Construction of model 1.

Decision Variables

Let • X1 =Tons produced daily of Exterior paint • X2 = Tons produced daily of Interior paint

Example2

Cont…

1. Objective Function Maximize the profit Z = 5 x1 + 4 x2 Where 5 x1 = profit produced by exterior paint. 4 x2 = profit produced by interior paint.

Example2

Cont…

1. Constraints Usage of raw material by both paints = 0

Example 5 • Power Plus-electrical manufac. Comp. producing three kinds of electrical appliances, which require four different processes. The man-hour requirements are: Product

Man-hour spent on Metal Fitting Electric Finishin Work al g Refrigerator 0.2 0.5 0.3 0.3 Washing 0.4 0.6 0.6 0.1 Machine Air 0.2 0.5 0.5 0.2 Conditioner

Example 5 Cont… • In any one-day, there are 60 man-hours available in the metal work station, 125 man-hours in the fitting section, 132 manhours available in the electrical section and 30 man-hours in the finishing section. Power Plus gets Rs 700 profit on each refrigerator, Rs 800 on each washing machine and Rs. 400 on each air conditioner. Read the problem carefully and formulate it as an LP model for maximizing profit.

Giapetto’s Woodcarving • GWC Inc. manufactures two types of wooden toys: soldiers and trains. A soldier sells for 27$ and uses 10$ worth of raw materials. Each soldier that is manufactured increases Giapetto’s variable labor and overhead costs by 14$. A train sells for 21$ and uses 9$ worth of raw materials. Each train built increases Giapetto’s variable labor and overhead costs by 10$. GWC requires two types of skilled labor: Carpentry and Finishing.

Giapetto’s Woodcarving Cont… • A soldiers requires two hours of finishing labor and 1 hour of carpentry labor. A train requires 1 hour of finishing and 1 hour of carpentry labor. Each week, Giapetto can obtain all the needed raw materials but only 100 finishing hour and 80 carpentry hours. Demand for trains is unlimited, but atmost 40 soldiers are bought each week. Giapetto wants to maximize weekly profit. Formulate a model of Giapetto’s situation that can be used to max. Giapetto’s weekly profit.

Giapetto’s Woodcarving Cont… • Since, Profit = revenue – cost • Profit of One soldier: – Soldier’s revenue/unit = 27$ – Spldier’s worth R. mat/unit= 10$ – Labor & overhead cost/unit= 14$ • Total cost/unit = 10 + 14 = 24 $

• Profit of soldier/unit = 27 – 24 = 3 $ • Profit of train/unit =21 – (9 + 10) = 2 $

Giapetto’s Woodcarving Cont… • Decision Variable X1 = No. of soldiers produced/week X2 = No. of trains produced/week

• Objective Function Z = 3X1 + 2X2

Giapetto’s Woodcarving Cont… • Constraints 2 X1 + X2 = 60 – After adding excess variables: X1 + X2 - e1 = 40 and 2 X1 + X2 - e2 = 60 – Where e1 and e2 are excess variables and nonnegative. i.e e1, e2 >= 0

An example of standard form • Max z = 20 x1 +15 x2 s.t. X1 = 0 Which is a standard form.

Basic Solution to Linear System Cont… • Non basic variables : NBV n – m variables, which are arbitrarily chosen as zero, called NBV

• Basic variables : BV Remaining m variables( which are determined by solving simultaneous equations) are called BV.

Optimality and Feasibility Conditions Cont… • Feasibility Condition – For both the max. and min. problems, the leaving variable is the basic variable associated with the smallest non-negative ratio (with strictly positive denominator) – Ties are broken arbitrarily.

The Simplex Algorithm 1) Convert the LP to standard form and then into tableau form. 2) Find the starting basic feasible solution. 3) Determine whether the current bfs is optimal(using optimality condition select an entering variable). Stop, if there is no entering variable; last solution is optimal. 4) Select a leaving variable using the feasibility condition. 5) Determine the new basic solution by using appropriate Gauss-Jordan computations. 6) Go To step 3.

Example: Simplex Algorithm • Reddy Mikks Paints: Interior and Exterior • Maximize Z = 5x1 + 4x2 Subject to 6x1 + 4x2