Trình bày quy hoạch tuyến tính. Lập trình tuyến tính

Quy hoạch tuyến tính▪ Bài toán quy hoạch tuyến tính – slide 3.
▪ Phương pháp hình học giải PLP – slide 26.
▪ Bài toán quy hoạch tuyến tính dạng chuẩn – slide 32.
▪ Phương pháp đơn giản giải ZLP – slide 42.
▪ Phương pháp Gaussian – 48 slide.
▪ Phương pháp đơn giản – 58 slide.
▪ Phương pháp nền nhân tạo – 76 slide.
▪ Tính đối ngẫu của bài toán quy hoạch tuyến tính – slide 87.

Bài toán quy hoạch tuyến tính (LP)

Các giai đoạn xây dựng mô hình toán học

Các bài toán quy hoạch tuyến tính cổ điển

Nhiệm vụ kiểm soát kỹ thuật

Giới thiệu

Lập trình tuyến tính như một nhánh của nghiên cứu hoạt động đã có lịch sử gần bốn mươi năm. Sự ra đời của công nghệ máy tính đã tạo động lực đáng kể cho việc nghiên cứu trong lĩnh vực toán học này. Một số thuật toán để giải các bài toán quy hoạch tuyến tính đã được phát triển và trong những năm tiếp theo, các chương trình và gói phần mềm được tạo ra chủ yếu cho các máy tính lớn. Phần lớn các tài liệu trên. quy hoạch tuyến tính ở nước ta ra đời vào những năm 60, 70. Nghiên cứu trong lĩnh vực này (cả lý thuyết và ứng dụng) vẫn tiếp tục cho đến ngày nay.

Phương pháp quy hoạch tuyến tính đã được chứng minh là rất hiệu quả trong việc giải quyết một số vấn đề trong lĩnh vực nghiên cứu hoạt động. Chúng tôi hiểu từ “lập trình” là lập kế hoạch và điều này quyết định bản chất của các ứng dụng đang được xem xét. Những ý tưởng cơ bản của quy hoạch tuyến tính nảy sinh trong Thế chiến thứ hai liên quan đến việc tìm kiếm các chiến lược tối ưu trong việc tiến hành các hoạt động quân sự. Kể từ đó, chúng đã được ứng dụng rộng rãi trong công nghiệp, thương mại và chính phủ - cả ở địa phương và quốc gia. Những phương pháp này có thể giải quyết được nhiều vấn đề (mặc dù không phải tất cả) liên quan đến việc sử dụng hiệu quả các nguồn lực hạn chế.

Các phương pháp và mô hình toán học được biết đến rộng rãi, phổ biến và được sử dụng dưới nhiều tên gọi khác nhau - các phương pháp toán học trong việc ra quyết định; phương pháp nghiên cứu hoạt động; phương pháp kinh tế và toán học; các phương pháp điều khiển học kinh tế; các phương pháp điều khiển tối ưu, toán học ứng dụng trong kinh tế và tổ chức sản xuất, v.v. Trong nhiều ấn phẩm về chủ đề này (ít nhiều toàn diện), chúng được xem xét theo nhiều cách kết hợp khác nhau.

Nghiên cứu hoạt động là một môn khoa học liên quan đến việc phát triển và ứng dụng thực tế các phương pháp để quản lý hiệu quả nhất các hệ thống tổ chức khác nhau.

Việc quản lý bất kỳ hệ thống nào đều được thực hiện như một quy trình tuân theo các luật nhất định. Kiến thức của họ giúp xác định các điều kiện cần và đủ để thực hiện quy trình này. Để làm được điều này, tất cả các thông số đặc trưng cho quá trình và các điều kiện bên ngoài phải được định lượng và đo lường. Do đó, mục tiêu của nghiên cứu hoạt động là cung cấp sự biện minh về mặt định lượng cho các quyết định được đưa ra liên quan đến việc tổ chức quản lý.

Mục tiêu của bất kỳ mô hình hóa nào là nghiên cứu đối tượng, trước tiên ở cấp độ định tính, sau đó, khi thông tin tích lũy và mô hình phát triển, ở cấp độ định lượng ngày càng chính xác hơn.

Những cân nhắc này có thể được minh họa bằng một ví dụ đơn giản. Đã có (và tồn tại) phương pháp “lý thuyết xác suất” là một lớp rộng các mô hình toán học vận hành với các khái niệm “xác suất”, “sự kiện ngẫu nhiên”, “biến ngẫu nhiên”, “kỳ vọng toán học (giá trị trung bình) của một biến ngẫu nhiên” , “phương sai (phân tán)”, v.v. Ở biên giới của thế kỷ 19 và 20. một đối tượng mới xuất hiện - một hệ thống điện thoại chuyển mạch, trong đó có liên quan đến các khái niệm “yêu cầu kết nối”, “từ chối”, “thời gian chờ kết nối”, “chuyển mạch” và các đặc điểm khác của hệ thống.

Vào những năm 20 A. K. Erlang đã kết hợp các phương pháp và đối tượng này; Kết quả là, một mô hình lý thuyết xác suất toán học của các quá trình trong mạng điện thoại chuyển mạch đã được tạo ra, hoạt động với các khái niệm “luồng yêu cầu”, “thời gian chờ trung bình”, “độ dài hàng đợi trung bình cho dịch vụ”, “phân tán thời gian chờ”, “ xác suất thất bại”, v.v. Sự phát triển hơn nữa của hướng khoa học này cho thấy thành quả của cơ sở khái niệm của mô hình này và khả năng thiết kế rộng rãi của nó. Mô hình này đã phát triển thành một phương pháp nghiên cứu các hệ thống phức tạp - “lý thuyết xếp hàng”, thuật ngữ và cơ sở khái niệm của nó được trừu tượng hóa từ các mối liên hệ với mạng điện thoại và có đặc điểm lý thuyết chung. Và bây giờ các mô hình mới có thể được xây dựng bằng cách áp dụng lý thuyết xếp hàng vào các đối tượng khác (quy trình sản xuất, hệ điều hành máy tính, luồng lưu lượng, v.v.).

Như vậy, một mặt, phương pháp được xác định nếu phát triển một tập hợp các mô hình đồng nhất, tức là các cách xem xét các đối tượng khác nhau trên một khía cạnh, mặt khác, đối tượng được nhận thức càng sâu thì càng có nhiều mô hình của đối tượng. đối tượng được phát triển. Đồng thời, tính chất kép của mô hình dẫn đến tính nhị nguyên của cơ sở khái niệm của mô hình hóa, bao gồm các khái niệm chung (từ “phương pháp”) và khái niệm cụ thể (từ “đối tượng”).

Nghiên cứu hoạt động là một tập hợp các phương pháp toán học ứng dụng được sử dụng để giải quyết các vấn đề thực tế về tổ chức (bao gồm cả kinh tế). Đó là một ngành khoa học phức tạp. Phạm vi của các vấn đề được nghiên cứu bởi nó không được xác định đầy đủ. Đôi khi, nghiên cứu hoạt động được hiểu rất rộng, bao gồm một số phương pháp toán học thuần túy, đôi khi ngược lại, rất hẹp - như một kỹ thuật thực tế để giải một danh sách các vấn đề được xác định chặt chẽ bằng cách sử dụng các mô hình kinh tế và toán học.

Phương pháp nghiên cứu hoạt động chính là phân tích có hệ thống các hành động (hoạt động) có mục tiêu và đánh giá so sánh khách quan (đặc biệt là định lượng) về kết quả có thể có của các hành động này.

Trong số các loại vấn đề nghiên cứu hoạt động quan trọng nhất là các vấn đề về quản lý hàng tồn kho, phân bổ và phân công nguồn lực (vấn đề phân phối), vấn đề xếp hàng, vấn đề thay thế thiết bị, sắp xếp và phối hợp (bao gồm cả lý thuyết lập kế hoạch), đối nghịch (ví dụ: trò chơi), vấn đề tìm kiếm. v.v. Trong số các phương pháp được sử dụng là lập trình toán học (tuyến tính, phi tuyến tính, v.v.), phương trình vi phân và sai phân, lý thuyết đồ thị, quy trình Markov, lý thuyết trò chơi, lý thuyết về các nghiệm (thống kê), lý thuyết nhận dạng mẫu và một số phương pháp khác.

