1Lời nói đầu

Các bài toán tối u nhằm nghiên cứu giải bài toán cực trị của một hàm dới những
ràng buộc nào đó. Các phơng pháp tối u là một công cụ hữu hiệu giúp chúng ta có những
giải pháp tốt nhất để giải quyết một vấn đề. Ngày nay, với sự phát triển của kỹ thuật tin học,
phạm vi ứng dụng của tối u hóa ngày càng mở rộng.
Giáo trình Tối u hóa ứng dụng nhằm mục đích giới thiệu cho ngời đọc những vấn
đề cơ bản nhằm xác lập một vấn đề tối u dới những ràng buộc nhất định và từ đó tìm kỹ
thuật giải thích hợp. Nội dung giáo trình mô tả phần cơ sở lý thuyết ngắn gọn, đủ dùng cho
phơng pháp tính và thuật toán. Một số ví dụ minh họa cho phơng pháp giải và các bài tập
ứng dụng.
Nguyễn Đắc Lực


Chơng 3: Bài toán tối u tuyến tính
3.1. Một số ví dụ về bài toán tối u
3.2. Phát biểu bài toán
3.3. Tính đối ngẫu và định lý cơ bản của tối u tuyến tính
3.4. Các phơng pháp giải bài toán tối u tuyến tính
3.5. Thuật toán đơn hình giải bài toán tối u tổng quát
Chơng 4: Bài toán tối u nguyên tuyến tính
4.1. Bài toán tối u nguyên tuyến tính
4.2. Một số mô hình thực tiễn
Chong 5; Bài toán tối u động
5.1. Bản chất bài toán tối u động
5.2. Quá trình phân phối nhiều bớc
5.3. Cấu trúc quá trình tối u động
5.4. Phơng trình điều khiển tối u các dự trữ
Chơng 6: Bài toán tối u phi tuyến không ràng buộc
6.1. Mở đầu
6.2. Điều kiện tối u của bài toán không ràng buộc
6.3. Các phong pháp dùng đạo hàm
6.4. Các phơng pháp dùng đạo hàm
Chơng 7: Bài toán tối u phi tuyến có ràng buộc
7.1. Mở đầu
7.2. Phơng pháp Gradient
7.3. Phơng pháp hàm phạt
Chơng 8: Quy hoạch thực nghiệm
8.1. Khái niệm về nhận dạng mô hình thống kê
8.2. Phơng pháp bình phơng bé nhất
8.3. Mô hình hồi quy tuyến tính bội
Tài liệu tham khảo
39
41
41
41
42
45
49
49
50
53
55
55
55
56
59
3
Chơng 1: CƠ Sở ĐạI Số TUYếN TíNH

Việc nghiên cứu các bài toán tối u tuyến tính đòi hỏi phải sử dụng một phần của
toán học, mà những phần đó cha đợc nghiên cứu trong các giáo trình cơ sở. Trong đó
trớc hết phải nói đến đại số tuyến tính. Kiến thức quan trọng nhất để nghiên cứu các bài
toán tối u tuyến tính là các phép tính về ma trận, cách giải các hệ phơng trình và bất
phơng trình tuyến tính. ở đây sẽ không chứng minh một số mệnh đề mà chỉ khẳng định.
1.1. Ma trận và các phép tính đối với ma trận
1.1.1. Ma trận: Ma trận là một bảng chữ nhật gồm m.n số sắp thành m
hàng n cột dới dạng:
a
11
a
12

Ma trận có nhiều ký hiệu khác nhau. Ma trận A có thể đợc viết dới dạng:
A=










mnm2m1
2n2221
1n1211
a a a

a a a
a a a
(1.1)
Ma trận có số hàng bằng số cột (m=n) đợc gọi là ma trận vuông. Lúc đó, ngời ta
nói rằng ma trận vuông có cấp n.
Ma trận mà các cột của nó là các hàng tơng ứng của ma trận ban đầu A thì đợc gọi
là ma trận chuyển vị của ma trận A và đợc ký hiệu là A
T
, tức là:
A
T

=





n
2
1
0 0

0 0
0




Đợc gọi là ma trận đờng chéo.
Nếu ma trận đờng chéo có tất cả
i
= 1 thì đợc gọi là ma trận đơn vị và thờng
đợc ký hiệu là E.
Ví dụ:
4
E =









mnm21
2n2221
1n1211
a a a

a a a
a a a



m
(1.3)
Tổng của hai ma trận A và B có cùng kích thớc là ma trận C mới mà mỗi phần tử
của nó bằng tổng các phần tử tơng ứng của ma trận A và B tức là:
A+B =










