QUI HOẠCH TUYẾN TÍNH

1. Bài toán QHTT và các tính chất 2. Giải bài toán QHTT  3. Các cặp bài toán đối ngẫu

1

1. Bài toán QHTT & các tính chất 1.1. Một vài bài toán trong kinh tế a) Bài toán lập kế hoạch sản xuất Tình huống: Một doanh nghiệp dự định sản xuất 4 loại sản phẩm S1, S2, S3, S4 từ 3 loại nguyên liệu N1, N2, N3.

Biết hao phí nguyên liệu, nguyên liệu dự trữ, lợi nhuận thu được từ mỗi đơn vị sản phẩm cho trong bảng (1).

Lập kế hoạch sản xuất (xác định khối lượng sản

2

phẩm mỗi loại), để doanh nghiệp đạt lợi nhuận tối đa, trong điều kiện nguyên liệu dự trữ hiện có, và các yếu tố sản xuất khác doanh nghiệp luôn có đủ.

Bảng 1

S1

S2

S3

S4

Nguyên liệu

b1 b2 b3

N1 N2 N3 Lợi nhuận

a11 a21 a31 c1

a12 a22 a32 c2

a13 a23 a33 c3

a14 a24 a34 c4

X=

x4

x1

x2

x3

Nguyên liệu dự trữ

Mô hình toán: Gọi xj là khối lượng sản phẩm loại Sj mà doanh nghiệp cần sản xuất j=1,2,3,4; F là tổng lợi nhuận.

Ta có bài toán sau:

3

Mô hình toán bài toán lập kế hoạch sản xuất

F=c1x1+c2x2+c3x3+c4x4Max

a11x1+a12x2+a13x3+a14x4  b1 a21x1+a22x2+a23x3+a24x4  b2 a41x1+a32x2+a33x3+a34x4 b3

xj 0 j

4

b) Bài toán lựa chọn danh mục đầu tư

Tình huống: Một công ty đầu tư dự định dùng

khoản quỹ 500 tỷ để mua một số cổ phiếu trên thị trường chứng khoán.

Biết lãi suất của các loại cổ phiếu, và giới hạn mua

các loại cổ phiếu cho trong bảng sau:

Giới hạn

Loại chứng khoán A B C D

Lãi suất năm 7% 8.5% 7.8% 8.2%

100 tỷ 300 tỷ 250 tỷ 320 tỷ

5

Tình huống.

Để ngăn ngừa rủi ro quỹ đầu tư quy định khoản đầu tư vào cổ phiếu A, C phải chiếm ít nhất 55%, cổ phiếu B chiếm ít nhất 15% trong tổng số tiền đầu tư.

Xác định số tiền công ty mua từng loại cổ phiếu (một danh mục đầu tư) sao cho không vượt quá các khoản dự kiến ban đầu, có mức lãi suất trung bình lớn nhất.

6

Mô hình toán: Gọi xA,xB,xC,xD là các khoản tiền mà quỹ dùng để mua các loại cổ phiếu của các công ty tương ứng. Bài toán đặt ra là tìm danh mục đầu tư (xA,xB,xC,xD) thỏa: F = 0.07xA+0.085xB+0.078xC+0.082xDMax

xA+xC0.55(xA+xB+xC+xD) xB 0.15(xA+xB+xC+xD) xA+xB+xC+xD500 0xA 100 0 xB 300 0 xC 250 0 xD 320

7

1.2. Bài toán QHTT a)Các khái niệm về bài toán QHTT

n

F

Min / Max

(1)

j

 c x j

j=1

n

a x ij

j

b i i

I 1

j=1 n

(2)

a x ij

j

b i i

I 2

    

j=1

I1, I2, I3I={1,2,..m}

8

a) Các khái niệm về bài toán QHTT

F(X) được gọi là hàm mục tiêu, hệ (2) là hệ ràng

buộc của bài toán QHTT.

Với mỗi iI ta có một phương trình hoặc một bất

phương trình gọi là ràng buộc thứ i. Với mỗi iI, ta có một véctơ dòng:

A*i=(ai1, ai2, .., ain)

Hệ {A*j} tạo thành một ma trận Amn=(aij). Hệ ràng buộc có hệ các véctơ {A*i} độc lập tuyến

tính được gọi là hệ ràng buộc độc lập.

Trong hệ ràng buộc (2), mỗi ẩn xj tương ứng với

một vectơ cột Aj =(a1j,a2j,..,amj)T, gọi là vectơ điều kiện.

9

a) Các khái niệm về bài toán QHTT

Vectơ X=(x1,x2,..,xn) thỏa hệ (2), gọi là một

phương án (PA) của bài toán QHTT, D là tập các PA của bài toán.

Nếu ràng buộc thứ i thỏa dấu “=“ với phương án X, thì ta nói ràng buộc thứ i chặt đối với X. Ngược lại ta nói ràng buộc thứ i lỏng đối với X.

Một PA thỏa chặt n ràng buộc độc lập, gọi là

phương án cực biên (PACB). (n là số ẩn số của bài toán QHTT)

PACB thỏa đúng n ràng buộc chặt gọi là PACB

không suy biến

10

a) Các khái niệm về bài toán QHTT

PACB thỏa nhiều hơn n ràng buộc chặt gọi là

PACB suy biến.

