Quy hoạch toán học - Ngô Hữu Tâm

Ô đưa ra là ô (3,3) và lượng điều chỉnh là cước phí” các ô chọn ta được:

x33 200 . Lập phương án mới rồi “quy 0

Xí nghiệp Sản phẩm	B1 1600	B2 2000	B3 2400
A1:2800	0  1600	0  1000	0,5 M  200
A2:2200	1 M	1 M	0  2200
A3: 1000	0,5	0  1000	0 0

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

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

cho

r1  0

r2  0,5 M

r3  0

s1  0

s2  0

s3 M  0,5

Tính lại “cước phí” các ô

Xí

nghiệp Sản phẩm

B1 1600		B2 2000		B3 2400
A1:2800	0	 1600	0	 1000	0  200
A2:2200	1,5		1,5		0  2200
A3: 1000	0,5		0	 1000	M  0,5 0

Tất cả các ô đều có cước phí không âm nên phương án cơ bản nà tối ưu. Vì ô cấm

(3,3) nhận giá trị 0 nên bài toán có phương án tối ưu là:

Xí

nghiệp Sản phẩm

B1 1600

B2 2000

B3 2400

A1:2800

1600

7,5

1000

200

A2:2200

8,5

7,5

2200

Tổng chi phí bé nhất:

10.000 đoàng)

