Chapter 3

Qui hoạch Tuyến tính (QHTT) Thiết lập bài toán & Giải bằng Đồ thị

Phụ trách: TS. Đinh Bá Hùng Anh Tel: 01647.077.055/090.9192.766 Mail: anhdbh_ise7@yahoo.com

Nội dung

(cid:132) Bài toán cực đại

(cid:132) Giải bằng đồ thị

(cid:132) Bài toán cực tiểu

(cid:132) Trường hợp đặc biệt

(cid:132) Bài tập ví dụ

Các thành phần của bài toán QHTT

(cid:132) Biến – Mô tả mức độ hoạt động.

(cid:132) Hàm mục tiêu – Mô hình tuyến tính mô tả mục tiêu.

(cid:132) Ràng buộc – Mô tả các ràng buộc của tài nguyên.

(cid:132) Tham số - Các hệ số và hằng số dùng trong hàm mục

tiêu và ràng buộc.

Bài toán QHTT (cực đại)

Hình thành bài toán

Bước 1 : Định nghĩa các biến Bước 2 : Thiết lập hàm mục tiêu Bước 3 : Hình thành các ràng buộc

Bài toán công ty gốm: C.ty gốm nên sản suất bao chén và ly

để tối đa hóa lợi nhuận với các ràng buộc về lao động và đất sét cho ở bảng?

Yêu cầu tài nguyên

Sản phẩm

Lao động (Giờ/sp)

Đất sét (đv/sp)

Lợi nhuận (k/sp)

Chén

1

4

40

Ly

2

3

50

Bài toán QHTT (cực đại)

Đất sét

120 đv/ngày

Đất sét

Lao đông

Đất sét

40 giờ/ngày

Ly 50k

Chén 40k

Hình 3.1 Công ty gốm

Bài toán QHTT

Tài nguyên: 40 giờ lao động/ngày, 120 đơn vị đất sét/ngày

B1: Biến:

x1 = Lượng chén/ngày x2 = Lượng ly/ngày

B2: Hàm mục tiêu

Maximize Z = 40x1 + 50x2, Với Z = Lợi nhuận/ngày

B3: Ràng buộc:

1x1 + 2x2 ≤ 40 giờ lao động 4x1 + 3x2 ≤ 120 đơn vị

Điều kiện không âm

x1 ≥ 0; x2 ≥ 0

Bài toán QHTT

Bài toán dạng tổng quát

St:

Maximize Z = 40x1 + 50x2 1x1 + 2x2 ≤ 40 4x1 + 3x2 ≤ 120 x1, x2 ≥ 0

Lời giải khả dĩ: Không vi phạm các ràng buộc

Chẳng hạn:

x1 = 5 Chén x2 = 10 Ly Z = 40x1 + 50x2 = 700

Kiểm tra lao động:

1(5) + 2(10) = 25 < 40 giờ

Đất sét:

4(5) + 3(10) = 70 < 120 đơn vị

Lời giải không hợp lệ

Lời giải không hợp lệ vi phạm một trong các ràng buộc:

Chẳng hạn:

x1 = 10 chén x2 = 20 ly Z = 40x1 + 50x2 = 1400

Ràng buộc lao động: 1(10) + 2(20) = 50 > 40 Giờ

Trục tọa độ Phương pháp đồ thị (bt. cực đại) (1 of 12)

(cid:132) Thường để giải b.toán 2 biến (cid:132) Trực quang

X2: Ly

Maximize Z = 40x1 + 50x2 St:

X1 Chén

1x1 + 2x2 ≤ 40 4x1 + 3x2 ≤ 120 x1, x2 ≥ 0

Hình 3.2 Trục tọa độ

Ràng buộc lao động Phương pháp đồ thị (2 of 12)

Maximize Z = 40x1 + 50x2 St:

1x1 + 2x2 ≤ 40 4x1 + 3x2 ≤ 120 x1, x2 ≥ 0

Hình 3.3 Ràng buộc lao động

Vùng cung ứng lao động khả dĩ Phương pháp đồ thị (3 of 12)

Maximize Z = 40x1 + 50x2 St:

1x1 + 2x2 ≤ 40 4x1 + 3x2 ≤ 120 x1, x2 ≥ 0

Hình 3.4 Vùng lao động khả dĩ (A)

Ràng buộc tài nguyên đất sét Phương pháp đồ thị (4 of 12)

Maximize Z = 40x1 + 50x2 St:

1x1 + 2x2 ≤ 40 4x1 + 3x2 ≤ 120 x1, x2 ≥ 0

Hình 3.5 Ràng buộc tài nguyên đất sét

Kết hợp các ràng buộc Phương pháp đồ thị (5 of 12)

Maximize Z = 40x1 + 50x2 St:

1x1 + 2x2 ≤ 40 4x1 + 3x2 ≤ 120 x1, x2 ≥ 0

Hình 3.6 Cả 2 ràng buộc

Lời giải khả dĩ Phương pháp đồ thị (6 of 12)

Maximize Z = 40x1 + 50x2 St:

1x1 + 2x2 ≤ 40 4x1 + 3x2 ≤ 120 x1, x2 ≥ 0

Hình 3.7 Vùng lời giải khả dĩ (R)

Lời giải = 800k Phương pháp đồ thị (7 of 12)

Maximize Z = 40x1 + 50x2 St:

1x1 + 2x2 ≤ 40 4x1 + 3x2 ≤ 120 x1, x2 ≥ 0

Hình 3.8 Đường mục tiêu với Z = 800k

Đường mục tiêu tương đương Phương pháp đồ thị (8 of 12)

Maximize Z = 40x1 + 50x2 St:

1x1 + 2x2 ≤ 40 4x1 + 3x2 ≤ 120 x1, x2 ≥ 0

Hình 3.9 Đường mục tiêu tương đương

Giải pháp tối ưu Phương pháp đồ thị (9 of 12)

Maximize Z = 40x1 + 50x2 St:

1x1 + 2x2 ≤ 40 4x1 + 3x2 ≤ 120 x1, x2 ≥ 0

Hình 3.10 Xác định giải pháp tối ưu

Trục tọa độ tối ưu Phương pháp đồ thị (10 of 12)

Maximize Z = 40x1 + 50x2 St:

1x1 + 2x2 ≤ 40 4x1 + 3x2 ≤ 120 x1, x2 ≥ 0

Hình 3.11 Trục tọa độ tối ưu

Điểm-góc Phương pháp đồ thị (11 of 12)

(cid:41) Lý thuyết toán học đã chứng minh điểm cực trị chỉ nằm ở các điểm cực biên (điểm-góc).

(cid:41) Để tìm điểm tối ưu thông qua điểm-góc, ta tìm hàm mục tiêu cho các điểm-góc rồi chọn điểm tối ưu.

Maximize Z = 40x1 + 50x2 St:

1x1 + 2x2 ≤ 40 4x1 + 3x2 ≤ 120 x1, x2 ≥ 0

Hình 3.12 Lời giải ở các đỉnh A, B, C

Biến thiếu - Dạng chuẩn (12 of 12)

(cid:132) Dạng chuẩn: Tất cả các ràng

(cid:132) Biến thiếu được sử dụng để chuyển ràng buộc dạng ≤ thành (=).

(cid:132) Biến thiếu không ảnh hưởng đến trị của hàm mục tiêu.

buộc ở dạng (=).

Max Z = 40x1 + 50x2 + s1 + s2 St:

1x1 + 2x2 + s1 = 40 4x1 + 3x2 + s2 = 120 x1, x2, s1, s2 ≥ 0

Trong đó:

Hình 3.13 Điểm giải pháp A, B, và C với biến thiếu

x1 = Số chén x2 = Số ly s1, s2 Biến thiếu

Bài toán QHTT - cực tiểu (1 of 7)

(cid:132) Hai loại phân bón Lâm Thao và Đầu Trâu

(cid:132) Đất được bón yêu cầu 16g đạm và 24g lân.

(cid:132) Giá Lâm Thao 6k/bao, Đầu Trâu 3k/bao.

(cid:132) Bài toán: Mua mỗi loại phân bao nhiêu để tối thiểu chi phí?

Thành phần

Hiệu

Đạm (g/bao)

Lân (g/bao)

2

4

Lâm Thao

4

3

Đầu Trâu

Bài toán QHTT (2 of 7)

Đ

Đ

g

ạ

ạ

g

3

m

m

4

n

â

4

â n

2g

L

g

L

Lâm Thao 6k

Đầu Trâu 3k

Yêucầu: ≥16g Đạm ≥26g Lân

Figure 3.14 Bón phân

Bài toán QHTT (3 of 7)

Biến:

x1 = Số bao phân Lâm Thao x2 = Số bao phân Đầu Trâu

Hàm mục tiêu:

Minimize Z = 6x1 + 3x2 Với:

6x1 = Giá bao phân Lâm Thao 3x2 = Giá Đầu Trâu

Ràng buộc:

2x1 + 4x2 ≥ 16 g (đạm) 4x1 + 3x2 ≥ 24 lb (lân) x1, x2 ≥ 0

Ràng buộc (cực tiểu) (4 of 7)

Minimize Z = 6x1 + 3x2 St:

2x1 + 4x2 ≥ 16 4x1 + 3x2 ≥ 24 x1, x2 ≥ 0

Hình 3.15 Dạng đồ thị của 2 ràng buộc

Nghiệm khả dĩ (5 of 7)

Nghiệm khả dĩ

Minimize Z = 6x1 + 3x2 St:

2x1 + 4x2 ≥ 16 4x1 + 3x2 ≥ 24 x1, x2 ≥ 0

Hình 3.16 Nghiệm khả dĩ

Nghiệm tối ưu (6 of 7)

Số bao phân Lâm Thao Số bao phân Đầu Trâu

24k

Minimize Z = 6x1 + 3x2 St:

2x1 + 4x2 ≥ 16 4x1 + 3x2 ≥ 24 x1, x2 ≥ 0

Hình 3.17 Điểm tối ưu

