Bài giảng Toán cao cấp: Chương 4 - TS. Nguyễn Phúc Sơn

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Chương 4: Quy hoạch tuyến tính

Tiến sĩ Nguyễn Phúc Sơn

Trường Đại học Kinh tế - Luật Đại học Quốc gia Thành phố Hồ Chí Minh

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Ngày 25 tháng 10 năm 2014

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Table of Contents

1 Bài toán mở đầu

2 Các dạng bài toán quy hoạch tuyến tính

3 Phương pháp đơn hình (simplex method)

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

SilComputers

Đề bài

1 Mỗi máy tính cần 1 CPU và trong kho có 10,000 bộ CPU

2 Trong kho có 15,000 bộ 16MB memory chipset. Mỗi laptop

SilComputer cần xác định số lượng laptop và desktop sản xuất trong quý tới. Mục tiêu của hãng là tối đa hóa lợi nhuận. Biết rằng bán 1 laptop lời $750 và bán 1 desktop lời $1000. Tuy nhiên, hãng bị các ràng buộc sau:

3 Cần 4 phút để ráp 1 laptop và 3 phút để ráp 1 desktop. Tổng

được gắn 16MB và mỗi desktop được gắn 32MB

số phút lao động là 25,000 phút.

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Tìm lời giải tối ưu cho bài toán.

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

SilComputers

Đề bài

1 Mỗi máy tính cần 1 CPU và trong kho có 10,000 bộ CPU

2 Trong kho có 15,000 bộ 16MB memory chipset. Mỗi laptop

SilComputer cần xác định số lượng laptop và desktop sản xuất trong quý tới. Mục tiêu của hãng là tối đa hóa lợi nhuận. Biết rằng bán 1 laptop lời $750 và bán 1 desktop lời $1000. Tuy nhiên, hãng bị các ràng buộc sau:

3 Cần 4 phút để ráp 1 laptop và 3 phút để ráp 1 desktop. Tổng

được gắn 16MB và mỗi desktop được gắn 32MB

số phút lao động là 25,000 phút.

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Tìm lời giải tối ưu cho bài toán.

1 x1 + x2 ≤ 10

2 x1 + 2x2 ≤ 15

3 4x1 + 3x2 ≤ 25

4 Ràng buộc tự nhiên về dấu x1, x2 ≥ 0

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Các ràng buộc: (Đơn vị: 1000) (constraints)

Mô hình

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Đặt x1 là số laptops định sản xuất và x2 là số desktops định sản xuất. (decision variables) Hàm mục tiêu: z = 750x1 + 1000x2 (objective function)

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Mô hình

1 x1 + x2 ≤ 10 2 x1 + 2x2 ≤ 15 3 4x1 + 3x2 ≤ 25 4 Ràng buộc tự nhiên về dấu x1, x2 ≥ 0

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Đặt x1 là số laptops định sản xuất và x2 là số desktops định sản xuất. (decision variables) Hàm mục tiêu: z = 750x1 + 1000x2 (objective function) Các ràng buộc: (Đơn vị: 1000) (constraints)

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Mô hình

1 x1 + x2 ≤ 10 2 x1 + 2x2 ≤ 15 3 4x1 + 3x2 ≤ 25 4 Ràng buộc tự nhiên về dấu x1, x2 ≥ 0

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Đặt x1 là số laptops định sản xuất và x2 là số desktops định sản xuất. (decision variables) Hàm mục tiêu: z = 750x1 + 1000x2 (objective function) Các ràng buộc: (Đơn vị: 1000) (constraints)

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Phương án tối ưu (PATU): PA (α1, α2) làm cho hàm mục tiêu z đạt max được gọi là 1 PATU.

Thuật ngữ

Phương án (PA): Mỗi bộ giá trị (α1, α2) của (x1, x2) thỏa mãn tất cả các ràng buộc được gọi là 1 phương án (feasible solution).

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Tập phương án hay miền ràng buộc: Tập hợp tất cả các phương án của bài toán (feasible region).

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Thuật ngữ

Phương án (PA): Mỗi bộ giá trị (α1, α2) của (x1, x2) thỏa mãn tất cả các ràng buộc được gọi là 1 phương án (feasible solution).

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Tập phương án hay miền ràng buộc: Tập hợp tất cả các phương án của bài toán (feasible region). Phương án tối ưu (PATU): PA (α1, α2) làm cho hàm mục tiêu z đạt max được gọi là 1 PATU.

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Thuật ngữ