X* là PATƯ khi và chỉ khi thỏa 2 điều kiện sau: Với FMin:

) X* D 1 ) F(X*) F(X) X D 2

 

Với FMax:

) X* D 1 ) F(X*) F(X) X D 2

 

11

b) Các tính chất của bài toán QHTT

TC1: Nếu bài toán QHTT có tập các phương án

D, và r(A)=n, thì bài toán có PACB.

TC2: Nếu bài toán QHTT có tập các phương án

D, và F(X) bị chặn /D thì có PATƯ.

TC3: Bài toán QHTT có và chỉ có 3 khả năng sau:

1) Bài toán không có PATƯ 2) Bài toán có duy nhất 1 PATƯ 3) Bài toán có vô số PATƯ

12

TD1:

F=3x1+x2+2x3+x4Min x2 -x3 + x4 =0 x1-4x2 +3x4 15 2x1 -x3 + x4 -2 xj0 j

a) Chứng tỏ bài toán có PACB, chỉ ra một PACB suy biến, một PACB không suy biến, PA không cực biên b) Chứng tỏ bài toán có PATƯ Giải: a) r(A)=4 Bài toán có PACB X0=(0,0,0,0) là PACB suy biến X1=(1,0,0,0) là PACB không suy biến X=(16,1,2,1) là PA không cực biên

13

b) Vì xj0 j  F(X)0 Bài toán có D, và F(X) bị chặn dưới nên có PATƯ Bài tập: 1) Cho bài toán QHTT

F=-4x2-3x3-x4-3x5-x6Max 20 x1-2x2+x3 -2x5 -11 3x2 -x3+x4+ x5 x2+4x3 +2x5+x6 -3 Chứng tỏ bài toán có PATƯ; Tìm một PATƯ HD: Lấy BPT (2)+BPT(3) F(X)14 PATƯ X*=(x1,0,0,-11,0,-3)

14

2) Cho bài toán QHTT (HVNH năm 2001)

F = 5x1 – 4x2 + 2x3 + 3x4  Min 3x1 – 2x2 + x3 + 2x4  20 x1 + x2 – 3x3 + 2x4  –15 2x1 – 2x2 + x3 + x4  30

a)Bài toán có PACB hay không? b)Chứng tỏ bài toán có PATƯ c)Có kết luận gì khi vectơ b thay đổi? HD: Lấy BPT(1)+BPT(3)F(X)50; D

Bài toán có PATƯ

15

3) Cho bài toán QHTT

F = –4x1 –5x2 + 2x3  Min/ Max

x1 + 3x2 –3x3 = 17 –x1 – x2 + 2x3  2 4x1 + 5x2 –2x3  43 2x1 – x2 + 8x3 = –1

x3  0

a) Xác định tập các PA và các PACB b) Chứng tỏ bài toán có PATƯ và chỉ ra PATƯ của hai bài toán Min/ Max HD: F=103  XD đều là PATƯ

16

2. Giải bài toán QHTT 2.1. Phân loại bài toán QHTT a) Bài toán tổng quát n

F

Min/Max

( ) 1

j

 c x j

j=1

n

ax b i ij

j

I   i 1

j=1 n

( ) 2

a x ij

j

b i i

I 2

j=1

n

a x ij

j

b i i

I 3

j=1

j

  

0

..n 1

( ) 3

jx

17

          

2.1. Phân loại bài toán QHTT b) Bài toán chính tắc

n

F

Min/Max

( ) 4

j

 c x j

j=1

n

..m

, 1 2

( ) 5

a x ij

j

b i i

0

j  

, 1 2

..n i 

( ) 6

 j=1 jx

    

18

khi k

i

a

kj

2.1. Phân loại bài toán QHTT c) Bài toán cơ bản Ẩn xj là ẩn cơ sỏ của PT thứ i nếu:

khi k

i

 

1    0 

Bài toán cơ bản là bài toán chính tắc nếu mỗi phương trình trong hệ ràng buộc có một ẩn cơ sở.

TD: F= 2x1+3x2-x3-3x4+x5Min

+x3

-2x1 3x1+x2 x1

+x4

+3x5 =3 -2x5 =5 =1 +x5

xj0 j=1,2..5

Bài toán có PACB X0=(0,5,3,1,0)

19

2.1. Phân loại bài toán QHTT c) Bài toán cơ bản

n

F

Min/Max

( ) 7

j

 c x j

j=1

x

..m

, 1 2

( ) 8

a x ij

b i i

j

iB

j

i

 j B     0

, 1 2

  

0

, 1 2

..m ( ) 9

j

..n; b i

    x 

XBi là ẩn cơ sở của phương trình thứ i; B là tập các chỉ số của các ẩn cơ sở.

i

X

Bài toán CB có PACB:

0 (x ) j

0

  i khi j B

0

b khi j B B    

20

2.2. Các tính chất của bài toán chính tắc

n

F

c x Min/Max

4 ( )

j

j

j=1

n

1 2 , ..m

5 ( )

a x ij

j

b i i

0

  j

1 2 , ..n

6 ( )

j

    j=1   x 

21

1) X là PACB của bài toán chính tắc (4)(5)(6)

ĐL: Hệ các véc tơ {Aj} tương ứng với các thành phần dương của X độc lập tuyến tính.

2) Nếu bài toán chính tắc có PA thì có PACB, và

số PACB là hữu hạn.

