BÀI TẬP MÔN TỐI ƯU HÓA
CHƯƠNG III
Bài 1. Chứng tỏ rằng bài toán sau luôn có phương án cực biên tối ưu
f(x) = - x
1
+ x
2
- x
3
=> min









−≥+
≤−
≤+
≥−+−
−≥+−
12xx
18xx3
20x2x
20x2x5x3
20xx4x2
21
32

13xx2x
10x5x4xx2
4321
431
421
431
4321
( )
4,1j3x
j
=≤
Bài 3. Cho bài toán f(x) = 3x
1
+ x
2
+ 2x
4
+ 5x
6
=> min





=+−+
−≤−+−
≥++−
5x2x3xx2
18x4x3x2x




≤+
≥−
≥+
≤−++−
−≥++−
10x7x4
3x5x3
5x6x
4xx4xx3
2x2xxx2
21
32
41
4321
4321
Chứng tỏ x = (- 1, 2, 0, 1) là PACB tối ưu.
Bài 5. Cho bài toán
∑
=
⇒=
n
1j
j
maxx)x(f

( )
n,1j1x0

Bài 7. Cho bài toán (A) dạng
f(x) = 2x
1
+ x
2
+ 4x
3
+ 5x
4
+ 2x
5
+ 4x
6
=> min





≤+−+++−
≤+++−
−≤+−−+
7x5x2xx4x2x
14xx3x2xx2
1x3x2xx2x
654321
65431
65432
x
j

4321
=≥







=++−
≤+−+
=+++
=++−

Bài 9. Cho bài toán QHTT dạng:
f(x) = 2x
1
+ 5x
2
+ 3x
3
+ c
4
x
4
+ 2x
5
=> min
( )
5,1j0x

1
+ 4x
2
+ 3x
3
+ x
4
=> min





≥++−
−≥−+−
≤++−
33xx3xx2
6xx2x
31xx3x3x4
4321
321
4321
( )
4,1j0x
j
=≥
a. Giải bài toán bằng thuật toán đơn hình; xác định phương án tối ưu có
x
4
= 28.

=−+−
14x2xxxx
15x3xx6
20xx2x
8x4xx2x4
54321
543
541
5431
( )
5,1j0x
j
=≥
a. Giải bài toán bằng thuật toán đơn hình.
b. Tìm một PA có x
3
> 0 và f(x) = - 27.
Bài 12. Cho bài toán:
f(x) = x
1
+ x
2
+ c
3
x
3
+ 2x
4
+ 2x
5