Thực đơn
trang chủAndroid

Giải bài toán quy hoạch tuyến tính bằng phương pháp đồ thị, phương pháp đơn hình và thông qua thao tác “tìm lời giải” trong Excel. kg nguyên liệu loại 1, a. Giải bài toán bằng Excel và phương pháp đơn giản

1. Chuyển bất đẳng thức thành đẳng thức

2. Tìm giải pháp cơ bản khả thi ban đầu

3. Dựa vào điều kiện tối ưu, biến đầu vào được xác định. Nếu không có biến đầu vào thì quá trình này hoàn tất.

4. Dựa vào điều kiện chấp nhận, chọn biến bị loại trừ

5. Tính các phần tử của hàng đầu mới

dòng dẫn đầu mới = dòng hiện tại/phần tử dẫn đầu

6. Tính phần tử của các hàng còn lại, kể cả chuỗi z

hàng mới = hàng hiện tại - hệ số của nó trong cột đầu tiên * hàng đầu mới

Hãy chuyển sang bước 3.

Để thuận tiện cho việc ghi lại quá trình lặp, chúng tôi viết tất cả các giá trị vào bảng Simplex.

2. Ví dụ giải bài toán lp bằng gói ms excel

Đối với nhiều bài toán tối ưu hóa, việc sử dụng mô hình quy hoạch tuyến tính là rất thuận tiện. Bản chất của bài toán là biên soạn một hệ bất đẳng thức mô tả các ràng buộc tương ứng của bài toán và xác định hàm tối ưu hóa.

Để tìm giải pháp trong các mô hình như vậy, bạn có thể sử dụng công cụ MS EXCEL - TÌM KIẾM GIẢI PHÁP.

Hãy xem cách tạo một mô hình quy hoạch tuyến tính và tìm giải pháp của nó bằng một ví dụ.

2.1. Xây dựng vấn đề

Hai loại bộ phận (A và B) được xử lý trên ba máy và mỗi bộ phận được xử lý trên tất cả các máy. Chúng ta biết được thời gian gia công các bộ phận trên mỗi máy, thời gian vận hành của các máy trong một chu kỳ sản xuất và lợi nhuận thu được từ việc bán một bộ phận của mỗi loại (dữ liệu trong bảng). Lập kế hoạch sản xuất mang lại lợi nhuận lớn nhất.

2.2. Xây dựng mô hình toán học

Chúng ta ký hiệu x 1 và x 2 là số lượng đơn vị bộ phận loại A và B dự kiến ​​sản xuất. Khi đó thời gian xử lý x 1 của chi tiết loại A trên máy thứ nhất là 1 * x 1; x 2 phần loại B tương ứng là 2*x2. Tổng thời gian vận hành của máy I để sản xuất số bộ phận theo kế hoạch là x 1 + 2 * x 2, giới hạn là 16 giờ vận hành của máy này trong một chu kỳ sản xuất. Do đó bất đẳng thức phải được thỏa mãn:

x 1 +2*x 2<=16;

Tương tự, đối với máy II và III ta lần lượt thu được các bất đẳng thức sau:

x 1 + x 2<=10;

3*x 1 + x 2<=24;

Ngoài ra, theo nghĩa định nghĩa của các giá trị x 1 và x 2 đã nhập phải đáp ứng các điều kiện sau: x 1 >=0; x 2 >=0;

Như vậy, ta thu được hệ bất đẳng thức gọi là hệ các ràng buộc bài toán:

Bất kỳ nghiệm (x 1; x 2) nào của hệ ràng buộc đều được gọi là phương án sản xuất hoặc phương án chấp nhận được cho bài toán.

Lợi nhuận bán x 1 đơn vị linh kiện loại A bằng 4. x 1, lợi nhuận bán x 2 đơn vị bộ phận loại B bằng 2x 2. Tổng lợi nhuận bán sản phẩm sản xuất theo kế hoạch (x 1; x 2) bằng:

F(X 1 ; X 2 )=4x 1 +2x 2 (nghìn rúp).

Hàm tuyến tính F(X 1 ; X 2 ) gọi điện hàm mục tiêu nhiệm vụ.

Tùy theo điều kiện của bài toán cần tìm phương án (x 1; x 2) sao cho lợi nhuận đạt được lớn nhất.

Như vậy, mô hình toán học của bài toán dưới dạng bài toán quy hoạch tuyến tính đã được xây dựng:

F(X 1 ; X 2 )=4x 1 +2x 2 → tối đa

Các mô hình tối ưu hóa được sử dụng để tìm câu trả lời cho các câu hỏi như:

  • Làm cách nào để tạo lịch làm việc cho nhân viên trung tâm cuộc gọi để đáp ứng yêu cầu nghỉ phép của họ, cân bằng thời gian làm thêm giờ và loại bỏ nghĩa vụ suốt ngày đêm?
  • Bạn nên tận dụng những cơ hội khoan dầu nào để tối đa hóa thu nhập của mình trong khi vẫn kiểm soát được mọi rủi ro?
  • Khi nào các đơn hàng mới nên được đặt ở Trung Quốc và chúng nên được giao như thế nào để giảm thiểu chi phí và đáp ứng nhu cầu dự kiến?

Tải xuống ghi chú ở định dạng hoặc, ví dụ ở định dạng

Mục tiêu của việc tối ưu hóa luôn là “tối đa hóa” hoặc “tối thiểu hóa”. Hình thức tối ưu hóa toán học phổ biến và được hiểu rõ nhất là quy hoạch tuyến tính, một sự phát triển bí mật của các kỹ sư Liên Xô vào cuối những năm 1930 và đã trở nên phổ biến trong Thế chiến thứ hai. Nhân tiện, từ "lập trình" trong cụm từ này là một di tích của thuật ngữ quân sự thời đó và không liên quan gì đến lập trình máy tính.

