Phương pháp giải tối ưu

NỘI DUNG

Các quy định chính của môn học “Phương pháp giải pháp tối ưu” là nền tảng giáo dục toán học của một chuyên gia được chứng nhận, điều này rất quan trọng để nghiên cứu thành công các môn học đặc biệt được cung cấp trong chương trình giáo dục chính cho chuyên ngành này.

Để hấp thụ hiệu quả Tài liệu giáo dục và đạt được chứng chỉ cuối cùng, trong thời hạn quy định của chương trình giảng dạy, cần phải hoàn thành nhiệm vụ kiểm soát và cung cấp chúng để giáo viên xem xét qua email. Lịch học tập và báo cáo theo ngành được thể hiện ở Bảng 1.

Bảng 1. Lịch làm việc độc lập môn “Các phương pháp giải tối ưu”

1. GIỚI THIỆU. CÔNG THỨC TỔNG QUÁT CỦA VẤN ĐỀ

Quá trình ra quyết định là cốt lõi của tất cả các hoạt động có mục đích. Trong kinh tế học, chúng đi trước việc thành lập các tổ chức sản xuất, kinh doanh và đảm bảo hoạt động và tương tác tối ưu của chúng. Trong nghiên cứu khoa học, chúng cho phép chúng ta xác định những vấn đề khoa học quan trọng nhất, tìm cách nghiên cứu chúng, định trước sự phát triển của cơ sở thực nghiệm và bộ máy lý thuyết. Trong khi tạo công nghệ mới- cấu tạo giai đoạn quan trọng trong việc thiết kế máy móc, thiết bị, dụng cụ, khu phức hợp, tòa nhà, trong việc phát triển công nghệ xây dựng và vận hành chúng; V. lĩnh vực xã hội– được sử dụng để tổ chức hoạt động và phát triển của các quá trình xã hội, sự phối hợp của chúng với các quá trình kinh tế và quá trình kinh tế. Các giải pháp tối ưu (hiệu quả) cho phép bạn đạt được mục tiêu với chi phí lao động, vật liệu và nguyên liệu tối thiểu.

Trong toán học cổ điển, các phương pháp tìm nghiệm tối ưu được xem xét trong các phần liên quan đến việc nghiên cứu cực trị của hàm số trong quy hoạch toán học.

Phương pháp giải pháp tối ưu là một trong những phần của nghiên cứu hoạt động - một lĩnh vực ứng dụng của điều khiển học được sử dụng để giải quyết các vấn đề tổ chức thực tế. Các bài toán lập trình toán học được sử dụng trong khu vực khác nhau hoạt động của con người, trong đó cần phải chọn một trong các phương án hành động khả thi (chương trình hành động).

Một số lượng đáng kể các vấn đề nảy sinh trong xã hội có liên quan đến các hiện tượng được kiểm soát, nghĩa là với các hiện tượng được điều chỉnh trên cơ sở các quyết định được đưa ra một cách có ý thức. Với lượng thông tin hạn chế có sẵn trong giai đoạn đầu phát triển của xã hội, quyết định tối ưu được đưa ra dựa trên trực giác và kinh nghiệm, sau đó, khi lượng thông tin về hiện tượng đang nghiên cứu tăng lên, sử dụng một loạt các phương pháp trực tiếp. tính toán. Ví dụ, điều này đã xảy ra trong việc lập lịch làm việc cho các doanh nghiệp công nghiệp.

Ví dụ, một bức tranh hoàn toàn khác xuất hiện trong một doanh nghiệp công nghiệp hiện đại với sản xuất nhiều lô và nhiều mặt hàng, khi khối lượng thông tin đầu vào quá lớn đến mức không thể xử lý nó nhằm mục đích đưa ra quyết định nhất định nếu không sử dụng điện tử hiện đại máy tính. Những khó khăn lớn hơn còn nảy sinh liên quan đến vấn đề đưa ra quyết định tốt nhất.

Trong môn học “Phương pháp quyết định tối ưu”, việc ra quyết định được hiểu là quá trình khó khăn, trong đó có thể phân biệt các giai đoạn chính sau:

Giai đoạn 1. Sự thi công mô hình chất lượng vấn đề đang được xem xét, tức là xác định các yếu tố có vẻ là quan trọng nhất và thiết lập các khuôn mẫu mà chúng tuân theo. Thông thường giai đoạn này vượt xa toán học.

giai đoạn 2. Xây dựng mô hình toán học của vấn đề đang xem xét, tức là viết mô hình định tính dưới dạng toán học. Vì vậy, mô hình toán học được viết bằng ký hiệu toán học sự trừu tượng của một hiện tượng có thật, được xây dựng sao cho việc phân tích nó có thể đi sâu vào bản chất của hiện tượng. Một mô hình toán học thiết lập mối quan hệ giữa một tập hợp các biến—các tham số để kiểm soát một hiện tượng. Giai đoạn này cũng bao gồm việc xây dựng hàm mục tiêu của các biến, tức là một đặc tính số có giá trị lớn hơn (hoặc nhỏ hơn) tương ứng với tình huống tốt nhất theo quan điểm của quyết định được đưa ra.