mnm2m1
2n2221
1n1211
a a a



+++
+++
+++
a a a

a a a
a a a
mn2m21m1
22n22222121
11n12121111
mnmm
n
n
bbb
bbb
bbb
= C (1.4)

Ma trận A nhân đợc với ma trận B chỉ trong trờng hợp số cột của ma trận A bằng
số hàng của ma trận B.
Nếu ma trận A có kích thớc m.n, còn ma trận B là n.l, thì kích thớc của ma trận C
là tích ma trận Avà B sẽ là m.l. Và mỗi phần tử của ma trận C đợc tính theo công thức:
c
ij
= a
i1
b
1j

Phép chuyển vị ma trận có tính chất sau:
1/ (A + B)
T
= A
T
+ B
T

2/ (AB)
T
= B
T
.A
T

Lũy thừa ma trận vuông A đợc định nghĩa nh sau:
A
k
= A.A A
k lần và: A
k1
A
k2
= A
k1+k2

1.2. Định thức và các tính chất của chúng
1.2.1. Khái niệm về hoán vị:
Ta lấy n số đầu tiên: 1,2 , n. Mỗi cách sắp xếp các số ấy theo một thứ tự nào đó
đợc gọi là hoán vị của n số. Nh ta đã biết số các hoán vị khác nhau sẽ bằng n!.

s+2
,
n
(s = 1, 2, , n-1) trong hoán vị I.
Hoán vị đợc gọi là hoán vị chẵn nếu số nghịch thể trong hoán vị I là số chẵn, và
đợc gọi là hóan vị lẻ nếu số các nghịch thể là số lẻ. Ví dụ đối với hoán vị 5, 2, 3, 4,1 thì
số tất cả các nghịch thế bằng:
k
1
+ k
2
+ k
3
+ k
4
= 4 +1 +1 +1 = 7. Vì vậy, hóan vị này là hóan vị lẻ.
1.2.2. Khái niệm về định thức và phép tính của chúng:
Số bằng tổng đại số của tất cả các tích những phần tử ma trận vuông A mà trong đó
mỗi tích chỉ gồm các phần tử khác hàng, khác cột của ma trận, tức là tổng các tích có dạng:
a
1j1
a
2j2
a
njn
(1.6)
đợc gọi là định thức của ma trận A (Số tích đó bằng n!). Mỗi tích nh thế lấy dấu cộng nếu
hoán vị tơng ứng là chẵn, còn lấy dấu trừ, nếu lẻ.
Khi tìm hạng của ma trận, ma trận nghịch đảo và giải hệ phơng trình tuyến tính ta sẽ
cần đến định thức. Định thức của ma trận A thờng đợc ký hiệu là

=
333231
232221
131211
aaa
aaa
aaa
= a
11
a
22
a
33
+ a
12
a
23
a
31
+ a
13
a
21
a
32
- a
13
a
22
a

ij
của định thức
n
và đợc ký hiệu là M
ij
.
Ta coi định thức cấp n:

n
=
nnnjn2n1
iniji2i1
2n2j2221
1n1j1211
a a a a

a a a a

a a a a
a a a a

Khi đó định thức con của phần tử a
ij
sẽ là định thức cấp (n-1):
6
M
ij
=
nn1nj1-njn2n1
n1,-i1j1,-i1-j1,-i12-i11-i

= 2.3 -1.1 = 6-1 = 5
Định thức con của phần tử a
ij
nhân với (-1) với số mũ bằng tổng các chỉ số của phần
tử đó (i + j) đợc gọi là phần phụ đại số của phần tử a
ij
và đợc ký hiệu là A
ij
. Vì vậy:
A
ij
= (-1)
i+j

M
ij
(1.10)
Chẳng hạn, phần phụ đại số của phần tử a
22
ở ví dụ vừa rồi sẽ là: A
22
=(-1)
2+2
.5=5
1.3. Ma trận nghịch đảo và hạng của ma trận
1.3.1. Ma trận nghịch đảo:
Đối với mỗi ma trận A không suy biến sẽ tồn tại một ma trận (ký hiệu A
-1
) thỏa mãn
điều kiện: A













|A|
A

|A|
A

|A|
A|A|
A

|A|
A

|A|
A

= 2.1-1.1 =1
A
12
= ( -1)
1+2

1 3
1 1
= -(1.1-3.1) = 2
A
13
= ( -1)
1+3

1 3
2 1
=1.1-2.3 = -5
Tơng tự ta tìm đợc các A
ij
còn lại: A
21
= -1 ; A
22
= - 4; A
23
= 7; A
31
= -1 ; A
32
= 0;

