Bài giảng Quản lý vận hành - Module B: Quy hoạch tuyến tính

Qu n lýảQu n lýả ậ ậV n hành V n hành

ế ạ ế ạ Quy ho ch tuy n tính Quy ho ch tuy n tính Module B Module B

B-1

Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e

Ạ

ể Nh ng ữNh ng ữ đđi m chính ểi m chính (cid:0) YÊU C U C A BÀI TOÁN QUY HO CH Ủ Ầ TUY N TÍNH

Ạ

Ậ

(cid:0) THI T L P BÀI TOÁN QUY HO CH

Ế Ế Ế TUY N TÍNH (cid:0) Ví d Shader Electronics ụ

Ả

Ạ

Ế

ể

ồ ợ ậ

(cid:0) GI I BÀI TOÁN QUY HO CH TUY N Ồ Ị Ằ TÍNH B NG Đ TH (cid:0) Bi u di n các ràng bu c b ng ễ (cid:0) Phương pháp gi

ộ ằ đ thồ ị ả ằ đư ng ờ đ ng l i nhu n

(CornerPoint

(cid:0) Phương pháp gi Solution Method)

B-2

Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e

ể i b ng (IsoProfit Line Solution Method) i b ng ả ằ đi m góc

ế ế

ể Nh ng ữNh ng ữ đđi m chính – Ti p ể i m chính – Ti p theo theo (cid:0) PHÂN TÍCH Đ NH Y Ạ

ị ế

ụ

Ả Ể

Ứ Ế

ụ ả ụ ự đơn ăn kiêng

Ộ (cid:0) Báo cáo đ nh y ộ ạ (cid:0) Thay đ i ngu n l c c a các giá tr v ph i ả ổ ồ ự ủ (cid:0) Thay đ i h s trong hàm m c tiêu ổ ệ ố (cid:0) GI I BÀI TOÁN C C TI U Ự (cid:0) CÁC NG D NG QUY HO CH TUY N TÍNH Ạ Ụ (cid:0) Ví d s n xu t h n h p ấ ỗ ợ (cid:0) Ví d bài toán th c (cid:0) Ví d ụ đi u ề đ s n xu t ấ ộ ả (cid:0) Ví d ụ đi u ề đ lao đ ngộ ộ

B-3

Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e

Ủ (cid:0) PHƯƠNG PHÁP ĐƠN HÌNH C A LP

ọ ậ ọ ậ

ụ ụ

Các m c tiêu h c t p Các m c tiêu h c t p

ể ương này b n s có th :

ị

ợ ế đư c ho c

ạ ẽ ặ đ nh nghĩa :

ụ

ệ

ồ

ọ Khi h c xong ch ậ Nh n bi t (cid:0) Hàm m c tiêu (cid:0) Các ràng bu cộ (cid:0) Vùng nghi m kh dĩ hay ch p nh n ấ ả (cid:0) Phương pháp đư ng ờ đ ng l ợ i nhu n/

ậ đư cợ ậ đ ng ồ

chi phí ả ể đi m góc

i pháp ầ

(Cornerpoint solution) ờ (Shadow price)

(cid:0) Gi (cid:0) Giá ng m hay giá m

B-4

Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e

ụ ụ

ế ế

ọ ậ ọ ậ Các m c tiêu h c t p – Ti p theo Các m c tiêu h c t p – Ti p theo

ạ ẽ

ể ương này b n s có th : i thích

ế ạ

ồ ị ế ạ

ọ Khi h c xong ch ả ặ ả Mô t ho c gi (cid:0) Các thi ế ậ t l p mô hình quy ho ch tuy n tính (cid:0) Phương pháp đ th trong quy ho ch tuy n

B-5

Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e

ả tính (cid:0) Cách gi i thích phân tích ộ ạ đ nh y

ế ế

ạ ạ

Quy ho ch tuy n tính là gì? Quy ho ch tuy n tính là gì?

(cid:0) K thu t toán h c ọ ậ ả ậ

ỹ (cid:0) Ch không ph i l p trình b ng máy tính (Not

ứ ằ

ồ ự

(cid:0) Phân b các ngu n l c khan hi m

ế đ ể đ t ạ

ụ

ợ ợ

(cid:0) Đư c khai sinh b i (Pioneered by) George

ế ả

computer programming)

i kh thi (workable solution)

ổ ộ đư c m t m c tiêu ở ế Dantzig trong Th Chi n II (cid:0) Đã đưa ra cách gi ả đư c g i là ph 1947

B-6

Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e

ợ ọ ương pháp đơn hình vào năm

ụ ụ

ụ ề ứ ụ ề ứ Các ví d v ng d ng LP Các ví d v ng d ng LP thành công thành công

