Bai toan quy hoach tuyen tinh

1.3 MÔ HÌNH BÀI TOÁN QUY HOẠCH THUYẾN TÍNH
1.3.1 Dạng tổng quát của bài toán quy hoạch tuyến tính.
ƒ(x) = c1x1 + c2x2 → min(max)

aijxj ≥ bi, i =1,2,…,m
aijxj ≤ bi, i =m1+1,…,m1+m2
aijxj = bi, i =m1+m2 +1,…,m

xj ≥0, j =1,2,…,n1, xj ≤ 0, j = n1 +1,…,n
Ràng buộc chính
Ràng buộc về dấu
Hàm mục tiêu
Mỗi vectơ x = (x1, x2, x3, …, xn) thỏa mãn tất cả các ràng buộc được gọi là một phương án.
Giá trị mà tại đó hàm mục tiêu đạt giá trị lớn nhất ( hoặc nhỏ nhất) được gọi là phương án tối ưu hay một lời giải của bài toán đã cho. Giá trị ấy được gọi là giá trị tối ưu của hàm mục tiêu trên tập các phương án.

Bài toán quy
hoạch tuến tính
Có lời giải nếu:
- Có ít nhất một phương
án tối ưu
Không có lời giải nếu:
- Miền ràng buộc rỗng D = Ø.
- Có phương án nhưng không
có phương án tối ưu.
1.3.2 Dạng chính tắc và chuẩn tắc của bài toán quy hoạch tuyến tính
1.3.3 chuyển đổi dạng bài toán quy hoạch tuyến tính.
Ta có thể đưa bài toán bất kì về dạng chính tắc hay chuẩn tắc như sau:
Mỗi ràng buộc đẳng thức aijx’j = bi có thể thay bởi hệ bất đẳng thức
aijx’j ≤ bi và aijx’j ≥ bi
Mỗi ràng buộc bất đẳng thức
aijx’j ≤ bi và aijx’j ≥ bi
Có thể đưa về ràng buộc đẳng thức nhờ thêm vào một biến mới gọi là biến bù hay ẩn bù xn+i≥0
aijx’j +xn+1= bi hoặc aijx’j - xn+1= bi
Một ràng buộc bất đẳng thức aijx’j ≤ bi có thể viết thành - aijx’j ≥ -bi hoặc ngược lại

Mỗi ẩn xj không có ràng buộc về dấu đều có thể viết thành hiệu của hai ẩn mới không âm: xj = xj+ – xj- với xj+ ≥0, xj- ≥0. Còn nếu xj ≤0 thì đặt biến mới xj = - tj với tj ≥0

Bài toán tìm cực đại :ƒ→max có thể đưa về bài toán tìm cực tiểu :g = - ƒ →min với cùng các ràng buộc

Ví dụ 1: đưa các bài toán sau về dạng chính tắc:
a) ƒ(x) = 4x1 + 3x2 + 4x3→min
2x1 + 3x2 + x3 ≥ 6
x1 + 2x2 +2x3 ≥ 7
3x1 + 2x2 + x3 ≥ 9
xj ≥ 0, j =1,3
b) ƒ(x) = 5x1 + 2x2 - 4x3→max
4x1 + 7x2 + x3 ≥ 3
x1 - x2 - 2x3 ≤ - 1
2x1 + 3x2 + 6x3 = 11
x1 ≥ 0, x2 ≥ 0
Giải
Giải
1.4 PHƯƠNG PHÁP HÌNH HỌC GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH HAI BIẾN
Xét bài toán quy hoạch tuyến tính với hai biến số:
ƒ(x) = c1x1 + c2x2 → min(max)
aijxj ≥(≤)bi, i =1,…,m
xj ≥, j =1,2

Ta có thể giải bài toán trên bằng phương pháp hình học như sau:
Bước 1: biểu diễn tập phương án X trên mặt phẳng Ox1x2.
Bước 2: biểu diễn vectơ pháp tuyến và hàm mục tiêu.
Bước 3: Giải bài toán
Ví dụ 4: cho bài toán quy hoạch tuyến tính:
ƒ(x) = -2x1 +x2 → min
x1 + x2 ≥ 2
x2 – 3x3 < 6
4x1 + 5x5 ≤ 20
x1≥0 , x2≥0
Hãy giải bài toán trên bằng phương pháp hình học.
Biểu diễn tập nghiệm của bài toán đã cho trên mặt phẳng tọa độ Ox1x2 ta xác định được tập phương án X của bài toán là ngũ giác lồi ABCDE với
C(0,1); D(2,0); B(0,4); A(45/11,8/11); E(3,0)
C
D
E
A
B
Biểu diển vectơ pháp tuyến n =(-2,1) và đường thẳng (d): z = -2x1 + x2
Vì đây là bài toán min nên ta tịnh tiên (d) ngược hướng với n. Như vậy ta có điểm A là vị trí tới hạng hay là phương án tối ưu.
Tọa độ của điểm A được xác định bởi hệ phương trình sau:
2x1-x3 =6 x1=45/11
4x1 + 5x2 = 20 x2=8/11
Phương an tối ưu của bài toán đang xét là: x=(45/11 , 8/11)
1.5 Đại cương về tập lồi trong không gian.

1.5.1 tổ hợp lồi
Giả sử x1, x2, …, xm là các điểm trong không gian Rn. Điểm được gọi là tổ hợp lồi của các điểm ấy nếu tồn tại các số không âm λ1x1, λ2x2, …, λmxm với λ1 + λ2 + λ3 +…+ λm =1 sao cho x = λ1x1 + λ2x2 + λmxm.


Trường hợp x là tổ hợp lồi của hai điểm x1, x2 ta thường viết x = . λ.x1 + (1- λ)x2, 0 ≤ λ ≤ 1. nếu 0 < λ < 1 thì ta nói x là tổ hợp lồi thực sự của hai điểm ấy.

1.5.2 tập hợp lồi
Tâp hợp L chứa trong Rn được gọi là tập hợp lồi nếu hễ như L chứa hai điểm nào đó thì nó chứa cả đoạn thẳng nối hai điểm ấy ( tức là nếu x và y là hai điểm bất kỳ thuộc L thì L chứa mọi điểm có dạng λ.x + (1- λ)y, 0 ≤ λ ≤ 1)
Định lí 1.1
Giao của một số bất kỳ các tập lồi là một tập lồi
Định lí 1.2
Nếu L là một tập lồi và xi (i = 1,m) là cá điểm bất kỳ của nó thì, với mọi m, tập L chứa mọi điểm là tổ hợp lồi cảu các điểm ấy
1.5.3 Điểm cực biên của một tập lồi
Điểm x0 của một tập lồi L được gọi là điểm cực biên của tập lồi ấy nếu nó không biểu diễn được dưới dạng tổ hợp lồi thực sự của hai điểm phân biệt trong L, tức là không tồn tại trong L hai điểm x1, x2 sao cho
x0 = . λ.x1 + (1- λ)x2 với 0 < λ < 1.
x0 là điểm cực biên của L khi và chỉ khi đẳng thức x = . λ.x1 + (1- λ)x2 với x1, x2 thuộc L, 0< λ < 1 chỉ xảy ra với x0=x1=x2
1.6 Tính chất của các tập phương án và tập nghiệm của bài toán quy hoạch tuyến tính
Định lí 1.3
Tập hợp các phương án của bài toán quy hoạch tuyến tính là một tập lồi.
Định lí 1.4
Tập hợp các phương án tối ưu của bài toán quy hoạch tuyến tính là một tập lồi