Bài giảng Tin học trong quản lý xây dựng chương 4: ThS. Đỗ Thị Xuân Lan

4 Q h

Chương 4 Quy hoạch Ch h tuyến tính số nguyên tuyến tính số nguyên

Tin học trong quản lý

ế

Chương 4Quy hoạch tuyến tính số nguyên ố Quy hoạch tuyến tính thuần nguyên • Quy hoạch tuyến tính thuần nguyên • Quy hoạch tuyến tính số nguyên hỗn

hợpợp

• Quy hoạch tuyến tính nhị nguyên Bài toán pha cắt vật tư • Bài toán pha cắt vật tư • Bài toán rút ngắn thời gian đường găng

có ét đế yếu tố c p có xét đến yếu tố chi phí

Chương 4 Quy hoạch tuyến tính số Chương 4 Quy hoạch tuyến tính số nguyên MÔ HÌNH QUY HOẠCH TUYẾN MÔ HÌNH QUY HOẠCH TUYẾN TÍNH THUẦN NGUYÊN

MÔ HÌNH QUY HOẠCH TUYẾN TÍNH THUẦN NGUYÊN TÍNH THUẦN NGUYÊN

p p

ự ị

ộ

Ví dụ 4.1: Ví d 4 1 Để phát triển sản xuất,chủ cơ cở gia công cốp pha dự định mua thêm một số máy y dập và máy tiện.Ước tính mỗi máy dập mỗi ngày cho 70USD tiền lời và máy tiện là 60USD tiền lời.Ông chỉ có 30.000USD là 60USD tiền lời.Ông chỉ có 30.000USD và diện tích xưởng có 12 m2.

Biết :

hiế

Má dậ

+ Máy dập chiếm 2m2 , giá 6.000 USD 2 2 iá 6 000 USD + Máy tiện chiếm 3m2, giá 5.000 USD Vậy số lượng máy mỗi loại nên mua bao Vậy số lượng máy mỗi loại nên mua bao

nhiêu thì tiền lời nhất.

MÔ HÌNH QUY HOẠCH TUYẾN TÍNH THUẦN NGUYÊN TÍNH THUẦN NGUYÊN

 Tóm tắt bài toán :

Tài nguyên Máy dập(x1) Máy tiện (x2) Khả năng đáp ứng

Tiền lời Tiề lời

70USD 0USD

60USD 60USD

Diện tích Diện tích

12 12

2 2

3 3

Giá

6.000USD

5.000USD

30.000

MÔ HÌNH QUY HOẠCH TUYẾN TÍNH THUẦN NGUYÊN TÍNH THUẦN NGUYÊN

Mô hình toán:

Hàm mục tiêu: Z = 70x1 +60x2 USD (cid:0) max

Các ràng buộc: 6x1 + 5x2 ≤ 30 (1.000USD) 6x + 5x ≤ 30 (1 000USD) 2x1 + 3x2 ≤ 12 (m2 )

Điều kiện biên: x1 ≥ 0, x2 ≥ 0

h t ế h

6 6

6X1 + 5X2 =30

n n ệ i t y á

D(4,2)

Lời giải tối ưu X1 3.75 ,X2 1.5 X1 =3 75 X2 =1 5 lợi nhuận = 352.5 USD

1 1

2X1 + 3X2 =12 2X + 3X =12

Z=340

E(4,1)

Z=350

3 3

4 4

B(5,0) 5 5

6 6

1 1

2 2

Máy dập

Giải bài toán quy hoạch tuyến Giải bài t á tính số nguyên bằng phương ị pháp đồ thị p p

MÔ HÌNH QUY HOẠCH TUYẾN TÍNH THUẦN NGUYÊN TÍNH THUẦN NGUYÊN

Mô hình toán:

Hàm mục tiêu: Z = 70x1 +60x2 USD (cid:0) max Z = 70x +60x USD (cid:0) max

Các ràng buộc: 6x1 + 5x2 ≤ 30 (1.000USD) 6x + 5x ≤ 30 (1 000USD) 2x1 + 3x2 ≤ 12 (m2 )

Điều kiện biên:

x1 ≥ 0, x2 ≥ 0 bổ sung x1 , x2 nguyên

MÔ HÌNH QUY HOẠCH TUYẾN TÍNH THUẦN NGUYÊN TÍNH THUẦN NGUYÊN

+ Lợi nhuận =350 Lời giải tối ưu của bài toán quy hoạch tuyến tính số nguyên í h ố ế ê

