10/5/2012

ĐẠI HỌC TÀI CHÍNH – MARKETING BỘ MÔN TOÁN – KHOA CƠ BẢN

Bài giảng

QUY HOẠCH TUYẾN TÍNH

Phong Nguyeãn VaênVaênVaênVaên Phong ThSThSThSThS. . . . Nguyeãn Phong Phong Nguyeãn Nguyeãn

Email : nvphong1980@gmail.com, nv.phongbmt@ufm.edu.vn

Chương 1. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH

TOAÙN QHTTQHTTQHTTQHTT 1.1.1.1. CAÙCCAÙCCAÙCCAÙC VÍVÍVÍVÍ DUÏDUÏDUÏDUÏ DAÃNDAÃNDAÃNDAÃN ÑEÁNÑEÁNÑEÁNÑEÁN BAØIBAØIBAØIBAØI TOAÙN TOAÙN TOAÙN

TOAÙN QHTTQHTTQHTTQHTT LOAÏI BAØIBAØIBAØIBAØI TOAÙN PHAÂN LOAÏI 2.2.2.2. PHAÂN TOAÙN TOAÙN LOAÏI LOAÏI PHAÂN PHAÂN

KHAÙI NIEÄMNIEÄMNIEÄMNIEÄM CÔCÔCÔCÔ BAÛNBAÛNBAÛNBAÛN 3.3.3.3. CAÙCCAÙCCAÙCCAÙC KHAÙI KHAÙIKHAÙI

TOAÙN QHTTQHTTQHTTQHTT PHAÙP HÌNHHÌNHHÌNHHÌNH HOÏCHOÏCHOÏCHOÏC GIAÛIGIAÛIGIAÛIGIAÛI BAØIBAØIBAØIBAØI TOAÙN PHÖÔNG PHAÙP 4.4.4.4. PHÖÔNG TOAÙN TOAÙN PHAÙP PHAÙP PHÖÔNG PHÖÔNG

TOAÙN QHTTQHTTQHTTQHTT PHAÙP ÑÔNÑÔNÑÔNÑÔN HÌNHHÌNHHÌNHHÌNH GIAÛIGIAÛIGIAÛIGIAÛI BAØIBAØIBAØIBAØI TOAÙN PHÖÔNG PHAÙP 5.5.5.5. PHÖÔNG TOAÙN TOAÙN PHAÙP PHAÙP PHÖÔNG PHÖÔNG

2

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT Ví dụ 1. ( Bài toán sản suất ) Giả sử một xí nghiệp sản xuất có m loại nguyên vật liệu V1, V2, … , Vm với số lượng tương ứng lần lượt là m1, m2, …, mm (đv) để sản xuất ra n loại sản phẩm S1, S2, … , Sn. Lợi nhuận và tỷ lệ các nguyên vật liệu dùng để sản xuất được cho trong bảng sau:

Sj

…

S1

S2

Sn

Vi

…

…

…

a11 a21 … am1

a12 a22 … am2

Lượng NL m1 m2 … mn

a1n a2n … amn

…

c1

c2

cn

V1 V2 … Vm Lợi nhuận

Yêu cầu: Lập kế hoạch sản xuất tối ưu

3

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

1

10/5/2012

CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT

Ví dụ 2. (Bài toán đầu tư vốn) Giả sử một doanh nhân A có

một lượng vốn là V0 tỷ muốn đầu tư vào các danh mục

a% /năm.

b% /năm.

c% /năm.

d% /năm.

sau đây: (cid:1) Gửi tiết kiệm không kì hạn với lãi suất (cid:1) Gửi tiết kiệm có kì hạn với lãi xuất (cid:1) Mua trái phiếu chính phủ với lãi xuất (cid:1) Cho doanh nghiệp tư nhân vay với lãi suất (cid:1) Mua đất phân lô bán nền với lãi suất

e% /năm.

Giả sử thời gian đáo hạn là như nhau. Các hình thức đầu

tư đều có rủi ro. Để hạn chế rủi ro chúng ta nhận được

các thông tin từ các chuyên gia tư vấn sau:

4

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT

Ví dụ 2. (Bài toán đầu tư vốn) (cid:1) Không cho doanh nghiệp tư nhân vay quá 30% số vốn. (cid:1) Số tiền mua trái phiếu Chính phủ không vượt quá số

