Bài toán sản xuất trong quy hoạch tuyến tính

MỘT THỦ TỤC CHỈNH LÝ CHO SƠ ĐỒ NGOẠI SUY RICHARDSON TRONG ĐÁNH GIÁ SAI SỐ VÀ TỐC ĐỘ HỘI TỤ VỚI P-VERSION BẰNG PHÂN TÍCH PHẦN TỬ HỮU HẠN

• 10 de on tap cuoi hoc ki 2 toan 10 ket noi tri thuc voi cuoc song 70 tn 30 tl
• Brief 156672 202005 05162147 Nguyen THI Tuyet MAI
• De thi giua ky 1 toan 8 nam 2021 2022 truong thcs tan dinh ha noi
• phân tích nội dung đi bộ của sinh viên năm nhất
• Bai tap bat dang thuc va bat phuong trinh

Preview text

CHƢƠNG I

BÀI TOÁN

QUY HOẠCH TUYẾN TÍNH

I. MỞ ĐẦU

Trong thực tế sản xuất kinh doanh người ta thường phải giải quyết vấn đề : trong các phương án khả thi, chọn phương án tốt nhất theo mục tiêu nào đó.

Ví dụ cần lập phương án sản xuất kinh doanh sao cho có thể đạt được một trong các yêu cầu sau :

• Tổng giá trị sản lượng là lớn nhất.
• Tổng chi phí là nhỏ nhất.
• Thời gian thực hiện là nhanh nhất.
• Ô nhiễm môi trường ít nhất. -... Những yêu cầu [hoặc mục tiêu] nói trên được biểu diễn bằng một hàm số, gọi là hàm mục tiêu, và ta cần tìm phương án sao cho hàm mục tiêu đạt giá trị lớn nhất hoặc nhỏ nhất. Những bài toán như vậy được gọi chung là các bài toán tối ưu. Các bài toán tối ưu thường gặp trong thực tế là những bài toán tối ưu có ràng buộc, tức là các điều kiện nhất định áp đặt lên các biến của hàm mục tiêu. Các điều kiện ràng buộc thường gặp là :
• Số lượng chủng loại vật tư bị hạn chế.
• Nhân công, thiết bị, tiền vốn... bị hạn chế.
• Số lượng sản phẩm bị hạn chế.
• Thời gian thực hiện bị hạn chế.
• ... Những điều kiện ràng buộc này có thể biểu diễn bằng các hàm, các phương trình, các bất phương trình đối với các biến, chúng lập thành một hệ điều kiện hoặc hệ ràng buộc. Như vậy bằng phương pháp mô hình hoá toán học ta có thể lập được mô hình bài toán tối ưu. Mô hình này gồm hai phần:
• Hàm mục tiêu.
• Hệ ràng buộc.

II. CÁC BÀI TOÁN THỰC TẾ

1. Bài toán lập phƣơng án sản xuất với tài nguyên hạn chế

Khái niệm tài nguyên ở đây dùng để chỉ nguyên vật liệu, thiết bị, nhân công và tiền vốn. Số lượng tài nguyên bị hạn chế bằng số lượng sẵn có hoặc sẽ có được trong thời kỳ thực hiện sản xuất. Để dễ dàng thấy được cách thức lập mô hình toán học của bài toán, ta xét ví dụ sau.

 Ví dụ Một xí nghiệp cần sản xuất 4 loại sản phẩm I, II, III, IV. Để sản xuất các loại sản phẩm này cần sử dụng 3 loại tài nguyên A, B, C. Số lượng hạn chế về các loại tài nguyên, định mức tiêu hao tài nguyên cho một đơn vị sản phẩm và tiền lời của chúng cho ở bảng sau:

Sản phẩm Tài nguyên I II III IV

A 12 5 15 6 300 B 14 8 7 9 500 C 17 13 9 12 200

5 8 4 6 Lời Hạn chế