f min  11600  7,5 1000  8  200  7,5  2200 =27200(đôn vò tính

Ví dụ 7

 272000 (đôn vò tính 1.000 đoàng)

 272000000

đoàng

 272 (triệu đồng)

Một công ty may mặc cần phân phối 2200 đơn vị sản phẩm may mặc loại A1, 2800 đơn vị sản phẩm may mặc loại A2vào ba xí nghiệp B1, B2, B3để sản xuất, với năng lực sản xuất (số đơn vị sản phẩm loại A1hay sản phẩm loại A2) lần lượt là 1600, 2400, 2000 đơn vị sản phẩm. Chi phí (đơn vị tính 10.000 đồng/1đơn vị sản phẩm) sản xuất của công ty khi phân phối mỗi đơn vị sản phẩm cho các xí nghiệp sản xuất được cho trong bảng sau

Xí

nghiệp Sản phẩm

B1 1600	B2 2400	B3 2000
A1:2200	8	8	8,5
A2:2800	7,5	9	8

Vì chiến lược phát triển công ty, nên xí nghiệp B2phải thu đủ 2400 đơn vị sản phẩm để sản xuất. Hỏi phải phân phối sản phẩm cho các xí nghiệp sản xuất như thế nào để tổng chi phí thấp nhất và tính tổng chi phí thấp nhất đó?

Giải

Bài tốn này có dạng bài tốn vận tải không cân bằng thu phát với lượng phát ít hơn

lượng thu là

(1600  2400  2000)  (2200  2800)  1000 . Lập thêm trạm giả

A3với

lượng cần phát

a3 1000 . Để trạm

B2thu đủ thì lượng hàng giả trạm

A3 không được

phát vào trạm

B2nên ô

(3,2)

là ô cấm, vì cần tổng chi phí thấp nhất nên đây là bài

toán

f  min

do đó “cước phí” ô (3,2)

là M (với M là số dương lớn tùy ý).

Lần lượt phân phối như sau: ô (2,1)

ô (3,3) 800

1600 ; ô (1,2)

2200; ô (2,3)

1200; ô (3,2)

200;

Xí nghiệp Sản phẩm	B1 1600		B2 2400	B3 2000
A1:2200	8		8	 2200	8,5
A2:2800	7,5	 1600	9	8	 1200
A3: 1000	0		M	 200	0	 800

Sau khi phân phối xong ta được phương án cơ bản ban đầu không suy biến, rồi tiếp theo “quy 0 cước phí” các ô chọn ta được:

r1 M

cho

r2  0

r3  8

s1 7,5

Tính lại “cước phí” các ô

s2 M  8

s3 8

Xí

nghiệp Sản phẩm

B1 1600

B2 2400

B3 2000

A1:2200

M+0,5

0 

2200

M+0,5

A2:2800

0 

1600

-M+1 

Đưa vào

0 

1200

A3: 1000

0,5

0 

Đưara 200

0 

800

Còn ô (2,2) có “cước phí” âm nên phương án cơ bản hiện có không tối ưu. Ô đưa vào là ô (2,2).

Vòng điều chỉnh là V (2,2), (2,3), (3,2), (3,3), V L(2,2), (3,3),V C(2,3), (3,2).

Ô đưa ra là ô (3,2)

và lượng điều chỉnh là

x32 200 . Lập phương án mới rồi “quy 0

Xí nghiệp Sản phẩm	B1 1600	B2 2400	B3 2000
A1:2200	M+0,5	0  2200	M+0,5
A2:2800	0  1600	-M+1  200	0  1000
A3: 1000	0,5	0 0	0  1000

cước phí” các ô chọn ta được:

r1 M  1

cho

r2  0

r3  0

s1  0

Tính lại “cước phí” các ô

s2 M 1

s3  0

Xí nghiệp Sản phẩm	B1 1600		B2 2400		B3 2000
A1:2200	1,5		0	 2200	1,5
A2:2800	0	 600	0	 200	0	 1000
A3: 1000	0,5		M-1	0	0	 1000

r1 M  1

cho

r2  0

r3  0

s1  0

s2 M 1

s3  0

Tất cả các ô đều có cước phí không âm nên phương án cơ bản nà tối ưu. Vì ô cấm

(3,2)

nhận giá trị 0 nên bài toán có phương án tối ưu là:

Xí

nghiệp

Sản phẩm

B1 1600

B2 2400

B3 2000

A1:2200

2200

8,5

A2:2800

7,5

1600

200

1000

Tổng chi phí bé nhất: f min  8  2200  7,5 1600  9  200  8 1000 =39400(đôn vò tính 10.000 đoàng)

 39400 (đôn vò tính 1.000 đoàng)

 394000000

đoàng

 394 (triệu đồng)

Chú yù Có thể giải bằng thuật toán thế vị ( gọn hơn thuật toán quy 0 cước phí 2 bảng vận tải).

Ví dụ 8

Một công ty cần bán 120 đơn vị sản phẩm loại A1, 45 đơn vị sản phẩm loại A2, 85 đơn vị sản phẩm loại A3thông qua bốn đại lý B1, B2, B3, B4với khả năng bán (số đơn vị sản phẩm loại A1hay sản phẩm loại A2hay sản phẩm loại A3) lần lượt là 60, 90, 70, 50 đơn vị sản phẩm. Lợi nhuận (đơn vị tính 500.000 đồng/1sản phẩm) khi bán mỗi sản phẩm thông qua mỗi đại lý được cho trong bảng sau

Đại lý

Sản phẩm

B160	B290	B3 70	B4 50
A1:120	3	4	4	5
A2:45	4	6	5	4,5
A3:85	6	6	7	8

Vì chiến lược phát triển kinh doanh của công ty, nên đại lý B1phải thu đủ 60 đơn vị sản phẩm để bán. Hỏi phải phân phối sản phẩm cho các đại lý bán như thế nào để tổng lợi nhuận lớn nhất và tính tổng lợi nhuận lớn nhất đó?

Giải

Bài toán này có dạng bài toán vận tải không cân bằng thu phát với lượng phát ít hơn

lượng thu là

(60  90  70  50)  (120  45  85)  20 . Lập thêm trạm giả

A4 với lượng

cần phát

a4 20 . Để trạm

B1thu đủ thì lượng hàng giả trạm

A4không được phát

vào trạm

B1nên ô

(4,1)

là ô cấm, vì cần tổng lợi nhuận lớn nhất nên đây là bài toán

f  max

do đó

C41 M

(với M là số dương lớn tùy ý).

Lần lượt phân phối như sau: ô (3,4)

50 ; ô (3,3)

35; ô

(2,2)

45; ô (1,2)

45; ô (1,3)

35 ; ô (1,1) 40 ; ô (4,1) 20.

Đại lý

Sản phẩm

B1 60	B2 90	B3 70	B450
A1:120	3  40	4  45	4  35	5
A2:45	4	6  45	5	4,5
A3:85	6	6	7  35	8  50
A4:20 Trạm giả	M  20	0	0	0

Sau khi phân phối xong ta được phương án cơ bản ban đầu không suy biến, tìm các thế vị hàng và các thế vị cột rồi tiếp theo tính kij ui+ vj- cij ta được được:

Đại lý Sản phẩm	B1 60			B2 90			B3 70			B450
A1:120	3		0 40	4		0 45	4		0 35	5	0
A2:45	4		1	6		0 45	5	1		4,5	2,5
A3:85	6		0	6	1		7		0 35	8		0 50
A4:20 Trạm giả	M 0 Đưa ra 20			0	1 M Đưa vào		0	1 M		0	2 M

cho

1  0

u2  2

u3  3

u4 M  3

v1  3

v2  4

v3  4

v4  5

Ô (4,2)

ô (4,2).

có

k42  1 M  0

nên phương án cơ bản hiện có không tối ưu. Ô đưa vào là

Đại lý Sản phẩm	B1 60			B2 90			B3 70			B450
A1:120	3		0 60	4		0 25	4		0 35	5		0
A2:45	4		1	6		0 45	5		1	4,5		2,5
A3:85	6		0	6		1	7		0 35	8		0 50
A4:20	M		M  1	0 		0 20	0		0	0		1

cho

v1  3

v2  4

v3  4

v4  5

1  0

u2  2

u3  3

u4 4

Tất cả các ô đều có

kij  0 nên phương án cơ bản này tối ưu. Vì ô cấm (4,1)

nhận giá

trị phân phối

x41  0

nên bài toán ban đầu có phương án tối ưu là:

Đại lý

Sản phẩm

B160	B290	B3 70	B4 50
A1:120	3  60	4  25	4  35	5
A2:45	4	6  45	5	4,5
A3:85	6	6	7  35	8  50

Tổng lợi nhuận lớn nhất:

f max  [3  60  4  25  4  35  6  45  7  35  8  50]  500.000 đoàng

= 1335  500.000 đoàng = 667500000 đoàng

Chú ý: Có thể giải bằng thuật toán quy 0 cước phí.

....................................................................................................................................

Bài tập

Bài 3.1Tìm phương án cơ bản ban đầu ( f

 min)

Thu

Phát

B1 60	B2 90	B3 55	B4 45
A1: 100	3	4	3,5	5
A2: 70	4	6	5	4,5
A3: 80	5	5,5	6	4,5

a) Trường hợp