tiền đầu tư trong 4 lĩnh vực kia.

(cid:1) Ít nhất 20% số tiền đầu tư phải thuộc lĩnh vực tiết kiệm

có kỳ hạn và trái phiếu.

(cid:1) Tỷ lệ tiết kiệm không kỳ hạn trên tiết kiệm có kỳ hạn

không vượt quá 1/3.

5

(cid:1) Số tiền mua đất không vượt quá 40% số vốn. Doanh nhân A muốn đầu tư toàn bộ số vốn. Hãy lập mô hình bài toán tìm phương án đầu tư sao cho thu được lợi nhuận tối đa.

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT Ví dụ 3. (Bài toán khẩu phần ăn). Giả sử ta cần chế biến món ăn từ nhiều thành phần nhưng đảm bảo đầy đủ các chất bổ cần thiết (như: đạm, béo, đường,…) mà giá thành lại rẻ nhất.

Giả sử có n thành phần, với giá một đơn vị thành phần j là cj, j = 1,2,…,n. Đồng thời có m chất. Biết rằng một đơn vị thành phần j chứa aij đơn vị chất i, i =1, 2, …, m, và mức chấp nhận được số đơn vị chất i là nằm giữa li và ui, i = 1,2,…,m. (hay ít nhất là bi)

6

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

2

10/5/2012

CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT Ví dụ 4. (Bài toán vận tải). Giả sử hàng hóa được vận chuyển từ m kho hàng đến n cửa hiệu bán lẻ. Lượng hàng ở kho thứ i có mi (i = 1,2,…,m) (đv) và cửa hiệu j có nhu cấu là nj (j =1,2,…,n) (đv). Cước vận chuyển một đv hàng hóa từ kho i đến cửa hiệu j là cij (đv). Giả sử rằng

1. Tổng hàng hóa ở các kho = Tổng nhu cầu hàng

hóa của các cửa hiệu.

2. Hàng hóa ở kho thứ i có thể vận đến bất kỳ của hiệu nào và cửa hiệu thứ j có thể nhận hàng hóa từ 1 kho bất kỳ.

3. Mỗi cửa hàng phải nhận đủ số hàng và mỗi kho

phải phát hết hàng.

Yêu cầu: Lập kế hoạch vận chuyển sao cho cước phí là bé nhất.

7

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

====

PHÂN LOẠI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH I. DẠNG TỔNG QUÁT (LP) x ,...,

x

(

)

sao cho :

Tìm

n

2

= = = =

fi fi fi fi

I ( )

f x (

)

min (max)

c x j

j

, x x 1 n ∑∑∑∑

j

n

£ £ £ £

,

= = = = i

1,

k

,

a x ij

j

b i

∑∑∑∑

====

1

j

n

‡ ‡ ‡ ‡

,

= = = = i

+ + + + k

l 1, ,

(2)

a x ij

j

b i

∑∑∑∑

====

II ( )

j

1

n

= = = =

,

1,

.

i

= + = + = + = + l

m

a x ij

j

b i

∑∑∑∑

====

j

1

==== 1         

£ ‡ ˛ £ ‡ ˛ £ ‡ ˛ £ ‡ ˛

x

0,

x

0,

x

= = = = ℝ ,

j

1,2,...,

n

(3)

j

j

j

          

là

Với: cj , là hệ số hàm mục tiêu, bi là các hệ số tự do, aij hệ số của các ràng buộc chung.

8

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

PHÂN LOẠI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH II. DẠNG CHÍNH TẮC (LPct)

,..., x ) x sao cho : Tìm x x , 1

2

n

fi fi = = = = fi fi min (max) f x ( ) c x j

j

====

==== ( n ∑∑∑∑

1

j

n

= = = = = = = = 1, m . a x ij

j

b i , i

j

‡ ‡ ‡ ‡

∑∑∑∑ ==== 1 0,

x = = = = j 1,2,..., n .

j

x ,..., x ) Tìm sao cho : x x , 1

2

n

fi fi = = = = fi fi f x ( ) min (max) c x j

j

