Uncategorized

Given: You are a planning engineer for a metropolitan area. You want to minimize the cost of land filling the refuse produced by Cities A, B, C, and D under your jurisdiction. Three of the cities have landfills (G, H, and I), but their capacities do not match up with the amount of waste produced in each city. Each city produces the following amount of refuse: A – 100 tons/day, B – 50 tons/day, C – 60 tons/day, D – 40 tons/day.

The city landfills have the following capacities: G – 50 tons/day, H – 75 tons/day, I – 150 tons/day

The cost per ton for hauling and land filling are given in the following matrix:

To Landfills G,H,I
From Cities A,B,C,D		G	H	I
	A	10	20	30
	B	18	12	16
	C	22	18	26
	D	28	20	8

Required: Solve this as a linear programming problem to minimize the total cost of disposing of all trash.

Learning Objectives – Class 30

After today’s lecture, and after working the homework problems, the student should be able to

• Compute interarrival times based on any of several probability distributions
  • Zero-one Uniform
  • Uniform
  • Normal
  • Exponential
• Simulate a simple engineering system

Topics covered in today’s class

Where the data comes from, how you know which distribution fits your data, mean, sigma, 3 sigma, 6 sigma, …

a) Given a “balanced” transportation problem, wherein source = supply. You are in charge of a large construction project that involves two sites. Currently, you need 50 tons of aggregate at site 1 and 22 tons of aggregate at site 2. Two suppliers are available. Supplier A can deliver 29 tons and supplier B can deliver 43 tons. Restrictions on the type of work to be done require that at least 20 tons used at site 1 have to come from source B and no more than 10 tons of aggregate from source A can be used at site 2. Delivered aggregate costs ($/ton) are as follows:

	To Site1	To Site 2
From Source A	1	2
From Source B	1.5	1.25

Required: Solve this as a linear programming problem to minimize the cost of aggregate.

Program won’t run? What did I warn you about over constraining the problem?

A small town requires the daily consumption of 6 million gallons of water of a quality such that the concentration of salt must be kept below 100 mg/gal and the concentration of iodine be kept below 12 mg/gallon. The water can be supplied from three sources: from local wells, from a local river, or from an out-of-state river. In each case, the cost of the necessary infrastructure (pipes, pumps, long term repairs and replacements, those sort of things) will be financed by floating bonds, which will be repaid by the users in their water bill.

Water from the local wells will have 50 mg/gal of salt, and 10 mg/gal of iodine, and can be supplied at a cost of $150/million gallons. Water from the local river will have 150 mg/gal of salt, and 2 mg/gal of iodine, and can be supplied at a cost of $75/million gallons. Water from the out-of-state river will have 20 mg/gal of salt, and no iodine, and can be supplied at a cost of $250/million gallons.

The water from the three sources will be completely mixed before it is used. Draw a scale map (schematic) of this problem, then draw a model (circles, arrows, neatly lined up), and then write a mathematical model to solve for the least expensive way to supply the water, and finally, solve the problem using MOR/LP.

NOTE: On all linear programming problems in this class:

1. Formulate the written solution necessary to be typed into into MOR. For example:
   Max Z = 3x+2y
   ST x+y>=5
   2x-3y<=20
2. COMPLETELY define at least one or two of the variables so that I will know what you are doing. For example: AB = the number of cubic yards of dirt that I find it to be in my best economic interest to haul from the borrow pit at A to the fill station at B.
3. Solve the problem using MOR.
4. COMPLETELY define your solution. Do not just hand in the computer output and expect that I can interpret it. That gets you only half credit. Rather, tell me exactly what the output means: For example if AB = 12, tell me that you have found you should haul 12 tons of gravel from Pit A to Job Site 2. JBO = 3 means you should make three base plates in January using overtime. Whatever.

If you do not follow these instructions, you will get zero credit for your work.

Learning Objectives – Class 18

After today’s lecture, and after working the homework problems, the student should be able to

• Solve linear programming open pit mining operation problems
• Solve linear programming siting problems
• Solve linear programming “template cutting” problems

Topics covered in today’s class

See main sheet

Print out this page and bring it to class with you.

Time Independent – A steel fabricating plant produces four different specialized steel assemblies, used in scaffolding. Each assembly is composed of the following elements:

	Angle Iron (lbs)	Steel Plate (ft^2)	Pipe (feet)	Labor (hours)	Paint (gallons)	Welds (ft^3)	Plating (ft^2)	Bolts (each)	Profit ($)