Các số liệu được hiểu như sau. Cột sản phẩm I: Để sản xuất một đơn vị sản phẩm loại I cần 12 đơn vị tài nguyên loại A, 14 đơn vị tài nguyên loại B và 17 đơn vị tài nguyên loại C. Mỗi đơn vị sản phẩm loại I cho 5 đơn vị tiền lời. Cột sản phẩm II: Để sản xuất một đơn vị sản phẩm loại II cần 5 đơn vị tài nguyên loại A, 8 đơn vị tài nguyên loại B và 13 đơn vị tài nguyên loại C. Mỗi đơn vị sản phẩm loại II cho 8 đơn vị tiền lời.

Cột sản phẩm III: Để sản xuất một đơn vị sản phẩm loại III cần 15 đơn vị tài nguyên loại A, 7 đơn vị tài nguyên loại B và 9 đơn vị tài nguyên loại C. Mỗi đơn vị sản phẩm loại III cho 4 đơn vị tiền lời.

Cột sản phẩm IV: Để sản xuất một đơn vị sản phẩm loại IV cần 6 đơn vị tài nguyên loại A, 9 đơn vị tài nguyên loại B và 12 đơn vị tài nguyên loại C. Mỗi đơn vị sản phẩm loại IV cho 6 đơn vị tiền lời.

Cột cuối cùng: Số lượng hạn chế của tài nguyên loại A là 300 đơn vị, tài nguyên loại B là 500 đơn vị, tài nguyên loại C là 200 đơn vị.

Xác định số liệu để ghi vào bảng trên là công việc của các nhà kinh tế, chuyên

môn, không thuộc phạm vi quy hoạch tuyến tính.

Nhiệm vụ đặt ra là xây dựng phương án sản xuất, tức là số lượng mỗi sản phẩm, sao cho tổng tiền lời là lớn nhất đồng thời không sử dụng quá số tài nguyên đã có.

Trước tiên chúng ta cần thiết lập mô hình của bài toán này. Gọi x 1 , x 2 , x 3 , x 4 lần lượt là số lượng sản phẩm loại I, II, III, IV cần sản xuất. Đây là những số cần tìm. Hàm mục tiêu sẽ là f = 5x 1 + 8x 2 + 4 x 3 + 6x 4  max [1] Hệ ràng buộc là 12 x 1 + 5x 2 + 15x 3 + 6x 4 ≤ 300 14 x 1 + 8x 2 + 7 x 3 + 9x 4 ≤ 500 [2] 17 x 1 + 13x 2 + 9 x 3 + 12x 4 ≤ 200 Điều kiện về dấu của các biến: x 1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0 [3] Điều kiện [3] có được là vì số lượng sản phẩm không thể âm. Nhiệm vụ của bài toán là tìm bộ giá trị [x 1 , x 2 , x 3 , x 4 ] thoả mãn các ràng buộc [2] và [3] và sao cho hàm mục tiêu f đạt giá trị lớn nhất.

 Mô hình tổng quát

Ký hiệu : n là số loại sản phẩm [j = 1, ..., n]

 Ví dụ

Có ba loại thức ăn I, II, III dùng trong chăn nuôi. Các chất dinh dưỡng cơ bản là chất đạm, chất béo và Albumin. Mức độ yêu cầu các chất dinh dưỡng trong mỗi ngày, hàm lượng các chất dinh dưỡng có trong mỗi loại thức ăn và giá cả của chúng cho ở bảng sau. Thức ăn Dinh dưỡng I II III Đạm 0,5 10 0,4 20 Béo 3 0,5 0,7 10 Albumin 0,3 0,8 2 15 0,8 1,5 3 Đơn giáYêu cầu

Các số liệu được hiểu như sau. Cột thức ăn I: Một đơn vị thức ăn loại I chứa 0,5 đơn vị chất đạm, 3 đơn vị chât béo và 0,3 đơn vị Albumin. Mỗi đơn vị thức ăn loại I có giá là 0,8 đơn vị tiền tệ. Cột thức ăn II: Một đơn vị thức ăn loại I chứa 10 đơn vị chất đạm, 0,5 đơn vị chât béo và 0,8 đơn vị Albumin. Mỗi đơn vị thức ăn loại I có giá là 1,5 đơn vị tiền tệ. Cột thức ăn III: Một đơn vị thức ăn loại I chứa 0,4 đơn vị chất đạm, 0,7 đơn vị chât béo và 2 đơn vị Albumin. Mỗi đơn vị thức ăn loại I có giá là 3 đơn vị tiền tệ. Cột cuối cùng: Yêu cầu tối thiểu của chất đạm là 20 đơn vị, của chất béo là 10 đơn vị và của Albumin là 15 đơn vị. Xác định số liệu để ghi vào bảng trên là công việc của các nhà kinh tế, chuyên môn, không thuộc phạm vi quy hoạch tuyến tính. Nhiệm vụ đặt ra là : cần xác định số lượng thức ăn mỗi loại sao cho đảm bảo yêu cầu về dinh dưỡng, đồng thời giá thành khẩu phần thức ăn là rẻ nhất. Ta cần thành lập mô hình của bài toán này: Gọi x 1 , x 2 , x 3 lần lượt là số lượng thức ăn loại I, II, III cần mua. Đây là những số cần tìm.

