165

Chương 7
GIẢI PHƯƠNG TRÌNH VÀ TỐI ƯU HÓA
7.1 GIẢI PHƯƠNG TRÌNH
7.1.1 Giải phương trình một biến số
Xét phương trình một biến có dạng:
f(x) = 0 (7.1)
Nếu hàm f(x) liên tục trong khoảng [a,b] và đổi dấu tại hai đầu mút của
khoảng, tức là f(a)fb)<0, thì trong [a,b] chứa ít nhất 1 nghiệm của phương trình
(7.1). Khi đó [a,b] được là một khoảng chứa nghiệm của phương trình. Nếu trong
khoảng [a,b] có đúng một nghiệm thì nó được gọi là khoảng phân ly nghiệm của
phương trình. Khi giải phương trình (7.1) theo các phương pháp số, một điều rất
quan trọng là phải tìm được các khoảng phân ly nghiệm. Có 2 phương pháp
thường được sử dụng để tìm các khoảng phân ly nghiệm:
 Phương pháp khảo sát hàm số: dựa vào các tính chất sau:
Định lý 7.1 Nếu trong khoảng [a,b] hàm f(x) liên tục, đơn điệu và hàm số
đổi dấu tại hai đầu mút của khoảng thì [a,b] là một khoảng phân ly
nghiệm của phương trình f(x)=0.
Như vậy khi xét bảng biến thiên hàm số, khoảng phân li nghiệm là khoảng
mà trong đó đạo hàm không đổi dấu và hàm số đổi dấu tại 2 đầu mút.
 Phương pháp đồ thị:
y

y=h(x)

y=g(x)


1

3


1
3
+


y’ + 0 - 0 +

y

M +
 -

m
Với
1 1 1
( ) 1 0
3 3 3 3
M f
      
, do đó
1
( ) 0
3
m f

x

. Khi đó dạng đồ thị của chúng là:

167
y g =
2
1
x h=lgx

1

x
Hình 7.2 Dáng điệu đồ thị của các hàm h(x) = lgx và
2
1
( )
g x
x

Từ đồ thị trong hình 7.2 ta tính giá trị hàm tại một số điểm đặc biệt:
x = 1 y = 0 - 1 < 0;
x =10 y =1
1
100

> 0.

thì dừng thủ tục và x là nghiệm xấp xỉ cần tìm;
Ngược lại chuyển sang bước k+1.
Quá trình lặp của thủ tục sẽ ngừng khi b- a 

. Do đó khi kết thúc thủ
tục ta được x

là nghiệm xấp xỉ cần tìm.

168
y

a x

b x Hình 7.3 Phương pháp Chia đôi
Định lý 7.2 Nếu f(x) liên tục trong khoảng phân ly nghiệm [a,b] thì phương
pháp Chia đôi kết thúc sau một số hữu hạn bước lặp và tìm được
nghiệm xấp xỉ của phương trình (7.1) trong khoảng đó.
Do sau mỗi bước lặp độ dài khoảng phân ly nghiệm là
b a

sẽ giảm đi đúng
một nửa nên có thể dễ dàng thấy thủ tục trên sẽ dừng lại ở bước k thỏa mãn:
k

Nội dung hàm Binary.m:

169
% BINARY : Giai phuong trinh bang phuong phap Chia doi.
% Cu phap x =Binary (FUN,a,b,Tol).
% FUN – Ten ham cua phuong trinh;
% a, b : 2 so xac dinh khoang phan ly nghiem [a,b];
% Tol - Sai so tuyet doi , mac dinh Tol =1.e-6;
%
function x = Binary(FUN,a,b,Tol)
if nargin==3
Tol=1e-6;
end
Sig = sign (feval(FUN,a));
x = (a+b)/2;
while abs(b-a)>Tol
if Sig*feval(FUN,x)>0
a = x;
else
b=x;
end;
x=(a+b)/2;
end
Thí dụ 3. Giải phương trình :
2
1
0
lg x
x
 


[a, b].
Bước k=1,2,3,…
Tính x
k
=

(x
k-1
). (7.6)
Công thức lặp (7.6) được gọi là hội tụ nếu
lim
k
k
x



. Tất nhiên chúng ta
chỉ quan tâm đến các công thức lặp hội tụ. Định lý sau đây cho ta tiêu chuẩn
nhận biết một công thức lặp đơn là hội tụ.
Định lý 7.3 Xét công thức lặp (7.6). Giả sử:
1) [a, b] là một khoảng phân ly nghiệm của phương trình f(x) =0;
2) Mọi x
k
tính theo (7.6) đều thuộc [a, b];
3) Tồn tại hằng số q sao cho hàm