Floors	46	24	40	2	12	2	50	10	$32
Stands	84	50	80	3	15	1	70	18	$54
Braces	26	30	10	1	7	2	10	4	$17
Brackets	12	2	–	0.5	–	3	–	–	$8
Max Available	40,000	20,000	24,000	5600	9000	2500	15,000	30,000

Marketing says that they can sell everything you can make. However, because construction equipment often runs into the stands, they ask that you make at least 2 stands for every floor.

Print out the following page and bring it to class with you.

Time Independent Production Models

Determine what scaffolding components to make for the following month, given the data below:

	Side Rails	Floors	Braces	Connections	Limits/month
Ft of 2” Pipe Used	50 ft	20 ft	10 ft		50,000 ft
Ft of 2x2x1/4” Angle Iron Used	30 ft	50ft	12 ft	8 ft	30,000
1” bolts	20	30		4	10,000
Pounds of Welding	2	1	4	3	1,000
Labor	10	6	2	1	3200
Profit	$80	$50	$12	$8
Minimum Required	30		50

Additionally, marketing requires that you make at least 2 sides for every floor manufactured.

Learning Objectives – Class 26

After today’s lecture, and after working the homework problems, the student should be able to

• Solve time-dependent linear programming production problems
• Work with balanced linear programming assignment problems
• Work with unbalanced linear programming assignment problems

Topics covered in today’s class

See main sheet

Learning Objectives – Class 25

After today’s lecture, and after working the homework problems, the student should be able to

• Solve linear programming problems by hand

Topics covered in today’s class

See main page

      ALGORITHMS

      LIMITS

      KEYWORDS

      FORMATS

      comments: “can be anywhere, enclosed in double quotes”

%ALGORITHMS

        SIMPLEX         BOUNDED      REVISED  SYMMETRIC

        SEPARABLE       QUADRATIC

        ALLINTEGER      INTEGER      BINARY

        TRANSPORTATION  MINCOSTFLOW

%FORMATS

      STANDARD        input format

      TRANSPORTATION  input format

      TABLEINPUT      format

%KEYWORDS

      GRID         ALLINTEGER   INTEGER   GRAPHICS

      VARIABLES    BOUNDonSUM   BINARY    GRAPHGRID

%LIMITS   Maximum number of variables is 100, including

               any slacks, surplus and artificials added by the system

               Maximum number of constraints is 50

               Maximum grid segments per variable in separable

               programming problems is 10

%GRAPHICS    The solution space and simplex algorithm steps can be

             graphically displayed for two-dimensional problems.

             To utilize these graphics capabilities, the keyword

             GRAPHICS and the domains for the x-axis and y-axis

             must be given.  The syntax is:

                GRAPHICS (x-lower, x-upper, y-lower, y-upper)

  example:   GRAPHICS( -1, 4, -1, 10)

%STANDARD input format:

        maximize z = 3×1 + 2×2       “can be minimize, max or min”

        subject to                   “can be st”

                     4×1 + 3×2 <= 5

                     2×1 – x2  >= 2

                     x1 +  x2  =  3

                     x1 >= 0, x2 >= 0  “nonnegativity assumed; not required”

        NOTE: The right hand sides must be a single constant number!

%TABLEINPUT is a shorthand problem formulation and input method.

           TABLEINPUT {            “data starts with left brace”

              variables(z, x1, x2) “required variables name list;

                                    objective variable name is 1st”

              3   2  max  0        “initial z value is 0”

              4   3  <=   5

              2  -1  >=   2

              1   1  =    3

           }                       “data ends with right brace”

%TRANSPORTATION   special input form is: all data is Integer valued

           TRANSPORTATION {     “data starts with left brace”

             DEMANDS = (1, 14, 23, 10)  “list of integer demands”

             SUPPLIES = (12, 13, 13) “list of integer supplies”

               “note: supplies and demands need not balance”

             COSTS = ( (5,2,10,1),  “costs from supply 1 to all demands”

                       (3,2,8,11),  “costs from supply 2 to all demands”

                       (5,11,2,8) ) “costs from last supply to all demands”

                 }             “data ends with right brace”

             PROFIT (or PROFITS) can be used instead of COST (or COSTS)

             COST (or COSTS) problems are to be minimized

             PROFIT (or PROFITS) problems are to be maximized

             order of DEMANDS, SUPPLIES and COSTS/PROFITS is immaterial

             DEMAND and DEMANDS, SUPPLY and SUPPLIES are equivalent terms