ở trên ta nhân hai ma trận đơn vị với nhau.
EE =










0 0 0
0 1 0
0 0 1











0 0 0
0 1 0
0 0 1
=

+ a
1n
x
n
= b
1
a
21
x
1
+ a
22
x
2
+ a
2n
x
n
= b
2
(1.20)

a
m1
x
1
+ a
m2
x
2

2
1
(1.21)
B - là véctơ cột các số hạng tự do
B =










m
b
b
b
.
2
1
(1.22)
Hệ phơng trình tuyến đợc gọi là:
Thuần nhất, nếu tất cả các b
i
= 0 (i = 1, 2 m) và không thuần nhất, nếu có ít nhất
một b
i
0.


Giả thiết ma trận A không suy biến, tức là | A| 0, khi đó sẽ tồn tại ma trận nghịch
đảo A
-1
.
Ta nhân vế trái và vế phải của đẳng thức (1.20a) với A
-1
về bên trái. Ta sẽ đợc:
A
-1
AX = A
-1
B.
Bởi vì A
-1
A = E mà nhân bất cứ ma trận nào với E sẽ đợc đúng ma trận đó, nên:
X = A
-1
B (1.23)
Sau khi thế A
-1
bởi biểu thức (1.18a) và thay các véctơ cột X và B ở (1.21) và (1.22)
rồi nhân ma trận A
-1
với B ta có:






nn
nn
bAbAbA
bAbAbA
bAbAbA

. . . 2211
2222112
1221111

