tài liệu trang web lớp đ5h13b đại học điện lực

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (521.29 KB, 88 trang )

(1)<div class='page_container' data-page=1>

CHƯƠNG I: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH

§1 MỢT SỚ VÍ DỤ DẪN ĐẾN BÀI TOÁN QUY HOẠCH

TUYẾN TÍNH

I. Bài toán lập kế hoạch sản xuất trong điều kiện tài nguyên hạn chế:

Ví dụ:

Nhân dịp tết trung thu, 1 xí nghiệp muốn sản xuất 3 loại bánh: Đậu xanh,
thập cẩm, bánh dẻo nhân đậu xanh. Để sản xuất 3 loại bánh này, xí nghiệp
phải có đường, đậu, bột, trứng, mứt, lạp xưởng…Gỉa sử số đường có thể
chuẩn bị được là 500kg, đậu là 300kg, các nguyên liệu khác muốn có bao
nhiêu cũng được. Lượng đường, đậu và số tiền lãi khi bán 1 chiếc bánh mỗi
loại cho trong bảng:

Bánh
Nguyên liệu

Bánh đậu xanh Bánh thập cẩm Bánh dẻo

Đường: 500kg 0.06kg 0.04kg 0.07kg

Đậu: 300kg 0.08kg 0 0.04kg

Lãi: 2 ngàn 1.7 ngàn 1.8 ngàn

Cần lập kế hoạch sản xuất mỗi loại bánh bao nhiêu cái để không bị động về
đường, đậu và tổng số lãi thu được là lớn nhất( nếu sản suất ra bao nhiêu
cũng bán hết)

GIẢI:

Phân tích:

Gọi x1; x2; x3 lần lượt là số lượng bánh đậu xanh, thập cẩm, bánh dẻo cần

sản xuất

1. Điều kiện của ẩn: xi≥ 0 , i=1,3 .

2. Tổng số đường: 0 . 06 x1+0 . 04 x2+0. 07 x3

Tổng số đậu: 0 . 08 x1+0 . x2+0 . 04 x3

Tổng tiền lãi: 2 x1+1 .7 x2+1. 8 x3
Ta có mô hình toán học của bài toán:

(1)
¿
¿

¿f ( x )=2 x1+1 . 7 x2+1 .8 x3→ max ¿ (2) ¿

{

0 .06 x1+0 . 04 x2+0 . 07 x3≤ 500

0 .08 x1+0 . x2+0 . 04 x3≤ 300 (3 ) ¿xj≥ 0 , j=1. 3

Mô hình toán học dưới dạng ma trận:

</div>
(2)<div class='page_container' data-page=2>

A=

[

0 .06 0 . 04 0 . 07

0 . 08 0 0 . 04

]

B=

[

500

300

]

véc tơ số hạng tự do.

x=(x1; x2;x3) là véc tơ ẩn số.

Một véc tơ x=(x1; x2; x3) thỏa (2) và(3) gọi là 1 phương án của bài toán.

Một phương án x=(x1; x2;x3) thỏa (1) gọi là 1 phương án tối ưu của bài

toán.

II. Bài toán đầu tư vốn nhỏ nhất:

Ví dụ:

Có 3 xí nghiệp may cùng có thể sản xuất áo vét và quần. Do trình độ công
nhân, tài tổ chức, mức trang bị kỹ thuật…khác nhau, nên hiệu quả của đồng
vốn ở các xí nghiệp cũng khác nhau. Gỉa sử đầu tư 1000$ vào mỗi xí nghiệp
thì cuối kỳ ta có kết quả

Xí nghiệp 1: 35 áo 45 quần.
Xí nghiệp 2: 40 áo 42 quần.
Xí nghiệp 3: 43 áo 30 quần.

Lượng vải và số giờ công cần thiết để sản xuất 1 áo hoặc 1 quần ( gọi là suất
tiêu hao nguyên liệu và lao động) được cho ở bảng sau:

XN
Sản phẩm

1 2 3

Áo vét 3.5m 20h 4m 16h 3.8m 18h

Quần 2.8m 10h 2.6m 12h 2.5m 15h

Tổng số vải và giờ công lao động có thể huy động được cho cả 3 xí nghiệp
là 10.000m và 52.000 giờ công.

Theo hợp đồng kinh doanh thì cuối kỳ phải có tối thiểu 1500 bộ quần áo. Do
đặc điểm hàng hóa, nếu lẻ bộ chỉ có quần là dễ bán.

Hãy lập kế hoạch đầu tư vào mỗi xí nghiệp bao nhiêu vốn để :
- Hoàn thành kế hoạch sản phẩm.

- Không khó khăn về tiêu thụ.
- Không bị động về vải và tiêu thụ.

- Tổng số vốn đầu tư nhỏ nhất là điều nổi bật cần quan tâm.
Phân tích:

1)Gọi x1; x2; x3 lần lượt là số đơn vị vốn đầu tư ( 1000$) vào mỗi xí

nghiệp.

Ta có: xj≥0 , j=1,3

2)Tổng số áo của 3 XN: 35 x1+40 x2+43 x3 ,

</div>
(3)<div class='page_container' data-page=3>

Để không khó khăn về tiêu thụ thì:

45 x1+42 x2+30 x3≥ 35 x1+40 x2+43 x3⇔10 x1+2 x2−13 x3≥0

4)Tổng số bộ quần áo= Tổng số áo của 3 XN: 35 x1+40 x2+43 x3 ,

5) Tổng số mét vải của 3 xí nghiệp ( dùng để may áo và quần ):

¿3 .5 ×35 x1+4 × 40 x2+3. 8 × 43 x3
+¿2 .8 × 45 x1+2 . 6 ×42 x2+2. 5 ×30 x3

248 .5 x1¿+269. 2 x2+238 . 4 x3

6) Tởng sớ giờ cơng của 3 xí nghiệp:
¿20× 35 x1+16 × 40 x2+18 × 43 x3

+¿10 × 45 x1+12× 42 x2+15 ×30 x3

1150 x1¿+1144 x2+1224 x3

7) Tởng sớ vớn đẩu tư( đơn vị: 1000$): x1+x2+x3

Mô hình toán học

(1) f ( x )=x1+x2+x3→ min

(2)

{

10 x1+2 x2− 13 x3≥ 0
35 x1+40 x2+43 x3≥1500

248 . 5 x1+269 .2 x2+238 . 4 x3≤10000

1150 x1+1144 x2+1224 x3≤ 52000
(3) xj≥ 0 , j=1,3

Mô hình toán học dưới dạng ma trận:

A=

[

10 2 − 13

35 40 43

248. 5 269. 2 238 . 4
1150 1144 1224

]

, B=

[

0
1500
10000
52000

]

III. Bài toán vận tải

Ví dụ:

Ta cần vận tải vật liệu từ 2 kho: K1 và K2 , đến 3 công trường xây dựng: C1,

C2, C3 . Tổng số vật liệu có ở mỗi kho, tổng số vật liệu yêu cầu của mỗi công

</div>
(4)<div class='page_container' data-page=4>

Hãy lập kế hoạch vận chuyển thế nào để:
- Các kho giải phóng hết vật liệu.

- Các công trường nhận đủ vật liệu cần thiết.
- Tởng sớ T × km phải thực hiện là ít nhất.
GỈAI

Phân tích:

1. Gọi x ¿

ij(i=1,2 ; j=1,2,3) ¿ lần lượt là số tấn vật liệu vận chuyển từ kho

Ki→ Cj∀ xij≥ 0

2. Số tấn vật liệu từ kho K1 đến 3 công trường:

x11+x12+x13

3. Số tấn vật liệu từ kho K2 đến 3 công trường:

x21+x22+x23

4. Số tấn vật liệu công trường C1 nhận được từ 3 kho:

x11+x21

5. Số tấn vật liệu công trường C2 nhận được từ 3 kho:

x12+x22

6. Số tấn vật liệu công trường C3 nhận được từ 3 kho:

x13+x23

7. Tởng sớ T × km :

5 x11+7 x12+2 x13+4 x21+3 x22+6 x23

</div>
(5)<div class='page_container' data-page=5>

(1) f ( x )=5 x11+7 x12+2 x13+4 x21+3 x22+6 x23→ min

(2)

{

x11+x12+x13=20

x21+x22+x23=40

x11+x21=15

x12+x22=20

</div>
(6)<div class='page_container' data-page=6>

j=1
n

aijxj≤ bi

∑

j=1
n

aijxj≥ bi

(3) xj ≥0(j∈ J1); xj ≤0(j∈ J2); xjtù̀ y y

'

̀́(j∈ J3);J1∪ J2∪J3={1 ;2; …;n}

Vector x=(x1; x2;… ;xn) thỏa (2);(3) gọi là 1 phương án của bài toán.

- Nếu phương án thỏa (1) tức là hàm mục tiêu đạt cực đại( hay cực tiểu)
thì gọi là phương án tối ưu.

- Giải 1 bài toán QHTT là đi tìm phương án tối ưu hoặc chỉ ra bài toán
không có phương án tối ưu.

Ví dụ:

Bài toán sau đây có dạng tổng quát:

(1) f ( x )=3 x1− x2+2 x3+x4+5 x5→ max

(2)

{

2 x1− x2+x3+2 x4+x5≤17
4 x1−2 x2+x3=20

x1− x2+2 x3+x5≥ −18

x1+x2+2 x3+x4≤ 100
(3) x1; x4≥ 0 ; x2; x5≤0 ; x3tu ̀̀ y y'
II. Dạng chính tắc:

(1) f ( x )=

∑

j=1
n

cjxj→ min (max)

(2)

∑

j=1
n

aijxj=bi(i=1 , m)

</div>
(7)<div class='page_container' data-page=7>

Ví dụ:

Bài toán sau đây có dạng chính tắc:

(1) f ( x )=3 x1− x2+x3−3 x4+x5→ min
(2)

{

2 x1+x2− x3+3 x4=0

x2− x3− x4+x5=−18

x3+2 x4− x5=17
(3 ) xj≥ 0 ; j=1,5

III. Dạng chuẩn:

(1) f (x )=

∑

j =1
n

cjxj→min (max)
x1

¿
¿

¿ ¿+a1(m +1)xm +1+⋯a1 nxn=b1 x2
¿ +a2(m +1)xm+1+⋯a2nxn=b2 ⋱
¿.. . .. .. .. . .. .. . .. .. . .. .. . .. .. . .. .. . .. .. . ¿ xm

am(m+1)xm +1+⋯amnxn=bm
(2){¿

(3 ) xj ≥ 0( j=1 , n); bi≥ 0 (i=1 , m)

x1 x2xm xm +1 ¿ xn ¿ ¿ A=

[

1 0 . . .. .. 0 a1(m +1) .. . a1 n
0 1 . . .. .. 0 a2(m +1) .. . a2 n

… … … … … … … …

0 0 . . .. .. 1 am(m+1) .. . amn

]

Nhận xét:

Ta thấy bài toán dạng chuẩn là bài toán dạng chính tắc thêm 2 điều kiện:

 Các số hạng tự do không âm: bi≥ 0 (i=1, m) .

 Ma trận các hệ số ràng buộc A chứa 1 ma trận đơn vị cấp m.

Định nghĩa:

1) ẩn cơ bản: Các ẩn ứng với véc tơ cột đơn vị trong ma trận A gọi là ẩn cơ
bản, trên ma trận A ta có x1; x2;… ; xm là các ẩn cơ bản.

- ẩn cơ bản ứng với véc tơ cột đơn vị thứ i gọi là ẩn cơ bản thứ i. Các ẩn còn
lại là không cơ bản.

2) Phương án cơ bản: 1 phương án mà các ẩn không cơ bản đều bằng 0 gọi
là phương án cơ bản.

Nhận xét:

Với bài toán dạng chuẩn ta luôn có phương án cơ bản ban đầu :

</div>
(8)<div class='page_container' data-page=8>

(1) f ( x )=3 x1− x2+x3−3 x4+x5→ min
(2)

{

2 x1+2 x4+x5=20

−3 x1+4 x2−4 x4+x6=0

x1+2 x2+x3+3 x4=28
(3 ) xj≥ 0 ; j=1,6

x1 x2 x3 x4 x5 x6 ¿

A=

[

−3 4 0 − 4 0 12 0 0 2 1 0

1 2 1 3 0 0

]

Ta có x5 là ẩn cơ bản thứ nhất, x6 là ẩn cơ bản thứ hai, x3 là ẩn cơ bản thứ ba

</div>
(9)<div class='page_container' data-page=9>

§3 BIẾN ĐỞI DẠNG CỦA BÀI TOÁN QUY HOẠCH TUYẾN

TÍNH

I. Đưa dạng tổng quát về dạng chính tắc:

1) Nếu gặp ràng buộc dạng:

∑

j=1
n

aijxj≤bi ta cộng thêm vào vế trái 1 ẩn phụ

( Slack variable) không âm xi+1≥ 0 để biến về dạng phương trình:

∑

j=1
n

aijxj+xn+1=bi

2) Nếu gặp ràng buộc dạng:

∑

j=1
n

aijxj≥bi ta cộng thêm vào vế trái 1 ẩn phụ

( Slack variable) không âm xi+1≥ 0 , với hệ số -1 để biến về dạng phương

trình:

∑

j=1
n

aijxj− xn+1=bi

Chú ý: Các ẩn phụ chỉ là những số giúp ta biến bất phương trình thành
phương trình, chứ không đóng vai trò gì về kinh tế, nên nó không ảnh hưởng
đến hàm mục tiêu. Vì vậy hệ số của nó trong hàm mục bằng 0.

3) Nếu gặp ẩn xj≤0 ta thay xj=− tj , tj≥ 0

4) Nếu gặp ẩn xjtu ̀̀ y y'ta thay xj=x'j− x' 'j , x'j, x' 'j≥ 0
Ví dụ:

Đưa bài toán sau về dạng chính tắc:

(1) f ( x )=2 x1− x2+2 x3+x4− 2 x5→ min

(2)

{

x1− 2 x2+x3+2 x4+x5≤7

x2+2 x3+x4≥− 1
2 x3+x4+3 x5≥10

x1+x2− 2 x3+x4=20

⇔

{

x1−2 x2+x3+2 x4+x5≤ 7 (a )

− x2− 2 x3− x4≤1 (b )

2 x3+x4+3 x5≥10 (c )

x1+x2−2 x3+x4=20 (d )
(3 ) x1; x5≥ 0 ; x4≤ 0; x2; x3tu ̀̀ y y

'
GIẢI

 Cộng vào (a) ẩn phụ x6≥ 0 .

 Cộng vào (b) ẩn phụ x7≥ 0 .

 Cộng vào (c) ẩn phụ x8≥ 0 .với hệ số -1

 Thay x4=− t4;t4≥ 0

 Thay x2=x2'− x2' '; x2'≥ 0 x2' '≥ 0

 Thay x3=x3'− x3' '; x3'≥ 0 x3''≥ 0

</div>
(10)<div class='page_container' data-page=10>

(1) f ( x )=2 x1−

(

x2'− x2''

)

− x3

' '

)

+t4+x7=1 (b)
2

(

x3' − x3' '

)

− t4+3 x5− x8=10 (c )

x1+

(

x2'− x2' '

)

−2

(

x3'− x3' '

)

−t4=20 (d )
(3) x1; x5≥ 0 ;t4≥0 ; x2

' ;x

' '; x

'; x

' '; x

6; x7; x8≥ 0

chú ý:

Nếu

0
0
0
0

(

x10, x2❑x2❑x❑3 x3❑t40, x50, x60, x70, x80

)

là phương án tối ưu của bài toán mới

thì

with

0
0
0

(

x10, x20, x30, x40, x50

)

0 x20=x2❑x2❑x30=x❑3 x❑3 , x40=−t40

là phương án tối ưu của
bài toán gốc.

II. Đưa dạng chính tắc về dạng chuẩn:

1) Mô tả phương pháp:

Giả sử bài toán đã có dạng chính tắc: (Gỉa sử bi≥ 0 ,i=1 , m )

(1) f ( x )=

∑

j=1
n

cjxj→ min (max)

(2 )

{

a11x1+¿⋯ +a1 nx❑n=b1

a11x1+¿⋯ +a11x1=b2

⋮ ¿⋮

a11x1+¿⋯ +a11x1=bm
(3 ) xj ≥ 0( j=1 , n)

 Ta thêm vào mỗi phương trình một ẩn giả khộng âm xn+i≥0 với

hệ số 1

 Trong hàm mục tiêu f ( x )→ min , ẩn giả có hệ số M( M>0, M lớn
hơn số nào ần so sánh)

 Trong hàm mục tiêu f ( x )→ max , ẩn giả có hệ số –M

</div>
(11)<div class='page_container' data-page=11>

(1) ¯f (¯x )=

∑

j =1
n

cjxj± M

∑

i=1
m

xn+i→ min (max)
a11x1+¿⋯

xn+1

¿ +a1 nx❑n+ ¿ ¿=b1 a21x1+¿⋯
+a2nxn+xn+2 ¿=b2 ¿ ⋮ ⋮+

⋱ ¿

am 1x1+¿⋯ +amnxn+xn+m=bm
¿

(3 ) xj ≥ 0( j=1 , n+m )

(2)¿

Ta thấy bài toán đã có dạng chuẩn với ẩn cơ bản thứ i là xn+i(i=1 ,m ) là các

ẩn giả.
Ví dụ:

(1) f ( x )=2 x1+x2+x3− x4→ max
(2)

{

x1+5 x2+5 x4=25

− 4 x2− x3+6 x4=18
3 x2+8 x4=28
(3) xj≥ 0 ; j=1,4

A=

[

10 − 4 −1 65 0 5

0 3 0 8

]

Ta thấy còn thiếu vector cột đơn vị thứ 2 và thứ 3 nên phải thêm ẩn giả vào
phương trình thứ 2 và thứ 3. Bài toán đưa về dạng chuẩn.

(1)¯f (¯x )=2 x1+x2+x3− x4− Mx5− Mx6→ max
(2)

{

x1+5 x2+5 x4=25

− 4 x2− x3+6 x4+x5=18
3 x2+8 x4+x6=28
(3) xj≥0 ; j=1,6

A=

[

10 − 4 − 1 6 1 05 0 5 0 0
0 3 0 8 0 1

]

2) Quan hệ giữa bài toán xuất phát và bài toán mở rộng
NHẬN XÉT

a) Nếu x=(x1, x2,… , xn) là phương án của bài toán xuất phát thì

¯x=(x1, x2,. .. , xn, 0, .. . , 0) là phương án của bài toán mở rộng.

b) Nếu x0=

(

x10, x20, … , xn0

)

là phương án tối ưu của bài toán xuất phát thì

x0

</div>
(12)<div class='page_container' data-page=12>

c) Nếu x0

(

x10, x20, … , xn0, 0 . .. , 0

)

là phương án tối ưu của bài toán mở
rộng thì x0=

(

x10, x20, … , xn0

)

là phương án tối ưu của bài toán xuất phát.

d) Nếu bài toán mở rộng có phương án tối ưu trong đó có 1 ẩn giả nhận
giá trị dương thì bài toán xuất phát không có phương án.

BÀI TẬP CHƯƠNG I

Lập mô hình toán học

1) Công ty bao bì dược cần sản xuất 3 loại hộp giấy đựng thuốc B1, Cao sao

vàng và đựng “Quy sâm đại bổ hoàn”.

Để sản xuất ra các hộp này công ty dùng các tấm bìa có kích thước
giống nhau. Mỗi tấm bìa có 5 cách cắt khác nhau

Cách Hộp B1 Hộp cao sao vàng Hộp quy sâm

1 2 0 2

2 0 7 4

3 8 0 3

4 1 6 2

5 9 2 0

Theo kế hoạch số hộp B1 phải có là 1500, số hộp quy sâm là 2000, số hộp

cao sao vàng tối thiểu là 1000. Cần phương án cắt sao cho tổng số tấm
bìa phải dùng là ít nhất. Hãy lập mô hình bài toán.

Xí nghiệp cơ khí An Phú cần cắt 1000 đoạn thép dài 0.55m; 800 đoạn dài
0.8m và 1120 đoạn dài 0.45m làm chuồng gà. Để có các đoạn thép này, xí
nghiệp phải dùng 3 loại thanh thép: loại 1 dài 1.2m; loại 2 dài 1.5m và loại 3
dài 1.8m. Các cách cắt được cho trong bảng dưới

Loại thép Cách cắt 0.55m 0.8m 0.45m Thừa

I: 1.2m 1

2
3
1
2
0

0
0
0
1
0
2
0.2
0.1
0.3

II: 1.5m 1

2
3
4
1
1
0
0
1
0
1
0
0
2
1
3
0.15
0.05
0.25

0.15

III: 1.8m 1

</div>
(13)<div class='page_container' data-page=13>

Nhận dạng và đổi dạng

Trong các bài toán từ 1 đến 5 dưới đây:
1)

(1 ) f ( x ) → min
(2)

{

2 x1+x2+3 x3+4 x5=17

4 x1+2 x3+x4+5 x5=20
(3) xj≥ 0 ( j=1,5)
2)

(1)f(x)→ max
(2)

