Chapter 3 Introduction to LP

Presentation on theme: "Chapter 3 Introduction to LP"— Presentation transcript:

1 Chapter 3 Introduction to LP
Professor Heesang Lee SKK University

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

3 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.

4 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

5 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

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

7 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.

8 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

9 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.

10 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

11 Standard Form Concise version:
A is an m by n matrix: n variables, m constraints

12 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

13 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

14 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

15 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

16 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.

17 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.

18 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

19 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

20 Violating Proportionality
Case 1 of Table 3.4

21 Violating Proportionality
Case 2 of Table 3.4 Case 3 of Table 3.4

22 Violating Additivity

23 Violating Divisibility & Certainty
Divisibilty Certainty 8 6 4 2 x1 > 0 , x2 > 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?

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

25 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

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

27 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 x x2 Subject to 0.3 x x2  2.7 (Absorption by critical tissues) 0.5 x x2 = 6 (Absorption by tumor region) 0.6 x x2  6 (Absorption by center of tumor) x1, x2  0

28 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 킬로래드를 조사하는 것이 최적

29 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

30 Radiation Therapy-LINGO
! Design for Radiation Therapy. LINGO model; [Exposure] MIN = 0.4 * X * X2; [Critical] 0.3 * X * X2 <= 2.7; [Tumor] 0.5 * X * X2 = 6.0; [Center] 0.6 * X * X2 >= 6.0;

31 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

32 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

33 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. 비음 조건

34 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 100 <= 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) 500 (all constrained =) WaterRequired K10:K12 Maximum Quota (acres) 325 Total Net Return $633,333.33

35 Regional Planning: LINDO input
Max Return)1000 X X X3+750 X X5+750 X X X 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

36 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 Cotton Sorg ; Kibbutz, Acres, WaterA = K K K ; ENDDATA

37 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

38 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

39 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

40 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

41 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 = ; Rate = !( Poll x ABat x Furn); ; Cost = ; ENDDATA [TCost] MIN Dec (i,j) : Cost(i,j) * (i) : (j,k) : Rate(i,j,k) * x(j,k)) >= EmissRate(i); : [Tch] x(i,j) <= 1.0;); END

42 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

43 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의 비율:

44 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, and xij ≥ 0 (i = A, B, C; j = 1, 2, 3, 4).

45 Spreadsheet Formulation for Save-It Co.

46 Reclaiming Solid Wastes: LINDO Input
MAX 5.5XAM1+5.5 XAM XAM XAM XBM XBM XBM XBM XCM XCM XCM XCM4 SUBJECT TO MixA1) .7 XAM XAM XAM XAM4 <= 0 MixA2) -.4 XAM XAM XAM XAM4 >= 0 MixA3) -.5 XAM XAM XAM XAM4 <= 0 MixA4) -.2 XAM XAM XAM XAM4 = 0 MixB1) .5 XBM XBM XBM XBM4 <= 0 MixB2)- .1 XBM XBM XBM XBM4 >= 0 MixB4)- .1 XBM XBM XBM XBM4 = 0 MixC1) .3 XCM XCM XCM 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

47 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 B C ; Mat, Avail, Treat = M M M M ; ! Mn is the minimum percent of a material in a grade.; Mn = ; ! Mx is the maximum percent of a material in a grade.; Mx = ; Contri = 30000; ENDDATA Max : (Price(g) - Cost(g))* x(g,m)); @FOR( Grade(g) : @FOR(Mat(m) : x(g,m) <= Mx(g,m)/100 : x(g,i)); x(g,m) >= Mn(g,m)/100 : 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

48 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

49 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?

50 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

51 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: x 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)

52 Figure 4.3 Union Airways Personnel Scheduling Problem

53 Personnel Scheduling: LINDO
TITLE Union Airways staff scheduling; MIN 170 X X X X X5 SUBJECT TO HR06AM) X >= 48 HR08AM) X1 + X >= 79 HR10AM) X1 + X >= 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

54 Personnel Scheduling: LINGO
! Union Airways Personnel Scheduling. LINGO model(LING03f); MODEL: TITLE Union Airways; SETS: Period / / : MinAgents; Shift / 1..5 / : Cost, Agents; PerShift( Period, Shift) : Coverage; ENDSETS DATA: MinAgents = ; Cost = ; Coverage = ; ENDDATA

55 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

56 Personnel Scheduling: MPL Input
TITLE UnionAirwaysPersonnel; INDEX i := 1..5; {5 shifts} j := ; {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

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

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

59 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

60 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 = F F W W DC ; UCost= !( F1 F2 W1 W2 DC); ! F1; ! F2; ! W1; ! W2; ;! DC; Cap = !( F1 F2 W1 W2 DC) A capacity of zero means there is capacity limit; ! F1; ! F2; ! W1; ! W2; ;! DC; ENDDATA [TCost] Min (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)) (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 : 0.0, x(i,j), Cap(i,j)); END

61 3.5 Spreadsheet Solution Range name Data cells Target cell
Output cells Changing cells Solver

62 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 추가 기능”으로 이동 해찾기 기능을 체크. 확인

63 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 키를 입력

64 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

65 3.5 Spreadsheet Fig. 3.16

66 3.5 Spreadsheet Fig. 3.17

67 3.5 Spreadsheet Fig. 3.18

68 3.5 Spreadsheet Fig. 3.19

69 3.5 Spreadsheet Fig. 3.20

70 3.5 Spreadsheet Fig. 3.21

71 3.5 Spreadsheet Fig. 3.22

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

73 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: 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.

74 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.

75 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.

76 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 X1 + 5 X2 Subject to ! Production time; Plant1) X <= 4 Plant2) X2 <= 12 Plant3) 3 X1 + 2 X2 <= 18 END ! Latest version of LINGO can be downloaded ! from

77 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: When downloading LINGO, note the name of the file (typically LINGO-WINDOWS-IA 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.

78 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.

79 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] X <= 4; [Plant2] *X2 <= 12; [Plant3] 3*X1 + 2*X2 <= 18; !The latest student version of LINGO and What'sBest can be downloaded from textbook web site;

80 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

81 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  

82 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 = ; ! Get the names of the products; Product = P01 P02 P03 P04; ! Profit contribution per unit; Profit = ; ! Hours needed per unit of product; ProdHoursUsed = ! Roll; ! Cut; ; ! Weld; ENDDATA ! Maximize total profit contribution; MAX 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); );

83 LINGO Example @SUM( Product(j): Profit(j) * Produce(j))
@FOR(Machine(i): @SUM( Product(i): ProdHoursUsed(i, j) * Produce (j)) <= ProdHoursAvail (i, j); ); MAX 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); );

84 LINGO: Union Airways HSLee@SKKU
! Union Airways Personnel Scheduling. LINGO model(LING03f); MODEL: TITLE Union Airways; SETS: Period / / : MinAgents; Shift / 1..5 / : Cost, Agents; PerShift( Period, Shift) : Coverage; ENDSETS DATA: MinAgents = ; Cost = ; Coverage = ; ENDDATA

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

86 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] := ( , ); VARIABLES Produce[product]; MODEL MAX TotalProfit = SUM(product: Profit * Produce); SUBJECT TO TimeCapacity[plant] -> TimeCap: SUM(product: ProdTime * Produce) <= TimeAvail; END

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

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

89 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);

90 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,

91 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;

92 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

93 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

94 Homework Problem 3.4.16 Problem 3.5.6 Problem 3.6.4 Problem 3.6.6