So sánh ngôn ngữ ampl và cples
Hãy xem xét ví dụ sau. Công ty sơn Berkeley sản xuất hai màu sơn, xanh dương và vàng. Sơn xanh được bán với giá$10 mỗi gallon, trong khi sơn vàng được bán với giá $15 mỗi gallon. Công ty có một nhà máy và mỗi lần chỉ có thểsản xuất một màu sơn. Tuy nhiên, sơn xanh lam dễ sản xuất hơn nên nhà máy có thể sản xuất 40 ga-lông mỗi giờ sơnxanh, nhưng chỉ có 30 ga-lông mỗi giờ sơn vàng. Ngoài ra, bộ phận tiếp thị nói với nhà sản xuất rằng họ có thểbán tối đa 860 gallon sơn vàng và 1000 gallon sơn xanh. Nếu một tuần là 40 giờ và sơn không thể được lưu trữ chođến tuần sau, chúng ta cần xác định cần tạo ra bao nhiêu gallon sơn xanh và vàng; sao cho tổng doanh thu là lớnnhất.tiêu chuẩn: Show
AMPL là một ngôn ngữ mạnh mẽ được thiết kế dành riêng cho lập trình toán học. AMPL có nhiều tính năng và tùychọn; tuy nhiên hướng dẫn này bao gồm một tập hợp con nhỏ của these1. Các phần từ 1 đến 5 cung cấp phần giớithiệu về lập mô hình các bài toán Quy hoạch tuyến tính (LP) với AMPL. Phần 6 và 7 lần lượt giới thiệu các khảnăng lập mô hình của AMPL cho Lập trình số nguyên (IP) và Lập trình phi tuyến tính (NLP).tối đa 10P aintB + 15P aintGĐể tạo một tệp văn bản, bạn có thể sử dụng bất kỳ trình soạn thảo văn bản nào mà bạn cảm thấy thoải mái. Vídụ: bạn có thể sử dụng Notepad, được tìm thấy trên mọi hệ thống Windows 95 và Windows NT. Để tạo tệp chươngtrình sau, hãy khởi động Notepad và nhập văn bản sau.Đặt P aintB đại diện cho số gallon sơn xanh chúng ta sẽ tạo ra và P aintG đại diện cho số gallon sơn vàng màchúng ta sẽ tạo ra. Sau đó, vấn đề được xây dựng như LP sau:AMPL được thiết kế để cho phép nhập các chương trình toán học theo một cú pháp rất gần với ký hiệu đại số màbạn thấy ở trên. Để sử dụng AMPL, chúng ta cần tạo một tệp văn bản có mã chương trình toán học.1 Mô hình LP đơn giảnGiới thiệu về AMPLHướng dẫn Hướng dẫn này ban đầu được chuẩn bị bởi P. Kaminsky. Phiên bản gốc sau đó được sửa đổi và mở rộng bởi D. Rajan.1Để biết thêm thông tin, hãy xem cuốn sáchAMPL: Ngôn ngữ lập mô hình cho lập trình toán học của R. Fourer, DM Gay và BW Kernighan (1993: Boyd & Fraser)
####### Ngoài ra, đôi khi Notepad tự động thêm phần mở rộng .txt vào tệp, vì vậy bạn có thể phải đổi tên tệp để loại bỏ phần ####### mở rộng .txt. Ví dụ: một số phiên bản Notepad sẽ tự động lưu tệp từ ví dụ trước dưới dạng z:\my iles\examp 1.mod, vì ####### vậy bạn có thể phải chỉnh sửa tên tệp để sử dụng phần mở rộng bổ sung. ####### Đừng quên kết thúc mọi lệnh bằng dấu chấm phẩy. Mỗi khi bạn khởi động AMPL, bạn cần chọn một bộ giải bằng cách sử ####### dụng lệnh bộ giải tùy chọn này. Hiện tại, chúng tôi sẽ luôn sử dụng cplex, nhưng sau này chúng tôi sẽ tìm hiểu về các bộ ####### giải khác. ####### Nếu bạn nhập đúng mô hình, bạn sẽ không nhận được thông báo lỗi nào. Nếu bạn mắc lỗi, hãy sửa tệp mô hình. Trước khi tải ####### lại mô hình, trước tiên bạn phải đặt lại AMPL bằng cách nhập: ####### Sau khi tệp được tạo, tệp sẽ được lưu với phần mở rộng .mod. Đối với các ví dụ sau, tệp được lưu trên ổ đĩa z: trong ####### thư mục myFiles dưới dạng z:\myFiles\examp 1. Lưu ý rằng không thể sử dụng tên tệp dài với AMPL. Tên tệp bạn chọn phải ####### có nhiều nhất tám ký tự theo sau là phần mở rộng ba ký tự.
####### mô hình z:\myFiles\examp_1;
####### menu bắt đầu thích hợp. Sau khi một số văn bản xuất hiện, bạn sẽ thấy lời nhắc AMPL, đó là ampl:. ####### Để tải lại mô hình, hãy nhập: ####### tuyên bố khách quan xuất hiện.
####### Sau khi tệp được tạo và bạn đã kiểm tra tên tệp, hãy chạy chương trình AMPL bằng cách chọn tệp đó từ ####### cài lại; ####### ## Ví dụ Một var ####### PaintB; # lượng màu xanh lam var ####### PaintG; # lượng vàng ####### bất đẳng thức xuất hiện. ####### Trước tiên, bạn phải chọn một bộ giải, là chương trình mà AMPL gọi để thực sự giải toán ####### bộ giải tùy chọn cplex;
####### chương trình. Chúng tôi sẽ sử dụng bộ giải có tên là cplex cho những ví dụ này, vì vậy hãy nhập: ####### Lưu ý những điều sau đây về ngôn ngữ AMPL:
####### Bây giờ, hãy nhập lệnh sau, lệnh này sẽ yêu cầu AMPL đọc trong tệp bạn đã tạo. ####### tối đa hóa lợi nhuận: 10PaintB + 15PaintG; tùy ####### thuộc vào thời gian: (1/40)*PaintB + (1/30)*PaintG <= 40; chịu blue_limit: ####### 0 <= PaintB <= 1000; chịu gold_limit: 0 <= PaintG <= 860; ####### ri Giải pháp tập tin mô hình trường hợp vấn đề Hình 1. CPLEX / MINOS AMPL Giải pháp Người giải quyết Tập tin dữ liệu ####### ## Ví dụ Hai - Mô hình ####### , mi), mô hình sẽ giữ nguyên bất kể giá trị của chúng. ####### So sánh mô hình này với mô hình trong phần trước. Dễ dàng thấy rằng đây là một phát biểu tổng quát hơn của phát biểu ####### trước. Lưu ý những điều sau: ####### Trước tiên, hãy xem tệp mô hình mà chúng tôi lưu trên ổ đĩa z: dưới dạng z:\myFiles\examp 2:
####### tối đa hóa lợi nhuận: tổng{i trong 1.} p[i]*paint[i]; tùy ####### thuộc vào thời gian: sum{i in 1.} (1/r[i])*paint[i] <= t; tùy theo dung ####### lượng{i trong 1.}: 0 <= paint[i] <= m[i]; ####### sơn var{i trong 1.}; ####### Đây chính xác là những gì AMPL làm. Nó cho chúng ta một cách để thể hiện biểu diễn đại số của mô hình và các giá trị ####### này cho các tham số một cách riêng biệt. Nó thực hiện điều này bằng cách sử dụng hai tệp riêng biệt, tệp mô hình và tệp dữ ####### liệu. AMPL đọc mô hình từ tệp .mod, dữ liệu từ tệp .dat và đặt chúng lại với nhau thành một định dạng mà bộ giải hiểu ####### được. Sau đó, nó bàn giao trường hợp vấn đề này cho bộ giải, do đó, giải quyết trường hợp này và trao lại giải pháp cho ####### AMPL. Điều này được minh họa trong Hình 1.
####### tham số mà chúng tôi đã khai báo đại số là pi , i = 1., chúng tôi có thể sử dụng i làm biến chỉ mục và 1. làm ####### phạm vi và do đó chúng tôi nhận được p{i trong 1. }. ####### thông số ####### n; thông ####### số t; tham số p{i trong ####### 1.}; tham số r{i trong ####### 1.}; tham số m{i trong 1.}; ####### một số cách xác định các tham số (n, t, pi , Do ####### đó, chúng ta thấy rằng Ví dụ Một thực sự là một ví dụ của Bài toán Berkeley Paint, chứ không phải là một mô hình.
####### Bây giờ, hãy nhập các lệnh sau, lệnh này yêu cầu AMPL đọc trong mô hình và tệp dữ liệu bạn vừa tạo, sau đó giải mô hình. ####### Lưu ý rằng bạn phải tải tệp mô hình trước tệp dữ liệu.
####### Như bạn có thể thấy, một cách để chỉ định dữ liệu tham số là sử dụng từ khóa param, dấu hai chấm và dấu bằng và giá trị. ####### Nếu một tham số có nhiều hơn một thành phần, chỉ cần liệt kê chỉ mục tham số (trong trường hợp này là 1 hoặc 2) theo sau là ####### giá trị. ####### Nếu mô hình và dữ liệu được nhập chính xác, bạn sẽ nhận được giá trị mục tiêu và đầu ra chính xác như nhau ####### được viết tổng {i trong 1.}. ####### tham số p:= 1 10 2 15; tham số ####### r:= 1 40 2 30; tham số m:= 1 ####### 1000 2 860; ####### mô hình z:\myFiles\examp_2; dữ liệu z: ####### \myFiles\examp_2; gỡ rối; ####### tham số p:= 1 10 2 ####### 15; ####### tham số r:= 1 40 2 ####### 30; ####### tham số m:= 1 1000 2 ####### 860; ####### N
####### Chúng ta có thể (và có lẽ nên) sử dụng tỷ lệ tên và maxDemand thay cho r và m. ####### phần, chúng tôi đã ####### viết: 0 ≤ painti ≤ mi cho mỗi i, i = ####### 1,... , cho một trong các ràng buộc. Trên thực tế, đây là một tập hợp n ràng buộc, một ràng buộc cho mỗi màu sơn. ####### Trong AMPL, chúng tôi thể hiện điều này trong biểu thức trong dấu ngoặc nhọn sau tên của ràng buộc. Do đó, ràng buộc ####### này trở ####### thành: chủ thể sơn {i in 1.}: 0 <= paint[i] <= m[i]; ####### Lưu ý rằng vì AMPL bỏ qua dấu xuống dòng trong tệp và thay vào đó tìm kiếm dấu chấm phẩy để kết thúc dòng, bạn cũ ng có ####### thể viết ba tham số cuối cùng dưới dạng: ####### như trước. Để xem các giá trị được gán cho paint[1] và paint[2], hãy nhập: ####### chúng tôi đã giải quyết trong phần trước, mà chúng tôi lưu trên ổ đĩa z: dưới dạng z:\myFiles\examp 2. ####### Tiếp theo, nếu chương trình AMPL không chạy, hãy chạy nó theo cách tương tự như trước. Nếu nó hiện đang, đang chạy, ####### cài lại; ####### Ngoài việc chỉ định mô hình, chúng ta cũ ng phải chỉ định dữ liệu. Đây là dữ liệu cho cùng một vấn đề ####### đầu tiên đặt lại AMPL bằng cách gõ:
####### tham số n:= 2; ####### tham số t:= 40; ####### Ngoài ra, nếu có lỗi trong mô hình hoặc tệp dữ liệu, đừng quên sử dụng đặt lại trước khi tải lại chúng. ####### ## Ví dụ Hai - Dữ liệu N tôi = 1 ####### tham số p:= xanh 10 vàng ####### 15; tham số ####### r:= xanh 40 vàng 30; ####### tham số m:= ####### xanh 1000 vàng 860; ####### Hãy xem xét ví dụ sau. Công ty sơn Berkeley đã mở rộng và hiện có ba nhà kho, tất cả đều được sơn màu xanh lam. ####### Trong một tuần cụ thể, sơn phải được chuyển đến bốn khách hàng. Đối với mỗi nhà kho và khách hàng, mỗi gallon chi phí ####### vận chuyển là khác nhau. Chi phí vận chuyển được hiển thị trong bảng sau. 3 4 2 ####### Khách hàng 4: 390 tham số: prm:= xanh 10 40 1000 ####### Khách hàng 1 khách hàng. 2 Cust. 3 Cust. 4 ####### ## Ví dụ Hai - Một cách khác để ghi dữ liệu với các tập hợp ####### Kho 1 250 ####### Nhu cầu của mỗi khách hàng là: ####### 15 30 860; ####### kho 3 2 5 2 ####### Khách hàng 2: 320 Lưu ý rằng sau khi tập hợp được xác định, mỗi phần tử tham số được nêu bằng cách sử dụng tên phần tử tập hợp,thay vì số chỉ mục. Như bạn có thể thấy, điều này dễ đọc và dễ làm theo hơn nhiều. Trên thực tế, chúng ta có thể kếthợp ký hiệu tập hợp với ký hiệu dữ liệu nhỏ gọn hơn được giới thiệu trong phần trước và chúng tôi nhận được: ####### Các nhà kho nằm trong cột đầu tiên, khách hàng ở hàng đầu tiên và chi phí vận chuyển nhà kho-khách hàng có thể được đọc ####### từ bảng. ####### Ngoài ra, lượng sơn xanh cung cấp tại mỗi nhà kho là: ####### đặt P:= vàng xanh; ####### Kho 2 800 ####### đặt P:= vàng xanh; tham ####### số t:= 40; ####### Kho 1 ####### vàng ####### ## Ví dụ Hai - Dữ liệu có tập hợp 1 3 2 ####### Kho 2 ####### Kho 3 760 ####### Khách hàng 1: 300 tham số t:= 40; ####### Khách hàng 3: 800 ####### Thông thường, một mô hình lập trình toán học có các biến và tham số có hai chiều. Chúng ta có thể ghi dữ liệu tham số ở ####### dạng bảng và AMPL cho phép chúng ta nhập thông tin này ở dạng bảng trong tệp dữ liệu. 1 1 2 5 Biến và Tham số Với Hai Thứ nguyênkho thông số; # số kho param khách hàng; # số lượngkhách hàng chi phí vận chuyển từ kho i #đến kháchhàng chi phí thông số j{i trong 1., j trong1.ách hàng};cung cấp thông số {i trong 1.};cung cấp tại kho iparam nhu cầu{i trong 1.ách hàng};nhầm lẫn chúng với các thông số cung, cầu và chi phí.2Đặc biệt chú ý đến cách nhập dữ liệu tham số chi phí. Lưu ý dấu hai chấm sau tên tham số, dấu hai chấm và dấubằng sau chỉ mục kho cuối cùng. Ngoài ra, hãy lưu ý rằng chỉ mục đầu tiên (kho) nằm trong cột đầu tiên, trong khichỉ mục thứ hai (khách hàng) nằm ở hàng đầu tiên, giống hệt như bảng mà chúng tôi đã chỉ định dữ liệu lần đầu tiên.tổng{i trong 1., j trong 1.ách hàng} chi phí[i,j]*số tiền[i,j]; tùy thuộcvào Nguồn cung {i trong 1.}: tổng{j trong1.ách hàng} lượng[i,j] = nguồn cung[i]; tùy thuộc vàoNhu cầu {j trong 1.ách hàng}: tổng {i trong1.} lượng[i,j] = nhu cầu[j]; tùy thuộc vào giá trịdương{i trong 1., j trong 1.ách hàng}: số tiền[i,j]>=0;z:\my iles\examp 3.số tiền var{i trong 1., j trong 1.ách hàng};12;Lưu ý những điều sau đây về mô hình này:1 1 3 3 1
số 8 2 giảm thiểu chi phí: ## Ví dụ Ba - Dữ liệu
2 2 5 kho tham số:= 3; thông sốkhách hàng:= 4; chi phítham số: 142## Ví dụ Ba - Mô hìnhcung tham số:= 1 250 2 800 3 760; tham số nhucầu:= 1 300 2 320 3 800 4 390;
####### Chúng tôi sử dụng ký hiệu tập hợp được giới thiệu trong Phần 4 để làm rõ mô hình và dữ liệu. Điều này đặc biệt hữu ích nhu cầu khách jchi phímở kho jtổng{i trong Kho, j trong Khách hàng} cost[i,j]*amount[i,j] + sum{itrong Kho} ixed_charge[i]*open[i]; tùy thuộc vào Nguồncung {i trong Kho hàng}: tổng{j trong Kháchhàng} lượng[i,j] <= nguồn cung[i]*mở[i]; tùy thuộc vào Nhu cầu {jtrong Khách hàng}: tổng{i trong Kho}lượng[i,j] = nhu cầu[j]; tùy thuộc vào tích cực{i trongKho hàng, j trong Khách hàng}:Để minh họa, hãy xem xét ví dụ sau. Công ty sơn Berkeley hiện đã mở rộng khả năng cung ứng tại mỗi kho hàngcủa mình. Tuy nhiên, sự mở rộng này đã phải trả giá. Ngoài chi phí vận chuyển, giờ đây công ty còn phải trả chiphí cố định cho việc mở kho hàng.Lưu ý rằng nguồn cung hiện có vượt quá tổng nhu cầu. Mô hình AMPL sau đây được thiết lập để giảm thiểu tổngchi phí tùy thuộc vào việc đáp ứng nhu cầu. Trên thực tế, vấn đề này được gọi là Vấn đề vị trí kho hàng. Chúngtôi lưu tệp trên ổ đĩa z: dưới dạng z:\myFiles\examp 4.giảm thiểu chi phí: Kho 2 1100## Ví dụ Bốn - Tệp mô hình IP hỗn hợp cho vấn đề về vị trí nhà khoKho 3 1060Kho 1 550 nếu khách hàng và kho hàng có tên hoặc tên địa điểm. lượng[i,j]>=0;Kho 1 500đặt Kho; đặt Kháchhàng; khả năng cung ứng tại kho iChi phí mở mỗi kho là:chi phí vận chuyển từ kho ichi phí tham sốj tới kháchhàng{i trong Kho hàng, j trong Khách hàng}; cung cấpthông số {i trong Kho}; param nhucầu{j trong Khách hàng}; thông số ixed_charge{i trong Kho hàng};May mắn thay, AMPL cho phép chúng tôi kết hợp điều này chỉ với một thay đổi nhỏ trong mô hình. Bằng cách thêmtừ khóa số nguyên vào khai báo var, chúng ta có thể hạn chế biến được khai báo thành các giá trị nguyên. Hơnnữa, bằng cách thêm từ khóa binary vào khai báo var, chúng ta có thể hạn chế biến được khai báo ở các giá trị0 và 1.Kho 3 500var số tiền{i trong Kho hàng, j trong Khách hàng}; varopen{i trong Kho} nhị phân; # = 1 nếu kho i được mở, 0 nếu khôngThông thường, một mô hình lập trình toán học yêu cầu một số (hoặc tất cả) biến chỉ nhận các giá trị tích phân.6 Lập trình số nguyên7 Lập trình phi tuyến####### Để minh họa, chúng ta hãy xem xét ví dụ về Tối ưu hóa danh mục đầu tư. Giả sử rằng chúng ta có một tập hợp các khoản ####### đầu tư thay thế A và chúng ta biết tỷ lệ hoàn vốn kỳ vọng R cho mỗi khoản đầu tư này trong một tập hợp năm T. Từ dữ liệu ####### này, chúng ta có thể tính toán ma trận hiệp phương sai cho các khoản đầu tư.
####### Mô hình AMPL sau đây được thiết lập để tối đa hóa lợi nhuận kỳ vọng với rủi ro tối đa
####### Albania ####### ngưỡng. Chúng tôi lưu tệp mô hình trên ổ đĩa z: dưới dạng z:\myFiles\examp 5. ####### Oakland ####### 800 ####### đặt Kho hàng:= Oakland San_Jose Albany; đặt Khách ####### hàng:= Home_Depot K_mart Wal_mart Ace; 2 5 ####### Để hoàn thành mô hình, chúng ta cần chỉ định dữ liệu tương ứng. Tệp dữ liệu được lưu trên ổ đĩa z: dưới dạng z: ####### \my iles\examp 4. ####### 1100 ####### 390; ####### Đầu tiên, bạn phải thay đổi bộ giải, vì cplex không giải được các bài toán lập trình phi tuyến tính. Đối với các vấn ####### đề phi tuyến tính, chúng ta sẽ sử dụng bộ giải minos. Vì vậy, gõ: ####### Home_Kho 300 ####### 500; ####### Chúng ta muốn ####### Home_Depot K_mart Wal_mart Ace:= ####### 2
####### 2 ####### Oakland
####### 550
####### Wal_mart Át chủ ####### San Jose ####### Nhiều chương trình toán học bao gồm các hàm phi tuyến tính trong các ràng buộc và cho mục tiêu. May mắn thay, AMPL cũ ng |