III. DẠNG CHUẨN (LPc) ==== ( n ∑∑∑∑

====

1

n

‡ ‡

j + + + +

= = = = ‡ ‡ x 0, = = = = i 1, m .

i

a x ij

j

b b , i

i

‡ ‡ ‡ ‡

∑∑∑∑ = += += += + j m = = = = j

x 0,

1 1,2,...,

n .

j

9

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

3

10/5/2012

CÁC KHÁI NIỆM CƠ BẢN

I. CÁC KÝ HIỆU Xét bài toán QHTT dạng tổng quát. Ta đặt

x ,...,

n

11

12

) )))) ( ((((

2 ,...,

a a a a ... ... ==== A b m ) c

21 ... a

22 ... a

... ... a 1 n a 2 n ... a

i a A ,

x x , 1 b b , 1 2 c c , ( ,..., 1 :

n i

j A

2 doøng , coät cuûa

m

1

m

2

mn

                       

j

==== x          ==== b     ,  ====      c          

Khi đó, bài toán QHTT được viết lại dưới dạng sau

= = = =

fi fi fi fi fi fi fi fi

f

c x ,

min(max)

= = = = f

c x ,

((((

))))

‡ ‡ ‡ ‡ ‡ ‡ ‡ ‡

min(max) ))))

(((( £ = £ = £ = £ =

Ax

£ = £ = £ = £ = , ,

b

i a x ,

,

,

1,

m

hay

= = = = b i , i

ℝ

‡ £ ˛ ‡ £ ˛ ‡ £ ˛ ‡ £ ˛ ‡ £ ˛ ‡ £ ˛ ‡ £ ˛ ‡ £ ˛

x

0,

x

0

or x

ℝ = = = =

+ + + +

x + + + +

+ + + +

or x c x ,

0, ...

c x 1 1

x c x 2

2

n

trong đó

10

0 c x n + + + +

= = = =

+ + + +

+ + + +

...

i , a x

a x 1 1 i

a x 2 i

2

a x in

n

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

CÁC KHÁI NIỆM CƠ BẢN

= = = =

((((

))))

£ £ £ £

D

x Ax

}}}} b

Gọi

là miền chấp nhận được. Khi đó

˛ ˛ ˛

*

((((

))))

))))

$ ˛ ‡ £ " ˛ $ ˛ ‡ £ " ˛ $ ˛ ‡ £ " ˛ $ ˛ ‡ £ " ˛

II. CÁC KHÁI NIỆM {{{{ ‡ = ‡ = ‡ = ‡ = , , - x D˛ x

(((( = = = = * D f x

Gọi là một phương án (PA) * x c ,

= = = = x c ,

,

f x (

),

x D

- thì x* là một phương án tối ưu (PATƯ)

0

}}}}

$ ˛ $ ˛ $ ˛ $ ˛

gọi là một ràng buộc chặt.

i

{{{{ 1,2,...,

= = = = m a x

,i

:

-

0

b i

0

- Một PA thỏa chặt n ràng buộc độc lập tuyến tính được gọi là phương án cực biên (PACB) - Một PACB thỏa chặt đúng n ràng buộc gọi là phương án cực biên không suy biến (PACB), thỏa chặt hơn n ràng buộc gọi là PACB suy biến

- Một bài toán QHTT được gọi là giải được nếu tồn tại ít nhất một PATƯ.

11

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

CÁC KHÁI NIỆM CƠ BẢN III. CHUYỂN DẠNG TỔNG QUÁT VỀ DẠNG CHÍNH TẮC

‡ £ ‡ £ ‡ £ ‡ £

hay

a x ij

j

b i

j

- - - -

x

x

thì

∑ ∑ ∑ ∑ hay

+ + + +

+ + + +

j

= = = = 1

b i

n

b i + + + + j

a x ij

n

= = = = 1

b i

‡ ‡ ‡ ‡

Đối với ràng buộc ∑ ∑ ∑ ∑ Neáu ∑ ∑ ∑ ∑ a x ij x

0

vôùi

a x ij ∑ ∑ ∑ ∑ : goïi laø aån phuï

++++

n

1 Đối với ràng buộc dấu

£ ‡ £ ‡ £ ‡ £ ‡ 0 0 x Neáu x thì ñaët x

j

j

˛ - ‡ ˛ - ‡ ˛ - ‡ ˛ - ‡ ℝ x x x , x 0 Neáu x thì ñaët x vôùi

j

= - = - = - = - / j = = = = j

// j

/ / / j

/ / j

/ // j

12

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

4

10/5/2012

CÁC KHÁI NIỆM CƠ BẢN

IV. CHUYỂN DẠNG CHÍNH TẮC VỀ DẠNG CHUẨN

Đối với hệ số tự do

$ £ - ‡ $ £ - ‡ $ £ - ‡ $ £ - ‡

0

0

Neáu

thì

a

b i

= - = - = - = - x ij

j

b i

∑∑∑∑

Đối với ràng buộc

Nếu ràng buộc nào chưa có ẩn cơ sở (Là ẩn chỉ xuất hiện trong một ràng buộc và có hệ số bằng 1) thì ta thêm vào ẩn cơ sở (ẩn giả). Khi đó hệ số của ẩn giả trong hàm mục tiêu tương ứng là +M cho BT min (M rất lớn) và –M cho BT max (M rất lớn). Lúc này bài toán được gọi là bài toán mở rộng, ký hiệu là (M)

Nhận xét :

fi fi fi fi fi fi fi fi

f x (

) min

g x (

= - = - = - = - )

f x (

) max

Neáu

thì

13

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

CÁC KHÁI NIỆM CƠ BẢN

V. MỘT SỐ NHẬN XÉT

‡ ‡

1. Bài toán QHTT dạng chính tắc đạt nghiệm tối ưu tại ít nhất một PACB. Khi đó = = = =

= = = =

‡ ‡

x Ax

A

j coät thöù cuûa A

· · · ·

m n

(cid:219) (cid:219) (cid:219) (cid:219)

vaø + + + + ...

0

˛ ˛ ˛ ˛ ˛ ˛ ˛ ˛

}}}} 0 + + + + A x 2 2 D J x ( ,

,...,

= = = = 0 )

b {1,2,..., }

> > > > n x

}}}} 0