Người ta tin rằng nghiên cứu hoạt động bắt nguồn từ trước Thế chiến thứ hai, khi một nhóm chuyên gia được thành lập tại một trạm radar ở Anh để giải quyết các vấn đề kỹ thuật bằng toán học. Họ tập trung vào việc so sánh tính hiệu quả của các cách giải quyết vấn đề và tìm ra giải pháp tối ưu. Sự tham gia của đại diện các chuyên ngành khác nhau trong nhóm này đã xác định trước một cách tiếp cận tổng hợp, hay như người ta nói ngày nay, là một cách tiếp cận có hệ thống. Hiện nay, hàng trăm tổ chức và nhóm nghiên cứu ở hàng chục quốc gia đang hoạt động theo hướng này. Các Hiệp hội Nghiên cứu Hoạt động, do Liên đoàn Quốc tế (IFRS) thống nhất, đã được tổ chức.

Các nhà khoa học Nga L.V. Kantorovich, N.P. đã có đóng góp to lớn trong việc tạo ra một bộ máy toán học hiện đại và phát triển nhiều lĩnh vực nghiên cứu hoạt động. Buslenko, E.S. Ventzel, N.N. Vorobyov, N.N. Moiseev, D.B. Yudin và nhiều người khác.

Những đóng góp đáng kể cho việc hình thành và phát triển nghiên cứu hoạt động được thực hiện bởi các nhà khoa học nước ngoài R. Akof, R. Bellman, G. Danzig, G. Kuhn, J. Neumann, T. Saaty, R. Churchman, A. Kofman và những người khác.

Các phương pháp nghiên cứu hoạt động, giống như bất kỳ phương pháp toán học nào, luôn đơn giản hóa và xử lý vấn đề ở mức độ này hay mức độ khác, phản ánh các quá trình phi tuyến tính với mô hình tuyến tính, hệ thống ngẫu nhiên với các mô hình xác định, v.v. Do đó, không nên phóng đại tầm quan trọng của các phương pháp định lượng trong nghiên cứu hoạt động cũng không hạ thấp nó, trích dẫn ví dụ về các quyết định thất bại. Có một định nghĩa nghịch lý nổi tiếng được đưa ra bởi một chuyên gia nổi tiếng người Mỹ trong lĩnh vực này

T. A. Saaty: “Nghiên cứu hoạt động là nghệ thuật đưa ra những câu trả lời tồi cho những câu hỏi thực tế mà thậm chí còn được trả lời tệ hơn bằng những cách khác.”

TRƯỜNG CÔNG NGHỆ LIÊN KHU TRUNG TÂM CÔNG NGHỆ CÔNG NGHIỆP VÀ KHỞI NGHIỆP

tôi chấp thuận

Phó Giám đốc phụ trách học thuật

" " 200 G .

BÀI TẬP

cho thiết kế khóa học

trong môn học “Phương pháp toán học”

Sinh viên: Evgeniy Anatolyevich Sergeev.

Đề tài: “Lập trình tuyến tính, giải bài toán bằng phương pháp đơn hình”.

LƯU Ý GIẢI THÍCH

1. Giới thiệu
2. Phần lý thuyết
3. Phần thực hành

Các vấn đề và giải pháp của họ:

Nhiệm vụ một:

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

F = 2X1 +3X2 → tối đa

3.1.2 Nhiệm vụ thứ hai:

Công ty sản xuất hai loại sản phẩm. Các loại nguyên liệu, trữ lượng, tỷ lệ tiêu hao nguyên liệu/năm. Nghĩa là, đối với từng loại sản phẩm, lợi nhuận sản xuất từ ​​việc bán sản phẩm được thể hiện ở bảng:

3.1.3. Nhiệm vụ ba:

Công ty sản xuất 3 loại sản phẩm, sử dụng 3 loại nguyên liệu. Tình hình tồn kho nguyên vật liệu, tỷ lệ tiêu hao và lợi nhuận bán ra của từng sản phẩm được thể hiện ở bảng:

Nên hoạch định sản xuất như thế nào để tối đa hóa lợi nhuận?

3.1.4. Nhiệm vụ bốn:

Để sản xuất 4 loại sản phẩm, 3 loại nguyên liệu thô được sử dụng. Tình hình tồn kho nguyên vật liệu, tỷ lệ tiêu hao và lợi nhuận bán ra của từng sản phẩm được thể hiện ở bảng:

Nên hoạch định sản xuất như thế nào để tối đa hóa lợi nhuận?

3. Phần kết luận

4. Thư mục

Chủ tịch ủy ban chu kỳ/Baranov V.A.

Trưởng dự án khóa học/Karpushkin A.G.

Ngày thực hiện: Ngày hoàn thành:

" " 2007 " " 2007

PHƯƠNG PHÁP ĐƠN GIẢN

Phương pháp đơn giản lần đầu tiên được đề xuất bởi nhà khoa học người Mỹ J. Danzig vào năm 1949, tuy nhiên, vào năm 1939, ý tưởng của phương pháp này đã được phát triển bởi một nhà khoa học Nga

L V. Kantorovich.

Phương pháp đơn hình, cho phép giải bất kỳ bài toán quy hoạch tuyến tính nào, có tính phổ quát. Hiện tại, nó được sử dụng để tính toán trên máy tính, nhưng các ví dụ đơn giản sử dụng phương pháp đơn hình có thể được giải thủ công.

Để thực hiện phương pháp đơn giản - cải tiến nhất quán giải pháp - cần nắm vững ba cơ bản

yếu tố:

Phương pháp xác định bất kỳ giá trị ban đầu nào có thể chấp nhận được

giải pháp cơ bản cho vấn đề;

Quy tắc chuyển sang giải pháp tốt nhất (chính xác hơn là không phải giải pháp tồi tệ nhất);

Tiêu chí kiểm tra tính tối ưu của lời giải tìm được.

Để sử dụng phương pháp đơn hình, bài toán quy hoạch tuyến tính phải được quy về dạng chính tắc, tức là hệ thống ràng buộc phải được biểu diễn dưới dạng phương trình.

Ngoại lệ thông thường của Jordan

Xét hệ m phương trình tuyến tính với n ẩn số

a11 x1 + a12 x2 + … + a1n xn = b1,

am1 x1 + am2 x2 + … + amn xn = bm.

Hãy viết hệ thống này dưới dạng bảng

Bước loại trừ Jordan (OJE) thông thường được thực hiện trên một bảng đã cho với phần tử phân giải aij ≠ 0 với hàng phân giải I và cột phân giải j được gọi là thao tác giải phương trình

bi = ai1 x1 + ai2 x2 + … + aij xj + … + ain xn

so với xj, thay nghiệm này vào hệ ban đầu và ghi lại hệ mới thu được dưới dạng bảng mới.

Thật dễ dàng để kiểm tra xem bảng mới sẽ trông như thế nào

trong đó brs = ars aij - arj ais (i ≠ r, j ≠ s),

và tất cả các phần tử của bảng phải được chia cho aij.

Như vậy, một bước loại bỏ Jordan (JE) sẽ biến bảng gốc thành bảng mới theo sơ đồ bao gồm 5 quy tắc sau:

1) phần tử phân giải được thay thế bằng một

2) các phần tử còn lại của cột độ phân giải j không thay đổi.

3) các phần tử còn lại của chuỗi phân giải tôi chỉ thay đổi dấu của chúng.

4) các phần tử còn lại của brs được tính bằng công thức brs = ars aij - arj ais

5) tất cả các phần tử của bảng mới được chia cho phần tử phân giải aij.

Ví dụ 1. Đối với một bảng

Các ngoại lệ của Jordan cho phép chúng ta chuyển từ hệ tọa độ Descartes được chọn ngẫu nhiên sang một hệ mới trong đó tọa độ của các điểm là độ lệch của chúng so với hệ mặt phẳng thú vị hơn đối với một bài toán cụ thể.

Ngoại lệ Jordan đã sửa đổi

Nếu hệ phương trình ban đầu ai1 x1 + ai2 x2 + … + ain xn = bi, trong đó i = 1,m,