ộ

(cid:0) Đi u ề đ xe buýt ch h c sinh nh m

ả

ự ể ằ c c ti u ở ọ ổ t ng kho ng cách di chuy n khi ch h c sinh

ở ọ ế đ n các ằ c c ự i ph m cao nh m ạ

ệ

ể ủ ả ạ i các cú

đi n tho i

ạ đ n ế

(cid:0) Phân các đ i tu n tra c a c nh sát ầ ộ ỷ ệ ộ ự l khu v c có t t ờ ti uể th i gian đáp l ố s 911

ộ ữ

(cid:0) Đi u ề đ nh ng ng

i các ngân

ạ ư i thu ngân t ứ

c a ngày mà v n

ổ ự ể t ng chi

ẫ c c ti u

ờ hàng sao cho nhu c u ầ đư c ợ đáp ng trong ờ ủ ỗ m i gi phí lao đ ngộ

B-7

Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e

ụ ề ứ ụ ề ứ

ụ ụ

ế ế

Các ví d v ng d ng LP Các ví d v ng d ng LP thành công – Ti p theo thành công – Ti p theo

ọ

ợ

ỗ

ệ

máy nghi n

ợ ỗ thâp nh tấ

ạ n p li u (feed mills) ạ n p li u hoàn ch nh v i chi phí ự ằ

ẩ ờ

máy và gi

ợ

(cid:0) Ch n h n h p nguyên li u thô ề ở ể đ làm ra các h n h p ớ ỉ (cid:0) L a ch n ph i h p s n ph m trong nhà máy ố ợ ả ờ ấ ố t nh t gi lao ậ ủ ẫ c c ự đ iạ l i nhu n c a

ố ợ

ố

ờ

(cid:0) Phân ph i ch cho m t ph i h p ng

ệ ệ ọ ậ ụ nh m t n d ng t ẵ ộ đ ng s n có mà v n doanh nghi pệ ỗ ự

ư i thuê ộ ớ ề ử m t khu v c có nhi u c a hàng m i nh m

ổ

ở ộ ằ ậ c c ự đ iạ t ng thu nh p cho công ty cho thuê

B-8

Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e

ầ ủ ầ ủ ạ ạ

ế ế

Yêu c u c a bài toán Yêu c u c a bài toán quy ho ch tuy n tính quy ho ch tuy n tính

ự ể s ố

c c ự đ iạ ho c ặ c c ti u

ả ợ

ế

ụ ặ các ràng bu cộ – ụ

ợ

đó (hàm m c tiêu) 2 Có nh ng h n ch ho c ạ ả ăng đ t ạ đư c m c tiêu ố

ờ

nh ng ữ đư ng l

i hành

ộ đ ng khác

ừ đó

1 Ph i tìm cách lư ng nào ữ ớ ạ i h n kh n 3 Ph i là ả ể ọ t đ ch n ụ

ộ

4 Các m c tiêu và các ràng bu c ph i có th ể ả ương trình ớ ạ

ế

di n ễ đ t ạ đư c dợ ư i d ng các ph ặ ấ ho c b t ph

ương trình tuy n tính

B-9

Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e

ế ậ ế ậ

ạ ạ

Thi Thi

t l p bài toán quy ho ch t l p bài toán quy ho ch

ế

ếtuy n tính tuy n tính

ố ả ạ ả ẩ ấ

ị ả đ nh: (cid:0) B n mu n s n xu t hai lo i s n ph m (1) ạ Walkman AM/FM/Cassette và (2) WatchTV và 2 gi

(cid:0) Walkman c n 4 gi

ệ ử ầ ờ ờ ắ làm vi c ệ đi n t l p

ráp

(cid:0) WatchTV c n 3 gi

ầ ờ ệ ử ờ ắ làm vi c ệ đi n t và 1 gi l p

(cid:0) Hi n có 240 gi

ờ ệ ử ờ ắ làm vi c ệ đi n t và 100 gi l p

ráp ệ ráp

(cid:0) Lãi trên m t Walkman là 7$; lãi trên m t WatchTV

ộ ộ

B-10

Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e

ạ ạ

Thi Thi

ế ế

ế ậ ế ậ t l p bài toán quy ho ch t l p bài toán quy ho ch ế ế tuy n tính – ti p theo tuy n tính – ti p theo

Cho:

(cid:0) X1 = s lố ư ng Walkman ợ (cid:0) X2 = s lố ư ng WatchTV ợ

Thì:

240 ộ ề ờ ràng bu c v th i gian đi n tệ ử

ộ ề ờ ắ 100 ràng bu c v th i gian l p ráp