(x) có đạo hàm



hay
1
| |
1
k k k
q
x a x x
q

  

. (7.7)
Thí dụ 4. Phương trình
x
3
- x – 1 = 0

171
có một khoảng phân ly nghiệm là [1,2] (xem mục 7.1.1).
Nếu ta chọn công thức lặp x = x
3
+1 thì

(x)= x
3
+1 và

’(x)=3x
2

’(x) | <
3
1
1
3 4
q
 
với mọi x

 [1,2]. Do đó công thức lặp sẽ hội tụ với
mọi x
0
[1,2]. Bây giờ bạn hãy chọn x
0
=1 và tính theo công thức
3
1
1
k k
x x

 

qua 5 bước lăp:
>> Phi=inline('(x+1)^(1/3)');
>> x=1;
>> for k=1:5
x=Phi(x)
end;
Kết quả của các bước lần lượt là:

của phương trình trong khoảng này với sai số tuyệt đối
không quá

. Trước hết ta có nhận xét: phương trình cát tuyến của đường cong
y=f(x) đi qua 2 điểm (a,f(a)) và (b,f(b)) là:
( )
( ) ( )
y f a x a
f b f a b a
 

 
.
Cho y =0, ta xác định được cát tuyến cắt trục hoành tại điểm có hoành độ:

. ( ) . ( )
( ) ( )
a f b b f a
x
f b f a



. (7.8)
Vì vậy để giải phương trình có thể thực hiện theo thủ tục lặp sau đây:
 Thủ tục tính toán
- Bước lặp k=1,2,
+ Tính
. ( ) . ( )
( ) ( )


y

a x
k


b x

Hình 7.4 Phương pháp dây cung

173
Có thể chứng minh rằng: nếu hàm số f(x) liên tục và khả vi trong khoảng
phân ly nghiệm [a,b], đồng thời


[ , ]
min '( )
x a b
m f x


>0 thì thuật toán trên sẽ kết
thúc sau một số hữu hạn bước lặp. Tuy nhiên trong nhiều trường hợp việc đánh
giá m rất khó. Mặt khác nếu m quá nhỏ thì ta cần phải thực hiện nhiều bước lặp
mới thỏa mãn điều kiện dừng lặp. Vì vậy khi thực hiện phương pháp Dây cung,
nếu thấy hai lời giải xấp xỉ liên tiếp có x

.
Nội dung file Arc.m:
% ARC : Giai phuong trinh bang phuong phap day cung;
% Cu phap x = Arc(FUN,a,b,Tol)
% FUN – Ten ham;
% a, b : 2 so xac dinh khoang phan ly nghiem [a,b];
% Tol - Sai so tuyet doi , mac dinh Tol =1.e-6
function x = Arc(FUN,a,b,Tol)
if nargin==3
Tol=1e-6;
end
x=(a+b)/2;
fa=feval(FUN,a); fb=feval(FUN,b);

174
while feval(FUN, x -Tol)*feval(FUN, x+Tol)>0
x=(a*fb - b*fa) / (fb - fa);
if fa*feval(FUN,x)>0
a = x; fa=feval(FUN,a);
else
b= x; fb=feval(FUN,b);
end;
end
Thí dụ 5. Giải phương trình:
2
1
lg 0
x
x
 

2
0
2
x x
, với c[a,b].

175
Khi đó phương trình tiếp tuyến của đường cong y=f(x) tại x
0
là:
y = f(x
0
) + f’(x
0
) (x-x
0
) (7.9)
Do đó, nếu f ’(x
0
) ≠ 0 thì từ (7.9) suy ra:
0
0
0
( )

'( )
f x
x x
f x
 

k
f x
x x
f x



 
+ Nếu
k
f ( x )
m


thì dừng thủ tục và x
k
là nghiệm xấp xỉ cần tìm;
Ngược lại thì chuyển sang bước k+1.
Cũng như phương pháp Dây cung, trong nhiều trường hợp, việc đánh giá


[ , ]
min '( )
x a b
m f x

 rất khó. Mặt khác khi m quá nhỏ thì cần phải thực hiện nhiều
bước lặp mới thỏa mãn điều kiện dừng lặp. Chú ý rằng khi x
k
đã khá gần

Khi đó công thức tính lặp trong thủ tục là: x
k
= x
k-1
-
1
1
k
k
f ( x )
f '( x )

176
có thể được thay bởi công thức:
1
1
1 1
. ( )

( ) ( )
k
k k
k k
f x
x x
f x f x


