Ch03linear Programming

Chapter 3 Linear Programming Models

edited for 321310 by..Benchaporn

1

Learning Objectives • เข้าใจสมมติฐานเบื้องต้นและคุณสมบัติพื้นฐานของกำาหนดการเชิงเส้น linear programming (LP) • สร้างตัวแบบกำาหนดการเชิงเส้นแทนปัญหาได้ • ใช้กราฟเป็นเครื่องมือในการหาผลลัพธ์ของตัวแบบกำาหนดการเชิงเส้นที่มสี องตัวแปรได้ • เข้าใจการใช้โปรแกรมตารางคำานวณประเภทสเปรดชีท เพื่อแทนปัญหา และใช้ solver ในโปรแกรม MS Excel ในการแก้ปัญหาได้

edited for 321310 by..Benchaporn

2

Introduction • ในการตัดสินใจของผู้บริหารในหน่วยงานและองค์การต่างๆ เป็นการตัดสินใจที่เกี่ยวกับ – การใช้ทรัพยากรทีม่ ีอยู่อย่างจำากัด ให้ได้อย่างเต็มทีแ่ ละได้รับผลตอบแทนสูงสุด ทรัพยากรดังกล่าว ได้แก่ เครื่องจักร, คนงาน, เงิน, เวลา, ที่ว่างในคลังสินค้า และวัตถุดิบ เป็นต้น – การผลิตสินค้า เช่น คอมพิวเตอร์, เครื่องยนต์, หรือเสื้อผ้า – การให้บริการ เช่น การจัดส่งสินค้า, การให้บริการด้านสุขภาพ หรือการตัดสินใจด้านการลงทุน edited for 321310 by..Benchaporn

3

Linear programming (LP) • กำาหนดการเชิงเส้น Linear programming (LP) เป็นวิธีการเชิงคณิตศาสตร์ที่ได้รับความนิยมในการแก้ปัญหาที่เกิดขึ้นในธุร กิจ โดยมีสมมติฐานเบื้องต้นในการสร้างตัวแบบว่าข้อมูลเข้า และ ค่าตัวแปรที่เกี่ยวข้องต่างๆ ต้องทราบค่าแน่นอน (deterministic models) • ในปัจจุบนั คอมพิวเตอร์ถูกนำามาใช้เป็นเครื่องมือในการหาค่าผลลัพธ์จากตัว แบบกำาหนดการเชิงเส้น edited for 321310 by..Benchaporn

4

Development of a LP Model • กำาหนดการเชิงเส้นสามารถนำาไปประยุกต์ใช้ได้กับปัญหาต่างๆ เช่น – การแพทย์, การขนส่ง, การปฏิบัติงาน – การเงิน, การตลาด, การบัญชี – ด้านการจัดการทรัพยากรมนุษย์ และด้านการเกษตร

• การสร้างตัวแบบกำาหนดการเชิงเส้นมี 3 ขั้นตอนได้แก่ : – (1) การสร้างตัวแบบกำาหนดการเชิงเส้น(formulation) – (2) การแก้ปญ ั หากำาหนดการเชิงเส้น(solution) – (3) การวิเคราะห์ผลลัพธ์(interpretation) edited for 321310 by..Benchaporn

5

Three Steps of Developing LP Problem การสร้างตัวแบบกำาหนดการเชิงเส้น(formulation) – เป็นกระบวนการแปลโจทย์ปัญหาให้อยูใ่ นรูปตัวแบบกำาหนดการเชิงเส้นแบบง่าย และแสดงความสัมพันธ์เชิงคณิตศาสตร์ระหว่างตัวแปรต่างๆ

การแก้ปญ ั หากำาหนดการเชิงเส้น(solution) – ความสัมพันธ์เชิงคณิตศาสตร์ ที่ได้จากขัน้ ตอนการสร้างตัวแบบ จะถูกนำามาหาผลลัพธ์ เพื่อให้ได้ผลลัพธ์ที่เหมาะสมที่สุด

การวิเคราะห์ผลลัพธ์(interpretation) – ในขั้นตอนนี้ผู้แก้ปัญหาหรือนักวิเคราะห์ จะทำางานร่วมกับผู้บริหารเพื่อ • แปลความหมายของผลที่ได้จากขัน้ ตอนแก้ปัญหา • ลองเปลี่ยนค่าตัวแปรต่างๆในตัวแบบ และสังเกตผลลัพธ์หรือผลที่เกิดขึน้ edited for 321310 by..Benchaporn

6

Properties of a LP Model 1. ทุกปัญหามีวัตถุประสงค์หลักเพียงวัตถุประสงค์เดียว คือพยายามค้นหาปริมาณสูงสุดหรือตำ่าที่สุด เช่น หากำาไรสูงสุด หรือต้นทุนตำ่าที่สุด เรียกว่าฟังก์ชันวัตถุประสงค์ (objective function). 2. ตัวแบบกำาหนดการเชิงเส้น ประกอบด้วย ข้อจำากัด(restrictions) หรือ เงื่อนไขบังคับ(constraints) ซึ่งเป็นกรอบหรือข้อจำำกัดที่มีผลโดยตรงต่อค่ำของวัตถุประสงค์ 3. ต้องมีทางเลือกในการปฏิบัตไิ ด้หลายทาง 4. วัตถุประสงค์และเงือ่ นไขจำากัดในปัญหากำาหนดการเชิงเส้น ต้องสามารถเขียนอยู่ในรูปของสมการหรืออสมการเชิงเส้น edited for 321310 by..Benchaporn

7

Linear Equations and Inequalities • ตัวอย่างสมการเชิงเส้น : 2A + 5B = 10 • สมการต่อไปนี้ไม่เป็นสมการเชิงเส้น: 2A2 + 5B3 + 3AB = 10 • ในตัวแบบกำาหนดการเชิงเส้น อาจมีการใช้อสมการในรูปแบบ : A + B ≤ C หรือ A + B ≥ C edited for 321310 by..Benchaporn

8

Basic Assumptions of a LP Model •

Certainty ต้องทราบข้อมูลต่างๆแน่นอน

•

Proportionality การเปลี่ยนแปลงค่าตัวแปรจะมีผลกระทบเป็นสัดส่วนแน่นอนทัง้ ในฟังก์ชันวัตถุ ประสงค์และในเงื่อนไขบังคับ (เช่น 1 หน่วย ใช้เวลา 3 ชม. ถ้าผลิต 3 หน่วย จะใช้เวลา 9 ชม.)

•

Additivity ผลรวมทั้งหมดได้มาจากการบวกกันของกิจกรรมแต่ละกิจกรรมต่างๆ(เช่น edited for 321310 by..Benchaporn

กำาไรรวม ได้จากกำาไรจากการขายสินค้าชนิดที1่ +ชนิดที่ 2)