Vì hai ma trận chỉ bằng nhau khi các phần tử tơng ứng của chúng bằng nhau, nên
x
1
=
||
1
A
(A
11
b
1
+ A
21
b
2
+ A
n1

(A
1n
b
1
+ A
2n
b
2
+ A
nn
b
n
)
Ta xét trờng hợp thứ hai (m n). Ta gọi ma trận:
A =








mnm2m1
1n1211
a a a

a a a
là ma trận cơ sở của hệ.
Sau khi thêm cột các số hạng tự do vào ma trận A ta lập đợc ma trận mở rộng B:

2.1. Bài toán tối u hoá tổng quát
2.1.1. Phát biểu:
Tìm trạng thái tối u của một hệ thống sao cho đạt đợc mục tiêu mong muốn về chất
lợng theo một nghĩa nào đó.
2.1.2. Các yếu tố của một bài toán tối u hoá:
Một bài toán tối u hoá có ba yếu tố cơ bản sau:
* Trạng thái: mô tả trạng thái của hệ thống cần tối u hoá.
* Mục tiêu: đặc trng cho tiêu chuẩn hoặc hiệu quả mong muốn (chi phí ít nhất, hiệu
suất cao nhất, trọng lợng nhỏ nhất, thời gian ngắn nhất, ).
* Ràng buộc: thể hiện các điều kiện kinh tế, kỹ thuật mà hệ thống phải thỏa mãn.
2.2. Các bài toán tối u
2.2.1. Bài toán quy hoạch tuyến tính:
Hệ thống ở trạng thái tĩnh có các biến trạng thái là:
x = [ x
1
, x
2
, , x
n
]
T
(2.1)
Mục tiêu đợc diễn đạt bởi hàm mục tiêu có dạng tuyến tính:
Z = c.x; với c = [c
1
, c
2
, , c
n
]

của trạng thái (2.1) với các ràng buộc
(2.3) sao cho hàm mục tiêu (2.2) đạt giá trị nhỏ nhất (Min) hoặc giá trị lớn nhất (Max).
2.2.2. Bài toán quy hoạch phi tuyến:
Hệ thống ở trạng thái tĩnh. Tìm trạng thái tối u x
*
khi hàm mục tiêu đợc diễn đạt
bởi một hàm phi tuyến f(x) hoặc có ít nhất một ràng buộc phi tuyến:
g
r
(x) 0; r = 1, , m.
2.2.3. Bài toán cực trị phiếm hàm:
Hệ thống ở trạng thái tĩnh hoặc trạng thái động. Biến trạng thái là z(x) với x là biến
độc lập. Mục tiêu đợc diễn đạt bởi phiếm hàm mục tiêu:
J(z) =

1
),,(
.
x
x
n
dxxzzL

với z = [z
1
(x), z
2
(x), z
n
(x)]

,
x
&&&
]
T
;
x
&
i
= dx
i
/dt;
u = [u
1
, , u
n
]
T
; u - điều khiển
Mục tiêu có dạng phiếm hàm:
J(u) =
dt u),x x,(t,
1
&

t
t
n
L
* Đối với hệ rời rạc:

Cần phải tìm điều khiển tối u u
*
và trạng thái tối u x
*
để hệ thống chuyển từ trạng
thái đầu đến trạng thái cuối sao cho mục tiêu J(u) đạt Min hoặc Max.
Các bài toán tối u có trạng thái tĩnh đợc gọi là bài toán tối u hoá tĩnh, các bài toán
có trạng thái phụ thuộc thời gian đợc gọi là bài toán tối u hoá động. Trạng thái của hệ
thống có thể ở dạng liên tục hoặc gián đoạn. Trong bài toán tối u có thể đặt ra một mục tiêu
hoặc nhiều mục tiêu.
i
ba
Gọi x
ij
0 và c
ij
lần lợt là lợng sản phẩm và chi phí vận chuyển từ điểm i đến j
Tìm phơng án chuyên chở

sao cho chi phí chuyên chở là nhỏ nhất.
Z =

==
n
j
m
i 11
c
ij
x
ij
Min
3.1.2. Bài toán phân phối kế hoạch sản xuất:
Có n xí nghiệp sản xuất m loại chi tiết. Gọi:
a
i
: số chi tiết loại i; b
j
: quỹ thời gian giành cho sản xuất ở xí nghiệp j;
x

m
1j
ijjij iij
.0x ; b ; m 1 i ; ax


3.1.3. Bài toán thực đơn:
Loại thức ăn
Chất dinh dỡng Nhu cầu tối thiểu hàng ngày
P
1
P
2

N
1
b
1
a
11
a
12

N
2
b
2
a
21
a

1
+ c
2
x
2
.
Tìm lợng x
1
, x
2
của từng loại thức ăn sao cho Z Min với các ràng buộc:
a
11
x
1
+ a
12
x
2
b
1 a
41
x
1
+ a
42
x
1
111

A đợc gọi là ma trận hệ số của các ràng buộc.
x =










=










=


1
2
1

Tìm các giá trị tối u x
*
= [x
*
1
, ,x
*
n
]
T
sao cho hàm mục tiêu:
Z = cx =

=

n
j
jj
Maxxc
1

với các ràng buộc:
Ax = b
x 0
2. Dạng chuẩn: ràng buộc ở dạng bất đẳng thức.
Tìm x sao cho Z = c.x Max

+=



+
+

6321
j
6 2
51
421
321
.0 074
6 1 j ; 0x
9 x x
12 x
18 x 30,5x
15 x 2x
xxxxZ
x
x
x
++++=
ữ=
=+
=+
=++
=
+

= Max(Z
1
) khi đó:
- c.x
*
- c.x hay c.x
*
c.x
Chứng tỏ x cũng là trạng thái tối u của bài toán Min.
Min (Z) = c.x
*
= - Max (Z
1
) = - Max (-Z).
3.3. Tính đối ngẫu và định lý cơ bản của bài toán tối u tuyến tính
3.3.1. Bài toán đối ngẫu:
Bài toán gốc (dạng chuẩn): tìm x = [x
1
, ,x
n
]
T
để hàm mục tiêu:
Z = c.x Max; c = [c
1
, , c
n
)
T
; b = [b

cy.A
T

Chuẩn
Sơ đồ đối ngẫu: x
1
x
2
x
n

Ngời ta đã chứng minh đợc: Giá trị tối u của bài toán chuẩn cũng là giá trị tối u
của bài toán đối ngẫu, nghĩa là: c.x
*
= b.y
*
.
3.3.2. Định lý cơ bản của bài toán tối u tuyến tính:

*
= [*, *, *, 0, 0]
T
.
3.4. Các phơng pháp giải bài toán tối u tuyến tính
3.4.1. Phơng pháp đồ thị:
Phơng pháp này đợc dùng khi số biến số 3.
1. Bài toán phẳng:
Ví dụ: Tìm x
*
= [x
1
*
, x
2
*
]
T
sao cho Z = c
1
x
1
+ c
2
x
2
Max
Các ràng buộc:
a
11

1
M
1
và N
2
M
2
.
+ Nếu là bất đẳng thức thì miền chấp nhận đợc là hình AN
1
OM
2
, bao gồm cả biên
AN
1
, AM
2
.
Vẽ các đờng cùng mục tiêu (đờng mức):
đối ngẫu
y
1

y
2y
m


1
c
2
c
n
Max
14
+ Cho một giá trị cụ thể Z = Z
0
. Vẽ đờng
1
2
1
1
0
2
x
c
c
c
z
x =

Thay đổi giá trị Z

2/ Nghiệm là đơn trị nếu 1 đỉnh của đa diện cho phép tiếp xúc với mặt cùng mục tiêu.
3/ Nghiệm là đa trị nếu tiếp xúc tại k đỉnh (k >1); k đỉnh này tạo nên 1 đơn hình (k-1)
chiều. Do đó có thể lấy (k-1) giá trị các biến tuỳ ý, còn n - (k-1) biến khác là hàm tuyến tính
của (k-1) biến tuỳ ý. Đó sẽ là cơ sở của phơng pháp đơn hình.
Chú ý:
Đơn hình là 1 hình có số đỉnh nhiều hơn 1 so với số chiều của không gian. Thí
dụ, trong không gian 2 chiều thì đơn hình là tam giác, trong không gian 3 chiều thì đơn hình
là tứ diện.
3.4.2. Phơng pháp đơn hình:
Phơng pháp này do nhà toán học Mỹ G.B. Dantzig đa ra năm 1948.
Nội dung: Tìm đỉnh tối u của đa diện các nghiệm cho phép bằng phơng pháp lần
lợt thử các đỉnh của đa diện. Để việc thử không phải mò mẫm, ngời ta đa ra thuật toán
để đi từ nghiệm xấu hơn tới nghiệm tốt hơn tức đi dần tới nghiệm tối u.
1. Nội dung phơng pháp đơn hình:
Giả sử có m ràng buộc độc lập đợc cho ở dạng chính tắc:
A.x = b (3.1)
1) Chọn biến cơ sở: đầu tiên ta chọn một điểm tuỳ ý của đa diện các nghiệm cho
phép, đó là tập n số (x
1
, , x
n
). Theo định lý cơ bản của bài toán tối u tuyến tính thì có m
số dơng, còn những số khác bằng không; gọi các biến dơng của điểm xuất phát là biến cơ
sở: (x
1
, x
2
, , x
m
, 0, 0, , 0).

*

x
2
=z
9
/
c
1
-
(
c
1
/
c
2
)
x
1
O x
1
* M
2
M
1
x
1
A
D
x

O x
1
* M
2
M
1
x
1
A
D
15
hay:





=++
=++
mmmm11m
1mm1111
bxa xa

b
x
a
x
a
(3.2)
Từ đó tìm đợc nghiệm xuất phát (hay nghiệm thử thứ 1):

++ 11,2211
; r = 1, 2, , m (3.3)
Hệ (3.3) gồm m phơng trình với m+1 biến, (3.3) có nghiệm đơn trị khi các phơng trình
tạo thành hệ phụ thuộc, do đó cột cuối cùng phụ thuộc tuyến tính vào các cột còn lại với hệ số y
i
:
a
r,m+1
= y
1
a
r1
+ + y
m
a
rm

hay a
r1
y
1
+ + a
rm
y
m
= a
r,m+1
(3.4)
Hệ (3.4) có nghiệm duy nhất là:
)

