TRƯỜNG ĐẠI HỌC SÀI GÒN                                         KÌ THI KẾT THÚC HỌC PHẦN

        KHOA TOÁN - ỨNG DỤNG                                        HỌC KỲ I - NĂM HỌC 2011 - 2012

ĐỀ THI HỌC PHẦN: QUY HOẠCH TUYẾN TÍNH. ĐỀ SỐ: 01.

DÀNH CHO LỚP: DQK 110.

THỜI GIAN LÀM BÀI: 90 phút (Không kể thời gian phát đề).

Câu 1: (6đ)  Một xí nghiệp sản xuất hai loại sản phẩm A và B từ ba loại nguyên liệu C, D và E với số lượng dự trữ lần lượt là 160, 200 và 120 đon vị. Để sản xuất ra mỗi đơn vị sản phẩm loại A cần sử dụng 4 đơn vị nguyên liệu C, 8 đơn vị nguyên liệu D và 6 đơn vị nguyên liệu E. Các chỉ số đó cho mỗi đơn vị sản phẩm B theo thứ tự trên là 8, 6 và 4. Do điều kiện thực tế, xí nghiệp bắt buộc phải sử dụng hết 120 đơn vị nguyên liệu loại E hiện có. Cho biết lợi nhuận thu được trên mỗi sản phẩm loại A và loại B lần lượt là 6 triệu đồng và 8 triệu đồng.

1.     Hãy thiết lập kế hoạch sản suất nhằm đạt tổng lợi nhuận tối đa và tìm phương án sản xuất tối ưu bằng phương pháp thích hợp.

2.     Viết bài toán đối ngẫu của bài toán trên và tìm phương án tối ưu của nó.

Câu 2: (4đ) Một công ty có ba xí nghiệp cùng sản xuất một loại sản phẩm. Năng suất trong tháng của ba xí nghiệp lần lượt là  sản phẩm. Hợp đồng công ty phải giao cho bốn nhà phân phối là  sản phẩm. Đơn giá (đơn vị tính: 1000 đồng) của mỗi sản phẩm tương ứng với các nhà phân phối được 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 (phương án tối ưu).

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

HẾT

TRƯỜNG ĐẠI HỌC SÀI GÒN                                               KÌ THI KẾT THÚC HỌC PHẦN

        KHOA TOÁN - ỨNG DỤNG                                        HỌC KỲ I - NĂM HỌC 2011 - 2012

ĐỀ THI HỌC PHẦN: QUY HOẠCH TUYẾN TÍNH. ĐỀ SỐ: 02.

DÀNH CHO LỚP: DQK110.

THỜI GIAN LÀM BÀI: 90 phút (Không kể thời gian phát đề).

Câu 1: (6đ)  Một xí nghiệp sản xuất ba loại sản phẩm A, B và C từ ba loại nguyên liệu dự trữ I, II và III với số lượng đơn vị từ các nguyên liệu dự trữ hiện có lần lượt là 120, 80 và 160. Để sản xuất ra mỗi đơn vị sản phẩm loại A cần sử dụng 3 đơn vị nguyên liệu dự trữ loại I, 2 đơn vị nguyên liệu dự trữ loại II và 1 đơn vị nguyên liệu dự trữ loại III. Các số liệu tương tự cho mỗi đơn vị sản phẩm loại B và C lần lượt là 4, 1, 3 và 2, 2, 2. Biết lợi nhuận thu được trên mỗi đơn vị sản phẩm loại A, B và C lần lượt là 2 triệu đồng, 4 triệu đồng và 3 triệu đồng. Anh (chị) hãy

1.     Xây dựng mô hình (P) để xí nghiệp sản xuất đạt lợi nhuận tối đa và tìm phương án tối ưu của bài toán;

2.     Viết bài toán đối ngẫu (D) của bài toán (P) và tìm phương án tối ưu của nó.

Câu 2: (4đ) Một công ty có ba xí nghiệp cùng sản xuất một loại sản phẩm. Năng suất trong tháng của ba xí nghiệp lần lượt là  sản phẩm. Hợp đồng công ty phải giao cho bốn nhà phân phối là  sản phẩm. Đơn giá (đơn vị tính: 1000 đồng) của mỗi sản phẩm tương ứng với các nhà phân phối được 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 (phương án tối ưu).

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

HẾT

Câu 1.

1.     Gọi : là số lượng sản phẩm loại j của xí nghiệp sản xuất, j=A,B.

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

.

Ta có bảng đơn hình

Ta có các , do đó phương án tối ưu của bài toán:

          và

2.     Gọi : là giá trị của nguyên vật liệu thứ i (i=C, D, E).

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

Từ bảng đơn hình ta có kết quả của bài toán đối ngẫu, như sau:

và .

Câu 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 tính tối ưu, ta thấy .

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

·        Kiểm tra tí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ệ.

Câu 1.

a)      Gọi : là số lượng sản phẩm loại A, B, và C (j=1,2,3)

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

.

Giải bài toán (P) bằng phương pháp đơn hình

§  Phương án tối ưu của bài toán  và .

b)      Gọi : là giá trị của nguyên vật liệu tương ứng..

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

Từ bảng đơn hình của câu a), ta suy ra phương án tối ưu của bài toán (D):

Hay  và

Câu 2.

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

·        Ta thêm một trạm phát giả  và .

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

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

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

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