Bài giảng tối ưu hóa

ĐẠI HỌC THÁI NGUYÊN

KHOA CÔNG NGHỆ THÔNG TIN

-----o0o-----

Bài giảng môn

TỐI ƯU HÓA

THÂN QUANG KHOÁT

Thái nguyên - 2007

Thân Quang Khoát

MỤC LỤC

Chương 1. MỞ ĐẦU......................................................................................................3

§1. ĐỐI TƯỢNG NGHIÊN CỨU...............................................................................3

1.1. Bài toán tối ưu tổng quát...................................................................................3

1.2. Phân loại bài toán..............................................................................................3

1.3. Một số mô hình thực tế .....................................................................................4

§2. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ..........................................................6

2.1. Dạng tổng quát..................................................................................................6

2.2. Dạng chuẩn tắc..................................................................................................7

2.3. Dạng chính tắc...................................................................................................7

§3. MỘT SỐ KIẾN THỨC BỔ TRỢ ..........................................................................9

3.1. Tập hợp lồi và điểm cực biên............................................................................9

3.2. Đa diện lồi (polytope) .....................................................................................10

§4. CẤU TRÚC MIỀN RÀNG BUỘC CỦA BÀI TOÁN........................................11

QUY HOẠCH TUYẾN TÍNH ............................................................................11

4.1. Phương án cực biên và phương án cực biên tối ưu.........................................11

4.2. Điều kiện cần và đủ để một phương án là cực biên ........................................13

4.3. Cơ sở của một phương án cực biên.................................................................15

Chương 2. THUẬT TOÁN ĐƠN HÌNH....................................................................17

§1. MỞ ĐẦU .............................................................................................................17

1.1. Bài toán ...........................................................................................................17

1.2. Phương pháp Hình Học...................................................................................17

§2. THUẬT TOÁN ĐƠN HÌNH...............................................................................19

2.1. Tư tưởng của thuật toán đơn hình...................................................................19

2.2. Công thức số gia hàm mục tiêu - dấu hiệu tối ưu ...........................................20

2.3. Tìm phương án cực biên tốt hơn - Công thức đổi cơ sở .................................21

2.4. Thuật toán đơn hình (Simplex method)..........................................................23

2.5. Bảng đơn hình .................................................................................................24

§3. TÍNH HỮU HẠN CỦA THUẬT TOÁN ĐƠN HÌNH .......................................28

3.1. Trường hợp bài toán không suy biến ..............................................................28

3.2. Trường hợp bài toán suy biến .........................................................................28

§4. PHƯƠNG PHÁP HAI PHA ................................................................................31

4.1. Vấn đề .............................................................................................................31

4.2. Phương pháp hai pha giải bài toán QHTT ......................................................32

Bộ môn Khoa Học Cơ Bản 1

Bài Giảng môn Tối Ưu Hoá

4.3. Một số ví dụ ....................................................................................................34

§5. PHƯƠNG PHÁP ĐÁNH THUẾ.........................................................................36

§6. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐỐI NGẪU ...................................41

6.1. Bài toán đối ngẫu ............................................................................................41

6.2. Các định lý đối ngẫu .......................................................................................42

6.3. Một số ứng dụng của lý thuyết đối ngẫu ........................................................44

6.4. Thuật toán đơn hình đối ngẫu .........................................................................46

Chương 3. TỐI ƯU HOÁ RỜI RẠC .........................................................................56

§1. BÀI TOÁN TỐI ƯU HOÁ RỜI RẠC.................................................................56

1.1. Mở đầu ............................................................................................................56

1.2. Một số bài toán tối ưu hoá rời rạc tiêu biểu....................................................56

§2. PHƯƠNG PHÁP CẮT GOMORY GIẢI BÀI TOÁN QHTT NGUYÊN..........58

2.1. Tư tưởng chung của phương pháp cắt ............................................................58

2.2. Phương pháp cắt Gomory cho bài toán QHTT nguyên hoàn toàn .................59

2.3. Phương pháp cắt Gomory cho bài toán QHTT nguyên bộ phận ....................64

§3. PHƯƠNG PHÁP NHÁNH CẬN ........................................................................65

3.1. Sơ đồ tổng quát ...............................................................................................65

3.2. Thuật toán nhánh cận Land-Doig giải bài toán QHTT nguyên......................66

3.3. Một số ví dụ ....................................................................................................68

§4. BÀI TOÁN CÁI TÚI...........................................................................................72

4.1. Đưa bài toán QHTT Nguyên về bài toán cái túi.............................................72

4.2. Phương pháp Quy hoạch động giải bài toán cái túi........................................74

