Học Tốt Phương pháp

Giải bài toán bằng phương pháp đơn hình đối ngẫu

f(x) = c1x1 + c2x2 + … + cnxn min

(P) [Bài toán gốc]

Trong đó aij, bi, cj là các hệ số cho trước; x= (x1, x2, … ,xn)  Rn l vecto biến cần tìm.

Ta gọi đối ngẫu của (P) là QHTT, ký hiệu (Q), có dạng:

g(y) = b1y1+b2y2+ … + bmym max

(Q) [Bài toán đối ngẫu]

Ở đây y = (y1, y2, … ,ym) Rm là vectơ biến cần tìm.

Các ràng buộc chính của (P)  các biến của (Q). Các biến của (P)  các ràng buộc chính của (Q).
Các hệ số vế phải ràng buộc chính của (P) trở thành các hệ số mục tiêu của (Q), còn các hệ số mục tiêu của (P) lại trở thành các hệ số vế phải ràng buộc chính của (Q).
Bài toán gốc tìm min thì bài toán đối ngẫu tìm max (và ngược lại).
Cả hai bài toán (P) và(Q) đều có dạng chuẩn.

Ví dụ: tìm bài toán đối ngẫu của bài toán QHTT dạng chuẩn.

f(x) = 20x1 + 15x2  min

Bài toán đối ngẫu là:

g(y) = 60y1 + 40y2 + 60y3  max

Dùng ký hiệu vectơ và ma trận, ta có thể viết:

Bài toán gốc: Bài toán đối ngẫu:

AT là ma trận chuyển vị của A, là tích vô hướng của hai vectơ a và b.

1.2. Định nghĩa đối ngẫu của bài toán qui hoạch tuyến tính dạng chính tắc:

Là bài toán:

Dưới dạng vectơ – ma trận, ta có thể viết:

Bài toán gốc: Bài toán đối ngẫu:

Trong đó I1I2I3 = {1,…,m}, IiIk = , i, k = 1, 2, 3 (ik); J1J2J3 = {1,…,n}, JiJk = , j, k = 1, 2, 3(jk).

Ta gọi đối ngẫu của bài toán trên là bài toán:

SƠ ĐỒ ĐỐI NGẪU TỔNG QUÁT
Bài toán gốc	Bài toán đối ngẫu
Các biến gốc: x1, x2,…, xn	Các biến đối ngẫu: y1, y2,…,ym
Hàm mục tiêu
f(x) = c1x1 + c2x2 +…+ cnxn  min	g(y) = b1y1+ b2y2 +…+ bmym  max
Các ràng buộc
ai1x1+ai2x2+…+ainxn	yi
xj	a1jy1+a2jy2+…+amjym

Nhận xét: Nếu lấy đối ngẫu của bài toán đối ngẫu thì ta sẽ nhận được bài toán gốc.

Ví dụ: tìm bài toán đối ngẫu của bài toán sau

Bài toán đối ngẫu là:

(P)

(Q)

Để tiện nghiên cứu lý thuyế đối ngẫu, ta xét cặp bài toán đối ngẫu (P) và (Q) cho ở dạng chuẩn. Tuy nhiên các kết quả nhận được cũng đúng cho một cặp bài toán đối ngẫu bất kỳ.

Định lý 1: (Đối ngẫu yếu).

Nếu x là 1 phương án bất kỳ của bài toán gốc (P) và y là 1 phương án bất kỳ của bài toán đối ngẫu (Q) thì:

f(x) = c1x1 + c2x2 +…+ cnxn  g(y) = b1y1 + b2y2 +…+ bmym

Hệ quả:

Giá trị mục tiêu của 1 phương án đối ngẫu bất kỳ là 1 cận dưới cho giá trị mục tiêu đối với mọi phương án của bài toán gốc.
Nếu hàm mục tiêu của bài toán gốc không bị chặn dưới trong miền ràng buộc của nó thì bài toán đối ngẫu không có bất kỳ mộ phương án nào.
Nếu hàm mục tiêu của bài toán đối ngẫu không bị chặn trên trong miền ràng buộc của nó thì bài toán gốc không có bất kỳ một phương án nào.
Nếu x* là 1 phương án của bài toán gốc, y* là 1 phương án của bài toán đối ngẫu và f(x*) = g(y*) thì x* là phương án tối ưu của bài toán gốc và y* là phương án tối ưu của bài toán đối ngẫu.