bảo đảm phương pháp Newton chắc chắn hội tụ thì bạn cần phải xét thêm điều
kiện về các đạo hàm cấp 1 và 2 đồng thời phải chọn x
0
thích hợp.
7.1.6 Một số hàm sử dụng để giải phương trình của Matlab.
 Hàm FZERO
Cú pháp:
[ x f ] = fzero(FUN,Init) :
Giải thích. Hàm FZERO tìm không điểm của một hàm số xác định bởi
tham số FUN và sử dụng xấp xỉ đầu Init.
- Nếu Init là một số thì nó xác định xấp xỉ đầu của lời giải;
- Nếu Init là vector 2 chiều thì nó xác định khoảng chứa nghiệm cần tìm,
khi đó Matlab sẽ kiểm tra điều kiện hàm FUN phải đổi dấu tại 2 biên của
khoảng.
- Các tham số ra: x là lời giải xấp xỉ cần tìm và f là giá trị của hàm tại x.

177
Thí dụ 7. Soạn file Myfunct.m có nội dung như sau:
% Function for computing the zeros of a function
function z=myfunct(x)
z = tan(x) – x;
Sau đó lần lượt gọi hàm:
>> fzero('Myfunct',[-1 1])
Zero found in the interval: [-1, 1].
ans =
0
>> fzero('Myfunct',[-0.5 1])
Zero found in the interval: [-0.5, 1].
ans =
-1.1801e-008

ans =
-1.0000
-0.3333
>> x= roots([1 2 3 2 1])
x =
-0.5000 + 0.8660i
-0.5000 - 0.8660i
-0.5000 + 0.8660i
-0.5000 - 0.8660i

7.2 GIẢI HỆ PHƯƠNG TRÌNH PHI TUYẾN
Hệ phương trình phi tuyến là hệ n phương trình n ẩn có dạng như sau:



 
 
1 1 2 3
2 1 2 3
1 2 3
0
0
0
n
n
n n
f x ,x ,x , x
f x ,x ,x , x

f x ,x ,x , x

( )

( )
n
f x
f x
f x
 
 
 
 
 
 
.

179
Đây là một bài toán khó. Sau đây chúng ta sẽ nghiên cứu một số phương
pháp giải hệ (7.11). Tính liên tục và khả vi của các hàm số được khảo sát luôn
luôn được gải thiết trong các phương pháp này.
7.2.1 Phương pháp Lặp đơn
Đầu tiên đưa hệ phương trình (7.11) về dạng tương đương:


 
 
1 1 1 2 3
2 2 1 2 3
1 2 3
n
n

= (x
1
(0)
,x
2
(0)
, ,x
n
(0)
)
- Bước lặp k =1,2,3
Tính x
i

(k+1)
=

i
(x
1
(k)
,x
2
(k)
, ,x
n
(k)
) với
1,
i n

  
  
 
 
  
 
 
  
 
  
 
 
 
 
  
 
 
  
 
: là ma trận Jacoby của

(x).
Định lý 7.4 Nếu các hàm

i
(x),
1,
i n

xác định, liên tục và khả vi trong

chứa 1 nghiệm x=α của hệ phương trình (7.11).
Đầu tiên ta tính ma trận Jacoby của hàm f(x):
1 1 1
1 2
2 2 2
1 2
1 2
( ) ( ) ( )

( ) ( ) ( )

( )

( ) ( ) ( )

n
n
n n n
n
f x f x f x
x x x
f x f x f x
x x x
F x
f x f x f x
x x x
  
 
 
  