%VARIABLES    Required list of variable names for TABLEINPUT form.

             First name MUST be the objective function name.

   example   VARIABLES (z, x1, x2)

%GRID         In separable programming a set of grid points for each

             expanded variable must be given.  These are indicated by

             GRID(varName) = {0, pt2, pt3, … , ptN}

             where 0, pt2, … , ptN are increasing points for the

             grid of variable varName.

             Note that the first point must be zero.

   example   GRID(x1) = {0, 1.4, 3, 5}

             This will result in the additional variables:

                x1.1 over 0 to 1.4

                x1.2 over 1.4 to 3

                x1.3 over 3 to 5

%SIMPLEX  BOUNDED  REVISED  SYMMETRIC

             All of these algorithms have the standard linear

             programming formulations.  Note that slacks, surplus

             and artificial variables are added by the algorithms

             if needed and, therefore, not by the user.

   example   max z =  3×1 +  2×2

              st      2×1 +  4×2  <= 8

                             2×2  <= 4

             The bounded variable technique uses an extended pivot

             rule to omit constraints such as 2×2 <= 4.

%SEPARABLE    A separable programming problem is one where all

             functions can be written as the sum of terms of

             functions of individual variables.  The “convex”

             separable method is used.  Thus, problems must be

             of the convex programming class.  The algorithm will

             check to see that the approximated problem on the

             given grid points is a convex program.

             To check if the grid spacing yields an acceptable

             approximation, a graph of all functions of the specified

             single variable over the variable grid is accomplished via

             the GRAPHGRID(varName) command.  Thus, variables can be

             checked one at a time with this graphics support facility.

   example   min  z  =  3×1^2 +  3×2*x2

              st         x1^4 +  3×2    <= 15

              grid(x1) = {0, 0.5, 1, 1.5, 2}

              grid(x2) = {0, 1, 2, 3, 5}

              GraphGrid(x1)

%QUADRATIC    A quadratic programming problem has a quadratic objective

             function subject to linear constraints.  The algorithm

             assumes a strictly convex form for minimization or a

             strictly concave function for maximization.  The algorithm

             checks for adherence to this form.

   example   max z = 3 + 2×1 – 3×1^2 + x1*x2 -3×2 -5×2^2

             st      3×1 + 5×2  <= 15

                      x1 +  x2  <=  6

%MINCOSTFLOW  Algorithm for minimizing the cost for a capacitated

             flow network with an objective flow value to be met.

             All numbers are integer valued; infinity is INF.

             The order of the data categories is immaterial.

             Cost is the unit flow cost and Capacity is the upper

             limit on the flow.

             Input format:

                 MINCOSTFLOW {                     “starting brace”

                    cost = ( (v1,v2,v3, … , vn),

                                  …

                             (v1,v2,v3, … , vn) )

                capacity = ( (v1,v2,v3, … , vn),

                                  …

                             (v1,v2,v3, … , vn) )

                source = starting node number

                sink = ending node number

                flowObjective = target flow value  } “ending brace”

%INTEGER      Variables list for restricting variables to be integer.

             INTEGER(x1, x3) restricts x1 and x3 to be integer for

             integer programming problem.  For all integer variables

             problems, all the problem’s coefficients should also be

             integer and a bound on the sum of the variables is required.

             ALLINTEGER allows the declaration of all variables as integer

             without listing all the variables in the INTEGER list.

             If the ALLINTEGER algorithm is to be used then the construct

             BOUNDonSUM = value is required.

%BINARY       Used to indicate that all problem variables are to be

             0/1 variables.  This keyword causes the Balas zero/one

             algorithm to be selected.

             To use merely include BINARY at the end of the model.

%ALLINTEGER   Replaces variables list in declaring all variables

             to be integer.  Can be used in Gomory-Cut and AllInteger

             algorithms; ignored if other algorithms are chosen.

%BOUNDONSUM   AllInteger algorithm requires that a bound estimate be

             given for the maximum value of the sum of the variables.

             BoundonSum = value is the syntax for this construct.

%ALLINTEGER   All integer algorithm is an efficient procedure for

             solving integer programming problems where all the

             variables are restricted to be integer.  The all integer

             restriction can be connoted to the system via the

             ALLINTEGER keyword, but also included must be a bound

             on the sum of the variables: BOUNDonSUM = value.