Định lý 2: (Đối ngẫu mạnh).

Nếu một quy hoạch có phương án tối ưu thì quy hoạch đối ngẫu của nó cũng có phương án tối ưu và giá trị tối ưu của chúng là bằng nhau.

Định lý 3: (Định lý tồn tại).

Đối với mỗi cặp quy hoạch đối ngẫu nhau thì có thể xảy ra một trong ba khả năng loại trừ nhau sau đây.

Cả hai bài toán đều không có phương án.
Cả hai bài toán đều có phương án. Khi đó, cả hai bài toán đều có phương án tối ưu và giá trị tối ưu của các hàm mục tiêu là bằng nhau.
Một bài toán có phương án và bài toán kia không có phương án. Khi đó, bài toán có phương án sẽ không có phương án tối ưu và hàm mục tiêu của nó không giới nội trong miền ràng buộc.

Định lý 4: (Định lý về độ lệch bù).

Một cặp phương án x, y của hai bài toán (P), (Q) là những phương án tối ưu khi và chỉ khi chúng nghiệm đúng các hệ thức:

Nhận xét:

: độ lệch ở ràng buộc I của (P).

: độ lệch ở ràng buộc j của(Q).

Ghi chú:

Các hệ thức (1), (2) nói rằng: với mỗi ràng buộc gốc hay đối ngẫu thì tích của độ lệch ở ràng buộc này và biến đối ngẫu (hay biến gốc) tương ứng với ràng buộc đó phải bằng không.

Nói cách khác, nếu một ràng buộc có độ lệch dương thì biến (gốc hay đối ngẫu) tương ứng với ràng buộc đó phải bằng không; ngược lại, nếu một biến gốc hay đối ngẫu có giá trị dương thì phương án của bài toán thỏa mãn ràng buộc tương ứng với dấu bằng.

Như vậy, hệ thức (1) có nghĩa là:

>bi

yi = 0

Và yi > 0

=bi

Hệ thức (2) cũng có nghĩa tương tự:

< cj

xj = 0

Và xj > 0

= cj

Định lý 5 (Định lý mạnh về độ lệch bù).

Nếu cặp bài toán đối ngẫu (P) và (Q) có phương án thì tồn tại một cặp phương án tối ưu x*, y* nghiệm đúng

y* + (Ax* - b) > 0

Và x* + ( c – ATy*) >0

2.2. Tìm phương án tối ưu của bài toán đối ngẫu

Nếu biết phương án tối ưu của bài toán gốc, vận dụng lý thuyết đối ngẫu ta có thể suy ra phương án tối ưu của bài tối đối ngẫu tương ứng mà không cần giải nó,

Ví dụ: Bài toán qui hoạch tuyến tính

Có phương án tối ưu x* = (0, 1, 0, 2, 3) với fmin = 6. Hãy tìm phương án tối ưu của bài toán đối ngẫu tương ứng.

Giải

Bài toán đối ngẫu của bài toán gốc là:

Gọi y* là phương án tối ưu của bài toán đối ngẫu

Do x*2, x*3, x*5 >0, nên theo định lý độ lệch bù, y* là nghiệm đúng hệ phương trình:

Giải hệ phương trình ta có:

Vậy y* (-5, 1, 1) là phương án tối ưu của g(y) với

gmax = -5 +(3*1) + (8*1) = 6 = fmin

Ví dụ: dùng phương pháp đơn hình giải quy hoạch gốc (P) sau đây, từ đó suy ra lời giải của bài toán đối ngẫu tương ứng với nó.

Xuất phát từ phương án cực biên ban đầu x0=(2, 12, 9, 0, 0, 0), cơ sở tương ứng {A1, A2, A3). Quá trình giải được ghi lại trong bảng đơn hình dưới đây.

