第九章节 整数规划.pptVIP

超级泡沫公司市场计划Super suds Corporation Marketing Plan 超级泡沫正为其下一年的新产品制定营销计划， 并准备在全国电视网上购买了五组广告时段，以 促销三种产品，每个广告只针对一种产品，每种 产品最多可以作三个广告。 问题：怎样将五个广告时间分配给三种产品？ 实际举例5 整数规划和0－1整数规划 超级泡沫公司数据Data for the Supersuds Corp. Problem 利润 (Millions) 广告时段数量 产品1 产品2 产品3 0 $0 $0 $0 1 1 0 –1 2 3 2 2 3 3 3 4 整数规划和0－1整数规划 代数模型 Algebraic Formulation Let yij = 1 if there are j TV spots for product i; 0 otherwise (i = 1, 2, 3; j = 1, 2, 3)Maximize Profit = y11 + 3y12 + 3y13 + 2y22 + 3y23 – y31 + 2y32 + 4y33 subject to Mutually Exclusive: Product 1: y11 + y12 + y13 ≤ 1 Product 2: y21 + y22 + y23 ≤ 1  Product 3: y31 + y32 + y33 ≤ 1 Total available spots: y11 + 2y12 + 3y13 + y21 + 2y22 + 3y23 + y31 + 2y32 + 3y33 ≤ 5 and yij are binary (i = 1, 2, 3; j = 1, 2, 3). 超级泡沫公司市场计划Super suds Corporation Marketing Plan 整数规划和0－1整数规划 西南航空公司人员排程Southwestern Airways Crew Scheduling 西南航空公司需要将其机组人员分配给其所有航 班，我们将重点把以旧金山为基地的3个机组人 员分配给11个航班。 问题：如何将3个机组分配给3个航班的序列？ 实际举例6 整数规划和0－1整数规划 西南航空公司航线图Southwestern Airways Flights 整数规划和0－1整数规划 西南航空公司问题数据Data for the Southwestern Airways Problem Feasible Sequence of Flights Flights 1 2 3 4 5 6 7 8 9 10 11 12 1. SFO–LAX 1 1 1 1 2. SFO–DEN 1 1 1 1 3. SFO–SEA 1 1 1 1 4. LAX–ORD 2 2 3 2 3 5. LAX–SFO 2 3 5 5 6. ORD–DEN 3 3 4 7. ORD–SEA 3 3 3 3 4 8. DEN–SFO 2 4 4 5 9. DEN–ORD 2 2 2 10. SEA-SFO 2 4 4 5 11. SEA–LAX 2 2 4 4 2 Cost, $1,000s 2 3 4 6 7 5 7 8 9 9 8 9 整数规划和0－1整数规划 代数模型Algebraic Formulation Let xj = 1 if flight sequence j is assigned to a crew; 0 otherwise. (j = 1, 2, … , 12).Minimize Cost = 2x1 + 3x2 + 4x3 + 6x4 + 7x5 + 5x6 + 7x7 + 8x8 + 9x9 + 9x10 + 8x11 + 9x12 subject to Flight 1 covered: x1 + x4 + x7 + x10 ≥ 1 Flight 2 covered: x2 + x5 + x8 + x11 ≥ 1 : : Flight 11 covered: x6 + x9 + x10 + x11 + x12 ≥ 1 Three Crews: x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10 + x11 + x12 ≤ 3 and xj are binary (j = 1, 2, … , 12). 西南航空公司人员排程Southwestern Airways Crew Scheduling 整数规划和0－1整数规划 西南航空公司问题的结果Solution for the Southwestern Airwa