Hãy bắt đầu với ví dụ yêu thích của các nhà kinh tế học - súng và bơ. Năm đó là năm 1941, bạn là chủ một trang trại bò sữa của Pháp. Ban ngày bạn vắt sữa bò và sản xuất bơ, ban đêm bạn lắp ráp máy móc tự động. Mục tiêu của bạn là lợi nhuận tối đa để sản xuất máy móc càng lâu càng tốt. Từ người trung gian từ phe Kháng chiến, bạn nhận được 195 đơn vị tiền tệ cho mỗi máy (để không làm phiền Excel với những đồng franc không tồn tại, hãy giả sử rằng đây là đô la). Đối với mỗi thùng dầu trên thị trường, bạn được trả 150 USD.

Điều kiện và hạn chế. Giá một thùng dầu là 100 USD, giá một chiếc máy là 150 USD. Ngân sách sản xuất hàng tháng - $1800. Bạn lưu trữ sản phẩm của mình trong tầng hầm rộng 21 mét khối. Máy chiếm ½ m 3, thùng dầu 1½ m 3. Bạn cần bán bao nhiêu máy bán hàng tự động và thùng dầu trong một tháng để kiếm được lợi nhuận tối đa?

Một chương trình tuyến tính được định nghĩa là một tập hợp các giải pháp cần thiết để tối ưu hóa một đối tượng trong một số điều kiện, trong đó cả đối tượng và các điều kiện đều tuyến tính. Bạn có thể cộng, trừ, nhân với các hằng số, nhưng bạn không thể sử dụng các hàm phi tuyến để giải, chẳng hạn như nhân các biến (bạn không thể nhân với bơ), bình phương hoặc các vòng lặp logic như IF.

Hãy tưởng tượng các khu vực giá trị chấp nhận được về mặt đồ họa. Đầu tiên, số súng và thùng dầu phải không âm. Thứ hai, số tiền tối đa bạn có thể sản xuất là $1800/$150 = 12 máy hoặc $1800/$100 = 18 thùng dầu (Hình 1). Tên chung của tam giác này là đa hình– một hình có các cạnh phẳng (ví dụ: hình thoi). Thứ ba, tầng hầm có thể chứa không quá 21/(½) = 42 máy hoặc 21/(1½) = 14 thùng dầu (Hình 2).

Để tìm ra tỉ lệ lý tưởng giữa máy và thùng, chúng tôi đưa khái niệm vào bài toán đường mức chức năng. Dòng như vậy trong mô hình tối ưu hóa bao gồm các giá trị mang lại lợi nhuận như nhau. Đường mức có thể được xác định bằng phương trình:

(195 – 150) * N máy + (150 – 100) * N thùng dầu = C,

trong đó C là hằng số.

Ví dụ: với C = 450, đường thẳng sẽ đi qua tọa độ (0;10) và (9;0). Về mặt đồ họa, ý tưởng tối đa hóa lợi nhuận được thực hiện bằng cách di chuyển đường mức song song với chính nó theo hướng tăng giá trị dọc theo trục X và Y (Hình 3). Điều đáng tò mò là đối với một đa giác, điểm tối ưu luôn nằm ở một trong các đỉnh (hoặc không có nghiệm duy nhất nào cả). Thuật toán phương pháp đơn giản dựa trên thuộc tính này. Giải quyết vấn đề trong Excel bắt đầu bằng việc tạo vùng mô hình (Hình 4). Công thức cho hàm mục tiêu trong ô B1 =SUMPRODVEL(C4:D4;C10:D10).

Cơm. 3. Đường cấp độ và chức năng tối ưu hóa lợi nhuận: a) một số vị trí ban đầu tùy ý; b) đường mức ở vị trí tối ưu

Bạn đã sẵn sàng nhấn nút. DỮ LIỆU –> Tìm giải pháp. (Nếu bạn không thấy nút này, hãy cài đặt tiện ích bổ sung Tìm Giải pháp; xem Chương 1). Trong cửa sổ mở ra Tùy chọn tìm kiếm giải phápđặt các tùy chọn được đánh dấu và nhấn Tìm một giải pháp.

Cơm. 5. Cửa sổ Tìm giải pháp

Excel sẽ cập nhật trang tính và thêm kết quả tính toán vào đó (Hình 6).

Điều gì xảy ra nếu bạn thêm tính phi tuyến? Giả sử người trung gian của bạn đề nghị 500 USD nếu số lượng máy mỗi tháng nhiều hơn 5. Chỉ cần thêm hàm IF vào ô lợi nhuận (B1). Bây giờ hàm mục tiêu có dạng như sau: =SUMPROD(C4:D4,C10:D10)+IF(C4>5.500,0). Nhấp chuột Tìm giải pháp. Thất bại, Excel báo lỗi - không đáp ứng điều kiện tuyến tính (Hình 7).

Bạn có thể thử thuật toán tiến hóa, thuật toán này hoạt động tốt nhất với các mô hình phi tuyến và hầu như không có hạn chế nào trong việc lựa chọn hàm. Công việc của thuật toán tiến hóa ở một khía cạnh nào đó lặp lại các nguyên tắc của công việc tiến hóa sinh học:

  • tạo ra một nhóm các giải pháp ban đầu (giống như nhóm di truyền) có mức độ xác suất khác nhau;
  • mọi quyết định đều có mức độ phù hợp nhất định để tồn tại;
  • các giải pháp được nhân lên bằng cách chuyển giao chéo, nghĩa là các thành phần của chúng được chọn từ hai hoặc ba giải pháp hiện có và sau đó kết hợp;
  • các giải pháp hiện có biến đổi thành những giải pháp mới;
  • xảy ra tìm kiếm địa phương, trong đó các giải pháp mới được tạo ra gần với giải pháp tốt nhất khoảnh khắc này các quyết định trong dân số;
  • quá trình lựa chọn xảy ra: các giải pháp ứng cử viên không thành công được chọn ngẫu nhiên sẽ bị loại khỏi nhóm di truyền.