Hàm mục tiêu sẽ là : f = 0,8x 1 + 1,5x 2 + 3x 3  min [1] Hệ ràng buộc là 0,5x 1 + 10x 2 + 0,4x 3  20 3 x 1 + 0,5x 2 + 0,7x 3  10 [2] 0,3x 1 + 0,8x 2 + 2 x 3  15 Điều kiện về dấu của các biến: x 1  0, x 2  0, x 3  0 [3] Điều kiện [3] có được vì là số lượng thức ăn không thể âm. Nhiệm vụ của bài toán là tìm bộ giá trị [x 1 , x 2 , x 3 ] thỏa mãn các ràng buộc [2] và [3] và sao cho hàm mục tiêu f đạt giá trị nhỏ nhất.

 Mô hình tổng quát Ký hiệu : n là số loại thức ăn [j = 1, ..., n] m là số loại dinh dưỡng cần cho khẩu phần [i = 1, ..., m]

a ij là hàm lượng chất dinh dưỡng i có trong một đơn vị thức ăn j

[i = 1, ..., m, j = 1, ..., n]

b i là số đơn vị chất dinh dưỡng i cần cho 1 khẩu phần thức ăn [i = 1, ..., m]

c j là đơn giá 1 đơn vị thức ăn j [ j = 1, ..., n]

x j là số lượng thức ăn j cần mua cho một khẩu phần thức ăn [ j = 1, ..., n]

Hàm mục tiêu là: f = c 1 x 1 + c 2 x 2 + ... + cnxn Bài toán có thể phát biểu như sau: Xác định các giá trị x 1 , ..., xn sao cho hàm mục tiêu f đạt giá trị nhỏ nhất đồng thời đảm bảo yêu cầu dinh dưỡng cho mỗi khẩu phần thức ăn. Mô hình toán học của bài toán là:

Các loại phôi

Chiều dài phôi [cm]

Số lượng phôi cần cắt

Phương pháp cắt phôi

1 2 3 4 5 6 7 8

1 57 100 3 2 2 1 1 2 82 200 1 1 2 1 3 101 300 1 1 2 4 131 400 1 1 Phế liệu 50 25 6 8 0 38 19 33

Các số liệu được hiểu như sau: Phôi loại một chiều dài 57cm và yêu cầu 100 cái, phôi loại 2 chiều dài 82cm và yêu cầu 200 cái, phôi loại 3 chiều dài 101cm và yêu cầu 300 cái và phôi loại 4 chiều dài 131cm và yêu cầu 400 cái. Theo cách cắt 1, một tấm tôn đươc cắt thành 3 phôi loại 1 hết 3  57 = 171 cm còn dư 221 – 171 = 50cm. Tương tự đối với các cách cắt khác. Xác định số liệu để ghi vào bảng trên là công việc các nhà kinh tế, chuyên môn, không thuộc phạm vi quy hoạch tuyến tính. Nhiệm vụ đặt ra là cần xác định số lượng tôn cắt theo mỗi phương pháp sao cho đảm bảo yêu cầu về phôi đồng thời tổng phế liệu là nhỏ nhất. Ta cần thành lập mô hình của bài toán này. Gọi x 1 , x 2 , ..., x 8 lần lượt là số lượng tấm tôn cắt theo cách 1, 2, ..., 8. Đây là những số cần tìm. Hàm mục tiêu sẽ là: f = 50 x 1 + 25x 2 + 6x 3 + 8x 4 + 0 5 + 38x 6 + 19x 7 + 33x 8  min [1] Hệ ràng buộc là:

3 x 1 + 2x 2 + 2x 3 + x 5 + x 8 = 100 x 2 + x 4 + 2x 5 + x 6 = 200 [2] x 3 + x 6 + 2x 7 = 300 + x 4 + x 8 = 400 Điều kiện về dấu của các biến : xj  0 [j = 1, ..., 8] [3] Điều kiện [3] có được là vì số lượng tấm tôn không thể âm. Nhiệm vụ của bài toán là tìm bộ giá trị [x 1 , x 2 , ..., x 8 ] thoả mãn các ràng buộc [2] và [3] sao cho hàm mục tiêu f đạt giá trị nhỏ nhất.  Mô hình tổng quát Ký hiệu : n là số phương pháp cắt vật liệu [j = 1, ... , n] m là số loại phôi [i = 1, ... , m] aij là số phôi loại i cắt được từ 1 tấm vật liệu theo phương pháp j [i = 1, ..., m ; j = 1, ..., n] bi là số lượng phôi loại i cần cắt [i = 1, ..., m] cj là phế liệu từ 1 tấm vật liệu cắt theo phương pháp j [j = 1, ..., n] xj là số tấm vật liệu cắt theo phương pháp j [j = 1, ..., n] Hàm mục tiêu là: f = c 1 x 1 + c 2 x 2 + ... + cnxn Bài toán có thể phát biểu như sau : Xác định các giá trị x 1 , ..., xn sao cho hàm mục tiêu f đạt giá trị nhỏ nhất đồng thời đảm bảo yêu cầu của từng loại phôi. Mô hình toán học của bài toán là : f = c 1 x 1 + ... + cnxn  min [1] a 11 x 1 + ... + a 1 nxn = b 1 .................. [2] am 1 x 1 + ... + amnxn = bm x 1  0, ..., xn  0 [3]







Bài toán max: f = c 1 x 1 + ... + cnxn  max [1] với điều kiện [2] và [3], tương đương với bài toán min sau: g =  f = c 1 x 1  ...  cnxn  min [1’] với điều kiện [2] và [3]. Khi đó phương án tối ưu của bài toán min cũng là phương án tối ưu của bài toán max và trị tối ưu f * = g*. Như vậy ta chỉ cần phát triển thuật toán giải bài toán min là đủ.

[ii] Biến đổi các biến không có ràng buộc  0 về các biến có ràng buộc  0.

Với những biến xj có ràng buộc xj  0, ta thay bằng biến xj’ = xj có ràng buộc

tương đương xj’  0. Với những biến xj không có ràng buộc về dấu ta đặt: xj = xj’  xj”

trong đó xj’  0 và xj”  0. Như vậy hệ ràng buộc về dấu [3] có thể quy về trường hợp xj  0,  j = 1, ..., n.

[iii] Biến đổi tương đương các ràng buộc  và  Trong hệ ràng buộc [2], những ràng buộc dạng ai 1 x 1 + ... + ainxn  bi tương đương với ràng buộc ai 1 x 1  ...  ainxn  bi Như vậy mọi ràng buộc ở hệ [2] dạng  có thể quy về dạng  và ngược lại. [iv] Biến đổi tương đương các ràng buộc bất đẳng thức về ràng buộc đẳng thức Trong hệ ràng buộc [2], những ràng buộc dạng ai 1 x 1 + ... + ainxn  bi tương đương với ràng buộc ai 1 x 1 + ... + ainxn  zi = bi

trong đó zi là biến phụ [biến bù] với ràng buộc zi  0. Những ràng buộc dạng

ai 1 x 1 + ... + ainxn  bi tương đương với ràng buộc ai 1 x 1 + ... + ainxn + zi = bi

trong đó zi là biến phụ [biến bù] với ràng buộc zi  0. Ngược lại ràng buộc dạng ai 1 x 1 + ... + ainxn = bi tương đương với 2 ràng buộc

ai 1 x 1 + ... + ainxn  bi và ai 1 x 1  ...  ainxn  bi Như vậy mọi ràng buộc ở hệ [2] dạng  hoặc  có thể quy về dạng = và ngược lại.