rm
(x
m
- y
m
) + a
r,m+1
= b
r
(3.5)
r = 1,2, m.
Hệ (3.5) là biến thể của (3.4) chỉ có các ẩn là khác nhau.
c) Chọn nghiệm thử thứ 2 cho (3.5) là:


),.(), ,.(x ),.(
)0()0()0(
2
(0)
2
)0(
1
)0(
1 mm
yxyyx
(3.6)
Vì có m+1 biến, do đó một trong các biến phải nhận giá trị không. Ngoài ra các biến
còn lại x
m+2
, , x

)0(
22
)0(
1
)0(
1
).( ).().(
+
++++
mmmm
cyxcyxcyx
Đặt số gia: Z
1
= Z
1
- Z
0
Z
1
=
[
]
[
]
11
)0()0(
22
)0(
111
) (

1
< 0: nghiệm mới xấu hơn nghiệm xuất phát.
* Z
1
> 0: nghiệm mới tốt hơn nghiệm xuất phát.
** Khi đã chọn đợc nghiệm mới bằng hoặc tốt hơn (Z
1
0) ta đa nó vào cơ sở và
cần phải loại bỏ bớt một nghiệm trong biến xuất phát (theo định lý cơ bản), chỉ có m nghiệm
dơng). Giả thiết đã đa biến mới thứ (m +1) vào cơ sở, khi đó có thể viết các biến mới của
phơng án theo (3.6). Một biến thứ i nào đó phải thoả mãn phơng trình:

0
y