Thật không may, vẫn còn một số vấn đề với thuật toán tiến hóa:

  • Thời gian vận hành dài hơn đáng kể so với phương pháp đơn giản
  • Không có gì đảm bảo rằng anh ta sẽ tìm thấy giải pháp tối ưu. Tất cả những gì anh có thể làm là kiểm soát giải pháp tốt nhất trong quần thể cho đến khi hết thời gian hoặc quần thể thay đổi ở một mức độ vừa đủđể tiếp tục hoặc bạn không buộc dừng “Tìm kiếm giải pháp” bằng cách nhấn nút ESC.
  • Quá trình tìm kiếm giải pháp tiến hóa diễn ra khá chậm. Và nếu phạm vi các giá trị có thể chấp nhận được rất phức tạp, anh ta thường chửi thề, thậm chí không tìm được nơi để bắt đầu.
  • Nếu bạn muốn làm cho thuật toán tiến hóa hoạt động tốt trong Excel, bạn sẽ phải xác định giới hạn cố định cho mỗi thuật toán. biến quyết định. Ngay cả khi giải pháp của bạn ít nhiều không bị hạn chế, bạn vẫn cần có những hạn chế.

Tính đến điểm cuối cùng, để giải quyết vấn đề với máy móc và bơ, bạn cần thêm một ràng buộc là cả hai nghiệm không được lớn hơn 25 (Hình 8). Sau khi thiết lập các thông số cơ bản của mô hình, nhấp vào nút Tùy chọn. Sau khi làm việc khoảng một phút, thuật toán tiến hóa đã tạo ra giải pháp mong đợi - 6 chiếc máy và 9 thùng dầu. Vì tốt nhất là chỉ tạo ra ba máy mà không có tiền thưởng và tiền thưởng được trả khi có hơn 5 máy được sản xuất, rõ ràng lựa chọn tối ưu sẽ là 6 máy.

Bây giờ chúng ta hãy xem xét thêm ví dụ phức tạp. Bạn làm việc cho một công ty sản xuất nước cam bằng cách pha trộn các loại nước ép tự nhiên thuộc nhiều loại khác nhau (Hình 9). Để đảm bảo nước ép của bạn đáp ứng được những yêu cầu phức tạp nhất:

  • tỷ lệ Brix/độ axit phải duy trì trong khoảng 11,5–12,5;
  • mức độ axit phải duy trì trong khoảng 0,75–1%;
  • mức độ se khít phải từ 4 trở xuống;
  • màu sắc phải nằm trong khoảng 4,5–5,5.

Người đứng đầu nói với bạn rằng ông ấy kỳ vọng nhu cầu sẽ là 600.000 gallon nước trái cây mỗi tháng trong tháng Một và tháng Hai, và 700.000 gallon nước trái cây mỗi tháng trong tháng Ba. Chưa hết, có một thỏa thuận với bang Florida cung cấp các khoản giảm thuế với điều kiện công ty mua ít nhất 40% lượng nước ép mỗi tháng từ những người nông dân trồng giống này. Valencia. Thỏa thuận phải được tôn trọng.

Cơm. 9. Danh sách các đặc điểm để sản xuất nước cam ép tươi (để phóng to hình ảnh, nhấp vào hình ảnh click chuột phải chuột và chọn Mở hình ảnh trong trang mới)

Tạo nên mô hình tối ưu hóa(Hình 10). Các công thức có thể được nghiên cứu trên bảng tương ứng của tệp Excel đính kèm. Nhấp chuột Tìm giải pháp, và nhập các thông số (Hình 11). Nhấp chuột Tìm một giải pháp.

Cơm. 11. Cửa sổ đầy Tìm giải pháp cho nhiệm vụ trộn

Ra mắt Tìm giải pháp, bạn thấy chi phí tối ưu mua hàng - 1,23 triệu USD (Hình 12). Xin lưu ý rằng các đơn đặt hàng của Florida Valencia được xử lý thông qua Giơi hạn dươiđiều kiện. Rõ ràng thương vụ này không sự lựa chọn tốt nhất, nhưng bạn phải chấp nhận nó. Loại phổ biến thứ hai là Verna từ Mexico, loại này cực kỳ rẻ nhưng cũng tệ không kém.

Bạn trình bày kết quả tính toán với sếp của mình, nhưng ông ấy vẫn không hài lòng và nói rằng ông ấy không muốn vượt quá ngân sách 1,17 triệu USD. Bạn quay lại máy tính và bắt đầu hiểu rằng chi phí đã không còn là một hàm khách quan nữa. Bây giờ đây là một điều kiện! Mục tiêu là gì? Bạn chỉ có thể giảm chi phí mua hàng bằng cách nới lỏng các yêu cầu về chất lượng. Bạn quyết định xây dựng chúng dưới dạng giảm tỷ lệ phần trăm và thực hiện người mẫu mới(Hình 13).

Xin lưu ý rằng các ô B26:29 và F26:F29 hiện chứa công thức thay vì hằng số. Mục tiêu mới của bạn là giảm thiểu sự suy giảm phần trăm trong các ô G26:G29. Chính xác hơn, bạn muốn giảm thiểu giá trị tối đa trong các ô G26:G29. Tuy nhiên, nếu bạn đặt công thức =MAX(G26:G29) vào ô D2 thì mô hình sẽ không hoạt động. Hãy để tôi nhắc bạn rằng hàm MAX không tuyến tính. Có một mẹo nhỏ ở đây - bạn có thể nhập Điều kiện bổ sungđể lập mô hình: $G$26:$G$29<=$D$2 (рис. 14), а ячейку D2 оставить пустой. Т.е., ячейка D2 будет оптимизироваться не благодаря наличию в ней формулы, а последовательными циклами, запускаемыми этим дополнительным условием.