Xeùt Luùc ñoù = = = = x Xeùt

, b x + + + + A x 1 1 )))) 0 x n

0 j

0

0

{{{{ D = = = = Ax b (((( 0 0 x x , 2 1 J x (

)

x

:j = = = = A x {{{{ n n j ++++ ( ) laø soá thaønh phaàn

trong

Kyù hieäu Nhận xét :

0

0

˛ (cid:219) ˛ ˛ (cid:219) ˛ ˛ (cid:219) ˛ ˛ (cid:219) ˛

{{{{

x

D

J x (

}}}} )

-

laø PACB

Heä caùc veùc tô

laø ÑLTT

A j j

0

0

£ £ £ £

x

J x (

)

r A (

)

- Neáu

laø PACB thì

0

0

+ + + +

= = = =

J x (

r A ( )

x

)

Neáu

thì

khoâng suy bieán

0

0

+ + + +

< < < <

)

J x (

r A (

)

x

Neáu

thì

suy bieán

14

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

CÁC KHÁI NIỆM CƠ BẢN

V. MỘT SỐ NHẬN XÉT

2. Bài toán QHTT dạng chuẩn Đối với bài toán dạng chuẩn, thì việc xác định một PACB ban đầu được thực hiện như sau:

Cho các ẩn tự do nhận các giá trị bằng 0. Khi đó,

các ẩn cơ sở sẽ có giá trị là số hạng tự do tương ứng.

0

====

((((

))))

i e x . .,

,...,

,0,....,0

b b , 1 2

b m

15

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

5

10/5/2012

CÁC KHÁI NIỆM CƠ BẢN

VI. MỐI QUAN HỆ GIỮA CÁC BÀI TOÁN

1. Tổng quát (TQ) với Chính tắc (CT)

- Nếu (CT) không có PATƯ thì (TQ) không có PATƯ - Nếu (CT) có PATƯ mà không chứa các ẩn phụ thì

(TQ) có PATƯ 2. Chính tắc với Bài toán (M)

- Nếu (M) không có PATƯ thì (CT) không có PATƯ - Nếu (M) có PATƯ là x(M) thì

+ Nếu trong x(M) có thành phần ứng với biến

giả khác 0 thì (CT) không có PATƯ

+ Nếu trong x(M) có tất cả các thành phần

ứng với biến giả đều bằng 0 thì (CT) có PATƯ

16

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

CÁC KHÁI NIỆM CƠ BẢN

VII. MỘT SỐ VÍ DỤ

Ví dụ 1a. Hãy tìm miền chấp nhận được cho bài toán QHTT sau

= - = - = - = -

min (

f x

)

2

x

x

2

+ + + +

- £ - £ - £ - £

2

1

+ + + +

£ £ £ £

+ + + + 1 2 x x

x x

4 5

2

1

£ £ £ £

1

+ + + +

£ £ £ £

x x

4 8

2

x

1

      

‡ ‡ ‡ ‡

2 0;

1,2

= = = = j

x

j

Ví dụ 1b. CMR

17

(0,2), (4,1) (2,3) (3,2) (1,2)

: PACBKSB : PACBSB : Không là PACB : Là PA

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

CÁC KHÁI NIỆM CƠ BẢN

VII. MỘT SỐ VÍ DỤ

Ví dụ 2. Cho bài toán QHTT sau

- - = = = = + + + + - - min ( f x ) x x 2 x

1

2

3

+ + + + + + + + x

1

2

3

- - + + + + = = = = = = = = - - x 4 x 10 x 10 1

1

2

3

‡ ‡ ‡ ‡ x = = = = j 0; 1,3

j

 3 x  x   

a) CMR (2,1,0) là PACBKSB b) CMR (0,0,1) lá PACBSB

18

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

6

10/5/2012

CÁC KHÁI NIỆM CƠ BẢN

VII. MỘT SỐ VÍ DỤ

Ví dụ 3. Cho bài toán QHTT với tập ràng buộc sau

+ + + +

- - - -

x

2

3

+ + + +

+ + + +

= = = = = = = =

- - -

2 2

x x

x

1

2

4

+ + + +

= = = =

x 1 x x

2 4 5

x

1

5

 -   

‡ ‡ ‡ ‡

0

,

,

,

,

x x x x x 3

1

2

4

5

Các véc tơ sau có là PACB của bài toán trên không? a) (0,2,2,0,5) b) (1,1,1,3,4) c) (2,0,0,6,5)

19

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

PHƯƠNG PHÁP HÌNH HỌC GIẢI BT QHTT

Xét bài toán QHTT 2 biến

fi fi + + + + = = = = = = = = fi fi min(max) f x ( ) c x 2

2

‡ ‡ , c x £ = £ =‡ £ =‡ £ = ( , , ) c x 1 1 b Ax ‡ £ ˛ ‡ £ ˛ ‡ £ ˛ ‡ £ ˛ x 0, x 0, x

j

j

j

= = = =

£ £ £ £ ℝ }}}} b

D

x Ax

‡ = ‡ = ‡ = ‡ = ( ,

,

)

laø mieàn chaáp nhaän ñöôïc

- Goïi ====

c

-

2

˛ ˛

f : laø phaùp veùc tô cuûa a a a a

, c c ( 1 = = = =

˛ ˛

{{{{ ) {{{{

}}}}

a a a a ( L

f , )

x D f x

= = = = )

(

-

f laø ñöôøng möùc cuûa

Khi đó, phương pháp hình học, bao gồm các bước sau: B1: Vẽ miền D, c, và đường mức L( 0,f ) qua 0 và vuông góc với c. B2: Lấy một điểm bất kỳ

˛ ˛ ˛ ˛

x D

L

x

L

f

vaø veõ ñöôøng

ñi qua

vaø // vôùi (0, )

20

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

PHƯƠNG PHÁP HÌNH HỌC GIẢI BT QHTT

B3: Ta dịch chuyển đường L theo hướng ngược với c cho bài toán min (cùng cho bài toán max). Cho đến khi L không còn cắt D. Thì các điểm của D nằm trên đường mức cuối cùng này (nếu có) là PATƯ.

Ví dụ. Giải bài toán sau bằng phương pháp hình học

= - = - = - = -

fi fi fi fi

f x (

)

2

x

min

+ + + + 1

2

- £ - £

x + + + +

- £ - £

2

1

+ + + +

£ £ £ £

2 x x

x x

4 5

2

1

£ £ £ £

x

4

1

‡ ‡ ‡ ‡

x

0 ,

= = = = i

1,2

i

      

21

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

7

10/5/2012

PHƯƠNG PHÁP HÌNH HỌC GIẢI BT QHTT

• D là miền được tô đậm. • D có các đỉnh là (0,0), (0,2), (4,0), (4,1) và (2,3). • c = (-2,1), các đường

mức L0, L,

• Dịch chuyển L ngược hướng với c , ta thấy đường mức cuối cùng của hàm f mà còn cắt D là đường mức đi qua điểm (4,0).

• Vậy bài toán có phương là án tối ưu duy nhất (4.0) và fmin = - 8

22

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

PHƯƠNG PHÁP HÌNH HỌC GIẢI BT QHTT

Ví dụ. Giải bài toán sau bằng phương pháp hình học

= = = =

- fi - fi - fi - fi

f x (

)

x

max

2

- £ - £

x 2 + + + +

- £ - £

1

2

+ + + +

£ £ £ £

1 x x

x 2 x

4 5

1

2

£ £ £ £

x

4

1

‡ ‡ ‡ ‡

x

0 ,

= = = = i

1,2

i

      

23

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

PHƯƠNG PHÁP HÌNH HỌC GIẢI BT QHTT

• D là miền được tô đậm. • D có các đỉnh là (0,0), (0,2), (4,0), (4,1) và (2,3). • c = (1,-2), các đường

mức L0, L,

• Dịch chuyển L ngược hướng với c , ta thấy đường mức cuối cùng của hàm f mà còn cắt D là đường mức đi qua điểm (0,2) và (2,3).

• Vậy bài toán có vô số phương án tối ưu. Lúc này ta chọn một đỉnh đại diện là (0,2) và fmax = - 4

24

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

8

10/5/2012

PHƯƠNG PHÁP HÌNH HỌC GIẢI BT QHTT

Ví dụ. Giải các bài toán sau bằng phương pháp hình học

= = = =

+ + + +

fi fi fi fi

f x (

)

x

x

min(max)

‡ ‡

1 + + + +

‡ ‡

2 x

2

2

x

2

a

)

£ - £ - £ - £

2

x

4

x

2

‡ ‡ ‡ ‡

1 + + + + 1 0

 -  x x , 1

2

= - = - = - = -

fi fi fi fi

f x (

)

x

x

min(max)

+ + + + 1

2

+ + + +

‡ - ‡ - ‡ - ‡ -

2

x

x

2

2

+ + + +

- £ - £ - £ - £

b

)

1 x

1

2

- £ - £ - £ - £

2 x

x x

2 4

1

2

    

25

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

PHƯƠNG PHÁP HÌNH HỌC GIẢI BT QHTT

Ví dụ. Giải bài toán sau bằng phương pháp hình học

Cơ sở A sản xuất đồ gốm sứ với các dữ liệu cho trong bảng sau:

Sản phẩm Thời gian làm việc Đất sét Doanh thu

(giờ/đơn vị)

(kg/đơn vị) (1000$/đơn vị)

Tô Bình

1 2

4 3

40 50

Trong một xưởng mỗi ngày, có tối đa 40 giờ làm việc và 120 kg đất sét để sản xuất tô và bình.Tìm phương án sản xuất tối ưu .

26

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

PHƯƠNG PHÁP HÌNH HỌC GIẢI BT QHTT

Nhận xét: Qua các ví dụ trên ta thấy:

i) Nếu tập chấp nhận được khác rỗng và bị chặn thì

chắc chắn QHTT có nghiệm tối ưu.

ii) Nếu QHTT có nghiệm tối ưu và tập D có đỉnh thì

nghiệm tối ưu đạt trên ít nhất một đỉnh của D

iii) Trường hợp bài toán không có nghiệm tối ưu và tập D

khác rỗng, ta có hàm mục tiêu không bị chặn trên D.

iv) Nếu tập D không có đỉnh thì QHTT không có nghiệm

hoặc có nghiệm. Trường hợp có nghiệm thì nghiệm

tối ưu không phải là đỉnh.

27

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

9

10/5/2012

PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BT QHTT

1. Mô tả hình học của phương pháp đơn hình Thuật toán đơn hình xuất phát từ một đỉnh x0 ∈ D. Tại đỉnh x0 chỉ có một trong ba khả năng sau:

- KN1:Trên mọi cạnh của tập nghiệm chấp nhận được xuất phát từ x0 giá trị hàm mục tiêu không giảm. Khi đó x0 là nghiệm tối ưu của (LP)

D

0L

(cid:2) c

0x

28

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BT QHTT

0

<<<<

- KN2: Mọi cạnh xuất phát từ x0 , theo đó giá trị hàm mục tiêu giảm, đều là cạnh hữu hạn. Đi theo một cạnh như thế, ta sẽ đến một đỉnh x1 kề với x0 mà: 1 )

