GiẢI BÀI TOÁN ĐƠN HÌNH
Cho bài toán đơn hình sau
Z=
4x1 + 6x2 +8x3 -> MAX
x1 + 2x2 – 3x3 ≤ 12
3x1 + x2 +x3 ≤ 4
2x1 + 2x2 +5x3 ≤ 5
xj ≥ 0 , j = 1,3

B1- chuyển về bài toán phụ
Z=
4x1 + 6x2 +8x3 -> MAX
x1 + 2x2 – 3x3 + x4
= 12
3x1 + x2 + x3 + + x5
=4
2x1 + 2x2 + 5x3 +
+ x6 = 5
xj ≥ 0 , j = 1,6

B2- Nhận xét vài câu như bên dưới:
Trong đó x4, x5, x6 là 3 biến phụ.
NX: BT phụ có dạng chuẩn, có 3 biến cơ sở là x4, x5, x6
Lập bảng đơn hình

20/4/2012

1


GiẢI BÀI TOÁN ĐƠN HÌNH


4

6

8

0

0

0

1

x4

0

12

1

2

-3

1

0


2

2

5

0

0

1

20/4/2012

λ

2


GiẢI BÀI TOÁN ĐƠN HÌNH
i

Cơ sở

Ci

Bi
P/a


12

1

2

-3

1

0

0

2

x5

0

4

3

1

1

0


5

->

0

λ

Δj

=

X

0 * 12 + 0 * 4 + 0 *5 = 0
20/4/2012

3


GiẢI BÀI TOÁN ĐƠN HÌNH
i

Cơ sở

Ci

Bi
P/a


12

1

2

-3

1

0

0

2

x5

0

4

3

1

1

0


=

0
0
0

X

1
3
4

-

4

->

-4

0 * 1 + 0 * 3 + 0 *4 = 0
20/4/2012

4


GiẢI BÀI TOÁN ĐƠN HÌNH
i

Cơ sở

1

x4

0

12

1

2

-3

1

0

0

2

x5

0

4

3


0

-4

Δj

=

0
0
0

X

2
1
2

-

6

->

λ

-6

0*2+0*1+0*2=0
20/4/2012

8

0

0

0

1

x4

0

12

1

2

-3

1

0

0

2


5

0

0

1

0

-4

-6

Δj

=

0
0
0

X

-3
1
5

-


x4

x5

x6

4

6

8

0

0

0

1

x4

0

12

1

2


x6

0

5

2

2

5

0

0

1

0

-4

-6

-8

0

0


P/a
4
6
8
0
0
0
1

x4

0

12

1

2

-3

1

0

0

2

x5


0

0

1

0

-4

-6

-8

0

0

0

Δj

BT Max -> cột xoay
là số âm nhỏ nhất
(hoặc số âm có trị
tuyệt đối lớn nhất)
20/4/2012

8


0

0

0

1

x4

0

12

1

2

-3

1

0

0

2

x5


0

0

1

0

-4

-6

(-8)

0

0

0

Δj

=

20/4/2012

12

/


x4

x5

x6

4

6

8

0

0

0

1

x4

0

12

1

2


x6

0

5

2

2

5

0

0

1

0

-4

-6

(-8)

0

0


Ci

Bi
P/a

x1

x2

x3

x4

x5

x6

4

6

8

0

0

0


4

3

1

1

0

1

0

4

3

x6

0

5

2

2

5


5

->

1

11


GiẢI BÀI TOÁN ĐƠN HÌNH
Dòn xoay sẽ là dòng có lamda dương nhỏ nhất
i

Cơ sở

Ci

Bi
P/a

x1

x2

x3

x4

x5


1

0

0

-

2

x5

0

4

3

1

1

0

1

0

4


0

0

0

Δj

số 1 là lamda
dương nhỏ nhất

20/4/2012

12


GiẢI BÀI TOÁN ĐƠN HÌNH
Đã xác định được dòng xoay -> tại sao phải xác định dòng xoay vào cột xoay ?
Thật ra xác định để biết được biến vào và biến ra cơ sở
ở đây biến vào là cột xoay (x3) và biến ra là dòng xoay (x6)

i

Cơ sở

Ci

Bi
P/a


0

12

1

2

-3

1

0

0

-

2

x5

0

4

3