Nhấp chuột Tìm một giải pháp. Thuật toán đơn giản sẽ cố gắng đẩy D2 đến gần 0 hơn làm hàm mục tiêu của mô hình, trong khi các ràng buộc về hương vị và màu sắc sẽ cố gắng tăng nó lên nhiều nhất có thể để có được hỗn hợp khả thi. Giá trị của D2 dừng ở đâu? Giá trị nhỏ nhất có thể là tỷ lệ phần trăm tối đa của 4 được giảm trong phạm vi G26:G29. Chúng tôi thấy (Hình 15, các ô C26:E29) yêu cầu giảm 5% chi phí vượt quá giới hạn chất lượng ở cả bốn thông số.

Bạn trình bày dữ liệu với ông chủ, người thấy rằng việc cắt giảm 5% chi phí không đáng để giảm chất lượng nước trái cây nên ông ấy đã đồng ý với lựa chọn đầu tiên của bạn. Nhưng khi bạn mang đến bộ phận cung ứng thì nhân viên lại tỏ ra phẫn nộ. Làm sao nguồn cung cấp có thể được chia nhỏ như vậy!? Các nhà cung cấp nhất quyết yêu cầu bạn mở rộng lô hàng của mình: không quá 4 nhà cung cấp mỗi tháng! Và bạn ngồi xuống với mô hình mới. Thật không may, bạn không thể sử dụng hàm IF hoặc COUNT vì bạn muốn vẫn ở trong mô hình tuyến tính. Vì vậy, bạn lại phải dùng đến thủ đoạn (Hình 16). Bạn thêm vùng C33:E43 vào mô hình mà bạn xác định là nhị phân (các giá trị trong đó chỉ có thể là 0 hoặc 1) và để trống. Và cả vùng F33:H43, trong đó mỗi ô bằng tích của giá trị từ vùng C33:E43 với G5:G15. Để tham số Tìm giải pháp(Hình 17) bạn thêm một điều kiện khác $C$15:$E$15<= $F$33:$H$43 и еще одну область переменных – $C$33:$E$43.

Thuật toán tối ưu hóa sẽ hoạt động như thế nào trong trường hợp này? Khi nó bắt đầu, tất cả các giá trị trong các vùng C5:E15, C33:E43 và F33:H43 đều bằng 0. Giả sử thuật toán cố gắng đặt giá trị 240 vào ô C7. Điều kiện C7 sẽ hoạt động<= F35, которое приведет к увеличению значения в F35, которое, в свою очередь, определяется формулой F35 = C35*$G7. Поскольку G7 – константа, а С35 – бинарная переменная, последней присваивается значение 1. Условие С7 <= F35 выполнено, т.к., 240 <= 1200. Таким образом вы моделируете неудобное условие «если… то»: «если заказ сделан, то бинарная переменная включается».

Nhấp chuột Tìm một giải pháp. Bạn sẽ nhận thấy rằng bài toán mất nhiều thời gian hơn để giải do có thêm các biến nhị phân. Nếu vì lý do nào đó Tìm giải pháp quá trình tìm kiếm của bạn mất quá nhiều thời gian, bạn luôn có thể nhấn ESC và xem giải pháp tốt nhất được tìm thấy vào lúc này.

Về cơ bản, bạn đã là một chuyên gia khá cao cấp trong lĩnh vực lập trình tuyến tính. Tuy nhiên, nếu bạn thích nó và muốn xử lý các mô hình có độ phức tạp ngày càng tăng thì đây là hai ví dụ đáng chú ý khác.

Các kỹ sư báo cáo rằng “chất giảm độ axit” mới đã xuất hiện trong sản xuất. Công nghệ này có khả năng trung hòa 20% lượng axit có trong nước ép chảy qua thiết bị. Điều này không chỉ làm giảm tỷ lệ axit mà còn làm tăng chỉ số Brix/độ axit lên 25%. Nhưng "bộ giảm tốc" đòi hỏi năng lượng và vật tư có giá 20 USD cho mỗi 1.000 gallon nước ép. Tuy nhiên, không phải tất cả nước trái cây đến từ các nhà cung cấp đều phải trải qua quy trình này, tuy nhiên, nếu lô hàng từ đơn đặt hàng được vận chuyển qua bộ trao đổi ion thì toàn bộ khối lượng phải được xử lý. Xây dựng mô hình sử dụng thiết bị trao đổi ion để giảm chi phí.

Vấn đề với quy tắc mới là cách tự nhiên để mô hình hóa nó là phi tuyến tính, điều này sẽ dẫn đến thuật toán tối ưu hóa chậm. Tuy nhiên, như trong ví dụ trước, bạn có thể nhập biến nhị phân vào vùng C25:E35, biến này sẽ được “bật” nếu cần giảm độ axit của mẻ (Hình 18). Vì bạn không thể sử dụng sản phẩm “chỉ báo giảm độ axit (nhị phân) * thể tích lô”, nên bạn tạo vùng C37:E47, vùng này sẽ hữu ích cho việc cân bằng thể tích cần giảm độ axit mà không cần tham gia trực tiếp vào công thức của các thể tích này . Vì vậy, vùng C25:E35 và C37:E47 không chứa công thức. Trong vùng G25:I35, các công thức được sử dụng =C25:E35*G5:G15 (đây là giới hạn của lô theo tổng thể tích nước ép sẵn có) và trong vùng K25:M35 =E5:E15-GG5:15 *(1-E25:E35). Điều kiện này sẽ chỉ có hiệu quả nếu mẻ trộn được giảm độ axit.