viết dưới dạng –ai1 (-x1) – ai2 (-x2) - … - ain (-xn) = bi

và làm một cái bàn

đạt được theo quy tắc 1 - 5 của OJI với thay đổi duy nhất là quy tắc 2 và 3 thay đổi vai trò:

1) các phần tử còn lại của chuỗi quyền không thay đổi

2) các phần tử còn lại của cột độ phân giải chỉ thay đổi dấu

Hãy xem xét hệ thống

2X1 + 3X2 – 5X3 = 16 = b1,

3X1 - 2X2 + 4X3 = 36 = b2,

5X1 + 7X2 – 11X3 = 44 = b3.

Hãy viết nó dưới dạng một bảng

Cực trị của hàm tuyến tính

Chúng ta hãy xem xét một vấn đề quy hoạch tuyến tính tổng quát. Cơ sở của phương pháp tính toán LP là định lý cơ bản sau.

Định lý. Nếu bài toán quy hoạch tuyến tính có lời giải tối ưu

(luôn luôn trong miền bị chặn và trong miền không bị chặn phụ thuộc vào giới hạn của hàm Z) thì nó trùng với ít nhất một trong các nghiệm hỗ trợ của hệ phương trình ràng buộc.

Theo định lý này, thay vì nghiên cứu một tập vô hạn các lời giải khả thi để tìm ra lời giải tối ưu mong muốn trong số đó thì chỉ cần nghiên cứu một số hữu hạn lời giải tham chiếu.

Định lý này phát biểu rằng có ít nhất một giải pháp tối ưu tham chiếu, tuy nhiên, các bài toán có thể chứa nhiều giải pháp tối ưu tham chiếu (tối ưu thay thế).

Vì vậy, sơ đồ cơ bản để giải các bài toán quy hoạch tuyến tính như sau:

1. Sử dụng LC, chúng tôi tìm thấy tất cả các giải pháp hỗ trợ của hệ thống.

a11 x1 + a12 x2 + … + a1n xn = b1,

……...................

ak1 x1 + ak2 x2 + … + akn xn = bk,

ak+1.1 x1 + ak+1.2 x2 + … + ak+1n xn ≤ bk+1 ,

……...................

am1 x1 + am2 x2 + … + amn xn ≤ bm .

2. Chúng ta hãy tính cho mỗi giá trị của hàm Z, được xác định bởi mối quan hệ.

Z = c1 x1 + c2 x2 + … + cn xn.

3. Hãy chọn một Z cực trị từ chúng.

Cần lưu ý rằng có thể có một số lượng rất lớn các giải pháp hỗ trợ, vì vậy cần tiến hành tìm kiếm các giải pháp hỗ trợ một cách có trật tự, đạt được

mỗi bước của một sự thay đổi đơn điệu trong hàm Z.

Ý tưởng cải tiến tuần tự lời giải này được đưa vào phương pháp tính toán chính để giải các bài toán quy hoạch tuyến tính, được gọi là phương pháp đơn hình.

Phương pháp đơn giản dựa trên các bảng hoàn chỉnh

Phát biểu bài toán xác định dãy sản phẩm tối ưu

Doanh nghiệp có thể sản xuất hai loại sản phẩm A và B, do nguồn lực sản xuất hạn chế là vật liệu gang và thép với số lượng lần lượt là 350 và 392 kg và thiết bị với số lượng 408 giờ máy. Dữ liệu, được trình bày dưới dạng bảng, mô tả chi phí của từng loại trong số ba loại nguồn lực được liệt kê để sản xuất một sản phẩm A và B.

Cần xác định doanh nghiệp nên sản xuất bao nhiêu sản phẩm A và B để đạt được lợi nhuận lớn nhất.

Chúng ta hãy đưa ra các ẩn số cần thiết X1 và X2, biểu thị số lượng sản phẩm A và B mà doanh nghiệp nên sản xuất.

Khi đó về mặt toán học, bài toán có thể được phát biểu như sau.

Trong số các nghiệm không âm của hệ bất đẳng thức

14X1 + 5X2 350, (1.1)

14Х1 + 8Х2 392,

6Х1 + 12Х2 408,

tìm một giải pháp cho chức năng

Z = 10 X1 + 5 X2

đạt giá trị lớn nhất.

Giải pháp hình học cho vấn đề

Trước hết chúng ta xây dựng một miền nghiệm khả thi tương ứng với hệ bất phương trình.

Để làm điều này, thay thế từng bất đẳng thức bằng đẳng thức

14X1 + 5X2 = 350, (dòng 1),

14X1 + 8X2 = 392, (dòng thứ 2),

6X1 + 12X2 = 408, (dòng thứ 3),

xây dựng đường ranh giới. Xét X1 ≥ 0 và X2 ≥ 0, chúng ta thu được phần được tô bóng của mặt phẳng tạo thành đa giác nghiệm OABCD (Hình 1).

Sau đó, chúng ta xây dựng đường mức 10X1 + 5X2 = 0 và vectơ (10;5), chúng vuông góc với nhau. Dễ dàng chứng minh rằng vectơ cho hướng tăng lớn nhất của hàm tuyến tính.

Thật sự

Z0= 10X10 + 5X20 = ​​​​10 * 0 + 5 * 0 = 0,

ZA = 10X1A + 5X2A = 10 * 0 + 5 * 34 = 170,

ZD = 10X1D + 5X2D = 10 * 25 + 5 * 0 = 250, v.v.

Từ tất cả các đường mức, chúng ta chọn hai đường, trong đó một đường đi qua điểm 0 và cho giá trị tối thiểu của hàm Z, đường kia đi qua điểm C và hàm Z lấy giá trị tối đa. Những đường mức này được gọi là đường tham chiếu.

Cơm. 1

Điểm C được tạo bởi đường thẳng thứ nhất và thứ hai. Vì vậy việc giải hệ phương trình

14Хl + 5Х2 = 350,

14X1 + 8X2 = 392,

tìm tọa độ điểm C

X1 = 20, X2 = 14,

trong trường hợp này Zmax = 10 * 20 + 5 * 14 = 270 rúp.

Như vậy, lợi nhuận tối đa là 270 rúp. sẽ nhận được nếu doanh nghiệp sản xuất 20 sản phẩm loại A và 14 sản phẩm loại B.

Tìm cực đại của hàm tuyến tính

Cơ sở của phương pháp đơn hình để giải các bài toán quy hoạch tuyến tính, với một số bổ sung, là phương pháp loại bỏ tuần tự đã thảo luận trước đó, là một tập hợp các thuật toán tính toán thuận tiện được xây dựng trên ứng dụng tuần tự của các phép biến đổi giống hệt nhau (đơn giản) của một hệ phương trình.

Cộng vế trái của bất đẳng thức

14X1 + 5X2 350,

14Х1 + 8Х2 392,

6Х1 + 12Х2 408,

một số đại lượng không âm Yj ≥ 0 (i = 1, 2, 3), (1.2)

được gọi là biến san lấp mặt bằng hoặc biến cơ sở, hãy biến chúng thành phương trình:

Trong trường hợp này, có thể chứng minh rằng mỗi nghiệm của hệ bất đẳng thức (1.1) tương ứng với một nghiệm duy nhất của hệ phương trình (1.3) và bất đẳng thức (1.2) và ngược lại.

Mỗi biến Y1, Y2, Y3 chỉ có trong một phương trình và phụ thuộc vào các biến X1 và X2 mà chúng ta gọi là miễn phí.

Hệ (1.3) tương ứng với nghiệm cơ sở được chấp nhận ban đầu X1 = X2 = 0;

Y1 = 350; Y2 = 392; Y3 = 408 và Z = 0.

Chúng tôi thực hiện phép biến đổi nhận dạng đầu tiên của hệ phương trình (1.3). Chúng tôi chọn cột phân giải tương ứng với phần tử âm nhỏ nhất trong hàng Z, bởi vì về mặt lý thuyết đã được thiết lập rằng trong trường hợp này, chúng tôi có thể mong đợi, tất cả những thứ khác đều bằng nhau, hàm Z sẽ tăng nhiều hơn. Chúng tôi chia vế phải của các phương trình thành các phần tử của cột phân giải và chọn tỷ lệ dương nhỏ nhất tương ứng với hàng phân giải (phương trình). Tại giao điểm của cột và hàng đã chọn có số độ phân giải.