3) Nếu bài toán chính tắc có PATƯ, thì sẽ có ít

nhất một PATƯ là PACB.

TD: Xét bài toán QHTT:

F = x1 + 4x2 + 6x3 Max 3x1 + 4x2 + 4x3 = 10 -x1 + x2 + x3 = -1 xj0 j

Cho X0=(2,1,0) chứng tỏ X0 là PACB Vì A1=(3,-1)T, A2=(4,1)T là hệ vectơ độc lập tuyến tính.

22

2.3. Giải bài toán QHTT cơ bản Bài toán cơ bản:

n

F

Min/Max

( ) 7

c x j

j

j=1

x

, 1 2

..m ( ) 8

B

a x ij

j

b i i

i

j B 

..n

0

j  

, 1 2

( ) 9

j

     x 

Bài toán cơ bản luôn có PACB:

khi j B B

X

0 (x ) j

0

  i khi j B

0

b  i   

23

2.3. Giải bài toán QHTT cơ bản Ý tưởng: Giả sử bài toán cơ bản (7)(8)(9) có PATƯ, thì sẽ có PATƯ là PACB. Như vậy ta chỉ cần tìm PATƯ của bài toán quy hoạch trên tập các PACB. Bắt đầu từ PACB X0, ta xây dựng một tiêu chuẩn để đánh giá tính tối ưu của X0. Nếu X0 là PATƯ thì bài toán giải xong, nếu X0 chưa tối ưu, ta chuyển qua PACB mới X1 tốt hơn. Nếu X1 là PATƯ thì bài toán giải xong, ngược lại ta chuyển qua PACB X2 ... Nhờ tính hữu hạn của các PACB, nên việc giải bài toán QHTT sẽ kết thúc sau một số hữu hạn bước.

24

2.3. Giải bài toán QHTT cơ bản Để xây dựng tiêu chuẩn đánh giá tính tối ưu của X0 ta rút các ẩn cơ sở trong hệ (8) thế vào hàm F(X) (7) được:

m

m

F(X)

j

c b B i i

c a B ij i

i

i

j B 

 1

 1

    

 c x  j 

m

m

Đặt:

  j

c a Bi ij

c   j

j ; F(X ) 0

c b B i i

i

i=1

 1

)x

(*)

j

j

F(X) F(X )  0

 (

j B 

Từ (*) ta có các tiêu chuẩn tối ưu như sau:

25

ĐL2: (Tiêu chuẩn tối ứu cho FMin) 1) Nếu j0 j thì X0 là PATƯ. 2) Nếu tồn tại j>0 và akj0 với mọi k  F(X) không bị chặn dưới  Bài toán không có PATƯ. 3) Nếu mỗi j>0 đều có akj>0, thì xây dựng được PACB X1 tốt hơn (F(X1)F(X0)).

ĐL3: (Tiêu chuẩn tối ứu cho FMax) 1) Nếu j0 j thì X0 là PATƯ. 2) Nếu tồn tại j<0 và akj 0 với mọi k  F(X) không bị chặn trên  Bài toán không có PATƯ. 3) Nếu mỗi j<0 đều có akj>0, thì xây dựng được PACB X1 tốt hơn (F(X1)F(X0)).

26

Thuật toán đơn hình FMin 1/ Lập bảng đơn hình cho PACB X0 2/ Xét dấu j 0?

+ Nếu j 0 j X0 là PATƯ + Nếu j >0, và akj0 k  F không bị chặn dưới  bài toán không có PATƯ + Nếu mỗi j>0, đều có akj>0, chuyển qua

bước 3/. 3/ Xây dựng PACB X1 tốt hơn

+ Lấy xj tương ứng với j>0 là ẩn cơ sở mới. + Xét Min{bk/akj: akj>0}=bi/aij=j + Lấy aij làm phàn tử chủ yếu + Tính các hệ số cho bảng đơn bảng X1

Lặp lại thuật toán từ bước 2/

27

FMin

Bảng đơn hình của x0

CS

b

CB

x2 c2 a12 a22

ai2

xB1 xB2 .. xBi .. xBm

cB1 cB2 .. cBi .. cBm

b1 b2 .. bi .. bm

.. xn .. xj x1 .. cn .. cj c1 .. a1n .. a1j a11 .. a2n .. a2j a21 .. .. .. .. .. ain .. aij ai1 .. .. .. .. .. amj am1

.. amn

am2

F(X0) 1

2

j .. n

28

Chú ý: Nếu xj là ẩn cơ sở thì j=0

Tính các hệ số cho bảng X1 theo quy tắc hình chữ nhật

- Dòng chủ yếu (dòng i): d’i=di/aij - Cột chủ yếu: ghi số 0 và các ô còn lại - Các phần tử còn lại akt (ki, tj)

.. a

a a kt

ij

a a kj

it

[a ] kt ..

kj ..

..

a ' kt

a

ij

a

..

it

(a ) ij

Tính các hệ số cho bảng X1 theo quy tắc dòng:

- Dòng chủ yếu (dòng i): d’i=di/aij - Dòng k (ki):

d’k=-akj*d’i+dk

29

Chú ý: 1/ khi tính các hệ số của bảng X1 theo quy tắc hình chữ nhật các hệ số bi vẫn tính theo quy tắc này. 2/ Theo quy tắc điều chỉnh này thì ta có: F(X1)=F(X0)-jj