9

Formulating a LP Problem • การประยุกต์ใช้กำาหนดการเชิงเส้นที่พบได้บ่อยๆ เช่น ปัญหาการกำาหนดสัดส่วนการผลิต – ได้แก่ ปัญหาเกี่ยวกับการผลิตสินค้า 2 ชนิดหรือมากกว่า ภายใต้ข้อจำากัดด้านทรัพยากร เช่น ด้านจำานวนคน, เครื่องจักร, วัตถุดิบ ฯลฯ

• กำาไรสูงสุดที่บริษัทต้องการ ขึ้นอยู่กับกำาไรต่อหน่วยของสินค้าแต่ละชิน้ และจำานวนผลิตของสินค้าแต่ละชนิด • สิ่งที่บริษัทต้องการทราบ ได้แก่ -

edited for 321310 by..Benchaporn

– ควรผลิตสินค้าแต่ละชนิดอย่างละเท่าใด

10

LP Example: Flair Furniture Company ข้อมูลและเงือ่ นไขบังคับของบริษัท • Flair Furniture Company ผลิตโต๊ะและเก้าอี้ • โต๊ะแต่ละตัวใช้เวลา : 4 ชม. ในการประกอบ และ 2 ชม. ในการทาสี • เก้าอี้แต่ละตัวใช้เวลา : 3 ชม. ในการประกอบ และ 1 ชม. ในการทาสี • ความสามารถในการผลิตที่มีอยู่: แผนกประกอบมีเวลา 240 ชม. และ แผนกทาสีมีเวลา 100 ชม. • เนื่องจากในคลังสินค้ามีเก้าอี้เหลือค้างอยู่ ดังนั้นบริษัทจะต้องไม่ผลิตเก้าอีใ้ หม่เกินกว่า 60 ตัว • การขายโต๊ะได้กำาไรตัวละ $7 ส่วนเก้าอีไ้ ด้กำาไรตัวละ $5

ปัญหาของบริษทั Flair Furniture: • จงหาว่าต้องผลิตโต๊ะและเก้าอี้อย่างละกี่ตัวเพื่อให้ได้กำาไรสูงสุดภายใต้เงื่อนไขบังคับและข้อจำากั ดของบริษัท edited for 321310 by..Benchaporn

11

ตัวแปรที่ต้องตัดสินใจ(Decision Variables) • ปัญหาของบริษัท Flair คือ ต้องการทราบว่าต้องผลิตโต๊ะและเก้าอี้จำานวนอย่างละเท่าใด เพื่อให้ได้กำาไรสูงที่สุด? • ในปัญหานี้ มีตัวแปรที่ต้องตัดสินใจ หรือตัวแปรที่เราต้องการหาค่าผลลัพธ์มี 2 ตัวได้แก่ T - จำำนวนโต๊ะที่ผลิต C - จำำนวนเก้ำอีท ้ ี่ผลิต edited for 321310 by..Benchaporn

12

ฟังก์ชันวัตถุประสงค์(Objective Function) • ฟังก์ชันวัตถุประสงค์ แสดงเป้าหมายของปัญหา – วัตถุประสงค์หลักที่ต้องการแก้ปัญหาคืออะไร? – กำาไรสูงที่สุด!

• ตัวแบบกำาหนดการเชิงเส้นต้องมีฟงั ก์ชันวัตถุประสงค์เพียงวัตถุประสงค์เดียวเท่านั้ น ในปัญหาของบริษัท Flair กำาไรรวมคำานวณได้ดังนี้ : ใช้ตวั แปรที่ตอ้ งตัดสินใจโดย T แทนจำำนวนโต๊ะ และ C แทนจำานวนเก้าอี้ Maximize P =

$7 T + $5 C

(กำาไร $7 ต่อโต๊ะหนึ่งตัว ) x (จำานวนโต๊ะที่ผลิต) + (กำาไร $5 ต่อเก้าอี้หนึ่งตัว) x (จำานวนเก้าอี้ที่ผลิต) edited for 321310 by..Benchaporn

13

เงื่อนไขบังคับ(Constraints) • แทนเงื่อนไข เพื่อหลีกเลี่ยงกรณีที่อาจมีการเลือกค่าตัวแปรที่ต้องตัดสินใจ นอกขอบเขตเงือ่ นไขที่มี • ในปัญหาของบริษัท Flair Furniture มีข้อจำากัด 3 ข้อได้แก่ – ข้อจำากัด 1 และ 2 เป็นข้อจำากัดเกีย่ วกับการผลิตภายในเวลาที่มอี ยู่ของแผนกประกอบ และแผนกทาสี – ข้อจำากัด 3 เป็นedited ข้อจำากัforดเกี ่ยวกับจำานวนผลิตเก้าอี้สูงสุดที่ยอมได้ 321310 by..Benchaporn

14

เงื่อนไขบังคับ(Constraints) • เวลาว่างของแผนกประกอบ คือ 240 ชม. 4T + 3C ≤ 240 • เวลาว่างของแผนกทาสี คือ 100 ชม. 2T + 1C ≤ 100 • ข้อจำากัดของจำานวนผลิตเก้าอี้ C ≤ 60 • เงือ่ นไขบังคับที่ตัวแปรทุกตัวต้องมีค่าไม่ติดลบ T ≥ 0 (จำานวนโต๊ะทีผ่ ลิต C ≥ 0 (จำานวนเก้าอี้ทผี่ ลิต edited for 321310 by..Benchaporn

0) 0) 15

A Simplified Model Mathematical relationship: Decision variables (Independent variables):

Maximize Profit

Objective

T, C (What quantities of Table and Chair should be produced?)

Dependent variable:

P=7T+5C Subject to: 4T + 3C ≤ 240 2T + 1C ≤ 100 C ≤ 60

(Total Profit) Constraint

Uncontrollable variables: 240, 100, and 60 (Time available, marketing limitation)

edited for 321310 by..Benchaporn

16

Example 1 ผู้จัดการบริษัทพัฒนาอุตสาหกรรม ต้องการผลิตวิทยุ 2 แบบ คือ แบบมาตรฐาน และแบบพิเศษ ซึง่ ผลิตเท่าไรก็ขายได้หมด แผนก เวลาที่ใช้ เวลาว่างของแต่ละแผนก แบบมาตรฐาน แบบพิเศษ ในแต่ละวัน(ชม.) ประกอบ

(นาที)

(นาที)

20

30

55

ทดสอบ 10 6 18 บรรจุ 3 3 6 โดย วิทยุแบบมาตรฐานขายได้กำาไรเครื่องละ 250 บาท และ แบบพิเศษได้กำาไรเครื่องละ 290 บาทby..Benchaporn edited for 321310