Phương án (PA): Mỗi bộ giá trị (α1, α2) của (x1, x2) thỏa mãn tất cả các ràng buộc được gọi là 1 phương án (feasible solution).

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Tập phương án hay miền ràng buộc: Tập hợp tất cả các phương án của bài toán (feasible region). Phương án tối ưu (PATU): PA (α1, α2) làm cho hàm mục tiêu z đạt max được gọi là 1 PATU.

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Lời giải hình học

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Ràng buộc 1

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Lời giải hình học (tt)

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Miền ràng buộc

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Lời giải hình học (tt)

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Lời giải

Nhận xét

PATU chỉ xảy ra trên biên của miền ràng buộc.

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Trong phần lớn trường hợp, PATU chỉ xảy ra trên đỉnh của đa diện ràng buộc.

Lời giải hình học (tt)

Từ hình vẽ, ta thấy PATU xảy ra tại giao điểm của 2 đường thẳng

x1 + 2x2 = 15 4x1 + 3x2 = 25

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Từ đó PATU là (1, 7) tương ứng với lợi nhuận tối đa z = $7, 750, 000.

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Lời giải hình học (tt)

Từ hình vẽ, ta thấy PATU xảy ra tại giao điểm của 2 đường thẳng

x1 + 2x2 = 15 4x1 + 3x2 = 25

Từ đó PATU là (1, 7) tương ứng với lợi nhuận tối đa z = $7, 750, 000.

Nhận xét

PATU chỉ xảy ra trên biên của miền ràng buộc.

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Trong phần lớn trường hợp, PATU chỉ xảy ra trên đỉnh của đa diện ràng buộc.

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Lời giải hình học (tt)

Từ hình vẽ, ta thấy PATU xảy ra tại giao điểm của 2 đường thẳng

x1 + 2x2 = 15 4x1 + 3x2 = 25

Từ đó PATU là (1, 7) tương ứng với lợi nhuận tối đa z = $7, 750, 000.

Nhận xét

PATU chỉ xảy ra trên biên của miền ràng buộc.

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Trong phần lớn trường hợp, PATU chỉ xảy ra trên đỉnh của đa diện ràng buộc.

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Table of Contents

1 Bài toán mở đầu

2 Các dạng bài toán quy hoạch tuyến tính

3 Phương pháp đơn hình (simplex method)

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Dạng tổng quát (Dạng (G))

Yêu cầu: Tất cả các ràng buộc cũng như hàm mục tiêu đều là phương trình hay bất phương trình tuyến tính của các biến số.

Ví dụ

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

f = x1 + 2x2 − 5x3 + 3x4 − 2x5 + 5x6 −→ min  2x1 − x2 + 4x3 − 2x4 − 3x5 + 4x6 = 4  x1 + 3x2 − 2x3 + 6x4 − 4x5 + 2x6 ≤ 6 3x1 − 2x2 + 3x3 ≥ 5  x1 ≥ 0, x2 ≤ 0

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Dạng tổng quát (Dạng (G))

Yêu cầu: Tất cả các ràng buộc cũng như hàm mục tiêu đều là phương trình hay bất phương trình tuyến tính của các biến số.

Ví dụ

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

f = x1 + 2x2 − 5x3 + 3x4 − 2x5 + 5x6 −→ min  2x1 − x2 + 4x3 − 2x4 − 3x5 + 4x6 = 4  x1 + 3x2 − 2x3 + 6x4 − 4x5 + 2x6 ≤ 6 3x1 − 2x2 + 3x3 ≥ 5  x1 ≥ 0, x2 ≤ 0

Lưu ý

Mọi bài toán max f tương đương với bài min −f

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Mọi bài dạng (G) đều có thể được biến đổi về dạng (C)

Dạnh chính tắc - Dạng (C)

Yêu cầu: Tất cả các rang buộc đều ở dạng phương trình và tất cả các biến đều không âm

Ví dụ

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

 f = x1 + 2x2 − 5x3 + 3x4 −→ max  2x1 − x2 + 4x3 − 2x4 = 3  x1 + 3x2 − 2x3 + 6x4 = 8 xj ≥ 0, j = 1, 2, 3, 4

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Dạnh chính tắc - Dạng (C)