ố

+ Lợi nhuận =340 Lời giải khi làm tròn nghiệm tối ưu của bài toán quy hoạch tuyến tính y

Chương 4 Quy hoạch tuyến tính số Chương 4 Quy hoạch tuyến tính số nguyên MÔ HÌNH QUY HOẠCH MÔ HÌNH QUY HOẠCH TUYẾN TÍNH NHỊ NGUYÊN

MÔ HÌNH QUY HOẠCH TUYẾN TÍNH NHỊ NGUYÊN TÍNH NHỊ NGUYÊN Bài toán : Chính quyền thị trấn Tương Lai đang xem Chính quyền thị trấn Tương Lai đang xem xét sẽ xây dựng những công trình thể thao trong bốn công trình được đề nghị sau đây :

g ị

ợ

Công trình thể thao thao

Số người kỳ vọng sử dụng vọng sử dụng hàng ngày

Kinh phí xây dựng (triệu dựng (triệu đồng )

Diện tích mặt bằng cần thiết bằng cần thiết (1000m2 )

Hồ bơi

300

3500

Sân quần vợt

1000

Sân điền kinh

400

2500

Nhà thi đấu mini

150

9000

ợp

ộ

ị

ấ

ể

MÔ HÌNH QUY HOẠCH TUYẾN TÍNH NHỊ NGUYÊN TÍNH NHỊ NGUYÊN Tổng mặt bằng dành cho các công trình không được vượt quá 12000 m2 Tổng kinh không được vượt quá 12000 m .Tổng kinh phí để xây dựng chỉ có 12 tỷ đồng. Thị trấn chỉ có một khu đất có địa thế thích hợp để có thể để xây dựng hoặc hồ bơi hoặc sân quần vợt. Nên xây dựng công trình nào để người dân trong thị trấn có thể sử dụng được nhiều nhất?

là h

â d

Gọi : (cid:0) x1 là chọn phương án xây dựng hồ (cid:0) hồ

bơi .

là h

â d

h ơ

(cid:0) x2 là chọn phương án xây dựng sân (cid:0)

quần vợt .

(cid:0) x3 là chọn phương án xây dựng sân (cid:0) x là chọn phương án xây dựng sân

điền kinh .

(cid:0) x4 là chọn phương án xây dựng nhà (cid:0) x là chọn phương án xây dựng nhà

thi đấu 0 thì phương án i không – Nếu xi = 0 thì phương án i không Nếu xi được chọn ngược lại xi = 1 thì p phương án i được chọn .

MÔ HÌNH QUY HOẠCH TUYẾN TÍNH NHỊ NGUYÊN TÍNH NHỊ NGUYÊN Mô hình bài toán : * Hàm mục tiêu : Hàm mục tiêu :

Z = 300 x1 + 90x2 + 400x3 + 150x4  max

ộ

* Các ràng buộc : g - Ràng buộc về kinh phí : 3500x1 + 1000x2 + 2500x3 + 9000x4 ≤ 12000 - Ràng buộc về địa điểm xây dựng : x1 + x2 ≤ 1 x + x ≤ 1 - Ràng buộc về diện tích đất : 3x4 ≤ 12 4x1 + 2x2 + 7x3 + 3x4 ≤ 12 7x3 4x1

2x2

* Điều kiện biên : x1 , x2 , x3 , x4  0,1

MÔ HÌNH QUY HOẠCH TUYẾN TÍNH NHỊ NGUYÊN TÍNH NHỊ NGUYÊN

Lời giải tối ưu của bài toán là :

x1 = 1 ( xây dựng hồ bơi) 0 ( không xây dựng sân quần vợt ) x2 = 0 ( không xây dựng sân quần vợt ) x2 x3 = 1 ( xây dựng sân điền kinh ) x4 = 0 ( không xây dựng nhà thi đấu mini)

Z = 700 người .

Chương 4 Quy hoạch tuyến tính số Chương 4 Quy hoạch tuyến tính số nguyên MÔ HÌNH QUY HOẠCH TUYẾN MÔ HÌNH QUY HOẠCH TUYẾN TÍNH SỐ NGUYÊN HỖN HỢP

MÔ HÌNH QUY HOẠCH TUYẾN TÍNH SỐ NGUYÊN HỖN HỢP TÍNH SỐ NGUYÊN HỖN HỢP

 Ví dụ 4.2: g ị

Ông Giàu có tiền vốn là 250.000USD định đầu tư theo 3 phương án sau:

1.Mua xe ô tô chở khách, mỗi xe giá

50.000USD, cuối năm cho tiền lời 5.000USD. 50 000USD cuối năm cho tiền lời 5 000USD

2.Mua đất vườn, mỗi ha đất giá 12.000USD,

cuối năm cho tiền lời 1.500USD. hiế 3.Mua tín phiếu kho bạc, mỗi 3 M ỗi b tí

tín phiếu giá tí iá hiế kh 8.000USD,cuối năm lãnh tiền lời 1.000USD.

g ậy ự

ụ g g g ị

Vậy ông Giàu nên đầu tư vào dự án như thế nào để tiền lời nhiều nhất? Biết rằng ông Giàu chỉ nên mua tối đa 4 xe ô tô để đảm bảo có kế hoạch sử y dụng thường xuyên và khu đất ông Giàu định mua chỉ còn 30ha.

MÔ HÌNH QUY HOẠCH TUYẾN TÍNH SỐ NGUYÊN HỖN HỢP TÍNH SỐ NGUYÊN HỖN HỢP

• Gọi : x1 là số xe ô tô sẽ mua x2 là số ha đất sẽ mua là ố h đất ẽ x3 là số tín phiếu sẽ mua

• Mô hình toán: • Mô hình toán:

axm

– Hàm mục tiêu: (để có tiền lời mỗi năm nhiều nhất)

3 (

) Z = 5.000x1 + 1.500x2 + 1000x3 (USD)

– Các ràng buộc :

50.000x1 + 12.000x2 + 8.000x3 ≤ 250.000 (USD) x1 ≤ 4 x2 ≤ 30 ề – Điều kiện biên:

x1 ≥ 0 , nguyên; x2 ≥ 0 ; x3 ≥ 0 , nguyên

MÔ HÌNH QUY HOẠCH TUYẾN TÍNH SỐ NGUYÊN HỖN HỢP TÍNH SỐ NGUYÊN HỖN HỢP

Lời giải tối ưu của bài toán là: – x1 = 0 xe ô tô sẽ mua – x2 = 7,5 ha đất sẽ mua – x3 = 20 tín phiếu sẽ mua – Tiền lời thu được hàng năm Z = 31.250 USD

Lời giải tối ưu thứ hai của bài toán là:

– x1 = 0 xe ô tô sẽ mua – x2 = 20,83 ha đất sẽ mua – x3 = 0 tín phiếu sẽ mua – Tiền lời thu được hàng năm Z = 31.250 USD

Chương 4 Quy hoạch tuyến tính số Chương 4 Quy hoạch tuyến tính số nguyên BÀI TOÁN PHA CẮT VẬT BÀI TOÁN PHA CẮT VẬT TƯ

BÀI TOÁN PHA CẮT VẬT TƯ

g p

Ø 16 dài 2 9

176 đ

ụ Ví dụ 4.4 : Có một số thanh cốt thép Ø16 dài 11,7m. Để thi công lắp đặt cốt thép dầm, cột cho một p tầng của một tòa nhà bê tông cốt thép thì cần phải có 210 đoạn Ø 16 dài 2,1m; 161 đ 161 đoạn Ø 16 dài 2,9m; 176 đoạn Ø 16 dài Ø 16 dài 3,2m; 48 đoạn Ø 16 dài 4,2m. Vậy nên cắt cốt thép như thế nào để tốn ít thanh nguyên cốt thép như thế nào để tốn ít thanh nguyên nhất

BÀI TOÁN PHA CẮT VẬT TƯ

 Đặt tên biến:

ặ

Gọi x1 là số thanh nguyên pha cắt theo PA 1 Gọi xi là số thanh nguyên pha cắt theo PA i

Các phương án pha cắt từ thanh nguyên 11,7m được trình bày trong bảng sau : được trình bày trong bảng sau :

Số lượng các đoạn

Các phương án

Mẫu thừa (m)

2.1m

2.9m

3.2m

4.2m

0

1

2

0.1 0 0

1 1

0 0

2 2

0.4 0 4

1

0

2

1.2

0

2

1

1.1 0 0

1 1

1.4 1 4

0

2

0

1

1.7

2

1

0

1

0.4

3

0

1

1.2

1

0

3

0

1

2

0

0.3

2

0

2

0

1.1

1

2

1

0

0.6

2

1

0

1.4

4

0

1

0

0.1

0

4

0

0.1

1

3

0

0.9

2

0

1.7

4

1

0

0.4

5

0

1.2 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17 x18 x19

BÀI TOÁN PHA CẮT VẬT TƯ

ặ

 Đặt tên biến: Gọi x1 là số thanh nguyên pha cắt theo phương án 1 Gọi xi là số thanh nguyên pha cắt theo phương án i  Mô hình toán :

ụụ Hàm mục tiêu Hàm mục tiêu

min



 x i

1 19  

Điều kiện biên: Điề kiệ biê

≥ 0

xi ≥ 0, nguyên ê

BÀI TOÁN PHA CẮT VẬT TƯ

0x1 + 0x2 + 1x3 + 0x4 + 0x5 + 0x6 + 2x7 + 3x8 + 1x9 + 1x10 + 2x11 + 1x12 + 2x13 + 4x14 + 0x15 + 12 11 13 1x16 + 2x17 + 4x18 + 5x19 ≥ 210

+ 3

+ 0

+ 4

+ 2

+ 0

0x1 + 1x2 + 0x3 + 0x4 + 1x5 + 2x6 + 1x7 + 0x8 + 0x9 + 1x10 + 0x11 + 2x12 + 1x13 + 0x14 + 4x15 + 3x16 + + + 1 + 1 2x17 + 1x18 + 0x19 ≥ 161

Điều kiện ràng buộc:

1x1 + 0x2 + 0x3 + 2x4 + 1x5 + 0x6 + 0x7 + 0x8 + 3x9 + 2x10 + 2x11 + 1x12 + 1x13 + 1x14 + 0x15 + 0x16 + 0x17 + 0x18 + 0x19 ≥ 176

Có đủ 210 đoạn dài 2.1m Có đủ 161 đoạn dài 2.9m Có đủ 176 Có đủ 176 đoạn dài 3.2m

Có đủ 48 ạ đoạn dài 4.2m

BÀI TOÁN PHA CẮT VẬT TƯ

 Lời giải tối ưu của bài toán:

BÀI TOÁN PHA CẮT VẬT TƯ

Ví dụ 4.5 :

Có hai loại thanh cốt thép dài 6m và 8m. Cần phải gia công 100 đoạn dài 2,4m và 150 đoạn dài 2,8m. Nên cắt cốt thép như thế nào để cho tiết kiệm nhất

BÀI TOÁN PHA CẮT VẬT TƯ

 Đặt tên biến:

là ố th

ắt th

G i Gọi x1 là số thanh nguyên pha cắt theo PA1 PA1 Gọi xi là số thanh nguyên pha cắt theo PA i Các phương án pha cắt từ thanh nguyên 6m : ắ

BÀI TOÁN PHA CẮT VẬT TƯ

 Đặt tên biến:

là ố th

ắt th

G i Gọi x1 là số thanh nguyên pha cắt theo PA1 PA1 Gọi xi là số thanh nguyên pha cắt theo PA i Các phương án pha cắt từ thanh nguyên 8m : ắ

BÀI TOÁN PHA CẮT VẬT TƯ

Để tổng chiều dài các thanh nguyên được sử dụng ít nhất

Hàm mục tiêu

min

(x1 + x2 + x3)6 + (x4 + x5 + x6)8 min

Để tổng chiều dài các mẫu thừa là ít nhất

4x1 + 8x2 + 12x3 + 0x4 + 4x5 + 8x6

Điều kiện biên : Điề kiệ biê

xi ≥ 0, nguyên

BÀI TOÁN PHA CẮT VẬT TƯ

Điều kiện ràng buộc:

0x1 + 1x2 + 2x3 + 1x4 + 2x5 + 3x6 = 100 (100 đoạn dài 2,4m)

2x1 + 1x2 + 0x3 + 2x4 + 1x5 + 0x6 = 150 (150 đoạn dài 2,8m)

BÀI TOÁN PHA CẮT VẬT TƯ

 Lời giải tối ưu của bài toán:

Chương 4 Quy hoạch tuyến tính số Chương 4 Quy hoạch tuyến tính số nguyên RÚT NGẮN THỜI GIAN HOÀN RÚT NGẮN THỜI GIAN HOÀN THÀNH DA CÓ XÉT ĐẾN CHI PHÍ PHÍ

RÚT NGẮN THỜI GIAN HOÀN THÀNH DA CÓ XÉT ĐẾN CHI PHÍ THÀNH DA CÓ XÉT ĐẾN CHI PHÍ

Ví dụ 4.6 : Ví d 4 6

y ự g

Rút ngắn thời gian của DA xây dựng nhà công nghiệp của công ty ABC. - Thời gian thực hiện DA là 12 tuần - Chi phí rút ngắn thấp nhất ấ

ắ

ấ

RÚT NGẮN THỜI GIAN HOÀN THÀNH DA CÓ XÉT ĐẾN CHI PHÍ THÀNH DA CÓ XÉT ĐẾN CHI PHÍ

Sơ đồ mạng: S đồ

A2 C2

E4 E4 H2 H2 BĐ

G5 G5

B3 D4

RÚT NGẮN THỜI GIAN HOÀN THÀNH DA CÓ XÉT ĐẾN CHI PHÍ

Thời gian ( tuần )

Công Công việc

Rút ngắn

Chi phí ( ngàn đồng ) Thời gian rút ngắn ắ út được

Chi phí rút ngắn ắ út đơn vị

Bình thường

, 22,000

, 23,000

1,000

30,000

34,000

2,000

26,000

27,000

1,000

48,000

49,000

1,000

56,000

58,000

1,000

F F

3 3

2 2

30,000 30,000

30,500 30,500

1 1

500 500

80,000

86,000

2,000

16,000

19,000

3,000

RÚT NGẮN THỜI GIAN HOÀN THÀNH DA CÓ XÉT ĐẾN CHI PHÍ THÀNH DA CÓ XÉT ĐẾN CHI PHÍ

Đặt tên biến (cid:0) Gọi X là thời điểm kết sớm (EF) của một công việc

XA = EF của công việc A X = EF của công việc B XB = EF của công việc B ………………………. XH = EF của công việc H

g ệ g

(cid:0) Gọi Y là thời gian rút ngắn (tuần) của từng công việc YA = thời gian rút ngắn của công việc A g YB = thời gian rút ngắn của công việc B …………………………. YH = thời gian rút ngắn của công việc H Y = thời gian rút ngắn của công việc H

RÚT NGẮN THỜI GIAN HOÀN THÀNH DA CÓ XÉT ĐẾN CHI PHÍ

Xác định hàm mục tiêu

Vì mục tiêu của bài toán là cực tiểu chi phí rút ngắn nên hàm mục tiêu của bài toán quy hoạch tuyến tính là:

Z Z = 1 000YA + 2 000YB + 1 000YC + 1 000YD +

1,000YA + 2,000YB + 1,000YC + 1,000YD + + 1,000YE + 500YF + 2,000YG + 3,000YH → min

RÚT NGẮN THỜI GIAN HOÀN THÀNH DA CÓ XÉT ĐẾN CHI PHÍ THÀNH DA CÓ XÉT ĐẾN CHI PHÍ

Xác định các ràng buộc

Thời gian ( tuần )

Ràng buộc về thời gian rút ngắn ( Yi)

Công việc ệc

Thời gian rút ngắn được đ

Rút

ắ

Bì h th ờ Bình thường Rút ngắn 2

(cid:0) Ràng buộc về thời gian rút ngắn: (cid:0) Ràng buộc về thời gian rút ngắn:

1 A 1

B B 1 1 2 2 3 3

C 1 1 2

D D 3 3 1 1 4 4

E 2 2 4

F G 2 2 3 5

RÚT NGẮN THỜI GIAN HOÀN THÀNH DA CÓ XÉT ĐẾN CHI PHÍ THÀNH DA CÓ XÉT ĐẾN CHI PHÍ

ó ột à hệ ủ ề ối b ộ iệ iệ ô

(cid:0) Ràng buộc về mối quan hệ giữa các công việc: Mỗi công việc có một ràng buộc về mối quan hệ của công việc Mỗi ô đứng trước. Dạng thức của ràng buộc này là:

g g

Ràng buộc về quan hệ trước sau Công việc EF của công việc sau ≥ EF của công việc đứng trước + (t-Y) ) Công việc

BĐ F

X B B

H H D D ( g Ràng buộc về quan hệ trước sau XF – XC + YF ≥ 3 XG – XD + YG ≥ 5 XG – XE + YG ≥ 5 X Y ≥ 5 XH – XF + YH ≥ 2 XH – XG + YH ≥ 2 X X + Y ≥ 2

E XBD = 0 X 0 XA - XBD + YA ≥ 2 XB - XBD + YB ≥ 3 X X Y ≥ 3 XC – XA + YC ≥ 2 X XD – XB + YD ≥ 4 X + Y ≥ 4 XE – XC + YE ≥ 4