Chương I BÀI TOÁN QUY HOẠCH TUYẾN TÍNH - Bài 4. PHƯƠNG PHÁP ĐƠN HÌNH docx

Chương I

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

Bài 4. PHƯƠNG PHÁP ĐƠN HÌNH

1. Giới thiệu chung: Ta xét bài toán

QHTT dạng chính tắc:

1

1

( ) , min (max)

1,

0 1, .

n

j j

j

n

ij j i

j

j

f x c x c x

a x b i m

x j n

=

=

= = 〈 〉 →

= =

≥ =

∑

∑

Hoặc viết dưới dạng:

( ) , min (max)

0

f x c x

Ax b

x

= 〈 〉 →

=

≥

( ) 1,

1,

ij i m

j n

A a =

=

=

1 2 1 2

1 2

( , ,.., ) , ( , ,.., )

( , ,.., )

T T

n m

n

x x x x b b b b

c c c c

= =

=

Trong đó:

Giả sử bài toán đang xét ta đã biết

một phương án cực biên dạng :

10 20 0 ( ; ;..; ;0;0;..;0) m

x x x x =

0 0, 1, j

trong đó x j m > = cơ sở liên kết của

x là 1 2

, ,...,

m A A A

1 2

10 20 0 ..

m

m

x A x A x A b + + + =

1 10 2 20 0 ( ) .. m m

f x c x c x c x = + + +

Giá trị hàm mục tiêu là:

1 2

1 2 ..

m j

j j mj x A x A x A A + + + =

Với mỗi j = 1, 2, .., n

Ký hiệu : 1 2 ( ; ;..; ) j

j j mj x x x x =

Nếu mà ta đã biết được x là phương án tối

ưu nhờ một cách nào đó thì mục đích của ta đã

xong.

Nếu x không phải là phương án tối ưu thì ta

tìm phương án cực biên khác tốt hơn tức là

phương án làm cho giá trị hàm mục tiêu nhỏ

hơn.

Muốn vậy ta phải xây dựng một cơ sở mới,

đơn giản nhất là thay thế một véctơ trong cơ sở

cũ bằng một véctơ nằm ngoài cơ sở cũ.

1

, , 1,

m

j

j i ij

i

z c x c x j n

=

= = 〈 〉 = ∑

Đặt:

j j j ∆ = − z c

Từ hai véctơ:

10 20 0

1 2

( ; ;..; ;0;0;..;0)

( ; ;..; )

m

j

j j mj

x x x x

x x x x

=

=

2. Định lý 1.( Dấu hiệu tối ưu)

Nếu là một

phương án cực biên của bài toán Quy

hoạch tuyến tính dạng chính tắc sao cho :

thì x là phương án tối ưu, và ngược lại.

10 20 0 ( ; ;..; ;0;0;..;0) m

x x x x =

0, 1, j ∆ ≤ ∀ =j n