2. Bài toán quy hoạch tuyến tính dạng chuẩn

Bài toán quy hoạch tuyến tính dạng chuẩn min định nghĩa như sau: f = c 1 x 1 + .... + cnxn  min [1]

với điều kiện

ai 1 x 1 + .... + ainxn  bi [i = 1, ...., m] [2] xj  0 [j = 1, ...., n] [3] Bài toán quy hoạch tuyến tính dạng chuẩn max định nghĩa như sau: f = c 1 x 1 + .... + cnxn  max [1]

với điều kiện

ai 1 x 1 + .... + ainxn  bi [i = 1, ...., m] [2] xj  0 [j = 1, ...., n] [3] Rõ ràng là bài toán quy hoạch tuyến tính dạng chuẩn là trường hợp riêng của bài toán tổng quát. Bằng các kỹ thuật biến đổi tương đương trên ta dễ dàng suy ra:  Mệnh đề 1. Mọi bài toán quy hoạch tuyến tổng quát đều có thể đưa về bài toán quy hoạch tuyến tính dạng chuẩn tương đương.  Ví dụ. Xét bài toán quy hoạch tuyến tính [P]

Cuối cùng bài toán tương đương dạng chuẩn min [P’] có dạng : g = 3 x 1 + 2x 2 ’ + x 3 ’  x 3 ”  min [1’] 2 x 1  3 x 2 ’ + x 3 ’ – x 3 ”  2 x 1 + x 2 ’ – x 3 ’ + x 3 ”   1 [2’] x 1 – 4 x 2 ’ + x 3 ’  x 3 ”  1 x 1 + 4x 2 ’ – x 3 ’ + x 3 ”   1 x 1  0, x 2 ’  0, x 3 ’  0, x 3 ”  0 [3’]

3. Bài toán quy hoạch tuyến tính dạng chính tắc

Bài toán quy hoạch tuyến tính dạng chính tắc min [max] được định nghĩa như sau: f = c 1 x 1 + .... + cnxn  min [max] [1]

với điều kiện ai 1 x 1 + .... + ainxn = bi [i = 1, ...., m] [2] xj  0 [ j =1, ...., n] [3] Rõ ràng là bài toán quy hoạch tuyến tính dạng chính tắc là trường hợp riêng của bài toán tổng quát. Bằng các kỹ thuật biến đổi tương đương trên ta dễ dàng suy ra:  Mệnh đề 2. Mọi bài toán quy hoạch tuyến tổng quát đều có thể đưa về bài toán quy hoạch tuyến tính dạng chính tắc tương đương.  Ví dụ. Xét bài toán quy hoạch tuyến tính [P]

f =  3 x 1 + 2x 2 – x 3  max [1] 2 x 1 + 3x 2 + x 3  2 x 1 + x 2 + x 3  1 [2] x 1 + 4x 2 + x 3 = 1 x 1  0, x 2  0 [3] Ta chuyển bài toán [P] về bài toán quy hoạch tuyến tính dạng chính tắc min [P”] tương đương.

• Biến x 2 thay bằng biến x 2 ’ = x 2 với điều kiện x 2 ’  0, x 2 = x 2 ’.
• Biến x 3 thay bằng biến x 3 ’ và x 3 ” với điều kiện x 3 ’ ≥ 0, x 3 ” ≥ 0 và x 3 = x 3 ’  x 3 ”
• Hàm mục tiêu f chuyển thành g = f = 3x 1  2 x 2 + x 3 = 3x 1 + 2x 2 ’ + x 3 ’  x 3 ”  min [1”]
• Biến đổi ràng buộc thứ nhất 2 x 1 + 3x 2 + x 3  2  2 x 1  3 x 2 ’ + x 3 ’ – x 3 ”  2  2 x 1 – 3 x 2 ’ + x 3 ’ – x 3 ” – z 1 = 2

trong đó z 1 là biến phụ với ràng buộc z 1  0. - Biến đổi ràng buộc thứ 2 x 1 + x 2 + x 3  1  x 1  x 2 ’ + x 3 ’ – x 3 ” ≤ 1  x 1  x 2 ’ + x 3 ’ – x 3 ” + z 2 = 1