Cơ Sở	Hệ số cj	Phương án	A1	A2	A3	A4	A5	A6	
1	-1	0	-2	2	-3
A1	1	2	1	0	0	[1]	1	-1	2
A2	-1	12	0	1	0	1	0	1	12
A3	0	9	0	0	1	2	4	3	4,5
Bảng 1	-10	0	0	0	2	-1	1
A4	-2	2	1	0	0	1	1	-1
A2	-1	10	-1	1	0	0	-1	2	5
A3	0	5	-2	0	1	0	2	[5]	1
Bảng 2	-14	-2	0	0	0	-3	3
A4	-2	3	3/5	0	1/5	1	7/5	0
A2	-1	8	-1/5	1	-2/5	0	-9/5	0
A6	-3	1	-2/5	0	1/5	0	2/5	1
Bảng 3	-17	-4/5	0	-3/5	0	-21/5	0

Để tìm lời giải (phương án tối ưu) của bài toán đối ngẫu ta áp dụng qui tắc sau:

Qui tắc

Nếu cơ sở ban đầu của (P) là cơ sở chính tắc (các vecto đơn vị), giả sử là {Aj, jJ}.

Để tìm lời giải của bài toán đối ngẫu, ta chọn ra từ bảng đơn hình cuối cùng của (P) các j (jJ) rồi cộng với hệ số cj tương ứng.

Vì thế, lời giải của bài toán đối ngẫu y* = (y*1, y*2, y*3) được xác định như sau:

Vậy y* =(

, -1,

) và gmax = -17 = fmin

Page 2

trang	3/4
Chuyển đổi dữ liệu	21.04.2018
Kích	0.52 Mb.
	#18088

Cho bài toán qui hoạch tuyến tính

f = 2x1 + 3x2 - 4x3 + 5x4+ min Điều kiện Giải Bài toán đối ngẫu của bài toán gốc : g = 10y1 + 8y2 + 9y3  max Điều kiện f = x1 - 4x2 - 3x3 - 2x4  min Điều kiện Giải Bài toán đối ngẫu của bài toán gốc: g = -y1 + 8y2 - 4y3  max Điều kiện Xét qui hoạch tuyến tính: Chứng tỏ rằng bài toán này trùng với bài toán đối ngẫu của nó (bài toán tự đối ngẫu). Giải Giả sử bài toán g’(y) sau đây trùng với bài toán gốc: Bài toán đối ngẫu của bài toán gốc f(x) là: Đưa bài toán đối ngẫu về dạng min ta có bài toán tương đương: Bài toán tương đương của bài toán đối ngẫu trùng với bài toán gốc.  bài toán tự đối ngẫu.  điều phải chứng minh. Có phương án tối ưu x* = (2, 4, 0, 0) và giá trị tối ưu là -6. Hãy tìm phương án tối ưu và giá trị tối ưu của bài toán đối ngẫu. Giải Bài toán đối ngẫu của bài toán gốc: Gọi y* = (y1, y2) là phương án tối ưu của bài toán đối ngẫu. Do x1, x2 > 0 nên theo định lí về độ lệch bù, y* là nghiệm đúng hệ phương trình Giải hệ phương trình, ta được y* = (1, - ). Với gmax = 6.1 + 8.(- ) = -6 = fmin Xét qui hoạch tuyến tính: Phát biểu bài toán đối ngẫu của bài toán trên. Hãy giải một trong hai bài rồi suy ra phương án tối ưu của bài toán còn lại. Giải Bài toán đối ngẫu của bài toán gốc: Ta giải bài toán đối ngẫu: Thêm vào hai ẩn phụ vào ràng buộc thứ nhất và thứ hai. Lập bảng đơn hình, ta có: sở	Hệ số	Phương án	A1	A2	A3	A4	A5	
3	2	7	0	0
A4	0	15	3	1	3	1	0	5
A5	0	19	1	1	[4]	0	1	19/4
Bảng 1	0	-3	-2	-7	0	0
A4	0	3/4	[9/4]	1/4	0	1	-3/4	1/3
A3	7	19/4	1/4	1/4	1	0	1/4	19
Bảng 2	133/4	-5/4	-1/4	0	0	7/4
A1	3	1/3	1	[1/9]	0	4/9	-1/3	3
A3	7	14/3	0	2/9	1	-1/9	1/3	21
Bảng 3	101/3	0	-1/9	0	5/9	4/3
A2	2	3	9	1	0	4	-3
A3	7	4	-2	0	1	-1	1
Bảng 4	34	1	0	0	1	1

 Phương án tối ưu của bài toán đối ngẫu: y* = (0, 3, 4)

Gọi x* = (x1, x2) là phương án tối ưu của bài toán gốc.