Vì vậy, là kết quả của hai giai đoạn này, tương ứng bài toán. Hơn nữa, giai đoạn thứ hai đã yêu cầu sử dụng kiến ​​thức toán học.

giai đoạn thứ 3. Nghiên cứu ảnh hưởng của các biến đến giá trị của hàm mục tiêu. Giai đoạn này liên quan đến việc thành thạo bộ máy toán học để giải các bài toán phát sinh ở giai đoạn thứ hai của quá trình ra quyết định.

Một lớp rộng các bài toán điều khiển bao gồm các bài toán cực trị như vậy, trong đó các mô hình toán học của chúng, các điều kiện trên các biến được xác định bằng các đẳng thức và bất đẳng thức. Lý thuyết và phương pháp giải những bài toán này chính xác là nội dung của lập trình toán học. Ở giai đoạn thứ ba, sử dụng các công cụ toán học, người ta tìm ra lời giải cho các bài toán cực trị tương ứng. Chúng ta hãy chú ý đến thực tế là các bài toán lập trình toán học gắn liền với việc giải những vấn đề thiết thực, như một quy luật, có con số lớn biến và hạn chế. Khối lượng công việc tính toán để tìm ra giải pháp thích hợp lớn đến mức không thể tưởng tượng được toàn bộ quá trình nếu không sử dụng máy tính điện tử hiện đại (máy tính), và do đó yêu cầu tạo ra các chương trình máy tính thực hiện các thuật toán nhất định hoặc sử dụng tiêu chuẩn hiện có. các chương trình.

giai đoạn thứ 4. So sánh kết quả tính toán thu được ở giai đoạn thứ 3 với đối tượng được mô hình hóa, tức là xác minh kết quả của chuyên gia (tiêu chí thực hành). Vì vậy, ở giai đoạn này, mức độ đầy đủ của mô hình và đối tượng được mô hình hóa được thiết lập trong phạm vi độ chính xác của thông tin ban đầu. Có hai trường hợp có thể xảy ra ở đây:

trường hợp thứ nhất. Nếu kết quả so sánh không đạt yêu cầu (tình huống phổ biến ở giai đoạn đầu của quá trình lập mô hình), thì hãy chuyển sang chu kỳ thứ hai của quy trình. Đồng thời, làm rõ thông tin đầu vào về đối tượng được mô hình hóa và nếu cần, làm rõ vấn đề (giai đoạn 1); mô hình toán học được cải tiến hoặc xây dựng lại (giai đoạn 2); bài toán tương ứng được giải (giai đoạn 3) và cuối cùng việc so sánh được thực hiện lại (giai đoạn 4).

trường hợp thứ 2. Nếu kết quả so sánh đạt yêu cầu thì mô hình được chấp nhận. Khi Chúng ta đang nói về về việc sử dụng lặp lại kết quả tính toán trong thực tế đặt ra nhiệm vụ chuẩn bị mô hình để vận hành. Ví dụ, giả sử mục đích của việc lập mô hình là tạo ra các lịch trình hoạt động sản xuất doanh nghiệp. Sau đó, hoạt động của mô hình bao gồm thu thập và xử lý thông tin, nhập thông tin đã xử lý vào máy tính, tính toán dựa trên các chương trình lịch trình đã phát triển và cuối cùng đưa ra kết quả tính toán (ở dạng thân thiện với người dùng) để sử dụng trong lĩnh vực hoạt động sản xuất.

Có hai hướng trong lập trình toán học.

Hướng đầu tiên đã được thiết lập rõ ràng - bản thân lập trình toán học - bao gồm các vấn đề tất định giả định rằng tất cả thông tin ban đầu được xác định hoàn toàn.

Hướng thứ hai - cái gọi là lập trình ngẫu nhiên - bao gồm các bài toán trong đó thông tin ban đầu chứa các yếu tố không chắc chắn hoặc khi một số tham số của bài toán có tính chất ngẫu nhiên với các đặc tính xác suất đã biết. Vì vậy, việc lập kế hoạch hoạt động sản xuất thường được thực hiện trong điều kiện thông tin chưa hoàn tất về tình hình thực tế nơi kế hoạch sẽ được thực hiện. Hoặc, chẳng hạn, khi một vấn đề cực đoan mô phỏng công việc thiết bị tự động, đi kèm với nhiễu ngẫu nhiên. Lưu ý rằng một trong những khó khăn chính của lập trình ngẫu nhiên nằm ở việc hình thành các vấn đề, chủ yếu là do sự phức tạp của việc phân tích thông tin ban đầu.

Theo truyền thống, lập trình toán học được chia thành các phần chính sau:

Lập trình tuyến tính - hàm mục tiêu là tuyến tính và tập hợp cực trị của hàm mục tiêu được tìm kiếm được xác định bởi một hệ thống các đẳng thức và bất đẳng thức tuyến tính. Đổi lại, trong lập trình tuyến tính có các lớp bài toán, cấu trúc của chúng cho phép bạn tạo ra các phương pháp đặc biệt để giải chúng, so sánh thuận lợi với các phương pháp giải bài toán tổng quan. Như vậy, một phần bài toán vận chuyển đã xuất hiện trong quy hoạch tuyến tính.