17

Example 1 บริษทั พัฒนาอุตสาหกรรม จำากัด •ตัวแปรที่ต้องตัดสินใจ :

จำานวนการผลิตวิทยุแบบมาตรฐาน และ จำานวนการผลิตวิทยุแบบพิเศษ

•ฟังก์ชันวัตถุประสงค์ : กำาไรสูงสุด

•เงื่อนไขบังคับ :

ทรัพยากรทีม่ ีอยู่ในแต่ละวัน (เวลาว่าง,เวลาที่ใช้ในแต่ละแผนก) edited for 321310 by..Benchaporn

18

Example 1 บริษทั พัฒนาอุตสาหกรรม จำากัด

•ตัวแปรที่ต้องตัดสินใจ : ให้ x1 แทนจำานวนวิทยุแบบมาตรฐานที่จะผลิตในหนึ่งวัน หน่วย : เครื่อง x2 แทนจำานวนวิทยุแบบพิเศษที่จะผลิต ในหนึง่ วัน หน่วย : เครื่อง

•ฟังก์ชันวัตถุประสงค์ :

กำาไร = (กำาไรต่อเครื่องของวิทยุแบบมาตรฐาน ) × (จำานวนวิทยุแบบมาตรฐาน)

+

(กำาไรต่อต่อเครื่องของวิทยุแบบพิเศษ) × (จำานวน วิทยุแบบพิเศษ)

Maximize Z = 250x1 + 290x2

edited for 321310 by..Benchaporn

19

Example 1 เงื่อนไขบังคับ : แผนก

ประกอบ

เวลาที่ใช้(ต่อเครื่อง) แบบมาตรฐาน (นาที)

แบบพิเศษ (นาที)

20

30

X1

X2

เวลาว่างของแต่ละแผนก ในแต่ละวัน(นาที)

55×60 = 3,300

20x1 + 30x2 ≤ 3,300 edited for 321310 by..Benchaporn

20

Example 1 เงื่อนไขบังคับ : แผนก

ทดสอบ

เวลาที่ใช้(ต่อเครือ่ ง) แบบมาตรฐาน (นาที)

แบบพิเศษ (นาที)

10

6

X1

X2

เวลาว่างของแต่ละแผนก ในแต่ละวัน(นาที)

18×60 = 1,080

10x1 + 6x2 ≤ 1,080 edited for 321310 by..Benchaporn

21

Example 1 เงื่อนไขบังคับ : แผนก

บรรจุ

เวลาที่ใช้(ต่อเครือ่ ง) แบบมาตรฐาน (นาที)

แบบพิเศษ (นาที)

3

3

X1

X2

เวลาว่างของแต่ละแผนก ในแต่ละวัน(นาที)

6×60 = 360

3x1 + 3x2 ≤ 360 edited for 321310 by..Benchaporn

22

Example 1 ข้อจำากัด:

ค่าตัวแปรที่ต้องตัดสินใจทุกตัวจะต้องมีคา่ ไม่ติดลบ x1 , x2 ≥ 0

edited for 321310 by..Benchaporn

23

Example 1

ตัวแบบกำำหนดกำรเชิงเส้น

Maximize Z = 250x1 + 290x2 Subject to 20x1 + 30x2 ≤ 3,300 10x1 + 6x2 ≤ 1,080 3x1 + 3x2 ≤ 360 x1 , x2 ≥ 0 edited for 321310 by..Benchaporn

24

Example 2 โรงงานผลิตแชมพูสระผมแห่งหนึ่งทำาการผลิตแชมพู 3 แบบคือ 1.แบบธรรมดา 2.แบบเข้มข้น 3.แบบผสมครีมนวดผม โดยใช้วัตถุดิบที่เป็นสารเคมีที่สำาคัญ 3 ชนิดคือ A ,B และ C ในสัดส่วนดังตาราง ถ้าโรงงานคาดว่าจะขายแชมพูแบบเข้มข้นได้ไม่เกิน 100 ลิตร โรงงานควรผลิตอย่างไร edited for 321310 by..Benchaporn

25

Example 2 สารเคมี

A B C

กำาไร (บาท/ลิตร)

อัตราส่วนผสมใน 1 ลิตร แบบธรรมดา แบบเข้มข้น แบบผสมครีมนวด ปริมาณสารที่หาได้(ลิตร)

0.3 0.6 0.1 15

0.5 0.3 0.2 20

0.2 0.1 0.7 25

edited for 321310 by..Benchaporn

1,000 1,500 2,000

26

Example 2 โรงงานผลิตแชมพู

การผลิตแชมพู 3 ชนิด (แบบธรรมดา, แบบเข้มข้น, แบบผสมครีมนวดผม)

•ตัวแปรที่ต้องตัดสินใจ : จำานวนแชมพูแต่ละชนิดที่จะผลิต •ฟังก์ชันวัตถุประสงค์ : กำาไรสูงสุด •เงื่อนไขบังคับ : สารเคมีที่ใช้ A, B, C

edited for 321310 by..Benchaporn

27

Example 2 กำาหนดตัวแปรที่ต้องตัดสินใจ ให้

X1

จำานวนแชมพูแบบธรรมดา ที่จะผลิต (ลิตร)

X2

จำานวนแชมพูแบบเข้มข้น ที่จะผลิต (ลิตร)

X3

จำานวนแชมพูแบบผสมครีมนวด ที่จะผลิต (ลิตร)

edited for 321310 by..Benchaporn

28

Example 2 Maximize Z

= 15X1 + 20X2 + 25X3

ภายใต้เงื่อนไขบังคับและข้อจำากัด ดังนี้ 0.3 X1 + 0.5 X2 + 0.2 X3

≤ 1,000

0.6 X1 + 0.3 X2 + 0.1 X3

≤ 1,500

0.1 X1 + 0.2 X2 + 0.7 X3

≤ 2,000

X2 ≤ 100 X1 , X2, X3

≥

edited for 321310 by..Benchaporn

0 29

Example 3 โรงงานผลิตอาหารสัตว์แห่งหนึง่ ควรจะผลิตอาหารสัตว์อย่างไร หากในขบวนการผลิตจะต้องนำาวัตถุดิบประเภทต่างๆมาผสมกันเพื่อใ ห้ได้คุณค่าทางอาหารตามข้อกำาหนดเหล่านี้ โปรตีน อย่างน้อยเท่ากับ 18 หน่วย คาร์โบไฮเดรต อย่างน้อยเท่ากับ 31 หน่วย ไขมัน อย่างน้อยเท่ากับ 25 หน่วย โดยวัตถุดิบ ราคาวัตถุดิบ และสารอาหารแต่ละชนิด มีรายละเอียดดังนี้ edited for 321310 by..Benchaporn