(cid:0) 4X1 + 3X2 (cid:0) (cid:0) 2X1 + 1X2 (cid:0) (cid:0) 7X1 + 5X2 = ti n lãi

B-11

Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e

ề ạ ợ c c ự đ i l ậ i nhu n

ả ằ ả ằ

đđ ồ ồ

i b ng i b ng

ụ

PhPhươương pháp gi ng pháp gi thịthị (cid:0) V ẽ đ th v i tr c tung & tr c hoành (ch ỉ

ứ ấ

ư đư ng ờ

ặ

ồ ị ồ ẳ th ng, r i nh (cid:0) S d ng ( ử ụ

ồ ị ớ ụ góc ph n tầ ư th nh t) (cid:0) V ẽ đ th các ràng bu c nh ộ ẳ ư m t ph ng X1,0), (0,X2) cho đư ng th ng

(cid:0) Tìm vùng nghi m ệ kh dĩả (cid:0) Tìm nghi m ệ t

i ố ưu ể

ẳ ờ

(cid:0) Phương pháp đi m góc (cid:0) Phương pháp đư ng ờ ồ đ ng l

B-12

Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e

ợ ậ i nhu n

Công ty Shader Electronic Công ty Shader Electronic Bài toán Bài toán

ộ ậ B ph n

ố ờ ầ S gi c n thi ấ ả s n xu t 1 X1 Walkmans 4 ế để t đơn vị X2 WatchTV 3 ố ờ ẵ s n có S gi ầ trong tu n này 240 Đi n tệ ử

ắ 100 L p ráp 2 1

5$ 7$

(cid:0)

ố ờ đi n t ) ệ ử ố ờ ắ l p ráp)

B-13

Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e