Lập trình phi tuyến – hàm mục tiêu và các ràng buộc là phi tuyến. Lập trình phi tuyến thường được chia như sau:

Lập trình lồi – hàm mục tiêu là lồi (nếu bài toán tối thiểu hóa nó được xem xét) và tập hợp mà bài toán cực trị được giải quyết là lồi.

Lập trình bậc hai - hàm mục tiêu là bậc hai và các ràng buộc là các đẳng thức và bất đẳng thức tuyến tính.

Các vấn đề đa cực. Ở đây, các lớp vấn đề chuyên biệt thường gặp trong các ứng dụng thường được phân biệt, ví dụ, các vấn đề giảm thiểu hàm lõm trên một tập lồi.

Một nhánh quan trọng của lập trình toán học là Lập trình số nguyên, khi các điều kiện nguyên được áp đặt cho các biến.

Mục tiêu của lập trình toán học là tạo ra, nếu có thể, các phương pháp phân tích để xác định nghiệm và trong trường hợp không có các phương pháp đó, tạo ra các phương pháp tính toán hiệu quả để thu được nghiệm gần đúng.

Cuối cùng, chúng tôi lưu ý rằng tên của chủ đề – “các phương pháp giải pháp tối ưu” – là do mục tiêu của việc giải quyết vấn đề là chọn một chương trình hành động. Chúng ta hãy xem xét kỹ hơn vấn đề quy hoạch tuyến tính

2. GIẢI THÍCH HÌNH HỌC CỦA BÀI TOÁN LẬP TRÌNH TUYẾN TÍNH

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

tìm vectơ X = (x 1 ,x 2 ,...,x n) sao cho dạng tuyến tính cực đại hóa

F = Σ c j x j → max (2.1)

J=1

và thỏa mãn điều kiện:

Σa ij x j ≤ b i (2.2)

J=1

x j ≥0 , j = 1,…,n (2.3)

Hàm tuyến tính F được gọi là hàm mục tiêu của bài toán.

Hãy viết lại vấn đề này dưới dạng vector:

Hãy tìm các hàm:

F = c 1 x 1 + c 2 x 2 + … + c n x n (2.4)

x 1 P 1 + x 2 P 2 + … + x n P n = P 0 , (2.5)

x j ≥0 , j = 1,…,n (2.6)

trong đó P 1, ..., P n và P 0 là các cột vectơ m chiều, từ các hệ số ẩn và số hạng tự do của hệ phương trình của bài toán:

B 1 a 11 a 12 a 1n

P 0 = (b 2) ; P 1 = (a 21) ; P 2 = (a 22) ;……. Pn = (a 2n) ; (2.7)

… … … …

B n a m1 a m2 a mn

Phương án X = (x 1 ,x 2 ,...,x n) được gọi là phương án tham chiếu của ZLP chính nếu các hệ số dương x j nằm tại các vectơ độc lập tuyến tính P j .

Một khối đa diện có lời giải là bất kỳ tập hợp mặt bằng nào không trống cho bài toán quy hoạch tuyến tính chính và bất kỳ điểm góc nào của khối đa diện có lời giải được gọi là một đỉnh.

Định lý

Nếu ZLP chính có phương án tối ưu thì hàm mục tiêu của bài toán sẽ lấy giá trị lớn nhất tại một trong các đỉnh của nghiệm đa diện.

Nếu hàm mục tiêu của một bài toán có giá trị cực đại ở nhiều hơn một đỉnh thì nó sẽ lấy giá trị cực đại đó tại bất kỳ điểm nào là tổ hợp tuyến tính lồi của các đỉnh này.

Kết luận:

Tập hợp các mặt bằng không trống của ZLP chính tạo thành một khối đa diện lồi;

Mỗi đỉnh của khối đa diện này xác định một mặt phẳng tham chiếu;

Tại một trong các đỉnh của khối đa diện, giá trị của hàm mục tiêu là lớn nhất.

Trường hợp hai chiều của ZLP

Chúng ta hãy tìm lời giải cho bài toán, trong đó bao gồm việc xác định giá trị lớn nhất của hàm

F = c 1 x 1 + c 2 x 2 (2.8)

trong những điều kiện

a i1 x 1 + a i2 x 2 ≤ b i , (i=1,…,k) (2.9)

x j ≥0 (j=1,2) (2,10)

Bài toán quy hoạch tuyến tính là tìm một điểm trong đa giác nghiệm mà tại đó hàm mục tiêu F đạt giá trị lớn nhất. Điểm này tồn tại khi đa giác nghiệm không trống và hàm mục tiêu trên đó được giới hạn từ phía trên.