f x (

)

f x ( Gán x0 cho x1 và lập lại quá trình tính toán với đỉnh x0 mới

D

(cid:2) c

0x

1x

29

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BT QHTT

- ¥ - ¥ - ¥ - ¥

- KN3: Có một cạnh vô hạn xuất phát từ x0, theo đó giá trị hàm mục tiêu giảm. Khi đó giá trị hàm mục tiêu tiến theo cạnh này và bài toán không có nghiệm tối ưu đến

0x

0L

(cid:2) c

30

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

10

10/5/2012

PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BT QHTT

PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BÀI TOÁN DẠNG CHUẨN Xét QHTT dạng chuẩn

x ,..., x ) Tìm sao cho : x x , 1

2

n

fi fi = = = = fi fi f x ( ) min (max) c x j

j

====

==== ( n ∑∑∑∑

1

n

‡ ‡

j + + + +

= = = = ‡ ‡ x 0, = = = = i 1, m .

i

a x ij

j

b b , i

i

‡ ‡ ‡ ‡ x 0,

∑∑∑∑ = += += += + j m = = = = j

1 1,2,...,

n .

j

Thuật toán đơn hình gồm 4 bước sau

B1: Lập bảng đơn hình xuất phát ứng với PACB x0 B2: Kiểm tra điều kiện tối ưu B3: Kiểm tra bài toán không có lời giải B4: Tìm phương án cực biên mới tốt hơn

31

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BT QHTT

B1: Lập bảng đơn hình xuất phát ứng với PACB x0

…

…

θ

Cơ sở B

Phương án

Hệ số CB

…

…

x0

…

…

j1 …

…

…

x0

…

…

j …

…

…

θ j1 … θ j … θ

x0

jm

cj1 … cj … cjm

Aj1 … Aj … Ajm

c1 A1 zj1,1 … zj,1 … zjm,1 ∆

jm f (x0)

ck A2 zj1,k … zj,k … zjm,k … … ∆

cn An zj1,n … zj,n … zjm,n … … ∆

1

k

n

Vôùi

0

))))