3/ Dòng  từ bảng X1 trở đi có thể được tính bằng 2 cách.

Cách 1: Tính như bảng X0 Cách 2: Coi dòng  bình đẳng như những

khác, và tính theo quy tắc dòng.

30

Thuật toán đơn hình F(x) Min

Băt đầu

Lập bảng X0

j0 j

X0 – PATƯ

Xét dấu j

F(X) -

j>0&akj0k

Mỗi j>0 có akj>0

Lập bảng X1

31

TD1: Giải bài toán QHTT

F = 3x1+x2+2x3+3x4+2x5+4x6Min 2x1 +x3+ x4 +2x6=5 3x1+x2 +2x4 +x6 =11 x1 +2x4 +x5 +x6 =5 xj0; j=1,2..6

Giải: Đây là bài toán cơ bản, với các ẩn cơ sở x2,x3,x5,và PACB X0=(0,11,5,0,5,0) Lập bảng đơn hình cho X0

32

CS

CB

b

x1 3

FMin x5 2

x3 2

x4 3

x6 4

x2 1

5

(2)

2

1

1

0

2

0

11

3

1

0

2

0

1

1

5

1

2

0

2

1

1

0

x3 x2 x5

31

[6]

0

5

0

3

0

5/2

1

3

1/2

1/2

0

1

0

7/2

0

1

-3/2

1/2

0

-2

1

5/2

0

2

-1/2

(3/2)

1

0

0

x1 x2 x5

16

0

-3

[2]

0

-3

0

5/3

1

3

2/3

0

-1/3

1

0

8/3

0

1

-4/3

0

-1/3

-2

1

5/3

0

3

-1/3

1

2/3

0

0

x1 x2 x4

38/3

0

-7/3

0

-4/3

-3

0

Bài toán có PATƯ X2=(5/3, 8/3, 0, 5/3, 0, 0) FMin = 38/3

33

Thuật toán đơn hình FMax 1/ Lập bảng đơn hình cho PACB X0 2/ Xét dấu j 0?

+ Nếu j  0 j X0 là PATƯ + Nếu j<0, và akj<0 k  F không bị chặn trên

 bài toán không có PATƯ

+ Nếu mỗi j<0 đều có akj>0, chuyển qua bước 3/.

3/ Xây dựng PACB X1 tốt hơn (F(X1)>F(X0))

+ Lấy xj tương ứng với j<0 làm ẩn cơ sở mới. + Xét Min{bk/akj: akj>0}=bi/aij + Lấy aij làm phàn tử chủ yếu + Tính các hệ số cho bảng đơn bảng X1 như FMin

34

TD: Giải bài toán QHTT

F=20x1+33x2+18x3Max

2x1+5x2+2x3+x4 =24 x1+2x2+x3 +x5 =12 4x1+ x2 +2x3 +x6=39 xj0 j

Giải: Lập bảng đơn hình cho X0

35

CS CB b

x1 20 x2 33 x3 18 x4 0 FMax x6 0 x5 0

24 2 5 2 1 0 0 0

12 1 2 (1) 0 0 0 1

0 x4 x5 x6

39 0 4 -20 1 -33 2 [-18] 0 0 1 0 0 0

0 0 1 0 1 0 0 -2

12 1 2 1 0 18 0 1

0 x4 x3 x6

15 216 0 (2) [-2] 0 -3 3 1 0 0 0 0 0 1 0 1 0 0 -2 18 0

9/2 0 7/2 1 0 18 -1/2 -2

20 x4 x3 x1

15/2 231 -1 16 0 0 1 0 0 0

36

1/2 -3/2 1 0 Bài toán có PATƯ X2=(15/2, 0, 9/2, 0, 0, 0); Fmax=231

Chú ý: Bài toán FMax có thể giải bằng hai cách. Cách 1: Giải theo thuật toán Max Cách 2: Giải bài toán (-F)Min.

- Nếu (-F)Min không có PATƯ thì bài toán Max cũng không có PATƯ. - Nếu bài toán (-F)Min có PATƯ X* thì bài toán Max cũng có PATƯ X* TD3: Giải bài toán QHTT

F = -27x1-2x2+x3+14x4+2x5+6x6+5x7Max

-2x1+x2 +3x4 -2x6+2x7=4 -3x1 +x3+4x4 + x7=3 -5x1 +2x4+x5+ x6+ x7=5

xjj

Giải: Bài toán (-F)Min

37

CS CB b

x1 27 x2 2 x3 -1 x4 -14

(-F)Min x7 -5

x6 -6 x5 -2

2 4 -2 1 0 3 -2 (2) 0

-1 3 -3 0 1 4 0 1 0

-2 5 -5 0 0 2 1 1 1 x2 x3 x5

 -5 -18 0 0 12 0 [6] 0

-5 2 -1 1/2 0 3/2 -1 1 0

-1 1 -2 -1/2 1 5/2 (1) 0 0

-2 3 -4 -1/2 0 1/2 2 0 1 x7 x3 x5

 -17 -12 -3 0 3 [6] 0 0

-5 3 -3 0 1 4 0 1 0

-6 1 -2 -1/2 1 -2 1 0 0

-2 1 0 31/2 2 -9/2 0 0 1 x7 x6 x5

38