Để xác định đỉnh này, chúng ta sẽ dựng một đường mức c 1 x 1 +c 2 x 2 =h, (trong đó h là một hằng số nào đó) đi qua đa giác nghiệm và chúng ta sẽ di chuyển nó theo hướng của vectơ C = ( c 1,c 2) cho đến khi đi qua điểm chung cuối cùng với đa giác nghiệm. Tọa độ của điểm được chỉ định sẽ xác định phương án tối ưu cho nhiệm vụ này.

Giai đoạn quyết định PPP phương pháp hình học:

1. Dựng đường thẳng bằng các phương trình (2.9), (2.10).

2. Tìm các nửa mặt phẳng được xác định bởi từng ràng buộc của bài toán.

3. Tìm đa giác nghiệm.

4. Xây dựng vectơ C.

5. Vẽ đường thẳng c 1 x 1 +c 2 x 2 =h đi qua đa giác nghiệm.

6. Di chuyển đường thẳng c 1 x 1 +c 2 x 2 =h theo hướng vectơ C.

7. Xác định tọa độ điểm cực đại của hàm số và tính giá trị hàm mục tiêu tại điểm đó.

Ví dụ 1.

Để sản xuất hai loại sản phẩm A và B, công ty sử dụng ba loại nguyên liệu thô. Định mức tiêu hao từng loại nguyên liệu để sản xuất ra một đơn vị sản phẩm loại này được trình bày ở Bảng 2.1. Nó cũng cho biết lợi nhuận từ việc bán một loại sản phẩm của mỗi loại và tổng lượng nguyên liệu loại này mà doanh nghiệp có thể sử dụng.

Bảng 2.1

Xét rằng sản phẩm A và B có thể được sản xuất ở bất kỳ tỷ lệ nàonias (doanh số được đảm bảo), cần phải lập kế hoạch phát hành chúng trong đóLợi nhuận tối đa của doanh nghiệp từ việc bán tất cả các sản phẩm là bé nhỏ

Giải pháp:

x1 – sản xuất sản phẩm loại A

x2 – sản xuất sản phẩm loại B

Sau đó, các hạn chế của vấn đề:

Tổng lợi nhuận từ việc bán sản phẩm loại A và B sẽ là: F = 30x1 + 40x2

Chúng ta hãy tìm giải pháp cho vấn đề bằng cách giải thích hình học của nó.

Để làm được điều này, trong các bất đẳng thức của hệ hữu hạn, chúng ta chuyển sang các đẳng thức và dựng các đường thẳng tương ứng:

Hãy tìm tọa độ điểm B - giao điểm của các đường thẳng:

Giải hệ phương trình này ta được: x 1 = 12; x 2 = 18

Do đó, nếu doanh nghiệp sản xuất 12 sản phẩm loại A và 18 sản phẩm loại B thì doanh nghiệp sẽ nhận được lợi nhuận tối đa bằng:

F tối đa = 30·12+40·18 = 1080 chà.

Ví dụ 2.

Giải PIL

tối đa(phút)F = 2x 1 +3x 2 ;

Giải pháp. Để xây dựng miền nghiệm khả thi, ta dựng các đường thẳng biên trong hệ x 1 Ox 2 tương ứng với các ràng buộc bất đẳng thức sau:

x 1 +x 2 ≤ 6, x 1 +4x 2 ≥ 4, 2x 1 -x 2 ≥ 0.

Chúng ta tìm thấy các nửa mặt phẳng chứa các bất đẳng thức này. Để làm điều này, do tính lồi của bất kỳ nửa mặt phẳng nào, chỉ cần lấy một điểm tùy ý mà đường thẳng biên tương ứng không đi qua và kiểm tra xem điểm kiểm tra này có thỏa mãn ràng buộc bất đẳng thức hay không. Nếu nó thỏa mãn thì bất đẳng thức này được thỏa mãn trong nửa mặt phẳng chứa điểm thử. Ngược lại, nửa mặt phẳng được lấy không chứa điểm kiểm tra. Thường thuận tiện khi lấy gốc tọa độ O(0; 0) làm điểm kiểm tra. Trong ví dụ của chúng ta, vùng có lời giải khả thi là tập hợp các điểm của tứ giác ABCD (Hình 6).

Chúng ta xây dựng một vectơ c = (c 1; c 2) = (2; 3). Vì chỉ cần làm rõ hướng tăng của hàm mục tiêu, đôi khi để rõ ràng hơn nên xây dựng λc(λ > 0). Vuông góc với vectơ c ta vẽ đường thẳng F=0. Bằng chuyển động song song của đường thẳng F=0, ta tìm được điểm cực trị B tại đó hàm mục tiêu đạt giá trị lớn nhất và điểm A đạt giá trị nhỏ nhất.

Tọa độ điểm B được xác định bởi hệ thống

Ở đâu Fmax = F(A) = 32/9

NHIỆM VỤ GIẢI PHÁP ĐỘC LẬP

Giải các bài toán 1.1-1.10 bằng đồ thị.

Vấn đề với nhiều biến

Xét bài toán quy hoạch tuyến tính sau

Để giải bằng đồ thị, cần biến đổi hệ hạn chế sao cho ở dạng bài toán chính hệ bao gồm không quá 2 biến.

