Đưa Bài Toán Qhtt Dạng Chính Tắc Về Bài Toán Qhtt Dạng Chuẩn

Giả sử các sản phẩm sản xuất ra đều có thể bán hết với lợi nhuận là 620 USD đối với mỗi sản phẩm S1và 570 USD đối với mỗi sản phẩm S2. Hỏi mỗi tuần phải sản xuất bao nhiêu sản phẩm S1và bao nhiêu sản phẩm S2để nhà máy có lợi nhuận lớn nhất?

Bài 1.12Một phân xưởng cơ khí có 3 loại máy G1, G2, G3dùng để sản xuất 3 loại chi tiết C1, C2, C3. Năng suất của mỗi loại máy sản xuất từng loại chi tiết được cho như sau ( số chi tiết /1ca ):

Chi tiết

Máy

C1 3	C2 1	C3 3
G1:2	0	15	18
G2: 3	50	20	30
G3:1	60	40	45

Có thể bạn quan tâm!

• Quy hoạch toán học - Ngô Hữu Tâm - 1
• Quy hoạch toán học - Ngô Hữu Tâm - 2
• Quy Tắc Vàng Khi Lập Mô Hình Toán Học Bài Toán Thực Tế Và Khái Niệm Tối Ưu:
• Các Bước Giải Bài Toán Qhtt Hai Biến Bằng Phương Pháp Hình Học
• Định Lý 3 (Dấu Hiệu Bài Toán Có Thể Điều Chỉnh Để Được Pa Tốt Hơn)
• Quy hoạch toán học - Ngô Hữu Tâm - 7

Xem toàn bộ 192 trang tài liệu này.

Các chi tiết sau khi sản xuất được lắp ráp thành sản phẩm. Mỗi sản phẩm bao gồm 3 chi tiết C1, 1 chi tiết C2và 3 chi tiết C3.

Hãy tìm phương án phân công thời gian làm việc cho các máy sao cho số sản phẩm

được lắp ráp trong một ca sản xuất là nhiều nhất. Biết rằng phân xưởng có 2 máy G1, 3 máy G2và 1 máy G3.

Bài 1.13Một công ty may mặc có 3 xí nghiệp I, II, III. Công ty ký hợp đồng giao cho đối tác 1500 bộ gồm áo veston và quần tây, nếu có lẻ bộ thì đối tác lấy thêm quần tây chứ không lấy thêm áo. Tổng số vải và giờ công lao động mà công ty có thể huy động được từ 3 xí nghiệp mỗi tháng là 10 000 m và 52 000 giờ. Mức tiêu hao vải và giờ công lao động để sản xuất một áo hoặc một quần tại mỗi xí nghiệp (XN) được cho trong bảng sau:

XN

Sản phẩm

I	II	III
Áo veston	3,5 m và 20 giờ	4m và 16 giờ	3,8m và 18 giờ
Quần tây	2,8 m và 10 giờ	2,6m và 10 giờ	2,5m và 15 giờ

Giả sử nếu đầu tư 10 triệu đồng vào xí nghiệp I ( để mua nguyên liệu, máy móc và đầu tư vào hoạt động sản xuất ) sẽ thu được 35 áo veston và 45 quần tây, vào xí nghiệp II sẽ thu được 40 áo veston và 42 quần tây, vào xí nghiệp III sẽ thu được 43 áo veston và 30 quần tây. Hãy lập mô hình toán học của bài toán lập kế hoạch đầu tư vào mỗi xí nghiệp bao nhiêu tiền để thực hiện được hợp đồng và tổng số tiền đầu tư vào các xí nghiệp ít nhất.

Bài 1.14Một công ty sử dụng 2 loại nguyên liệu N1, N2 để sản xuất ra 1 loại sản phẩm theo 2 công nghệ khác nhau là CN1, CN2. Biết lượng nguyên liệu mỗi loại hiện có; định mức tiêu hao các loại nguyên liệu, chi phí sản xuất, lượng sản phẩm làm ra trong một giờ được cho trong bảng sau:

Nguyên liệu

Số lượng nguyên liệu hiện có (đv)	Định mức tiêu hao nguyên liệu trong 1 giờ
	CN1	CN2
N1	300	2	4
N2	400	3	2
Sản lượng (sản phẩm/giờ)		7	8
Chi phí (USD/giờ)		120	150