Chúng ta chia phương trình đầu tiên cho số có độ phân giải và viết ra phương trình thu được. Nhân phương trình này với 14, 6 và -10 rồi trừ lần lượt các phương trình thứ 2, 3 và 4 của hệ (1.3), ta thu được hệ (1.4):

Một phép biến đổi giống hệt như vậy, trong đó số độ phân giải được chọn theo quy tắc đã chỉ định, sẽ được gọi là phép biến đổi đơn giản.

Do đó, phép biến đổi đơn giản được thực hiện theo quy tắc sau:

1. Cột độ phân giải tương ứng với phần tử âm nhỏ nhất trong hàng Z được chọn.

2. Một hàng phân giải được chọn tương ứng với tỷ lệ dương nhỏ nhất của các phần tử bên phải của phương trình với các phần tử tương ứng của cột phân giải. Tại giao điểm của cột độ phân giải và hàng độ phân giải có số độ phân giải.

3. Các phần tử của chuỗi độ phân giải được chia cho số độ phân giải.

4. Các phần tử của tất cả các hàng khác được tính bằng công thức:

Từ hệ (1.4) ta tìm được nghiệm cơ bản chấp nhận được thứ hai X2 = Yl = 0; X1 = 25; Y2 = 42; Y3 = 258, tương ứng với giá trị hàm tăng mới Z = 250.

Như vậy, quá trình các phép biến đổi đơn liên tiếp là quá trình cải tiến liên tiếp nghiệm. Trong đó:

1. Nếu có ít nhất một phần tử âm trong hàng Z và

a) có ít nhất một phần tử tích cực trong cột độ phân giải thì giải pháp đó có thể được cải thiện;

b) nếu cột độ phân giải không chứa phần tử dương thì hàm Z tăng không giới hạn.

2. Nếu tất cả các phần tử trong hàng Z đều không âm thì đã đạt được giải pháp tối ưu.

Đây là những điều kiện đủ để tồn tại phương án giải quyết tối ưu.

Trong hệ (1.4), hệ số của X2 ở hàng Z là âm nên cột thứ hai sẽ được phân giải. Chúng tôi thấy rằng dòng thứ hai sẽ được giải quyết. Tiếp theo, chúng ta thực hiện phép biến đổi đơn giản của hệ (1.4) theo quy tắc đã cho:

X1 + 8/42 Y1 – 5/42 Y2 = 20,

X2 – 1/3 Y1 + 1/3 Y2 = 14,

20/7 Y1 – 23/7 Y2 + Y3 = 120,

10/42 Y1 + 20/42 Y2 + Z = 270, (1,5)

Vì tất cả các phần tử trong hàng Z đều không âm nên phương án này là tối ưu. Trong trường hợp này, Yl = Y2 = 0; X1 = 20; X2 = 14 và Zmax = 270.

Việc thực hiện các phép biến đổi đơn giản đòi hỏi phải tính toán tỉ mỉ và thường khá cồng kềnh. Những phép tính này có thể được đơn giản hóa rất nhiều bằng cách sử dụng cái gọi là bảng đơn giản để giải quyết vấn đề.

Mỗi phép biến đổi đơn giản của hệ thống được rút gọn thành một chuyển đổi từ bảng đơn giản này sang bảng đơn giản khác.

Theo hệ phương trình gốc (1.3), ta lập bảng đơn thứ nhất (Bảng 1.1).

Bảng 1.1

Cột đầu tiên là cột các biến cơ bản, cột thứ hai chứa các hệ số tự do ở vế phải của phương trình (1.3), dòng đầu tiên chứa tất cả các biến, cột cuối cùng là cột điều khiển và các hệ số trong đó bằng tổng của tất cả các hệ số trong hàng.

Từ cái bàn 1.1 ta có nghiệm khả thi thứ nhất của hệ (1.3) X1 = X2 = 0, Y1 = 350,

Y2 = 392, Y3 = 408, Z = 0, ứng với đỉnh O (0,0) của đa giác nghiệm khả thi OABCD (Hình 1).

Việc chuyển sang bảng đơn thứ hai (Bảng 1.2) được thực hiện theo quy tắc nêu tại đoạn này đối với các phép biến đổi đơn giản của hệ phương trình, trong khi biến giải X1 đi về cơ sở thay cho biến giải quyết Y1 ta thu được bảng. 1.2.

Bảng 1.2

Sau khi điền vào bảng. 1.2, bạn nên kiểm tra xem đã điền đúng chưa bằng cách tính tổng hệ số theo hàng và tổng này phải bằng các hệ số ở các ô tương ứng của cột điều khiển. Từ cái bàn 1.2 Phương án khả thi thứ 2 sẽ là X1 = 25, X2 = 0, Y1 = 0, Y2 = 42, Y3 = 258 và Z = 250.

Dễ dàng nhận thấy bảng này tương ứng với hệ (1.4) và nghiệm tham chiếu

X1 = 25, X2 = 0 tương ứng với đỉnh D(25,0) của đa giác nghiệm.

Vì có một phần tử âm trong hàng Z, nên chúng tôi cải tiến giải pháp mà chúng tôi soạn một bảng đơn giản. 1.3.

Bảng 1. 3

*Ghi chú. Để đơn giản hóa các phép tính, hãy nhớ rằng trong bảng mới, các phần tử của cột độ phân giải (ngoại trừ phần tử độ phân giải) được thay thế bằng số 0. Nếu dòng phân giải chứa số 0 thì các cột tương ứng sẽ được chuyển sang bảng mới mà không thay đổi:

Vì không có phần tử âm nào trong chuỗi Z nên giải pháp này sẽ tối ưu.

Bàn 1.3 tương ứng với hệ phương trình (1.5) và nghiệm tối ưu X1 = 20,

X2 = 14 và Zmax = 270 và đỉnh C (20,14) của đa giác nghiệm khả thi OABCD.

Các bảng mở rộng như vậy, chứa tất cả các biến ở hàng đầu tiên, nhờ sự hiện diện của cột điều khiển, cho phép bạn kiểm soát tính chính xác của việc điền vào bảng và tránh các lỗi số học.

Phương pháp đơn giản dựa trên bảng rút gọn

Xét hệ phương trình (1.3) và viết dưới dạng bảng 1.4

Bảng 1.4

Chúng ta viết các biến cơ bản (BP) ở cột đầu tiên và các biến tự do (SP) ở hàng đầu tiên. Tiếp theo chúng ta chuyển sang bảng mới 1.5 theo quy tắc:

1) hoán đổi SP và BP

2) thay cho phần tử phân giải có một giá trị nghịch đảo với nó

3) các phần tử của luồng phân giải được chia cho số phân giải

4) chia các phần tử của cột phân giải cho cột phân giải và đổi dấu

5) các phần tử còn lại tìm như trong chương “Tìm cực đại của hàm tuyến tính”, quy tắc 4 (quy tắc hình chữ nhật cho OGI). Ta được bảng 1.5.

Bảng 1.6

Chúng tôi đã thu được phương án tối ưu Zmax = 270 với X1 = 20, X2 = 14 và tài nguyên thiết bị hóa ra đã vượt quá số lượng 120 giờ máy.

Giải bài toán quy hoạch tuyến tính

Tìm cực đại của hàm mục tiêu

dưới những hạn chế

14x + 5y 350

Giải quyết vấn đề bằng chương trình Microsoft Excel.

Chúng ta gán A3 và B3 cho giá trị của biến x và y.

Tại ô C4 chúng ta nhập hàm mục tiêu

Trong ô A7:A9, chúng tôi nhập phần bên trái của các hạn chế

và trong các ô B7:B9 – phần bên phải của các hạn chế.

Sau đó chọn lệnh Dịch vụ, Tìm giải pháp(Công cụ, Bộ giải) và điền vào hộp thoại mở ra Tìm cách giải quyết ( Bộ giải) như trong Hình. 2. Sau khi nhấn nút Hành hình(Giải quyết) cửa sổ mở ra Kết quả tìm kiếm giải pháp(Kết quả bộ giải), báo cáo rằng một giải pháp đã được tìm thấy (Hình 3).