Điều này có thể được thực hiện tuần tự, loại trừ các biến hoặc sử dụng phương pháp Jordan-Gauss. Hãy xem xét phương pháp Jordan-Gauss.

Bảng 1

(-3) 1 , (-1) 3,4

ban 2

(2) 1 , (-1) 2 ,(1) 3

bàn số 3

(-1) 2 , (1) 3 ,(2) 4

Bảng 4

(-1) 2 , (1) 3 ,(2) 4

Chúng ta hãy loại bỏ các ẩn số cho phép không âm trong các phương trình ràng buộc

x 2 , x 4 , x 5 và thay dấu bằng bằng dấu bất đẳng thức, ta thu được bài toán quy hoạch tuyến tính phụ với hai biến:

F(x) = 2 x 3 +2 → tối đa

F(x) = 0: 2 x 3 +2 -0 (0;-1) ;(5;-1)

F max = 2 tại x 1 = 0; x 3 = 0

3. PHƯƠNG PHÁP SIMPLEX GIẢI QUYẾT VẤN ĐỀ LẬP TRÌNH TUYẾN TÍNH

3.1. Giải thích hình học của phương pháp đơn hình

Nếu bài toán quy hoạch tuyến tính được tối ưu hóa thì điểm tối ưu tương ứng với điểm góc (ít nhất một) của O.D.R. và trùng với ít nhất một trong các nghiệm cơ bản không âm. Do đó, bằng cách sắp xếp qua một số hữu hạn các nghiệm cơ bản không âm của hệ thống, chúng ta chọn từ chúng một nghiệm tương ứng với giá trị cực trị của hàm mục tiêu. Về mặt đồ họa, điều này có nghĩa là chúng ta đi qua các điểm góc của khối đa diện nghiệm, cải thiện giá trị của hàm mục tiêu.

Phương pháp đơn giản bao gồm:

1) xác định mức chấp nhận ban đầu giải pháp cơ bản nhiệm vụ;

2) chuyển sang giải pháp tốt hơn;

3) kiểm tra giải pháp khả thi tối ưu.

3.2. Giải thích dạng bảng của phương pháp đơn giản

Phương pháp đơn hình được sử dụng để giải các bài toán quy hoạch tuyến tính viết dưới dạng chính tắc:

Tìm giải pháp tối ưu

X = (x 1 ,x 2 ,...,x n) (3.1)

thỏa mãn hệ ràng buộc (phương trình)

Σa ij x j = b i (i=1,m) (3.2)

j=1

và điều kiện x j ≥ 0 (j=1,n)

và cho giá trị cực trị của hàm mục tiêu

Z(x) = Σc j x j (3.3)

j=1

Giả sử nghiệm cơ bản không âm ban đầu của hệ (3.2), trong đó x 1, x 2, x 3 ... x m là các ẩn cơ bản và x m+1, x m+2, ..., x n là những ẩn số miễn phí.

Khi đó hệ (3.2) trở thành hệ được phép

(3.4)

Hệ này tương ứng với nghiệm cơ bản không âm có dạng

X 0 = (b 1 ,b 2 ,...,b m ,0,0...0)

Chúng ta hãy thay nghiệm kết quả vào hàm mục tiêu

Δ 0 = L(X 0) = Σ C j B j (3.5)

J=1

và biến đổi nó theo cách nó chỉ phụ thuộc vào các ẩn số tự do x m+1, x m+2, ... x n

Mọi ẩn số cơ bản x 1, x 2, x 3... x m đều có thể biểu diễn dưới dạng tự do x m+1, x m+2, … x n và thay thế nó vào hàm mục tiêu.

Khi đó hàm mục tiêu sẽ có dạng (3.6)

Hãy để chúng tôi giới thiệu khái niệm ước tính Δ j của ẩn số tự do

(3.7)

Khi đó hàm mục tiêu sẽ có dạng

(3.8)

Chúng ta hãy xét các vectơ C = (c 1 , c 2 , …, c m) và B = (a 1j , a 2j , …, a mj) (j=m+1,n) , thì đẳng thức (3.7) có thể viết dưới dạng vectơ

Δ j =CB j -c j(3.9)

Đẳng thức (3.8) không khác về bản chất so với các phương trình của hệ, vì vậy hãy thêm nó vào hệ này và có được một hệ mở rộng:

Kết quả của các phép biến đổi được thực hiện, được ghi lại dưới dạng hệ thống, có thể được nhập vào biểu thức sau bảng đơn:

cột đầu tiên chứa các ẩn số cơ bản x 1 , x 2 , ..., x m ; Cột C 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 này; ở cột B - số hạng tự do của hệ phương trình, trùng với các thành phần dương của nghiệm cơ bản ban đầu không âm X 0 . Dưới các ẩn số x 1 , x 2 , …, x n các hệ số của hệ được ghi vào các cột.