Ngoài ra, trong mô hình “giảm độ axit”, các công thức trong các ô C16:E16 đã được thay đổi (bây giờ chúng tính đến chi phí giảm độ axit bằng cách sử dụng công thức “chỉ báo (nhị phân) * khối lượng lô * $20) và trong các ô C50:E51 (hiện nay họ tính đến việc tăng hệ số Brix/độ axit thêm 25% và giảm độ axit thêm 20% cho các lô đã qua xử lý). Trong thông số Tìm giải pháp các biến mới và điều kiện bổ sung xuất hiện (Hình 19). Thật không may, nhấn nút Tìm một giải pháp, bạn sẽ phát hiện ra rằng tiện ích bổ sung Tìm giải pháp không thể hoàn thành nhiệm vụ (Hình 20). Mô hình đã trở nên quá phức tạp.

Cơm. 19. Tùy chọn Tìm giải pháp trong mô hình có “chất giảm độ axit”

Cơm. 20. Tìm giải pháp không đương đầu với nhiệm vụ

Bạn cần tải xuống và cài đặt bộ giải mở(làm thế nào để làm điều này, xem Chương 1). bộ giải mở sẽ “nhặt” các cài đặt vừa nhập trong cửa sổ Tìm giải pháp. Vì vậy chỉ cần nhấn nút Bộ giải. Giải pháp thu được – 1.235.927 USD – tốt hơn 100.000 USD so với mức thấp trước đó – 1.338.913 USD.

Cho đến nay, chúng tôi giả định rằng các sản phẩm được cung cấp có chính xác các thông số được chỉ định. Thật hợp lý khi giả định rằng các tham số này có thể thay đổi, được đặc trưng bởi độ lệch chuẩn (Hình 21; xem để biết thêm chi tiết). Phân phối nổi tiếng và được sử dụng rộng rãi nhất của một biến ngẫu nhiên là phân phối chuẩn, hay còn gọi là đường cong hình chuông. Ví dụ, trong trường hợp nước trái cây từ Ai Cập, tỷ lệ Brix/độ axit trung bình sẽ là 13 và độ lệch chuẩn (còn gọi là độ lệch chuẩn) sẽ là 0,9 (Hình 21). Trong ví dụ này, 13 là trung tâm của phân bố xác suất, 68% đơn hàng sẽ nằm trong khoảng ±0,9 của 13 và 95% sẽ nằm trong khoảng ±1,8 của 13.

Mục tiêu của bạn là đề xuất một kế hoạch pha trộn có chi phí dưới 1,25 triệu USD đáp ứng tốt nhất những mong đợi về chất lượng trong bối cảnh nguồn cung có thể thay đổi.

Chúng tôi sử dụng giá trị trung bình và độ lệch chuẩn của các đặc tính để áp dụng mô phỏng Monte Carlo (nếu bạn nghe đến cái tên này lần đầu tiên thì tôi khuyên bạn nên dùng nó). Trong phương pháp này, thay vì đưa trực tiếp các tham số phân phối (giá trị trung bình và độ lệch chuẩn) vào mô hình, một số lượng lớn các kịch bản được tạo ra dựa trên cùng các tham số phân phối này.

Một kịch bản có thể là một câu trả lời cho câu hỏi: “Nếu đây là những phân phối dựa trên số liệu thống kê, thì một thứ tự cụ thể sẽ trông như thế nào?” Mỗi kịch bản bao gồm bốn mươi tham số cho mười loại nước ép (Hình 22). Để có được một tham số như vậy, hãy sử dụng hàm NORM.REV (để biết thêm thông tin về hàm, hãy xem). Ví dụ: trong ô B33, tỷ lệ Brix/độ axit cho Hamlin được tính bằng =NORM.REV(RAND();H5;N5). Nhập các công thức tương tự vào vùng B33:СW76, tạo ra 100 kịch bản. Tìm giải pháp sẽ không thể hoạt động với các công thức này vì chúng không tuyến tính, vì vậy hãy sao chép chúng vào khay nhớ tạm và dán chúng dưới dạng giá trị.

Mục tiêu là giảm thiểu giá trị trong ô D2. Tức là tìm giải pháp giảm giới hạn chất lượng cho 100 kịch bản ít nhất. Như trong các ví dụ trong Hình. 13–15, ô D2 không có công thức. Tối ưu hóa được thực hiện bằng cách thiết lập các thông số trong cửa sổ Tìm một giải pháp. Tất cả những gì cần thiết là đặt ra các ranh giới chất lượng trong mọi tình huống, không chỉ các giá trị hiệu suất mong đợi. Vì vậy, trong tỷ lệ Brix/độ axit, bạn thêm các thuật ngữ B78:CW80 >= B26 và =< F26, затем проделываете то же самое с кислотностью, вяжущей составляющей вкуса и цветом (рис. 24). Нажмите Tìm một giải pháp. Giải pháp sẽ được tìm thấy khá nhanh chóng. Nếu bạn tự tạo các giá trị ngẫu nhiên thay vì sử dụng các giá trị trong tệp tải xuống, giải pháp của bạn có thể khác. Trong hàng trăm kịch bản của tôi, điều tốt nhất tôi có thể nhận được là chất lượng thay đổi 133%.

Cơm. 24. Thiết lập Tìm giải pháp cho một mô hình có đặc điểm thay đổi

Nếu bạn muốn mở rộng kiến ​​thức về lập trình tuyến tính, tôi khuyên bạn nên sử dụng cuốn sách Mô hình tối ưu hóa AIMMS. Đừng bỏ lỡ hai chương về thủ thuật và mẹo - chúng thực sự rất xuất sắc.