30

Example 3 วัตถุดิบ

ปริมาณสารอาหารต่อกิโลกรัม (กก.)

ราคาต่อหน่วย (บาท/กก.)

โปรตีน

คาร์โบไฮเดรต

ไขมัน

A

0.18

0.43

0.31

200

B

0.31

0.25

0.37

300

C

0.12

0.12

0.37

150

D

0.18

0.50

0.12

100

edited for 321310 by..Benchaporn

31

Example 3 การผสมอาหารสัตว์ การผสมอาหารสัตว์ 4 ชนิด (A, B, C, D)

•ตัวแปรที่ต้องตัดสินใจ : จำานวนวัตถุดิบแต่ละชนิดที่จะนำามาผสมเป็นอาหารสัตว์ •ฟังก์ชันวัตถุประสงค์ : ค่าใช้จา่ ยตำ่าสุด •เงื่อนไขบังคับ : ปริมาณสารอาหารที่ต้องการ edited for 321310 by..Benchaporn

32

Example 3 กำาหนดตัวแปรที่ต้องตัดสินใจ ให้ X1 จำานวนวัตถุดิบ A ที่จะนำามาผสม (กก.) X2 จำานวนวัตถุดิบ B ที่จะนำามาผสม (กก.) X3 จำานวนวัตถุดิบ C ที่จะนำามาผสม (กก.) X4 จำานวนวัตถุดิบ D ที่จะนำามาผสม (กก.)

edited for 321310 by..Benchaporn

33

Example 3 Minimize Z = 200X1 + 300X2 + 150X3 + 100X4

ภายใต้ข้อจำากัด 0.18X1 + 0.31X2 + 0.12 X3 + 0.18 X4 ≥ 18 0.43X1 + 0.25X2 + 0.12 X3 + 0.50 X4 ≥ 31 0.31X1 + 0.37X2 + 0.37 X3 + 0.12 X4 ≥ 25 X 1 , X 2, X 3, X 4 ≥ 0 edited for 321310 by..Benchaporn

34

Example 4 บริษัทพัฒนาการผลิต จำากัด ต้องการโฆษณาประชาสัมพันธ์ สินค้าของตนเอง เพื่อให้เข้าถึงกลุ่มเป้าหมาย (ผู้บริโภคสินค้า) ให้ได้มากที่สุด โดยจะใช้สื่อที่มีอยู่ 4 ชนิด คือ สือ่ โทรทัศน์, สือ่ หนังสือพิมพ์ และสือ่ วิทยุ 2 รายการ ทั้งนี้สื่อแต่ละชนิดสามารถเข้าถึงลูกค้าของบริษัทฯ โดยมีค่าใช้จ่ายในการโฆษณาต่อครั้ง และจำานวนครั้งที่สามารถทำาการโฆษณาได้สงู สุดต่อสัปดาห์ เป็นดังนี้ edited for 321310 by..Benchaporn

35

Example 4

โทรทัศน์ (เวลา 15 วินาที) หนังสือพิมพ์ (ขนาดเต็ม1 หน้า) วิทยุรายการเพลงสากล (1 spot) วิทยุรายการหลังข่าวดัง (1 spot)

จำานวนลูกค้า ค่าใช้จ่ายต่อครั้ง จำานวนครั้งสู ที่เข้าถึง งสุด (ต่อครั้ง) 800 12 5,000 8,500

925

5

2,400

290

25

2,800

380

20

edited for 321310 by..Benchaporn

36

Example 4 •ถ้าบริษัทตั้งงบประมาณค่าโฆษณาต่อสัปดาห์ไว้ 8,000 บาท •โดยกำาหนดว่าจะต้องโฆษณาทางวิทยุอย่างน้อยสัปดาห์ละ 5 ครั้ง แต่ต้องใช้งบประมาณไม่เกิน 1,800 บาท อยากทราบว่าบริษัทฯ จะต้องตัดสินใจโฆษณาแต่ละสัปดาห์อย่างไร

edited for 321310 by..Benchaporn

37

Example 4 การเลือกสื่อโฆษณา

การเลือกสื่อโฆษณา 4 ชนิด (โทรทัศน์, หนังสือพิมพ์, วิทยุ1, วิทยุ2) •ตัวแปรที่ต้องตัดสินใจ : จำานวนครั้งที่โฆษณาในแต่ละสื่อ •ฟังก์ชันวัตถุประสงค์ : จำานวนผู้ชมสูงสุด •เงื่อนไขบังคับ : งบประมาณ, จำานวนครัง้ สูงสุด edited for 321310 by..Benchaporn

38

Example 4 กำาหนดตัวแปรที่ต้องตัดสินใจ ให้ X1 จำานวนครั้งที่ โฆษณาทางโทรทัศน์ X2 จำานวนครั้งที่ โฆษณาทางหนังสือพิมพ์ X3 จำานวนครั้งที่ โฆษณาทางวิทยุรายการเพลงสากล X4 จำานวนครั้งที่ โฆษณาทางวิทยุรายการหลังข่าวดัง

edited for 321310 by..Benchaporn

39

Example 4 Maximize Z = 5000X1 + 8500X2 + 2400X3 + 2800X4 ภายใต้ข้อจำากัด 800X1 + 925X2 + 290X3 + 380X4 ≤ 8000 X3 + X 4 ≥ 5 290X3 + 380X4 ≤ 1800 X1 ≤ 12 X2 ≤ 5 X3 ≤ 25 X4 ≤ 20 X1for,321310 X2, by..Benchaporn X3, X4 ≥ 0 edited

40

Graphical Solution of a LP With Two Variables • ข้อดีของการใช้กราฟ ได้แก่ สามารถใช้แก้ปัญหากำาหนดการเชิงเส้นที่มีตัวแปรที่ต้องตัดสินใจ 2 ตัวแปร โดยการใช้กราฟสองมิติได้ • ข้อเสีย คือ ในกรณีที่พื้นที่ผลลัพธ์เป็นรูปหลายเหลี่ยมที่มีจุดยอดมุมหลายจุด จะทำาให้เสียเวลาในการคำานวณมาก อีกทั้งการใช้กราฟแก้ปัญหายังไม่สามารถใช้ได้กับการแก้ปัญหาที่ for 321310าby..Benchaporn มีตัวแปรที่ต้องตัดสิedited นใจมากกว่ 3 ตัวแปร

41

Graphical Representation of Constraints

ตัวแบบเชิงเส้นของโจทย์ปัญหา Flair Furniture Company Maximize profit = $7T + $5C

(objective function)

Subject to constraints 4T + 3C ≤ 240

(carpentry constraint)

2T + 1C ≤ 100

(painting constraint)

C ≤ 60

(chairs limit constraint)

T ≥ 0