f  min

b) Trường hợp

f  max

Bài 3.2Giải bài toán vận tải ( f

 min)

Thu

Phát

B1 70	B2 80	B3 65	B4 85
A1: 100	5	4	6	7
A2: 50	8	5	5	6,5
A3: 60	5,5	6,5	7	7,5
A4: 90	6	7	4	5

Bài 3.3Cho bài toán vận tải ( f

 min)

Thu

Phát

B1 60	B2 90	B3 70	B4 50
A1: 80	3	4	4	5
A2: 45	4	6	5	4,5
A3: 85	5	5	6	7

a) Giải bài toán trên.

b) Giải bài toán trên với điều kiện trạm B3thu đủ hàng.

Bài 3.4Cho bài toán vận tải ( f

 max)

Thu

Phát

B1 60	B2 90	B3 70	B4 50
A1: 80	3	4	4	5
A2: 45	4	6	5	4,5
A3: 85	5	5	6	7

a) Giải bài toán trên.

b) Giải bài toán trên với điều kiện trạm B1thu đủ hàng.

Bài 3.5Một nông trường có 3 khu đất A1, A2, A3có diện tích tương ứng 250, 1400, 350 ha. Nông trường định trồng 4 loại cây B1, B2, B3, B4với diện tích dự định là 500, 400, 600, 500 ha. Lợi nhuận khi trồng loại cây Bjtrên một ha đất Ailà cij (triệu đồng) được cho trong bảng sau:

Loại cây Khu đất

B1 500	B2 400	B3 600	B4 500
A1:250	22	25	20	18
A2:1400	30	32	25	28
A3:350	29	28	25	23

Hãy lập kế hoạch trồng cây của nông trường sao cho tổng lợi nhuận cao nhất.

Đáp soá

Khu đất A1trồng 250 ha loại cây B3.

Khu đất A2trồng 500 ha loại cây B1, 400ha loại cây B2, 500 ha loại cây B4.

Khu đất A3trồng 350 ha loại cây B3.

Tổng lợi nhuận lớn nhất là: 55 550 000 000 đồng.

Bài 3.6Một xí nghiệp có 200 công nhân gồm : 50 loại A1, 70 loại A2, 80 loại A3 . Xí nghiệp lại có 200 máy gồm : 40 loại B1, 60 loại B2, 100 loại B3.Khi sản xuất mỗi công nhân sử dụng một máy để tạo ra cùng một loại sản phẩm. Công nhân lọai A3 không sử dụng được máy lọai B1. Năng suất của mỗi loại công nhân khi sử dụng mỗi loại máy được cho trong bảng sau (sản phẩm/ giờ ). Hỏi phải phân công lao độngnhư thế nào để trong 1 giờ tạo ra được nhiều sản phẩm nhất?

Máy

C. nhân

B1 40	B2 60	B3 100
A1: 50	4	4	7
A2: 70	5	10	9
A3: 80	--	6	5

Bài 3.7Một xí nghiệp có 30 công nhân loại I, 20 công nhân loại II và 10 công nhân loại III. Xí nghiệp có 10 máy A, 25 máy B, 25 máy C. Năng suất của mỗi công nhân đối với mỗi loại máy ( sản phẩm/ giờ) được cho trong bảng sau đây.