Bài toán (–F)Min có PATƯ X2=(0,2,0,0,0,2,3). Bài toán Fmax cũng có PATƯ X2 và FMax =23

 -23 0 0 -6 -12 0 0 0

Chú ý: Từ bảng đơn hình cuối cùng ta thấy x1 x2 là các ẩn phi cơ sở, có 1=0, 2=0 nên có thể tìm thêm được 2 PATƯ:

[0,+)

X4=(,2,0,0,0,2+2,3+3) X5=(0,,0,0,(2-31)/2,(2+)/2,3) 1[0,2/31]

Từ đó suy ra bài toán có vô số PATƯ, và tập các PATƯ là: X = X4+(1-)X5 trong đó [0,1]

Nếu FMin thì từ bảng đơn hình X0 có 1=18 và ak1<0 với mọi k  bài toán không có PATƯ.

39

Bài tập: Giải các bài toán QHTT sau: 1/

F=2x1+4x2+6x3+8x4+x5+6x6Min/Max

x1 +2x3 +x4 =6 2x1 +x2 +3x3 + x6=10 4x1 +3x3 +x5 + x6=36

xj0 j ĐS: X*=(0,10,0,6,0,0); FMin=88

X*=(0,0,0,6,26,10); FMax=134

2/

F=-23x1-6x2+6x3+6x4+6x5-6x6Min/Max + x4

x1

x2- 4x3 - 3x4

+6x6 =0 -16x6=2 2x3 - x4 +x5 - 4x6=6 xj0 j

ĐS: X*=(0,14,3,0,0,0); FMin=-66 X*=(0,2,0,0,6,0); Fmax=24

40

3/

F=x1-6x2+3x3+3x4+11x5-6x6Min/Max

- x6 =2 x3-2x4 +2x4 -2x6=0 + x4 +x5 - x6=1

2x1+x2 x1 xj0 j

ĐS: Bài toán không có PATƯ, D=

4/

x1+4x2

F=5x1+4x2-5x3+5x4-2x5+3x6Min/Max =12 +2x4+2x5 2x2+ x3+4x4+3x5 =24 3x4+2x5+x6=18 xj0 j

ĐS: X*=(0,3,18,0,0,18); Fmin=-24 X*=(0,0,0,6,0,0); Fmax=30

41

5/

F= -4x1+2x2+3x3 +x4 -2x5Min/Max -5x1+ x2 +3x3+2x4 =5 + x3+ x4+ x5 =2 -2x1 +2x3+2x4 +x6=8 -4x1

xj0 j

ĐS: X*=(0,0,5/3,0,1/3,14/3) Fmin=13/3

Bài toán Fmax không có PATƯ (F không bị chặn)

6/ Giải và biện luận theo tham số m

F=mx1+(1+m)x2+2x3+(2-m)x4+x5+2x6Min/Max

-x1 + x2 +2x3 - x4 =4 -2x1 + x3 +2x4 +x6=6 +2x3 +2x4 +x5 =10 -3x1

xj0 j

ĐS:

42

CS

b

CB

x1 m

x2 1+m

x3 2

x4 2-m

x5 1

x6 2

1+m 2 1

4 6 10

-1 -2 -3

1 0 0

2 1 2

-1 (2) 2

0 0 1

0 1 0

x2 x6 x5 

24+4m

-8-2m

0

4+2m

[3]

0

0

1+m 2-m 2

7 3 4

-2 -1 -1

1 0 0

(5/2) 1/2 1

0 1 0

0 0 1

1/2 1/2 -1

x2 x4 x5

0

21+4m

-6-2m

7/2+2m

0

0

-5/2

2 2-m 2

14/5 8/5 6/5

-4/5 -3/5 3/5

2/5 -1/5 -2/5

1 0 0

0 1 0

0 0 1

1/5 2/5 -6/5

x3 x4 x5

0

0

0

56/5- 8/5m

-8/5- 2/5m

-7/5- 4/5m

-16/5- 2/5m

ĐS: TH1: m (-,-3) F không bị chặn, Bài toán không có PATƯ

TH2: m[-3,-7/4] X*=(0,7,0,3,4,0); Fmin=21+4m TH3: m(-7/4,+ ) X*=(0,0,14/5,8/5,6/5,0); Fmin=56/5-(8/5)m

43

2.4. Giải bài toán chính tắc Để giải bài toán chính tắc (4)(5)(6) (bài toán P), bằng bảng đơn hình, ta cần có một PACB X0

Ta xét bài toán cơ bản với các ẩn giả xg

i ký hiệu là

m

n

Min(Max)

(7)

F M

j

j

g i

bài toán PM như sau:   c x M x 

i

i

 1

1  m

x

b

..m

i  

, 1 2

g i

i

j

a x ij

( ) 8

j; b

i

..n

  

0

j

i

    j=1    x 

, 1 2 0 Trong đó: +M cho bài toán FMin -M cho bài toán Fmax

Chú ý: Nếu PT thứ i đã có ẩn cơ sở thì không cần

thêm ẩn giả.

44

i) và có x*g

i=0 i)