Được viết dựa trên cuốn sách của John Forman. – M.: Nhà xuất bản Alpina, 2016. – P. 129–186. Về vấn đề bí mật phát triển và Thế chiến thứ hai, đây dường như là quan điểm cá nhân của tác giả cuốn sách. Xem Wikipedia. – Ghi chú Baguzina.

Vấn đề 1 (phân phối)

Tại doanh nghiệp, 4 loại sản phẩm có thể được sản xuất trên 3 máy riêng biệt có thể hoán đổi cho nhau.

Được biết:

· Nhiệm vụ sản xuất các loại sản phẩm trong kỳ kế hoạch

  • · Kinh phí cho thời gian hoạt động hiệu quả của thiết bị trong kỳ kế hoạch - ;
  • · Tiêu chuẩn về chi phí thời gian máy để sản xuất ra một đơn vị sản phẩm - ;
  • · Lợi nhuận tính bằng rúp. từ việc bán một đơn vị sản phẩm được sản xuất trên thiết bị này hoặc thiết bị kia - .

Thông tin ban đầu được hiển thị trong bảng có dạng sau.

Bảng 1. Dữ liệu ban đầu

Quỹ hiệu quả nô lệ. thời gian -

Tiêu chuẩn tiêu thụ thời gian trên mỗi đơn vị sản phẩm - lợi nhuận trên mỗi đơn vị. các sản phẩm -

Bài toán đòi hỏi phải tìm phương án phân bổ nhiệm vụ sản xuất đầu ra sản phẩm giữa những người thực hiện

trong đó nhiệm vụ sẽ được hoàn thành với tổng lợi nhuận tối đa từ việc bán sản phẩm.

GIẢI PHÁP

Phát triển mô hình kinh tế và toán học.

Các biến yêu cầu đặc trưng cho khối lượng sản xuất của nhà thầu.

Khi đó ma trận các biến cần tìm

mô tả kế hoạch phân bổ nhiệm vụ sản xuất đầu ra sản phẩm giữa những người thực hiện.

Hàm mục tiêu

đặc trưng của tổng lợi nhuận từ việc bán tất cả các sản phẩm phải được tối đa hóa.

Những hạn chế về sự sẵn có và sử dụng thời gian làm việc hiệu quả của người biểu diễn sẽ có dạng hệ thống bất bình đẳng tuyến tính (2):


Hệ thống hạn chế này đặc trưng cho điều kiện là tổng chi tiêu thời gian làm việc hiệu quả của mỗi người thực hiện trong giai đoạn lập kế hoạch để sản xuất tất cả các loại sản phẩm không được vượt quá quỹ thời gian. Như vậy, khi giải quyết được vấn đề, mỗi người thực hiện sẽ nhận được nhiệm vụ riêng, tùy theo khả năng của mình. Nếu một số biến cân bằng nào đó có giá trị trong việc giải quyết một vấn đề, thì nó sẽ đặc trưng cho thời gian làm việc hiệu quả chưa được sử dụng đúng mức của một hoặc một người thực hiện khác, thời gian này trong điều kiện sản xuất có thể được sử dụng để tạo ra các sản phẩm vượt quá nhiệm vụ.

Khối hạn chế sau đây phải phản ánh điều kiện bắt buộc phải thực hiện mục tiêu sản xuất chung để sản xuất sản phẩm theo chủng loại và sẽ được biểu thị bằng hệ phương trình tuyến tính (3):


Điều kiện cho biến không âm:


Hãy đưa bài toán về dạng chính tắc, để làm được điều này, chúng ta thêm các biến vào bất đẳng thức (2) và thêm 4 cơ số nhân tạo vào các đẳng thức (3). Kết quả là chúng ta viết mô hình toán học của bài toán ở dạng chính tắc:

Phương pháp đơn giản

Hãy giải bài toán này bằng phương pháp đơn hình bằng cách điền vào bảng. Giải pháp này cần nhiều lần lặp lại. Hãy thể hiện nó.


Bảng 1

Các hệ số của hàm mục tiêu được nhập vào dòng trên cùng của bảng, dòng thứ hai là tên của tất cả các ẩn số có trong phương trình đơn. Cột đầu tiên bên trái chứa các hệ số của hàm mục tiêu, tương ứng với các ẩn số cơ bản có trong chương trình gốc (được viết trong cột). Cột tiếp theo, thứ ba, trong bảng đơn giản đầu tiên chứa đầy các giá trị của các ẩn số cơ bản. Tiếp theo là các cột biểu diễn các vectơ điều kiện. Số của chúng là 19. Trong cột tiếp theo, cột đầu tiên sau ma trận các điều kiện, tổng của tất cả các phần tử trong các hàng được viết. Cột ghi thương số từ việc chia các phần tử của cột B cuối cùng thành các phần tử của một cột nhất định, một ma trận các điều kiện. Vì chúng ta có cơ sở nhân tạo, nên sẽ có hai phép tính trong dòng chỉ số, phép tính đầu tiên có tính đến các biến và phép tính thứ hai chỉ là cơ sở nhân tạo. Vì chúng ta có bài toán cực đại hóa nên cần phải rút ra các cơ sở nhân tạo từ cơ sở. Trong dòng chỉ số thứ hai, chúng tôi chọn điểm tích cực lớn nhất. Đây là cột đầu tiên của chúng tôi. Hãy tìm mối quan hệ giá trị

Và. Từ các tỷ lệ này, chúng tôi chọn tỷ lệ nhỏ nhất, đối với chúng tôi đây là hàng thứ tư, trong đó tỷ lệ ước tính bằng 1300. Chọn hàng. Cột cuối cùng là hệ số mà mỗi phần tử của hàng được nhân trong quá trình tính toán lại. Nó có được bằng cách chia các phần tử của cột đã chọn cho phần tử chính, nằm ở giao điểm của cột đã chọn và hàng, đối với chúng tôi là 1. Chúng tôi thực hiện tính toán lại cho tất cả các phần tử không được chọn, được thực hiện như sau như sau: từ phần tử được tính toán lại, chúng tôi trừ phần tử hàng khóa, nhân với hệ số hàng được tính toán lại: v.v. cho tất cả các phần tử. Từ cơ sở, chúng ta rút ra một cơ sở nhân tạo, đồng thời đưa một biến vào cơ sở.