Cơm. 2. Tìm giải pháp

Cơm. 3. Kết quả tìm kiếm giải pháp

Giải hình học của bài toán bằng chương trình MATHCAD 2000.

1. Viết dưới dạng y = kx + b các phương trình đường giới hạn khoảng giá trị cho phép của các biến. Để nhập và giải ràng buộc 14x + 5y ≤ 350 so với y, nhập vế trái của bất đẳng thức, nhấn nút Ctrl và nhấn đồng thời nút =, giữ nút trước đó cho đến khi dấu = đậm hiện lên, đánh dấu biến y bằng hộp tô sáng, nhấp vào menu Ký hiệu (Ký hiệu) trên dòng Giải (Tính toán) – kết quả của các phép tính sẽ được hiển thị trong tài liệu làm việc ở bên phải của phương trình; Nhập tên của hàm (trong ví dụ này là y1(x)) và gán biểu thức kết quả cho nó. Như vậy, phương trình của một trong các đường giới hạn khoảng giá trị cho phép đã được xác định. Nhập các hạn chế còn lại theo cách tương tự. Nhập phương trình 10x + 5y = Đường mức C (đường tham chiếu) của hàm mục tiêu. Tiến hành theo cách tương tự như khi nhập các ràng buộc, nhưng trước khi giải phương trình tìm y, gán một giá trị nào đó cho hằng số C.
2. Vẽ các đường thẳng tương ứng trên đồ thị và xác định miền nghiệm khả thi của hệ.
3. Bằng cách thay đổi giá trị của hằng số C, ví dụ C = 100,150,200,250,..., quan sát sự chuyển động của đường tham chiếu và rút ra kết luận về khả năng giải được của bài toán.
4. Nếu bài toán có nghiệm duy nhất, hãy tìm đỉnh mà tại đó Z = Zmax. Trong ví dụ của chúng tôi, hàm mục tiêu đạt cực đại tại điểm giao nhau của các đường 14x + 5y = 350 và 7x + 14y = 196. Tìm tọa độ của điểm bằng hàm Find.
5. Tính giá trị của hàm mục tiêu tại điểm tìm được.

14x + 5y = 350 (-14/5)x + 70 y1(x):= (-14/5)x + 70

7x + 4y = 196 (-7/4)x + 49 y2(x):= (-7/4)x + 49

x + 2y = 68 (-1/2)x + 34 y3(x):= (-1/2)x + 34

10x + 5y = C -2x + (1/5)C y4(x):= -2x + (1/5)C

Cơm. 4.

Tìm (x, y) → (20, 14)

f(x, y): = 10x + 5y

fmin: = f(20, 14)

Phân tích giải quyết vấn đề bằng chương trình MATHCAD 2000.

Giải pháp phân tích một vấn đề trong MathCAD đơn giản hơn nhiều.

1. Đặt chế độ tính toán tự động.
2. Viết bài toán với x và y tùy ý được gán giá trị tùy ý (hợp lệ) để chương trình bắt đầu đếm.

Z(x, y): = 10x + 5y

14x + 5x 360

M: = Tối đa hóa(z, x, y) M = (20, 14) Z(M0, M1) = 270

Bài toán tối đa hóa hàm tuyến tính khi có hệ số tự do âm

Tìm cực đại của hàm tuyến tính

dưới những hạn chế

X1 – X2 3,

2X1 – 3X2 6,

X1 ≥ 0, X2 ≥ 0.

Hãy viết hệ thống dưới dạng

Y1 = -X1 + X2 + 3 ≥ 0

Y2 = X1 + X2 - 5 ≥ 0

Y3 = -2X1 + 3X2 + 6 ≥ 0

Y4 = -X2 + 6 ≥ 0

Hãy làm một cái bàn.

Chúng tôi tiếp tục làm việc với dòng thứ 2, vì phần tử âm không bị thiếu. Chúng tôi thực hiện SMGI với phần tử phân giải -2. Chúng tôi nhận được một cái bàn.

Bài toán tối thiểu hóa hàm tuyến tính

Chuyển bài toán cực tiểu hóa thành bài toán cực đại hóa của hàm tuyến tính

Chúng tôi đã xem xét việc giải bài toán tìm cực đại của hàm tuyến tính bằng phương pháp đơn hình

W = c1 x1 + c2 x2 + … + cn xn.

Tuy nhiên, trong nhiều bài toán kinh tế cần tìm điểm cực tiểu của hàm tuyến tính. Để làm điều này, chỉ cần đặt

W = -Z = -c1 x1 – c2 x2 - … - cn xn

và giải bài toán cực đại hóa hàm W dưới các ràng buộc thích hợp. Vì rõ ràng rằng

Giảm thiểu hàm tuyến tính

khi thực hiện các hạn chế

7X1 + 2X2 ≥ 14,

5X1 + 6X2 30,

3X1 + 8X2 ≥ 24,

X1 ≥ 0, X2 ≥ 0.

Lời giải hình học của bài toán (Hình 5) và nó tương ứng với lời giải tối ưu tại điểm

C (48/11, 15/11) đồng thời Zmin = -21/11.

Hình 5. Lời giải hình học của bài toán

Bằng cách đưa vào các biến cân bằng Yi ≥ 0 và hàm W = -Z = 2X1 - 5X2 → max, ta viết bài toán dưới dạng.

Y1 = 7X1 + 2X2 - 14,

Y2 = -5X1 - 6X2 + 30,

Y3 = 3X1 + 8X2 - 24,

Chúng tôi viết hệ thống này dưới dạng một bảng.

Chúng ta loại bỏ số hạng tự do âm trong hàng Y1 bằng cách thực hiện SMGI với phần tử phân giải “-50/8”, chúng ta thu được một bảng.

Do không có phần tử âm nào ở hàng W và 1 cột nên ta thu được phương án tối ưu X1 = 48/11, X2 = 15/11, Wmax – 21/11 hoặc Zmin = –Wmax = -21/11,

Phần thực hành

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

X1 + 3X2 300 F = 2X1 + 3X2 → tối đa

Giải pháp

X1 + 3X2 + X3 = 300 F - 2X1 - 3X2 = 0

X1 + X2 + X4 = 150

Đáp án: X1 = 75; X2 = 75; X3 = 0; X4 = 0.

Nhiệm vụ số 1.

Công ty sản xuất hai loại sản phẩm. Các loại nguyên liệu, trữ lượng, tỷ lệ tiêu hao nguyên liệu tương đương. Với mỗi loại sản phẩm, lợi nhuận sản xuất từ ​​việc bán sản phẩm được trình bày ở bảng.

Giải pháp

2X1 + 2X2 17

X1 + 3X2 + X3 = 20 F - 2X1 - X2 = 0

2X1 + X2 + X4 = 10

2X1 + 2X2 + X5 =17

Đáp án: X1 = 5; X2 = 0; X3 = 15; X4 = 0; X5 = 7.

Nhiệm vụ số 2.

Công ty sản xuất ba loại sản phẩm, sử dụng ba loại nguyên liệu thô. Tình hình tồn kho nguyên vật liệu, tỷ lệ tiêu thụ và lợi nhuận bán ra của từng sản phẩm được thể hiện trong bảng.

Nên tổ chức sản xuất như thế nào để doanh nghiệp có lợi nhuận lớn nhất?

Giải pháp

2X1 + 3X2 + 7X3 ≤ 1250 F = 41X1 + 35X2 + 96X3 → tối đa

5X1 + 3X2 900

2X1 + 3X2 + 7X3 + X4 = 1250 F - 41X1 - 35X2 - 96X3 = 0

X1 +X2 + X5 = 250

5X1 +3X2 + X6 = 900

X1 + 3X2 20 F = 2X1 + X2 → tối đa

2X1 + 2X2 17

(-1/3)(-1/3)(2/3)

Đáp án: X1 = 0; X2 = 29/5; X3 = 0; X4 = 13/5; X5 = 0; X6 = 0; X7 = 54/5.

Phần kết luận

Chúng ta hãy tập trung vào những cách giải thích đơn giản nhất của phương pháp đơn giản.

