Chapter 3 Introduction to LP Professor Heesang Lee SKK University

Start of Linear Programming George Dantzig Junior Statistician U.S. Bureau of Labor Statistics (1937-39) Head of USAF Combat Analysis Branch (1941-46) PhD Mathematics, Cal Berkeley (1946) Invented “Simplex” method for solving linear programs (1947) HSLee@SKKU

3.1 Prototype Example: The Wyndor Glass Company Problem The Wyndor Glass Company is planning to launch two new products. Product 1 is an 8-foot glass door with aluminum framing and Product 2 a 4x6 foot double-hung wood-framed window Aluminum frames are made in Plant 1, wood frames are made in Plant 2, and Plant 3 produces the glass and assembles the products. Product 1 requires some of the production capacity in Plants 1 and 3, but none in Plant 2. Product 2 needs only Plants 2 and 3. The marketing division has concluded that the company could sell as much of either product as could be processed by these plants. The management of the company wants to determine what mixture of both products would be the most profitable. The following table provides the information available. HSLee@SKKU

Example – Wyndor Glass Formulate and take a guess at soln. Time required per batch Plant Product 1 Product 2 Time Avail 1 4 2 12 3 18 profit per batch $3,000 $5,000 HSLee@SKKU

Graphical Solution FIGURE 3.1 Shaded area shows values of (x1, x2) allowed by x1  0, x2  0, x1  4 FIGURE 3.2 Shaded area shows the set of permissible values of (x1, x2), called the feasible region HSLee@SKKU

Graphical Solution FIGURE 3.3 The value of (x1, x2) that maximizes 3x1 + 5x2 is (2, 6). HSLee@SKKU

Graphical Solution Procedure Graph the feasible region Graph a representative profit line Move the line in the direction of increasing profit. Stop when you are as high as you can get within the feasible region. HSLee@SKKU

Finding the Optimal Solution Determine the slope of the objective function (an infinite set of straight lines-isoclines) Select a convenient point in the feasible region Draw the corresponding straight line (a single isocline) Determine the direction of increase of the objective function (we are maximizing) Select a second point in the feasible region and simply evaluate the objective function at that point Follow the direction of increase until reaching the (corner) point beyond which any increase of the objective function would take you outside of the feasible region HSLee@SKKU

Continuing the Learning Process with OR Courseware OR Tutor This program includes a complete demonstration example of the graphical method introduced in this section. This demonstration begins by introducing a problem and formulating a linear programming model for the problem before then applying the graphical method step by step to solve the model. This computer demonstration highlights concepts that are difficult to convey on the printed page. You may refer to Appendix 1 for documentation of the software. Worked Examples of the CD-ROM This section includes a few supplement examples with complete solutions The examples for the current chapter begin with a relatively straightforward problem that involves formulating a small linear programming model and applying the graphical method. IOR Tutorial This program features many interactive procedures for interactively executing various solution methods presented in the book This enables you to focus on learning and executing the logic of the method efficiently while the computer does the number crunching. You then can print out your work and results for your homework. These procedures are designed specifically to provide you with an efficient, enjoyable, and enlightening learning experience while you do your homework. HSLee@SKKU

3.2 LP Models Allocate m resources across n activities to maximize Z. Z = objective xj = level of activity j cj = increase in z from 1 unit of xj bi = amount of resource i available aij = amount of resource i consumed by activity j HSLee@SKKU

Standard Form Concise version: A is an m by n matrix: n variables, m constraints HSLee@SKKU

Sec. 3.2 Standard Form for LP Max Z c X s t a b n m mn = + £ × ³ 1 2 11 12 21 22 . , Decision Variables HSLee@SKKU

Sec. 3.2 Standard Form for LP Max Z c X s t a b n m mn = + £ × ³ 1 2 11 12 21 22 . , Objective HSLee@SKKU

Sec. 3.2 Standard Form for LP Max Z c X s t a b n m mn = + £ × ³ 1 2 11 12 21 22 . , Functional Constraints Nonnegativity Constraints HSLee@SKKU

Other Forms Slack/surplus variables The other legitimate forms are the following: 1. Minimizing rather than maximizing the objective function: Minimize Z = c1x1 + c2x2 + · · · + cnxn. 2. Some functional constraints with a greater-than-or-equal-to inequality: ai1x1 + ai2x2 · · · + ainxn  bi for some values of i. 3. Some functional constraints in equation form: ai1x1 + ai2x2 · · · + ainxn = bi for some values of i. 4. Deleting the nonnegativity constraints for some decision variables: xj unrestricted in sign for some values of j. Converting into Standard Form Slack/surplus variables Replacing ‘free’ variables Minimization is converted to maximization HSLee@SKKU

Linear Programming Terminology Solution: any set of (x1, …,xn) Feasible solution: all constraints satisfied Optimal solution: no better solution exists Corner point feasible (CPF): a solution that lies at the corner of the feasible region. Corner point feasible solution lies at a corner of the feasible region. That is, it lies at the intersection of n constraints, where n is the number of decision variables. If there is an optimal solution, then there is always a corner point feasible solution. HSLee@SKKU

Linear Programming An LP can have a unique optimal solution. This is always a corner point. LP can have multiple optimal solutions. At least two corner points are optimal. There are infinite optimal solutions lying on the line between the two CPF. HSLee@SKKU

Linear Programming LP can be infeasible. LP can be unbounded The constraints are such that no point exists that satisfies all the contraints. LP can be unbounded HSLee@SKKU

3.3 Assumptions of LP Linear objective function, constraints Proportionality: The contribution of each activity to the value of the objective function is proportional to the level of activity. Additivity: Every function in the LP model is the sum of the individual contributions of the respective activities (Interaction not allowed) Divisibility Continuous decision variables cf. Integer variable Certainty Deterministic parameters (The value assigned to each parameter of a linear programming model is assumed to be a known constant.) cf. stochastic programming HSLee@SKKU

Violating Proportionality Case 1 of Table 3.4 HSLee@SKKU

Violating Proportionality Case 2 of Table 3.4 Case 3 of Table 3.4 HSLee@SKKU

Violating Additivity HSLee@SKKU

Violating Divisibility & Certainty Divisibilty Certainty 2 4 6 8 10 12 8 6 4 2 x1 > 0 , x2 > 0 or x1 > 0 , x2 > 0 & integers Max Z = 3X1 + 5X2 s.t. X1 < 8 X2 < 6 3X1 + 4X2 < 36 X1 > 0 , X2 > 0 How certain are we of this demand? HSLee@SKKU

Homework Solve the following Problems 3.1-6 3.1-7 3.2-4 3.2-5 3.3-1 (교과서 Typo: “문제 3.2.13을 다시 고려하라”  “문제 3.2.3을 다시 고려하라”) HSLee@SKKU

3.4 Additional Examples Page 47. Design of Radiation Therapy Page 51. Regional Planning of Kibbutzim Page 53. Controlling Air Pollution Page 56. Reclaiming Solid Waste Page 60. Personnel Scheduling Page 63. Distributing Goods in a Network HSLee@SKKU