Hai dòng cuối cùng là các dòng chỉ mục trong đó các giá trị của hàm mục tiêu được tính toán lại, cũng như toàn bộ dòng chỉ mục, khi tất cả các phần tử đều dương hoặc bằng 0 - vấn đề sẽ được giải quyết.

Hãy thể hiện nó.

ban 2


Hãy chọn cột có biến. Chúng tôi tìm thấy các tỷ lệ ước tính, từ đó chúng tôi chọn tỷ lệ nhỏ nhất - đây là 550. Chúng tôi lấy một biến nhân tạo từ cơ sở, đồng thời đưa một biến vào cơ sở. Khi một cơ sở nhân tạo được lấy từ cơ sở đó thì cột tương ứng sẽ bị loại bỏ.

bàn số 3


Hãy chọn cột. Tỷ lệ ước tính nhỏ nhất, 600, được tìm thấy ở hàng thứ sáu. Từ cơ sở, chúng ta rút ra một cơ sở nhân tạo, đồng thời đưa một biến vào cơ sở.

Bảng 4


Hãy chọn cột có biến. Tỷ lệ ước tính thấp nhất, 28,57, nằm ở hàng đầu tiên. Chúng ta rút ra một biến từ cơ sở và đưa một biến vào cơ sở.

Bảng 5


Hãy chọn cột có biến. Tỷ lệ ước tính thấp nhất, 407,7, nằm ở hàng thứ ba. Chúng ta rút ra một biến từ cơ sở và đưa một biến vào cơ sở.

Bảng 6


Hãy chọn cột có biến. Tỷ lệ ước tính thấp nhất, 344,3, được tìm thấy ở hàng thứ bảy. Từ cơ sở, chúng ta rút ra một cơ sở nhân tạo, đồng thời đưa một biến vào cơ sở.

Bảng 7


Hãy chọn cột có biến. Tỷ lệ ước tính nhỏ nhất, 3,273, được tìm thấy ở hàng thứ hai. Chúng ta rút ra một biến từ cơ sở và đưa một biến vào cơ sở.

Bảng 8


Hãy chọn cột có biến. Tỷ lệ ước tính nhỏ nhất, 465, được tìm thấy ở hàng thứ bảy. Chúng ta rút ra một biến từ cơ sở và đưa một biến vào cơ sở.

Bảng 9


Hãy chọn cột có biến. Tỷ lệ ước tính nhỏ nhất, 109, nằm ở hàng thứ ba. Chúng ta rút ra một biến từ cơ sở và đưa một biến vào cơ sở.

Bảng 10


Hãy chọn cột có biến. Tỷ lệ ước tính nhỏ nhất, 10, nằm ở hàng đầu tiên. Chúng ta rút ra một biến từ cơ sở và đưa một biến vào cơ sở.

Bảng 11


Hãy chọn cột có biến. Tỷ lệ ước tính nhỏ nhất, 147, nằm ở hàng thứ hai. Chúng ta rút ra một biến từ cơ sở và đưa một biến vào cơ sở.

Bảng 12


Hãy chọn cột có biến. Tỷ lệ ước tính nhỏ nhất, 367, nằm ở hàng thứ năm. Chúng ta rút ra một biến từ cơ sở và đưa một biến vào cơ sở.

Bảng 13


Hãy chọn cột có biến. Tỷ lệ ước tính nhỏ nhất, 128, nằm ở hàng thứ tư. Chúng ta rút ra một biến từ cơ sở và đưa một biến vào cơ sở.

Bảng 14


Vì không có ước tính âm trong đường chỉ số nên sẽ thu được một kế hoạch tối ưu trong đó khối lượng đầu ra được biểu thị bằng ma trận

đồng thời, lợi nhuận là tối đa và lên tới 17.275,31 rúp.

Giải quyết vấn đề bằng Excel

Mô hình toán học của bài toán phải được chuyển sang ET EXCEL. Đối với điều này:

  • · Xem xét việc tổ chức dữ liệu ban đầu của mô hình (các hệ số của hàm mục tiêu và các ràng buộc), đặt tên rõ ràng cho chúng.
  • · Dự trữ các biến độc lập của mô hình toán học trong các ô riêng biệt.
  • · Tại một trong các ô, tạo công thức xác định hàm mục tiêu.
  • · Chọn các ô và đặt các công thức tương ứng với vế trái của các ràng buộc vào đó.
  • · Nhập mục menu "Tìm kiếm giải pháp", nhập dữ liệu cần thiết và nhận được giải pháp tối ưu cho vấn đề.
  • · Phân tích giải pháp và báo cáo kết quả.

Hãy xem xét trình tự các hành động để thực hiện các giai đoạn giải quyết vấn đề này bằng EXCEL.

Hãy tạo một bảng để nhập dữ liệu ban đầu.

Chúng ta sẽ nhập dữ liệu ban đầu vào biểu mẫu đã tạo.


Các hệ số của hàm mục tiêu biểu thị lợi nhuận từ việc sản xuất một đơn vị sản phẩm mỗi loại (lợi nhuận đơn vị) được ghi tại các ô B6:M6.

Các hệ số ràng buộc về nguồn lực xác định nhu cầu của từng loại nguồn lực để tạo ra một đơn vị đầu ra được đặt trong các ô B9:M15. Các ô P9:P15 chứa phía bên phải của các hạn chế về tài nguyên. Các ô B3:M3 được dành riêng cho các biến độc lập của bài toán - khối lượng sản xuất cần thiết.