(non-negativity constraint on tables)

C ≥ 0 (non-negativity constraint on chairs) edited for 321310 by..Benchaporn

42

Graphical Solution of a LP With Two Variables • • • • • •

ลากแกนแนวนอน แทนตัวแปรตัวที่ 1 (T) และ ลากแกนแนวตั้งแทนตัวแปรตัวที่ 2 (C) เปลีย่ นฟังก์ชนั่ เงื่อนไขบังคับ จากรูปแบบอสมการเป็นรูปแบบสมการ หาจุดตัดระหว่างฟังก์ชั่นเงื่อนไขบังคับทุกอัน กับแกนแนวนอนและแนวตั้ง หาจุดตัดระหว่างเส้นฟังก์ชั่นเงือ่ นไขบังคับที่ตดั กันในกราฟ หาพืน้ ที่ผลลัพธ์ที่นา่ จะเป็นผลเฉลย(Feasible Area) รวมถึงหาจุดตัดยอดมุมของพื้นที่ดังกล่าว หาผลเฉลยที่เหมาะสมทีส่ ุด(The Optimal Solution) ด้วยวิธกี ารแทนค่าจุดตัดยอดมุมลงไปในฟังก์ชั่นวัตถุประสงค์ edited for 321310 by..Benchaporn

43

Graphical Representation of Constraints Carpentry Time Constraint 4T + 3C = 240 แทน C = 0 จะได้ 4T+ 3(0) = 240 T = 60 ดังนั้น จุดตัดกับแกนแนวนอน คือ ( 60 , 0 )

4T + 3C ≤ 240 เปลีย่ นฟังก์ชั่นเงือ่ นไขบังคับ จากรูปแบบอสมการ เป็นรูปแบบสมการ ได้ดังนี้ 4T + 3C = 240 แทน T = 0 จะได้ 4(0)+ 3C = 240 C = 80 ดังนั้น จุดตัดกับแกนแนวตัง้ คือ ( 0 , 80 )

(T=60,C=0)

edited for 321310 by..Benchaporn

44

Graphical Representation of Constraints Carpentry Time Constraint

หาพื้นที่ผลลัพธ์ โดยสมมติจุดใดๆ เพื่อทดสอบ โดยสังเกตได้ว่าจุดใดๆที่อยู่บนเ ส้น จะเป็นไปตามเงื่อนไขเช่น (30,40) •ทดสอบ จุด(30,20) 4(30) + 3(20) ≤ 240 จริง •ทดสอบ จุด(70,40) 4T + 3C 4(70) + 3(40) > 240 ไม่เป็นไปตามเงือ่ นไข ดังนั้นพื้นทีแ่ รเงาจะอยูใ่ ต้เส้นกร edited for 321310 by..Benchaporn าฟ

≤ 240

45

Graphical Representation of Constraints Painting Time Constraint

2T + 1C ≤ 100

เปลี่ยนฟังก์ชั่นเงื่อนไขบังคับ จากรูปแบบอสมการ เป็นรูปแบบสมการ ได้ดงั นี้ 2T + 1C = 100 แทน T = 0 จะได้ 2(0)+ 1C = 100 C = 100 ดังนั้น จุดตัดกับแกนแนวตั้ง คือ (0 , 100) หาพื้นที่ผลลัพธ์ โดยสมมติจุดใดๆ เพื่อทดสอบ เหมือนเงื่อนไขก่อนหน้า(Carpentry Time Constraint) จะได้ว่าพื้นที่ edited for 321310 by..Benchaporn แรเงาจะอยู่ใต้เส้นกราฟ

2T + 1C = 100

แทน C = 0 จะได้ 2T+ 1(0) = 100 T = 50 ดังนั้น จุดตัดกับแกนแนวนอน คือ ( 50 , 0 )

46

Graphical Representation of Constraints Chair Limit Constraint and Feasible Solution Area

2T + 1C ≤ 100

พื้นที่ผลลัพธ์ทเี่ ป็นไปไ ด้ จะถูกกำาหนดโดยเงื่อนไ ขบังคับทั้ง 3 แสดงได้ดังรูป

C ≤ 60

4T + 3C ≤ 240

edited for 321310 by..Benchaporn

47

Graphical Solution Isoprofit Line Solution Method • ผลเฉลยเหมาะที่สุด จะเป็นจุดภายในพืน้ ที่แรเงา ที่ให้ค่ากำาไรสูงสุด • อาจมีผลเฉลยที่เป็นไปได้มากกว่าหนึง่ ผลเฉลย

ภายในบริเวณพืน้ ที่แรเงา

ดังนัน้ ในการเลือกจุดที่ดีที่สุด ที่จะให้ค่าผลกำาไรสูงที่สุดทำาได้โดย • กำาหนดให้ฟังก์ชันวัตถุประสงค์ ($7T + $5C) เท่ากับค่าสมมติค่าหนึง่ โดยค่านัน้ จะต้องสอดคล้องกับจุด ซึ่งอยู่ภายในพื้นที่แรเงา • ลากเส้นฟังก์ชั่นวัตถุประสงค์ซึ่งเท่ากับค่าที่กำาหนด โดยจะได้กราฟเป็นเส้นedited ตรง for 321310 by..Benchaporn

48

Isoprofit Line Solution Method • ฟังก์ชั่นวัตถุประสงค์ คือ: $7 T + $5 C = Z • เลือกสมมติค่า Z ให้เป็นค่าค่าหนึ่ง ตัวอย่าง เช่น เลือกค่า Z ให้เท่ากับ

$210 ดังนัน้ จะได้ว่า : $7 T + $5 C = $210 • การวาดกราฟของเส้นแสดงผลกำาไร ทำาได้โดย: กำาหนดให้ T = 0 และแก้สมการฟังก์ชนั่ วัตถุประสงค์ เพื่อหาค่า C – ให้ T = 0 จะได้วา่ $7(0) + $5C = $210 หรือ C = 42 กำาหนดให้ C = 0 และแก้สมการฟังก์ชั่นวัตถุประสงค์ เพื่อหาค่า T – ให้ C = 0 จะได้วedited ่า $7Tfor+321310 $5(0) =by..Benchaporn $210 หรือ T = 30

49

Isoprofit Line Solution Method

จากนัน้ ทำาการเลือกสมมติค่ า Z ให้สูงขึ้น เพือ่ หาว่าเป็นผลเฉลยที่เหม าะสมหรือไม่ จากรูปจะเห็นว่า ค่า Z=210 ที่เราเลือก ยังไม่ใช่ค่าสูงสุดที่เป็นไปไ ด้ edited for 321310 by..Benchaporn

50

Isoprofit Line Solution Method