Page 47 Design of Radiation Therapy Mary 상당히 진전된 상태의 암 방광 부근에 대형 종양 방사선 시술 이온화된 방사선 빔: 암 세포 조직은 물론 건강한 세포 조직도 파괴 몇 가지 방사선 빔이 2차원상의 서로 다른 각도로 정교하게 시술 감쇠효과: 출구점 주변의 조직보다 진입점 주변의 조직에 더 많은 방사선이 있음 산란현상: 방사선 빔의 직접적인 경로 바깥의 조직에도 방사선이 도달 암 세포는 보통 현미경적으로 작은 단위로 정상 세포 사이에 퍼져 있고, 암 세포는 정상 세포보다 조금 더 전파에 민감 방사선이 암세포 지역에 충분히 강하게 조사되어 암 세포를 죽일 수 있어야 하며 너무 강하게 조사되지 않아서 건강한 세포를 죽이지 말아야 함 HSLee@SKKU

Radiation Therapy: Formulation 영역 진입점에서의 방사선량 총 조사량 제한, 킬로래드 빔 1 빔 2 건강한 세포조직 0.4 0.5 Minimize 중요 장기 0.3 0.1  2.7 전체 암세포 = 6.0 암세포 중심부 0.6  6.0 Variables: x1 = amount of dose at the entry point by beam 1 x2 = amount of dose at the entry point by beam 2 Minimize: (Total absorption by healthy anatomy) 0.4 x1 + 0.5 x2 Subject to 0.3 x1 + 0.1 x2  2.7 (Absorption by critical tissues) 0.5 x1 + 0.5 x2 = 6 (Absorption by tumor region) 0.6 x1 + 0.4 x2  6 (Absorption by center of tumor) x1, x2  0 HSLee@SKKU

Radiation Therapy: Solution 12 .5x+.5y=6 x y 9 10 .3x+.1y=2.7 .6x+.4y = 6 (7.5,4.5), Z= 5.25 (6,6) Objective function contour 그래프 사용하여 구하는 해 가능 해 영역은 (6, 6), (7.5, 4.5)를 연결하는 청색의 선분 하나의 항등식 제약조건은 가능 해 영역을 이 선분을 포함하는 선분으로 한정, 다른 두 개의 기능 제약식은 이 선분의 양 끝점을 결정 점선은 Z = 5.25를 갖는 (x1, x2) = (7.5, 4.5)의 최적 해를 지나는 목적함수 CFP (7.5, 4.5)의 Z= 5.25 < CFP (6,6)의 Z = 5.4     방사선 빔 1은 7.5 킬로래드, 방사선 빔 2는 4.5 킬로래드를 조사하는 것이 최적 HSLee@SKKU

Excel for Radiation Therapy Mary's Radiation Therapy Problem Fraction of Entry Dose Range Name Cells Absorbed by Area (Average) Total Restriction on DosageRestriction G7:G9 Beam 1 Beam 2 Dosage Total Average EntryDosage C11:D11 Healthy Anatomy 0.4 0.5 5.25 Dosage (Kilorads) FractionAbsorbed C6:D9 Critical Tissues 0.3 0.1 2.7 <= TotalDosage E6:E9 Tumor Region 6 = TotalDosageToHealthyAnatomy E6 Center of Tumor 0.6 6.3 >= Entry Dosage (kilorads) 7.5 4.5 HSLee@SKKU

Radiation Therapy-LINGO ! Design for Radiation Therapy. LINGO model; [Exposure] MIN = 0.4 * X1 + 0.5 * X2; [Critical] 0.3 * X1 + 0.1 * X2 <= 2.7; [Tumor] 0.5 * X1 + 0.5 * X2 = 6.0; [Center] 0.6 * X1 + 0.4 * X2 >= 6.0; HSLee@SKKU

Radiation Therapy: MPL Input TITLE MarysRadiationTherapy; INDEX i := 1..2; {(Beam1, Beam2)} j := 1..3; {(CriticalTissues, TumorRegion, CenterTumor)} DATA aH[i] := (0.4, 0.5); {HealthyAnatomy} aC[j,i] := (0.3,0.1, 0.5,0.5, 0.6,0.4); {Absorption in area j by beam i} {aC[i,j] := (0.3, 0.5, 0.6,0.1, 0.5, 0.4);} R[j] := (2.7, 6.0, 6.0); {Restriction on each area} VARIABLE x[i]; {Dosage} MODEL MIN HealthyDosage = SUM(i: aH * x); SUBJECT TO Restrict[j=1] : SUM(i: aC * x) <= R; Restrict[j=2] : SUM(i: aC * x) = R; Restrict[j=3] : SUM(i: aC * x) >= R; END HSLee@SKKU

Page 51. Regional Planning of Kibbutzim 남부 키부츠 연합 (SOUTHERN CONFEDERATION OF KIBBUTZIM): 이스라엘의 3개의 키부츠 연합체 이 그룹을 위한 전반적인 계획은 기술조정 사무소(Coordinating Technical Office)에서 수행 현재 이 사무소는 내년도 농업 계획을 수립 중 각각의 키부츠의 농업 산출물은 경작가능한 농지의 크기와 수자원 위원회가 관리하는 용수의 양에 의해 제한 표 3.8 남부 키부츠 연합의 자원 자료 표 3.9 남부 키부츠 연합의 경작물 자료 키부츠 경작 가능 농지 (에이커) 수자원 배분 (에이커*피트) 1 400 600 2 800 3 300 375 작물 최대 경작지 할당량 수자원 사용 (피트/에이커) 순이익 (달러/에이커) 사탕무우 600 3 1,000 면화 500 2 750 사탕수수 325 1 250 표 3.10 남부 키부츠 연합 문제의 의사결정 변수 작물 경작지 할당량 (에이커) 키부츠 1 2 3 사탕무우 x1 x2 x3 면화 x4 x5 x6 사탕수수 x7 x8 x9 HSLee@SKKU

Regional Planning of Kibbutzim: Formulation 목적함수:   Z의 효율성에 대한 척도는 총 수익 Maximize Z = 1,000(x1 + x2 + x3) + 750(x4 + x5 + x6) + 250(x7 + x8 + x9) 제약 조건 1. 각각의 키부츠의 사용가능한 경작지 2. 각각의 키부츠의 용수 할당: 3. 각각의 경작물의 총 면적 제한 4. 경작지의 비율 형평성 5. 비음 조건 HSLee@SKKU

Regional Planning of Kibbutzim: Excel Southern Confederation of Kibbutzim Regional Planning Problem Sugar Beets Cotton Sorghum Range Name Cells Net Return (per acre) $1,000 $750 $250 AcresPlanted C10:E12 CropsPlanted C13:E13 Water Consumption (per acre) 3 2 1 MaximumQuota C15:E15 Total NetReturn C4:E4 Acres Planted Acres Usable Proportion Water TotalAcresPlanted F10:F12 Planted Land Used Required Allocation TotalNetReturn I15 Kibbutz 1 133.333 100 233.333 <= 400 0.583 600 UsableLand H10:H12 Kibbutz 2 250 350 800 WaterAllocation M10:M12 Kibbutz 3 25 150 175 300 375 WaterConsumption C6:E6 Total Crops Planted (acres) 258.333 500 (all constrained =) WaterRequired K10:K12 Maximum Quota (acres) 325 Total Net Return $633,333.33 HSLee@SKKU

