4 Integer Programming
Download 299.78 Kb.
|
Define variables yj as the number of times the j-th pattern is cut. In addition, denote by v1, v2, & v3 the number of 8 ft, 5 ft, and 3 ft rods that are purchased. Min z = 1y1 + 1y2 + 1.5y3 + 1.5y4 + 0.5y5 + 0.5y6 + 1y7 + 1.5y8 + 2v1 + 1.5v2 + 1.1v3. s.t. y1 + y2 + y3 + y4 ≤ 20. (1) y5 + y6 + y7 + y8 ≤ 25. (2) (supply constraints) y1 + y5 + v1 ≥ 60. (3) 2y2 + 1y3 + 2y6 + 1y7 + v2 ≥ 40. (4) 1y1 + 2y3 + 4y4 + 1y7 + 3y8 + v3 ≥ 75. (5) (demand constraints) y1, y2, …, y8; v1, v2, v3 ≥ 0 and integer. Optimal solution:  = 2,  = 0,  = 0,  = 18,  = 5,    = 0, and  = 0, as well as  = 53,  = 0, &  = 1. No rods are left over, the demand is exactly satisfied.
2-dimensional cutting stock problems: same formulation, cutting plans are more difficult to set up. Material usage: pattern 1: 34/40 sq ft = 85%, pattern 2: 32/40 sq ft = 80%. However: pattern 1 requires frequent machine adjustments. Also: guillotine cuts. 4.2.2 Diet Problem Revisited Two foodstuffs, one nutrient. Min z = 3x1 + 4x2 s.t. x1 + 2x2 5 x1, x2 0. plus: “if food 1 is in the diet, then food 2 should not be included. Define logical variables y1 (and y2) as one, if food 1 (food 2) is included in the diet, and zero otherwise.
A formulation that allows the first three cases & prohibits the last case is y1 + y2 1. y1, y2 = 0 or 1. Adding these constraints to the formulation is not sufficient, though, as it allows the continuous variables x1 & x2 to change independent of y1 and y2. We need linking constraints. Here, x1 My1 & x2 My2, with M >> 0 (but not too large, scaling). Validity: If y1 = 1 (the food is included in the diet), then the constraint reads x1 M, &, given that M is sufficiently large, the constraint is redundant. On the other hand, if y1 = 0 (the food is not included in the diet), the constraint reads x1 ≤ 0, &, since x1 ≥ 0, x1 = 0 follows. In other words, if a food is not in the diet, its quantity is zero. Different additional (conditional) constraint: “if food 1 is included in the diet, then food 2 must be included in the diet as well.”
Here, the additional constraint y1 y2 together with the linking constraints will do. 4.2.3 Land Use Two choices for a parcel of land: harvest or protect (but not both). Define variables y1= 1, if we harvest & 0 otherwise, & y2 = 1, if we protect, & 0 otherwise.
Again, the additional constraint is y1 + y2 ≤ 1. (There are no other variables, so that there is nothing to link). Allow 3 options: Harvest (y1), build a sanctuary (y2), or allow the building of a municipal well (y3).
Formulate: y1 + y2 ≤ 1 (eliminates the solutions in the last two rows of the decision table), & the constraint y1 + y3 ≤ 1 (eliminates the solution in the third row from the bottom of the table). 4.2.4 Modeling Fixed Charges Manufacture a combination of three Operations Research texts: Gabby and Blabby (GB), Huff, Fluff, and Stuff (HFS), & “Real OR” (ROR). There are 3 printing machines are available (only 1 is needed), 2 binding machines (again, only one is needed). Processing times for printing and binding machines
Directory: files files -> Answer True False 2 points Question 2 files -> Integer programming and game theory files -> Bpa vehicle Window Repair Scenario #1 task: Procure vehicle window relacement. Objective files -> Pop Warner History files -> North Carolina Inclusion Initiative Mapping Where Children with ieps are Being Served Purpose files -> Fall 2013 Spring 2014 Program Data: Standard 1 Exhibit 4d files -> Hanban – asia society confucius classrooms network 2010 request for proposal files -> Northern England’s set-jetting locations files -> Is it possible to construct a canon of tv programmes? Immanent reading versus textual-historicism Download 299.78 Kb. Share with your friends:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||