Yêu cầu: Tất cả các rang buộc đều ở dạng phương trình và tất cả các biến đều không âm

Ví dụ

 f = x1 + 2x2 − 5x3 + 3x4 −→ max  2x1 − x2 + 4x3 − 2x4 = 3  x1 + 3x2 − 2x3 + 6x4 = 8 xj ≥ 0, j = 1, 2, 3, 4

Lưu ý

Mọi bài toán max f tương đương với bài min −f

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Mọi bài dạng (G) đều có thể được biến đổi về dạng (C)

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Dạnh chính tắc - Dạng (C)

Yêu cầu: Tất cả các rang buộc đều ở dạng phương trình và tất cả các biến đều không âm

Ví dụ

 f = x1 + 2x2 − 5x3 + 3x4 −→ max  2x1 − x2 + 4x3 − 2x4 = 3  x1 + 3x2 − 2x3 + 6x4 = 8 xj ≥ 0, j = 1, 2, 3, 4

Lưu ý

Mọi bài toán max f tương đương với bài min −f

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Mọi bài dạng (G) đều có thể được biến đổi về dạng (C)

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Lưu ý: Yếu cầu 2 nói rằng hệ các phương trình ràng buộc là độc lập (hay nói cách khác ta không thể bỏ đi bất kỳ ràng buộc nào mà không làm thay đổi nghiệm bài toán)

Dạnh chính tắc chuẩn - Dạng (N)

Yêu cầu: Giả sử dạng chính tắc có hệ ràng buộc với m phương trình. Khi đó, ta nói dạng chính tắc là chuẩn nếu

Mỗi phương trình đều có vế phải không âm.

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Ma trận hệ số chứa 1 ma trận con sơ cấp đơn giản cấp m (tức là ma trận có được từ Im bằng cách đổi chỗ các dòng)

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Dạnh chính tắc chuẩn - Dạng (N)

Yêu cầu: Giả sử dạng chính tắc có hệ ràng buộc với m phương trình. Khi đó, ta nói dạng chính tắc là chuẩn nếu

Mỗi phương trình đều có vế phải không âm.

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Ma trận hệ số chứa 1 ma trận con sơ cấp đơn giản cấp m (tức là ma trận có được từ Im bằng cách đổi chỗ các dòng) Lưu ý: Yếu cầu 2 nói rằng hệ các phương trình ràng buộc là độc lập (hay nói cách khác ta không thể bỏ đi bất kỳ ràng buộc nào mà không làm thay đổi nghiệm bài toán)

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Dạnh chính tắc chuẩn - Dạng (N)

Yêu cầu: Giả sử dạng chính tắc có hệ ràng buộc với m phương trình. Khi đó, ta nói dạng chính tắc là chuẩn nếu

Mỗi phương trình đều có vế phải không âm.

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Ma trận hệ số chứa 1 ma trận con sơ cấp đơn giản cấp m (tức là ma trận có được từ Im bằng cách đổi chỗ các dòng) Lưu ý: Yếu cầu 2 nói rằng hệ các phương trình ràng buộc là độc lập (hay nói cách khác ta không thể bỏ đi bất kỳ ràng buộc nào mà không làm thay đổi nghiệm bài toán)

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Phương án cực biên (PACB)

Định nghĩa

n ) được gọi là 1

1 , . . . , x (cid:63)

n ) được gọi là 1

j > 0

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Đối với bài toán (G): Một PA x (cid:63) = (x (cid:63) PACB nếu nó thỏa mãn dấu “=" với ít nhất n ràng buộc, trong đó có đúng n ràng buộc độc lập tuyến tính, nghĩa là ma trận hệ số của n ràng buộc đó có hạng bằng n Đối với bài toán (C): Một PA x (cid:63) = (x (cid:63) 1 , . . . , x (cid:63) PACB nếu hệ các cột của ma trận hệ số ứng với các x (cid:63) lập thành một hệ độc lập tuyến tính

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Phương án cực biên (PACB)

Định nghĩa

n ) được gọi là 1

1 , . . . , x (cid:63)

n ) được gọi là 1