Regional Planning: LINDO input Max Return)1000 X1+1000 X2+1000 X3+750 X4 +750 X5+750 X6 + 250 X7+ 250 X8 + 250 X9 Subject to Land1) x1 + x4 + x7 <= 400 Land2) x2 + x5 + x8 <= 600 Land3) x3 + x6 + x9 <= 300 Water1) 3 x1 + 2 x4 + x7 <= 600 Water2) 3 x2 + 2 x5 + x8 <= 800 Water3) 3 x3 + 2 x6 + x9 <= 375 Crop1) x1 + x2 + x3 <= 600 Crop2) x4 + x5 + x6 <= 500 Crop3) x7 + x8 + x9 <= 325 !Prop1) (x1 + x4 + x7)/400 = (x2 + x5 + x8)/600 Prop1) 3 x1 + 3 x4 + 3 x7 - 2 x2 - 2 x5 - 2 x8 = 0.0 !Prop2) (x2 + x5 + x8)/600 = (x3 + x6 + x9)/300 Prop2) x2 + x5 + x8 - 2 x3 - 2 x6 - 2 x9 = 0.0 END HSLee@SKKU

Regional Planning: LINGO input MODEL: TITLE: Kibbutzim ; ! This Lingo formulation of the linear program is scalable. SETS: ! The structure of the data; Crop : Quota, Water, Return; Kibbutz : Acres, WaterA; Alloc(Crop, Kibbutz) : X; ENDSETS DATA: ! The actual data for this instance; Crop, Quota, Water, Return = Beets 600 3 1000 Cotton 500 2 750 Sorg 325 1 250; Kibbutz, Acres, WaterA = K1 400 600 K2 600 800 K3 300 375; ENDDATA HSLee@SKKU

Regional Planning: MPL input TITLE KibbutzimCropAllocation; INDEX k := 1..3; {kibbutz} c := 1..3; {(SugarBeets, Cotton, Sorghum)} DATA L[k] := (400, 600, 300); {Usable Land} [Acres] W[k] := (600, 800, 375); {Water available} [AcreFeet] wc[c]:= (3, 2, 1); {Water consumption} [AcreFeet/Acre] R[c] := (1000, 750, 250); {Net return} [$/Acre] Q[c] := (600, 500, 325); {Quota for each crop} [Acres] VARIABLES x[k,c]; {Acres allocated in kibutz k for crop c} MODEL MAX Profit = SUM(k,c: R * x); SUBJECT TO Land[k]: SUM(c: x) <= L; Water[k]: SUM(c: wc * x) <= W; Quota[c]: SUM(k: x) <= Q; Balance1: SUM(k=1,c: x / L) = SUM(k=2,c: x / L); Balance2: SUM(k=2,c: x / L) = SUM(k=3,c: x / L); END HSLee@SKKU

Page 51. Air Pollution Controlling Nori & Leets: A Steel Company Three pollutants: particulate matter, sulfur oxides, hydrocarbons Annual requirements of reduction of these (60, 150, 125 million pounds) Activities: some pollution abatement methods Each activity reduce different amount of each pollutant Performance measure: Minimizing pollution control cost with satisfying goals of pollution reduction HSLee@SKKU

Air Pollution Controlling: Formulation 표 3.13 Nori & Leets 회사의 가능 경감 대책의 사용을 통한 배출율의 감소   굴뚝 높이 개선 필터 장치 사용 연료 첨가 사용 오염 형태 용광로 평로 미립자 물질 12 9 25 20 17 13 유황산화물  35 42 18 31 56 49 탄화수소 37 53 28 14 29 Minimize Z = 8x1 + 10x2 + 7x3 + 6x4 + 11x5 + 9x6 1. 배출 감소: 12x1 + 9x2 + 25x3 + 20x4 + 17x5 + 13x6 >= 60 35x1 + 42x2 + 18x3 + 31x4 + 56x5 + 49x6 >= 150 37x1 + 53x2 + 28x3 + 24x4 + 29x5 + 20x6 >= 125 2. 기술적 제한: xj <= 1, for j = 1, 2, ..., 6 3. 비음조건: xj >= 0, for j = 1, 2, ..., 6. 표 3.15 감소 대책의 최대 사용의 부분 비율 의사결정 변수 개선 방법 용광로 평로 굴뚝 높이 개선  x1 x2  필터 장치 사용 x3 x4 연료 첨가 사용 x5 x6 HSLee@SKKU

Controlling Air Pollution: LINDO Input TITLE Nori & Leets Co.; MIN 8XTBF+10XTOH+7XFIBF+6XFIOH +11XFUBF+9XFUOH SUBJECT TO PART)12XTBF+9XTOH+25XFIBF+20XFIOH+17XFUBF+13XFUOH>=60 SO)35XTBF+42XTOH+18XFIBF+31XFIOH+56XFUBF+49XFUOH>=150 HC)37XTBF+53XTOH+28XFIBF+24XFIOH+29XFUBF+20XFUOH>=125 TCHTALBF) XTBF <= 1 TCHTALOH) XTOH <= 1 TCHFILBF) XFIBF <= 1 TCHFILOH) XFIOH <= 1 TCHFULBF) XFUBF <= 1 TCHFULOH) XFUOH <= 1 END HSLee@SKKU

Controlling Air Pollution: LINGO ! Nori & Leets Co. LINGO model, sets based; MODEL: TITLE: NoriLeets; SETS: ! There is a set of Pollutants; Poll :EmissRate; ! a set of Abatement methods; Abat; ! and a set of Furnace types; Furn ; ! Decision set; Dec(Abat, Furn) : Cost, x; R(Poll, Abat, Furn) : Rate; ENDSETS DATA: ! Pollutants considered; Poll = Part, SO, HC; ! Abatement methods; Abat = Tall, Fil, Fuel; ! Furnace types; Furn = BF, OH; ! Required Reduction in Annual Emission Rate; EmissRate = 60 150 125; Rate = !( Poll x ABat x Furn); 12 9 25 20 17 13 35 42 18 31 56 49 37 53 28 24 29 20; Cost = 8 10 7 6 11 9; ENDDATA [TCost] MIN = @SUM( Dec (i,j) : Cost(i,j) * x(i,j)); @FOR(Poll (i) : [ReqRed] @SUM(Dec (j,k) : Rate(i,j,k) * x(j,k)) >= EmissRate(i); ); @FOR(Dec(i,j) : [Tch] x(i,j) <= 1.0;); END HSLee@SKKU

