MATH 251 ACTIVITY 1:



MATH 251 ACTIVITY 3: Formulating Linear Programming Problems; Integer and Binary variables

WHY: The solution process for linear programming problems is quite straightforward [though not necessarily easy], and can be programmed. What requires the intelligence of human beings is the formulation of problems and the interpretation of results. Certain types of restrictions (percentage limits, integer requirements) require special handling or specialized solution methods.

LEARNING OBJECTIVES:

1. Work as a team, using the team roles.

2. Be able to determine the variables and objective, and write the constraints, for a problem that fits the linear programming model.

3. Recognize integer and binary constraints and be able to represent them.

4. Know how determine what is a "small" change in a constraint.

CRITERIA:

1. Success in completing the exercises.

2. Success in working as a team

RESOURCES:

1. The notes “BinaryVars.doc” and examples “Binaryvars.xls” available on the Public server (P: drive) and in th e”Linear Programming Docs” folder (of “Course documents”) on the Blackboard site

2. Your text – chapter 3

3. Microsoft Excel running on the college network

4 45 minutes

PLAN:

1. Select roles, if you have not already done so, and decide how you will carry out steps 2 and 3

2. Work through the exercises given here - be sure everyone understands all results

3. Assess the team's work and roles performances and prepare the Reflector's and Recorder's reports including team grade.

4. Be prepared to discuss your results.

EXERCISES:

1. Set up and solve exercise 28 on p.177 as an integer linear programming problem. That is

a. Define variables

b. Write (algebraically) the objective and constraints (you will need a variable for each of the 9 shifts and a constraint for each of the eight time blocks plus the four restrictions given at the top of page 178 and the integer value requirement)

c. Set up and solve an Excel spreadsheet model corresponding to the model in b. and give an answer (requires words) – how many workers for each shift, and what is the minimum daily employee cost? .

2. Set up and solve Exercise 34 on p. 179 as a binary linear programming problem [The usual three parts – as listed in #1]

You will need a binary variable (1 for yes, 0 for no ) for each project

To say “at most one of Xi, Xj is 1” you can use Xi + Xj ≤ 1

“Xi and Xj are both 0 or both 1” is represented by Xi – Xj = 0

“At least 1 of Xi, Xj is 1 “ is represented by Xi + Xj ≥ 1

“Xi is one only if Xj is 1” is represented by Xi – Xj ≤ 0 (or by Xj – Xi ≥ 0)

CRITICAL THINKING QUESTIONS:(answer individually in your journal)

1. The solution to an integer linear programming problem can never have a better value (larger max or smaller min) than the solution of the matching linear programming problem (and usually the value is not as good). Why is this true?

2. What type of constraint do you find the hardest to deal with (understand and set up in a problem)? Can you tell why it is hard for you?

3. Working to solve and write up problems is slower with a team than by yourself – if you understand what is to be done. Do you find the trade-off (more chance to understand the problems, more chance to catch mistakes traded for more time spen int getting the work discussed, explained, completed) wothwhile, or would you be better off working by yourself?

SKILL EXERCISES:(This is the assignment due next class)

Chapter 3 problems (p 168) # 4, #29(15 binary variables and 15 constraints), #30 #38

For #29: Each Sector gives a constraint for “the sector or one of the adjacent sectors must have a patrol unit”

For # 30: The binary variable for Michigan plant, for example , must be 1 if anything is built in Michigan. One way to do this (asssuming the variable is called XM, so XM = 0 if Michigan not used, 1 if Michigan used) is 60XM – (#cars from Mich + # vans from Mich + # buses from Mich) ≥ 0 - the 60 comes from the fact that at most 60 vehicles (30 + 20 + 10) can be made in Michigan – XM will have to be positive if any of the Michigan variables are positive). Any number that is at least as large as the maximum number of vehicles to be made could be used in place of the 60

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download