Trong ô N7, nhập công thức cho hàm mục tiêu bằng lệnh chèn hàm SUMPRODVEL:


Chúng tôi cũng điền vào các hạn chế ở phía bên phải.

Sau này, bạn có thể bắt đầu tìm kiếm giải pháp. Để giải quyết các vấn đề tối ưu hóa trong EXCEL, hãy sử dụng lệnh TÌM KIẾM GIẢI PHÁP trong menu DỊCH VỤ.

Lệnh này hoạt động với ba thành phần chính của mô hình tối ưu hóa được tích hợp trong ET:

  • · Một ô chứa hàm mục tiêu của bài toán.
  • · Các ô có thể chỉnh sửa chứa các biến độc lập.
  • · Các ô chứa vế trái của các hạn chế về nguồn lực sẵn có, cũng như các hạn chế đơn giản đối với các biến độc lập.

Hãy xem xét trình tự nhập các thành phần này.

Con trỏ ở ô N7 và lệnh DỊCH VỤ - Tìm kiếm giải pháp. Một hộp thoại sẽ xuất hiện trên màn hình.


Trong cửa sổ, điền vào trường Đặt ô đích, trường này sẽ chứa địa chỉ $N$7. Tiếp theo, đặt nút để tìm kiếm giá trị lớn nhất. Trong trường Thay đổi ô, nhập địa chỉ của các biến mong muốn $B3:$M3. Sau đó, bạn nên nhập các hạn chế bằng nút Thêm.

Bây giờ tất cả các hạn chế để tìm giải pháp tối ưu đã được đặt ra, chúng ta có thể nhấn nút:

Sau này chúng ta sẽ có được giải pháp cho vấn đề.



Nếu tính toán thành công, sau khi hoàn tất tìm kiếm giải pháp, các giá trị sẽ được chèn vào bảng và bạn cũng có thể chỉ định Loại báo cáo - Kết quả, nhờ đó chúng ta có thể nhận được báo cáo sau. lợi nhuận thiết bị thời gian công nhân


Do đó, cách giải trong EXCEL cũng giống như cách giải trong phương pháp SIMPLEX, nghĩa là bài toán đang xem xét đã được giải đúng.

Giải ZLP bằng phương pháp đơn hình bằng bảng EXCEL

Hãy để ZLP ban đầu được rút gọn về dạng chính tắc và hệ thống hạn chế của nó có dạng ưa thích. Ví dụ: đối với “Bài toán sử dụng nguyên liệu thô”, mô hình toán học loại tương ứng sẽ như sau:

Bảng đơn giản đầu tiên trên bảng tính EXCEL sẽ trông như thế nào (Hình 10):



Giả sử rằng học sinh đã quen thuộc với thuật toán của phương pháp đơn giản dạng bảng, chúng tôi sẽ mô tả các giai đoạn chính của quá trình thực hiện nó bằng bảng EXCEL.

Giai đoạn 1. Chọn cột và hàng kích hoạt và đánh dấu phần tử kích hoạt (xem Hình 11).

Bước 2. Thay thế các cột “Base” và “Cb” vào bảng mới theo quy tắc điền.



    Các phần tử của dòng cho phép được chia thành phần tử cho phép và được ghi vào hàng tương ứng với số của bảng mới:

, Tại tôi = r. (*)

    Tất cả các phần tử khác của bảng mới được tính bằng công thức:

, Tại tôi ≠ r (**)

một phần tử của bảng đơn giản mới ở đâu, Một ij , - phần tử của bảng đơn trước đó, Một rk- yếu tố cho phép, Một tôi- phần tử của cột độ phân giải, Một rj- phần tử của chuỗi kích hoạt.

Ghi chú . Để sử dụng khả năng sao chép công thức của EXCEL với việc sửa đổi địa chỉ của các ô có trong chúng, bạn nên lập trình công thức (*) và (**) chỉ cho các ô của cột “B”, cung cấp địa chỉ tuyệt đối cho các ô đừng thay đổi. Dữ liệu công thức sau đó được sao chép sang tất cả các ô còn lại trong mỗi hàng của bảng mới.

Giai đoạn 4. Các phần tử ở hàng cuối cùng của bảng mới được điền bằng cách sử dụng công thức (**) hoặc theo quy tắc điền vào hàng này.

Kết quả tính toán trong bảng EXCEL cho ví dụ của chúng tôi được hiển thị trong Hình 11 và các công thức được sử dụng trong các tính toán này được hiển thị trong Hình. 12.



    Akulich I.L. Lập trình toán học trong các ví dụ và bài toán: Proc. cẩm nang dành cho sinh viên kinh tế. chuyên gia. trường đại học - M.: Cao hơn. trường học, 1986.-319 trang, bệnh.

    Sakovich V.A. Nghiên cứu hoạt động (Các phương pháp và mô hình xác định): Hướng dẫn tham khảo. - Mn.: Cao hơn. trường học, 1984.-256p.

    Taha H. Giới thiệu về nghiên cứu hoạt động: trong 2 cuốn sách. Cuốn sách 1. Mỗi. từ tiếng Anh – M.: Mir, 1985.-479 trang, bệnh.

    Hướng dẫn phương pháp thực hành môn “Lập trình toán học” (quy hoạch tuyến tính) cho sinh viên chuyên ngành kinh tế / Comp. Turovtsev G.V., khỏa thân I.P. – Zaporozhye, ZGIA, 1984.-31 tr.

    Lập trình toán học. Bài giảng dành cho sinh viên chuyên ngành kinh tế của các khoa toàn thời gian và bán thời gian / Glushchevsky V.V., Isaenko A.N. – Zaporozhye: ZGIA, 2003. – 150 tr.