Operations Research Linear Programming PDF

OPERATIONS RESEARCH “OR:THE SCIENCE OF BETTER” “Operations Research is the discipline of applying advanced analytical methods to help make better decisions.” Linear Programming: Model Formulation & Graphical Solution...

OPERATIONS RESEARCH “OR:THE SCIENCE OF BETTER” “Operations Research is the discipline of applying advanced analytical methods to help make better decisions.” Linear Programming: Model Formulation & Graphical Solution Dr. Waqar Ahmed Khan 1  Contents What is Linear Programming (LP)? LP Model Assumptions Mathematical Formulation of LP Problems Graphical LP Solutions Classification of LP Problems 2  What is Linear Programming? ▪ First conceived by George B. Dantzig (1947); Dantzig’s first paper was titled “Programming in Linear Structure” ▪ Koopmans Coined the term “Linear Programming” in 1948. ▪ Simplex Method was published in 1949 by Dantzig. ▪ A linear programming problem (LP) is a class of the mathematical programming problem, a constrained optimization problem, for which: We attempt to maximize (or minimize) a linear function of the decision variables. (Objective Function) The values of the decision variables must satisfy a set of constraints, each of which must be a linear George B. Dantzig inequality or linear equality. (1914–2005) A sign restriction on each variable. For each variable 𝑋𝑖 the sign restriction can either say 𝑋𝑖 ≥ 0, 𝑋𝑖 ≤ 0, 𝑋𝑖 unrestricted. LP Model Using Matrix Notation 𝑛 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑜𝑟 𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑍 = 𝑐 𝑇 𝑋 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑜𝑟 𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑍 = ෍ 𝐶𝑖 𝑥𝑖 𝑆𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑖=1 ≤ 𝑆𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝐴𝑋 = 𝑏 ≤ ≥ σ𝑛𝑖=1 𝑎𝑖𝑗 𝑥𝑖 = 𝑏𝑗 𝑓𝑜𝑟 𝑗 = 1,2, … , 𝑚 𝑋≥0 ≥ Where 𝐴 ∈ ℝ𝑚×𝑛 , 𝑐 ∈ ℝ𝑛 , 𝑎𝑛𝑑 𝑏 ∈ ℝ𝑚 𝑥𝑖 ≥ 0 𝑓𝑜𝑟 𝑖 = 1,2, … , 𝑛 Assumption: 𝑚 ≤ 𝑛, 𝑟𝑎𝑛𝑘 𝐴 = 𝑚 3  Assumptions of the LP Model ▪ LINEARITY OR PROPORTIONALITY: Proportionality means that the objective function and constraint coefficients are strictly proportional to the decision variable (e.g., If the first unit of production requires ‘2’ hours of labor so it must the 50th and 100th unit also requires ‘2’ hours of labor). ▪ DIVISIBILITY: Divisibility means that non integer (fractional) values of the decision variables are acceptable. Integer Programming is a special technique which can be used for finding non-fractional values of resource usage and decision variables). ▪ CERTAINTY: Certainty means that the values of the parameters are known and constant ▪ ADDITIVITY: Additivity means the total effect of each decision variable (Profit, Cost, etc.) must equal the sum of the effects contributed by each decision variable and terms of each constraint must be additive (Total amount of resource consumed or provided) must equal the sum of the resources used (or provided) by each decision variable. ▪ NON–NEGATIVITY: Non – negativity means that the decision variables are permitted to have only the values which are greater than or equal to zero. 4  Development (Formulation) of LP Model: Product Mix A firm is engaged in producing two products ‘A’ and ‘B’. Each unit of product ‘A’ requires 3Kg of raw material and 5 labor hour for processing, where as each unit of product ‘B’ requires 6Kg of raw material and 4 labor hours of the same type. Every month the firm has the availability of 60Kg of raw material and 70 Labor hours. One unit of product ‘A’ sold earns profit $30 and one unit of product ‘B’ sold gives $40 as profit. Formulate this problem as linear programming problem to determine as to how many units of each of the products should be produced per month so that the firm can earn maximum profit, assume all unit produced can be sold in the market. Decision Variables: Let X1 and X2 be the number of products ‘A’ and ‘B’ respectively. The Complete LP problem model is: Objective Function: Maximize: Z = 30X1 + 40X2 Maximize Z = 30X1 + 40X2 Subject to: 3X1 + 6X2 ≤ 60 CONSTRAINTS: 5X1 + 4X2 ≤ 70 Material Constraint: 3X1 + 6X2 ≤ 60 X1 , X2 ≥ 0 Labor Constraint: 5X1 + 4X2 ≤ 70 Non–negativity Constraint: X1,X2 ≥ 0. 5  Development (Formulation) of LP Model: Product Mix Decision Variables: → Let X1 & X2 be the number of bowls and mugs produced, respectively. Objective Function: → Maximize: Z = 40X1 + 50X2 LP MODEL:→ Maximize: Z = 40X1 + 50X2 (Profit Function) Constraints: → SUBJECT TO: X1 + 2X2 ≤ 40 (Labor Constraint) X1 + 2X2 ≤ 40 (Labor Constraint) 4X1 + 3X2 ≤ 120 (Clay Constraint) 4X1 + 3X2 ≤ 120 (Clay Constraint) X1, X2 ≥0 (Non–Negativity) X1, X2 ≥ 0 (Non–Negativity)6  Development (Formulation) of LP Model: Product Mix Four varieties of ties produced: i) one is an expensive, all-silk tie, ii) one is an all-polyester tie, and iii) two are blends of polyester and cotton. The table on the following slide illustrates the cost and availability (per monthly production planning period) of the three materials used in the production process ▪ The following table summarizes the contract demand for each of o the four styles of ties, o the selling price per tie, and o the fabric requirements of each variety. Fifth Avenue’s goal is to maximize its monthly profit. It must decide upon a policy for product mix. DECISION VARIABLES: Let X1 = # of all-silk ties; X2 = # polyester ties; X3 = # of blend 1 poly-cotton ties; Subject to: X4 = # of blend 2 poly-cotton ties produced per month 0.125X1 ≤ 800 (Total Silk Availability Constraint) 0.08X2 + 0.05X3 + 0.03X4 ≤ 3,000 (Total Polyester Availability Constraint) Calculate profit for each tie: Profit = Sales price – (Cost per yard * Yards per tie) 0.05X3 + 0.07X4 ≤ 1,600 (Total Cotton Availability Constraint) Silk ties = $6.70 – $21 x 0.125 = $4.08 X1 ≥ 6,000 (Contract Constraint – 1) Polyester = $3.55 – $6 x 0.08 = $3.07 X2 ≥ 10,000 (Contract Constraint – 2) Poly-blend 1 = $4.31 – ($6 x 0.05 + $9 x 0.05) = $3.56 X3 ≥ 13,000 (Contract Constraint – 3) Poly-blend 2 = $4.81 – ($6 x 0.03 + $9 x 0.07) = $4.00 X4 ≥ 6,000 (Contract Constraint – 4) X1 ≤ 7,000 (Demand Constraint – 1) Objective function: maximize profit = $4.08X1 + $3.07X2 + $3.56X3 + $4.00X4 X2 ≤ 14,000 (Demand Constraint – 2) X3 ≤ 16,000 (Demand Constraint – 3) X4 ≤ 8,500 (Demand Constraint – 4) 7 X1, X2, X3, X4 ≥ 0 (Non-Negativity Constraints) Development (Formulation) of LP Model: Product Mix 8  Development of LP Model: Portfolio Selection Problem Mr. Ali has $70, 000 to investment in several alternatives. The alternative investments are national certificates with an 8.5% return, Defense Savings Certificates with a 10% return, NIT with a 6.5% return, and khas deposit with a return of 13%. Each alternative has the same time until maturity. In addition, each investment alternative has a different perceived risk thus creating a desire to diversify. Ali wants to know how much to invest in each alternative in order to maximize the return. The following guidelines have been established for diversifying the investments and lessening the risk; ▪ No more than 20% of the total investment should be in khas deposit. ▪ The amount invested in Defense Savings Certificates should not exceed the amount invested in the other three alternatives. ▪ At least 30% of the investment should be in NIT and Defense Savings Certificates. ▪ The ratio of the amount invested in national certificates to the amount invested in NIT should not exceed one to three. Formulate the problem as a LP model. DECISION VARIABLES: Let X1, X2, X3 & X4 be the amount (Rs.) invested in national certificates, Defense savings certificates, NIT, and khas deposit, respectively. OBJECTIVE FUNCTION: Maximize (the total return from all investment): Z = 0.085X1 + 0.100X2 + 0.065X3 + 0.130X4 LP MODEL:→ CONSTRAINTS: → Maximize Z = 0.085X1 + 0.100X2 + 0.065X3 + 0.130X4 (Investment return Function) X1 + X2 + X3 + X4 = 70,000 (Amount Availability Constraint) SUBJECT TO: X1 + X2 + X3 + X4 = 70,000 (Amount Availability Constraint) X4 ≤ (0.20 x 70,000 = 14,000) (Investment Constraint – i) X4 ≤ 14,000 (Investment Constraint – i) X2 ≤ (X1 + X3 + X4) ➔ X2 – X1 – X3 – X4 ≤ 0 (Investment Constraint – ii) X2 – X1 – X3 – X4 ≤ 0 (Investment Constraint – ii) X2 + X3 ≥ (0.30 x 70,000 = 21, 000) (Investment Constraint – iii) X2 + X3 ≥ 21, 000 (Investment Constraint – iii) (X1) / (X3) ≤ 1/3 ➔ 3X1 – X3 ≤ 0 (Investment Constraint – iv) 3X1 – X3 ≤ 0 (Investment Constraint – iv) X1, X2, X3 , X4 ≥ 0 (Non–Negativity Constraint) X1, X2, X3, X4 ≥ 0 (Non – Negativity Constraint) 9  Development of LP Model: Resource Allocation Problem ▪ All allocation models have in common that they attempt to allocate a scarce resource so as to optimize the consequence of that allocation. o The “Product Mix Problem” is a special case of the resource allocation problem o An agricultural allocation problem Amount of farmland that is devoted to the 𝑖 𝑡ℎ activity; maximize profit o A portfolio selection problem o the investor selecting the optimal portfolio from a set of possible portfolios Indices: 𝑛 ▪ 𝑖 = 1…𝑛 Activities (Products) ▪ 𝑗 = 1…𝑚 Resources (Machines) 𝑴𝒂𝒙𝒊𝒎𝒊𝒛𝒆 Prof𝑖𝑡 = ෍ 𝑝𝑖 𝑥𝑖 Parameters: 𝑖=1 ▪ 𝑝𝑖 = Profit for activity ‘𝑖’ Subject to: ▪ 𝑏𝑗 = Amount available of resource ‘𝑗’ 𝑛 ▪ 𝑎𝑖𝑗 = Amount of resource ‘𝑗’ used by a unit of activity ‘𝑖’ ෍ 𝑎𝑖𝑗 𝑥𝑖 ≤ 𝑏𝑗 𝑓𝑜𝑟 𝑗 = 1,2,... , 𝑚 𝑖=1 Decision Variables: 𝑥𝑖 ≥ 0 𝑓𝑜𝑟 𝑖 = 1,2,... , 𝑛 𝑥𝑖 = Amount of activity ‘𝑖’ selected 10  Development (Formulation) of LP Model: Production Planning Let us consider a company making a single product. The estimated demand for the product for the next four months are 1000, 800, 1200, 900 respectively. The company has a regular time capacity of 800 per month and an over time capacity of 200 per month. The cost of regular time production is $20 per unit and the cost of over time production is $25 per unit. The company can carry inventory to the next month and the holding cost is $3 per unit per month. The demand has to be met every month. Formulate linear programming problem for the above situation. Decision Variables: ▪ Let Rt = Quantity Produced Using Regular time in month ‘t’ ➔ t = 1, 2, 3, 4 ▪ Let Ot = Quantity Produced Using Over time in month ‘t’ ➔ t = 1, 2, 3, 4 ▪ Let It = Quantity Carried at the end of month ‘t’ to the next month ➔ t = 1, 2, 3 Objective Function: Minimize (the total cost): Z = 20 (R1+R2+R3+R4) + 25(O1+O2+O3+O4) + 3 (I1+I2+I3) Constraints: → Demand Constraints: R1 +O1 = 1000 + I1 I1 + R2 + O2 = 800 + I2 I2 + R3 + O3 = 1200 + I3 I3 + R4 + O4 = 900 Capacity Constraints: Rt ≤ 800 Where t = 1, 2, 3, 4 Ot ≤ 200 Where t = 1, 2, 3, 4 Non–Negativity Constraints: Rt , Ot , It ≥ 0 11  Development (Formulation) of LP Model: Production Planning A Production Planning Problem (Single Product, Multi-period ): Suppose a production manager is responsible for scheduling the monthly production levels of a certain product for a planning horizon of twelve months. For planning purposes, the manager was given the following information: ▪ The total demand for the product in month 𝑡 is 𝑑𝑡 , for 𝑡 = 1, 2,... , 12. These could either be targeted values or be based on forecasts. 𝑝 ▪ The cost of producing each unit of the product in month 𝑡 is 𝑐𝑡 (Rs.), for 𝑡 = 1, 2,... , 12. There is no setup/fixed cost for production. ▪ The inventory holding cost per unit for month 𝑡 is ℎ𝑡 (Rs.), for 𝑡 = 1, 2,... , 12. These are incurred at the end of each month. ▪ The production capacity for month 𝑡 is 𝐶𝑡 , for 𝑡 = 1, 2,... , 12. The manager’s task is to generate a production schedule that minimizes the total production and inventory-holding costs over this twelve-month planning horizon. Assumption: 1. There is no initial inventory at the beginning of the first month. 2. Shortage of the product is not allowed at the end of any month. Objective Function: ▪ Index: 𝑇 𝑇 o 𝑡: 𝑇𝑖𝑚𝑒 𝑝𝑒𝑟𝑖𝑜𝑑 𝑝 𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒: ෍ 𝑐𝑡 𝑄𝑡 + ෍ ℎ𝑡 𝐼𝑡 ▪ Data & Parameters: 𝑝 𝑡=1 𝑡=1 o 𝑐𝑡 : 𝑐𝑜𝑠𝑡 𝑜𝑓 𝑝𝑟𝑜𝑑𝑢𝑐𝑡𝑖𝑜𝑛 𝑒𝑎𝑐ℎ 𝑢𝑛𝑖𝑡 𝑖𝑛 𝑡𝑖𝑚𝑒 𝑝𝑒𝑟𝑖𝑜𝑑 t o ℎ𝑡 : 𝐼𝑛𝑣𝑒𝑛𝑡𝑜𝑟𝑦 ℎ𝑜𝑙𝑑𝑖𝑛𝑔 𝑐𝑜𝑠𝑡 𝑖𝑛 𝑡𝑖𝑚𝑒 𝑝𝑒𝑟𝑖𝑜𝑑 𝑡 Constraints: o 𝐶𝑡 : 𝑃𝑟𝑜𝑑𝑢𝑐𝑡𝑖𝑜𝑛 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦 𝑖𝑛 𝑡𝑖𝑚𝑒 𝑝𝑒𝑟𝑖𝑜𝑑 𝑡 𝐼𝑡 = 𝐼𝑡−1 + 𝑄𝑡 − 𝑑𝑡 , 𝑡 = 1,2, … , 𝑇 o 𝑑𝑡 : 𝑑𝑒𝑚𝑎𝑛𝑑 𝑜𝑓 𝑝𝑟𝑜𝑑𝑢𝑐𝑡 𝑖𝑛 𝑡𝑖𝑚𝑒 𝑝𝑒𝑟𝑖𝑜𝑑 𝑡 𝑄𝑡 ≤ 𝐶𝑡 , 𝑡 = 1,2, … , 𝑇 ▪ Decision Variable: 𝑄𝑡 , 𝐼𝑡 ≥ 0 o 𝑄𝑡 : 𝑃𝑟𝑜𝑑𝑢𝑐𝑡𝑖𝑜𝑛 𝑖𝑛 𝑡𝑖𝑚𝑒 𝑝𝑒𝑟𝑖𝑜𝑑 𝑡 o 𝐼𝑡 : 𝐼𝑛𝑣𝑒𝑛𝑡𝑜𝑟𝑦 𝑖𝑛 𝑡𝑖𝑚𝑒 𝑝𝑒𝑟𝑖𝑜𝑑 𝑡 12  Areas of Application of Linear Programming MANAGEMENT APPLICATIONS ▪ Media Selection Problems INDUSTRIAL APPLICATIONS ▪ Portfolio Selection Problems ▪ Product mix problems ▪ Profit Planning Problems ▪ Man–Power Scheduling Problem ▪ Blending Problems ▪ Transportation Problems ▪ Productions Scheduling Problems ▪ Assignment Problems ▪ Trim Loss Problems ▪ Production Planning ▪ Assembly Line Balancing MISCELLANEOUS APPLICATIONS ▪ Make–or–Buy (Sub–Contracting) Problems ▪ Diet Problems ▪ Agriculture Problems ▪ Flight Scheduling Problems ▪ Environment Protection ▪ Facilities Location ▪ Data Envelopment Analysis 13  Graphical LP Solution ▪ Used to solve LP problems with two decision variables ▪ Consists of two steps: – Determining the feasible solution space ▪ i.e., finding the values of the variables for which all the constraints are met (feasible region) – Determining the optimal solution ▪ i.e., finding the best solution from among all the points in the solution space 14  Graphical LP Solution I. Finding the Feasible Region – In a 2D graph, use x-axis to represent one decision variable and the y-axis to represent the other – For each constraint, replace the inequality with equality and graph the resulting straight line on the 2D graph – For each straight line, find the side (half-space) of the graph meeting the original inequality constraint – Find the intersection of all regions defined by all the constraints, the resulting region is the (overall) feasible region. 15  Two-Variable LP Model ▪ Example 2.1-1 (The Reddy Mikks Company): PROBLEM The Reddy Mikks company produces both interior and exterior paints from two basic raw materials, M1 and M2 The following table provides the basic data of the problem Tons of raw material per ton of paint Max daily Exterior Interior availability (tons) Raw Material, M1 6 4 24 Raw Material, M2 1 2 6 Profit per ton $5,000 $4,000 The daily demand for interior paint cannot exceed that for exterior paint by more than 1 ton The maximum daily demand for interior paint is 2 tons What is the optimum (best) product mix of interior and exterior paints that maximizes the total daily profit? ISE 303 - Term 192 Dr. Yasser Almoghathawi, KFUPM 16  Graphical LP Solution: Example (Max) Maximize 𝑧 = 5,000𝑥1 + 4,000𝑥2 I. Finding the Feasible Region subject to 6𝑥1 + 4𝑥2 ≤ 24 𝑥2 5 𝑥1 + 2𝑥2 ≤ 6 −𝑥1 + 𝑥2 ≤ 1 1 𝑥2 ≤ 2 𝑥1 , 𝑥2 ≥ 0 3 4 Feasibl 2 e 𝑥1 6(0) + 4(0)  24 Region 6 17  Graphical LP Solution II. Finding the Optimal Solution – Draw the objective function: ▪ Equate the objective to a “reasonable” value, draw the corresponding straight line – Determine the direction of increase/decrease of the objective function: ▪ Equate the objective function to a larger value and draw the corresponding line – Find the optimal solution: ▪ Draw lines parallel to the objective and in the direction of its increase ▪ Identify the farthest line in the direction of increase that still intersects with feasible region ▪ The solution is that point (or set of points) at the intersection of the straight line and the feasible region 18  Graphical LP Solution: Example (Max) II. Finding the Optimal Solution How to find the values of 𝒙𝟏 & 𝒙𝟐 ? 𝑥2 Maximize 𝑧 = 5,000𝑥1 + 4,000𝑥2 Corner points: (0,0), (4,0), (3,1.5), (2,2), (1.2,2), (0,1) Corner (0,0): 5,000(0) + 4,000(0) = $0 Corner (4,0): 5,000(4) + 4,000(0) = $20,000 Corner (3,1.5): 5,000(3) + 4,000(1.5) = $21,000 𝑥1 = 3 tons Corner (2,2): 5,000(2) + 4,000(2) = $18,000 Optimum 𝑥2 = 1.5 tons Corner (1.2,2): 5,000(1.2) + 4,000(2) = 𝑧 = $21,000 $14,000 Corner (0,1): 5,000(0) + 4,000(1) = $4000 𝑥1 Approach 1: Isoprofit Line Method Approach 2- Corner Point Method 19  Graphical LP Solution ▪ Solution Procedure for a Maximization Problem – Prepare a graph of the feasible solutions for each of the constraints – Determine the feasible region that satisfies all the constraints simultaneously – Draw an objective function line – Move parallel objective function lines toward higher objective function values without entirely leaving the feasible region – Any feasible solution on the objective function line with the highest value is an optimal solution How about a minimization problem? 20  Two-Variable LP Model ▪ Example 2.2-2 (Diet Problem): PROBLEM Ozark Farms uses at least 800lb of special feed daily The special feed is a mixture of corn and soybean meal as shown below: Ib per lb of feedstuff Feedstuff Protein Fiber Cost ($/lb) Corn 0.09 0.02 0.30 Soybean meal 0.60 0.06 0.90 The dietary requirements of special feed are at least 30% protein and at most 5% fiber The goal is to determine the daily minimum-cost feed mix? 21  Two-Variable LP Model ▪ Example 2.2-2 (Diet Problem): SOLUTION – Decision Variables: 𝑥1 = lb of corn in the daily mix 𝑥2 = lb of soybean meal in the daily mix – Objective: Minimize 𝑧 = 0.3𝑥1 + 0.9𝑥2 – Constraints: 𝑥1 + 𝑥2 ≥ 800 (daily feed requirement) 0.09𝑥1 + 0.6𝑥2 ≥ 0.30(𝑥1 + 𝑥2 ) (protein requirement) 0.02𝑥1 + 0.06𝑥2 ≤ 0.05 𝑥1 + 𝑥2 (fiber requirement) 𝑥1 ≥ 0 and 𝑥2 ≥ 0 (non-negativity) 22  Two-Variable LP Model ▪ Example 2.2-2 (Diet Problem): SOLUTION – The complete model is Minimize 𝑧 = 0.3𝑥1 + 0.9𝑥2 subject to 𝑥1 + 𝑥2 ≥ 800 0.21𝑥1 − 0.3𝑥2 ≤ 0 0.03𝑥1 − 0.01𝑥2 ≥ 0 𝑥1 , 𝑥2 ≥ 0 23  Graphical LP Solution: Example (Min) Minimize 𝑧 = 0.3𝑥1 + 0.9𝑥2 ▪ Example 2.2-2 (Diet Problem): SOLUTION subject to 𝑥1 + 𝑥2 ≥ 800 𝑥2 3 0.21𝑥1 − 0.3𝑥2 ≤ 0 0.03𝑥1 − 0.01𝑥2 ≥ 0 𝑥1 , 𝑥2 ≥ 0 2 1 Optimum: Optimum 𝑥1 = 470.6 lb 𝑥2 = 329.4 lb 𝑥1 𝑧 = $437.64 24 CLASSIFICATION OF LP SOLUTION 25  CLASSIFICATION OF LP SOLUTION… ▪ Multiple / Alternate Optimum Solution: More than One Optimal Solution: o Two or more optimal solutions may exist, and o This actually allows management great flexibility in deciding which combination to select. Maximize: Z = 4X1 + 4X2 Subject to: X1 + 2X2 ≤ 10 6X1 + 6X2 ≤ 36 X1 ≤ 4 X1, X2 ≥0 As, at point ‘A’ (2,4) the value of the objective function is: Z = 4(2) + 4(4) = 24, and at point ‘B’ (4,2) the value of the objective function is: Z = 4(4) + 4(2) = 24. 26  CLASSIFICATION OF LP SOLUTION… ▪ Unbounded Solution: In some LP models, the values of the variables may be increased indefinitely without violating any of the constraints in this result the solution space becomes unbounded so As a result the value of the objective function may increase (in Maximization Case) or decrease (in Minimization Case) indefinitely. But it is wrong to conclude that just because the solution space is unbounded then solution also unbounded. The solution space may be unbounded but the solution may be finite. Maximize: Z = 2X1 + X2 Subject to: X1 – X2 ≤ 10 2X1 ≤ 40 X1, X2 ≥ 0 27  CLASSIFICATION OF LP SOLUTION… Unbounded Solution: (Example # 2) Minimize: 6X1 + 4X2 Subject to: 3X1 + 3X2 ≥ 40 3X1 + X2 ≥ 40 2X1 + 5X2 ≥ 44 X1, X2 ≥ 0 Optimal value to be 88, at X1 = 12, and X2 = 4. 28  CLASSIFICATION OF LP SOLUTION… ▪ Degeneracy: In LP problems, intersection of two constraints will define a corner point of the feasible region. But if more than two constraints pass through any one of the corner points of the feasible region, excess constraints will not serve any purpose, and therefore they act as redundant constraints, so redundant constraints create the Degeneracy. Maximize: Z = 4X1 + 6X2 Subject to: 6X1 + 4X2 ≤ 24 X2 ≤ 3 5X1 + 10X2 ≤ 40 X1, X2 ≥ 0 Optimal value to be 26, at X1 = 2, and X2 = 3. 29  CLASSIFICATION OF LP SOLUTION… ▪ Non–existing / Infeasible Solution: A linear programming problem is infeasible if there is no solution exists that satisfies all of the constraints. Maximize: Z = 3X1 + 2X2 Subject to: 2X1 + X2 ≤ 2 3X1 + 4X2 ≥ 12 X1, X2 ≥ 0 30 QUESTIONS 31