Giải pháp đồ thị – Biến thừa (7 of 7)

(cid:132) Thêm biến thừa để chuyển ràng

(cid:132) Biến thừa không ảnh hưởng đến kết quả tính toán của hàm mục tiêu.

(cid:132) Thêm biến thừa ở bài toán bón

buộc ≥ thành (=).

phân:

2x1 + 4x2 - s1 = 16 (đạm) 4x1 + 3x2 - s2 = 24 (lân)

Minimize Z = 6x1 + 3x2 + 0s1 + 0s2 2x1 + 4x2 – s1 = 16 St: 4x1 + 3x2 – s2 = 24 x1, x2, s1, s2 ≥ 0

Hình 3.18 Dạng đồ thị của bài toán

Các trường hợp đặc biệt trong QHTT

Bao gồm (cid:131) Đa nghiệm (cid:131) Không có miền nghiệm (cid:131) Nghiệm không giới hạn (cid:131) Ràng buộc thừa

Đa nghiệm ở bài toán công ty gốm

Hàm mục tiêu thì song song với đường ràng buộc.

Maximize Z = 40x1 + 30x2 St:

1x1 + 2x2 ≤ 40 4x1 + 3x2 ≤ 120 x1, x2 ≥ 0

Trong đó:

x1 = Lượng chén x2 = Lượng ly

Hình 3.19 Đa nghiệm

Không có miền nghiệm

Tất cả các nghiệm đều vi phạm ít nhất một ràng buộc.

Maximize Z = 5x1 + 3x2 St:

4x1 + 2x2 ≤ 8 x1 ≥ 4 x2 ≥ 6 x1, x2 ≥ 0

Hình 3.20 Không có miền nghiệm

Nghiệm không giới hạn

Trị của hàm mục tiêu tăng mà không bị chặn

Maximize Z = 4x1 + 2x2 x1 ≥ 4 St: x2 ≤ 2 x1, x2 ≥ 0

Hình 3.21 Miền nghiệm không giới hạn

Ràng buộc thừa

X2

100

(cid:41) Một ràng buộc thừa không làm ảnh hưởng đến miền lời giải.

A (X1 = 0, X2 = 80)

80

60

X < 80 Ràng buộc thừa

4

X

40

1

+

Maximize Z = 7X1 + 5X2 St:

3

X

2

=

20

2

4

0

100

0

20

40

60

80

X1

4X1 + 3X2 ≤ 240 2X1 + 1X2 ≤ 100 ≤ 80 X1

Hình 3.22 Ràng buộc thừa

Bài tập ví dụ No. 1 (1 of 2)

■ Hot dog tổng hợp có khối lượng 1000g ■ Giá gà 3k/g, bò 5k/g ≥ 500g gà ■ Yêu cầu ≥ 200g bò

■ Tỷ lệ gà/bò ≥ 2. ■ Xác định tỷ lệ thành phần để cực tiểu chi phí.

Bước 1: Xác định biến

x1 = Khối lượng gà ở một hot dog x2 = Khối lượng bò

Bước 2: Hình thành hàm mục tiêu

Minimize Z = 3x1 + 5x2 Trong đó Z = giá của một hot dog 1,000g

3x1 = giá gà 5x2 = giá bò

Bài tập ví dụ No. 1 (2 of 2)

Bước 3:

Thành lập các ràng buộc

x1 + x2 = 1,000 lb x1 ≥ 500g gà x2 ≥ 200g bò x1/x2 ≥ 2 ⇔ x1 - 2x2 ≥ 0 x1, x2 ≥ 0

Mô hình bài toán

Minimize Z = 3x1 + 5x2 St: x1 + x2 = 1,000

x1 ≥ 500 x2 ≥ 200 x1 - 2x2 ≥ 0 x1, x2 ≥ 0

Bài tập ví dụ No. 2 (1 of 3)

Giải bài toán QHTT sau bằng PP. đồ thị: Maximize Z = 4x1 + 5x2 St:

x1 + 2x2 ≤ 10 6x1 + 6x2 ≤ 36 x1 ≤ 4 x1, x2 ≥ 0

Bước 1: Từ phương trình, vẽ các đường ràng buộc lên đồ thị

Hình 3.23 Các đường ràng buộc

Bài tập ví dụ No. 2 (2 of 3)

Maximize Z = 4x1 + 5x2 x1 + 2x2 ≤ 10 St: 6x1 + 6x2 ≤ 36 x1 ≤ 4 x1, x2 ≥ 0

Bước 2: Xác định miền nghiệm khả dĩ

Hình 3.24 Miền nghiệm khả và các điểm nghiệm (điểm-góc) A, B, C, và D

Bài tập ví dụ No. 2 (3 of 3)

Maximize Z = 4x1 + 5x2 St: x1 + 2x2 ≤ 10

6x1 + 6x2 ≤ 36 x1 ≤ 4 x1, x2 ≥ 0

Bước 3 và 4: Xác định trị tối ưu tại các điểm nghiệm và chọn giải pháp tối ưu.

Hình 3.25 Giải pháp tối ưu