0 2

j

}}}}

==== (((( ==== = = = =

(((( 0 x x , 1 A A , 1 j )))) (((( 0 J x

x B J ,..., ,..., 2 {{{{ = = = = j

0 x n A ,

jm j

)))) ,...,

j PACB Cô sôû ñôn vò Boä chæ soá cô sôû

1

2

B

m

32

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BT QHTT

B1: Lập bảng đơn hình xuất phát ứng với PACB x0 Coät 1: ghi heä soá haøm muïc tieâu öùng vôùi caùc bieán cô sôû Coät 2: ghi teân caùc veùc tô cô sôû Coät 3: ghi giaù trò cuûa caùc bieán cô sôû cuûa PACB

j

á trong ma traän A c z

jk

j

˛ ˛ > > > > ˛ ˛ 0, J z j neáu

js

B

qqq q

js

j

£ ˛ £ ˛ £ ˛ £ ˛ 0, J z ( j ) quy öôùc ghi "-"

js

B

0

∑∑∑∑

: giaù trò heä soá haøm muïc tieâu : heä so  x  ====  z +¥ +¥ +¥ +¥  ==== ) f x ( neáu 0 j c x j ˛ ˛ ˛ ˛

B

- " ˛ - " ˛ - " ˛ - " ˛ c 0, j J D = D = D = D = vaø D = D = D = D = k

j J z c jk

j

k

k

B

∑∑∑∑

˛ ˛ ˛ ˛

j J

B

33

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

11

10/5/2012

PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BT QHTT

0

D £ " D £ " D £ " D £ "

B2: Kiểm tra điều kiện tối ưu 0,

k x Neáu thì döøng thuaät toaùn: PATÖ laø

k

$ $ $ $ k 0 Neáu thì chuyeån sang B3 D > D > D > D > , k

B3: Kiểm tra bài toán không có lời giải

$ ˇ £ " ˛ $ ˇ £ " ˛ $ ˇ £ " ˛ $ ˇ £ " ˛ k J 0 z 0, j J Neáu vaø D > D > D > D > : B

jk

B

k

Thì döøng thuaät toaùn: BT khoâng coù PATÖ $ ˇ $ ˛ $ ˇ $ ˛ $ ˇ $ ˛ $ ˇ $ ˛ k J 0 j : z 0 Neáu vaø D > D > D > D > : B > > > > J B

jk

k

34

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

Thì chuyeån sang B4

PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BT QHTT

D D D D

B4: Tìm phương án cực biên mới tốt hơn {{{{

max

+ Tìm coät xoay: laø coät

vôùi

D = D = D = D = s

A s

k

q q q q

˛ ˛ ˛ ˛

}}}} 0 }}}}

r

j

J

D > D > D > D > k {{{{ q q q q + Tìm doøng xoay: laø doøng vôùi =min

r

j

B

z + Tìm phaàn töû truïc xoay: laø

rs

Khi ñoù chuyeån sang baûng môùi baèng caùch ñöa vaøo moät

ông öùng vôùi moät cô sôû cuõ ñöôïc ñöa ra)

cô sôû môùi (Tö qua thuaät toaùn Gauss-Jordan

35

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BT QHTT

min ( f x 2 x x ) 2 x 3 x

Ví dụ. Cho bài toán QHTT sau + = - + = - + = - + = - x 3

6

- - - - + + + + = = = = - - - - + + + + 4 x + + + + 1 + + + + 2

3

5

1

+ + + + 2 x + + + + x x x x 4 5

2

6

+ + + + 2 2 x + + + + x + + + + + + + + = = = = = = = =

3 x

2 x

1 x

2 7

3

1

‡ ‡ ‡ ‡ 0;

4 = = = = j

x 1,6

j

      

Ta có các kết quả sau

0

====

x

PACB

0

(0,0,0,7,4,5) : ====

{{{{

J x ( ====

) {{{{

}}}} 4,5,6 }}}}

B

,

,

A A A 6 4

5

36

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

12

10/5/2012

PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BT QHTT

Và bảng đơn hình được thành lập như sau

θ

Cơ sở B

Phương án

Hệ số CB

-2 A1 -1

2 A2 -2

1 A3 2

3 A4 0

0 A5 1

1 A6 0

1

-1

1

0

0

1

2

0

2

1

0

1

37

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BT QHTT

Và bảng đơn hình được thành lập như sau

θ

Cơ sở B

Phương án

Hệ số CB

0

4

-2 A1 -1

2 A2 -2

1 A3 2

3 A4 0

0 A5 1

1 A6 0

1

5

1

-1

1

0

0

1

3

7

2

0

2

1

0

1

A5 A6 A4

38

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BT QHTT

Và bảng đơn hình được thành lập như sau

θ

Cơ sở B

Phương án

Hệ số CB

0

4

-2 A1 -1

2 A2 -2

1 A3 2

3 A4 0

0 A5 1

1 A6 0

1

5

1

-1

1

0

0

1

3

7

2

0

2

1

0

1

A5 A6 A4

26

39

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

13

10/5/2012

PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BT QHTT

Và bảng đơn hình được thành lập như sau

θ

Cơ sở B

Phương án

Hệ số CB

0

4

-2 A1 -1

2 A2 -2

1 A3 2

3 A4 0

0 A5 1

1 A6 0

1

5

1

-1

1

0

0

1

3

7

2

0

2

1

0

1

A5 A6 A4

26

9

-1

6

0

0

0

40

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BT QHTT

Và bảng đơn hình được thành lập như sau

θ

Cơ sở B

Phương án

Hệ số CB

0

4

-2 A1 -1

2 A2 -2

1 A3 2

3 A4 0

0 A5 1

1 A6 0

-

1

5

1

-1

1

0

0

1

5

3

7

2

0

2

1

0

1

7/2

A5 A6 A4

26

9

-1

6

0

0

0

Nhận xét: x0 chưa là PATƯ

41

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BT QHTT

Và bảng đơn hình được thành lập như sau

θ

Cơ sở B

Phương án

Hệ số CB

0

15/2

-2 A1 0

2 A2 2

1 A3 3

3 A4 1/2

0 A5 1

1 A6 0

1

3/2

0

1

0

-1/2

0

1

-2

7/2

1

0

1

1/2

0

1

A5 A6 A1

26

0

-1

-3

-9/2

0

0

Nhận xét: x0 = (7/2, 0, 0, 15/2, 3/2 ) là PATƯ

42

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

14