Do y2*, y3* >0, nên theo định lí về độ lệch bù, x*là nghiệm đúng hệ phương trình:

Giải hệ phương trình, ta được: x* = (1, 1)

Với fmin = gmax = 34

Xét bài toán quy hoạch tuyến tính:

f(x) = 4x1 –x2 -3x3  min

(*)

Viết bài toán đối ngẫu. Chứng tỏ x0 = (-1, 1, 1) là phương án tối ưu. Xác định một phương án tối ưu của bài toán đối ngẫu.

Giải

Bài toán đối ngẫu của bài toán gốc:

g(y) = -2y1 + 4y2 - 3y3 - 6y4 + 3y5  max

Thay x0 = (-1, 1, 1) vào hệ ràng buộc (*), ta có:

x0 = (-1, 1, 1) thỏa (*)  x0 là phương án của bài toán gốc.

Gọi y0 = (y1, y2, y3, y4, y5) là phương án của bài toán đối ngẫu.

Do độ lệch ràng buộc 2, 4 của bài toán gốc khác 0 nên theo định lí về độ lệch bù, y0 là nghiệm đúng hệ phương trình:

Giải hệ phương trình, ta được y0 = (1, 0, 1, 0, -1).

Với: f(x) = g(x) = -8.

 x0 = (-1, 1, 1) là phương án tối ưu của bài toán gốc.

 y0 = (1, 0, 1, 0, -1) là phương án tối ưu của bài toán đối ngẫu.

Xét qui hoạch tuyến tính:

(*)

Kiểm tra tính tối ưu của phương án x0 = (5, -6, 1, -4, 0).
Phát biểu bài toán đối ngẫu của bài toán trên.
Chứng tỏ bài toán đã cho không có phưong án tối ưu.

Giải

Thế x0 = (5, -6, 1, -4, 0) vào hệ ràng buộc (*), ta có

Do độ lệch ràng buộc 2 khác 0 và x10, x20, x30, x40 khác 0 nên theo định lí về độ lệch bù vectơ x0 = (5, -6, 1, -4, 0) là phương án tối ưu của bài toán gốc khi tồn tại vectơ y0 = (y1, y2, y3)  R3 sao cho:

Hệ này vô nghiệm

 không tồn tại y0  R3 thoả hệ trên.

 phương án x0 = (5, -6, 1, -4, 0) không phải là phương án tối ưu của bài toán gốc.

Bài toán đối ngẫu của bài toán gốc:

Ta giải hệ ràng buộc của bài toán đối ngẫu:

Hệ này vô nghiệm  bài toán đối ngẫu có tập phương án rỗng

Mà bài toán gốc có tập phương án khác rỗng (vì x0 là 1 phương án)

 bài toán gốc không có phương án tối ưu (theo định lí tồn tại).

Xét qui hoạch tuyến tính:

(*)

Kiểm tra tính tối ưu của phương án x0 = (2, 0, 1, -2, 3).
Phát biểu bài toán đối ngẫu của bài toán trên.
Tìm phương án tối ưu của bài toán đối ngẫu.

Giải

Thế x0 = (2, 0, 1, -2, 3) vào hệ ràng buộc (*), ta có:

Do độ lệch ràng buộc 1 của bài toán gốc khác 0 và x10, x30, x40, x50 khác không nên theo định lí về độ lệch bù vectơ x0 = (2, 0, 1, -2, 3) là phương án tối ưu của bài toán gốc khi tồn tại vectơ y0 = (y1, y2, y3)  R3 sao cho:

Giải hệ phương trình, ta được y0 = (0, 4, 0).

 tồn tại y0  R3 thỏa hệ trên.

 phương án x0 = ( 2, 0, 1, -2, 3) là phương án tối ưu của bài toán gốc.

Bài toán đối ngẫu của bài toán gốc:

Vì đã biết x0 = (2, 0, 1, -2, 3) là phương án tối ưu của bài toán gốc nên phương án tối ưu y0 của bài toán đối ngẫu có thể tìm từ định lí độ lệch bù:

Thay các giá trị đã biết vào hệ, ta được:

Vậy phương án tối ưu của bài toán đối ngẫu là y0 = (0, 4, 0).

Với gmax = fmin = -36.

Xét qui hoạch tuyến tính:

Phát biểu bài toán đối ngẫu của bài toán trên.
Hãy giải một trong hai bài toán rồi suy ra phương án tối ưu của bài toán còn lại.

Giải

Bài toán đối ngẫu của bài toán gốc:

Thêm vào hai ẩn phụ x5  0, x6  0 vào ràng buộc thứ hai và thứ ba. Lập bảng đơn hình, ta có:

sở

Page 3

f(x) = c1x1 + c2x2 + … + cnxn min

(P) [Bài toán gốc]

Trong đó aij, bi, cj là các hệ số cho trước; x= (x1, x2, … ,xn)  Rn l vecto biến cần tìm.

Ta gọi đối ngẫu của (P) là QHTT, ký hiệu (Q), có dạng:

g(y) = b1y1+b2y2+ … + bmym max

(Q) [Bài toán đối ngẫu]

Ở đây y = (y1, y2, … ,ym) Rm là vectơ biến cần tìm.

Các ràng buộc chính của (P)  các biến của (Q). Các biến của (P)  các ràng buộc chính của (Q).
Các hệ số vế phải ràng buộc chính của (P) trở thành các hệ số mục tiêu của (Q), còn các hệ số mục tiêu của (P) lại trở thành các hệ số vế phải ràng buộc chính của (Q).
Bài toán gốc tìm min thì bài toán đối ngẫu tìm max (và ngược lại).
Cả hai bài toán (P) và(Q) đều có dạng chuẩn.

Ví dụ: tìm bài toán đối ngẫu của bài toán QHTT dạng chuẩn.

f(x) = 20x1 + 15x2  min

Bài toán đối ngẫu là:

g(y) = 60y1 + 40y2 + 60y3  max

Dùng ký hiệu vectơ và ma trận, ta có thể viết:

Bài toán gốc: Bài toán đối ngẫu:

AT là ma trận chuyển vị của A, là tích vô hướng của hai vectơ a và b.

1.2. Định nghĩa đối ngẫu của bài toán qui hoạch tuyến tính dạng chính tắc:

Là bài toán:

Dưới dạng vectơ – ma trận, ta có thể viết:

Bài toán gốc: Bài toán đối ngẫu:

Trong đó I1I2I3 = {1,…,m}, IiIk = , i, k = 1, 2, 3 (ik); J1J2J3 = {1,…,n}, JiJk = , j, k = 1, 2, 3(jk).

Ta gọi đối ngẫu của bài toán trên là bài toán:

SƠ ĐỒ ĐỐI NGẪU TỔNG QUÁT
Bài toán gốc	Bài toán đối ngẫu
Các biến gốc: x1, x2,…, xn	Các biến đối ngẫu: y1, y2,…,ym
Hàm mục tiêu
f(x) = c1x1 + c2x2 +…+ cnxn  min	g(y) = b1y1+ b2y2 +…+ bmym  max
Các ràng buộc
ai1x1+ai2x2+…+ainxn	yi
xj	a1jy1+a2jy2+…+amjym

Nhận xét: Nếu lấy đối ngẫu của bài toán đối ngẫu thì ta sẽ nhận được bài toán gốc.

Ví dụ: tìm bài toán đối ngẫu của bài toán sau

Bài toán đối ngẫu là:

(P)

(Q)

Định lý 1: (Đối ngẫu yếu).

Nếu x là 1 phương án bất kỳ của bài toán gốc (P) và y là 1 phương án bất kỳ của bài toán đối ngẫu (Q) thì:

f(x) = c1x1 + c2x2 +…+ cnxn  g(y) = b1y1 + b2y2 +…+ bmym

Hệ quả:

Giá trị mục tiêu của 1 phương án đối ngẫu bất kỳ là 1 cận dưới cho giá trị mục tiêu đối với mọi phương án của bài toán gốc.
Nếu hàm mục tiêu của bài toán gốc không bị chặn dưới trong miền ràng buộc của nó thì bài toán đối ngẫu không có bất kỳ mộ phương án nào.
Nếu hàm mục tiêu của bài toán đối ngẫu không bị chặn trên trong miền ràng buộc của nó thì bài toán gốc không có bất kỳ một phương án nào.
Nếu x* là 1 phương án của bài toán gốc, y* là 1 phương án của bài toán đối ngẫu và f(x*) = g(y*) thì x* là phương án tối ưu của bài toán gốc và y* là phương án tối ưu của bài toán đối ngẫu.