Page 57. Reclaiming Solid Waste Product Data for the Save-It Company Grade Specification Amalgamation Cost per Pound Selling Price per Pound A Material 1: Not more than 30% of total Material 2: Not less than 40% of total Material 3: Not more than 50% of total Material 4: Exactly 20% of total $3.00 $8.50 B Material 1: Not more than 50% of total Material 2: Not less than 10% of the total Material 4: Exactly 10% of the total 2.50 7.00 C Material 1: Not more than 70% of the total 2.00 5.50 Table 4.9 Product data for the Save-It Company. Material Data for the Save-It Company Material Pounds/Week Available Treatment Cost per Pound Additional Restrictions 1 3,000 $3.00 1. For each material, at least half of the pounds/week available should be collected and treated. 2. $30,000 per week should be used to treat these materials. 2 2,000 6.00 3 4,000 4.00 4 1,000 5.00 HSLee@SKKU

Reclaiming Solid Waste: Formulation yi = 주당 등급 i의 제품을 생산하는 양 (파운드 단위) (i = A, B, C) zij = 물질 j가 등급 i 제품에 있는 비율 (i = A, B, C; j = 1, 2, 3, 4). 그러나 표 3.17은 처리 비용과 가용한 물질의 양을 비율이 아닌 파운드 단위로 제시하고 있어서, 이런 용량의 정보가 제약식에 기록될 필요 발생  물질 j, ( j = 1, 2, 3, 4)에 대해 주당 필요로 하는 물질 j의 (파운드 단위) 용량은 zAj yA + zBj yB + zCj yC zA1 yA + zB1 yB + zC1 yC <= 3,000  비선형 Formulation 2 xij = zij yi (for i = A, B, C; j = 1, 2, 3, 4) = 1주일에 등급 i 제품에 사용된 물질 j의 파운드 량, xij를 서로 다른 방법으로 결합하면 모형에 필요한 다음과 같은 용량들이 산출된다. xi1 + xi2 + xi3 + xi4 = 1주일에 등급 i에 생산한 용량 (파운드) xAj + xBj + xCj = 1주일에 물질 j를 사용한 용량 (파운드) 등급 i에 들어있는 물질 j의 비율: HSLee@SKKU

Algebraic Formulation for Save-It Co. Let xij = Pounds of material j allocated to product i per week (i = A, B, C; j = 1, 2, 3, 4). Maximize Profit = 5.5(xA1 + xA2 + xA3 + xA4) + 4.5(xB1 + xB2 + xB3 + xB4) + 3.5(xC1 + xC2 + xC3 + xC4) subject to Mixture Specifications: xA1 ≤ 0.3 (xA1 + xA2 + xA3 + xA4) xA2 ≥ 0.4 (xA1 + xA2 + xA3 + xA4) xA3 ≤ 0.5 (xA1 + xA2 + xA3 + xA4) xA4 = 0.2 (xA1 + xA2 + xA3 + xA4) xB1 ≤ 0.5 (xB1 + xB2 + xB3 + xB4) xB2 ≥ 0.1 (xB1 + xB2 + xB3 + xB4) xB4 = 0.1 (xB1 + xB2 + xB3 + xB4) xC1 ≤ 0.7 (xC1 + xC2 + xC3 + xC4) Availability of Materials: xA1 + xB1 + xC1 ≤ 3,000 xA2 + xB2 + xC2 ≤ 2,000 xA3 + xB3 + xC3 ≤ 4,000 xA4 + xB4 + xC4 ≤ 1,000 Restrictions on amount treated: xA1 + xB1 + xC1 ≥ 1,500 xA2 + xB2 + xC2 ≥ 1,000 xA3 + xB3 + xC3 ≥ 2,000 xA4 + xB4 + xC4 ≥ 500 Restriction on treatment cost: 3(xA1 + xB1 + xC1) + 6(xA2 + xB2 + xC2) + 4(xA3 + xB3 + xC3) + 5(xA4 + xB4 + xC4) = 30,000 and xij ≥ 0 (i = A, B, C; j = 1, 2, 3, 4). HSLee@SKKU

Spreadsheet Formulation for Save-It Co. HSLee@SKKU

Reclaiming Solid Wastes: LINDO Input MAX 5.5XAM1+5.5 XAM2 +5.5 XAM3 + 5.5 XAM4 + 4.5 XBM1 + 4.5 XBM2 + 4.5 XBM3 + 4.5 XBM4 + 3.5 XCM1 + 3.5 XCM2 + 3.5 XCM3 + 3.5 XCM4 SUBJECT TO MixA1) .7 XAM1 - .3 XAM2 - .3 XAM3 - .3 XAM4 <= 0 MixA2) -.4 XAM1 + .6 XAM2 - .4 XAM3 - .4 XAM4 >= 0 MixA3) -.5 XAM1 - .5 XAM2 + .5 XAM3 - .5 XAM4 <= 0 MixA4) -.2 XAM1 - .2 XAM2 - .2 XAM3 + .8 XAM4 = 0 MixB1) .5 XBM1 - .5 XBM2 - .5 XBM3 - .5 XBM4 <= 0 MixB2)- .1 XBM1 + .9 XBM2 - .1 XBM3 - .1 XBM4 >= 0 MixB4)- .1 XBM1 - .1 XBM2 - .1 XBM3 + .9 XBM4 = 0 MixC1) .3 XCM1 - .7 XCM2 - .7 XCM3 - .7 XCM4 <= 0 Availm1) XAM1 + XBM1 + XCM1 <= 3000 Availm2) XAM2 + XBM2 + XCM2 <= 2000 Availm3) XAM3 + XBM3 + XCM3 <= 4000 Availm4) XAM4 + XBM4 + XCM4 <= 1000 Treatmn1) XAM1 + XBM1 + XCM1 >= 1500 Treatmn2) XAM2 + XBM2 + XCM2 >= 1000 Treatmn3) XAM3 + XBM3 + XCM3 >= 2000 Treatmn4) XAM4 + XBM4 + XCM4 >= 500 CostRsrt) 3 XAM1 + 6 XAM2 + 4 XAM3 + 5 XAM4 + 3 XBM1 + 6 XBM2 + 4 XBM3 + 5 XBM4 + 3 XCM1 + 6 XCM2 + 4 XCM3 + 5 XCM4 = 30000 HSLee@SKKU

