QUY HOẠCH TUYẾN _DKE 31012

TRƯỜNG ĐẠI HỌC SÀI GÒN ĐỀ THI KẾT THÚC MÔN HỌC PHÒNG ĐÀO TẠO TẠI CHỨC & TNGV Môn thi: QUY HOẠCH TUYẾN TÍNH Lớp: DKE 31012 Thời gian làm bài: 60 phút

Sinh viên không được tham khảo tài liệu để làm bài

Câu 1. Xí nghiệp sản xuất giấy có 3 phân xưởng. Do trang bị kỹ thuật khác nhau nên mức hao phí tre gỗ, axit để sản xuất một tấn giấy thành phẩm cũng khác nhau. Mức hao phí được cho trong bảng dưới đây:

	Mức hao phí nguyên liệu cho một tấn giấy
Nguyên liệu	Phân xưởng I	Phân xưởng II	Phân xưởng III
Tre gỗ	1.4	1.3	1.2
Axit	0.1	0.12	0.15

Số lượng tre gỗ có trong năm là 1.500.000 tấn, Axit là 100.000 tấn. Yêu cầu:

1. Xây dựng mô hình sao cho tổng số giấy sản xuất trong năm của xí nghiệp là nhiều nhất.

2. Xây dựng mô hình bài toán đối ngẫu với mô hình toán của 1.

3. Tìm phương án tối ưu ứng với mô hình toán ở 1. Từ đó suy ra số tấn giấy của mỗi phân xưởng cần sản xuất trong năm.

4. Áp dụng kết quả bài toán đối ngẫu để từ bảng đơn hình tối ưu 3. suy ra phương án tối ưu cho bài toán đối ngẫu 2.

Câu 2. Cần vận chuyển một loại hàng từ bốn kho hàng đến năm nơi tiêu thụ (cửa hàng). Số lượng đơn vị hàng ở các kho tương ứng là , số lượng đơn vị hàng cần có ở các cửa hàng là và cước phí vận chuyển một đơn vị hàng từ kho thứ i đến cửa hàng thứ j cho bởi ma trận sau:

Hãy lập kế hoạch vận chuyển hàng sao cho đảm bảo cung cầu và cước phí vận chuyển nhỏ nhất.

Sinh viên không được tham khảo tài liệu để làm bài

Câu 1. Một xí nghiệp sản xuất ba mặt hàng . Việc sản xuất được thực hiện theo dây chuyền trên ba máy . Tiền khấu hao mỗi giờ (tính bằng USD) trên mỗi loại máy lần lượt là 2, 1, 3. Thời gian hoạt động tối đa của các máy trong tuần (tính theo giờ) lần lượt là 120, 100 và 80. Thời gian cần thiết đối với các máy (tính theo giờ) để sản xuất một đơn vị mặt hàng được cho bởi bảng sau:


4	1	2
3	3	1
1	2	1

Nguyên liệu được cung cấp tối đa để sản xuất là 250 đơn vị (đv). Lượng nguyên liệu cần thiết để sản xuất một đơn vị mặt hàng các loại lần lượt là 5đv, 3đv, 4đv. Chi phí về chuyên chở, về tiền công và giá bán mỗi đơn vị mặt hàng các loại (tính bằng USD) được cho trong bảng sau:

Chuyên chở	Tiền công	Giá bán
3	2	25
1	2	21
2	3	20

Yêu cầu:

1. Tính lợi nhuận thu được trên mỗi đơn vị mặt hàng.

2. Lập bài toán qui hoạch tuyến tính để xí nghiệp sản xuất đạt lợi nhuận cao nhất trong tuần.

3. Lập bài toán đối ngẫu của bài toán trên.

4. Tìm phương án tối ưu của cả hai bài toán.

Bài 2. Cần vận chuyển một loại hàng từ bốn kho hàng đến nơi tiêu thụ (cửa hàng). Số lượng đơn vị hàng ở các kho tương ứng là , số lượng đơn vị hàng cần có ở các cửa hàng là và cước phí vận chuyển một đơn vị hàng từ kho thứ i đến cửa hàng thứ j cho bởi ma trận sau:

Hãy lập kế hoạch vận chuyển hàng sao cho đảm bảo cung cầu và cước phí vận chuyển nhỏ nhất.

Đáp án đề 1

1. Tính lợi nhuận thu được trên mỗi đơn vị mặt hàng

Lợi nhuận = Giá bán – Tổng các chi phí

LN1=25 – (2.4+1.1+3.2+3+2)=5

LN2=21 – (2.3+1.3+3.1+1+2)=6

LN3=20 – (2.1+1.2+3.1+2+3)=8

2. Lập bài toán quy hoạch tuyến tính

Gọi lần lượt là số lượng các mặt hàng cần sản xuất ()

Lợi nhuận thu được cao nhất khi đạt max

Thời gian sử dụng máy

: không vượt quá 120

: không vượt quá 100

: không vượt quá 80

Nguyên liệu sử dụng

không vượt quá 250

Mô hình: Tìm thoả

(P)

3. Lập bài toán đối ngẫu

(D)

4. Tìm phương án tối ưu của cả hai bài toán.

Chọn bài toán (P) để giải

Đưa bài toán về dạng chính tắc

Lập bảng đơn hình

Hệ số	A.C.B	P.A.C.B	5	6	8	0	0	0	0
Hệ số	A.C.B	P.A.C.B
0		120	4	3	1	1	0	0	0
0		100	1	3	2	0	1	0	0
0		80	2	1	1	0	0	1	0
0		250	5	3	4	0	0	0	1
		0	-5	-6	-8	0	0	0	0
0	4	70	7/2	3/2	0	1	-1/2	0	0
8	3	50	½	3/2	1	0	½	0	0
0	6	30	3/2	-1/2	0	0	-1/2	1	0
0	7	50	3	-3	0	0	-2	0	1
		400	-1	6	0	0	4	0	0
0	4	35/3	0	5	0	1	11/6	0	-7/6
8	3	125/3	0	2	1	0	5/6	0	-1/6
0	6	5	0	1	0	0	½	1	-1/2
5	1	50/3	1	-1	0	0	-2/3	0	1/3
		1250/3	0	5	0	0	10/3	0	-1/3

Phương án tối ưu của bài toán (P) là và .

Suy ra phương án tối ưu của bài toán (D): và .

Bài 2.

· Kiểm tra điều kiện cân bằng thu phát, ta có .

· Xây dựng phương án ban đầu:

· Kiểm tra tính tối ưu, ta thấy .

· Xây dựng phương án mới:

· Kiểm tra tính tối ưu, ta thấy . Ta có phương án tối ưu của bài toán:

, và đơn vị tiền tệ.

Đề 02

Câu 1.

1. Gọi : là số lượng giấy do phân xưởng thứ j sản xuất, j=1,2,3.

Ta có mô hình bài toán:

2. Gọi : là giá trị của tre gỗ và axit.

Ta có mô hình bài toán:

3. Giải bài toán 1 bằng phương pháp đơn hình

Hệ số	A.C.B	P.A.C.B	1	1	1	0	0
Hệ số	A.C.B	P.A.C.B	x₁	x₂	x₃	x₄	x₅
0	x₄	1500000	1.4	1.3	1.2	1	0
0	x₅	100000	0.1	0.12	0.15	0	1
f(x₀)		0	-1	-1	-1	0	0
0	x₄	-12500000	0	-0.38	-0.9	1	-1.4
1	x₅	10000000	1	1.2	1.5	0	10
f(x₁)		10000000	0	0.2	0.5	0	10