j > 0

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Đối với bài toán (G): Một PA x (cid:63) = (x (cid:63) PACB nếu nó thỏa mãn dấu “=" với ít nhất n ràng buộc, trong đó có đúng n ràng buộc độc lập tuyến tính, nghĩa là ma trận hệ số của n ràng buộc đó có hạng bằng n Đối với bài toán (C): Một PA x (cid:63) = (x (cid:63) 1 , . . . , x (cid:63) PACB nếu hệ các cột của ma trận hệ số ứng với các x (cid:63) lập thành một hệ độc lập tuyến tính

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Table of Contents

1 Bài toán mở đầu

2 Các dạng bài toán quy hoạch tuyến tính

3 Phương pháp đơn hình (simplex method)

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Trở lại ví dụ SilComputer

PACB λi

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Bảng đơn hình bắt đầu Biến cơ sở Hệ số cơ sở 0 0 0 10 15/2 25/3 x3 x4 x5 Bảng 0 10 15 25 0 x1 -0,75 1 1 4 0,75 x2 -1 1 2 3 1 x3 0 1 0 0 0 x4 0 0 1 0 0 x5 0 0 0 1 0

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Ví dụ (tt)

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Vị trí xuất phát

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Trở lại ví dụ SilComputer (tt)

PACB λi

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Biến cơ sở Hệ số cơ sở 0 -1 0 5 15 1 x3 x2 x5 Bảng 1 2,5 15/2 2,5 -15/2 x1 -0,75 0,5 1/2 5/2 1/4 x2 -1 0 1 0 0 x3 0 1 0 0 0 x4 0 -0,5 1/2 -3/2 -1/2 x5 0 0 0 1 0

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Ví dụ (tt)

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Sau 1 bước

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Trở lại ví dụ SilComputer (tt)

PACB λi

Biến cơ sở Hệ số cơ sở 0 -1 -0,75 x3 x2 x1 Bảng 2 2 7 1 -7,75 x1 -0,75 0 0 1 0 x2 -1 0 1 0 0 x3 0 1 0 0 0 x4 0 1/4 5/4 -3/5 -4/5 x5 0 -1/5 -1/5 2/5 -1/10

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Lời giải tối ưu

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Ví dụ (tt)

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

Nghiệm tối ưu

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Vô số nghiệm - Vô nghiệm

Vô số nghiệm

Dấu hiệu bài toán vô số nghiệm: Khi kiểm tra điều kiện tối ưu, nếu mọi ∆j ≤ 0 (đối với bài toán MIN) đồng thời tại môt ∆j = 0 ứng với biến phi cơ sở xj thì bài toán có vô số nghiệm.

Ví dụ

x2 −→ max 1 2 x1 +  

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

 2x1 + x2 ≤ 4 x1 + 2x2 ≤ 3 x1, x2 ≥ 0

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Vô số nghiệm - Vô nghiệm

Vô số nghiệm

Dấu hiệu bài toán vô số nghiệm: Khi kiểm tra điều kiện tối ưu, nếu mọi ∆j ≤ 0 (đối với bài toán MIN) đồng thời tại môt ∆j = 0 ứng với biến phi cơ sở xj thì bài toán có vô số nghiệm.

Ví dụ

x2 −→ max 1 2 x1 +  

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

 2x1 + x2 ≤ 4 x1 + 2x2 ≤ 3 x1, x2 ≥ 0

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Vô nghiệm tối ưu

Khi chọn được biến vào (từ phi cơ sở thành cơ sở) nhưng không chọn được biến ra (từ cơ sở thành phi cơ sở) thì bài toán vô nghiệm tối ưu (lưu ý: Đây là trường hợp miền ràng buôc không bị chặn nên vẫn có phương án khả thi).

Ví dụ

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

 2x1 + x2 −→ max  −x1 + x2 ≤ 1  x1 − 2x2 ≤ 2 x1, x2 ≥ 0

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method)

Vô nghiệm tối ưu

Khi chọn được biến vào (từ phi cơ sở thành cơ sở) nhưng không chọn được biến ra (từ cơ sở thành phi cơ sở) thì bài toán vô nghiệm tối ưu (lưu ý: Đây là trường hợp miền ràng buôc không bị chặn nên vẫn có phương án khả thi).

Ví dụ

Tiến sĩ Nguyễn Phúc Sơn

Chương 4: Quy hoạch tuyến tính

 2x1 + x2 −→ max  −x1 + x2 ≤ 1  x1 − 2x2 ≤ 2 x1, x2 ≥ 0