Định lý: (Mối liên hệ giữa P và PM) Luôn tồn tại số M>0 đủ lớn để các mệnh đề sau luôn đúng: 1) Bài toán PM có FM không bị chặn thì bài toán P cũng có hàm F không bị chặn (Bài P không có PATƯ). 2) Bài toán PM có PATƯ X*g=(X*,x*g i>0 thì bài P có tập PA D= (Bài P không có PATƯ) 3) Nếu bài toán PM có PATƯ X*g=(X*,0) (x*g thì bài toán P có PATƯ X*

45



j

j

   j  

Công việc giải bài toán chính tắc P được chia thành 2 giai đoạn: Giai đoạn 1: Lập và giải bài toán PM Giai đoạn 2: Kết luận cho bài toán P theo định lý trên Chú ý: Khi lập bảng đơn hình cho PM không cần vẽ các cột ẩn giả. Mỗi j=j+jM trong bài toán PM được ghi 2 dòng:     Khi xét dấu: Nếu j>0  j>0; Nếu j<0  j<0 Nếu j=0 và j>0j>0; Nếu j=0 và j<0j<0

46

TD: F=3x1+4x2+2x3+2x4Min

2x1+2x2 + x4 =28 x1+5x2+3x3-2x4 + x5=31 2x1-2x2+2x3 + x4 =16

xj0 j

Bài toán PM:

2) Min

F=3x1+4x2+2x3+2x4+M(xg 1+xg 2x1+2x2 + x4 +xg 1 =28 x1+5x2+3x3-2x4 + x5 =31 2x1-2x2+2x3 + x4 +xg 2 =16

xj0 j

47

CS

CB

b

x1 3

x2 4

FMin x4 2

x3 2

x5 0

xg

M

28

2

2

1

0

0

0

31

1

5

-2

3

1

1 x5 xg

M

16

(2)

-2

1

2

0

2  

0 44 -3 [4] -4 0 -2 2 -2 2 0 0

xg

M

12

0

(4)

0

-2

0

0

23

0

6

-5/2

2

1

3

8

1

-1

1/2

1

0

1 x5 x1

24 12 0 0 -7 [4] -1/2 0 1 -2 0 0

4

3

0

1

0

-1/2

0

0

5

0

0

-5/2

5

1

3

11

1

0

1/2

½

0

x2 x5 x1

48

Bài toán có PATƯ: X0=(11,3,0,0,5); FMin=45

45 0 0 -1/2 -5/2 0

TD2:

F = 2x1+3x2+4x3+x4Max

x1+ x2+ x3+x4+x5 =5 2x1+2x1+3x3 =18 2x1+ x2 +2x4 -x6=8

Xj0 j

Bài toán PM:

F = 2x1+3x2+4x3+x4-M(xg

2) Max

1+xg x1+ x2+ x3+x4+x5 =5 2x1+2x1+3x3 +xg 2x1+ x2 +2x4 -x6+xg

1=18 2=8

Xj0 j

49

FMax

CS

CB

b

x1 2

x2 3

x3 4

x4 1

x5 0

x6 0

0

5

1

1

1

1

1

0

x5 xg

-M

18

2

2

3

0

0

0

1

xg

-M

8

(2)

1

0

2

0

-1

2

0 -26 -2 [-4] -3 -3 -4 -3 -1 -2 0 0 0 1

0

1

0

1/2

(1)

0

1

1/2

x5 xg

-M

10

0

1

3

-2

0

1

2

4

1

1/2

0

1

0

1/2

1 x1

8 -10 0 0 -2 -1 -4 [-3] 1 2 0 0 1 -1

4

1

0

1/2

1

0

1

1/2

x3 xg

-M

7

0

-1/2

0

-2

-3

-1/2

2

4

1

1/2

0

1

0

-1/2

1 x1

50

Bài toán P không có phương án  P không có PATƯ

12 -7 0 0 0 1/2 0 0 1 2 4 3 3 1/2

2.4. Giải bài toán tổng quát P

Để giải bài toán tổng quát P. Ta chuyển bài toán P về dạng chính tắc, bằng cách thêm vào mỗi bất phương trình một ẩn phụ xn+i0, theo quy tắc:

Với các bất phương trình “” ta cộng thêm vào vế trái một ẩn phụ xn+i

Với bất phương trình “” ta lấy vế trái trừ cho ẩn phụ xn+i

Với hệ số cn+i=0 i ta được bài toán chính tắc P’ tương ứng với bài toán P như sau:

51

Bài toán tổng quát (P)

Bài toán chính tắc (P’)

n

n

F'

Min / Max

F

Min / Max

j

j

 c x j

 c x j

j

 1

 1

j n

n

b

i

i

a x ij

j

i

I 1

a x ij

j

b i

I 1

j=1

j=1

n

n

x

b

i

b

i

a x ij

j

i

n i 

I 2

a x ij

j

i

I 2

j=1

j=1

n

n

b

i

a x ij

j

n i

i

x 

I 3

b

i

j=1

a x ij

j

i

I 3

x

  0

0

j

n i

j; x 

          

j=1 x

  0

i   0

j; b i

j

          

52

Định lý: Bài toán P có PATƯ X* khi và chỉ khi bài toán P’ có PATƯ X’*=(X*|..x*n+i..) Quy tắc giải bài toán tổng quát P:

1) Lập bài toán chính tắc với các ẩn phụ P’ 2) Giải bài toán chính tắc P’ 3) Kết luận cho bài toán P

(P) F=5x1+4x2+6x3Min 2x1 +4x2+ 3x3 - x4 =48 -x1 +2x2 - x4 18