Tài liệu tham khảo.......................................................................................................77

Khoa Công nghệ thông tin - ĐHTN 2

Thân Quang Khoát

Chương 1. MỞ ĐẦU

§1. ĐỐI TƯỢNG NGHIÊN CỨU

1.1. Bài toán tối ưu tổng quát

Bài toán tối ưu tổng quát có dạng như sau:

1

1 2

2

( ) min (max)

( ) , 1,

( ) , 1,

( ) , 1,

i i

j j

k k

n

f x

g x b i m

g x b j m m

g x b k m m

x X

→

⎧⎪ ≥ = ⎪

⎪

⎪

⎪ ≤ = + ⎪⎪

⎨

⎪

⎪ = = + ⎪

⎪

⎪

⎪ ∈ ⊂ℜ ⎪⎩

Trong đó f(x) được gọi là hàm mục tiêu; ( ), 1, g xi i = m được gọi là các

hàm ràng buộc. Mỗi một đẳng thức hay bất đẳng thức được gọi là một ràng

buộc. Gọi

1 1

2

( ) , 1, ; ( ) , 1,

( ) , 1, ;

i i j j n

k k

g x b i m g x b j m m

D x

g x b k m m x X

⎧ ⎫ ⎪ ⎪ ≥ = ≤ = +

= ∈ ⎨ ⎬ ℜ

⎪ ⎪ = = + ∈

⎩ ⎭

2

∈

D được gọi là miền ràng buộc (hay miền chấp nhận được). Mỗi một vectơ

được gọi là một phương án của bài toán (hay lời giải chấp

nhận được).

x x =( 1 2 , x , ..., xn) D

Định nghĩa: Phương án được gọi là phương án tối ưu của bài toán nếu

thoả mãn điều kiện sau

* x ∈D

(®èi víi bµi to¸n t×m Min)

(®èi víi bµi to¸n t×m Max)

*

*

( ) ( ) ,

( ) ( ) ,

f x f x x D

f x f x x D

≤ ∀ ∈

≥ ∀ ∈

khi đó giá trị * f(x ) được gọi là giá trị tối ưu.

1.2. Phân loại bài toán

Chúng ta thấy rằng, một cách hiển nhiên nhất để giải bài toán đặt ra là: Tính

giá trị của hàm f(x) trên tất cả các phương án của miền ràng buộc sau đó so

sánh các giá trị của hàm mục tiêu thu được để tìm ra phương án tối ưu. Tuy

Bộ môn Khoa Học Cơ Bản 3

Bài Giảng môn Tối Ưu Hoá

nhiên cách làm này là rất khó hoặc đúng hơn là không thể làm được trong

trường hợp tổng quát (chẳng hạn tập là không đếm được). Vì vậy chúng ta

phải phân tách nhỏ ra bằng cách thêm một số điều kiện nào đó để được các bài

toán “dễ giải”. Người ta đã phân ra một số loại bài toán như sau:

D

+ Quy hoạch tuyến tính

+ Quy hoạch lồi.

+ Quy hoạch phi tuyến.

+ Quy hoạch toàn phương.

+ Quy hoạch rời rạc.

+ Quy hoạch nguyên.

1.3. Một số mô hình thực tế

Ta sẽ xem xét một số bài toán trong thực tế đưa đến bài toán tối ưu hoá và

mô mình toán học tương ứng của nó.

1.3.1. Bài toán lập kế hoạch sản xuất cho một nhà máy

Một nhà máy có khả năng sản xuất loại sản phẩm. Để sản xuất loại

sản phẩm này thì cần m loại nguyên liệu. Biết:

n n

aij - lượng nguyên liệu loại i cần thiết để sản xuất một đơn vị sản phẩm loại j

bi - lượng dự trữ nguyên liệu loại i

cj - tiền lãi từ việc bán một đơn vị sản phẩm loại j

i m = = 1, , j 1,n

Hãy xây dựng kế hoạch sản xuất sao cho nhà máy thu được tổng lợi nhuận

là nhiều nhất.

Gọi là lượng sản phẩm loại mà nhà máy sẽ sản xuất, rõ ràng ta có

. Kế hoạch sản xuất của nhà máy sẽ là véctơ . Đại lượng

là tổng chi phí nguyên liệu loại theo kế hoạch sản xuất , theo giả

thiết ta có:

xj j

xj ≥0 x x =( 1 2 , x , ..., xn)

1

n

ij j j a x ∑ = i x

1

n

ij j i j a x b ∑ = ≤

Khoa Công nghệ thông tin - ĐHTN 4

Thân Quang Khoát