Ý nghĩa đại số của phương pháp đơn hình là bằng cách thực hiện các phép biến đổi đại số giống hệt nhau, chúng ta chuyển từ một nghiệm khả thi của một hệ phương trình đại số sang một nghiệm cải tiến khác, đạt được nghiệm tối ưu cho bài toán.

Từ quan điểm hình học, các phép biến đổi giống hệt nhau bằng phương pháp đơn hình biểu thị các chuyển động liên tiếp từ một đỉnh của đa giác lồi của nghiệm sang đỉnh lân cận, từ đỉnh này sang đỉnh tiếp theo, v.v. đến đỉnh tối ưu dọc theo các cạnh của đa giác này.

Bản chất kinh tế của phương pháp đơn giản nằm ở chỗ nó là một phương pháp cải tiến nhất quán các giải pháp. Phương pháp này giúp bạn có thể thực hiện được, bằng cách chọn một kế hoạch hành động bắt đầu – tham khảo, dần dần tiến về phía trước và cuối cùng đạt được một kế hoạch tối ưu, tất nhiên, nếu kế hoạch đó tồn tại.

Một đơn hình là một đa giác lồi trong không gian n chiều với n + 1 đỉnh không nằm trên cùng một siêu phẳng. Các đơn hình được tách thành một lớp riêng vì đơn hình là đa giác đơn giản nhất chứa một thể tích không gian n chiều nhất định.

Người ta đã chứng minh rằng nếu tồn tại một giải pháp tối ưu thì chắc chắn nó sẽ được tìm thấy sau một số hữu hạn bước (ngoại trừ cái gọi là “bài toán suy biến”, trong đó có thể xảy ra hiện tượng “đi xe đạp”, tức là lợi nhuận lặp lại). vào cùng một vị trí).

Lập trình tuyến tính là một lĩnh vực lập trình toán học dành riêng cho lý thuyết và phương pháp giải các bài toán cực trị được đặc trưng bởi mối quan hệ tuyến tính giữa các biến.

Lập trình toán học (lập trình tối ưu) là một lĩnh vực toán học kết hợp nhiều phương pháp và bộ môn toán học khác nhau: quy hoạch tuyến tính, quy hoạch động, lập trình lồi, v.v. Nhiệm vụ chung của lập trình toán học là tìm giá trị tối ưu (cực đại hoặc cực tiểu) của mục tiêu. hàm và giá trị của các biến phải thuộc một phạm vi giá trị có thể chấp nhận được.

Danh sách tài liệu được sử dụng

1) A. S. Shapkin, N. P. Mazaeva; Phương pháp toán học và mô hình nghiên cứu hoạt động, 2005.

2) N.Sh. Kremer, B A Putko, I.M. Trishin, M.N. Friedman; Nghiên cứu hoạt động trong kinh tế. - ĐOÀN KẾT, 2002.

Ra quyết định trong điều kiện không chắc chắn Nếu đối tượng thứ nhất có m chiến lược và đối tượng thứ hai có n chiến lược thì chúng ta được cho là đang giải quyết một trò chơi m x n. Xét trò chơi m x n. Cho một tập hợp các chiến lược: đối với người chơi thứ nhất (Ai), đối với người chơi thứ hai (Bj), ma trận thanh toán, trong đó aij là phần thắng của người chơi thứ nhất hoặc phần thua của người chơi thứ hai khi họ chọn chiến lược Ai và Bj, tương ứng. Mỗi người chơi chọn duy nhất với xác suất là một chiến lược nào đó, tức là sử dụng một chiến lược thuần túy khi lựa chọn một giải pháp. Trong trường hợp này, giải pháp của trò chơi sẽ là các chiến lược thuần túy. Vì lợi ích của những người chơi là trái ngược nhau, nên người chơi thứ nhất cố gắng tối đa hóa số tiền thắng của mình, còn người chơi thứ hai thì ngược lại, giảm thiểu tổn thất của mình. Giải pháp của trò chơi là xác định chiến lược tốt nhất cho mỗi người chơi. Việc một người chơi lựa chọn chiến lược tốt nhất được thực hiện trong trường hợp hoàn toàn không có thông tin về quyết định của người chơi thứ hai.

Giải hệ bất phương trình tuyến tính

Bất bình đẳng

Bất đẳng thức tuyến tính là bất đẳng thức có dạng ∑ai xi +b ≥c

Việc xác định một hệ bất đẳng thức tuyến tính có hai hoặc ba ẩn số có nghĩa là xác định một vùng đa giác lồi trên một mặt phẳng hoặc theo đó là một khối đa diện lồi trong không gian.

Từ giữa những năm 1940, một lĩnh vực toán ứng dụng mới đã xuất hiện - quy hoạch tuyến tính - với những ứng dụng quan trọng trong kinh tế và công nghệ. Cuối cùng, quy hoạch tuyến tính chỉ là một phần (mặc dù là một phần rất quan trọng) của lý thuyết về hệ bất đẳng thức tuyến tính.

Xét phương trình bậc một với hai ẩn số x và y

Giải thích x và y là tọa độ điểm

trên máy bay, chúng ta có thể nói rằng

tập hợp các điểm xác định bởi phương trình (1) là một đường thẳng trên mặt phẳng.

Ý nghĩa hình học của phương trình bậc một

Tương tự với bất đẳng thức ax+by+c ≥0. (2)

Nếu b≠0 thì bất đẳng thức này được rút gọn thành một trong các loại y ≥kx+p hoặc y

Bất đẳng thức đầu tiên được thỏa mãn bởi tất cả các điểm nằm “phía trên” đường thẳng y=khx+p hoặc trên đường thẳng này, và bất đẳng thức thứ hai được thỏa mãn bởi tất cả các điểm nằm “bên dưới” đường thẳng y=khx+p hoặc trên đường thẳng này.

Nếu b=0 thì bất đẳng thức được rút gọn thành một trong các loại x ≥h hoặc x

Ý nghĩa hình học của hệ bất đẳng thức tuyến tính

Cho hệ bất phương trình với hai ẩn số x và y. a1 x+b1 y+c1 ≥0,

a2 x+b2 y+c2 ≥0,

………….........

sáng x+bm y+cm ≥0.

Bất đẳng thức thứ nhất của hệ xác định một nửa mặt phẳng P1 nhất định trên mặt phẳng tọa độ xOy, bất đẳng thức thứ hai – nửa mặt phẳng P2, v.v. Nếu một cặp số x, y thỏa mãn mọi bất đẳng thức của hệ thì điểm M(x, y) tương ứng thuộc tất cả các nửa mặt phẳng P1, P2,..., Pm đồng thời. Nói cách khác, điểm M thuộc giao điểm (của phần chung) của các nửa mặt phẳng đã cho. Dễ dàng thấy rằng giao của một số hữu hạn các nửa mặt phẳng là một vùng đa giác nhất định.

Ví dụ

Dọc theo đường viền của vùng có các nét đi vào vùng. Chúng đồng thời chỉ ra nửa mặt phẳng tương ứng nằm ở phía nào của một đường thẳng cho trước; điều tương tự được chỉ ra với sự trợ giúp của các mũi tên.

Phạm vi giải pháp không giới hạn

Vùng K được gọi là miền nghiệm của hệ bất đẳng thức. Chúng ta hãy lưu ý ngay rằng phạm vi của các giải pháp không phải lúc nào cũng bị giới hạn; Là kết quả của sự giao nhau của một số nửa mặt phẳng, một vùng không giới hạn có thể xuất hiện.

Mô tả bài thuyết trình theo từng slide:

1 slide

Mô tả slide:

Lý thuyết ra quyết định PetrSU, A.P. Moshchevikin, 2004 Lập trình tuyến tính Lớp lập trình tuyến tính này (75% các bài toán được người Mỹ giải quyết) bao gồm các bài toán trong đó hàm mục tiêu là Wm(x), m=1,2,..., M, các giới hạn ở dạng các đẳng thức hk(x)=0, k=1,2...K, và các bất đẳng thức gj(x)>0, j=1,2,...J, là tuyến tính và không có biểu thức toán học giải pháp. Các chủ đề có thể có của nhiệm vụ LP: sử dụng hợp lý nguyên, vật liệu; cắt giảm các vấn đề tối ưu hóa; tối ưu hóa chương trình sản xuất của doanh nghiệp; vị trí và sự tập trung sản xuất tối ưu; lập phương án vận chuyển và khai thác vận tải tối ưu; quản lý hàng tồn kho; và nhiều vấn đề khác thuộc lĩnh vực quy hoạch tối ưu. Phát biểu bài toán LP (xác định chỉ báo hiệu quả, các biến nhiệm vụ, xác định hàm mục tiêu tuyến tính W(x) cực tiểu hoặc cực đại, hàm hk(x), gj(x) và xli khu vực

2 cầu trượt

Mô tả slide:

Lý thuyết ra quyết định PetrSU, A.P. Moshchevikin, 2004. Ví dụ về bài toán LP Ví dụ - Tối ưu hóa vị trí các sản phẩm phụ của một sở lâm nghiệp Huyện lâm nghiệp có 24 ha đất bỏ hoang và đang quan tâm đến việc thu lợi nhuận từ nó. Nó có thể nuôi những cây giống cây Giáng sinh lai phát triển nhanh và trưởng thành trong một năm hoặc những con bò đực, dành một phần đất cho đồng cỏ. Cây được trồng và bán theo đợt 1.000 cây. Phải mất 1,5 ha để trồng một lứa cây và 4 ha để nuôi một con bò. Ngành lâm nghiệp chỉ có thể dành 200 giờ mỗi năm cho các sản phẩm phụ của mình. Thực tiễn cho thấy, phải mất 20 giờ để trồng trọt, tỉa, chặt và bó một lứa cây. Việc chăm sóc một con bò đực cũng cần 20 giờ. Lâm nghiệp có cơ hội chi 6 nghìn rúp cho mục đích này. Chi phí hàng năm cho một lứa cây lên tới 150 rúp. và 1,2 nghìn rúp. cho một con bò đực. Một hợp đồng đã được ký kết về việc cung cấp 2 con bò đực. Với mức giá hiện tại, một cây thông Noel sẽ mang lại lợi nhuận 2,5 rúp, một con bò đực - 5 nghìn rúp.

3 cầu trượt

Mô tả slide:

Lý thuyết ra quyết định PetrSU, A.P. Moshchevikin, 2004. Tuyên bố về vấn đề 1. Là một chỉ số về hiệu quả, nên lấy lợi nhuận cho hoạt động (lợi nhuận hàng năm từ đất tính bằng rúp). 2. Lấy các biến sau đây làm biến kiểm soát của bài toán: x1 - số bò đực được cho ăn trong năm; x2 - số lô cây Giáng sinh phát triển nhanh gồm 1000 cây. mỗi năm. 3. Hàm mục tiêu: 5000 x1 + 2500 x2  max, trong đó 5000 là thu nhập ròng từ một con bò đực, chà.; 2500 - thu nhập ròng từ một lứa cây (1000 chiếc với giá 2,5 rúp). 4. Hạn chế: 4.1. Theo loại hình sử dụng đất, ha: 4 x1 + 1,5 x2  24 4.2. Theo ngân sách, chà.: 1200 x1 + 150 x2  6000 4.3. Theo nguồn lực lao động h: 20 x1 + 20 x2  200 4.4. Nghĩa vụ theo hợp đồng, chiếc: x1  2 4.5. Giới hạn khu vực: x1  0, x2  0

4 cầu trượt

Mô tả slide:

Lý thuyết quyết định PetrSU, A.P. Moshchevikin, 2004 Giải pháp đồ họa của bài toán LP Hiển thị trên đồ thị các đường thẳng tương ứng với các phương trình sau, 4 x1 + 1,5 x2 = 24 1200 x1 + 150 x2 = 6000 20 x1 + 20 x2 = 200 x1 = 2 x2 = 0 tô bóng khu vực tại các điểm mà tất cả các hạn chế đều được thỏa mãn. Mỗi điểm như vậy được gọi là một giải pháp khả thi và tập hợp tất cả các giải pháp khả thi được gọi là vùng khả thi. Rõ ràng, giải pháp cho bài toán LP bao gồm việc tìm giải pháp tốt nhất trong vùng khả thi, do đó được gọi là tối ưu. Trong ví dụ đang xem xét, giải pháp tối ưu là giải pháp khả thi giúp cực đại hóa hàm W=5000 x1 + 2500 x2. Giá trị của hàm mục tiêu tương ứng với lời giải tối ưu được gọi là giá trị tối ưu của bài toán LP.

5 cầu trượt

Mô tả slide:

Lý thuyết ra quyết định PetrSU, A.P. Moshchevikin, 2004 Giải pháp đồ họa cho bài toán LP

6 cầu trượt

Mô tả slide:

Lý thuyết ra quyết định PetrSU, A.P. Moshchevikin, 2004. Giải pháp đồ họa của bài toán LP. Việc liệt kê tất cả các điểm góc trong vùng của các giải pháp khả thi dẫn đến việc tìm ra thu nhập tối đa với số tiền 34 nghìn rúp. (W=5000x1+2500x2), mà bộ lâm nghiệp có thể khai thác bằng cách trồng 3,6 con bò đực và 6,4 lô cây Giáng sinh. Các phương pháp số nguyên (ví dụ: lực lượng vũ phu) cho x1=3 và x2=6, dẫn đến thu nhập là 30 nghìn rúp, x1=4 và x2=5 dẫn đến kết quả tối ưu hơn là 32,5 nghìn rúp, điểm x1 =3 và x2=7 dẫn đến kết quả tương tự. Phương pháp đồ họa, do kích thước lớn của các bài toán LP thực tế thực tế, hiếm khi được sử dụng, nhưng nó cho phép người ta hiểu rõ ràng một trong những tính chất chính của LP - nếu có một giải pháp tối ưu cho bài toán LP thì ít nhất một trong các các đỉnh của vùng chấp nhận được biểu thị một giải pháp tối ưu. Mặc dù miền khả thi của bài toán LP bao gồm vô số điểm, giải pháp tối ưu luôn có thể được tìm thấy bằng cách tìm kiếm có mục đích thông qua một số hữu hạn các đỉnh của nó. Phương pháp đơn hình để giải bài toán LP được xem xét dưới đây dựa trên tính chất cơ bản này.

7 cầu trượt

Mô tả slide:

Lý thuyết ra quyết định PetrSU, A.P. Moshchevikin, 2004 Giải quyết vấn đề LP trong MS Excel Một trong những chức năng tích hợp sẵn của trình soạn thảo bảng tính MS Excel (bạn phải chọn hộp này trong khi cài đặt MS Office) là “Tìm kiếm giải pháp”. Gói này cho phép bạn giải quyết nhanh chóng các vấn đề lập trình tuyến tính và phi tuyến.

8 trượt

Mô tả slide:

Lý thuyết quyết định PetrSU, A.P. Moshchevikin, 2004. Bài toán LP ở dạng chuẩn. Bài toán LP ở dạng chuẩn với m ràng buộc và n biến có dạng: W = c1x1 + c2x2 + ... + cnxn  min (max) theo giới hạn a11x1 + a12x2 + ... + a1nxn = b1; a21x1 + a22x2 + ... + a2nxn = b2; ... am1x1 + am2x2 + ... + amnxn = bm; x10; x20;...; xn0 b10; b20;...; bm0 Ở dạng ma trận W = cx  min (max) có giới hạn Ax = b; x0; b0, trong đó A là ma trận có chiều m*n, x là vectơ cột chứa các biến có chiều n*1, b là vectơ cột chứa tài nguyên có chiều m*1, c là vectơ hàng ước lượng cho Vấn đề LP 1*n.

Trang trình bày 9

Mô tả slide:

Lý thuyết ra quyết định PetrSU, A.P. Moshchevikin, 2004 Biến đổi của bất bình đẳng Các ràng buộc ở dạng bất bình đẳng có thể được chuyển đổi thành đẳng thức bằng cách đưa ra cái gọi là biến dư hoặc biến dư. Phương trình ở ví dụ trước 4x1 + 1,5x2  24 có thể được chuyển đổi thành đẳng thức bằng cách sử dụng biến số dư không âm 4x1 + 1,5x2 + x3 = 24. Biến x3 không âm và tương ứng với hiệu của vế phải và vế trái của bất đẳng thức. Tương tự, x1  2 có thể được biến đổi bằng cách đưa vào biến dự phòng x4: x1 - x4 = 2.

10 slide

Mô tả slide:

Lý thuyết ra quyết định PetrSU, A.P. Moshchevikin, 2004. Ungr chuyển đổi. theo dấu biến Chuyển đổi biến có dấu không giới hạn Các biến nhận cả giá trị dương và âm nên được thay thế bằng hiệu của hai biến không âm: x = x+ - x-; x+0; x-  0. Ví dụ. 3x1+4x2+5x3+4x4  tối đa 2x1+x2+3x3+5x4  5 5x1+3x2+x3+2x4  20 4x1+2x2+3x3+x4 = 15 x10; x20; x3 0; x4 =  dấu -3x1-4x2+5x3-4x4  min 2x1+x2-3x3+5x4-x5 = 5 5x1+3x2-x3+2x4+x6 = 20 4x1+2x2-3x3+x4 = 15 x10; x20; x30; dấu x4 = ; x4 =x8-x7 -3x1-4x2+5x3-4x8+4x7 tối thiểu 2x1+x2-3x3+5x8-5x7-x5 = 5 5x1+3x2-x3+2x8-2x7+x6 = 20 4x1+2x2-3x3+x8 -x7= 15 x1,x2,x3,x5,x6,x7,x80; x4=x8 -3x1-4x2+5x3-4x4+4x7 tối thiểu 2x1+x2-3x3+5x4-5x7-x5 = 5 5x1+3x2-x3+2x4-2x7+x6 = 20 4x1+2x2-3x3+x4-x7 = 15 x1,x2,x3,x4,x5,x6,x70; x8 thay thế bằng x4

11 slide

Mô tả slide:

Lý thuyết ra quyết định PetrSU, A.P. Moshchevikin, 2004. Phương pháp LP đơn giản Phương pháp đơn giản là một thủ tục lặp lại để giải các bài toán LP được viết ở dạng chuẩn, hệ phương trình trong đó sử dụng các phép toán cơ bản trên ma trận được rút gọn về dạng chính tắc: x1 + a1,m+1xm+1 + ... + a1sxs+...+ a1nxn = b1; x2 + a2,m+1xm+1 + ... + a2sxs+...+ a2nxn = b2; ... xm + am,m+1xm+1 + ... + amsxs+...+ amnxn = bm. Các biến x1, x2,...,xm chỉ có hệ số đơn vị trong một phương trình của hệ và không có hệ số bằng 0 ở các phương trình còn lại, được gọi là cơ bản. Trong hệ thống chính tắc, mỗi phương trình tương ứng với chính xác một biến cơ bản. Các biến n-m còn lại (xm+1, ..., xn) được gọi là biến không cơ bản. Để đưa hệ thống về dạng chính tắc, bạn có thể sử dụng hai loại phép toán cơ bản trên chuỗi: Nhân bất kỳ phương trình nào của hệ thống với số dương hoặc số âm. Thêm vào bất kỳ phương trình nào một phương trình khác của hệ thống, nhân với số dương hoặc số âm.

12 trượt

Mô tả slide:

Lý thuyết ra quyết định PetrSU, A.P. Moshchevikin, 2004. Phương pháp Simplex LP Viết bài toán dưới dạng phương trình x1 + a1,m+1xm+1 + ... + a1sxs+...+ a1nxn = b1; x2 + a2,m+1xm+1 + ... + a2sxs+...+ a2nxn = b2; ... xm + am,m+1xm+1 + ... + amsxs+...+ amnxn = bm. giống hệt với mục nhập ma trận 1 0 .. 0 a1,m+1 .. a1s .. a1n x1 b1 0 1 .. 0 a2,m+1 .. a2s .. a2n x2 = b2 . . .. . . .. . .. . .. .. 0 0 .. 1 giờ sáng,m+1 .. ams .. amn xn bm

Trang trình bày 13

Mô tả slide:

Lý thuyết ra quyết định PetrSU, A.P. Moshchevikin, 2004. Thuật toán phương pháp Simplex 1. Chọn giải pháp cơ bản khả thi ban đầu. Giải pháp cơ bản là giải pháp thu được cho giá trị 0 của các biến không cơ bản, tức là. xi=0, i=m+1,...,n. Một nghiệm cơ bản được gọi là nghiệm cơ bản được chấp nhận nếu giá trị của các biến cơ bản có trong nó không âm, tức là. xj = bj  0, j=1,2,...,m. Trong trường hợp này, hàm mục tiêu sẽ có dạng sau: W=cbxb=c1b1+c2b2+...+cmbm. Ta điền vào bảng ban đầu của phương pháp đơn hình:

Trang trình bày 14

Mô tả slide:

Lý thuyết ra quyết định PetrSU, A.P. Moshchevikin, 2004. Thuật toán phương pháp Simplex 2. Tính vectơ ước lượng tương đối c sử dụng quy tắc tích vô hướng сj = сj - cbSj, trong đó сb là vectơ ước lượng của các biến cơ bản; Sj là cột thứ j của các hệ số aij trong hệ chính tắc tương ứng với cơ sở đang xét. Chúng ta bổ sung vào bảng ban đầu một hàng c.

15 trượt

Mô tả slide:

Lý thuyết ra quyết định PetrSU, A.P. Moshchevikin, 2004. Thuật toán phương pháp Simplex 3. Nếu tất cả các ước lượng cj  0 (cj  0), i=1,...,n thì phương án khả thi hiện tại là lớn nhất (tối thiểu ). Giải pháp đã được tìm thấy. 4. Mặt khác, cần nhập vào cơ sở một biến không cơ bản xr có giá trị lớn nhất là cj thay vì một trong các biến cơ bản (xem bảng).

16 trượt

Mô tả slide:

Lý thuyết ra quyết định PetrSU, A.P. Moshchevikin, 2004. Thuật toán phương pháp Simplex 5. Sử dụng quy tắc tỷ lệ tối thiểu min(bi/air), chúng ta xác định biến xp xuất phát từ cơ sở. Nếu hệ số không khí âm thì bi/air=. Kết quả, giao điểm của cột chứa biến cơ bản đầu vào xr và hàng chứa biến cơ bản đầu ra xp sẽ xác định vị trí của phần tử đầu bảng. 6. Chúng ta áp dụng các phép biến đổi cơ bản để thu được nghiệm cơ bản khả thi mới và một bảng mới. Kết quả là phần tử đứng đầu phải bằng 1 và các phần tử còn lại của cột phần tử đứng đầu phải có giá trị bằng 0. 7. Tính điểm tương đối mới bằng quy tắc biến đổi vô hướng và chuyển sang bước 4.

Trang trình bày 17

Mô tả slide:

Lý thuyết ra quyết định của PetrSU, A.P. Moshchevikin, 2004. Ví dụ về quyết định sử dụng phương pháp đơn giản Ví dụ - Tối ưu hóa việc sắp xếp các phụ phẩm của lâm nghiệp 3. Hàm mục tiêu: 5000 x1 + 2500 x2  max, 4. Hạn chế: 4.1. Theo loại hình sử dụng đất, ha: 4 x1 + 1,5 x2  24 4.2. Theo ngân sách, chà.: 1200 x1 + 150 x2  6000 4.3. Theo nguồn lực lao động h: 20 x1 + 20 x2  200 4.4. Nghĩa vụ theo hợp đồng, chiếc: x1  2 4.5. Giới hạn vùng: x1  0, x2  0 Ta rút gọn bài toán về dạng chuẩn: 4 x1 + 1.5 x2 +x3= 24 1200 x1 + 150 x2 +x4= 6000 20 x1 + 20 x2 +x5= 200 x1 – x6= 2 x1 ... x6  0 Ba phương trình đầu lần lượt có biến cơ sở x3, x4, x5, nhưng phương trình thứ tư vắng mặt do biến x6 có hệ số đơn vị âm. Để đưa hệ thống về dạng chính tắc, chúng ta sử dụng phương pháp biến nhân tạo. x1 – x6+x7= 2, đưa ra biến nhân tạo x7.