(x
(k-1)
).f(x
(k-1)
). (7.14)
Chú ý:
- Ưu điểm của phương pháp Newton hội tụ rất nhanh nếu x
(0)
được chọn
khá gần nghiệm α của hệ (7.11). Mặt khác phương pháp Newton không đòi hỏi
phải thay đổi mô hình bài toán như phương pháp Lặp đơn.
- Từ công thức (7.14) ta thấy tại mỗi bước lặp cần phải tính một ma trận
nghịch đảo F
-1
(x
(k-1)
, cho nên thuật toán đòi hỏi khối lượng tính toán rất lớn. Để
khắc phục điều này và làm tăng tốc độ tính toán, nếu tại bước t nào đó
x
= x
(t)
đã
khá gần nghiệm α của hệ phương trình thì nên cố định F
—1
(
x
) và sử dụng công
thức sau đây ở các bước lặp tiếp theo:
x
(k)

- Các hàm g
i
(x),
i 1,m

: gọi là các hàm ràng buộc. Mỗi bất đẳng thức gọi là
một ràng buộc.
- Tập
i
{ | ( ) ( , )b , 1, }
i
D x X g x i m
     
: gọi là miền ràng buộc hay tập các
phương án chấp nhận được. Mỗi phần tử xD gọi là một phương án hay lời giải
chấp nhận được.
- Phương án x*

D làm cực tiểu (cực đại) hàm mục tiêu gọi là phương án
tối ưu hay lời giải tối ưu. Cụ thể là: f(x*)

f(x) với

x

D đối với bài toán max
hoặc f(x*)

f(x) với

7.4 QUI HOẠCH TUYẾN TÍNH
7.4.1 Bài toán qui hoạch tuyến tính (QHTT)
Bài toán qui hoạch tuyến tính tổng quát có dạng như sau:
Tìm min (hoặc max) của hàm
n
j j
j 1
F(x) c x




thỏa mãn các điều kiện:

n
ij j i
j 1
a x , , b ,i 1,m

   

.
Đặt D là tập các phương án của bài toán qui hoạch tuyến tính:
D= {xR
n
:
n
ij j i

1
( )
n
j j
j
F x c x





min
Thỏa mãn các điều kiện:

1
, 1,
0, 1,
n
ij j i
j
j
a x b i m
x j n


 





j j
j
F x c x





min
thỏa mãn các điều kiện:

1
, 1,
0, 1,
n
ij j i
j
j
a x b i m
x j n


 




 



min
D={ x

R
n
| A x = b , x

0 }
Với các giả thiết : b

0 , rank(A)= m < n thì tập các phương án chấp nhận
được D là đa diện có thứ nguyên n-m.
 Đường lối chung của thuật toán đơn hình (Simplex)
Thuật toán đơn hình bao gồm các bước cơ bản như sau:
Bước 1. Tìm phương án cực biên xuất phát
Kết quả của bước này là một trong hai khả năng:
- Nếu phát hiện bài toán không có phương án thì kết thúc thuật toán.
- Nếu tìm được phương án cực biên x
0

D thì chuyển sang bước 2.
Bước 2. Kiểm tra tiêu chuẩn tối ưu đối với phương án tìm được.
Có hai khả năng có thể xảy ra:
- Nếu x
0
thỏa mãn tiêu chuẩn tối ưu thì đặt x
*
= x
0
, tính F

*
hay phát hiện bài toán không có phương án tối ưu.

185
 Chi tiết hóa các bước của thuật toán
Bước 1. Tìm phương án cực biên xuất phát x
0
D
Giả sử D có một phương án cực biên là


0 0 0 0
1 2
n
x x ,x , ,x

. Vì là phương
án cực biên nên x
0
phải thỏa mãn chặt n ràng buộc độc lập tuyến tính. Do x
0
là
một phương án nên x
0
đã phải thỏa mãn m phương trình ràng buộc dạng Ax=b,
nên nó còn phải thỏa mãn chặt thêm n-m ràng buộc dạng x
j
=0 nữa. Không làm
mất tính tổng quát, giả sử:
0 0 0



  

(7.17)
Để thuận tiện cho việc nghiên cứu, người ta đưa thêm vào các ký hiệu:



1,2,3,
J m
  : gọi là tập chỉ số cơ sở của x
0
;

1
2
, j=1,n

j
j
j
mj
a
a
A
a
 
 
 

với j

J gọi là các biến cơ sở ; Còn các biến x
j
với j

J gọi là
các biến phi cơ sở. Các thành phần của một phương án cực biên tương ứng với
các biến phi cơ sở đều bằng 0.
Khi đó hệ phương trình (7.17) có thể viết thành Bx
J
=b. Do giả thiết
rank(B)= rank(A) = m nên
0
J
x
là nghiệm của hệ (7.17):

0
J
x
=B
-1
b  0 và
0 0 0 0 0
1 2 3
( , , , , ,0,0.0, ,0).
m
x x x x x
Nếu

sao cho ||J|| = m và B=(A
j
)
j

J
là ma trận không suy
biến. Khi đó các vector của B tạo thành một cơ sở của R
m
. Khi đó:
- Nếu B
-1
b

0 thì B gọi là một cơ sở chấp nhận được của bài toán QHTT,
đồng thời nó xác định một phương án cực biên x
0
nào đó của bài toán.
- Nếu điều kiện B
-1
b

0 không thỏa mãn thì B không phải là cơ sở chấp
nhận được của bài toán. Khi đó ta phải chọn lại m cột độc lập tuyến tính khác của
ma trận A…Cứ như vậy cho đến khi tìm được cơ sở chấp nhận được.
Cách làm như trên mang tính may rủi, tốn công sức. Vì vậy, khi chưa biết
cơ sở xuất phát của bài toán QHTT, để giải bài toán ta thường áp dụng một trong
hai phương pháp: phương pháp đơn hình hai pha và phương pháp hàm phạt.
Thực chất của cả hai phương pháp này là đưa thêm vào bài toán QHTT gốc
một số biến giả để bài toán mở rộng là bài toán QHTT dạng chính tắc có sẵn một

m
. Ta có
thể phân tích các vector A
k
với
k J

theo cơ sở này:
A
k
=
jk j
j J
v A



k J

(7.18)
Đặt
k jk j k
j J
v c c

  

với k=1,2, : gọi là các số kiểm tra. (7.19)
Định lý 7.6 (Công thức số gia của hàm mục tiêu) Nếu x
0


F(x).

(7.21)

187
Bây giờ nếu đặt:
0
j j j jk k
k J
x x x v x

    

là số gia của biến x
j
và


F x


=
 
0
( )
k k
k J
F x F x x


là phương án tối ưu của bài toán
QHTT; Ngược lại nếu nó không thỏa mãn tiêu chuẩn (7.22) thì khi đó 
k J


sao cho 
k
>0 nên ta cần cải tiến phương án. Khi đó có thể tồn tại phương án cực
biên tốt hơn x
0
và cũng có thể bài toán không có phương án tối ưu . Định lý sau
đây giúp ta nhận biết bài toán không có phương án tối ưu.
Định lý 7.8 (Tiêu chuẩn nhận biết bài toán không có phương án tối ưu). Giả
sử x
0
là phương án cực biên tương ứng với cơ sở B=(A
j
)
j

J
. Nếu

k J

sao cho

k
>0 và v
jk

1
) < F(x
0
). Gọi B
1
là cơ sở chấp nhận được
tương ứng với x
1
. Do x
0
chưa phải phương án tối ưu nên có ít nhất một cạnh kề
với x
0
mà khi đi trên cạnh đó từ x
0
hàm mục tiêu giảm. Để đơn giản cho việc tính
toán, ta tìm x
1
là một đỉnh kề của x
0
nghĩa là hai cơ sở tương ứng chỉ khác nhau
đúng 1 vector, nghĩa là:
B
1
= B\ {A
p
}

{A
q

thường chọn:

188

ax
q k
k J
m

  
. (7.24)
Khi đó này A
q
tương ứng với phương của cạnh có tốc độ giảm nhanh nhất
của hàm mục tiêu vì:





1 0 0 1
( ) F x
k k q q
k J
F x F x x x

    

.
Có hai trường hợp có thể xảy ra:

v
pq jq
x x
v v


. (7.25)
Tính hợp lý của (7.25) được giải thích như sau: việc phải chọn A
p
đưa ra
khỏi cơ sở phải bảo đảm phương án mới x
1

0. Theo công thức (7.20) ta có:
1 0 1 0 1
0
j j jk k j jq q
k J
x x v x x v x

    

với j

J
1
= J\{p}

{q}. (7.26)
- Nếu v

v
jq
x
x
v


, vì vậy ta cần
phải chọn A
p
tương ứng với:
0 0
1
0
min
jq
p j
q
v
pq jq
x x
x
v v

 
.
7.4.3 Thuật toán đơn hình dạng bảng
 Bảng đơn hình xuất phát :
Xét bài toán QHTT dạng chính tắc:


 
0 1 1 1 1 1
1 2 1 2
, , , , , , ,
J n n
x B b H B A B A B A B A V V V
    
     
.
Sau đó đưa các kết quả tính toán vào bảng đơn hình. Trong bảng đơn hình
các số kiểm tra được tính theo công thức:
k jk j k
j J
v c c

  

nếu k

J và

k
=0 nếu k

J.
Nếu


1,2, ,
J m

2
… A
m
A
m+1
… A
k
… A
q
… A
n
A
1
c
1
x
1 1 0 0
v
1,m+1
v
1,k
v
1,q
v
1,nA
2
c

v
j,n

/
j jq
x v

… … …
A
p
c
p
x
p

0 0 0
v
p,m+1
v
p,k
v
p,q
v
p,n

/
p pq
x v

… … …

…

k
…

q
…


n

 Sử dụng bảng đơn hình
Từ bảng đơn hình ta phân tích:
- Nếu

k

J

k

0 thì dừng thuật toán: x
0
là phương án tối ưu;
Ngược lại cần chọn A
q
đưa vào B
1
theo qui tắc:
max

đưa ra khỏi B theo qui tắc: