Lecture_3_Introduction_to_Linear_Programming_I
pdf
keyboard_arrow_up
School
Drexel University *
*We aren’t endorsed by this school
Course
501
Subject
Industrial Engineering
Date
Dec 6, 2023
Type
Pages
14
Uploaded by CoachPorcupine1570
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