Tổng lợi nhuận thu được theo kế hoạch sản xuất x sẽ là . Như vậy

yêu cầu của bài toán này đưa về mô hình toán học như sau:

1

n

j j j c x ∑ =

1

1

( )

, 1,

0 , 1,

n

j j j

n

ij j i j

j

f x c x M

a x b i m

x j n

=

=

= →

⎧⎪ ≤ = ⎪⎪

⎨

⎪

⎪ ≥ = ⎪⎩

∑

∑

ax

Mô hình thu được chính là một bài toán quy hoạch tuyến tính.

1.3.2. Bài toán cái túi

Một nhà thám hiểm cần đem theo một cái túi có trọng lượng không quá b .

Có loại đồ vật có thể đem theo. Đồ vật thứ có trọng lượng là và giá trị

sử dụng là

n j aj

( 1, c j j = n). Hỏi rằng nhà thám hiểm cần lấy các loại đồ vật nào và

số lượng bao nhiêu để cho tổng giá trị sử dụng của các đồ vật mang theo là

nhiều nhất ?

Gọi ( 1, x j j = n) là số lượng đồ vật loại mà nhà thám hiểm sẽ đem theo.

Khi đó tổng giá trị của các đồ vật đó là , tổng trọng lượng của chúng là

. Từ giả thiết ta có . Như vậy yêu cầu của bài toán sẽ đưa

về việc giải bài toán sau:

j

1

n

j j j c x ∑ =

1

n

j j j a x ∑ = 1

n

j j j a x b ∑ = ≤

vµ nguyªn

1

1

max

0 (

n

j j j

n

j j j

j

c x

a x b

x j

=

=

→

⎧⎪ ≤ ⎪

⎨

⎪

⎪ ≥ = ⎩

∑

∑

1,n)

Đây lại là một bài toán quy hoạch tuyến tính Nguyên.

1.3.3. Bài toán vận tải

Có m kho hàng cùng chứa một loại hàng hoá, lượng hàng có ở kho thứ i là

a i i ( 1 = ,m). Có n địa điểm tiêu thụ loại hàng nói trên, với nhu cầu tiêu thụ ở

điểm j là ( 1, b j j = n). Biết là cước phí vận chuyển một đơn vị hàng hoá từ

kho thứ đến điểm tiêu thụ thứ . Hãy lập kế hoạch vận chuyển hàng hoá từ

các kho đến các điểm tiêu thụ sao cho tổng chi phí vận chuyển là nhỏ nhất.

cij

i j

Ký hiệu là lượng vận chuyển từ kho i đến điểm tiêu thụ thứ , khi đó: xij j

Bộ môn Khoa Học Cơ Bản 5

Bài Giảng môn Tối Ưu Hoá

ij

1 1

m n

ij

i j

c x = =

∑∑ là tổng chi phí vận chuyển

1

n

ij

j

x =

∑ là lượng hàng vận chuyển từ kho thứ i

1

m

ij

i

x =

∑ là lượng hàng vận chuyển đến điểm tiêu thụ thứ j

khi đó bài toán lập kế hoạch trên có thể đưa về mô hình toán học như sau:

1 1

1

1

0, 1, , 1,

m n

ij ij

i j

n

ij i j

n

ij j j

ij

c x Min

x a

x b

x i m j

= =

=

=

→

⎧⎪ = ⎪

⎪

⎪⎪

⎨ = ⎪

⎪

⎪

⎪ ≥ = = ⎪⎩

∑∑

∑

∑

n

ℜn

Đây chính là một bài toán Quy hoạch tuyến tính.

§2. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH

2.1. Dạng tổng quát

Tìm véctơ ( ,1 2, ..., ) sao cho: t x x = ∈ x xn

1

( ) ( ) n

j j

j

f x c x Min Ma =

= → ∑ x

với các điều kiện:

tù do ,

1 1

1 1 2

1 2

1

1 2

2

, 1,

, 1

, 1

0, 1,

0, 1,

1,

n

ij j i j

n

j pj j p

n

j kj j k

j

j

j

a x b i m

a x b p m m

a x b k m m

D

x j n

x j n n

x j n n

=

=

=

⎧⎪ ≥ = ⎪

⎪

⎪

⎪ ≤ = + ⎪

⎪

⎪

⎪

⎪ = = +

=⎪

⎨

⎪

⎪ ≥ = ⎪

⎪

⎪

⎪ ≤ = + ⎪

⎪

⎪

⎪ = + ⎪⎩

∑

∑

∑

,

,

Dễ thấy rằng:

1) f( ) x f → ⇔ min − (x)→max

Khoa Công nghệ thông tin - ĐHTN 6