Reclaiming Solid Wastes: LINGO ! Save-it Company. LINGO model(LING03e); MODEL: TITLE Saveit; SETS: Grade : Cost, Price; Mat : Avail, Treat; Spec(Grade, Mat) : Mn, Mx, x; ! Minimum and maximum percent; ENDSETS DATA: Grade, Cost, Price = A 3.00 8.50 B 2.50 7.00 C 2.00 5.50; Mat, Avail, Treat = M1 3000 3.00 M2 2000 6.00 M3 4000 4.00 M4 1000 5.00; ! Mn is the minimum percent of a material in a grade.; Mn = 0 40 0 20 0 10 0 10 0 0 0 0; ! Mx is the maximum percent of a material in a grade.; Mx = 30 100 50 20 50 100 100 10 70 100 100 100; Contri = 30000; ENDDATA Max = @SUM(Spec(g,m) : (Price(g) - Cost(g))* x(g,m)); @FOR( Grade(g) : @FOR(Mat(m) : x(g,m) <= Mx(g,m)/100 *@SUM(Mat(i) : x(g,i)); x(g,m) >= Mn(g,m)/100 *@SUM(Mat(i) : x(g,i)); ); @FOR( Mat(m) : @SUM(Grade(g) : x(g,m)) <= Avail(m); @SUM(Grade(g) : x(g,m)) >= 0.5 * Avail(m); @SUM(Spec(g,m) : Treat(m) * x(g,m) ) = Contri; END HSLee@SKKU

Reclaiming Solid Wastes: MPL Input TITLE SaveItCompany; INDEX i:= (A, B, C); {grade} j := 1..4; {material} DATA MixL[i,j]:=[A,2,0.4, A,4,0.2, B,2,0.1, B,4,0.1]; MixU[i,j]:=[A,1,0.3,A,3,0.5,A,4,0.2,B,1,0.5,B,4,0.1,C,1,0.7]; AC[i] := (3, 2.5, 2); {AmalgamCost} Price[i] := (8.5, 7, 5.5); Material[j] := (3000, 2000, 4000, 1000); TreatCost[j] := (3, 6, 4, 5); VARIABLES x[i, j]; {Material j in grade i} MODEL MAX Profit = SUM(i,j: Price*x) - SUM(i, j: AC * x); SUBJECT TO MinSpecs[i,j] WHERE MixL > 0 : x >= MixL * SUM(j: x); MaxSpecs[i,j] WHERE MixU > 0 : x <= MixU * SUM(j: x); MaterialLimit[j] : SUM(i: x) <= Material; MinTreatedMat[j] : SUM(i: x) >= 0.5*Material; MinTreatCost: SUM(i, j: TreatCost * x) = 30000; END HSLee@SKKU

Page 60. Personnel Scheduling Small sized version of United Airline (Union Airways) Problem: adding more flights to and from its hub airport and so needs to hire additional customer service agents Activities: shifts Level of an activity: the number of agents of the shift The five authorized eight-hour shifts are Shift 1: 6:00 AM to 2:00 PM Shift 2: 8:00 AM to 4:00 PM Shift 3: Noon to 8:00 PM Shift 4: 4:00 PM to midnight Shift 5: 10:00 PM to 6:00 AM Benefits: required number of agents of a time period Performance measure: minimize staffing cost Question: How many agents should be assigned to each shift? HSLee@SKKU

Schedule Data for Union Airways Time period Shift coverage (8 hr each) Number of agents needed 1 2 3 4 5 6-8 AM 48 8-10 79 10-12 65 12-2PM 87 2-4 64 4-6 73 6-8 82 43 10-12AM 52 12-6 15 Cost/agent-day 170 160 175 180 195 Table 4.4 Data for the Union Airways personnel scheduling problem HSLee@SKKU

Algebraic Formulation for Union Air Let xj = Number working shift j (for j = 1 to 5), Minimize Cost = $170 x1 + $160 x2 + $175 x3 + $180 x4 + $195 x5 subject to Total agents 6AM–8AM: x1 ≥ 48 Total agents 8AM–10AM: x1 + x2 ≥ 79 Total agents 10AM–12PM: x1 + x2 ≥ 65 Total agents 12PM–2PM: x1 + x2 + x3 ≥ 87 Total agents 2PM–4PM: x2 + x3 ≥ 64 Total agents 4PM–6PM: x3 + x4 ≥ 73 Total agents 6PM–8PM: x3 + x4 ≥ 82 Total agents 8PM–10PM: x4 ≥ 43 Total agents 10PM–12AM: x4 + x5 ≥ 52 Total agents 12AM–6AM: x5 ≥ 15 and xj ≥ 0 (for j = 1 to 5) HSLee@SKKU

Figure 4.3 Union Airways Personnel Scheduling Problem HSLee@SKKU

Personnel Scheduling: LINDO TITLE Union Airways staff scheduling; MIN 170 X1 + 160 X2 + 175 X3 + 180 X4 + 195 X5 SUBJECT TO HR06AM) X1 >= 48 HR08AM) X1 + X2 >= 79 HR10AM) X1 + X2 >= 65 HRNOON) X1 + X2 + X3 >= 87 HR02PM) X2 + X3 >= 64 HR04PM) X3 + X4 >= 73 HR06PM) X3 + X4 >= 82 HR08PM) X4 >= 43 HR10PM) X4 + X5>= 52 HRMIDN) X5 >= 15 END HSLee@SKKU

Personnel Scheduling: LINGO ! Union Airways Personnel Scheduling. LINGO model(LING03f); MODEL: TITLE Union Airways; SETS: Period / 1..10 / : MinAgents; Shift / 1..5 / : Cost, Agents; PerShift( Period, Shift) : Coverage; ENDSETS DATA: MinAgents = 48 79 65 87 64 73 82 43 52 15; Cost = 170 160 175 180 195; Coverage = 1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1; ENDDATA HSLee@SKKU

Personnel Scheduling: MPL Input TITLE UnionAirwaysPersonnel; INDEX shift := 1..5; period := (AM_6_8, AM_8_10, AM_10_12, PM_12_2, PM_2_4, PM_4_6, PM_6_8, PM_8_10, PM_10_12, AM_12_6); ShiftSchedule[shift, period] := (1, AM_6_8, 1, AM_8_10, 1, AM_10_12, 1, PM_12_2, 2, AM_8_10, 2, AM_10_12, 2, PM_12_2, 2, PM_2_4, 3, PM_12_2, 3, PM_2_4, 3, PM_4_6, 3, PM_6_8, 4, PM_4_6, 4, PM_6_8, 4, PM_8_10, 4, PM_10_12, 5, PM_10_12, 5, AM_12_6); DATA MinAgentsNeeded[period]:=(48, 79, 65, 87, 64, 73, 82, 43, 52, 15); DailyCostPerAgent[shift]:= (170, 160, 175, 180, 195); VARIABLES AssignAgents[shift] -> Agents; MODEL MIN TotalCost =SUM(shift: DailyCostPerAgent*AssignAgents); SUBJECT TO MeetRequirements[period]: SUM(shift IN ShiftSchedule: AssignAgents) >= MinAgentsNeeded; END HSLee@SKKU

Personnel Scheduling: MPL Input TITLE UnionAirwaysPersonnel; INDEX i := 1..5; {5 shifts} j := 1..12 ; {12 two-hour time slots} Schedule[i, j] := (1,1, 1,2, 1,3, 1,4, 2,2 2,3, 2,4, 2,5, 3,4, 3,5, 3,6, 3,7, 4,6, 4,7, 4,8, 4,9, 5,9, 5,10, 5,11, 5,12); {Each shift covers 8 hrs} DATA N[j]:=(48,79,65,87,64,73,82,43,52,15,15,15); C[i]:= (170, 160, 175, 180, 195); VARIABLES x[i]; MODEL MIN SUM(i: C*x); SUBJECT TO Requirements[j]: SUM(i IN Schedule: x) >= N; END HSLee@SKKU