(P’) F’= 5x1+4x2+6x3Min 2x1+4x2+3x3- x4 =48 -x1+2x2 -x4+x5=18 x1 + x2 - x3 -x4+x6=25

x1 +x2 -x3 – x4 25

xj0 j

xj0 j

53

FMin

CS CB b

x1 5 x2 4 x3 6 x4 0 x5 0 x6 0

1 48 (2) 4 3 -1 0 0

0 18 -1 2 0 -1 1 0

0 xg 1 x5 x6

5 25 0 48 24 1 -5 [2] 1 1 -4 4 2 -1 -6 3 3/2 -1 0 -1 1/4 0 0 0 0 1 0 0 0

0 42 0 (4) 3/2 -3/8 1 0

0 x1 x5 x6

1 120 0 0 -1 [6] -5/2 -3/4 -7/8 -1/2 0 0 1 0

5 3 1 0 3/4 1/4 -1/2 0

4 21/2 0 1 3/8 -3/8 1/4 0

0 x1 x2 x6

Bài toán có PATƯ X*=(3,21/2,0,0); FMin=57

54

23/2 57 0 0 0 0 -17/8 -3/4 -7/8 -1/4 1/4 -3/2 1 0

BT1: Giải bài toán QHTT bằng bảng đơn hình

F=2x1+x2+3/2x3-x4Min 5x1+3x2+x3 -2x420 +2x3 +x4=18 2x1 -2x1+2x2+2x3+x4=10

xjj

ĐS: X*=(2,0,0,14,38)

55

BT2: Cho bài toán QHTT

F=x1+5x2-3x3+6x4Min -x1+3x2-x3+x4 =-2 3x1-x2+2x3-x4 14 2x1+x2+x3-3x4 30 xj0 j

a)Chứng tỏ X0=(0,2,8,0) là PACB, lợi dụng X0 giải bài toán bắng phương pháp đơn hình. b)Có kết luận gì khi FMax. Khi đó xác định một PA có thành phần X4>0 và F(X)=0

56

BT3: Cho baøi toán QHTT

F = x1 - 3x2 - 4x3 + x4 + 5x5  Max 2x1 + x2 - 3x3 +2x4

= 30 = 23 x2 – x3 + x4 – x5 3x1 – 2x2 + x3 + x4 + 4x5  -10

xj  0 j

• • • •a) Giaûi baøi toaùn QHTT treân baèng PP ñôn hình •b) Tìm taäp taát caû caùc PATÖ cuûa baøi toaùn

57

+ x4

BT4: Cho baøi toaùn QHTT: F = 5x1 + 2x2 - x3 + 8x4 - 8x5 + 10x6  Min 2x1 – x2 –3x6 = –4 –7x1+3x2 + x3 –3x4 – 2x5 +13x6 = –4 + 2x4 +4x5 –11x6 = 53 4x1 – 3x3

xj  0 j

•a) Chöùng toû X0 = (7, 0, 0, 18, 0, 12) laø PACB •b) Tìm ñieàu kieän cuûa  ñeå X0 laø PATÖ •c) Tìm ñieàu kieän cuûa  ñeå baøi toaùn khoâng giaûi

ñöôïc

58

BT5: Cho baøi toaùn QHTT: F=2x1+4x2+3x3+2x4Min 4x1-3x2+3x3+x4 31 -6 -x1+2x2-x3 2x1-x2+3x3+x4 33

xj0 j

a)Giaûi baøi toaùn baèng baûng ñôn hình. b)Tìm moät PATÖCB khaùc, moâ taû taäp caùc PATÖ vaø tìm moät PATÖ khoâng cöïc bieân coù x3=10 ÑS: X*=(0,3,12,0,4,0,0); X’=(0,1,8,10,0,0,0)

X()= X*+(1-)X’ vôùi [0,1] X’’=(0,2,10,5,2,0,0) TÖ khoâng cöïc bieân

59

BT6: Cho baøi toaùn QHTT: F=3x1-2x2+4x3-x4Min 2x1+x2+2x3+ x4=15 2x2+ x3-2x4=6

x1+5x2

-x4=45

xjj

a)Giaûi baøi toaùn treân b)Coù keát luaän gì khi b3=39? ÑS: Baøi toaùn khoâng coù PATÖ. Neáu b3=39 baøi toaùn coù PATÖ X*=(0,9,0,6)

60

Bài toán đối ngẫu

3. Các cặp bài toán đối ngẫu 3.1. Định nghĩa các cặp ràng buộc đối ngẫu Bài toán gốc F=c1x1+c2x2+..+cnxnMin(Max)

G=b1y1+b2y2+..+bmymMax(Min)

 yi tự do

ai1x1+ai2x2+..+ainxn = bi

iI1

 yi () 0

ai1x1+ai2x2+..+ainxn bi

iI2

ai1x1+ai2x2+..+ainxn  bi

iI3

xj Tự do jJ1 xj 0 jJ2

xj 0 jJ3

 yi () 0  aj1y1+aj2y2+..+ajym = ci  aj1y1+aj2y2+..+ajym () ci  aj1y1+aj2y2+..+ajym () ci

61

Bài toán gốc F= 3x1-2x2+x3Min x1+x2 + x3=3 -2x1 +x2 +3x35 3x1 -2x2-3x3-1

Bài toán đối ngẫu G= 3y1+5y2-y3Max y1-2y2+3y33 y1+y2-2y3-2 y1+3y2-3y31 y20; y30