Hàng cuối cùng của bảng này, được gọi là đánh giá hoặc chỉ mục, p tính toán bằng các công thức. Khi chuyển từ một giải pháp cơ bản sang Mặt khác, đường ước tính cũng có thể được tính trực tiếp theo quy tắc hình vuông (phương pháp Jordan-Gauss).

Trong dòng đánh giá, bất đẳng thức Δ j ≥0 nghĩa là tiêu chí tối ưu cho phương án tham chiếu.

Thuật toán giải ZLP bằng phương pháp đơn hình.

1. Tìm kế hoạch tham khảo.

2. Tạo một bảng đơn giản.

3. Tìm hiểu xem có ít nhất một một số âm∆j

Nếu không thì kế hoạch tham khảo được tìm thấy là tối ưu. Nếu trong số các số có Δ j số âm thì bài toán không thể giải được. chi, hoặc chuyển sang một kế hoạch tham khảo mới.

4. Tìm cột và hàng hướng dẫn. Cột lớn nhất được xác định bởi cột lớn nhất giá trị tuyệt đối số âm Δ j và đường dẫn hướng là tỷ số tối thiểu của các thành phần cột của vectơ P 0 với các thành phần dương của cột dẫn hướng.

5. Sử dụng công thức (3.7) – (3.9), xác định các thành phần dương sơ đồ tham chiếu mới, hệ số phân rã vectơ P j thành vectơ cơ sở và số mới. Tất cả các số này đều được viết dưới dạng đơn giản mới bàn.

6. Kiểm tra phương án tìm được ở mức tối ưu. Nếu kế hoạch không tối ưu và cần phải chuyển sang kế hoạch tham chiếu mới thì quay lại điểm 4 và nếu đã đạt được kế hoạch tối ưu hoặc thiết lập nhiều lần Với quyết tâm, quá trình giải quyết vấn đề được hoàn thành.

Ví dụ 3.1.

Để sản xuất các sản phẩm A, B và C, công ty sử dụng ba nhiều loại khác nhau nguyên liệu thô. Tỷ lệ tiêu hao nguyên vật liệu để sản xuất một loại sản phẩm, giá thành một sản phẩm A, B, C và tổng số lượng nguyên liệu của từng loại mà doanh nghiệp có thể sử dụng chúng tôi ăn, tại được thể hiện trong bảng.

Lập kế hoạch sản xuất các sản phẩm có tổng chi phí của tất cả các sản phẩm được sản xuất sẽ là tối đa.

Giải pháp:

Hãy tạo một mô hình toán học. Hãy biểu thị:

x 1 – sản xuất sản phẩm loại A;

x 2 – sản xuất sản phẩm loại B;

x3 – sản xuất sản phẩm loại C.

Hãy viết hệ thống các hạn chế:

Tổng giá thành sản phẩm sản xuất ra là:

F = 9x 1 +10x 2 +16x 3

Theo nội dung kinh tế, các biến x 1, x 2, x 3 chỉ được lấy giá trị không âm:

x1,x2,x3 ≥0

Hãy viết bài toán này dưới dạng ZLP chính, để làm điều này, chúng ta chuyển từ hệ bất đẳng thức sang hệ đẳng thức, để làm điều này, chúng tôi giới thiệu ba biến bổ sung:

Ý nghĩa kinh tế của các biến mới là số lượng nguyên liệu thô thuộc loại này hay loại khác không được sử dụng trong một kế hoạch sản xuất nhất định.

Viết hệ phương trình đã biến đổi dưới dạng vectơ:

x 1 P 1 +x 2 P 2 +x 3 P 3 +x 4 P 4 +x 5 P 5 +x 6 P 6 =P 0

Ở đâu

Vì trong số các vectơ Pj có ba vectơ đơn vị nên đối với bài toán này chúng ta có thể viết sơ đồ tham chiếu X = (0, 0, 0, 360, 192, 180) được xác định bởi hệ vectơ đơn vị P 4, P 5, P 6, tạo thành cơ sở của không gian ba chiều.

Chúng ta biên soạn một bảng lặp I đơn giản và tính các giá trị F 0, z j -c j.

Chúng tôi kiểm tra kế hoạch ban đầu để tối ưu:

F 0 = (C,P 0) = 0; z 1 =(C,P 1)=0; z 2 =(C,P 2)=0; z 3 =(C,P 3)=0;

z 1 -c 1 = 0-9 = -9; z 2 -c 2 = 0-10 = -10; z 3 -c 3 = 0-16 = -16;

Đối với vectơ cơ sở z j -c j = 0 (j=4,5,6).

Số âm lớn nhất Δ j nằm ở hàng thứ 4 cột P 3. Do đó, chúng tôi đưa vectơ P 3 vào cơ sở. Hãy định nghĩa vectơ là ngoại lệ từ cơ sở, vì điều này chúng ta tìm thấy Θ 0 = min(b i /a ij) cho a i3 >0 tức là. Θ = phút (360/12; 192/8; 180/3) =192/8 =24.

Những thứ kia. yếu tố hạn chế cho việc sản xuất sản phẩm C là lượng nguyên liệu sẵn có loại II. Xét đến khả năng sẵn có, doanh nghiệp có thể sản xuất được 24 sản phẩm C, trong khi nguyên liệu loại II sẽ được tiêu thụ hết vano.