Page 63. Distributing Goods in a Network  DISTRIBUTION UNLIMITED CO. 한 상품을 두 개의 다른 공장에서 생산하고 두 개의 창고로 운반 어느 공장에서든  어느 창고로도 보낼 수 있음 수송을 위한 유통 네트워크는 그림 3.13 F1, F2는 두 개의 공장, W1, W2는 두 개의 창고를 의미, DC는 배송센터 의미 F1이나 F2로부터 보낼 용량의 상한은 공장을 나타내는 원의 왼쪽에 표시, W1과 W2에서 받을 용량의 상한은 창고를 나타내는 원의 오른쪽에 표시 HSLee@SKKU

Distributing Goods in a Network: Formulation 1. 흐름 보존 조건: 유출 흐름의 양 - 유입 흐름의 양 = 필요한 양 2. 상한 조건: 3. 비음 조건 Table 4.5 Some data for the Big M Company distribution-network problem HSLee@SKKU

Distribution Network: EXCEL Spreadsheet model Requirement F1-F2 F1-DC F1-W1 F2-DC DC-W2 W1-W2 W2-W1 Actual flow 　Required　 F1 1 50 = F2 -1 40 DC W1 -30 W2 -60 Capacity 10 80 Unit Cost ($100) 2 4 9 3 490 Solution 20 HSLee@SKKU

Distribution Network: LINGO ! Distribution Unlimited Co.; MODEL: TITLE Distribution Unlimited; SETS: ! The set of locations includes all three types of location; Loc : Prod, Need; Link (Loc, Loc) : UCost, Cap, x; ENDSETS DATA: Loc, Prod, Need = F1 50 0 F2 40 0 W1 0 30 W2 0 60 DC 0 0; UCost= !( F1 F2 W1 W2 DC); 0 200 900 0 400 ! F1; 0 0 0 0 300 ! F2; 0 0 0 300 0 ! W1; 0 0 200 0 0 ! W2; 0 0 0 100 0;! DC; Cap = !( F1 F2 W1 W2 DC) A capacity of zero means there is capacity limit; 0 10 0 0 0 ! F1; 0 0 0 0 0 ! F2; 0 0 0 0 0 ! W1; 0 0 0 0 0 ! W2; 0 0 0 80 0;! DC; ENDDATA [TCost] Min = @SUM (Link(i,j) | UCost(i,j) #NE# 0.0 : UCost(i,j) * x(i,j)); @For (Loc(i) : [Node] @Sum (Link (i, j) | UCost(i,j) #NE# 0.0 : x(i,j)) -@Sum (Link (j, i) | UCost(j,i) #NE# 0.0 : x(j,i)) = Prod(i) -Need(i); ); @FOR (Link(i,j) | Cap(i,j) #NE# 0.0 : [PCap] @BND( 0.0, x(i,j), Cap(i,j)); END HSLee@SKKU

3.5 Spreadsheet Solution Range name Data cells Target cell Output cells Changing cells Solver HSLee@SKKU

Loading Solver Standard with old version of Excel Insert MS Office or Excel master CD Click on “Add/Delete” components Open “Add-In” tools Click on “Solver” or “add all” Click “OK” Solver should now appear in the “Tools” menu Standard with 2007 Excel version Home 스위치에서 Excel 옵션 탭 추가기능 – 해찾기 – Excel 추가기능 이동 – 해찾기 기능을 체크. 확인 설치되면 데이터 메뉴 중 해찾기가 나타남 Standard with 2010 Excel version 파일 메뉴에서 옵션 탭 선택 창이 뜨면 추가기능 탭에서 아래 관리 “Excel 추가 기능”으로 이동 해찾기 기능을 체크. 확인 HSLee@SKKU

3.5 Spreadsheet Fig. 3.16 범위 (range)의 이름 이용 범위 이름을 입력하려면 HSLee@SKKU 범위 이름 (range name)은 범위 지정한 블록 단위의 셀을 묘사하는 내용으로 결정 Wyndor 문제의 자료 셀에 주어진 이름은: UnitProfit (C4:D4), HoursUsedPerUnitProduced (C7:D9), HoursAvailable (G7:G9) 범위 이름은 단어간에 빈 칸을 허용하지 않고, 각 단어는 대문자로 시작 범위 이름이 주어진 셀의 범위가 범위 이름 다음에 소괄호 ()를 사용하여 명시될 수 있다. (예를 들면, Excel의 C7:D9 범위는 C7부터 D9까지의 범위 - 즉 C, D 열의 7, 8, 9 행의 모든 셀의 블록을 약칭한다.) 범위 이름을 입력하려면 이름을 지정할 셀, 셀 범위 또는 인접하지 않은 선택 영역을 선택, 수식 입력줄의 왼쪽 끝에서 이름 상자를 클릭, 선택 영역을 참조하는 데 사용할 이름을 입력 이름에는 255자까지 사용할 수 있음. 이름을 만드는 추가 규칙에 대한 자세한 내용은 이름의 구문 규칙에 대한 자세한 정보 섹션을 참고. Enter 키를 입력 HSLee@SKKU

3.6 Spreadsheet Fig. 3.16 제약식 반영 목적함수 작성 Target Cell Changing Cells E7 = C7*C12 + D7*D12 E8 = C8*C12 + D8*D12 E9 = C9*C12 + D9*D12 목적함수 작성 G12 = SUMPRODUCT(C4:D4, C12:D12) 또는 TotalProfit = SUMPRODUCT(ProfitPerBatch, BatchesProduced) Target Cell Changing Cells Output Cells HSLee@SKKU

3.5 Spreadsheet Fig. 3.16 HSLee@SKKU

3.5 Spreadsheet Fig. 3.17 HSLee@SKKU

3.5 Spreadsheet Fig. 3.18 HSLee@SKKU

3.5 Spreadsheet Fig. 3.19 HSLee@SKKU

3.5 Spreadsheet Fig. 3.20 HSLee@SKKU

3.5 Spreadsheet Fig. 3.21 HSLee@SKKU

3.5 Spreadsheet Fig. 3.22 HSLee@SKKU

3.6 Large Models Modeling Languages Citgo had 3000 functional constraints and 15000 decision variables Need for a modeling language You can learn MPL and Lingo with the attached CD HSLee@SKKU

LINDO (see 부록 4.1 in pages 154 ~ 157) LINGO can be downloaded from the textbook web site You can download the latest “student” version of LINGO from: http://www.lindo.com. When downloading it, note the name of the file (typically Lingo9.exe) and the directory into which it was downloaded. You install it by running the Lingo9.exe file that was downloaded into this directory. Installation takes about one minute. Lindo is now a subset of the Lingo package LINGO | Options | Interface | File Format | ltx (LINDO) | Apply. LINGO | Options | Interface | File Format | lg4 or lng(LINGO) | Apply. HSLee@SKKU

Using LINDO to Solve LPs Use a plain text file as input file: no super/subscripts case insensitive Title is optional. Begin with “Max” or “Min” Objective function is given as a sum of terms. Each term has a coefficient constant (number) and a variable name (beginning with a letter) (Ex) “3 x11”  3 is a coefficient and x11 is a variable name (Note) One or more spaces between a coefficient and a variable is considered as multiplication. However, no space between numbers or letters are allowed in a coefficient or in a variable name. HSLee@SKKU

Using LINDO to Solve LPs Below the objective function is the system command “Subject to” followed by a series of constraints. Each constraint consists of LHS, (in)equality sign, and RHS. LHS is a sum of terms like the objective function Use “>” or “>=“ for “” (Note) By continuity assumption, “>” is interpreted as “>=“. Use and < or “<=“ for “” Do not use “/” as a notation for division (Ex) “x1/x2 > 2”  “x1 - 2 x2 > 0” RHS must be a single constant (number) term. No variable should be in the RHS. (Ex) “x1 > 2 x2” will cause an error message. HSLee@SKKU

LINDO for Wyndor Glass Co. TITLE Wyndor Glass Co. Problem. LINDO model ! X1 = batches of product 1 per week ! X2 = batches of product 2 per week ! Profit, in 1000 of dollars MAX 3 X1 + 5 X2 Subject to ! Production time; Plant1) X1 <= 4 Plant2) 2 X2 <= 12 Plant3) 3 X1 + 2 X2 <= 18 END ! Latest version of LINGO can be downloaded ! from http://www.lindo.com HSLee@SKKU