Hãy lập mô hình toán học bài toán tìm kế hoạch sản xuất sao cho giá thành sản phẩm là thấp nhất.

Bài 1.15Hãy lập mô hình toán học của bài toán sau đây. Một công ty may mặc ký hợp đồng giao cho khách hàng 248.000 bộ quần áo trong thời gian 1 tháng. Công ty có ba xí nghiệp A, B, C và quần áo phải được sản xuất và đóng gói thành bộ tại mỗi xí nghiệp. Năng lực sản xuất trong một tháng và lợi nhuận đối với mỗi bộ quần áo (sau khi đã trừ tất cả các chi phí) của các xí nghiệp trong thời gian thường trong thời gian tăng ca được cho trong bảng sau:

Xí nghiệp

Thời gian SX

Xí nghiệp A		Xí nghiệp B		Xí nghiệp C
Năng lực sản xuất	Lợi nhuận	Năng lực sản xuất	Lợi nhuận	Năng lực sản xuất	Lợi nhuận
Thời gian thường	90.000 bộ/tháng	8.000 đồng/bộ	50.000 bộ/tháng	7.500 đồng/bộ	80.000 bộ/tháng	8.000 đồng/bộ
Thời gian tăng ca	40.000 bộ/tháng	7.200 đồng/bộ	20.000 bộ/tháng	6.500 đồng/bộ	30.000 bộ/tháng	7.500 đồng/bộ

Biết rằng số bộ quần áo sản xuất tại hai xí nghiệp A và B phải ít nhất là 152.000 bộ. Hỏi phải phân công sản xuất cho các xí nghiệp như thế nào để hoàn thành hợp đồng với lợi nhuận lớn nhất.

Bài 1.16(bài toán qui hoạch phân tuyến tính) Một công ty sử dụng 3 loại nguyên liệu N1, N2, N3để sản xuất ra một loại sản phẩm tại hai xí nghiệp khác nhau là XN1, XN2. Do trình độ chuyên môn, trình độ quản lý, trang thiết bị sản xuất của hai xí nghiệp khác nhau nên định mức tiêu hao nguyên liệu và năng suất của hai xí nghiệp cũng khác nhau. Biết lượng nguyên liệu mỗi loại hiện có, định mức tiêu hao các loại nguyên liệu, chi phí sản xuất, lượng sản phẩm làm ra trong một giờ được cho trong bảng sau:

Nguyên liệu

Số lượng nguyên liệu hiện có (đv)	Định mức tiêu hao nguyên liệu trong 1 giờ
	XN1	XN2
N1	3500	40	39
N2	3200	27	30
N3	5600	45	43
Sản lượng (sản phẩm/giờ)		112	100
Chi phí (USD/giờ)		165	162

Ban giám đốc công ty yêu cầu xí nghiệp 2 phải sản xuất ít nhất 1000 sản phẩm. Hãy lập mô hình toán học bài toán tìm kế hoạch sản xuất sao cho giá thành sản phẩm là thấp nhất.

Bài 1.17Một công ty sử dụng 4 loại nguyên liệu N1, N2, N3, N4 để sản xuất ra 3 loại sản phẩm SP1, SP2, SP3. Biết lợi nhuận của mỗi đơn vị sản phẩm (không phụ thuộc vào số giờ sản xuất và số sản phẩm được sản xuất), số lượng nguyên liệu hiện có, định mức tiêu hao các loại nguyên liệu và lượng sản phẩm làm ra trong một giờ được cho trong bảng sau:

Nguyên liệu

Số lượng nguyên liệu hiện có	Định mức tiêu hao nguyên liệu (đôn vò) trong 1 giờ
	SP1	SP2	SP3
N1	350 (đôn vò)	2	3	4
N2	650 (đôn vò)	6	8	9
N3	600 (đôn vò)	3	5	7
N4	900 (đôn vò)	8	10	9
Sản lượng (sản phẩm/giờ)		12	10	9
Lợi nhuận (đồng/sản phẩm)		10.000	12.000	13.000

Sản phẩm của xí nghiệp sản xuất ra đều có thể tiêu thụ hết với điều kiện tiêu thụ là số sản phẩm SP2và SP3phải có tỷ lệ 1:2. Hãy lập mô hình toán học bài toán tìm kế hoạch sản xuất sao cho lợi nhuận lớn nhất.