Do đó, vectơ P 5 phải bị loại khỏi cơ sở. Cột vectơ P 3 và hàng thứ 2 là hướng dẫn.

Hãy tạo một bảng cho lần lặp II. Đầu tiên, chúng ta điền vào hàng của vectơ mới được đưa vào cơ sở, tức là. hướng dẫn dòng 2. Các phần tử của dòng này có được bằng cách chia các phần tử tương ứng của bảng 1 cho phần tử kích hoạt (tức là 8). Đồng thời ở cột C b ta viết hệ số bệnh nhân C 3=16, đứng trong cột của vectơ P 3 được đưa vào cơ sở

Để xác định các phần tử còn lại của Bảng II, ta áp dụng quy tắc tam giác.

Hãy tính các phần tử của Bảng II trong cột P 0.

Phần tử đầu tiên - tìm ba số

1) số ở dòng 1 tại giao điểm của cột P0 và dòng thứ 1 (360);

2) số ở dòng 1 tại giao điểm của cột P3 và dòng 1 (12);

3) số tại điểm 2 tại giao điểm của cột P0 và dòng thứ 2 (24).

360-12 24 = 72

Phần tử thứ hai đã được tính trước đó (Θ 0 = 192/8 =24)

Yếu tố thứ ba -

1) số ở dòng 1 tại giao điểm của cột P0 và dòng thứ 3 (180);

2) số ở dòng 1 giao nhau giữa cột P3 và dòng thứ 3 (3);

3) số tại điểm 2 tại giao điểm của cột P0 và dòng thứ 2 (24).

180-3·24 =108

Giá trị F 0 ở hàng thứ 4 của cùng một cột có thể tìm được bằng hai cáchbami:

1) theo công thức F 0 =(C,P 0) =0·72+16·24+0·108 = 384;

2) theo quy tắc tam giác:

Hãy tính các phần tử của vectơ P 1 t.2. Chúng tôi lấy hai số đầu tiên từ cộttsov R 1 và R 3 v.1,

và số thứ ba tính từ điểm 2 tại giao điểm của hàng thứ 2 và cột P1.

18-12 (3/ 4) = 9; 5-3 (3/ 4)=11/ 4.

Số z 1 -c 1 ở hàng thứ 4 cột vectơ P 1 bảng 2

có thể được tìm thấy theo hai cách:

1) theo công thức z 1 -с 1 =(C,P 1)-c 1 ta có:

0 9+16 3/ 4+0 11/ 4-9 =3

2) Theo quy tắc tam giác ta có:

-9-(-16) 3/ 4 = 3

Tương tự, ta tìm các phần tử của cột của vectơ P 2.

Các phần tử của cột vectơ P 5 được tính bằng quy tắc tam giác.

trông khác nhau. Tuy nhiên, các hình tam giác được xây dựng để xác định các phần tử này

Khi tính phần tử của hàng đầu tiên của cột được chỉ định, kết quả làtam giác được tạo bởi các số 0;12 và 1/8. Vì vậy, mong muốnphần tử bằng nhau

0 – 12 (1/8) = -3/2.

Phần tử ở dòng thứ 3 của cột này, bằng nhau

0 - 3 (1 /8) = -3/8.

Sau khi hoàn thành việc tính toán tất cả các phần tử trong Bảng II, thu được nhưngsơ đồ cơ bản và hệ số khai triển của vectơ Р j thông qua cơ bảnvectơ P 4, P 3, P 6 và các giá trị F 0 “Δ j”.

Như có thể thấy từ bảng này, kế hoạch tham khảo mới cho vấn đề này làphương án X=(0; 0; 24; 72; 0; 108).

Kế hoạch giải quyết vấn đề được tìm thấy ở lần lặp II là không tối ưu.

dòng này chứa số âm - 2. Điều này cũng có thể được nhìn thấy từ dòng thứ 4 của bảng 2, vì trong cột của vectơ P 2 .

Điều này có nghĩa là vectơ P 2 phải được đưa vào cơ sở, tức là kế hoạch mới sẽ cung cấp cho việc sản xuất sản phẩm B.

Khi xác định số lượng có thể sản xuất được sản phẩm B, cần tính đến số lượng nguyên liệu sẵn có của từng loại, cụ thể là: có thể đầu ra của sản phẩm B được xác định bởi min (b i "/a i 2") cho a i2 ">0 tức là chúng ta tìm thấy Θ 0 = min(72/9; 24 2/1; 108 2/3) = 72/9= số 8.

Do đó, vectơ P4 bị loại khỏi cơ sở, nói cách khác, việc sản xuất sản phẩm B bị hạn chế bởi nguyên liệu thô loại I mà doanh nghiệp có sẵn. Tính đến khối lượng sẵn có của nguyên liệu thô này, doanh nghiệp nên sản xuất 8 sản phẩm B. Số 9 là phần tử phân giải, cột vectơ P2 và hàng đầu tiên của bảng 2 là các hướng dẫn.

