Lecture_3_Introduction_to_Linear_Programming_I

pdf

School

Drexel University *

*We aren’t endorsed by this school

Course

501

Subject

Industrial Engineering

Date

Dec 6, 2023

Type

pdf

Pages

14

Uploaded by CoachPorcupine1570

Report
Lecture 3: Introduction of Linear Programming-I Ankit Bansal Binghamton University abansal@binghamton.edu Ankit Bansal (BU) SSIE 553-Operations Research 1 / 14
Linear Programs (LPs) 1 LPs are optimization models with linear objective functions and constraints. 2 For the next few classes we will: Formulate LPs Solve LPs Ankit Bansal (BU) SSIE 553-Operations Research 2 / 14
Ingredients of an LP Model 1 Decision Variables 2 Objective Function 3 Constraints 4 Model parameters Objective function coefficients Constraint coefficients Right hand sides (Rhs) Ankit Bansal (BU) SSIE 553-Operations Research 3 / 14
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
LPs in words Following are some examples of LPs stated informally: 1 Maximize the production yield of pharmaceuticals subject to constraints on production parameters. 2 Minimize radiation absorption to healthy tissue subject to the requirement that cancer causing cells are destroyed. 3 Maximize advertising revenues on a broadcast network subject to a fixed schedule of commercial slots. Ankit Bansal (BU) SSIE 553-Operations Research 4 / 14
Simple Example 1 A surgical suite serves two types of surgeries: S1 and S2. 2 The surgeries require three resources: S1 requires R1 and R2. S2 requires R2 and R3. 3 Question: How many of each type of surgery should be planned for each day? 4 Note : R2 must be divided between S1 and S2. Ankit Bansal (BU) SSIE 553-Operations Research 5 / 14
Input Data (in Words) 1 Capacity: Number of units available per day for each resource. 2 Requirements: Number of units of resource needed for each surgery. 3 Performance Measure: Revenue per surgery. Ankit Bansal (BU) SSIE 553-Operations Research 6 / 14
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
Input Data (in Numbers) Resource S1 S2 Availability R1 1 0 4 R2 1.5 1 9 R3 0 2 12 Value/Surgery $3k $ 5k Ankit Bansal (BU) SSIE 553-Operations Research 7 / 14
In Class Example Write the model formulation. What are the decision variable? What is the objective function? What are the constraints? Solve using Graphical Method. Are following solutions feasible or infeasible? ( x 1 = 4 , x 2 = 7 ) , ( x 1 = 4 , x 2 = - 7 ) , ( x 1 = 4 , x 2 = 3 ) What is the best solution? Ankit Bansal (BU) SSIE 553-Operations Research 8 / 14
Another In-class Example Company X manufactures mechanical heart valves which different heart operations require in different sizes. Company X purchases basic valves from three different suppliers. The cost and size mix of valves purchased from each supplier are given in the following Table. Each month, Company X places one order with each supplier. At least 500 large, 300 medium, and 300 small valves must be purchased each month. Because of limited availability of basic valves, at most 700 valves per month can be purchased from each supplier. Formulate an LP to minimize the cost of acquiring the needed valves. Supplier Cost/Valve($) % Large % Medium % Small 1 5 40 40 20 2 4 30 35 35 3 3 20 20 60 Ankit Bansal (BU) SSIE 553-Operations Research 9 / 14
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
Key Words Company X manufactures mechanical heart valves which different heart operations require in different sizes .Company X purchases basic valves from three different suppliers. The cost and size mix of valves purchased from each supplier are given in the following Table . Each month, Company X places one order with each supplier. At least 500 large, 300 medium, and 300 small valves must be purchased each month. Because of limited availability of basic valves, at most 700 valves per month can be purchased from each supplier. Formulate an LP to minimize the cost of acquiring the needed valves. Supplier Cost/Valve($) % Large % Medium % Small 1 5 40 40 20 2 4 30 35 35 3 3 20 20 60 Ankit Bansal (BU) SSIE 553-Operations Research 10 / 14
Breaking Down the Problem 1 Define the decision variables. 2 Write the objective function 3 Write the constraints 4 Put it all together into the complete LP formulation Ankit Bansal (BU) SSIE 553-Operations Research 11 / 14
Work-Scheduling Problem A company requires different number of full-time employees on different days of the week. The number of full-time employees required on each day is given in the following Table. Union rules state that each full-time employee must work for five consecutive days and then receive two days off. For example, an employee who works Monday to Friday must be off on Saturday and Sunday. The company wants to meet its daily requirements using only full-time employees. Formulate an LP that the company can use to minimize the number of full-time employees who must be hired. Day Number of full-time employees required 1=Monday 17 2=Tuesday 13 3=Wednesday 15 4=Thursday 19 5=Friday 14 6=Saturday 16 7 = Sunday 11 Ankit Bansal (BU) SSIE 553-Operations Research 12 / 14
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
Another Multi-period Example Company X is a chain of computer service stores. The number of hours of skilled repair time that Company X requires during the next five months is given in the following table. At the beginning of January, 50 skilled technicians work for company X. Each skilled technician can work up to 160 hours per month. To meet future demands, new technicians must be trained. It takes one month to train a new technician. During the month of training, a trainee must be supervised for 50 hours by an experienced technician. Each experienced technician is paid $2,000 per month (even if that technician doesn’t work for full 160 hours). During the month of training, a trainee is paid $1000 a month. At the end of each month, 5% of company X’s experienced technicians quit to join Company Y. Formulate an LP whose solution is will enable company X to minimize the labor cost incurred in meeting the service requirements for next five months. Month Hours Month 1 (January) 6000 Month 2 (February) 7000 Month 3 (March) 8000 Month 4 (April) 9500 Month 5 (May) 11000 Ankit Bansal (BU) SSIE 553-Operations Research 13 / 14
Diet Problem 1 Assume your diet is based on the four “basic food groups”: pizza, coffee, red bull, and chocolate bars. 2 Pizza costs $3/slice, coffee costs $1/cup, red bull costs $1.50/can, and chocolate bars cost $1 each. 3 Each day, you must have at least 1500 calories, 10 oz of sugar, and 0.5 oz of caffeine. Pizza Slice Coffee (1 cup) Red Bull (1 can) Choc. Bar Calories 500 100 250 200 Sugar 0 0.5 2 3 Caffeine 0 0.1 0.2 0.03 Write the LP formulation minimizing the cost such that Calorie, Sugar and Caffeine requirements are satisfied. Ankit Bansal (BU) SSIE 553-Operations Research 14 / 14