Bài 1.18Một công ty sử dụng 4 loại nguyên liệu N1, N2, N3, N4để sản xuất ra một loại sản phẩm tại ba xí nghiệp khác nhau là XN1, XN2, XN3. Do trình độ chuyên môn, trình độ quản lý, trang thiết bị sản xuất của ba xí nghiệp khác nhau nên định mức tiêu hao nguyên liệu và năng suất của ba xí nghiệp cũng khác nhau. Biết lượng nguyên liệu mỗi loại hiện có, định mức tiêu hao các loại nguyên liệu, chi phí sản xuất, lượng sản phẩm làm ra trong một giờ của mỗi xí nghiệp được cho trong bảng sau:

Nguyên liệu

Số lượng nguyên liệu hiện có (đv)	Định mức tiêu hao nguyên liệu trong 1 giờ của mỗi xí nghiệp
	XN1	XN2	XN3
N1	36000	38	37	39
N2	35000	31	32	31
N3	63000	45	43	44
N4	Không hạn chế	68	72	70
Sản lượng (sản phẩm/giờ)		117	114	118
Chi phí (USD/giờ)		170	165	168

Hãy lập mô hình toán học bài toán tìm kế hoạch sản xuất sao cho giá thành sản phẩm là thấp nhất, biết xí nghiệp I phải sản xuất ít nhất 1200 sản phẩm.

§ 2. CÁC DẠNG BÀI TOÁN QUI HOẠCH TUYẾN TÍNH

2.1. Bài toán qui hoạch tuyến tính tổng quát

Tìm x = (x1, x2,…, xn) n sao cho:

n

(1) f(x) = c jx j

j1

min ( max)

n

(2) aijx j

b i 

b i 

, i = 1, 2, …, m



j1

(3) xj

b i

0 

0 , j = 1, 2, …, n



tùy ý

f(x) gọi là hàm mục tiêu.

Mỗi phương trình hoặc bất phương trình ở (2) gọi là một ràng buộc. Vậy có m ràng buộc.

(3) gọi là ràng buộc về dấu của các ẩn số.

Tập D trong nthỏa (2) và (3) gọi là miền ràng buộc hay miền phương án.

Mỗi vectơ x = (x1, x2,…, xn) nthỏa (2) và (3) gọi là một phương án (PA).

Phương án xthỏa (1) gọi là phương án tối ưu (PATƯ) và f (x) gọi là giá trị tối ưu của bài toán; tức là f (x) f(x) xD đối với bài toán f min, f (x) f(x) xD đối với bài toán f max.

Việc giải bài toán QHTT là tìm PATƯ và giá trị hàm mục tiêu ứng với PATƯ

đó; hoặc chỉ rõ bài toán không có phương án tối ưu.

Nhận xétf(x) min tương đương với -f(x) max. Do đó, mọi bài toán có hàm mục tiêu min đều có thể chuyển về bài toán có hàm mục tiêu max và ngược lại.

Ví dụ 1Tìm x = (x1,x2,x3) 3 sao cho

(1) f(x) = 2x1-x2 + x3 min (max)

x1

(2) 2x

2x2

2x

x3 2

x 3

1 2 3



x1

x2

x3 4

(3) x1tùy ý, x20, x30

Ví dụ 2Tìm x = (x1,x2,x3,x4,x5) 5 sao cho

(1) f(x) = 3x1-x2 +2 x3 +x4 +5x5 max (min)

2x1

4x

x2

2x

x3

x

2x4

x5

17

18

(2) 1 2 3



x1

x1

x2

x2

2x3

2x3

x4

x5

20

100

(3) x1, x40; x2, x30 ; x5tùy ý

Ví dụ 3Cỏc bài toỏn lập ở vớ dụ 3, 4, 5 bài Đ1 đều cú dạng tổng quỏt.

2.2. Bài toán qui hoạch tuyến tính dạng chính tắc:(Canonical form) Tìm x = (x1, x2,…, xn) n sao cho:

n

(1) f(x) = c jx j

j1

min ( max)

n

(2) aijx jbi

j1

, i = 1, 2, …, m

(3) xj 0 , j = 1, 2, …, n

Không mất tính tổng quát, có thể giả sử m ràng buộc ở (2) là độc lập tuyến tính. Tức là, nếu A là ma trận bổ sung của hệ phương trình tuyến tính (2) thì r( A ) = m.