LINGO Overview LINGO is a program for solving general optimization models, including linear models, integer models and nonlinear models. It contains a built-in users manual that can be accessed from the Lingo menu: Help | Help Topics | Contents | LINGO 11.0 User’s Manual.  Installation You can download the latest “student” version of LINGO for use with the Hillier text from: http://www.lindo.com/hillier. When downloading LINGO, note the name of the file (typically LINGO-WINDOWS-IA32-11.0.exe) and the directory into which it was downloaded. You install it by running the downloaded file and following the prompts. Installation takes about one minute. HSLee@SKKU

LINGO Lingo supports powerful set-based statements to create very large planning models with just a few statements It has very simple “hooks” that allow it to retrieve input data from and return results to spreadsheets, databases, and regular files. HSLee@SKKU

Wyndor Glass Co. Problem. LINGO model ! X1 = batches of product 1 per week; ! X2 = batches of product 2 per week; ! Profit, in 1000 of dollars; [Profit] MAX = 3*X1 + 5*X2; ! Production time; [Plant1] X1 <= 4; [Plant2] 2*X2 <= 12; [Plant3] 3*X1 + 2*X2 <= 18; !The latest student version of LINGO and What'sBest can be downloaded from textbook web site; HSLee@SKKU

LINGO Example Page 88 1, machine의 set, {Roll, Cut, Weld}. (index i처럼 생각) 2. product의 set, {P01, P02, P03, P04}. (index j처럼 생각) 이들 set의 구성원들에 대해서 attribute(속성)은 1. 각 machine 대한 attribute: 주당 생산가능한 시간  machine: ProdHoursAvail (bi처럼 생각) 2. 각 product에 대한 attribute: 단위 생산당 이익; 주당 생산한 단위 수  product: Profit, Produce (cj, xj처럼 생각) Machine 단위당 생산시간 주당 필요한 생산시간 (시간) Product P01 P02 P03 P04 Roll 1.7 2.1 1.4 2.4 28 Cut 1.1 2.5 2.6 34 Weld 1.6 1.3 0.8 21 단위 이익 26 35 25 37   HSLee@SKKU

LINGO Example  MaPr(machine, product): ProdHoursUsed 각 기계에서 각 제품의 한 단위가 만들어질 때 사용되는 생산시간  제품 하나와 기계 하나의 결합의 set의 각 구성원이 attribute가 됨. 이 집합은 두개의 간단한 set에서 유도되었으므로 derived set(유도된 집합) (index ij처럼 생각)  MaPr(machine, product): ProdHoursUsed LINGO의 문제 정립은 보통 다음 3개의 section을 갖는다. 1. SETS section: set들과 그들의 attribute를 명시. 이 section은 자료 의 구조를 묘사 2. DATA section: 사용되는 자료를 제공하고, 이것들이 어디서 얻어지 는 지를 표현 3. 수학적 모형 자체를 제공하는 section   HSLee@SKKU

LINGO Example HSLee@SKKU ! LINGO3h; ! Product mix example; SETS: !The simple sets; Machine: ProdHoursAvail; Product: Profit, Produce; !A derived set; MaPr( Machine, Product): ProdHoursUsed; ENDSETS DATA: !Get the names of the machines; Machine = Roll Cut Weld; ! Hours available on each machine; ProdHoursAvail = 28 34 21; ! Get the names of the products; Product = P01 P02 P03 P04; ! Profit contribution per unit; Profit = 26 35 25 37; ! Hours needed per unit of product; ProdHoursUsed = 1.7 2.1 1.4 2.4 ! Roll; 1.1 2.5 1.7 2.6 ! Cut; 1.6 1.3 1.6 0.8; ! Weld; ENDDATA ! Maximize total profit contribution; MAX = @SUM( Product(j): Profit(j) * Produce(j)); ! For each machine i; @FOR( Machine( i): ! Hours used must be hours available; @SUM( Product( j): ProdHoursUsed( i, j) * Produce( j)) <= ProdHoursAvail(i); ); HSLee@SKKU

LINGO Example @SUM( Product(j): Profit(j) * Produce(j)) @FOR(Machine(i): @SUM( Product(i): ProdHoursUsed(i, j) * Produce (j)) <= ProdHoursAvail (i, j); ); MAX = @SUM(Product(j): Profit(j) * Produce(j)); ! For each machine i; @FOR( Machine(i): ! Hours used must be hours available; @SUM( Product(j): ProdHoursUsed( i, j) * Produce( j)) <= ProdHoursAvail(i); ); HSLee@SKKU

LINGO: Union Airways HSLee@SKKU ! Union Airways Personnel Scheduling. LINGO model(LING03f); MODEL: TITLE Union Airways; SETS: Period / 1..10 / : MinAgents; Shift / 1..5 / : Cost, Agents; PerShift( Period, Shift) : Coverage; ENDSETS DATA: MinAgents = 48 79 65 87 64 73 82 43 52 15; Cost = 170 160 175 180 195; Coverage = 1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1; ENDDATA HSLee@SKKU

MPL + CPLEX의 사용 MPL은 다양한 선도적 solver (선형계획 모형 및 관련 모형을 푸는 소프트웨어 패키지)들을 지원 MPL 안에 설치될 수도 있음 CPLEX는 특히 유명하고 강력한 solver OR Courseware에 있는 MPL 버전은 이미 선형계획 모형을 풀기 위해 심플렉스 방법을 사용하는 학생용 버전의 CPLEX를 설치 MPL로 정립된 모형을 풀기 위해서 해야 되는 것은 단지 Run 메뉴에서 Solve CPLEX를 선택하거나 Toolbar에서 Run Solve를 누름 Status Window의 아래쪽의 View 버튼을 누르면 view window에서 solution 파일을 열 수 있다. HSLee@SKKU