xj0 j

F= -2x1+x2-3x3Max x1 - x2 + x33 2x1 + x2 -3x3=5 x1 -2x2 - x3 1

G= 3y1+5y2+y3Min y1+2y2+y3-2 -y1+ y2 -2y3 1 y1-3y2-y3 -3 y10; y30

xj0 j

62

3.2. Các tính chất Gọi D là tập các PA của bài toán gốc, D* là tập các PA của bài toán đối ngẫu. ĐL1: Giả sử X=(x1,x2,..,xn)D, Y=(y1,y2,..,ym)D* 1/ Bài toán gốc FMin: F(X)G(Y) XD,YD* 2/ Bài toán gốc FMax: F(X)G(Y) XD,YD* ĐL2: Bài toán gốc có PATƯ  Bài toán đối ngẫu có PATƯ và khi đó trị tối ưu của hai bài toán bằng nhau. ĐL3: Giả sử X=(x1,x2,..,xn)D, Y=(y1,y2,..,ym)D* Khi đó X, Y là 2 PATƯ tương ứng khi và chỉ khi Hoặc: 1) Nếu: xj0  a1jy1+a2jy2+...+amjyi = cj

2) Nếu:

63

ai1x1+ai2x2+...+ainxn  bi  yi=0

Hoặc: 3) Nếu: yi0  ai1x1+ai2x2+...+ainxn = bi 4) Nếu: a1jy1+a2jy2+...+amjym  ci  xj=0

(Phát biểu khác ĐL3: X,Y là hai PATƯ tương ứng khi và chỉ khi: Nếu ràng buộc của bài toán này chặt, thì ràng buộc đối ngẫu tương ứng của bài toán kia phải lỏng)

TD1: Dùng ĐL3 để kiểm tra tính TƯ của X*

F=3x1+4x2+2x3+2x4Min 2x1+2x2 + x4 =28 x1+5x2+3x3-2x4 31 2x1-2x2+2x3 + x4 =16

xj0 j

Hỏi X*=(11,3,0,0) có là PATƯ hay không?

64

Giải: X*=(11,3,0,0)D; x1=11>0 x2=3>0 x1+5x2+3x3-2x4=26<31

 2y1+y2+2y3 =3 *  2y1+5y2-2y3=4 ** ***  y2 =0

Từ *, **, ***  Y*=(7/4,0,-1/4)D*  Y* là PATƯ của bài toán đối ngẫu  X* là PATƯ của bài toán gốc.

65

BT1: Dùng định lý 3 để tìm PATƯ của bài đối ngẫu (gốc) khi biết PATƯ của bài toán gốc (đối ngẫu)

F = 15x1+12x2+16x3+10x4Max x1+3x2+ x3+ x420 2x1+x2 +3x3+2x4=20 x1+2x2+ x3+2x424 xj0 j

a) Giải bài toán bằng phương pháp đơn hình

ĐS: X*=(0,4,0,8); Fmax=128

b) Viết bài toán đối ngẫu và tìm tập các PATƯ của bài toán đối ngẫu

66

ĐS: Y=(y1,-2+2y1,7-(5/2)y1); y124/5

BT2: Cho bài toán QHTT

F=-4x2-3x3-x4-2x5-x6Max x1-2x2+ x3 -2x5 20 3x2 -x3+x4 -x5 -11 x2+4x3 +3x5+x6-3

Chứng tỏ bài toán có PATƯ, tìm một PATƯCB và một PATƯ không cực biên. HD: Bài toán đối ngẫu có duy nhất một PA nên cũng là PATƯ, suy ra bài toán gốc có PATƯ

67

BT3: Cho bài toán QHTT

F=-2x1+x2+x3+5x4Min

x1 3x1-2x2

=5 9 8 -13

x3 -x3+5x4

a) Hãy chỉ ra một PACB b) Chứng tỏ bài toán không có PATƯ c) Nếu c2=-1, tìm PATƯ ĐS: X*=(5,3,8,-1)

68

BT4: Cho veùc tô X0=(0,0,2,5,0,0) vaø baøi toaùn QHTT

F = 5x1+4x2–x3+3x4+6x5–2x6  Min 2x1 –x2 + x3 –2x4 + x6 = –8 –x1 + x2 + 2x4 –4x5 –x6 = 10 –3x1 + 2x2 –x3 + x4 –2x5  3

xj  0 j

Vieát baøi toaùn ñoái ngaãu, chöùng toû X0 laø PACBTÖ, vaø tìm taäp caùc PATÖ cuûa baøi toaùn ñoái ngaãu.

69

BT5: Cho baøi toaùn QHTT:

F=5x1+4x2-x3+3x4+6x5-2x6Min 2x1-x2+x3-2x4 +x6=-8 -x1+x2 +2x4-4x5-x6=10 3 3x1+2x2-x3+x4-2x5 xj0j

Vaø vectô X0=(0,2,5,0,0)

a)Vieát baøi taùn ñoái ngaãu b)Chöùng toû X0 laø PACBTÖ, xaùc ñònh taäp caùc PATÖ vaø caùc PACBTÖ cuûa baøi toaùn ñoái ngaãu. ÑS: Y*=(-1+y3,1/2,+1/2y3,y3); Y1=(-3,-1/2,-2); Y2=(-2,0,-1)

70