ụ Lãi/đơn vị Ràng bu c:ộ 4x1 + 3x2 2x1 + 1x2 (cid:0) ạ C c ự đ i: 7x M c tiêu: 240 (s gi 100 (S gi 1 + 5x2

Công ty Shader Electronic Các Công ty Shader Electronic Các ràng bu cộ ràng bu cộ

ộ

120

) 2

ắ

(

100

ộ

Đi n tệ ử (Ràng bu c A) L p ráp (Ràng bu c B)

V T h c t a

W g n ợ ư

ố S

ợ

S lố ư ng Walkman (X

B-14

Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e

ả ả

Công ty Shader Electronic Công ty Shader Electronic ệ ệ Vùng nghi m kh dĩ Vùng nghi m kh dĩ

120

ộ

) 2

ắ

100

ộ

(

Đi n tệ ử (Ràng bu c A) L p ráp (Ràng bu c B)

V T h c t a

Vùng nghi mệ kh dĩả

W g n ợ ư

ố S

ợ

S lố ư ng Walkman (X

B-15

Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e

ồ ồ

ợ ợ

Công ty Shader Electronic Công ty Shader Electronic ĐĐưư ng ờng ờ đđ ng l ng l

i nhu n i nhu n

120

) 2

100

7*X1 + 5*X2 = 420

ắ

(

ộ

ậ ậ Đi n tệ ử (Ràng bu cA)ộ L p ráp (Ràng bu c B)

V T h c t a

Đư ng ờ đ ngồ ậ ợ l

i nhu n

7*X

1 + 5*X

W g n ợ ư

2 = 210

ố S

ợ

S lố ư ng Walkman (X

B-16

Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e

Công ty Shader Electronic Công ty Shader Electronic

ả ảGi Gi

i pháp i pháp

ể ểi m góc đđi m góc

ộ

ợ

ồ đ ng l

) 2

ắ

Đư ng ờ nhu nậ

120

ộ

Đi n tệ ử (Ràng bu c A) L p ráp (Ràng bu c B)

(

100

ể

ể Nghi m có th ạ đi m góc t

ệ i các

V T h c t a

W g n ợ ư

ố S

ợ

S lố ư ng Walkman (X

B-17

Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e

Công ty Shader Electronic Công ty Shader Electronic

ệ ệ Nghi m t Nghi m t

ố ưưuu ố i i

ộ

ợ

ồ đ ng l

ắ

) 2

Đư ng ờ nhu nậ

ộ

120

Đi n tệ ử (Ràng bu c A) L p ráp (Ràng bu c B)

(

100

ể

ể Nghi m có th ạ đi m góc t

ệ i các

V T h c t a

ệ Nghi m t

ố ưu i

W g n ợ ư

ố S

ợ

S lố ư ng Walkman (X

B-18

Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e

Công ty Shader Electronic Công ty Shader Electronic

ệ ệ nghi m t nghi m t

ố ưưuu ố i i

ộ

ồ

ợ

đ ng l

ắ

) 2

Đư ng ờ nhu nậ

ộ

120

Đi n tệ ử (Ràng bu c A) L p ráp (Ràng bu c B)

(

100

ể

ể Nghi m có th ạ đi m góc t

ệ i các

X1 = 30

V T h c t a

X2 = 40

ệ Nghi m t

ố ưu i

W g n ợ ư

ố S

ợ

S lố ư ng Walkman (X

B-19

Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e

Trình bày l Trình bày l

ờ ả ờ ả i i gi i gi i

(cid:0) Các bi n quy t ế

ả ấ đư cợ

ị ế đ nh (cid:0) X1 = s t n hoá ch t BW s n xu t (cid:0) X2 = s t n hoá ch t Color s n xu t

ố ấ ố ấ ấ ấ ả ấ đư cợ

(cid:0) M c tiêu ụ (cid:0) C c ti u (cid:0) Các ràng bu cộ

ự ể Z = 2500X1 + 3000X2

(cid:0) X1 ‡ 30 (BW); X2 ‡ 20 (Color) (cid:0) X1 + X2 ‡ 60 (T ng l ư ng hàng) ổ (cid:0) X1 ‡ 0; X2 ‡ 0 (Không âm)

B-20

Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e

ợ

ế ấ đ ể đưa vào l 1. Ch n bi n có C i ờ

Các bCác bưư c ớc ớ đơđơn hình cho bài toán n hình cho bài toán c c ực c ự đđ iạiạ ớ j Zj dương l n nh t

ọ iả gi

ế ằ ầ

2. Xác đ nh hàng c n thay th b ng cách ch n hàng mà ố ị s gi a c t h ng s và các ph n t

ỷ ố ữ ộ ằ ứ ỏ ọ ầ ử ủ ộ có t c a c t ấ xoay tương ng (không âm) nh nh t

ả ị ớ 3. Tính các giá tr m i cho hàng xoay ị ớ 4. Tính các giá tr m i cho (các) hàng xoay khác 5. Tính các giá tr Cị

j và CjZj cho b ng này. ố jZj nào l n hớ

ấ ỳ ế N u còn b t k con s C ở ề ơn 0, hãy tr v

B-21

Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e

bư c 1.ớ

ế ờ ọ 1. Ch n bi n có C ấ đ ể đưa vào l i gi ả i

ế ằ

Các bCác bưư c ớc ớ đơđơn hình cho bài toán n hình cho bài toán ự ể ự ể c c ti u c c ti u ớ j Zj âm l n nh t ầ 2. Xác đ nh hàng c n thay th b ng cách ch n hàng mà ố

ị s gi a c t h ng s và các ph n t

ỷ ố ữ ộ ằ ứ ỏ ọ ầ ử ủ ộ có t c a c t ấ xoay tương ng (không âm) nh nh t

j và CjZj cho b ng này.

ả ị ớ 3. Tính các giá tr m i cho hàng xoay ị ớ 4. Tính các giá tr m i cho (các) hàng xoay khác 5. Tính các giá tr Cị

ấ ỳ ế N u còn b t k con s C

B-22

Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e

ố jZj nào nh hỏ ơn 0, hãy tr ở v bề ư c 1.ớ

ộ ạ ộ ạ nh y Phân tích đđ nh y Phân tích

ể

(cid:0) D ự đoán nghi m có th thay ệ

ặ

ổ

ổ đ i bao nhiêu ế đ i trong các bi n ho c

ị ủ

ộ đơn v ị

ữ ế n u có nh ng thay ầ ữ ệ đ u vào. d li u (cid:0) Giá m (ờ đ i ng u) – giá tr c a m t ố ẫ ồ ự ăng thêm ngu n l c t

B-23

Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e

ự ể ự ể

ụ ụ

Ví d bài toán c c ti u Ví d bài toán c c ti u

ờ

ấ ấ

ấ

ả

BW: 2.500$ chi BW: 2.500$ chi ỗ ả phí s n xu t m i ỗ ả phí s n xu t m i tháng tháng

ể

ỗ i thi u 30 t n BW

i thi u

ả ấ và ộ ố . Toàn b s ả ợ ấ đư c ph i ầ ả ể là 60 t nấ . C n s n xu t ạ

ấ

ộ ộ ư i phân tích cho m t b ạ B n là ng ậ ủ ph n c a Kodak, s n xu t các hoá ấ ch t BW & color. M i tháng ph i ố ấ t ả s n xu t ấ ể ố t i thi u 20 t n color ấ ả lư ngợ hoá ch t s n xu t ấ ố t ấ đ ể ỗ bao nhiêu t n m i lo i hoá ch t ự ể chi phí? c c ti u

ả

ấ

ỗ

Color: 3.000$ chi phí s n xu t m i tháng

B-24

Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e