MPL for Wyndor Glass { Exmpl3.1-1_WyndorGlass.mpl } { Hillier and Lieberman, Introduction to Operations Research, 8th ed. } { Chapter 3.1, Example 1, Product-mix, Size: 2x3, Page 26 } TITLE WyndorGlass; INDEX product := (Door, Window); plant := 1..3; DATA TimeAvail[plant] := (4, 12, 18); ProdTime[plant, product] := (1, 0, 0, 2, 3, 2); Profit[product] := (3000.00, 5000.00); VARIABLES Produce[product]; MODEL MAX TotalProfit = SUM(product: Profit * Produce); SUBJECT TO TimeCapacity[plant] -> TimeCap: SUM(product: ProdTime * Produce) <= TimeAvail; END HSLee@SKKU

WORLDWIDE CORPORATION 전 세계적으로 다양한 지역에 10개의 공장 이들 공장은 10개의 제품을 생산하고 그들을 각각의 지역에 판매 각각의 공장에서 이들 상품의 각각의 수요는 향후 10개월간 알려짐 생산이 수요보다 더 클 수 있고, 이 경우 남는 양은 다음 달에 팔리기 위해 재고로 남김 각 제품은 재고를 위해 동일 면적을 차지하며, 각 공장은 재고를 보관할 장소의 제한이 있음 각 공장은 똑같이 10개의 생산 프로세스(이들 프로세스를 기계라고 하자)를 가지고 있음 각각의 프로세스는 10개의 제품 중 어떤 것을 위해서도 사용될 수 있음 제품의 단위생산비용과 제품의 생산률(하루에 생산되는 제품의 단위 수)은 (매월 다른 것이 아니라) 공장과 기계의 조합에 의존하여 다르고 공장이 가동하는 날 (생산 가능일)은 매월 다소 다름 제품의 일부를 한 공장에서 다른 공장으로 수송하여 도착한 지역에서 소비되도록 함 출발공장(fromplant)에서 도착공장(toplant)으로의 조합에 대해 특정한 단위 비용이 발생하며, 이는 모든 상품에 대해서 동일      경영진은 이제 매달 각 제품이 각 공장의 각 기계에서 얼마나 생산되어야 하는 지, 매달 각 제품을 얼마나 팔고, 각 공장에서 다른 공장으로 얼마나 보내져야 하는 지를 결정  각 상품의 전 세계적인 가격을 고려하여, 목표는 전체 이익 (전체 판매수입에서 전체 생산비용, 전체 재고비용, 전체 수송비용을 뺀 값)을 최대화 하는 가능 해는? HSLee@SKKU

WORLDWIDE CORPORATION 결정변수 10,000개의 생산량 변수: 공장, 기계, 제품, 월의 조합 하나에 대응하여 한 개씩 1,000개의 재고량 변수: 공장, 제품, 월의 조합 하나에 대응하여 한 개씩 1,000개의 판매량 변수: 공장, 제품, 월의 조합 하나에 대응하여 한 개씩 9,000개의 수송량 변수: 제품, 월, 공장(fromplant)과 다른 공장(toplant)의 조합 하나에 대응하여 한 개씩 목적함수 (이익 = 총 판매 수입 - 총 비용) 최대화, 이때 총비용 = 총 생산비용 + 총 재고비용 + 총 수송비용 기능제약식 1,000 생산 용량 제약식 (공장, 기계, 월의 조합 하나당 각 한 개씩) 생산에 사용된 날 수 <= 생산이 가능한 날 수,  1,000개의 공장 균형 제약식 (공장, 제품, 월의 조합 하나당 각 한 개씩) : 생산량 + 지난달 재고량 + 수송 유입량 = 판매량 +현재 재고량 + 수송 유출량 100개의 최대 재고 제약식 (공장, 월의 조합 하나 당 각 한 개씩) 총 재고 <= 재고 용량 1,000개의 최대 판매 제약식 (공장, 제품, 월의 조합 하나 당 각 한 개씩) 판매량 <= 수요. HSLee@SKKU

MPL의 사용 TITLE Production_Planning; INDEX product : (A1, A2, A3, A4, A5, A6, A7, A8, A9, A10); month : (Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct); plant : (p1, p2, p3, p4, p5, p6, p7, p8, p9, p10); fromplant : plant; toplant : plant; machine : (m1, m2, m3, m4, m5, m6, m7, m8, m9, m10); HSLee@SKKU

MPL의 사용 ! Produce.dat - Production Cost and Rate DATA Price[product] := SPARSEFILE(“Price.dat”); Demand[plant, product, month] := SPARSEFILE(“Demand.dat”); ProdCost[plant, machine, product] := SPARSEFILE(“Produce.dat”, 4); ProdRate[plant, machine, product] := SPARSEFILE(“Produce.dat”, 5); ProdDaysAvail[month] := SPARSEFILE(“ProdDays.dat”); InvtCost[plant, product] := SPARSEFILE(“InvtCost.dat”); InvtCapacity[plant] := SPARSEFILE(“InvtCap.dat”); ShipCost[fromplant, toplant] := SPARSEFILE (“ShipCost.dat”); ! Produce.dat - Production Cost and Rate ! ProdCost[plant, machine, product]: ! ProdRate[plant, machine, product]: p1, m1, A1, 73.30, 500, p1, m1, A2, 52.90, 450, p1, m2, A3, 65.40, 550, p1, m3, A3, 47.60, 350, HSLee@SKKU

MPL의 사용 VARIABLES MACROS Produce[plant, machine, product, month] -> Prod; Inventory[plant, product, month] -> Invt; Sales[plant, product, month] -> Sale; Ship[product, month, fromplant, toplant] WHERE (fromplant <> toplant); MACROS Total Revenue := SUM(plant, product, month: Price*Sales); TotalProdCost := SUM(plant, machine, product, month: ProdCost*Produce); TotalInvtCost := SUM(plant, product, month: InvtCost*Inventory); TotalShipCost := SUM(product, month, fromplant, toplant: ShipCost*Ship); TotalCost := TotalProdCost + TotalInvtCost + TotalShipCost; HSLee@SKKU

MPL의 사용 MODEL MAX Profit = TotalRevenue - TotalCost; SUBJECT TO ProdCapacity[plant, machine, month] -> PCap: SUM(product: Produce/ProdRate)  ProdDaysAvail; PlantBal[plant, product, month] -> PBal: SUM(machine: Produce) + Inventory [month - 1] + SUM(fromplant: Ship[fromplant, toplant:= plant]) = Sales + Inventory + SUM(toplant: Ship[from plant:= plant, toplant]); MaxInventory [plant, month] -> MaxI: SUM(product: Inventory) <= InvtCapacity; BOUNDS Sales <= Demand; END HSLee@SKKU

3.7 Conclusions LP is powerful LP is “standard” For allocating resources in any social organization Sometimes LP is not applicable; instead do other things HSLee@SKKU

Homework Problem 3.4.16 Problem 3.5.6 Problem 3.6.4 Problem 3.6.6 HSLee@SKKU