รูปในหน้านี้ แสดงเส้น Isoprofit lines ต่างๆ เมือ่ เลือกกำาหนดค่า Z ให้เท่ากับ $350 และ $280 ซึ่งจะเห็นว่าทุกเส้นจะขน านกับเส้นผลกำาไรแรกที่ กำาหนดให้ Z= $210 edited for 321310 by..Benchaporn

51

Optimal Solution ผลเฉลยที่เหมาะที่สุด(Optimal Solution) : อยูท่ ี่จุดมุมหมายเลข 4 คือ: T=30 (โต๊ะ) และ C=40 (เก้าอี)้ โดยได้รับกำาไร เท่ากับ $410

edited for 321310 by..Benchaporn

52

Optimal Solution • ผลเฉลยเหมาะที่สุด จะอยู่ที่จุดสูงสุดในพื้นที่แรเงา • โดยจะเห็นว่า อยู่ที่จุดตัดกันระหว่าง เงื่อนไขบังคับด้านการประกอบ (carpentry constraints) และเงื่อนไขบังคับด้านทาสี(painting constraints): - สมการ Carpentry constraint คือ: 4T + 3C = 240 ---- - สมการ Painting constraint คือ: 2T + 1C = 100 ---- หากเราแก้สมการเพื่อหาจุดตัดของกราฟเงือ่ นไขบังคับทั้งสอง(ที่จุดหมายเลข 4) จะได้ผลเฉลยที่เหมาะสมที่ให้ค่ากำาไรสูงสุด ทำำได้ดังนี้ นำา 2 จะได้ 4T + 2C = 200 และ นำาไปลบกับ จะได้ว่า C = 40 นำาค่า C = 40 ที่ได้ไปแทนใน เพื่อหาค่า T จะได้ T=30 321310รby..Benchaporn T=30 (โต๊ะ) และ C=40edited (เก้าอีfor้) โดยได้ บั กำาไร เท่ากับ $410

53

Corner Point Solution Method Corner Point Property “คำาตอบของปัญหาที่เหมาะสม ของปัญหากำาหนดการเชิงเส้น มักจะเกิดขึ้นที่จุดมุม” จากรูปจะทำาให้ทราบบริเวณพืน้ ที่ของ ผลลัพธ์ที่เป็นไปได้สำาหรับโจทย์ที่ กำาหนด ซึ่งบริเวณดังกล่าวมีจุดมุม 5 จุด คือจุด 1, 2, 3, 4, และ 5 ตามลำาดับ ในการหาว่าจุดใดที่ให้กำาไรมากที่สุด ทำาได้โดยนำาจุดมุมแต่ละจุดไปคำาน วณหาค่ากำาไร ในฟังก์ชั่นวัตถุประสงค์ edited for 321310 by..Benchaporn

54

Corner Point Solution Method • จุดที่ 1 (T = 0, C = 0) กำาไร = $7(0) + $5(0) = $0 • จุดที่ 2 (T = 0, C = 60) กำาไร = $7(0) + $5(60) = $300 • จุดที่ 3 (T = 15, C = 60) กำาไร = $7(15) + $5(60) = $405 • จุดที่ 4 (T = 30, C = 40) กำาไร = $7(30) + $5(40) = $410 • จุดที่ 5 (T = 50, C = 0) กำาไร = $7(50) + $5(0) = $350 edited for 321310 by..Benchaporn

55

Setting Up and Solving LP Problems Using Excel’s Solver การใช้ solver เพื่อหาผลเฉลยปัญหา Flair Furniture จากโจทย์ตัวแปรตัดสินใจคือ T ( Tables ) และ C ( Chairs ) :

Maximize profit = $7T + $5C Subject to constraints 4T + 3C ≤ 240 (carpentry constraint) 2T + 1C ≤ 100 (painting constraint) C ≤ 60 (chairs limit constraint) T, C ≥ 0 (non-negativity)

edited for 321310 by..Benchaporn

56

Solver Spreadsheet Setup • Changing Cells เพื่อความชัดเจน จากรูปจึงใส่พื้นหลังสีเหลืองให้กับเซลล์ที่เก็บค่าตัวแปรตัดสินใจ

edited for 321310 by..Benchaporn

Changing Cells ให้ระบุตัวแปรตัดสินใจ B5 และ C5

57

LP Excel and Solver Parts Target Cell

จะถูกอ้างอิงลงในส่วน target cell ของ solver ในแผ่นงานให้กำาหนดสูตร = SUMPRODUCT(B6:C6,$B$5:$C$5) ซึ่งมีความหมายเช่นเดียวกับการใส่สูตร =B6*B5+C6*C5 Objective function

Target Cell

edited for 321310 by..Benchaporn

58

LP Excel and Solver Parts Constraints ในแต่ละเงือ่ นไข้อจำากัด(constraint) จะแบ่งเป็น 3 ส่วน คือ (2) ส่วนด้านซ้ายมือ(LHS) ประกอบด้วยทุกๆค่าที่อยู่ด้านซ้ายมือของเครื่องหมายสมการ(=) หรือเครือ่ งหมายอสมการ(≤ , ≥) (3) ส่วนด้านขวามือ(RHS) ประกอบด้วยทุกๆค่าที่อยู่ด้านขวามือของเครื่องหมายสมการ(=) หรือเครือ่ งหมายอสมการ(≤ , ≥) (4) ส่วนเครื่องหมายสมการ(=) หรือเครื่องหมายอสมการ(≤ , ≥) 1 3 2

edited for 321310 by..Benchaporn

59

Entering Information in Solver เรียกใช้งาน Solver โดยคลิก๊ เมนู ToolsSolver • ระบุ Target Cell (D6) • ระบุ Changing Cells (B5, C5)

Flair Furniture T C Tables Chairs Number Of Units Profit Constraints: Carpentry Hours Painting Hours Chairs Limit

edited for 321310 by..Benchaporn

7

5

4 2

3 1 1

0 <-Objective 0 0 0 LHS

<= 240 <= 100 <= 60 Sign RHS

60

Constraints Specifying Constraints • คลิก๊ ปุ่ม "Add" เพือ่ เพิม่ เงื่อนไขข้อจำากัดที่อ้างอิงถึงส่วน LHS และ RHS • โดยอาจเพิ่มเงื่อนไขข้อจำากัดครั้งละหนึ่งเงื่อนไข หรืออาจเพิ่มเงื่อนไขข้อจำากัดทั้งชุดในครั้งเดียวกันได้ หากทั้งชุดเงื่อนไขนัน้ มีเครื่องหมาย (<=, >=, หรือ =) เดียวกัน • จากโจทย์ปัญหานี้ เงือ่ นไขข้อจำากัดทั้งหมดมีเครื่องหมาย <= เหมือนกัน ดังนั้นจึงกำาหนดให้ส่วนซ้ายมือ(LHS) เป็น D8:D10 และส่วนขวามือ(RHS) ของเครื่องหมาย <= เป็น F8:F10 edited for 321310 by..Benchaporn