x
(0)
i
)0
(
i
=

từ đó
)0(
i
)0
(
i
y

, Z
3
, cho đến khi thử hết các biến cơ sở.
Z
1
= [c
m+1
-
m+1
]
Z
2
= [c
m+2
-
m+2
]
Z
i
= [c
m+i
-
m+i
]
ở mỗi bớc cần tính hiệu suất (c
m+1
-
m+1
), kiểm tra Z
i

2
- 3x
3
+ 4x
4
Max
với các ràng buộc:





ữ=
=++
=++
4 1 i ,0x
800x10xx3x2
100
x
x
7
x
x
1
4321
4321

Giải:

1. Chọn biến cơ sở:

(0)
= 220; x
2
(0)
= 120
do đó nghiệm xuất phát là:
(220, 120, 0, 0) và Z
0
= 220 + 2x120 = 460
3. Thử đa x
3
vào cơ sở:
Phơng trình ràng buộc:




=+
=+
800xx3x2
100
x
7
x
x
321
321

Đó là hệ phơng trình phụ thuộc, nên hệ số của cột thứ ba phụ thuộc vào cột 1 và cột
2 với hệ số y

y
c
y
c
)0
(
2
)0
(
1
(0)
22
(0)
11
=+=+
Hiệu xuất c
3
-
3
= -3 + 2 < 0 nên Z
1
= (c
3
-
3
) = (-3 + 2) < 0
Nh vậy nếu đa x
3
vào cơ sở thì phơng án xấu hơn phơng án xuất phát.
17

6,1y ; 6,2
(0)
2
)0(
1
==y

Tính hiệu suất của x
4
:

4
= c
1
8,56,1.26,2
)0(
22
)0(
1
=+=+ ycy

Hiệu suất: (c
4
-
4
) = 4 - 5,8 < 0 Z
2
= (c
4
-

4
) sao cho hàm mục tiêu:
Z = 500x
1
+ 300x
2
+ 200x
3
+ 280x
4
Max
Các ràng buộc:





+++
+++
+++
2000 10xx5,2x8x5
1800 5,6x 1,2x x5x8
20002x 4x x5x10
4521
4321
4321

Giải:

Biến đổi về dạng chính tắc

+ 0x
7
= 0
Lập bảng 1
:
Chọn một biến khác để đa vào cơ sở:
Bảng 1.
s (cột xoay)

Biến cơ
sở
x
1
x
2
x
3
x
4
x
5
x
6
x
7

r
(dòng xoay)
x
5

===
dòng nào có tỷ số nhỏ nhất gọi là
dòng r (dòng xoay).
a
rs
= 10: gọi là phần tử xoay (pivot).
Lập bảng 2:

Đa biến x
1
vào cơ sở thay cho x
5
.
Tạo dòng chính: chia dòng r ở bảng I cho pivot a
rs

Các yếu tố của các dòng khác đợc tính theo công thức:
a
ij
(mới) = a
ij
(cũ)

- a
is
.a
rj
,

có nghĩa:

6
0 1 -2 -0,8 1 0 200

x
7
0 5,5 0,5 9 -0,5 0 1 1000
Z 0 -50 0 -180 50 0 0 100000

Lập bảng 3
: Bảng 3.
Biến cơ
sở
x
1
x
2
x
3
x
4
x
5
x
6
x
7

x
1
1 0,45 0,5 0 0,14 0,05 0 190

1
1 1,125 0 0 0,001 0,175 0,1 135
x
4
0 0,575 0 1 -0,07 0,025 0,1 105
dòng chính x
3
0 0,65 1 0 -0,26 0,45 0,2 110
Z 0 53,3 0 0 37,4 4,5 18 118900
ở bảng 4, các hệ số của Z đều 0, do đó dừng và không cần phải tiến hành bảng 5.
Biến cơ sở là tối u, các biến khác có giá trị 0, do đó:
x* = [x
1
, x
4
, x
3
]
T
= [135, 105, 110 ]
T
;
Z* = 500x135 + 200x110 + 280x250 = 118900.

3.5. Thuật toán đơn hình giải bài toán tối u tuyến tính tổng quát
3.5.1. Phát biểu bài toán:
Hàm mục tiêu:
y
ếu tố dòng mới
y


.mm
,
,2m
,
1mi ;b
x
a
2111
j
ijij
+++=


m
,
2mm
,
1mmi ;b
x
a
2121
j
ijij
++++==


x
j
0 ; b

; các biến giả tạo ứng
với ràng buộc và = đợc đánh số từ n+m
1
+1 đến n+m; các biến bù ứng với ràng buộc
đợc đánh số từ n+m+1 đến n+m+m
2
.
Trong hàm mục tiêu, các hệ số ứng với biến bù x
j
là c
j
= 0, các hệ số ứng với biến giả
tạo x
j
là c
j
> 0 đủ lớn, có thể chọn c
j
= M = max {|aij,|bi,|cj|}.
Ví dụ:
Tìm (x
1
, x
2
) sao cho hàm mục tiêu:
Z = 30x
1
+ 45x
2
Max


Trong thuật toán, ta đa bài toán về dạng chính tắc bằng cách thêm các biến bù x
3
, x
4
,
x
5
; các biến giả tạo x
6
, x
7
, x
8
,x
9
và các biến bù x
10
, x
12
, x
13
.
Các ràng buộc:
1) x
1
+ x
3
= 6000
2) x