1


(1)

0

-4

-6

(-8)

0

0

0

Δj

Ra khỏi cơ sở
20/4/2012

13


GiẢI BÀI TOÁN ĐƠN HÌNH
i

Cơ sở

Ci

1

x4

0

12

1

2

-3

1

0

0

-

2

x5

0

4


0

1

(1)

0

-4

-6

(-8)

0

0

0

->

1

Δj
1

x4

0

Cơ sở

Ci

Bi
P/a

x1

x2

x3

x4

x5

x6

4

6

8

0

0

0


4

3

1

1

0

1

0

4

3

x6

0

5

2

2

(5)

2

x5

0

3

x3

8

1

Δj
=

20/4/2012

2

/

5

->

2/5

15

0

0

0

λ

1

x4

0

12

1

2

-3

1

0

0

-


2

2

(5)

0

0

1

(1)

0

-4

-6

(-8)

0

0

0

2/5


5

->

2/5

16


GiẢI BÀI TOÁN ĐƠN HÌNH
i

Cơ sở

Ci

Bi
P/a

x1

x2

x3

x4

x5

x6


0

0

-

2

x5

0

4

3

1

1

0

1

0

4

3


0

0

2/5

2/5

1

Δj
1

x4

0

2

x5

0

3

x3

8


x2

x3

x4

x5

x6

4

6

8

0

0

0

λ

1

x4

0


0

1

0

4

3

x6

0

5

2

2

(5)

0

0

1

(1)



x4

0

2

x5

0

3

x3

8

Δj
làm tương tự để
có kết quả như
bảng
20/4/2012

18


GiẢI BÀI TOÁN ĐƠN HÌNH
i

Cơ sở

λ

1

x4

0

12

1

2

-3

1

0

0

-

2

x5

0


0

0

-4

-6

(-8)

0

1

2/5

2/5

1

0

Δj
1

x4

0

2


-

?

*

1

->

1

hehe, hệ số là 1,
khỏe rồi.
19


GiẢI BÀI TOÁN ĐƠN HÌNH
i

Cơ sở

Ci

Bi
P/a

x1


12

1

2

-3

1

0

0

-

2

x5

0

4

3

1

1


0

-4

-6

(-8)

0

0

0

0

0

1/5

Δj
1

x4

0

2

x5


2/5

->

3/5
nếu là hệ số 1, không
cần phải nhân cho
2/5. có thể trừ trực
tiếp cho 2/5

20


GiẢI BÀI TOÁN ĐƠN HÌNH
i

Cơ sở

Ci

Bi
P/a

x1

x2

x3


2

-3

1

0

0

-

2

x5

0

4

3

1

1

0

1


-6

(-8)

0

0

0

3/5

0

2/5

1

0

0

1/5

Δj
1

x4

0

13/5

21


GiẢI BÀI TOÁN ĐƠN HÌNH
i

Cơ sở

Ci

Bi
P/a

x1

x2

x3

x4

x5

x6

4

6


-

2

x5

0

4

3

1

1

0

1

0

4

3

x6

0


13/5

3/5

0

1

2/5

2/5

1

0

0

1/5

1

->

3

Δj
1



Cơ sở

Ci

Bi
P/a

x1

x2

x3

x4

x5

x6

4

6

8

0

0


0

4

3

1

1

0

1

0

4

3

x6

0

5

2

2



2

x5

0

3

13/5

3/5

0

0

0

-1/5

3

x3

8

1

2/5


x2

x3

x4

x5

x6

4

6

8

0

0

0

λ

1

x4

0


0

1

0

4

3

x6

0

5

2

2

(5)

0

0

-4

-6

3

x3

8

1

2/5

2/5

1

0

0
1
(1)
Số0 ở đây bắt
0
buộc là số 0, vậy
ta phải tìm hệ số.
có 0hệ số sẽ
tìm
-1/5
được giá trị dòng
0 này 1/5

Δj


Ci

Bi
P/a

x1

x2

x3

x4

x5

x6

4

6

8

0

0

0


4

3

1

1

0

1

0

4

3

x6

0

5

2

2

(5)



2

x5

0

3

13/5

3/5

0

0

0

-1/5

3

x3

8

1

2/5

2 + 6/5 =16/5
cái này cộng trừ
phân số thôi
25