Định lý 2: (Đối ngẫu mạnh).

Nếu một quy hoạch có phương án tối ưu thì quy hoạch đối ngẫu của nó cũng có phương án tối ưu và giá trị tối ưu của chúng là bằng nhau.

Định lý 3: (Định lý tồn tại).

Đối với mỗi cặp quy hoạch đối ngẫu nhau thì có thể xảy ra một trong ba khả năng loại trừ nhau sau đây.

Cả hai bài toán đều không có phương án.
Cả hai bài toán đều có phương án. Khi đó, cả hai bài toán đều có phương án tối ưu và giá trị tối ưu của các hàm mục tiêu là bằng nhau.
Một bài toán có phương án và bài toán kia không có phương án. Khi đó, bài toán có phương án sẽ không có phương án tối ưu và hàm mục tiêu của nó không giới nội trong miền ràng buộc.

Định lý 4: (Định lý về độ lệch bù).

Một cặp phương án x, y của hai bài toán (P), (Q) là những phương án tối ưu khi và chỉ khi chúng nghiệm đúng các hệ thức:

Nhận xét:

: độ lệch ở ràng buộc I của (P).

: độ lệch ở ràng buộc j của(Q).

Ghi chú:

Như vậy, hệ thức (1) có nghĩa là:

>bi

yi = 0

Và yi > 0

=bi

Hệ thức (2) cũng có nghĩa tương tự:

< cj

xj = 0

Và xj > 0

= cj

Định lý 5 (Định lý mạnh về độ lệch bù).

Nếu cặp bài toán đối ngẫu (P) và (Q) có phương án thì tồn tại một cặp phương án tối ưu x*, y* nghiệm đúng

y* + (Ax* - b) > 0

Và x* + ( c – ATy*) >0

2.2. Tìm phương án tối ưu của bài toán đối ngẫu

Ví dụ: Bài toán qui hoạch tuyến tính

Có phương án tối ưu x* = (0, 1, 0, 2, 3) với fmin = 6. Hãy tìm phương án tối ưu của bài toán đối ngẫu tương ứng.

Giải

Bài toán đối ngẫu của bài toán gốc là:

Gọi y* là phương án tối ưu của bài toán đối ngẫu

Do x*2, x*3, x*5 >0, nên theo định lý độ lệch bù, y* là nghiệm đúng hệ phương trình:

Giải hệ phương trình ta có:

Vậy y* (-5, 1, 1) là phương án tối ưu của g(y) với

gmax = -5 +(3*1) + (8*1) = 6 = fmin

Ví dụ: dùng phương pháp đơn hình giải quy hoạch gốc (P) sau đây, từ đó suy ra lời giải của bài toán đối ngẫu tương ứng với nó.

Xuất phát từ phương án cực biên ban đầu x0=(2, 12, 9, 0, 0, 0), cơ sở tương ứng {A1, A2, A3). Quá trình giải được ghi lại trong bảng đơn hình dưới đây.

Cơ Sở	Hệ số cj	Phương án	A1	A2	A3	A4	A5	A6	
1	-1	0	-2	2	-3
A1	1	2	1	0	0	[1]	1	-1	2
A2	-1	12	0	1	0	1	0	1	12
A3	0	9	0	0	1	2	4	3	4,5
Bảng 1	-10	0	0	0	2	-1	1
A4	-2	2	1	0	0	1	1	-1
A2	-1	10	-1	1	0	0	-1	2	5
A3	0	5	-2	0	1	0	2	[5]	1
Bảng 2	-14	-2	0	0	0	-3	3
A4	-2	3	3/5	0	1/5	1	7/5	0
A2	-1	8	-1/5	1	-2/5	0	-9/5	0
A6	-3	1	-2/5	0	1/5	0	2/5	1
Bảng 3	-17	-4/5	0	-3/5	0	-21/5	0

Để tìm lời giải (phương án tối ưu) của bài toán đối ngẫu ta áp dụng qui tắc sau:

Qui tắc

Nếu cơ sở ban đầu của (P) là cơ sở chính tắc (các vecto đơn vị), giả sử là {Aj, jJ}.