61

Constraints Specifying Constraints

edited for 321310 by..Benchaporn

62

Solver Options • คลิก๊ ปุ่ม Options เพือ่ กำาหนดตัวเลือกของ Solver

• ต้องเช็คเครื่องหมายถูกที่ checkbox – Assume Linear Model – Assume Non-Negative edited for 321310 by..Benchaporn

63

Solving Model • เมือ่ กดปุ่ม Solve , Solver จะรันตัวแบบ(Model) และแสดงผลลัพธ์ที่ได้

• หน้าต่าง Solver Results จะแสดงรายงานได้สามแบบ คือ - Answer - Sensitivity - Limits edited for 321310 by..Benchaporn

64

Solution • ผลเฉลยที่เหมาะสม(Optimal solution) แสดงว่าต้องผลิตโต๊ะ 30 ตัว และเก้าอี้ 40 ตัว ซึ่งจะทำาให้ได้กำาไรมากที่สุดคือ $ 410 Flair Furniture

Number Of Units Profit Constraints: Carpentry Hours Painting Hours Chairs Limit

T C Tables Chairs 30 40 7 5 410 <-Objective 4 2

3 1 1

240 100 40 LHS

edited for 321310 by..Benchaporn

<= 240 <= 100 <= 60 Sign RHS 65

Possible Messages in Results Window

edited for 321310 by..Benchaporn

66

Flair Furniture Solver Answer Report

edited for 321310 by..Benchaporn

67

Solving LP Problems Using QM for Windows

edited for 321310 by..Benchaporn

68

Using QM for Windows

edited for 321310 by..Benchaporn

69

Using QM for Windows

edited for 321310 by..Benchaporn

70

A Minimization LP Problem ปัญหากำาหนดการเชิงเส้นหลายๆปัญหา อาจมีฟังก์ชันวัตถุประสงค์ เพื่อหาค่าตำ่าสุด เช่น ต้นทุนตำ่าสุด แทนการหาค่ากำาไรสูงสุด ตัวอย่าง เช่น: – ร้านอาหารต้องการจัดตารางการทำางานของพนักงาน ให้ทำางานได้ตามที่ต้องการ โดยจ้างพนักงานจำานวนน้อยที่สุด – ผูผ้ ลิตอาจจะต้องการส่งสินค้าของตนจากโรงงานหลายๆโรงงาน ไปยังคลังสินค้าที่อยู่ในหลายๆที่ โดยให้ค่าใช้จ่ายในการขนส่งน้อยที่สุด – โรงพยาบาลอาจจะต้องการวางแผนรายการอาหารให้กบั คนไข้ โดยคนไข้ต้องได้รับสารอาหารตามเกณฑ์มาตรฐาน โดยให้เกิดต้นทุนการซืedited ้ออาหารตำ ่าที่สุดby..Benchaporn for 321310

71

Example of a Two Variable Minimization LP Problem Holiday Meal Turkey Ranch

• ต้องการเลือกซือ้ อาหารสำาหรับลา 2 ยี่ห้อ โดยมีต้นทุนตำ่าที่สุด • อาหารสัตว์แต่ละยี่ห้อมีสารอาหาร 3 ชนิด ได้แก่ โปรตีน, วิตามิน และธาตุเหล็ก • Brand A 1 ปอนด์ ประกอบด้วย: – โปรตีน 5 หน่วย – วิตามิน 4 หน่วย – ธาตุเหล็ก 0.5 หน่วย • Brand B 1 ปอนด์ ประกอบด้วย: – โปรตีน 10 หน่วย – วิตามิน 3 หน่วย – ธาตุเหล็ก 0 หน่edited วย for 321310 by..Benchaporn

72

Example of Two Variable Minimization Linear Programming Problem Holiday Meal Turkey Ranch • ต้นทุนของอาหาร Brand A เท่ากับ $0.02 ต่อปอนด์ ส่วน Brand B มีต้นทุน $0.03 ต่อปอนด์ • เจ้าของร้านต้องการอาหารที่มีต้นทุนตำ่าที่สุด โดยอาหารยี่ห้อนั้นจะต้องมีสารอาหารแต่ละชนิดขั้นตำ่า edited for 321310 by..Benchaporn

ตามที่ลาจะต้องได้รับในแต่ละเดือน

73

Summary of Holiday Meal Turkey Ranch Data

edited for 321310 by..Benchaporn

74

Formulation of LP Problem: Minimize cost (in cents) = 2A + 3B Subject to: 5A + 10B ≥ 90 (protein constraint) 4A + 3B ≥ 48 (vitamin constraint) ½A ≥ 1½ (iron constraint) A ≥ 0, B ≥ 0 (nonnegativity constraint) โดยที่: A แทนปริมาณของอาหาร Brand A หน่อยเป็นปอนด์ B แทนปริมาณของอาหาร Brand B หน่อยเป็นปอนด์ edited for 321310 by..Benchaporn

75

Graphical Solution of Holiday Meal Turkey Ranch Problem กราฟแสดงเงื่อนไขบังคับ : ½A ≥ 1½

4A + 3B ≥ 48 5A + 10B ≥ 90 Nonnegativity Constraint A ≥ 0, B ≥ 0

edited for 321310 by..Benchaporn

76

Isocost Line Method. กราฟแสดงต้นทุน (cost line) ที่ต้นทุนเท่ากับ 54cent 2A + 3B = 54

edited for 321310 by..Benchaporn

77

Isocost Line Method

• Isocost line จะถูกขยับขนานเส้นแสดงต้นทุนที่ 54-cent ลงไปใกล้กับจุดกำาเนิด. • จากรูปแสดงจุดสุดท้ายที่เส้น isocost line สัมผัส โดยที่ยังอยู่ภายในบริเวณแรเงา(ผลลัพธ์ที่เป็นไปได้) คือจุดมุมหมายเลข 2 edited for 321310 by..Benchaporn

78

Isocost Line Method

• หาพิกัดของจุดตัดหมายเลข 2 ที่สมการเงื่อนไขบังคับทั้งสองตัดกัน จะได้ว่า A= 8.4 และ B=4.8 ดังนั้นผลเฉลยเหมาะที่สุดที่มีต้นทุนตำ่าสุดคือ: 2A + 3B = (2)(8.4) + (3)(4.8) = 31.2 edited for 321310 by..Benchaporn

79

Corner Point Solution Method • Point 1 - (A = 3, B = 12) – ต้นทุนคือ 2(3) + 3(12) = 42 cents • Point 2 - (A = 8.4, b = 4.8) – ต้นทุนคือ 2(8.4) + 3(4.8) = 31.2 cents • Point 3 - (A = 18, B = 0) – ต้นทุนคือ (2)(18) + (3)(0) = 36 cents

• ผลเฉลยที่เหมาะสมที่มีต้นทุนตำ่าที่สดุ คือ: จุดมุมที่ 2, ต้นทุน = 31.2 cents

edited for 321310 by..Benchaporn

4A + 3B ≥ 48 5A + 10B ≥ 90

80

Summary of Graphical Solution Methods 1. วาดกราฟของแต่ละสมการเงือ่ นไขบังคับ 2. หาพื้นที่ผลลัพธ์ที่เป็นไปได้ ซึ่งพื้นที่ดังกล่าวจะเป็นไปตามเงื่อนไขบังคับของปัญหาทุกเงือ่ นไข 3. เลือกวิธีการหาผลเฉลย จากการวาดกราฟ จากนั้นจึงทำาการหาผลเฉลย 1. วิธีหาจุดมุม (Corner Point Method) 2. วิธีลากเส้นผลกำาไร(Isoprofit) หรือเส้นต้นทุน(Isocost)

edited for 321310 by..Benchaporn

81

Summary of Graphical Solution Methods (Continued)

Corner Point Method • หาจุดตัด ที่เป็นมุมของพื้นที่ผลลัพธ์ที่เป็นไปได้ โดยการดูจากกราฟ หรือโดยการแก้สมการ • คำานวณหาผลกำาไร หรือต้นทุน โดยการแทนค่าจุดตัดต่างๆ ลงในฟังก์ชันวัตถุประสงค์ • หาผลเฉลยทีเ่ หมาะทีส่ ุด โดยเลือกจุดมุมที่ให้ค่ากำาไรสูงสุด หรือให้ค่าต้นทุนตำ่าสุด edited for 321310 by..Benchaporn

82

Summary of Graphical Solution Methods (continued) Isoprofit or Isocost Method •

เลือกค่ากำาไรหรือค่าต้นทุนหนึ่งค่า และวาดเส้นกราฟกำาไร/เส้นกราฟต้นทุน เพือ่ แสดงให้เห็นถึงความชันของกราฟ

•

สำาหรับปัญหาการหาค่าสูงสุด ให้ทำาการขยับเส้นกราฟขึ้นไปทางด้านขวา จนกระทั่งสัมผัสกับขอบหรือจุดมุมของพื้นที่ผลลัพธ์ทเี่ ป็นไปได้

•

สำาหรับปัญหาค่าตำ่าสุด ให้ทำาการขยับเส้นกราฟลงไปทางด้านซ้าย จนกระทั่งสัมผัสกับขอบหรือจุดมุมของพื้นที่ผลลัพธ์ทเี่ ป็นไปได้

•

หาผลเฉลยที่เหมาะสมได้จากจุดพิกัด ที่เส้นกราฟกำาไร หรือเส้นกราฟต้นทุนสัมผัสเป็นจุดสุดท้ายของบริเวณพืน้ ที่ผลลัพธ์ที่เป็นไปได้

•

นำาผลเฉลยที่ได้ แทนลงในฟั งก์ชนั วัตถุประสงค์ edited for 321310 by..Benchaporn เพือ่ หาค่ากำาไรหรือต้นทุนที่เหมาะสมที่สุด

83

Special Situations in Solving LP Problems Redundancy: เงื่อนไขข้อจำากัดซำ้าซ้อนเกิดขึ้นในกรณีที่มีเงื่อนไขข้อจำากัดบางเงื่อนไข ทีไ่ ม่มีผลทำาให้พื้นทีแ่ รเงา(พื้นทีผ่ ลลัพธ์ที่เป็นไปได้)เปลี่ยนแปลง

Maximize Profit = 2X + 3Y subject to: X + Y ≤ 20 2X + Y ≤ 30 X ≤ 25 X, Y ≥ 0

edited for 321310 by..Benchaporn

84

Special Situations in Solving LP Problems Infeasibility: เกิดขึ้นเมื่อปัญหาการโปรแกรมเชิงเส้นนั้นไม่มีผลเฉลยที่เป็นไปตามเงื่อน ไขข้อบังคับทั้งหมด X + 2Y ≤ 6 2X + Y ≤ 8 X ≥ 7

edited for 321310 by..Benchaporn

85

Special Situations in Solving LP Problems Unboundedness: เกิดขึ้นในกรณีที่ปัญหาการโปรแกรมเชิงเส้นนั้นไม่มีผลเฉลยที่จำากัด จึงไม่สามารถหาผลเฉลยได้ Maximize profit = $3X + $5Y subject to: X ≥ 5 Y ≤ 10 X + 2Y ≥ 10 X, Y ≥ 0

edited for 321310 by..Benchaporn

86

Alternate Optimal Solutions • An LP problem may have more than one optimal solution. – Graphically, when the isoprofit (or isocost) line runs parallel to a constraint in problem which lies in direction in which isoprofit (or isocost) line is located. – In other words, when they have same slope. edited for 321310 by..Benchaporn

87

Example: Alternate Optimal Solutions Maximize profit = $3x + $2y Subject to: 6X + 4Y ≤ 24 X ≤ 3 X, Y ≥ 0

edited for 321310 by..Benchaporn

88

Example: Alternate Optimal Solutions

• At profit level of $12, isoprofit line will rest directly on top of first constraint line. • This means that any point along line between corner points 321310 by..Benchaporn 89 1 and 2 providesedited an for optimal X and Y combination.

Using Solver to Solve Holiday Meal Turkey Ranch Problem LP formulation for this problem is as follows:

Minimize cost (in cents) = 2A + 3B subject to constraints 5A + 10B ≥ 90

(protein constraint)

4A + 3B ≥ 48

(vitamin constraint)

½A ≥ 1½

(iron constraint)

A, B ≥ 0

(nonnegativity) edited for 321310 by..Benchaporn

90

Holiday Meal Turkey Ranch Problem Spreadsheet

edited for 321310 by..Benchaporn

91

Excel Layout and Solver Entries

edited for 321310 by..Benchaporn

92

Solver Answer Report

edited for 321310 by..Benchaporn

93

Solving LP Problems Using QM for Windows

edited for 321310 by..Benchaporn

94

Using QM for Windows

edited for 321310 by..Benchaporn

95

Summary • Introduced a mathematical modeling technique called linear programming (LP). • LP models used to find an optimal solution to problems that have a series of constraints binding objective value. • Showed how models with only two decision variables can be solved graphically. • To solve LP models with numerous decision variables and constraints, one need a solution procedure such as simplex algorithm. • Described how LP models can be set up on Excel and solved using Solver. edited for 321310 by..Benchaporn

96