8
+x
12
= 0
7) 2,5x
1
+2x
2
-x
9
+x
13
= 10000
Hàm mục tiêu:
Z = 30x
1
+45x
2
+0x
3
+0x
4
+0x
5
-Mx
6
-Mx
7
= Mx
8

x
*
1
= 6000; x
*
2
= 4000
Z
*
= 30x
*
1
+ 45x
*
2
= 360000. Bµi tËp
1. 2.

⎪
⎪
⎩
⎪
⎪
⎨
⎧
≤≤
≤≤

2
3
xx
6
x
-
x
x

x
2
1
6321
4321
4321

Z = 4x
1
+ 6x
2
→ max Z = 2x
1
+ 3x
2
+
minx
2
5
→


⎪
⎪
⎨
⎧
=≥
=+−−
=++−
=+−+
1,2, ,6 i ;0x
3- x- 2x xx3
4 x x x3x2
5 2x
_
x
3
x

x
I
5321
5432
6421

⎪
⎪
⎩
⎪
⎪
⎨
⎧

= 360000. 21
Chơng 4: Bài toán tối u hóa nguyên tuyến tính

4.1. Bài toán tối u nguyên tuyến tính
Trong các bài toán đã xét ở chơng 2, các biến có thể nhận các giá trị thực không âm.
Trong thực tế thờng gặp nhiều bài toán ở đó các biến số chỉ có thể nhận một số hữu hạn
hay đếm đợc giá trị, thờng là các giá trị nguyên. Ví dụ, thực là không đúng nếu cần thuê
2,3 ngời thợ. Vì thế trong chơng này đề cập đến các bài toán có các biến nguyên hay trên
các tập rời rạc. bài toán có dạng sau:

2
, , N
k
. Khi đó bằng cách đặt:
x = u
1
N
1
+ u
2
N
2
+ + u
k
N
k
,
với u
1
+ u
2
+ + u
k
= 1, u
j
{0, 1}, j = 1, 2, , k
Nh vậy biến rời rạc x có thể đợc thay thế bởi biến u
j
chỉ nhận giá trị 0 hay 1.
Tơng tự, nếu bất kỳ bài toán với các biến nguyên bị chặn tùy ý, đều có thể quy về

+ x
2
= 30
2x
2
+ x
3
= 50
x
i
0 và nguyên với i = 1, 2, 3.
Tổng quát ta ký hiệu:
a
ij
là số đoạn loại i thu đợc khi cắt theo mẫu j
b
i
là số đoạn loại i cần có
c
j
là rẻo thừa khi cắt theo mẫu j
x
j
là số thanh cắt theo mẫu j.
Ta có mô hình của bài toán nh sau:
Z=

=

n

và trên máy B là b
j
. Tìm thứ tự gia công các chi tiết để việc
gia công tất cả các chi tiết trên 2 máy là ngắn nhất.
Mỗi một thứ tự gia công sẽ tơng ứng với một hoán vị = (s
1
, s
2
, , s
n
) của n số tự
nhiên 1, 2, , n. Ký hiệu P là tập hợp tất cả các hoán vị của {1, 2, , n}.
Thời gian gia công theo thứ tự bằng:
t() =

==
+
n
j
j
n
j
s
bx
j
11
(4.3)
Trong đó
j
s

++ kk
ss
ba ) (4.4)
Với mọi k = 1, 2, , n-1.
Dựa vào định lý trên ta có thuật toán để tìm thứ tự gia công theo yêu cầu:
1) Ghi lại thời gian công các chi tiết trên mỗi máy vào bảng thời gian gia công:
Chi tiết 1 2 n
Máy A
Máy B
a
1
a
2
a
n

b
1
b
2
b
n