trong đó z 2 là biến phụ với ràng buộc z 2  0. - Biến đổi ràng buộc thứ 3 thành ràng buộc mới x 1 + 4x 2 + x 3 = 1  x 1 – 4 x 2 ’ + x 3 ’  x 3 ” = 1 Cuối cùng bài toán chính tắc min tương đương [P”] có dạng :

BÀI TẬP

1. Một trại chăn nuôi định nuôi 3 loại bò: bò sữa, bò cày và bò thịt. Số liệu điều tra cho ở bảng sau: Loại bò Vốn / con Chi phí nuôi / con Lãi / con Bò sữa 123 120 59 Bò cày 127 150 49 Bò thịt 162 150 57 Cộng ≤ 7020 ≤ 800 0 Max? Lập bài toán tìm số bò mỗi loại cần nuôi để đạt số tiền lãi lớn nhất, biết rằng số bò sữa không quá 18 con. Đưa bài toán về dạng chính tắc min tương đương.
2. Một đội sản xuất dành 31 sào trồng bắp cải, cà chua, đậu, khoai tây, hành. Số liệu điều tra về công, chi phí kể cả phân và giống, cho ở bảng sau: Loại Công /sào Chi phí /sào Lãi /sào Bắp cải 79 38 376 Cà chua 55 22 128 Đậu 23 31 104 Khoai tây 26 63 177 Hành 35 50 310 Cộng ≤ 1892 ≤ 1828 Max? Lập bài toán tìm phương án phân phối đất trồng mỗi loại để được lời nhiều nhất. Đưa bài toán về dạng chính tắc min tương đương.
3. Để sản xuất 3 loại sản phẩm I, II, III cần dùng 4 loại nguyên liệu N1, N2, N3, N4. Bảng sau cho lượng dự trữ từng loại nguyên liệu, định mức nguyên liệu cần dùng để sản xuất 1 đơn vị sản phẩm mỗi loại và thu nhập của xí nghiệp từ 1 đơn vị sản phẩm mỗi loại: Loại Nguyên liệu Dự trữ nguyên liệu

Định mức nguyên liệu cho 1 sản phẩm Loại I Loại II Loại III N1 22 2 3 1 N2 16 2 1 0 N3 18 0 0 3 N4 21 3 3 4 Thu nhập 7 5 6

Lập bài toán tìm phương án sản xuất các loại sản phẩm sao cho tổng thu nhập của xí nghiệp là nhiều nhất. Đưa bài toán về dạng chính tắc min tương đương. 4. Một xí nghiệp có 4 loại máy A, B, C, D sản xuất 6 loại sản phẩm 1, 2, 3, 4, 5, 6. Định mức thời gian [h/cái] của mỗi loại máy sản xuất từng loại sản phẩm và số giờ làm việc nhiều nhất của mỗi loại máy trong 1 tuần cho ở bảng sau: Sản phẩm Định mức [h/cái] Máy

Số giờ máy 1 tuần A 0 0 0 0 0 0 85 B 0 - - 0 - - 70 C - 0 - - 0 - 10 D - - 0 - - 0 90 Giá 1 sản phẩm [1đ] 4 2 3 7 6 6.

Max?

Hãy lập bài toán tính xem trong 1 tuần phải sản xuất bao nhiêu sản phẩm mỗi loại để cho tổng giá trị sản phẩm là lớn nhất. Đưa bài toán về dạng chính tắc min tương đương.

1. Một xí nghiệp sản xuất tủ lạnh dùng các tấm tôn có diện tích 1420  710 mm để làm nguyên liệu. Những tấm tôn này sẽ được cắt thành các tấm bé hơn. Cần cắt các tấm tôn như thế nào để tổng phế liệu là nhỏ nhất. Kích thước và số lượng yêu cầu của các tấm bé cho ở bảng sau: Loại tấm bé Kích thước Số lượng 1 749  608 2520 2 186  170 1260 3 270  48 5047 4 142  77 1520

Xác định các phương pháp cắt tôn. Lập bài toán tìm phương án cắt các tấm tôn để tổng phế liệu là nhỏ nhất. Đưa bài toán về dạng chính tắc min tương đương.