{

x1+x2− 2 x3+x4+x5=32

x2+x3−2 x4=16

x1+x2−2 x3+x4=32
(3)x1, x3≤ 0 ; x2≥ 0; x4, x5tù̀ y y'

(1 ) f ( x ) → min
(2)

{

2 x1+x2+3 x3+4 x5=17
4 x1+2 x3+x4+5 x5=20

− 2 x1+4 x5+x6=6
(3) xj≥ 0 ( j=1,6)

(1) f ( x )→ max
(2)

{

x1− x2−2 x3≤ 5
x1+2 x2+x3+x4=15

2 x1+x2+3 x3≥ 8
(3) xj≥ 0 ( j=1,4 )

(1) f (x ) → min
(2)

{

x1− 2 x2− 2 x3=−7

x2+2 x3+x4≤ 15
2 x1+3 x3+x4≥ 8
(3) xj≥ 0 ( j=1,4)

a) Những bài toán nào đã có dạng chính tắc.

</div>
(14)<div class='page_container' data-page=14></div>
(15)<div class='page_container' data-page=15>

CHƯƠNG II: PHƯƠNG PHÁP ĐƠN HÌNH

§1 THUẬT TOÁN ĐƠN HÌNH

I. Trường hợp f(x)→ min ( gồm 5 bước)
Bước 1: Lập bảng ban đầu

Hệ
số

Ẩn
cơ
bản

Phương
án

c1¿ c2 ¿cr ¿cm cm +1 … cv … cn

λi
x1¿ x2 ¿xr ¿xm xm+ 1 … xv … xn

c1

c2

¿cr
¿cm

x1

x2

¿xr
¿xm

b1

b2

¿br
¿bm

1¿
¿
0 … 0 … 0 a1(m +1) … a1 v … a1 n 0¿

1 … 0 … 0 a2(m +1) … a2 v … a2 n ¿

¿ ¿ ¿ ¿ ¿ ¿ 0¿ 0 … 1 …

¿a3(m+1)¿…¿arv¿…¿arn¿ ¿ ¿¿ ¿ ¿ ¿ ¿ ¿ ¿ ¿ ¿ ¿0¿ ¿0¿…¿0¿…¿1¿am(m +1)¿…¿amv¿…¿amn¿

λ1

λ2

λr

f ( x ) f0   r m m v n

1  

2
1

Trong đó f0=

∑

i=1
m

cibi∧ Δj=

∑

i=1
m

ciaij−cj

Bước 2: Kiểm tra tính tối ưu

a) Nếu Δj≤0∀ j thì phương án đang xét là tối ưu và giá trị hàm mục

tiêu tương ứng là f ( x )=f0

b) Nếu ∃ Δj>0 mà̀ aij≤ 0 (i=1 , m) thì bài toán không có phương án tối ưu

Nếu cả 2 trường hợp trên không xảy ra thì chuyển sang bước 3

Bước 3: Tìm ẩn đưa vào:

Nếu Δv=max

j Δjthi ̀̀ xv được chọn đưa vào.
Bước 4: Tìm ẩn đưa ra:

λi= bi

aivwith aiv>0
If λr=min

i λithen xrout

Bước 5:Biến đổi bảng(dùng phương pháp khử Gauss-Jordan)

1. Thay xr bằng xv . Các ẩn cơ bản khác và các hệ số tương ứng giữ

nguyên.

2. hàng chuẩn=hàng đưa ra( xr )/ arv .

</div>
(16)<div class='page_container' data-page=16>

4. hàng cuối (mới)= − Δ¿v×

hàng ch̉n+ hàng ći(cũ).

II. Trường hợp f ( x )→ max

Đặt g ( x)=− f ( x ) → min . Vậy ta đã chuyển về bài toán Hàm mục tiêu cực
tiểu và do đó ta hoàn toàn có thể áp dụng kết quả của bài toán min.

Ví dụ:

Giải bài toán QHTT:

(1) f ( x )=2 x1+5 x2+4 x3+x4− x5→ min

(2)

{

x1− 6 x2−2 x4−9 x5=32
2 x2+x3+1

2x4+
3

2x5=30
3 x2+x5≤ 36
(3 ) xj≥ 0 ; j=1,5

→ s tan dard form

(1) f ( x )=2 x1+5 x2+4 x3+x4− x5+0. x6→ min

(2)

{

x1− 6 x2−2 x4−9 x5=32

2 x2+x3+1

2x4+
3

2x5=30
3 x2+x5+x6=36
(3 ) xj≥ 0; j=1,6

A=

[

1 −6 0 −2 − 9 0

0 2 1 1

2
3

2 0

</div>
(17)<div class='page_container' data-page=17>

Bảng đơn hình:

Hệ số Ẩn cơ

bản

Phương
án

2 5 4 1 -5 0

x1 x2 x3 x4 x5 x6

2
4
0

x1

x3

x6

32
30
36

1
0
0

-6
2
3

0
1
0

-2
½
0

-9
3/2

0
0
1

f ( x ) 184 0 -9 0 -3 -7 0

Δj≤0,∀ j ⇒ phương án tối ưu là (x1, x2, x3, x4, x5)=(32 , 0 ,30 , 0,0)

Ví dụ:

(1) f ( x )=6 x1+x2+x3+3 x4+x5−7 x6+7 → min
(2)

{

− x1+x2− x4+x6=15
2 x1− x3+2 x6=−9
4 x1+2 x4+x5−3 x6=2

(3) xj≥ 0 ; j=1,6

→ s tandard form

(1) f ( x )=6 x1+x2+x3+3 x4+x5−7 x6+7 → min
(2)

{

− x1+x2− x4+x6=15

−2 x1+x3−2 x6=9
4 x1+2 x4+x5−3 x6=2

(3) xj≥ 0 ; j=1,6
¯

</div>
(18)<div class='page_container' data-page=18>

Bảng đơn hình:

Hệ số Ẩn cơ

bản

Phương
án

6 1 1 3 1 -7

x1 x2 x3 x4 x5 x6

1
1
1
x2
x3

x5
15
9
2
-1
-2
4
1
0
0
0
1
0
-1
0
2
0
0
1
(1)
-2
-3

f ( x ) 26+7 Δ1

-5
Δ2
0
Δ3
0

Δ4
-2
Δ5
0
Δ6
(3)
-7
1
1
x6
x3
x5
15
39
47
-1
-4
1
1
2
3
0
1
0
-1
-2
-1
0
0
1

1
0
0

f ( x ) -19+7 -2 -3 0 (1) 0 0

Ở phương án cơ bản ban đầu:

max Δj=Δ6=3⇒ x6(in )

arv=1⇒ x2(out )

Ở phương án thứ 2

</div>
(19)<div class='page_container' data-page=19>

Ví dụ:

(1 ) f ( x )=− 2 x1+6 x2+4 x3− 2 x4+3 x5→ max
(2)

{

x1+2 x2+x3=52
4 x2+2 x3+x4=60

3 x2+x5=36
(3) xj≥0 ; j=1,5

→ s tan dard form

(1) g ( x)=− f ( x )=2 x1−6 x2−4 x3+2 x4−3 x5→ min
(2)

{

x1+2 x2+4 x3=52
4 x2+2 x3+x4=60

3 x2+x5=36
(3) xj≥0 ; j=1,5

A=

[

1 2 4 0 00 4 2 1 0
0 3 0 0 1

]

Bảng đơn hình:

Hệ số Ẩn cơ

bản

Phương
án

2 -6 -4 2 -3

x1 x2 x3 x4 x5

2
2
-3
x1
x4
x5
52
60

36
1
0
0
2
4
3
(4)
2
0
0
1
0
0
0
1

g(x) 116 Δ1

0
Δ2
9
Δ3
(16)
Δ4
0
Δ5
0
x3
x4

x5
13
34
36
1/4
-1/2
0
1/2
(3)
3
1
0
0
0
1
0
0
0
1

g ( x) -92 -4 (1) 0 0 0

x3
x2
x5
22/3
34/3
2
1/3
-1/6

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

g ( x) -310/3 -23/6 0 0 -1/3 0

Ở phương án cơ bản ban đầu:

max Δj=Δ3=16⇒ x3(in )
min λi=λ1=524 =13

</div>
(20)<div class='page_container' data-page=20>

Ở phương án thứ 2

max Δj=Δ2=1⇒ x2(in )
min λi=λ2=34

arv=3⇒ x4(out)

Phương án cuối cùng: Δj≤0,∀ j ⇒ ta có phương án tối ưu là:

(x1, x2, x3, x4, x5)=

(

0,
34

3 ,
22

3 ,0,2

)

</div>
(21)<div class='page_container' data-page=21>

§2 THUẬT TOÁN ĐƠN HÌNH MỞ RỘNG

I. Chú ý trong thuật toán đơn hình mở rộng

Nếu gặp bài toán dạng chính tắc chưa phải dạng chuẩn ta dùng ẩn giả để đưa
bài toán về dạng chuẩn.

1. Nếu bài toán mở rộng không có phương án tối ưu thì bài toán xuất
phát cũng không có phương án tối ưu.

2. Nếu bài toán mở rộng có phương án tối ưu mà các ẩn giả đều bằng 0,
thì bỏ phần ẩn giả đi ta còn phương án tối ưu của bài toán xuất phát.
3. Nếu bài toán mở rộng có phương án tối ưu mà trong đó còn ít nhất 1

ẩn giả > 0, thì bài toán xuất phát không có phương án tối ưu.
Ví dụ:

5 x

(1) f ( x )=x1+2 x2+x❑5 → min

(2)

{

−3 x3− 9 x4=0

x2−7 x3−5 x4− 2 x5=5

x1−13x2+23x3+43 x4+51x5=32

, A=

[

0 0 − 3 − 9 0
0 1 − 7 − 5 − 2

1 −1
3

2
3

4
3

1
5

]

(3 ) xj≥ 0 ; j=1,5

→ s tan dard form

5 x

(1) ¯f ( ¯x)=x1+2 x2+x❑5+Mx6+Mx7→ min

(2)

{

−3 x3− 9 x4+x6=0

x2−7 x3−5 x4−2 x5+x7=5

x1−1
3x2+

2
3x3+

4
3 x4+

1
3x5=

2
3
(3 ) xj≥ 0 ; j=1,7

A=

[

0 0 −3 −9 0

0 1 −7 −5 −2

1 −1
3

2
3

4
3

1
5

</div>
(22)<div class='page_container' data-page=22>

Bảng đơn hình:

Hệ số Ẩn cơ

bản

Phương
án

1 2 0 1 -5

x1 x2 x3 x4 x5

M
M

1
x6
x7
x1
0
5
2/3
0
0
1
0
(1)
-1/3
-3
-7
2/3
-9
-5
4/3
0
-2
1/3

f ( x ) 5M+2/3

Δ1
0
Δ2
(-7/3+M)
Δ3

2/3-10M
Δ4
1/3-14M
Δ5
16/3-2M
x6
x2
x1
0
5
7/3
0
0
1
0
1
0
-3
-7
-5/3
-9
-5
-1/3
0
-2
-1/3

f ( x ) 37/3 0 0 -47/3-3M -34/3-9M 2/3

Ở phương án cơ bản ban đầu:

max Δj=Δ2=−7

3+M⇒ x2( in )
min λi=λ2=

5
1

arv=1⇒ x7(out )

Ở phương án thứ 2

</div>
(23)<div class='page_container' data-page=23>

Ví dụ:

(1) f ( x )=−16 x1+7 x2+9 x3→ min
(2)

{

−

2
3x1−

3x2+x3=
1
3

−5 x1+5 x2=7

⇒

[

−23 −
1
3 1

− 5 5 0

]

(3) xj≥ 0 ; j=1,3

→ s tan dard form

(1)¯f (¯x )=− 16 x1+7 x2+9 x3+Mx4→ min
(2)

{

−

2
3x1−

3x2+x3=
1
3

−5 x1+5 x2+x4=7
(3) xj≥ 0 ; j=1,4
¯

A=

[

−

2
3 −

1
3 1

− 5 5 0

0
1

]

Bảng đơn hình:

Hệ số Ẩn cơ

bản

Phương
án

-16 7 9

x1 x2 x3

9
M

x3

x4 1/37 -2/3-5 -1/3(5) 10

f ( x ) 7M+3

Δ1

10-5M

Δ2

(-10+5M)

Δ3

x3

x2 12/157/5 -1-1 01 10

f ( x ) 17 0 0 0

Ở phương án cơ bản ban đầu:

max Δj=Δ2=− 10+5 M⇒ x2(in )
min λi=λ2=7

arv=5⇒ x4(out)

Phương án cuối cùng: Δj≤0,∀ j ⇒ ta có phương án tối ưu là:

(x1, x2, x3)=

(

0,
7
5,

12
15

)

Giá trị của phương án: f0=17

</div>
(24)<div class='page_container' data-page=24>

(1) f ( x )=2 x1+4 x2− 2 x3→ min
(2 )

{

x1−2 x2+x3=27
2 x1+x2+2 x3=50

x1− x2− x3≤ 18

(3) xj≥ 0 ; j=1,3

→ stan dard form

(1)¯f (¯x )=2 x1+4 x2− 2 x3+0 . x4→ min
(2)

{

x1−2 x2+x3=27
2 x1+x2+2 x3=50

x1− x2− x3+x4=18
(3) xj≥ 0 ; j=1,4

A=

[

1 − 22 1 12 00
1 − 1 −1 1

]

→ stan dard form

(1)¯f (¯x )=2 x1+4 x2− 2 x3+0 . x4+Mx5+Mx6→ min
(2)

{

x1−2 x2+x3+x5=27
2 x1+x2+2 x3+x6=50

x1− x2− x3+x4=18
(3) xj≥ 0 ; j=1,6
¯

A=

[

1 −22 1 12 00
1 −1 −1 1

</div>
(25)<div class='page_container' data-page=25>

Bảng đơn hình:

Hệ số Ẩn cơ

bản

Phương
án

1 2 0 1

x1 x2 x3 x4

M
M
0

x5

x6

x4

27
50
18

1
2
1

-2
1
-1

1
(2)

-1

0
0

f ( x ) 77M

Δ1

-2+3M

Δ2

-4-M

Δ3

(2+3M)

Δ4

x5

x3

x4

2
25
43

0
1
2

-5/2
1/2
-1/2

0
1
0

0
0
1

f ( x ) -50+2M -4 -5-5M/2 0 0

Ở phương án cơ bản ban đầu:

max Δj=Δ3=2+3 M⇒ x3( in )
min λi=λ2=25

arv=2⇒ x6(out )

Ở phương án thứ 2

</div>
(26)<div class='page_container' data-page=26>

BÀI TẬP
Bài 1

(1) f ( x )=2 x1− x2+2 x3→ min
(2)

{

x1+4 x3=7

x2+x3=10

⇒ A=

[

1 0 4

0 1 1

]

(3 ) xj≥ 0 ; j=1,3

→ s tan dard form

Bảng đơn hình:

Hệ số Ẩn cơ

bản

Phương
án

2 -1 2

x1 x2 x3

2
-1

x1

x2 107 10 01 (4)1

f ( x ) 4

Δ1

Δ2

Δ3

(5)

x3

x2 33/47/4 -1/41/4 01 10

f ( x ) -19/4 -5/4 0 0

Phương án cuối cùng: Δj≤0,∀ j ⇒ ta có phương án tối ưu là:

(x1, x2, x3)=

(

0,
33

4 ,
7
4

)

Giá trị của phương án: f0=−19
4

</div>
(27)<div class='page_container' data-page=27>

(1) f ( x )=4 x1+x2−2 x3→ max
(2)

{

x2+x3=8

x1− x2=5

⇒ A=

[

0 1 1

1 −1 0

]

(3) xj≥0 ; j=1,3

→ s tan dard form

(1) g ( x )=− f ( x )=− 4 x1− x2+2 x3→ min

Bảng đơn hình:

Hệ số Ẩn cơ

bản

Phương
án

-4 -1 2

x1 x2 x3

2
-4

x3

x1 85 01 (1)-1 10

g(x) -4

Δ1

Δ2

(7)

Δ3

x2

x1 138 01 10 11

g(x) -60 0 0 -7

Phương án cuối cùng: Δj≤0,∀ j ⇒ ta có phương án tối ưu là:

(x1, x2, x3)=(13 , 8,0)

Giá trị của phương án: f0=− g0=60

</div>
(28)<div class='page_container' data-page=28>

(1) f ( x )=x1−2 x2+x3→ min
(2)

{

x1+2 x2+x3≤12

2 x1+x2− x3≤ 10
(3) xj≥0 ; j=1,3

→ s tan dard form

(1)¯f (¯x )=x1− 2 x2+x3+0 x4+0 x5→ min
(2)

{

x1+2 x2+x3+x4=12

2 x1+x2− x3+x5=10
(3) xj≥0 ; j=1,5
¯

A=

[

1 2 1 1 0

2 1 −1 0 1

]

Bảng đơn hình:
Hệ số Ẩn cơ

bản

Phương
án

1 -2 1 0 0

x1 x2 x3 x4 x5

0
0

x4

x5 1210 12 21 -11 10 01

f(x) 0

Δ1

-1

Δ2

Δ3

-1

Δ4

Δ5

x2

x5 46 1/23/2 10 -3/21/2 -1/21/2 01

f(x) -12 -2 0 -2 -1 0

Phương án cuối cùng: Δj≤0,∀ j ⇒ ta có phương án tối ưu là:

(x1, x2, x3)=(0,6,0)

</div>
(29)<div class='page_container' data-page=29>

Bài 4

(1) f ( x)=x1+2 x2− x3→ max
(2)

{

− x1+2 x2+3 x3≤10

x1+3 x2+x3≥5
(3 ) xj≥ 0; j=1,3

→ s tan dard form

(1) g ( x )=− f (x )=− x1− 2 x2+x3+0 x4+0 x5→ min
(2)

{

− x1+2 x2+3 x3+x4=10

x1+3 x2+x3− x5=5

(3 ) xj≥ 0 ; j=1,5 ,¿A=

[

−1 2 3 1 0

1 3 1 0 − 1

]

→ s tan dard form

(1) g ( x )=− f ( x )=− x1−2 x2+x3+0 x4+0 x5+Mx6→ min
(2)

{

− x1+2 x2+3 x3+x4=10

x1+3 x2+x3− x5+x6=5
(3 ) xj≥ 0 ; j=1,6¿A=

[

−1 2 3 1 0

</div>
(30)<div class='page_container' data-page=30>

Bảng đơn hình:
Hệ số Ẩn cơ

bản

Phương
án

-1 -2 1 0 0

x1 x2 x3 x4 x5

0
M

x4

x6 105 -11 (3)2 31 10 -10

g ( x) 5M

Δ1

M+1

Δ2

(3M+2)

Δ3

M-1

Δ4

Δ5

-M

x4

x2 5/320/3 -5/31/3 01 7/31/3 10 (2/3)-1/3

g ( x) -10/3 1/3 0 -5/3 0 (2/3)

x5

x2 105 -5/2-1/2 01 7/23/2 3/21/2 10

g ( x) -10 2 0 -4 -1 0

Phương án cuối cùng: ∃ Δ1=2>0, but ai 1 ̀́=

{

−

5
2;−

}

(0)⇒ Bài toán xuất phát

không có phương án tối ưu.
Bài 5

(1) f (x )=3 x1+x2−3 x3→ max
(2)

{

x1+2 x2− x3=2

− 10 x2+5 x3=5

− 3 x2+2 x3=4

⇒ A=

[

10 − 102 − 15
0 − 3 2

]

(3) xj≥0 ; j=1,3

→ s tan dard form

(1) g ( x )=− f ( x )=−3 x1− x2+3 x3+Mx4+Mx5→ min
(2)

{

x1+2 x2− x3=2

− 10 x2+5 x3+x4=5

− 3 x2+2 x3+x5=4
(3 ) xj≥ 0; j=1,5⇒ ¯A=

[

1 2 −1

0 −10 5

0 −3 2

0 0
1 0
0 1

]

Bảng đơn hình:
Hệ số Ẩn cơ

bản

Phương
án

-3 -1 3

</div>
(31)<div class='page_container' data-page=31>

-3
M
M

x1

x4

x5

2
5
4

1
0
0

2
-10

-3

-1
(5)

g ( x) 9M-6

Δ1

Δ2

-13M-5

Δ3

(7M)

x1

x3

x5

3
1
2

1
0
0

0
-2
(1)

0
1
0

g ( x) 2M-6 0 (M-5) 0

x1

x3

x2

3
5
2

1
0
0

0
0
1

0
1
0

g ( x) 4 0 0 0

Phương án cuối cùng: Δj≤0,∀ j ⇒ ta có phương án tối ưu là:

(x1, x2, x3)=(3,2,5) , Giá trị của phương án: f0=− g ( x )=− 4

</div>
(32)<div class='page_container' data-page=32>

(1) f ( x )=2 x1+x2− x3→ min

(2)

{

− 4 x1− x2+2 x3− x4=12

− 2 x1+2 x2− x3+x5=10

x1−2 x2−1

2x3=23

⇒ A=

[

− 4 − 1 2 −1 0

−2 2 −1 0 1

1 − 2 −1

2 0 0

]

(3 ) xj≥ 0 ; j=1,5

→ s tan dard form

(1) f ( x )=2 x1+x2− x3+Mx6+Mx7→ min

(2)

{

− 4 x1− x2+2 x3− x4+x6=12

− 2 x1+2 x2− x3+x5=10

x1−2 x2−1

2x3+x7=23
(3) xj≥ 0 ; j=1,7⇒ ¯A=

[

− 4 −1 2 − 1 0

− 2 2 −1 0 1

1 −2 −1

2 0 0

1 0
0 0
0 1

]

Bảng đơn hình:

Hệ
số
Ẩn cơ
bản
Phương

án

2 1 -1 0 0

x1 x2 x3 x4 x5

M
0
M
x6
x5
x7
12
10
23
-4
-2
1
-1
2
-2
(2)
-1
-1/2
-1
0
0
1
0
0

f(x) 35M

Δ1
-3M-2
Δ2
-3M-1
Δ3
(3M/2
+1)
Δ4
-M
Δ5
0
x3
x5
x7
6
16
26
-2
-4
0
-1/2
3/2
-9/4
1
0
0
-1/2

-1/2
-1/4
0
1
0

f ( x ) 26M-6 0 (-9M/4-1/2) 0 -M/4+1/2 0

Phương án cuối cùng: Δj≤0,∀ j but x7=26>0⇒ Bài toán gốc không có

</div>
(33)<div class='page_container' data-page=33>

(1) f ( x )=x4+x5+20 → max
(2)

{

x2+2 x4+3 x5=7

x3− x4− 3 x5=2

x1+x4+x5=2

⇒ A=

[

0 1 00 0 1 − 1 −32 3

1 0 0 1 1

]

(3) xj≥ 0 ; j=1,5

→ stan dard form

(1) g ( x )=− f ( x )=− x4− x5−20 → min
(2)

{

x2+2 x4+3 x5=7

x3− x4−3 x5=2

x1+x4+x5=2
(3) xj≥ 0 ; j=1,5

Bảng đơn hình:
Hệ
số
Ẩn cơ
bản
Phương
án

0 0 0 -1 -1

x1 x2 x3 x4 x5

0
0
0
x2
x3
x1
7
2
2
0
0

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

g(x) -20

Δ1
0
Δ2
0
Δ3
0
Δ4
(1)
Δ5
1
x2
x3
x4
3

4
2
-2
1
1
1
0
0
0
1
0
0
0
1
1
-2
1

g(x) -22 -1 0 0 0 0

Phương án cuối cùng: Δj≤0,∀ j ⇒ ta có phương án tối ưu là:

(x1, x2, x3, x4, x5)=(0,3,4,2,0) , Giá trị của phương án: f0=− g0=22

</div>
(34)<div class='page_container' data-page=34>

(1) f ( x )=x1+2 x2− x3→ max
(2 )

{

4 x1+4 x2+2 x3≥ −6

x1+x2+2 x3≥6

2 x1− x2+2 x3=4

⇒

{

− 4 x1− 4 x2− 2 x3≤ 6

x1+x2+2 x3≥6
2 x1− x2+2 x3=4
(3 ) xj≥ 0 ; j=1,3

→ s tan dard form

(1 ) g ( x )=− f ( x )=− x1− 2 x2+x3+0 x4+0 x5→ min
(2)

{

− 4 x1−4 x2−2 x3+x4=6

x1+x2+2 x3− x5=6
2 x1− x2+2 x3=4

⇒ A=

[

− 4 − 4 −2 11 1 2 0 −10
2 − 1 2 0 0

]

→ s tan dard form

(1 ) g ( x )=− f ( x)=− x1− 2 x2+x3+0 x4+0 x5+Mx6+Mx7→ min
(2)

{

− 4 x1− 4 x2− 2 x3+x4=6

x1+x2+2 x3− x5+x6=6
2 x1− x2+2 x3+x7=4

⇒ A=

[

−4 − 4 − 2 11 1 2 0 −10

2 −1 2 0 0

0 0
1 0
0 1

]

(3 ) xj≥ 0; j=1,7

Hệ
số
Ẩn cơ
bản
Phương
án

-1 -2 1 0 0

x1 x2 x3 x4 x5

0
M
M
x4
x6
x7
6

6
4
-4
1
2
-4
1
-1
-2
2
(2)
1
0
0
0
-1
0

g(x) 10M

Δ1
3M+1
Δ2
-2
Δ3
(4M-1)
Δ4
0
Δ5
-M

x4
x6
x3
10
2
2
-2
-1
1
-5
(2)
-1/2
0
0
1
1
0
0
0
-1
0

g(x) 2M+2 -M+2 (2M+3/2) 0 0 -M

x4
x2
x3
15
1
5/2

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

g(x) 1/2 11/4 0 0 0 3/4

Phương án cuối cùng: Δ5=3

4>0, but ai 5≤ 0⇒ Bài toán xuất phát khôngcó
phương án tối ưu.

</div>
(35)<div class='page_container' data-page=35>

(1 ) f ( x )=x1+2 x2+3 x3+x4→ max
(2)

{

− x1+2 x2−3 x3=−15
2 x1+x2+5 x3=20

x1+2 x2+x3+x4=10

⇒

{

x1− 2 x2+3 x3=15
2 x1+x2+5 x3=20

x1+2 x2+x3+x4=10

⇒

[

1 − 2 3 02 1 5 0
1 2 1 1

]

(3) xj≥ 0 ; j=1,4

→ s tandard form

(1 ) g ( x )=− f ( x)=− x1− 2 x2− 3 x3− x4+Mx5+Mx6→ min
(2)

{

x1− 2 x2+3 x3+x5=15
2 x1+x2+5 x3+x6=20

x1+2 x2+x3+x4=10

⇒ A=

[

1 − 2 3 02 1 5 0

1 2 1 1

1 0
0 1
0 0

]

Bảng đơn hình:

Hệ
số
Ẩn cơ
bản
Phương
án

-1 -2 -3 -1

x1 x2 x3 x4

M
M
-1
x5
x6
x4
15
20
10
1
2
1
-2
1
2
3
(5)
1

0
0
1

g(x) 35M-10

Δ1
3M
Δ2
-M
Δ3
(8M+2)
Δ4
0
x5
x3
x4
3
4
6
-1/5
2/5
3/5
-13/5
1/5
9/5
0
1
0
0

0
1

g(x) 3M-18 -M/5-4/5 -13M/5-2/5 0 0

Phương án cuối cùng: Δj≤0,∀ j but x5=3>0⇒ Bài toán gốc không có

</div>
(36)<div class='page_container' data-page=36>

Bài 10

(1) f ( x )=−2 x1+x2+x4→ min
(2)

{

x1+x2− x3≤ 15

x1+x2+x3+x4=27
2 x1− x2− x3≤ 18

(3) xj≥ 0 ; j=1,4

→ s tan dard form

(1) f ( x )=− 2 x1+x2+x4+0 x5+0 x6→ min
(2)

{

x1+x2− x3+x5=15

x1+x2+x3+x4=27
2 x1− x2− x3+x6=18

⇒

[

11 11 −1 0 1 01 1 0 0

2 −1 −1 0 0 1

]

(3) xj≥0 ; j=1,6

Bảng đơn hình:
Hệ
số
Ẩn cơ
bản
Phương
án

-2 1 0 1 0 0

x1 x2 x3 x4 x5 x6

0
1
0
x5
x4
x6
15
27
18
1
1
(2)
1
1
-1

-1
1
-1
0
1
0
1
0
0
0
0
1

f(x) 27

Δ1
(3)
Δ2
0
Δ3
1
Δ4
0
Δ5
0
Δ6
0
x5
x4
x1

6
18
9
0
0
1
3/2
3/2
-1/2
-1/2
(3/2)
-1/2
0
1
0
1
0
0
-1/2
-1/2
1/2

f(x) 0 0 3/2 (5/2) 0 0 -3/2

x5
x3
x1
12
12
15

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

f(x) -30 0 -1 0 -5/3 0 -2/3

Phương án cuối cùng: Δj≤0,∀ j ⇒ ta có phương án tối ưu là:

(x1, x2, x3, x4)=(15 , 0 ,12 , 0) , Giá trị của phương án: f0=−30

</div>
(37)<div class='page_container' data-page=37>

(1) f ( x )=2 x1+4 x2+x3+x4→ max
(2)

{

x1+3 x2+x4≤1

− 5 x2−2 x4≤3
2 x2+8 x3+2 x4≤ 6
(3 ) xj≥ 0 ; j=1,4

→ s tan dard form

(1) g ( x )=− f ( x )=− 2 x1− 4 x2− x3− x4+0 x5+0 x6+0 x7→ min
(2)

{

x1+3 x2+x4+x5=1

− 5 x2−2 x4+x6=3
2 x2+8 x3+2 x4+x7=6

⇒

[

10 −5 0 − 2 0 1 03 0 1 1 0 0
0 2 8 2 0 0 1

]

(3) xj≥ 0 ; j=1,7

Bảng đơn hình:
Hệ
số
Ẩn cơ
bản
Phương
án

-2 -4 -1 -1 0 0 0

x1 x2 x3 x4 x5 x6 x7

-2
0
0
x1
x6
x7
1
3
6
1
0
0
3
-5
2
0
0
(8)
1
-2
2
1
0
0
0
1
0
0
0
1

g(x) -2

Δ1
0
Δ2
-2
Δ3
(1)
Δ4
-1
Δ5
-2
Δ6
0
Δ7
0
x1
x6
x3
1
3
3/4
1
0
0
3
-5
1/4
0

0
1
1
-2
1/4
1
0
0
0
1
0
0
0
1/8

g(x) -11/4 0 -9/4 0 -5/4 -2 0 -1/8

Phương án cuối cùng: Δj≤0,∀ j ⇒ ta có phương án tối ưu là:

(x1, x2, x3, x4)=

(

1,0,34, 0

)

, Giá trị của phương án: f0=− g0=
11

</div>
(38)<div class='page_container' data-page=38>

Bài 12

(1) f ( x )=−10 x1−3 x2+2 x3+2 x4−2 x5− 4 x6+5→ min
(2)

{

x1+x2− x3+x5+2 x6=2
2 x1+x3− x4+2 x5+x6=3
4 x1+6 x3−6 x4+3 x5+4 x6=18

(3) xj≥ 0 ; j=1,6

→ stan dard form
⇒

[

1 1 − 12 0 1 −1 2 10 1 2

4 0 6 −6 3 4

]

(1) f ( x)=−10 x1−3 x2+2 x3+2 x4− 2 x5− 4 x6+Mx7+Mx8+5→ min
(2)

{

x1+x2− x3+x5+2 x6=2
2 x1+x3− x4+2 x5+x6+x7=3
4 x1+6 x3−6 x4+3 x5+4 x6+x8=18

⇒

[

1 1 − 12 0 1 − 1 2 10 1 2

4 0 6 −6 3 4

0 0
1 0
0 1

]

(3) xj≥ 0 ; j=1,8

Bảng đơn hình:

Hệ
số
Ẩn cơ
bản

Phương
án

-10 -3 2 2 -2 -4

x1 x2 x3 x4 x5 x6

-3
M
M
x2
x7
x8
2
3
18
1
2
4
1
0
0
-1
(1)
6
0
-1
-6
1
2

3
2
1
4

g(x) 21M-1

Δ1
6M+7
Δ2
0
Δ3
(7M+1)
Δ4
-7M-2
Δ5
5M-1
Δ6
5M-2
x2
x3
x8
5
3
0
3
2
-8
1
0

0
0
1
0
-1
-1
0
3
2
-9
3
1
-2

g(x) -4 -8M+5 0 0 -1 -9M-3 -2M-3

Phương án cuối cùng: Δj≤0,∀ j ⇒ ta có phương án tối ưu là:

</div>
(39)<div class='page_container' data-page=39>

Bài 13

Giải bài toán QHTT:

(1) f ( x )=10 x1+3 x2− 2 x3− x4+2 x5+4 x6+2→ max
(2)

{

x1+x2− x3+x5+2 x6=2
2 x1+x3− x4+2 x5+x6=3
4 x1+6 x3−6 x4+3 x5+4 x6=18

(3 ) xj≥ 0 ; j=1,6

Bài 14

Giải bài toán QHTT:

(1) f ( x )=2 x1+x2− x3+x4→ min
(2)

{

x1+x2− x3− 2 x4=2

− x2+3 x3+7 x4≤2
2 x3+3 x4≤5

(3 ) xj≥ 0 ; j=1,4

ĐS: x=(x1, x2, x3, x4)=(0,2,0,0)

Bài 15

Giải bài toán QHTT:

(1) f ( x )=2 x1−3 x2− 4 x3− x4→ min
(2)

{

3 x1+x2+2 x3+4 x4=2
2 x1− x3+3 x4≥ 1

x1− 4 x3+2 x4≤ 4

(3) xj≥ 0 ; j=1,4
ĐS: x=(x1, x2, x3, x4)=

(

0,2

3, 0,
1
3

)

Bài 16

Giải bài toán QHTT:

(1) f ( x )=3 x1+2 x2+x3→ min
(2)

{

− x1+x2+2 x3=6

</div>
(40)<div class='page_container' data-page=40>

Bài 17

Giải bài toán QHTT:

(1) f ( x )=4 x1−3 x2−2 x3− x4→ min
(2)

{

6 x1−2 x2+3 x3+x4=57

x1+3 x2+2 x3≤ 16
2 x1+x2− 4 x3=12
(3) xj≥ 0 ; j=1,4
Bài 18

Giải bài toán QHTT:

(1) f ( x )=2 x1−2 x2− x3+x4→ min
(2 )

{

3 x1+2 x2+4 x3+x4=8
2 x1− 3 x2+x3≥ −5

x1+x2− x3≤ 12
(3) xj≥ 0 ; j=1,4
ĐS: x=(x1, x2, x3, x4)=(0,2,1,0)

Bài 19

Giải bài toán QHTT:

(1) f ( x )=2 x1−10 x2+4 x3− 6 x4→ max
(2)

{

3 x1− x2+2 x4≤16

x1+2 x2+x3− 2 x4≥ − 4

x2+3 x3− x4≥ 0
(3 ) xj≥ 0 ; j=1,4
ĐS: no PATU

Bài 20

Giải bài toán QHTT:

(1) f ( x )=− x1−2 x2+x3→ min

(2 )

{

− x1+4 x2− 2 x3≤6

x1+x2+2 x3≥6
2 x1− x2+2 x3=4
(3 ) xj≥ 0 ; j=1,3

ĐS: x=(x1, x2, x3)=

(

14
5 ,

12
5 ,

</div>
(41)<div class='page_container' data-page=41>

CHƯƠNG III: BÀI TOÁN ĐỚI NGẪU

§1 KHÁI NIỆM

I. Bài toán đối ngẫu( D) của bài toán gốc ( P)dạng chính tắc:

(P)

(1) f ( x )=c1x1+c2x2+c3x3→ min
(2)

{

a11x1+a12x2+a13x3=b1

a21x1+a22x2+a23x3=b2

⇒

(3) xj ≥0( j =1,3)

A=

[

a11 a12 a13

a21 a22 a23

]

⇒ AT

[

a11 a21
a12 a22
a13 a23

]

(D)

(1) g ( y )=b1y1+b2y2→ max
¿

a11y1+a21y2≤ c1 ¿a12y1+a22y2≤ c2 ¿a13y1+a 3 y2≤c3 ¿
¿

¿
(2)¿

Nhận xét:

1. hàm mục tiêu Pf(x)→ min thì hàm mục tiêu của Dg(y)→ max và

ngược lại.

2. số ẩn của bài toán này là số ràng buộc của bài toán kia và ngược lại.

3. các hệ số cibi ở 2 bài toán đổi ngược cho nhau.

4. ma trận các hệ số ràng buộc ở 2 bài toán là chuyển vị của nhau.

II. Quy tắc lập bài toán đối ngẫu( Dual problem)

Bài toán P(D) Bài toán D(P)

f ( x )=

∑

j=1
n

cjx → min g ( y )=

∑

i=1
m

biy → max

Ràng buộc thứ i:

∑

j=1
n

aijxj

[

bi
bi
bi

]

Cùng chiều

Ẩn thứ i: yi

[

0
0
tu ̀̀ y y'

]

Cùng chiều
Ẩn thứ j: xj

[

0
0
tu ̀̀ y y'

]

Ngược chiều

Ràng buộc thứ j:

∑

i=1
m

aijyi

[

cj
cj
cj

]

</div>
(42)<div class='page_container' data-page=42>

(1) f (x )=2 x1+3 x2− x3+x4→ max
(2)

{

2 x1− x2− x3+x4≤ 5 (1 )

x1+x2+2 x3+x4=7 (2)
5 x1+x2+3 x3+x4≥ 20 (3 )
(3) x1, x2≥ 0 , x3≤ 0 , x4tù̀ y y'

A=

[

2 − 1 −1 11 1 2 1

5 1 3 1

]

⇒ AT

[

2 1 5

−1 1 1
−1 2 3

1 1 1

]

(D)

(1) g ( y )=5 y1+7 y2+20 y3→ min

(2)

{

2 y1+1 y2+5 y3≥2

− y1+y2+y3≥ 3

− y1+2 y2+3 y3≤− 1

y1+y2+y3=1
(3 ) y1≥ 0 , y2tu ̀̀ y y

'

</div>
(43)<div class='page_container' data-page=43>

Ví dụ: Tìm bài toán đối ngẫu của bài toán

(1) f ( x )=5 x1− x2+2 x3+3 x4−6 x → min

(2)

{

3 x1− x2+2 x3+3 x4+4 x=80

x1+x2+x3+x4+x ≥− 10
3 x1−2 x2−2 x3− x4+x ≤ 30

x1+x3≤ 6

(3) x1≤ 0 , x2, x3≥0 , x4, x5tù̀ y y

'

A=

[

3 − 1 2 3 4

1 1 1 1 1

3 − 2 −2 −1 1

1 0 1 0 0

]

⇒ AT

[

3 1 3 1

−1 1 −2 0

2 1 −2 1
3 1 −1 0
4 1 1 0

]

( D)

(1) g ( y )=80 y1−10 y2+30 y3+6 y4→ max

(2)

{

3 y1+y2+3 y3+y4≥ 5

− y1+y2− 2 y3≤− 1
2 y1+y2−2 y3+y4≤3

</div>
(44)<div class='page_container' data-page=44>

§2 QUAN HỆ GIỮA BÀI TOÁN GỐC VÀ BÀI TOÁN ĐỐI

NGẪU

I. Định lý đối ngẫu:

1) Định lý 1: Đối với cặp bài toán đối ngẫu P&D chỉ xảy ra 1 trong các

trường hợp sau:

1. cả 2 đều không có phương án.

2. cả 2 đều có phương án, lúc đó cả 2 có cùng phương án tối ưu và giá trị
2 hàm mục tiêu đối với phương án tối ưu bằng nhau.

3. điều kiện cần và đủ để 2 phương án

¿
¿

of D ¿

of P ¿∧ y0¿

x0

Tối ưu là:

f(x0)=g(y0)

2) Định lý 2: ( độ lệch bù yếu):
Điều kiện cần và đủ để 2 phương án

¿
¿
of D ¿

of P ¿∧ y0¿

x0¿

Tối ưu là:

{

x0j

(

∑

i=1
m

aijyi0− cj

)

=0 ( j=1 , n)

yi0

(

∑

j=1
n

aijx0j− bj

)

=0 (i=1 , m)

II. Tìm nghiệm của bài toán gốc qua nghiệm của bài toán đối ngẫu

Giả sử bài toán đối ngẫu có phương án tối ưu:

y0=

(

y1
0

, y2
0

, … , ym

)

Thứ 1: nếu có yi

>0⇒

∑

j

aijxj=bi
Thứ 2: Thay y0=

(

y1

, y2
0

, … , ym

)

vào các biểu thức

∑

i=1
m

aijyi0−cj (j=1, n)

nếu với chỉ số j nào đó biểu thức này khác 0 thì xj=0

ví dụ:

cho bài toán gốc:

(1) f ( x )=2 x1+5 x2+4 x3+x❑4−5 x5→ min

x1−6 x2− 2 x❑

4−9 x5=32

(2)

{

❑4+¿3

2x5=30
2 x2+x3+1

</div>
(45)<div class='page_container' data-page=45>

Bài toán đối ngẫu là:

(1) g ( y )=32 y1+30 y2+36 y3→ max

(2)

{

y1≤2

− 6 y1+2 y2+3 y3≤ 5

y❑2≤ 4

− 2 y1+
1
2y21

−9 y1+
3

2 y2+y3− 5
(3) y1, y2tu ̀̀ y y

', y

Ta đã biết kết quả bài toán gốc:

phương án tối ưu: x0=(32 , 0 ,30 , 0,0) with f(x0)=184 Bây giờ ta tìm phương

án tối ưu của bài toán đối ngẫu:
thứ 1:

x10=32>⇒ y1=2

x30=30>⇒ y 2=4

Thứ 2: thay x0=(32 , 0 ,30 , 0,0) vào biểu thức 3 x

2+x5− 36<0⇒ y3=0

Vậy phương án tối ưu là y0=(2,4,0 )∧ g(y0)=184

Ví dụ:

Cho bài toán gốc:

(1) f ( x )=52 x1+60 x2+36 x3→ min

(2)

{

x1≥ −2

2 x1+4 x2+3 x3≥ 6

4 x1+2 x2≥ 4

x2≥ −2

x3≥ 3

(3 ) xjtu ̀̀ y y
'

( j=1,3 )

⇒ A=

[

1 0 0
2 4 3
4 2 0
0 1 0
0 0 1

]

⇒ AT

[

</div>
(46)<div class='page_container' data-page=46>

Bài toán đối ngẫu là:

(1) g ( y )=−2 y1+6 y2+4 y3− 2 y4+3 y5→ max
(2)

{

y1+2 y2+4 y3=52
4 y2+2 y3+y4=60

3 y2+y5=36
(3) yi≥ 0 (i=1,5)
Kết quả của bài toán đối ngẫu:

y0

(

0,34
3 ,

3 , 0,2

)

, g(y

)=310
3

Bây giờ ta tìm kết quả của bài toán gốc:
Thứ 1:

y20
=34

3 >0⇒ 2 x1+4 x2+3 x3=6

y30
=22

3 >0⇒ 4 x1+2 x2=4¿⇒

{

2 x1+4 x2+3 x3=6
4 x1+2 x2=4

x3=3

⇔

{

x1=11
6

x2=−5
3

x3=3

y50=2>0⇒ x3=3

Vậy phương án tối ưu của bài toán gốc: x0

=(x1, x2, x3)=

(

11
6 , −

5
3,3

)

BÀI TẬP:
1)

(1) f ( x )=2 x1+4 x2+x3+x❑4−5 x5→ max
(2)

{

x1+3 x2+x❑4≤ 1

−5 x2− 2 x❑43

x2+4 x3+x43
(3) xj≥0 ( j=1,4 )

a) Tìm BTĐN của bài toán trên.

</div>
(47)<div class='page_container' data-page=47>

(1) f ( x )=27 x1+50 x2+18 x3→ max
(2)

{

x1+2 x2+x❑

3≤ 2

− 2 x1+x2− x34

x1+2 x2− x3−2

(3 ) x1, x2tu ̀̀ y y', x30

c) Tìm BTĐN của bài toán trên.

d) Giải BTĐN và suy ra kết quả cho BT gốc.
3)

(1) f ( x )=−2 x1+x2+x❑

4→ min

(2)

{

x1+x2− x❑3≤15

x1+x2+x❑

3+x❑4=27

2 x1− x2− x318
(3) xj≥0 ( j=1,4 )

e) Tìm BTĐN của bài toán trên.

f) Giải BT gốc và suy ra kết quả cho BTĐN.
4)

(1) f ( x )=2 x1+3 x2+3 x3→ max
(2)

{

x1+x2+x❑3≤ 12

x1+x2+2 x❑315

x1+2 x2+2 x320
(3 ) xj0 ( j=1,3)

g) Tìm BTĐN của bài toán trên.

h) Giải BT gốc và suy ra kết quả cho BTĐN.

</div>
(48)<div class='page_container' data-page=48>

(1) f ( x )=2 x1+4 x2+x3+x❑

4→ max

(2)

{

x1+3 x2+x❑4≤ 1 (1)

−5 x2− 2 x❑43 (2)

2 x2+8 x3+2 x46 (3 )
(3) xj≥ 0 ( j=1,4)

i) Tìm BTĐN của bài toán trên.

j) Giải BT gốc và suy ra kết quả cho BTĐN.
GIẢI:

Bài toán đối ngẫu là:

A=

[

10 − 5 0 −23 0 1

0 2 8 2

]

⇒ AT

[

1 0 0

3 −5 2

0 0 8

1 −2 2

]

(1) g ( y )= y1+3 y2+6 y3→ min

(2)

{

y1≥2

3 y1−5 y2+2 y3≥ 4

8 y❑3≥1

¿y1− 2 y2+2 y31
(3 ) yj0, ( j=1,3)

Ta đã biết kết quả bài toán gốc:

phương án tối ưu: x0=(x1, x2, x3, x4)=

(

1,0,3

4, 0

)

with f(x
0

)=11

4 Bây giờ ta tìm

phương án tối ưu của bài toán đối ngẫu:
thứ 1:

x1
0

=1>⇒ y1=2

x30=
3

4>⇒ y3=
1
8

Thứ 2: thay x0

(

1,0,3

4, 0

)

vào biểu thức(2) −5 x2− 2 x4−3=−3 ≠ 0⇒ y2=0

Vậy phương án tối ưu là y0

(

2,0,1

)

∧ g(y
0)

=11
4

(1) f ( x )=−10 x1−3 x2+2 x3+2 x4−2 x5− 4 x6+5→ min
(2)

{

x1+x2− x3+x5+2 x6=2

2 x1+x3− x4+2 x5+x6=3
4 x1+6 x3−6 x4+3 x5+4 x6=18

</div>
(49)<div class='page_container' data-page=49>

k) Tìm BTĐN của bài toán trên.

l) Giải BT gốc và suy ra kết quả cho BTĐN.
GIẢI:

Bài toán đối ngẫu là:

A=

[

1 1 −1 0 1 2

2 0 1 −1 2 1

4 0 6 −6 3 4

]

⇒ AT

[

1 2 4

1 0 0

−1 1 6

0 − 1 −6

1 2 3

2 1 4

]

(1) g ( y )=2 y1+3 y2+18 y3→ max

(2)

{

y1+2 y2+4 y3≤ −10

y1≤ −3
− y1+y2+6 y3≤2

− y2− 6 y3≤ 2

y1+2 y2+3 y3≤ −2
2 y1+y2+4 y3≤ −4
(3 ) yjtù̀ y y'( j=1,3 )

Ta đã biết kết quả bài toán gốc:

phương án tối ưu: x0

=(x1, x2, x3, x4, x5, x6)=(0,5,3,0,0,0) with f(x0

)=11

4 Bây

giờ ta tìm phương án tối ưu của bài toán đối ngẫu:
thứ 1:

x20=5>0⇒ y1=− 3

x30=3>0⇒ y2+6 y3=−1

⇒

{

y1=−3

y3=a

y2=−6 a −1

Vậy phương án tối ưu là y0

=(y1, y2, y3)=(−3 , a , −6 a −1 ),∀ a ∈ R ∧ g(y0)=− 4

(1) f ( x )=x1+3 x2+3 x3→ min

(2)

{

x1+2 x2≥ 2(1)
3 x1+x2+x❑3≥ 4 (2)

x31

4(3)
(3 ) xj0 ( j=1,3)

m) Tìm BTĐN của bài toán trên.

</div>
(50)<div class='page_container' data-page=50>

Bài toán đối ngẫu là:

A=

[

1 2 0
3 1 1
0 0 1
1 0 1

]

⇒ AT

[

1 3 0 1
2 1 0 0
0 1 1 1

]

(1) g ( y )=2 y1+4 y2+

4y3+y4→ max
(2)

{

y1+3 y2≤ 1

2 y1+y2≤ 3

y2+y3≤ 3
(3) yj≥ 0, ( j=1,3)

Ta biết kết quả bài toán ĐN:

phương án tối ưu: y0=(y1, y2, y3, y4)=(1,0,3,0 ) with g(y0)=11

4 Bây giờ ta tìm

phương án tối ưu của bài toán gốc:
thứ 1:

y10=1>0⇒ x1+2 x2=2

y30=3>0⇒ x3=
1
4

Thứ 2: thay y0=(1,0,3,0) vào biểu thức(2) 2 y

1+y2−3=−1 ≠0⇒ x2=0

Vậy phương án tối ưu là x0

(

2,0,1
4

)

∧ f(x

)=11

(1) f ( x )=3 x1−7 x2+x3−2 x❑4→ max

(2)

{

2 x1− 3 x2− x3+2 x❑4≤15 (1)

2 x1−2 x2+3 x330 (2)
2 x1− 2 x2− 3 x3+4 x4=16 (3 )

(3 ) xj≥ 0 ( j=1,4 )

o) Tìm BTĐN của bài toán trên.

p) Giải BT gốc và suy ra kết quả cho BTĐN.
GIẢI:

Bài toán đối ngẫu là:

A=

[

1 −3 −1 21 − 2 3 0
1 − 2 −3 4

]

⇒ AT

[

1 1 1

− 3 − 2 −2
− 1 3 −3

</div>
(51)<div class='page_container' data-page=51>

(1) g ( y )=15 y1+30 y2+16 y3→ min

(2)

{

2 y1+2 y2+2 y3≥3
−3 y1−2 y2− 2 y3≥− 7

− y1+3 y2−3 y3≥1

¿2 y1+4 y3≥− 2
(3 ) y1, y2≥ 0 , y3tù̀ y y

'
Ta đã biết kết quả bài toán gốc:

phương án tối ưu: x0

=(x1, x2, x3, x4)=

(

7,0,0,1

)

with f(x
0

)=20 Bây giờ ta tìm

phương án tối ưu của bài toán đối ngẫu:
thứ 1:

x10=7>0⇒ 2 y1+2 y2+2 y3=3

x4
0

2>0⇒2 y1+4 y3=−2

Thứ 2: thay x0=

(

7,0,0,1

)

vào biểu thức(2)
2 x1−2 x2+3 x3− 30=− 16≠ 0⇒ y2=0

Vậy phương án tối ưu là y0=

(

4,0, −5

)

∧ g(y
0

)=20

(1) f ( x )=12 x1+9 x2+7 x3+8 x❑4→ min

(2)

{

3 x1+2 x2+x3+x❑

4≤15 (1)

x1+2 x2+2 x3+3 x4=10 (2)
2 x1+x2+2 x3+x412 (3)

(3) xj≥ 0( j=1,4 )

q) Tìm BTĐN của bài toán trên.

r) Giải BT gốc và suy ra kết quả cho BTĐN.
GIẢI:

Bài toán đối ngẫu là:

A=

[

3 2 1 11 2 2 3

1 1 2 1

]

⇒ AT

[

3 1 1
2 2 1
1 2 2
1 3 1

]

(1) g ( y )=15 y1+10 y2+12 y3→ max

(2)

{

3 y1+y2+2 y3≤ 12
2 y1+2 y2+y3≤ 9

y1+2 y2+2 y3≤7
¿y1+3 y2+y3≤8

</div>
(52)<div class='page_container' data-page=52>

Ta đã biết kết quả bài toán gốc:

phương án tối ưu: x0

=(x1, x2, x3, x4)=(2,0,4,0) with f(x0)=52 Bây giờ ta tìm

phương án tối ưu của bài toán đối ngẫu:
thứ 1:

x1
0

=2>0⇒3 y1+y2+2 y3=12

x3
0

=4>0⇒ y1+2 y2+2 y3=7

Thứ 2: thay x0=(2,0,4,0) vào biểu thức(1)
3 x1+2 x2+x3+x4−15=−5 ≠ 0⇒ y1=0

Vậy phương án tối ưu là y0

(

0, −5,17

)

∧ g(y
0

</div>
(53)<div class='page_container' data-page=53>

(1) f ( x )=4 x1+3 x2+3 x3→ max
(2)

{

x1+2 x2+x3≤ 40 (1)

x1+x2+2 x3≤60 (2)

x1≤ 20 (3)

(3) xj≥ 0 ( j=1,3)

s) Tìm BTĐN của bài toán trên.

t) Giải BT gốc và suy ra kết quả cho BTĐN.
GIẢI:

Bài toán đối ngẫu là:

A=

[

1 2 1
1 1 2
1 0 0

]

⇒ AT

[

[

3 5 3
1 3 2
6 2 5

]

⇒ AT

[

3 1 6
5 3 2
3 2 5

]

(1) g ( y )=20 y1+9 y2+30 y3→ max

(2 )

{

3 y1+y2+6 y3≤ 6
5 y1+3 y2+2 y3≤ 8
3 y1+2 y2+5 y3≤ 1
(3) yj≥ 0,( j=1,3)

Ta biết kết quả bài toán ĐN:

phương án tối ưu: y0=(y1, y2, y3)=

(

3, 0,0

)

with g(y

)=20

3 Bây giờ ta tìm

phương án tối ưu của bài toán gốc:
thứ 1:

y1
0

3>0⇒3 x1+5 x2+3 x3=20

Thứ 2: thay y0

(

3, 0,0

)

vào biểu thức(1)&(2)
5 y1+3 y2+2 y3− 8=−19

3 ≠ 0⇒ x2=0
3 y1+y2+6 y3− 6=− 5≠ 0⇒ x1=0

Vậy phương án tối ưu là x0=

(

0,0,20

)

∧ f(x
0

)=20
3

</div>
(55)<div class='page_container' data-page=55>

(1) f ( x )=x1+2 x2+x3→ min
(2)

{

x1− 3 x2+4 x3≥ 12(1)
3 x1+x2+2 x❑3≥ 10(2)

x1− x2− x❑3− 8 (3 )

(3 ) xj0 ( j=1,3)

w) Tìm BTĐN của bài toán trên.

x) Giải BTĐN và suy ra kết quả cho gốc.
GIẢI:

Bài toán đối ngẫu là:

A=

[

1 − 33 1 42
1 − 1 − 1

]

⇒ AT

[

1 3 1

−3 1 − 1

4 2 − 1

]

(1) g ( y )=12 y1+10 y2− 8 y3→ max

(2)

{

y1+3 y2+y3≤ 1

− 3 y1+y2− y3≤2
4 y1+2 y2− y3≤1
(3 ) yj≥ 0, ( j=1,3 )

Ta biết kết quả bài toán ĐN:

phương án tối ưu: y0=(y1, y2, y3)=

(

1
10,

10 , 0

)

with g(y
0

)=21

5 Bây giờ ta tìm

phương án tối ưu của bài toán gốc:
thứ 1:

y10

= 1

10>0⇒ x1−3 x2+4 x3=12

y20

= 3

10>0⇒ 3 x1+x2+2 x3=10

Thứ 2: thay y0

(

1
10 ,

10, 0

)

vào biểu thức(2)

−3 y1+y2− y3− 2=−2 ≠ 0⇒ x2=0⇒

{

x1+4 x3=12
3 x1+2 x3=10

Vậy phương án tối ưu là x0=

(

8
5, 0,

)

∧ f(x
0

</div>
(56)<div class='page_container' data-page=56>

(1) f ( x )=x1+2 x2+4 x3→ min
(2)

{

x1− x2+3 x3≥ 4 (1)

2 x1+2 x2−3 x❑3≥ 6 (2)

− x1+2 x2+3 x❑

32(3 )

(3) xj0 ( j=1,3)

y) Tìm BTĐN của bài toán trên.

z) Giải BTĐN và suy ra kết quả cho gốc.
GIẢI:

Bài toán đối ngẫu là:

A=

[

1 − 1 3

2 2 −3

−1 2 3

]

⇒ AT

[

1 2 −1

−1 2 2

3 −3 3

]

(1) g ( y )=4 y1+6 y2+2 y3→ max

(2)

{

y1+2 y2− y3≤ 1
− y1+2 y2+2 y3≤ 2
3 y1− 3 y2+3 y3≤ 4

(3 ) yj≥ 0, ( j=1,3 )

Ta biết kết quả bài toán ĐN:

phương án tối ưu: y0=(y1, y2, y3)=

(

10
11 ,

31
33 ,

)

with g(y
0

)=349

33 Bây giờ ta

tìm phương án tối ưu của bài toán gốc:
thứ 1:

y1
0

=10

11 >0⇒ x1− x2+3 x3=4

y20
=31

33>0⇒2 x1+2 x2− 3 x3=6

y20
=17

33>0⇒− x1+2 x2+3 x3=2

⇒

{

x1=

32
11

x2=1411

x3=
26
33

PATU x0=

(

32
11 ,

14
11 ,

26
33

)

</div>
(57)<div class='page_container' data-page=57>

(1) f ( x )=16 x1+8 x2+4 x3→ min
(2 )

{

3 x1+2 x2+2 x3≥ 16 (1)

4 x1+3 x2+x❑3≥14 (2)

5 x1+3 x2+x❑312(3 )

(3) xj0 ( j=1,3)

aa)Tìm BTĐN của bài toán trên.

bb)Giải BTĐN và suy ra kết quả cho gốc.
GIẢI:

Bài toán đối ngẫu là:

A=

[

3 2 24 3 1
5 3 1

]

⇒ AT

[

3 4 5
2 3 3
2 1 1

]

(1) g ( y )=16 y1+14 y212 y3→ max

(2)

{

3 y1+4 y2+5 y3≤ 16
2 y1+3 y2+3 y3≤ 8

2 y1+y2+y3≤ 4
(3 ) yj≥ 0, ( j=1,3 )

Ta biết kết quả bài toán ĐN:

phương án tối ưu: y0=(y1, y2, y3)=(1,2,0)with g(y
0)

=44 Bây giờ ta tìm

phương án tối ưu của bài toán gốc:
thứ 1:

y10=1>0⇒3 x1+2 x2+2 x3=16

y20=2>0⇒ 4 x1+3 x2+x3=14

Thứ 2: thay y0=(1,2,0 ) vào biểu thức(1)
3 y1+4 y25 y3−16=−5 ≠ 0⇒ x1=0⇒

{

2 x2+2 x3=16
3 x2+2 x3=14

</div>
(58)<div class='page_container' data-page=58>

CHƯƠNG IV: BÀI TOÁN VẬN TẢI

§1 BÀI TOÁN VẬN TẢI DẠNG TỞNG QUÁT

I. Thiết lập bài toán

Giả sử có m nơi A1, A2, .. . , Am cung cấp 1 mặt hàng nào đó có khối lượng

tương ứng là a1, a2,. . ., am . Cùng lúc đó có n nơi B1, B2, . .. , Bn tiêu thụ loại

hàng đó với khối lượng yêu cầu tương ứng là b1, b2,. . ., bn .

Gọi Ai(i=1 ,m ) là điểm phát hàng thứ i., Bj( j=1 , n) là điểm thu hàng thứ

Điều kiện cân bằng thu phát

∑

i ai=

∑

j

bj

Ma trận cước phí C=

[

cij

]

m × n trong đó cij là chi phí vận chuyển 1 tấn hàng

từ Ai đến Bj

Hãy lập kế hoạch vận chuyển từ mỗi điểm phát đến mỗi điểm thu bao nhiêu
tấn hàng để:

 các điểm phát đều phát hết hàng.

 Các điểm thu nhận đủ số hàng yêu cầu.

 Tổng cước phí phải trả là ít nhất

II. Mô hình toán học:

Gọi xij là số tấn hàng vận chuyển từ Ai đến Bj

Ta có mô hình toán học:

(1) f ( x )=

∑

i

∑

j

cijxij→ min

(2)

{

∑

j=1
n

xij=ai(i=1 , m)

∑

i=1
m

</div>
(59)<div class='page_container' data-page=59>

Thu
Cước
Phát

B1

b1
B2

b2 …

Bj

bj …

Bn
bn

A1: a1

c11
x11

c12

x12 …

c1 j

x1 j …

c1 n
x1n

A2: a2

c21
x21

c22

x22 …

c2 j

x2 j …

c2 n
x2n

… … … …

Ai:ai

ci 1
xi1

ci 2
xi2

cij
xij

cin
xin

… … … …

Am:am

cm 1
xm 1

cm 2
xm 2

cmj
xmj

cmn
xmn

1) Dây chuyền:

a. 1 dãy các ô của bảng mà 2 ô liên tiếp ở cùng hàng hay cột gọi là dây
chuyền.

b. 1 dây chuyền khép kín gọi là 1 vòng.

c. Những ô ứng với xij>0 trong 1 phương án nào đó gọi là ô chọn.

Những ô còn lại là ô loại.

</div>
(60)<div class='page_container' data-page=60>

§2 TÍNH CHẤT CỦA BÀI TOÁN VẬN TẢI

I.Tính chất 1:

Bài toán vận tải cân bằng thu phát luôn có phương án tối ưu.
II. Tính chất 2:

Gỉa sử ta có bảng m hàng, n cột và E là tập hợp gồm m+n-1 ô của bảng
không chứa vòng. Gỉa sử (i, j) là ô của bảng không thuộc E. Nếu ta bổ

sung (i, j) vào E để được E1 thì E1 sẽ chứa 1 vòng duy nhất V. Cuối cùng

ta loại khỏi E1 1 ô tùy ý của vòng V để được E2, thì E2 lại gồm m+n-1 ô của

bảng không chứa vòng.

Ở hình trên: m=4,n=4, tập E gồm m+n-1=7 ô đánh dấu X không chứa vòng.
Khi bổ sung thêm ô(4,4) tạo thành vòng V duy nhất. Khi mất đi 1 ô của V
thì mất vòng.

III. Lập phương án cơ bản ban đầu

Dùng phương pháp phân phối tối đa vào ô có cước phí nhỏ nhất
Ví dụ

Thu
Cước phí
Phát

B1

B2

B3

A1:30

¿20

¿10

5
¿ ¿

A2: 25

5
¿ ¿

4
¿ ¿

2
¿25

A3:35

8
¿ ¿

¿30

¿5

</div>
(61)<div class='page_container' data-page=61>

Ví dụ

Thu
Cước phí
Phát

B1

B2

B3

A1:10

5
¿ ¿

3
¿ ¿

1
¿10

A2: 30

¿25

¿5

8
¿ ¿

A3:20

3
¿ ¿

2
¿20

2
¿ ¿

Phương án cơ bản ban đầu có 4 ô chọn < m+n-1=5, nên Phương án ban đầu
suy biến do đó ta phải bổ sung ô chọn không ô (2,3) mà không tạo thành
vòng.

IV. Thuật toán “Quy 0 ô chọn”

1.Định lý: Nếu ta cộng vào hàng i của ma trận cước C=(cij)m×n sớ

ritu ̀̀ y y'

(i=1 , m) ¿ và cộng vào cột j số

sjtù̀ y y'

( j=1 , n) ¿ ta sẽ

có bài toán vận tải mới với ma trận cước phí C'=

(

cij'

)

m ×nwith cij'=cij+ri+sj

tương đương với bài toán ban đầu

( nghĩa là phương án tối ưu của bài toán này cũng là phương án tối ưu của
bài toán kia và ngược lại)

2. Thuật toán:

Bước 1: quy 0 cước phí các ô chọn:

Giả sử ta có 1 phương án cơ bản ban đầu với m+n-1 ô chọn . Ta cộng vào

hàng i của ma trận cước phí số r ¿

i(i=1 ,m) ¿ và cộng vào cột j số
¿

sj(j=1 ,n) ¿ . Ta chọn ri, sj thế nào để cước phí mới cij
'

=cij+ri+sj=0
Bước 2: Kiểm tra tính tối ưu:

1) Nếu sau khi quy 0 cước phí các ô chọn, mà các ô loại đều có cước phí

0 thì phương án đang xét là tối ưu.

2) Nếu sau khi quy 0 cước phí các ô chọn, mà có ít nhất 1 ô loại có cước
phí <0 thì phương án đang xét không phải tối ưu, ta chuyển sang bước
3

Bước 3: Xây dựng phương án mới tốt hơn

1) Tìm ô đưa vào: (i❑, j❑) có cước phí âm nhỏ nhất là ô đưa vào.

2) Tìm vòng điều chỉnh: bổ sung (i❑

, j❑

</div>
(62)<div class='page_container' data-page=62>

3) Phân ô chẵn lẻ của vòng V: ta đánh số thứ tự các ô của vòng V bắt
đầu từ ô (i❑, j❑) , khi đó V phân thành 2 lớp:

VC : Các ô có thứ tự chẵn

VL : Các ô có thứ tự lẻ.

4) Tìm ơ đưa ra và lượng điều chỉnh:
Ơ đưa ra là (i , jmin)∈VC

xij=xi0j0

5)Lập phương án mới: X'=¿

(

xij'

)

m × n

xij'

{

xij− xi0j0if (i , j)∈V

C

xij+xi0j0if (i , j)∈V

L

xij¿if (i , j)∉V

Nghĩa là:

 Các ô lẻ ta cộng thêm vào 1 lượng điều chỉnh xi0j0 .

 Các ô chẵn ta trừ 1 lượng điều chỉnh xi0j0 .

 Giữ nguyên các ô không nằm trong vòng điều chỉnh.

Ví dụ: Gỉai bài toán vận tải sau:

Thu
Cước phí
Phát
B1
80
B2
20
B3
60

A1:50

5
¿ ¿

4
¿ ¿

¿50 r1

A2: 40

3
¿20
2
¿20
6
¿ ¿

r2 =

A3:70

7
¿60
9
¿ ¿
11
¿10

r3 =

-4

s1 =-3 s2 =-2 s3 =-7

Bước 1: lập phương án cơ bản ban đầu: có 5 ô chọn đúng bằng
m+n-1=5, do đó PABĐ là 0 suy biến.

Bước 2: quy 0 ô chọn
Chọn r2=0⇒

{

s1=−3

s3=−7

⇒

{

r3=− 4

r1=6

⇒ s2=− 2

Cước phí mới các ô 0 chọn: cij

'

=cij+ri+sj
Ô (1,1):10-7+5=8.

</div>
(63)<div class='page_container' data-page=63>

Ô (2,3): 0+6-7=-1
8

¿ ¿

0
¿50

r¿− 1

¿20

−1

¿ ¿

r¿0

0
¿60

2
¿ ¿

0
¿10

r¿0

S=0 S=0 S=1

Bước 3: Kiểm tra tính tối ưu: Phương án chưa tối ưu vì ô loại (2,3) có
cước phí âm

Bước 4: lập phương án mới tốt hơn:

Chọn vòng điều chỉnh V ={(2,3) ,(2,1) , (3,1), (3,3) ,}

Lượng điều chỉnh: min{20 , 10}=10

</div>
(64)<div class='page_container' data-page=64>

Ta có phương án mới và cước phí mới theo bảng sau:
7

¿ ¿

7¿
¿ ¿

0
¿50

0¿
¿10

0¿
¿20

0¿
¿10

0¿
¿70

3¿
¿ ¿

1
¿0

Ta có cước phí mới các ô không chọn 0 , nên phương án cuối cùng là tối

j

cijxij→ min

(2)

{

∑

j=1
n

xij≤ ai(i=1 ,m)

∑

i=1
m

xij=bj( j=1 , n)
(3 ) xij≥ 0 (i=1 ,m ; j=1 , n)

(2)

{

∑

j=1
n

xij=ai(i=1 , m)

∑

i=1
m

xij≤bj( j=1, n)
(3 ) xij≥ 0 (i=1 ,m ; j=1 , n)

Phương pháp:

Trường hợp 1: lập thêm trạm thu giả Bn+1 với nhu cầu

Ví dụ:

</div>
(66)<div class='page_container' data-page=66>

Thu 20 40 60
Cước phí

phát

80 3 4 1

30 4 2 3

50 1 5 6

Tổng số phát=160>tổng số thu=120

Ta lập thêm trạm thu giả( cột thứ tư) ta được bảng sau:

Thu 20 40 60 Trạm(40)

Thu
giả

Cước phí

phát

80 3 4 4 0

1 0
60

0 0
10

R=0

30 4 7 2 0

3 4 0 2 R=2

50 1 0

5 1 6 5 0 0
30

R=0

S=1 S=-4 S=-1 S=0

Ta có các ô 0 chọn có cước phí 0 . Ta có PATU:

X =

[

00 10 60 1030 0 0
20 0 0 30

]

</div>
(67)<div class='page_container' data-page=67>

BÀI TẬP:

1) Gỉai bài toán vận tải sau:

80 20 60

50 5 4 1

40 3 2 6

70 7 9 11

GIẢI:

80 20 60

50 5 8 4 8 1 0
50

R=6

40 3 0

20(-10)

2 0
20

6 -1
(+10)

R=0

70 7 0

60(+10)

9 11 0

10(-10)

R=-4

S=-3 S=-2 S=-7

Chọn vòng điều chỉnh

V ={(2,3) ,(2,1) , (3,1), (3,3) ,}

</div>
(68)<div class='page_container' data-page=68>

Phương án và cước phí mới được cho ở bảng sau:
5 7 4 7 1 0

R=-1
3 0

2 0
20

6 0
10

R=0
7 0

9 3 11 1
0

R=0

S=0 S=0 S=1

Ta có các ô 0 chọn có cước phí 0 . Ta có PATU:

X =

[

10 20 100 0 50
70 0 0

]

Tổng chi phí vận chuyển: f ( x )=670

2) Gỉai bài toán vận tải sau:

60 70 40 30

100 2 1 4 3

80 5 3 2 6

20 6 2 1 5

GIẢI:

60 70 40 30

100 2 0

30(+30)

1 0
70(-30)

4 5 3 0 R=3

80 5 0

30(-30)

3 -1
(+30)

2 0
20

6 0
30

R=0

</div>
(69)<div class='page_container' data-page=69>

S=-5 S=-4 S=-2 S=-6

Chọn vòng điều chỉnh

V ={(2,2), (1,2) , (1,1) , (2,1) ,}

Lượng điều chỉnh: min{30 , 70}=30

Phương án và cước phí mới được cho ở bảng sau:

2 0
60

1 0
40(-30)

4 4 3 -1
(+30)

R=-1
5 1

3 0
30(+30)

2 0
20

6 0
30 (-30)

R=0
6 3 2 0 1 0

5 0 R=0

S=1 S=1 S=0 S=0

Chọn vòng điều chỉnh

V ={(1,4 ) , (1,2 ), (2,2) ,(2,4 ) ,}

Lượng điều chỉnh: min{30 , 40}=30

Phương án và cước phí mới được cho ở bảng sau:

2 0

1 0
10

4 4 3 0
30

R=0
5 1

3 0
60

2 0
20

6 1
0

R=0
6 3 2 0 1 0

5 1 R=0

S=0 S=0 S=0 S=1

Ta có các ô 0 chọn có cước phí 0 . Ta có PATU:

X =

[

60 100 60 200 300
0 0 20 0

]

</div>
(70)<div class='page_container' data-page=70>

3) Gỉai bài toán vận tải sau:

20 100 145 30 150

120 6 3 1 4 5

150 1 2 5 4 3

150 2 4 3 1 6

25 3 1 4 2 7

GIẢI:

20 100 145 30 150

120 6 4

3 0 1 0
120

4 5 5 1 R=2

150 1 0

20(-20)

2 0
75

5 5 4 6 3 0
55(+20)

R=3

150 2 -2

(+20)

4 -1 3 0
25

1 0

6 0
95(-20)

R=0

25 3 3 1 0

4 5 2 5 7 5 R=4

S=-4 S=-5 S=-3 S=-1 S=-6 S=-4

Chọn vòng điều chỉnh

V ={(3,1 ), (3,5) , (2,5) ,(2,1) ,}

</div>
(71)<div class='page_container' data-page=71>

Phương án và cước phí mới được cho ở bảng sau:

6 6

3 0 1 0
120

4 5 5 1 R=0

1 2
0

2 0
75(-75)

5 5 4 6 3 0
75(+75)

R=0

2 0

4 -1
(+75)

3 0
25

1 0

6 0
75(-75)

R=0
3 5 1 0

4 5 2 5 7 5 R=0

S=2 S=0 S=0 S=0 S=0

Chọn vòng điều chỉnh

V ={(3,2 ), (3,5) , (2,5) ,(2,2) ,}

Lượng điều chỉnh: min{75 , 75}=75 , lúc này phương án mới có 7 ô chọn<8
ô. Nên PA suy biến ta bổ sung thêm ô chọn 0: ô(3,5) mà 0 tạo thành vòng
với các ô đã chọn của PA mới.

Phương án và cước phí mới được cho ở bảng sau:

6 6

3 1 1 0
120

4 5 5 1 R=0

1 2
0

2 1
0

5 5 4 6 3 0
150

R=0
2 0

4 0
75

3 0
25

1 0

6 0
0

R=0
3 4 1 0

4 4 2 4 7 4 R=-1

S=0 S=1 S=0 S=0 S=0

Ta có các ô 0 chọn có cước phí 0 . Ta có PATU:

X =

[

0 0 120 0 0

0 0 0 0 150

</div>
(72)<div class='page_container' data-page=72>

Tổng chi phí vận chuyển: f ( x )=1040

4) Gỉai bài toán vận tải sau:

10 10 10 20 20

5 5 1 4 6 7

15 3 4 2 7 8

20 4 3 1 7 9

30 6 5 4 9 11

GIẢI:

10 10 10 20 20

5 5 4 1 0

4 5 6 1 7 0 R=4

15 3 0

4 1 2 1 7 0
5(-5)

8 -1
(+5)

R=2

20 4 1 3 0 1 0

7 0
10

9 0 R=2

30 6 1 5 0

4 1 9 0
5(+5)

11 0
20(-5)

R=0

S=-5 S=-5 S=-3 S=-9 S=-11

Chọn vòng điều chỉnh

V ={(2,5) ,(2,4 ) ,( 4,4) , (4,5) ,}

</div>
(73)<div class='page_container' data-page=73>

Phương án và cước phí mới được cho ở bảng sau:

5 3 1 0
5

4 5 6 1 7 0 R=0

3 0
10

4 2 2 2 7 0
0

8 0
5

R=1
4 0 3 0 1 0

7 0
10

9 0 R=0
6 0 5 0

4 1 9 0

11 0
15

R=0

S=-1 S=0 S=0 S=0 S=0

Ta có các ô 0 chọn có cước phí 0 . Ta có PATU:

X =

[

0 5 0 0 0

10 0 0 0 5

0 0 10 10 0
0 5 0 10 15

]

Tổng chi phí vận chuyển: f(x)=435

5 Gỉai bài toán vận tải sau:

30 15 2 15

25 3 4 2 6

15 5 1 6 2

40 2 1 5 3

</div>
(74)<div class='page_container' data-page=74>

30 15 2 15

25 3 0

4 2 2 0
20

6 2 R=-1

15 5 3 1 0

15(-15)

6 5 2 -1
Đưa vào
(+15)

R=0

40 2 0

1 0
Bổ sung
0(+15)

5 4 3 0
15(-15)

R=0

S=-2 S=-1 S=-1 S=-3

Ở bảng trên: PACB ban đầu có 5 ô<m+n-1=6. PA suy biến, do đó ta bổ sung
ô(3,2) 0 tạo vòng với các ô đã chọn.

Chọn vòng điều chỉnh

V ={(2,4) , (2,2), (3,2) , (3,4 ) ,}

Lượng điều chỉnh: min{15 , 15}=15

Phương án và cước phí mới được cho ở bảng sau:
3 0

4 2 2 0
20

6 3 R=0

5 3 1 0
Bổ sung
0

6 5 2 0
15

R=0
2 0

1 0
15

5 4 3 0
0

R=0

S=0 S=0 S=0 S=1

Ở PA này số ô chọn: 5<6, nên PA suy biến ta bổ sung ô(2,2) 0 tạo vòng với
các ô đã chọn.

Ta có các ô 0 chọn có cước phí 0 . Ta có PATU:

X =

[

5 0 20 0

0 0 0 15

25 15 0 0

]

</div>
(75)<div class='page_container' data-page=75>

6)Gỉai bài toán vận tải sau:

180 200 230 280

280 8 6 14 7

320 2 4 6 7

290 5 3 4 9

GIẢI:

180 200 230 280

280 8 5 6 0

Bổ sung
0

14 7 7 0
280

R=-3

320 2 0

180

4 -1
Đưa vào

6 0
140

7 1

R=-2

290 5 5 3 0

200

4 0
90

9 5 R=0

S=0 S=-3 S=-4 S=-4

Ở bảng trên: PACB ban đầu có 5 ô<m+n-1=6. PA suy biến, do đó ta bổ sung
ô(1,) 0 tạo vòng với các ô đã chọn.

Chọn vòng điều chỉnh

V ={(2,2), (3,2) , (3,3 ), (2,3) ,}

Lượng điều chỉnh: min{200 , 140}=140

Phương án và cước phí mới được cho ở bảng sau:
8 4 6 0

Bổ sung
0

14 7 7 0
280

R=0
2 0

180

4 0
Đưa vào
140

6 1
0

7 2

R=1

5 4 3 0
60

4 0
230

9 5 R=0

</div>
(76)<div class='page_container' data-page=76>

Ở PA này số ô chọn: 5<6, nên PA suy biến ta bổ sung ô(1,) 0 tạo vòng với
các ô đã chọn.

Ta có các ô 0 chọn có cước phí 0 . Ta có PATU:

X =

[

0 0 0 280

180 140 0 0

0 60 230 0

]

Tổng chi phí vận chuyển: f ( x )=3980

Bài toán không cân bằng thu phát

7 Gỉai bài toán vận tải sau:

8 7 12 15

10 8 9 12 5

19 4 8 5 9

11 5 9 7 1

9 1 2 6 3

GIẢI:

8 7 12 15 Trạm

thu giả

10 8 1 9 1 12 7 5 0

0 0
6

R=0

19 4 -3

Đưa vào
(+6)

8 0
6(-6)

5 0
12

9 4 0 0
1

R=0

11 5 2 9 5 7 6 1 0

0 4 R=4

9 1 0

8(-6)

2 0
1(+6)

6 7 3 4 0 6 R=6

S=-7 S=-8 S=-5 S=-5 S=0

</div>
(77)<div class='page_container' data-page=77>

V ={(2,1), (4,1 ), (4,2) , (2,2) ,}

Lượng điều chỉnh: min{6,8}=6

</div>
(78)<div class='page_container' data-page=78>

8 4 9 4 12 7 5 0
4

0 0
6

R=0
4 0

Đưa vào
6

8 3
0

5 0
12

9 4 0 0
1

R=0
5 5 9 8 7 6 1 0

0 4 R=0
1 0

2 0
7

6 4 3 1 0 3 R==-3

S=3 S=3 S=0 S=0 S=0

Ta có các ô 0 chọn có cước phí 0 . Ta có PATU:

X =

[

0 0 0 4 6

6 0 12 0 1
0 0 0 11 0
2 7 8 0 0

]

Tổng chi phí vận chuyển: f(x)=131

8) Gỉai bài toán vận tải sau:

20 50 60 30

50 4 5 1 0

40 2 3 6 0

70 9 7 11 0

</div>
(79)<div class='page_container' data-page=79>

20 50 60 30
Trạm
thu giả

50 4 8 5 8 1 0

0 10 R=10

40 2 0

3 0
20(-10)

6 -1
(+10)

0 4 R=4

70 9 3 7 0

30(+10)

11 0
10(-10)

0 0
30

R=0

S=-6 S=-7 S=-11 S=0

Chọn vòng điều chỉnh

V ={(2,3) ,(2,2) , (3,2), (3,3) ,}

Lượng điều chỉnh: min{10 , 20}=10

Phương án và cước phí mới được cho ở bảng sau:
4 7 5 7 1 0

0 9 R=-1

2 0
20

3 0
10

6 0
Đưa vào
10

0 4 R=0
9 3 7 0

11 1
0

0 0
30

R=0

S=0 S=0 S=1 S=0

Ta có các ô 0 chọn có cước phí 0 . Ta có PATU:

X =

[

20 10 100 0 50 00
0 40 0 30

]

</div>
(80)<div class='page_container' data-page=80>

9) Gỉai bài toán vận tải sau:

30 40 60 70

100 4 5 3 2

80 7 3 6 4

20 6 2 7 3

GIẢI:

30 40 60 70

100 4 0 5 5 3 0

30(+30)

2 0
70(-30)

R=3

80 7 0

3 0
20

6 0
30(-30)

4 -1
Đưa vào
(+30)

R=0

20 6 0 2 0

7 2 3 -1 R=1

S=-7 S=-3 S=-6 S=-5

Chọn vòng điều chỉnh

V ={(2,4) , (1,4) , (1,3 ), (2,3) ,}

Lượng điều chỉnh: min{70 , 30}=30

Phương án và cước phí mới được cho ở bảng sau:
4 -1

(+30)

5 4 3 0
60

2 0
40(-30)

R=-1
7 0

30(-30)

3 0
20

6 1
0

4 0
30(+30)

R=0
6 0 2 0

7 3 3 0 R=0

S=0 S=0 S=1 S=1

Chọn vòng điều chỉnh

</div>
(81)<div class='page_container' data-page=81></div>
(82)<div class='page_container' data-page=82>

Phương án và cước phí mới được cho ở bảng sau:
4 0

5 4 3 0
60

2 0
10

R=0
7 1

3 0
20

6 1
0

4 0
60

R=0
6 1 2 0

7 3 3 0 R=0

S=1 S=0 S=0 S=0

Ta có các ô 0 chọn có cước phí 0 . Ta có PATU:

X =

[

300 200 60 100 60
0 20 0 0

]

Tổng chi phí vận chuyển: f ( x )=660

10) Gỉai bài toán vận tải sau:

150 120 80 50

100 3 5 7 11

130 1 4 6 3

170 5 8 12 7

GIẢI:

150 120 80 50

100 3 0

20(-20)

5 0
80(+20)

7 -2 11 7 R=3

130 1 0

130

4 1 6 -1 3 1 R=5

170 5 -1

Đưa vào
(+20)

8 0
40(-20)

12 0
80

7 0
50

R=0

</div>
(83)<div class='page_container' data-page=83>

Chọn vòng điều chỉnh

V ={(3,1 ), (3,2) , (1,2) , (1,1) ,}

Lượng điều chỉnh: min{40 ,20}=20

Phương án và cước phí mới được cho ở bảng sau:

3 1
0

5 0
100(-80)

7 -2
(+80)

11 7 R=0

1 0
130

4 0 6 -2 3 0 R=-1
5 0

8 0
20(+80)

12 0
80(-80)

7 0
50

R=0

S=1 S=0 S=0 S=0

Chọn vòng điều chỉnh

V ={(1,3 ), (1,2) , (3,2), (3,3) ,}

Lượng điều chỉnh: min{100 , 80}=80

Phương án và cước phí mới được cho ở bảng sau:
3 1

5 0

7 0
80

11 7 R=0

1 0
130

4 0 6 0 3 0 R=0

5 0
20

8 0
100

12 2
0

7 0
50

R=0

S=0 S=0 S=2 S=0

Ta có các ô 0 chọn có cước phí 0 . Ta có PATU:

X =

[

1300 200 800 00
20 100 0 50

]

</div>
(84)<div class='page_container' data-page=84>

BÀI TẬP TỰ GIẢI

Giải các bài toán vận tải cho bởi bảng sau:
1)

25 40 20 10

40 4 3 7 8

20 6 2 3 4

35 5 3 8 6

ĐÁP SÔ

X =

[

25 150 0 200 00
0 25 0 10

]

Tổng chi phí vận chuyển: f ( x )=340

220 310 200 250

300 8 5 4 6

500 12 11 9 13

180 10 15 18 14

ĐÁP SÔ

X =

[

400 50260 2000 2500

180 0 0 0

]

</div>
(85)<div class='page_container' data-page=85>

76 62 88 45 40

79 10 19 9 6 8

102 13 11 8 7 4

70 12 17 10 5 3

60 12 18 18 7 9

ĐÁP SÔ

X =

[

31 0 48 0 0

0 62 40 0 0

0 0 0 30 40

45 0 0 15 0

]

Tổng chi phí vận chuyển: f(x)=2659

85 75 60 50

105 4 16 10 14

65 10 18 12 20

55 6 4 14 18

45 8 6 8 12

ĐÁP SÔ X =

[

85 0 0 20

0 0 60 5

0 55 0 0

0 20 0 25

]

</div>
(86)<div class='page_container' data-page=86>

120 280 130 270

100 6 8 3 7

300 9 10 11 4

150 5 7 9 10

250 12 13 8 9

ĐÁP SÔ

X =

[

0 0 100 0

0 30 0 270

120 30 0 0

0 220 30 0

]

</div>
(87)<div class='page_container' data-page=87>

TÀI LIỆU THAM KHẢO

[1] GS. Đặng Hấn. Quy hoạch tuyến tính. Trường Đại học Kinh Tế TP. Hồ
Chí Minh.

[2] Ngô Thành Phong. Đại số tuyến tính và Quy hoạch tuyến tính. Nhà xuất
bản Đại học quốc gia TP. Hồ Chí Minh-2003.

[3] Nguyễn Cảnh. Quy hoạch tuyến tính. Nhà xuất bản Đại học quốc gia TP.

Hồ Chí Minh-2004.

</div>
(88)<div class='page_container' data-page=88>

MỤC LỤC

Trang

Chương 1: Bài toán quy hoạch tuyến tính 1

§1 : 1 số ví dụ dẫn đến bài toán quy hoạch tuyến tính 1

§2 : Các dạng bài toán quy hoạch tuyến tính 6

§3 : Biến đởi dạng của bài toán quy hoạch tuyến tính 9

Chương 2: Phương pháp đơn hình 15

§1 : Thuật toán đơn hình 15

§2 : Thuật toán đơn hình mở rộng 20

Bài tập có lời giải 26

Chương 3: Bài toán đối ngẫu 41

§1 : Khái niệm 41

§2 : Quan hệ giữa bài toán gốc và bài toán đốio ngẫu 44

Bài tập có lời giải 47

Chương 4: Bài toán vận tải 59

§1 : Bài toán vận tải dạng tổng quát 59

§2 : Tính chất của bài toán vận tải 61

§3 : Bài toán vận tải không cân bằng thu phát 66

Bài tập có lời giải 68

Tài liệu tham khảo 86

</div>

tài liệu trang web lớp đ5h13b đại học điện lực

<b>CHƯƠNG I: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH</b>

<b>§1 MỢT SỚ VÍ DỤ DẪN ĐẾN BÀI TOÁN QUY HOẠCH</b>

<b>TUYẾN TÍNH</b>

{

[

]

[

]

{

[

]

[

]

{

<b>§2 CÁC DẠNG BÀI TOÁN QUY HOẠCH TUYẾN TÍNH</b>

∑

{

∑

∑

∑

{

∑

∑

{

∑

[

]

{

[

]

<b>§3 BIẾN ĐỞI DẠNG CỦA BÀI TOÁN QUY HOẠCH TUYẾN</b>

<b>TÍNH</b>

<sub>∑</sub>

∑

<sub>∑</sub>

∑

{

{

<sub>(</sub>

<sub>)</sub>

(

)

{

<sub>(</sub>

<sub>)</sub>

<sub>(</sub>

<sub>)</sub>

<sub>(</sub>

)

<sub>(</sub>

)

<sub>(</sub>

)

(

)

(

)

(

)

(

)

∑

{

∑

<sub>∑</sub>

{

[

]

{

[

]

(

)

(

)

<sub>(</sub>

<sub>)</sub>

{

{