Bất kỳ bài toán QHTT nào cũng có thể đưa về bài toán QHTT dạng chính tắc bằng các phép biến đổi tương đương ( đưa thêm vào các ẩn phụ) như sau:

n

Biến đổi 1Mỗi ràng buộc là bất phương trình dạng aijx jbiđược đưa về

j1

phương trình bằng cách cộng vế trái với một ẩn phụ xn+k 0 ( k1,2,3,...).

n

Nghĩa là nó tương đương với aijx j

j1

+ xn+k = bi. Hệ số của ẩn phuù xn+k trong

hàm mục tiêu là 0.

n

Biến đổi 2Mỗi ràng buộc là bất phương trình dạng aijx j

j1

biđược đưa về

phương trình bằng cách trừ vế trái với một ẩn phụ xn+k 0 ( k1,2,3,...). Nghóa

n

là nó tương đương với aijx j

j1

- xn+k = bi. Hệ số của ẩn phuù xn+k trong hàm mục

tiêu là 0.

j

Biến đổi 3Mỗi biến xj 0 thì được thay bởi xj = - x'

x

j

, với '

x

0.

x

j

Biến đổi 4Mỗi biến xjtùy ý thì được thay bởi xj= '

- x", với '

0 ,

x" 0.

j

j

j

Ví dụ 4Đưa bài toán QHTT sau đây ( bài toán (P)) về dạng chính tắc:

(1) f(x) = 2x1-x2 + x3 min (max)

x1

(2) 2x

2x2

2x

x3 2

x 3

1 2 3



x1

x2

x3 4

(3) x1tùy ý, x20, x30

Giải

Để đưa bài tốn về dạng chính tắc, ta phải đưa các ràng buộc bất phương trình về phương trình, đồng thời tất cả các ẩn số đều phải không âm. Như vậy, ta cần thực hiện các phép biến đổi sau:

Cộng vế trái ràng buộc thứ nhất ẩn phụ x40 và hệ số trong hàm mục tiêu của x4là 0.

x

x

x

-

Trừ vế trái ràng buộc thứ hai ẩn phụ x50 và hệ số trong hàm mục tiêu của x5là 0.

Thay x1 =

' x" , với

' 0 ,

x" 0. Thay x3 = -

x' , với '

0.

1

1

3

x

1

x

1

1

3

1

3

Ta có bài toán chính tắc ( P ) tương ứng với bài toán (P) là:

3

(1’) f ( x ) = 2

' - 2 x" -x2 - '

min (max)

x

1



1

' x"



2x2

x'

x4 2

1

3

(2’)

2x' 2x"

2x2

x' x5 3

1

x

1

x

' "

x

1

1

x2

x' 4

3

(3’)

' 0 ,

x" 0, x2 0, '

0, x4 0, x5 0

1

x

3

Nhận xét( liên hệ giữa bài toán tổng quát và bài toán chính tắc)

Gọi D là miền phương án của bài tốn tổng quát (P) và D là miền phương án của bài tốn chính tắc ( P ). Vì f(x) = f ( x ), xD và x D nên ta có:

Bài toán (P) có phương án khi và chỉ khi ( P ) có phương án. (vì D D )

Nếu bài tốn ( P ) không có PATƯ thì bài tốn (P) không có PATƯ.

Rõ ràng, ( x', x",x2, x', x4, x5) là phương án tối ưu của bài tốn ( P ) khi và chỉ

1 1 3

khi ( x'- x",x2, - x') là phương án tối ưu của bài tốn (P).

1 1 3

Vì các phép biến đổi để đưa bài tốn QHTT tổng quát về bài tốn QHTT chính tắc đều là phép biến đổi tương đương nên ta có kết luận sau.

Kết luận

Mọi bài toán QHTT tổng quát đều có thể đưa về bài toán QHTT dạng chính tắc.

Bài toán tổng quát (P) có phương án khi và chỉ khi bài tốn chính tắc ( P ) có phương án.

Bài toán tổng quát (P) có PATƯ khi và chỉ khi bài toán chính tắc ( P ) có PATƯ.

Như vậy, ta chỉ cần giải bài toán QHTT dạng chính tắc.

2.3. Bài toán qui hoạch tuyến tính dạng chuẩn (còn gọi là dạng chính tắc khả giải)

