4 Integer Programming
Download 299.78 Kb.
|
The capacities of the three printing machines are 120 100, and 110 hours (7,200, 6,000, and 6,600 minutes). Capacities of the binding machines: 333⅓ and 300 hours, respectively (or 20,000 and 18,000 minutes). The costs to lease the machines are independent of the number of books made with them. They are $10,000, $8,000, $9,000, $20,000, and $23,000, respectively. The profit contributions of the three books (other than the leasing costs) have been identified as $40, $60, and $70. Also, produce at least 500 copies of the landmark ROR book in order to maintain a good academic image. Define variables x1, x2 and x3 as the number of books of the three types that are manufactured and sold. Also, define binary variables y1, y2, …, y5 that assume a value of one, if a machine is leased, and 0 otherwise. P: Max z = 40x1 + 60x2 + 70x3 10,000y1 8,000y2 9,000y3 20,000y4 23,000y5 s.t. 3x1 + 2x2 + 4x3 7,200 + M(1−y1) 6x1 + 3x2 + 5x3 6,000 + M(1−y2) 4x1 + 3x2 + 5x3 6,600 + M(1−y3) 10x1 + 12x2 + 15x3 20,000 + M(1−y4) 10x1 + 11x2 + 14x3 18,000 + M(1−y5) x3 500 y1 + y2 + y3 = 1 y4 + y5 = 1 x1, x2, x3 0 and integer y1, y2, y3, y4, y5 = 0 or 1. With M = 1,000,000, the optimal solution is  = = 1 and  = 0 (i.e., we lease the second printing and the first binding machine), and make  = 0 GB books,  = 1,039 HFS books, and  = 502 ROR books. The profit associated with this plan is $69,480. Note that the slack capacities indicate huge (and meaningless) values for machines not leased. Their right-hand side values have the artificial value of M = 1,000,000, from which nonexistent usage is subtracted.
Now allow more than one printing and/or binding machine to be used. We now need additional variables xij to denote books of type i processed on machine j: P: Max z = 40x1 + 60x2 + 70x3 –10,000y1–8,000y2–9,000y3–20,000y4–23,000y5 s.t. x1 = x11 + x12 + x13 x2 = x21 + x22 + x23 x3 = x31 + x32 + x33 3x11 + 2x21 + 4x31 ≤ 7,200y1 6x12 + 3x22 + 5x32 ≤ 6,000y2 4x13 + 3x23 + 5x33 ≤ 6,600y3 10x14 + 12x24 + 15x34 ≤ 20,000y4 10x15 + 11x25 + 14x35 ≤ 10,000y5 x3 ≥ 500 y1 + y2 + y3 ≥ 1 y4 + y5 ≥ 1 x11 + x12 + x13 = x14 + x15 x21 + x22 + x23 = x24 + x25 x31 + x32 + x33 = x34 + x35 y1, …, y5 = 0 or 1 x1, x2, x3; x11, x12, …, x35 ≥ 0 and integer. The objective function has not changed. The first three constraints link xij and xi so that they define the amounts of the products actually made. The next five constraints are capacity constraints restricting the number of units we can make by the machine capacities (zero if we do not lease the machine). The next constraint ensures that we make at least 500 units of the ROR book, and the next two constraints specify that we must choose at least one of each of the two types of machines. The last three structural constraints require books printed also to be bound. The optimal solution is to lease the first printing machine and both binding machines. As before, we make no GB books, but 2,600 HFS books and 500 ROR books. The only significant change is the increase of HFS books from 1,039 to 2,600, resulting in a doubling of the profit from $69,480 to $138,000. 4.2.5 Workload Balancing Goal: Distribute the workload evenly. Tasks cannot be split. Example: Processing times for worker-task combinations
Define variables yij = 1, if employee Wi is assigned to task Tj, and zero otherwise. Assign each task to exactly one employee. y1j + y2j + y3j = 1 for all j = 1, ..., 5. Actual working times of the employees: w1 = 5y11 + 1y12 + 9y13 + 4y14 + 9y15, w2 = 4y21 + 3y22 + 8y23 + 3y24 + 8y25, and w3 = 7y31 + 5y32 + 6y33 + 4y34 + 7y35, Possibility: Min z = max {w1, w2, w3}. Rewrite as Min z, s.t. z ≥ w1, z ≥ w2, and z ≥ w3 + other constraints. Min z s.t. z ≥ 5y11 + 1y12 + 9y13 + 4y14 + 9y15 z ≥ 4y21 + 3y22 + 8y23 + 3y24 + 8y25 z ≥ 7y31 + 5y32 + 6y33 + 4y34 + 7y35 y11 + y21 + y31 = 1 y12 + y22 + y32 = 1 y13 + y23 + y33 = 1 y14 + y24 + y34 = 1 y15 + y25 + y35 = 1 yij = 0 or 1 for i=1, 2, 3; j=1, …, 5. Solution: W1 – T2 & T5, W2 – T1 & T4, W3 – T3. Workloads: 10, 7, and 6 hours. Alternative: Min z = ((1/3)w w1)2 + ((1/3)w w2)2 + ((1/3)w w3)2. Always combine “equity” with an efficiency objective (otherwise workloads of 12, 12, & 12 are preferred to 7, 8, 9). 4.3 Solution Methods for Integer Programming Problems 4.3.1 Cutting Plane Methods The first exact techniques for solving integer programming problems were cutting plane techniques. General idea: Solve linear programming relaxation, i.e., the given problem without integrality requirements. If the optimal solution is integer, we are done. Otherwise, introduce a cutting plane, i.e., an additional constraint that (1) cuts off (i.e., makes infeasible) the present optimal solution, while (2) not cutting off any feasible integer point. Example: Consider the all-integer programming problem: P: Max z = y1 + y2 s.t. 3y1 + 2y2 ≤ 6 y1 + 3y2 ≤ 3 y1, y2 ≥ 0 and integer. The shaded area shows the feasible set of the linear programming relaxation, and  = (12/7, 3/7) is the optimal solution of the linear programming relaxation.
The triangle shown by the broken lines connecting (0, 0), (2, 0), and (0, 1) is the convex hull of the feasible set. The dotted line is the cutting plane 5y1 + 10y2 ≤ 12. It is indeed a cutting plane, as the present optimal solution is cut off as 90/7 =  12, and since all four feasible integer points satisfy the condition & are thus not cut off.
Computation performance of cutting planes has been disappointing. Example: We use a simple Dantzig cut, which does not require any knowledge beyond the solution typically provided by a solver. Other, more efficient, cutting planes work on the same principle. Given: an all-integer linear programming problem. Include all slack and excess variables, so that all constraints are equations. Let there be n nonnegative variables (including the slack and excess variables) and m structural equation constraints, and assume that the present optimal solution of the linear programming relaxation has at least one noninteger component. Separate the variables into two disjoint sets B and N, where B includes all variables that are presently positive, while N includes all variables that are presently zero. If the solution is nondegenerate, the set B will include exactly m variables, and the set N exactly (n–m) variables. In case of primal degeneracy, the set N will include more than (n – m) variables, in which case we define N as any (n – m) variables presently at zero. A Dantzig cut requires the sum of all variables in the set N to be at least “1.” Validity: (1) Since all variables in the set N equal zero, the cutting plane invalidates the present solution. (2) Any feasible solution to the original integer problem will need to have at least one variable in N assume a positive value, which, since this is an all-integer optimization problem, must be at least one. Hence, the sum of all the variables that are presently zero, must be at least one. Add the cut to the problem & re-solve the problem (preferably with a warm start). Stop, if the new solution is integer; else, repeat. The the process, the z-value cannot increase (decrease) for max (min) problems. In each step, the feasible set shrinks. Unfortunately, for Dantzig cuts, this is not necessarily finite. Example: Consider the integer programming problem: Max z = 3y1 + 2y2 s.t. 3y1 + 7y2 22 5y1 + 3y2 17 y1 2 y1, y2 0 and integer. Adding slack variables S1 and S2 and an excess variable E3, we obtain the following formulation with n = 5 variables and m = 3 structural constraints: Max z = 3y1 + 2y2 s.t. 3y1 + 7y2 + S1 = 22 5y1 + 3y2 + S2 = 17 y1 – E3 = 2 y1, y2, S1, S2, E3 0 and integer. The optimal solution is   , ,  , and  with  . Here, N = {S1, S2}, so that the Dantzig cut is
S1 + S2 ≥ 1 (or 8y1 + 10y2 ≤ 38). Subtracting a new excess variable E4 from the left-hand side of this cut, we obtain S1 + S2 – E4 = 1. Adding this cut to the problem and solving it again, we obtain the new solution  ,  ,  ,  and  with an objective value  . Clearly, another cut is required. The sequence of cutting planes generated in the process is shown in the table below.
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:
|
, 
, 
, 
, 
with 
, 
, 
, 
, 
, 
with 
.
, 
, 
, 
, 
, 
, 
with 
.
, 
, 
, 
, 
, 
, 
, 
with 
.
, 
, 
, 
, 
, 
, 
, 
, 
with 
.
, 
, 
, 
, 
, 
, 
, 
, 
, 
with 
.
, 
, 
, 
with 
(optimal all-integer solution)