Để tìm lời giải của bài toán đối ngẫu, ta chọn ra từ bảng đơn hình cuối cùng của (P) các j (jJ) rồi cộng với hệ số cj tương ứng.

Vì thế, lời giải của bài toán đối ngẫu y* = (y*1, y*2, y*3) được xác định như sau:

Vậy y* =(

, -1,

) và gmax = -17 = fmin

Page 4

Câu 1:

Một công ty sản xuất hai thực phẩm A, B. nguyên liệu sản xuất gồm 3 loại Bột, Đường, Dẩu thực vật với trữ lượng tương ứng là 30 tấn, 12 tấn, 6 tấn. Để sản xuất 1 tấn thực phẩm loại A cần 0,5 tấn bột, 0.5 tấn đường và 0.2 tấn dầu thực vật. Để sản xuất 1 tấn thực phẩm loại B cần 0,8 tấn bột, 0.4 tấn đường và 0.4 tấn dầu thực vật. Giá bán 1 tấn thực phẩm loại A là 4000USD, giá bán 1 tấn thực phẩm loại B là 4500USD.

Hỏi cần sản suất mỗi loại thực phẩm bao nhiêu tấn để có doanh thu lớn nhất?

Giải:

Theo đề bài ta lập được bảng:

	Bột (Tấn)	Đường (Tấn)	Dầu thực vật (Tấn)	Giá Bán (USD)	Số Lượng Sản Xuất (Tấn)
Thực phẩm loại A	0,5	0,5	0,2	4000	X1
Thực phẩm loại B	0,8	0,4	0,4	4500	X2
Tổng Trữ	30	12	6	?

Bài toán được viết lại:

Tìm x1, x2 sao cho:

F(x) =4000.x1 + 4500.x2  Max

Điều kiện:

0,5.x1 + 0,8.x2

0,5.x1 + 0,4.x2

0,2.x1 + 0,4.x2

x1, x2

Đặt G(x) = - F(x) = -4000.x1 - 4500.x2

F(x)  Max => G(x) Min

Chuyển về dạng chính tắc:

Ta lần lượt them biến x3, x4, x5 vào các điều kiện bài toán sao cho:

G(x) = - F(x) = -4000.x1 - 4500.x2

Điều kiện:

0,5.x1 + 0,8.x2 +x3

0,5.x1 + 0,4.x2 +x4

0,2.x1 + 0,4.x2 +x5

x1, x2, x3, x4, x5

Cho x1 = 0, x2 = 0, ta có: x3 = 30, x4

12, x5

Phương án cực biên ban đầu: ( 0, 0, 30, 12, 6 )

Đánh giá PACB hiện có:

Xj	Cj	bj	X1	X2	X3	X4	X5
-4000	-4500	0	0	0
X3	0	30	0,5	[0,8]	1	0	0
X4	0	12	0,5	0,4	0	1	0
X5	0	6	0,2	0,4	0	0	1
		0	4000	4500	0	0	0
X2	-4500	37,5	5/8	1	5/4	0	0
X4	0	-3	0,25	0	-0,5	1	0
X5	0	-9	-0,05	0	-0,5	0	1
		-168750	-1187,5	0	-5625	0	0

Phương án tối ưu là: ( 0, 37.5, 0,0,0)

Sản suất 37,5 tấn loại B để có doanh thu lớn nhất là 168750 USD

Câu 2:

Gọi x,y,z lần lượt là thức ăn T1,T2,T3 cần mua. X,Y,Z ≥ 0.

Lượng gia sức tối thiểu 160 đơn vị của D1 là:

3x+4y+2z ≥ 160

Lượng gia súc tối thiểu 140 đơn vị của D2 là:

X+2y+3z ≥ 140

Số tiền mà xí nghiệp cần mua là:

F = 15000x+12000y+10000z

Tìm (x,y,z ) sao cho

F= 15000x+12000y+10000z => min

Với các ràng buộc

Đây là bài toán Quy Hoạch Tuyến Tính.

Câu 3. Cho bài toán Quy họach tuyến tính

Bài toán đối ngẫu:

g(x)=20y1+25y2 → max

Thêm biến cơ sở

vào điều kiện 1,2 và 3.

Bài toán trên chuyển về dạng chính tắc :

+ 2

= 1

+ 6

= 2

+ 3