2.3.1 Bài toán dạng chuẩn

Bài toán sau đây gọi là bài toán QHTT dạng chuẩn Tìm x = (x1, x2,…, xn) nsao cho :

n

(1) f(x) = c jx j

j1

min ( max)

n

(2) aijx jbi

j1

, i = 1, 2, …, m

(3) xj 0 , j = 1, 2, …, n

Trong đó hệ phương trình tuyến tính (2) là hệ phương trình chuẩn và các hệ số vế phải bi0 , i = 1, m .

Nhận xét

Bài toán QHTT dạng chuẩn là trường hợp đặc biệt của bài toán QHTT dạng chính tắc.

Vì bi 0, i = 1, m

thỏa (3).

2.3.2 Phương án cơ bản

nên mỗi nghiệm cơ bản của hệ phương trình chuẩn (2) cũng

Mỗi nghiệm cơ bản của hệ phương trình chuẩn (2) gọi là một phương án cơ bản (PACB) hay phương án cực biên của bài toán QHTT dạng chuẩn. Nói cách khác, một phương án mà các ẩn không cơ bản đều bằng 0 gọi là phương án cơ bản.

Một PACB mà tất cả các ẩn cơ bản đều nhận giá trị dương gọi là PACB không suy biến (bi> 0, i = 1, m ) . Ngược lại, một PACB mà có ít nhất một ẩn cơ bản nhận giá trị 0 gọi là PACB suy biến.

Vì số nghiệm cơ bản của một hệ phương trình chuẩn là hữu hạn nên số PACB của một bài toán QHTT dạng chuẩn cũng hữu hạn.

Ví du 5Các bài toán QHTT sau đây có dạng chuẩn.

a) (1) f(x) = 2x1+ x2-3x3 +x4 +x5 min (max)



x1

(2) x2





10x4

15x4

x3 3x4

2x5 1

3x5 2

7x5 3

(3) xj 0, j 1,5

Phương án (x1, x2, x3,x4,x5) = (1;2;3;0;0) là PACB không suy biến.

b) (1) f(x) = 2x1+3 x2-3x3 +5x4 +x5 –x6 min (max)

2x1

(2) 3x

x2

2x x

3x4

2x

x5 2

4

1 2 3 4



x1

3x2

x4

x6 3

(3) xj 0, j 1,6

Phương án (x1, x2, x3,x4,x5,x6) = (0;0; 4;0;2; 3) là PACB không suy biến. c) (1) f(x) = 2x1+8 x2+3x3-5x4+x5+x6min (max)

2x1

(2) 3x

x2

 2x x

 3x4

 2x

x5  0

 4

1 2 3 4

x x x

x  3

1 2 4 6

(3) xj 0, j 1,6

Phương án (x1, x2, x3,x4,x5,x6) = (0; 0; 4; 0; 0; 3) là PACB suy biến.

n

d) (1) f(x) = c jx j

j1

min (max)



x1



(2) x2





a1 m1 xm1

a2 m1 xm1



xm am m1 xm1

, với bi

0, i =1, 2, …, m

	a1n xn	b1
	a2n xn	b2
		
	amn xn	bm

(3) xj 0 , j = 1, 2, …, n

Phương án (x1, ..., xm, xm+1,...,xn) = (b1,..., bm,0, ..., 0) là PACB. Nếu bi> 0, i = 1, m

thì PACB này không suy biến; nếu bi= 0 thì PACB này suy biến.

Chú ýMọi bài toán QHTT dạng chuẩn đều có thể đánh số lại các ẩn để được bài toán có dạng như trong ví dụ 5.d) này.

2.3.3 Đưa bài toán QHTT dạng chính tắc về bài toán QHTT dạng chuẩn

Cho bài toán QHTT dạng chính tắc ( P ):

n

(1) f(x) = c jx j

j1

min ( max)

n

(2) aijx jbi

j1

, i = 1, 2, …, m

(3) xj 0 , j = 1, 2, …, n

Nếu ( P ) chưa có dạng chuẩn thì ta có thể đưa ( P ) về dạng chuẩn bằng các phép biến đổi sau:

Trong các ràng buộc ở (2) của ( P ), nếu ràng buộc nào có hệ số tự do ở vế phải âm thì ta đổi dấu hai vế để được bi> 0.