2) Chọn số nhỏ nhất trong tất cả các số ghi ở bảng nếu số đó nằm trong hàng máy A,
thì chi tiết tơng ứng đợc xếp gia công đầu tiên; nếu số đó nằm trong hàng máy B, thì chi
tiết tơng ứng xếp gia công sau cùng.
3) Trong bảng thời gian xóa đi cột tơng ứng với chi tiết đã đợc sắp xếp trình tự.
4) Nếu mọi chi tiết đã đợc sắp xếp trình tự thì dừng: Thứ tự sắp xếp đó là tối u. Nếu
không, thì quay lại bớc 2) đrre sắp xếp thứ tự cho các chi tiết còn lại.
Chú ý: Trờng hợp trong bảng có nhiều số dạt giá trị nhỏ nhất, ta có thể chọn một số bất kỳ

ij
là số hàng lọai j đợc chở trên công-ten-nơ
thứ i, y
i
là biến nhận giá trị 1 khi công-ten-nơ thứ i đợc dùng, ngoài ra thì nhận giá trị 0. Bài
toán đa đến mô hình:
Z =
Miny
m
i
i


=1

Với các điều kiện:
i
n
i
ijj
Tyxa

=1
, i = 1, 2, , m
i
n
i
ijj
Kyxb


130.000
80.000
Thời gian có
Mỗi tháng
600 300 300 140
2. một xởng dự định mua hai loại máy để in hình lên vải. Máy A có thể in 100m/ph và
chiếm 50m
2
diện tích sản xuất, còn máy b có thể in 200m/ph và chiếm diện tích là 140m
2
.
xởng cần in ít nhất là 600m/ph và diện tích mặt bằng tối đa là 350m
2
. Giá mua là 22 triệu
đồng cho 1 máy loại A và máy loại B là 42 triệu đồng. Hỏi cần mua bao nhiêu máy in mỗi
loại để chi phí là ít nhất.
24
3. Có 2 loại sản phẩm A, B đợc gia công trên 4 máy I, II, III, IV. Thời gian gia công mỗi
loại sản phẩm trên từng máy nh bảng sau:
Máy I Máy II Máy III Máy IV
Sản phẩm A (giờ) 2 4 3 1
Sản phẩm B (giờ) 1/4 2 1 4
Thời gian sử dụng các máy theo thứ tự 45, 100, 300, 50 giờ. Một đơn vị sản phẩm A lãi 600
đồng, còn sản phẩm B là 400 đồng. Nên sản xuất mỗi loại bao nhiêu để lãi tối đa.
4. Một Công ty lọc dầu sử dụng ngay nguồn dầu thô nặng có giá 300 đồng/lít và dầu thô nhẹ
có giá 350đồng/lít. Công ty sản xuất 3 loại sản phẩm Gasoline, Heating Oil và Jet Fuel và
lợng 3 loại dầu trên có đợc từ việc lấy từ 1 lita dầu thô nặng và nhẹ cho ở bảng sau:
Gasoline Heating oil Jet Fuel
Dầu thô nặng 0.3 0.2 0.3
Dầu thô nhẹ 0.3 0.4 0.2


25
Chơng 5: bài toán tối u động
Tối u động đợc dùng một cách có hiệu quả để giải một số loại bài toán tối u phi
tuyến. Nó xuất hiện trong kết quả khi nghiên cứu các bài toán, ở đó có sự thay đổi theo thời
gian. Về sau công cụ này đã đợc phát triển để giải các bài toán không liên quan đến sự thay
đổi theo thời gian.
Ta hiểu tối u động là phơng pháp tính dựa trên công cụ các công thức truy hồi, nó
đã đợc nghiên cứu khá kỹ lỡng trong các công trình của R. Bellman.
5.1. Bản chất của bài toán tối u động
Để làm sáng tỏ các t tởng cơ bản của tối u động ta sử dụng bài toán tối u trong
quá trình phân phối tài nguyên.
Giả sử ta có số lợng hạn chế các tài nguyên nào đó. Có thể hiểu là máy móc, tiền,
sức lao động,
Những tài nguyên hiện có có thể đợc sử dụng trong nhiều phơng pháp sản xuất
khác nhau. Kết quả của việc sử dụng tất cả hoặc một phần tài nguyên đó trong một phơng
pháp sản xuất nào đó là một khoản thu nhập, mà khối lợng của nó vừa phụ thuộc vào số
lợng tài nguyên đợc sử dụng vừa phụ thuộc vào phơng pháp sản xuất đợc chọn. Bài toán

, , y
n
) = g
1
(y
1
) + g
2
(y
2
) + + g
N
(y
N
) (5.1)
Ký hiệu y là số lợng tài nguyên hiện có, ta đi đến bài toán Max sau: Cần làm Max
hàm mục tiêu D(y
1
, y
2
, , y
N
) với điều kiện sau:
y
1
+ y
2
+ + y
N
= y (5.2)