Hãy tạo một bảng cho lần lặp III.

Trong bảng III, trước tiên chúng ta điền các phần tử của hàng thứ 1 là hàng của vectơ P2 mới được đưa vào cơ sở. Các phần tử của hàng này được lấy từ các phần tử của hàng đầu tiên của Bảng 2 bằng cách chia phần tử sau cho phần tử phân giải (tức là cho 9).

Đồng thời ở cột C b hàng này ta viết c 2 = 10.

Sau đó, chúng ta điền các phần tử của các cột của vectơ cơ sở và sử dụng quy tắc tam giác để tính các phần tử của các cột còn lại.

Kết quả ở Bảng III ta thu được sơ đồ tham chiếu mới X = (0; 8; 20; 0; 0; 96) và hệ số khai triển của vectơ P j thông qua các vectơ cơ sở P 1, P 2 và P 3 có giá trị tương ứng ​​F 0 "" và Δ j .

Chúng tôi kiểm tra xem kế hoạch tham khảo đã cho có tối ưu hay không. Để làm điều này, hãy xem xét hàng thứ 4, bảng 3. Không có số âm trong số các số trong dòng này. Điều này có nghĩa là phương án tham chiếu tìm được là tối ưu và F max = 400.

Vì vậy, kế hoạch sản xuất bao gồm sản xuất 8 sản phẩm B và 20 sản phẩm C là tối ưu. Với kế hoạch sản xuất sản phẩm này, nguyên liệu thô loại I và II được sử dụng hết và 96 kg nguyên liệu thô loại III vẫn chưa được sử dụng và giá thành sản phẩm sản xuất là 400 €.

Kế hoạch sản xuất tối ưu không quy định việc sản xuất sản phẩm A. Việc đưa sản phẩm loại A vào kế hoạch sản xuất sẽ dẫn đến giảm tổng chi phí đã chỉ định. Có thể thấy điều này từ hàng thứ 4 của cột vectơ P1, trong đó số 5 cho thấy rằng đối với một kế hoạch nhất định, việc đưa ra một đơn vị sản phẩm A trong đó chỉ dẫn đến giảm tổng chi phí 5 €.

Ví dụ 3.2

Điền vào bảng đơn giản ban đầu cho PPP sau:

Giải pháp:

Hãy làm nó bước tiếp theo theo thứ tự này:

-Dòng thứ hai viết ẩn x 1, x 2, ..., x 5;

- ở dòng đầu tiên phía trên chúng là các hệ số tương ứng 3, -2, 1,4, -1 của hàm mục tiêu;

-Dưới các ẩn số x 1 , x 2 , …, x 5 điền vào các cột hệ số vế trái tương ứng của các phương trình của hệ ban đầu;

- vào cột ghi các số hạng tự do của phương trình 3,1,5;

-ở cột đầu tiên B.p. hãy đặt những điều chưa biết x 2 ,x 3 , x 5 , vì có các cột đơn vị bên dưới chúng và do đó chúng tôi sẽ coi chúng là cơ bản; các ẩn số cơ bản được sắp xếp theo thứ tự sao cho các đơn vị trong cột giao nhau với các ẩn số giống hệt nhau;

-trong cột ta viết các hệ số -2,1,-1, từ hàm mục tiêu cho các ẩn số cơ bản đã chọn x 2 ,x 3 , x 5 ;

- Điền vào dòng đánh giá như sau: dưới cột B ta đặt số Δ 0, được tính theo công thức (3.5); dưới những ẩn số cơ bản x 2 ,x 3 , x 5 - số không, cũng có thể thu được từ đẳng thức (3.9); dưới các biến miễn phí x 1 , x 4 - ghi các giá trị thu được từ đẳng thức (3.9).

Chúng tôi ghi lại kết quả của những hành động này trong bảng sau:

Chúng ta hãy chọn cột x 4 làm cột phân giải, là cột “tệ nhất” (nó tương ứng với ước tính âm lớn nhất về giá trị tuyệt đối). Tiếp theo, chúng tôi giới thiệu đường phân giải như sau: đối với các hệ số dương của cột x 4, chúng tôi tính các tỷ số b i /a i4 và ghi vào cột θ.

Số nhỏ nhất sẽ xác định chuỗi độ phân giải. Chúng tôi không xem xét các hệ số âm và 0 do vế phải của các phương trình hệ thống không âm do tính không âm của vế phải của hệ phương trình và yêu cầu hàm mục tiêu ít nhất phải không giảm.

Tại giao điểm của hàng cho phép và cột cho phép, chọn phần tử cho phép. Hãy đạt được rằng phần tử phân giải bằng một, chúng ta chia toàn bộ dòng đầu tiên cho hai. Tiếp theo, chúng ta biến đổi bảng bằng phương pháp Jordan-Gauss.

Như vậy, trong bảng của bước thứ hai đã thỏa mãn tiêu chí tối ưu. Chúng ta nhận được phương án tối ưu X(0;0;11/2;3/2;13/2), max L(X) =5.