≥ 0 ; j=

Bài toán dạng chuẩn các biến cô lập là :

=(0,0,1,2,3) là phương án cực biên

Với biến cơ sở là :


20	25	0	0	0
	0	1	6	2	1	0	0
	0	2	3	6	0	1	0
	0	3	2	3	0	0	1
			-20	-25	0	0	0
	0	1/3	5	0	1	-1/3	0
	25	1/3	1/2	1	0	1/6	0
	0	2	1/2	0	0	-1/2	1
			-15/2	0	0	25/6	0
	20	1/15	1	0	1/5	-1/15	0
	25	3/10	0	1	-1/10	1/15	0
	0	59/30	0	0	-1/10	-7/15	1
			0	0	3/2	11/3	0

Suy ra phương án tối ưu của bài toán đối ngẫu :

= 3/2 + 0 =3/2

= 11/3 + 0 = 11/3

= 0 + 0 = 0

Hay

= (3/2 ; 11/3 ; 0)

Vì phần tử đưa vào trùng với phần tử đưa ra. Nên bài toán không có phương án tối ưu.

Câu 5 :

Giải

Gọi x1, x2 lần lượt là sản phẩm A, sản phẩm B mà xí nghiệp sản xuất:

Ta có : x1,x2 ≥0

Số nguyên liệu I cần sử dụng:

x1 + x2

Số nguyên liệu II cần sử dụng:

2x1 + x2

Số nguyên liệu III cần sử dụng:

x1 + 3x2

Tổng số lãi: 4x1 + 5x2

Do đó: ta có mô hình bài toán như sau

x1 + x2 ≤ 10

2x1 + x2 ≤ 12

x1 + 3x2 ≤ 15

x1 + x2 ≤ 13

x1,x2 ≥ 0

Câu 6. Giải bài toán sau đây và từ đó suy ra phương án tối ưu (nếu có) của bài toán đối ngẫu của nó

Ma trận đơn vị được tạo từ A4, A5, A6

x4, x5, x6 là cơ sở.

x1, x2, x3 là biến phi cơ sở.

Cho x1, x2, x3 =0 ta có: x4=4, x5=3, x6=3

Phương án ban đầu: (0,0,0,3,4,3)

Bảng đơn hình:

sở

Giải bài toán bằng phương pháp đơn hình đối ngẫu

1.2. Định nghĩa đối ngẫu của bài toán qui hoạch tuyến tính dạng chính tắc:

Page 2

Page 3

1.2. Định nghĩa đối ngẫu của bài toán qui hoạch tuyến tính dạng chính tắc:

Page 4

Video liên quan

Bài Viết Liên Quan

Tổng hợp kiến thức Toán 11 Hình học

Lãi vay ngân hàng tiếng anh là gì

Top 14 bảng màu son nars audacious tốt nhất 2022

Câu chuyện về trường học Tân Quý

Công thức tính diện tích hình nón cụt

Đánh giá mở bài bằng lí luận văn học về thơ

Ngành kinh tế vận tải biển học trường nào

De thi học sinh giỏi môn Tiếng Việt lớp 4

Top 0 tủ đông panasonic scr p1497 tốt nhất 2022

Siêu âm ổ bụng ở đâu tốt nhất

Toplist

Top 10 de thi ioe lớp 4 cấp quốc gia 2022

Top 9 bộ số lịch 2022 vector 2022

Top 6 đề thi violympic toán lớp 4 vòng 9 năm 2022-2022 2022

Top 10 miêu tả nơi làm việc của bạn bằng tiếng anh 2022

Top 8 lời chúc mừng lễ khởi công 2022

Top 10 đề tham khảo tuyển sinh lớp 10 môn toán 2022-2022 tphcm có đáp án 2022

Top 9 sơ đồ tư duy lịch sử việt nam 1930-1945 2022

Top 9 manga giang hồ học đường 2022

Top 10 dòi bò vào nhà là điềm gì 2022

Bài mới nhất

Cách ăn uống nào để có trinh ở nam năm 2024

Lỗi không zo dc trận trong liên minh năm 2024

Lỗi c windows syswow64 cmd.exe c powershell.exe hidden invoke-expression năm 2024

Chuyển nhượng mùa hè 2023 khi nào bắt đầu năm 2024

Chủ đề