Hãy để chúng tôi xây dựng trên bình diện tập hợp các giải pháp chấp nhận được của hệ thống bất bình đẳng tuyến tính và tìm về mặt hình học giá trị tối thiểu hàm mục tiêu.

Chúng tôi xây dựng trong hệ tọa độ x 1 oh 2 dòng

Chúng tôi tìm thấy các nửa mặt phẳng được xác định bởi hệ thống. Vì các bất đẳng thức của hệ được thỏa mãn đối với bất kỳ điểm nào từ nửa mặt phẳng tương ứng, nên chỉ cần kiểm tra một điểm bất kỳ là đủ. Chúng tôi sử dụng điểm (0; 0). Hãy để chúng tôi thay thế tọa độ của nó vào bất đẳng thức đầu tiên của hệ thống. Tại vì , khi đó bất đẳng thức xác định một nửa mặt phẳng không chứa điểm (0; 0). Tương tự, chúng ta xác định các nửa mặt phẳng còn lại. Chúng tôi nhận thấy tập hợp các giải pháp khả thi là một phần chung của các nửa mặt phẳng thu được - đây là vùng bóng mờ.

Ta xây dựng một vectơ và một đường thẳng có cấp độ không vuông góc với nó.

Bằng cách di chuyển đường thẳng (5) theo hướng của vectơ, chúng ta thấy rằng điểm cực đại của vùng sẽ nằm tại điểm A của giao điểm của đường thẳng (3) và đường thẳng (2). Ta tìm nghiệm của hệ phương trình:

Vì vậy, chúng tôi đã có điểm (13; 11) và.

Bằng cách di chuyển đường thẳng (5) theo hướng của vectơ, chúng ta thấy rằng điểm cực tiểu của vùng sẽ nằm tại điểm B của giao điểm của đường thẳng (1) và đường thẳng (4). Ta tìm nghiệm của hệ phương trình:

Vì vậy, chúng tôi đã có điểm (6; 6) và.

2. Một công ty nội thất sản xuất tủ và bàn máy tính kết hợp. Việc sản xuất chúng bị hạn chế bởi sự sẵn có của nguyên liệu thô (bảng, phụ kiện chất lượng cao) và thời gian hoạt động của máy móc chế biến chúng. Mỗi tủ yêu cầu 5 m2 ván, đối với bàn - 2 m2. Các phụ kiện với giá 10 đô la được chi cho một tủ và 8 đô la trên một bàn. Công ty có thể nhận từ các nhà cung cấp của mình tới 600 m2 ván mỗi tháng và các phụ kiện với giá 2000 đô la. Đối với mỗi tủ cần 7 giờ làm việc của máy, đối với bàn là 3 giờ. Chỉ cần 840 giờ vận hành máy mỗi tháng là có thể sử dụng được.

Một công ty nên sản xuất bao nhiêu tủ kết hợp và bàn máy tính mỗi tháng để tối đa hóa lợi nhuận nếu một tủ mang lại 100 đô la và mỗi bàn kiếm được 50 đô la?

• 1. Soạn một mô hình toán học của bài toán và giải nó bằng phương pháp simplex.
• 2. Soạn một mô hình toán học của bài toán đối ngẫu, viết ra lời giải của nó dựa trên lời giải của bài toán ban đầu.
• 3. Xác định mức độ khan hiếm của các nguồn lực được sử dụng và biện minh cho lợi nhuận của phương án tối ưu.
• 4. Khám phá các khả năng tăng sản lượng hơn nữa, tùy thuộc vào việc sử dụng từng loại tài nguyên.
• 5. Đánh giá tính khả thi của việc giới thiệu một loại sản phẩm mới - giá sách, nếu 1 m 2 bo mạch và phụ kiện với giá 5 đô la được chi cho việc sản xuất một kệ và cần 0,25 giờ vận hành máy và lợi nhuận từ việc bán một kệ là 20 đô la.
• 1. Hãy xây dựng một mô hình toán học cho bài toán này:

Biểu thị bằng x 1 - khối lượng sản xuất tủ và x 2 - khối lượng sản xuất bàn. Hãy để chúng tôi soạn một hệ thống các ràng buộc và một hàm mục tiêu:

Chúng tôi giải quyết vấn đề bằng cách sử dụng phương pháp simplex. Hãy viết nó ở dạng chuẩn:

Hãy viết dữ liệu nhiệm vụ dưới dạng một bảng:

Bảng 1

Tại vì bây giờ mọi thứ là đồng bằng Trên không, thì việc tăng thêm giá trị của hàm mục tiêu f là không thể và chúng ta đã thu được một phương án tối ưu.

Nếu chỉ có một yếu tố hạn chế (ví dụ: máy khan hiếm), có thể tìm ra giải pháp bằng cách sử dụng công thức đơn giản(xem link ở đầu bài viết). Nếu có một số yếu tố hạn chế, phương pháp lập trình tuyến tính được sử dụng.

Lập trình tuyến tính là tên được đặt cho một tổ hợp các công cụ được sử dụng trong khoa học quản lý. Phương pháp này giải quyết vấn đề phân bổ các nguồn lực khan hiếm giữa các hoạt động cạnh tranh nhằm tối đa hóa hoặc giảm thiểu một số giá trị số, chẳng hạn như lợi nhuận hoặc chi phí biên. Trong kinh doanh, nó có thể được sử dụng trong các lĩnh vực như lập kế hoạch sản xuất để tối đa hóa lợi nhuận, lựa chọn các bộ phận để giảm thiểu chi phí, lựa chọn danh mục đầu tư để tối đa hóa lợi nhuận, tối ưu hóa vận chuyển hàng hóa để giảm khoảng cách, bố trí nhân viên để tối đa hóa hiệu quả công việc và lập kế hoạch công việc trong để tiết kiệm thời gian.

Tải xuống ghi chú ở định dạng bản vẽ

Lập trình tuyến tính liên quan đến việc xây dựng một mô hình toán học của vấn đề đang được xem xét. Sau đó, giải pháp có thể được tìm thấy bằng đồ thị (thảo luận bên dưới), với sử dụng Excel(được xem xét riêng) hoặc các chương trình máy tính chuyên dụng.

Có lẽ việc xây dựng mô hình toán học là nhất phần khó lập trình tuyến tính, yêu cầu chuyển vấn đề đang được xem xét thành một hệ thống các biến, phương trình và bất phương trình - một quá trình cuối cùng phụ thuộc vào kỹ năng, kinh nghiệm, khả năng và trực giác của người biên dịch mô hình.

Hãy xem xét một ví dụ về việc xây dựng một mô hình toán học của lập trình tuyến tính

Nikolai Kuznetsov quản lý một nhà máy cơ khí. Vào tháng tới, anh ta dự định sản xuất hai sản phẩm (A và B), với lợi nhuận cận biên cụ thể ước tính lần lượt là 2.500 và 3.500 rúp.

Việc sản xuất cả hai sản phẩm đều đòi hỏi chi phí gia công, nguyên liệu thô và nhân công (Hình 1). Để sản xuất mỗi đơn vị sản phẩm A, người ta phân bổ 3 giờ gia công bằng máy, 16 đơn vị nguyên liệu thô và 6 đơn vị lao động. Các yêu cầu tương ứng đối với đơn vị B là 10, 4 và 6. Nikolai dự đoán rằng tháng tới anh ta có thể cung cấp 330 giờ gia công, 400 đơn vị nguyên liệu thô và 240 đơn vị lao động. Công nghệ của quá trình sản xuất sao cho ít nhất 12 đơn vị sản phẩm B phải được sản xuất trong một tháng nhất định.

Cơm. 1. Sử dụng và cung cấp các nguồn lực

Nikolay muốn xây dựng một mô hình để xác định số lượng đơn vị sản phẩm A và B mà anh ta phải sản xuất trong tháng tới để tối đa hóa lợi nhuận cận biên.

Mô hình tuyến tính có thể được xây dựng theo bốn bước.

Giai đoạn 1. Định nghĩa các biến

Có một biến mục tiêu (giả sử là Z) cần được tối ưu hóa, tức là tối đa hóa hoặc tối thiểu hóa (ví dụ: lợi nhuận, doanh thu hoặc chi phí). Nikolay tìm cách tối đa hóa lợi nhuận cận biên, do đó, biến mục tiêu là:

Z = tổng lợi nhuận cận biên (tính bằng rúp) nhận được trong tháng tới do sản xuất sản phẩm A và B.

Có một số biến chưa biết chưa biết (chúng tôi ký hiệu là x 1, x 2, x 3, v.v.), các giá trị của chúng phải được xác định để có được giá trị tối ưu của hàm mục tiêu, trong trường hợp của chúng tôi, là tổng lợi nhuận cận biên. Biên đóng góp này phụ thuộc vào số lượng sản phẩm A và B. Sản xuất ra, các giá trị này cần được tính toán và do đó là các biến quan tâm trong mô hình. Vì vậy, hãy biểu thị:

x 1 = số đơn vị sản phẩm A được sản xuất trong tháng tiếp theo.

x 2 = số đơn vị sản phẩm B được sản xuất trong tháng tiếp theo.

Điều rất quan trọng là phải xác định rõ ràng tất cả biến; Đặc biệt chú ý chú ý đến các đơn vị đo lường và khoảng thời gian mà các biến tham chiếu.

Sân khấu. 2. Xây dựng hàm mục tiêu

Hàm mục tiêu là một phương trình tuyến tính phải cực đại hoặc cực tiểu. Nó chứa biến mục tiêu được biểu thị dưới dạng các biến mong muốn, tức là Z được biểu thị dưới dạng x 1, x 2 ... dưới dạng một phương trình tuyến tính.

Trong ví dụ của chúng tôi, mỗi sản phẩm được sản xuất A mang lại 2500 rúp. lợi nhuận cận biên, và khi sản xuất x 1 đơn vị sản phẩm A, lợi nhuận cận biên sẽ là 2500 * x 1. Tương tự, lợi nhuận cận biên từ việc sản xuất x 2 đơn vị sản phẩm B sẽ là 3500 * x 2. Như vậy, tổng lợi nhuận cận biên nhận được trong tháng tới do sản xuất x 1 đơn vị sản phẩm A và x 2 đơn vị sản phẩm B, tức là biến mục tiêu Z sẽ là:

Z = 2500 * x 1 + 3500 * x 2

Nikolay tìm cách tối đa hóa chỉ số này. Do đó, hàm mục tiêu trong mô hình của chúng tôi là:

Tối đa hóa Z = 2500 * x 1 + 3500 * x 2

Sân khấu. 3. Định nghĩa các hạn chế

Ràng buộc là một hệ thống Các phương trình tuyến tính và / hoặc các bất đẳng thức giới hạn độ lớn của các biến được yêu cầu. Chúng phản ánh một cách toán học sự sẵn có của các nguồn lực, các yếu tố công nghệ, các điều kiện tiếp thị và các yêu cầu khác. Các ràng buộc có thể có ba loại: "nhỏ hơn hoặc bằng", "lớn hơn hoặc bằng", "hoàn toàn bằng".

Trong ví dụ của chúng tôi, các sản phẩm A và B yêu cầu thời gian chế biến, nguyên liệu thô và lao động để sản xuất, và sự sẵn có của các nguồn lực này bị hạn chế. Do đó, khối lượng sản xuất của hai sản phẩm này (tức là x 1 trong 2 giá trị) sẽ bị hạn chế do lượng tài nguyên cần thiết trong quá trình sản xuất không thể vượt quá những gì hiện có. Xem xét tình hình với thời gian xử lý của máy. Để sản xuất mỗi đơn vị sản phẩm A cần ba giờ gia công bằng máy, và nếu x 1 đơn vị được sản xuất thì tài nguyên này sẽ tiêu tốn 3 * x 1 giờ. Sản xuất mỗi đơn vị sản phẩm B cần 10 giờ và do đó, nếu sản xuất x 2 sản phẩm thì cần 10 * x 2 giờ. Như vậy, tổng thời gian máy cần thiết để sản xuất x 1 đơn vị sản phẩm A và x 2 đơn vị sản phẩm B là 3 * x 1 + 10 * x 2. nó Nghĩa tổng quát thời gian máy không được quá 330 giờ. Về mặt toán học, điều này được viết như sau:

3 * x 1 + 10 * x 2 ≤ 330

Các cân nhắc tương tự cũng được áp dụng đối với nguyên liệu thô và lao động, cho phép ghi thêm hai hạn chế:

16 * x 1 + 4 * x 2 ≤ 400

6 * x 1 + 6 * x 2 ≤ 240

Cuối cùng, cần lưu ý rằng có một điều kiện theo đó ít nhất 12 đơn vị sản phẩm B phải được sản xuất:

Giai đoạn 4. Viết các điều kiện của không tiêu cực

Các biến mong muốn không được là số âm, các biến này phải được viết dưới dạng bất đẳng thức x 1 ≥ 0 và x 2 ≥ 0. Trong ví dụ của chúng ta, điều kiện thứ hai là dư thừa, vì nó đã được xác định ở trên rằng x 2 không thể nhỏ hơn 12.

Hoàn thành mô hình lập trình tuyến tính cho nhiệm vụ sản xuất Nicholas có thể được viết là:

Tối đa hóa: Z = 2500 * x 1 + 3500 * x 2

Với điều kiện: 3 * x 1 + 10 * x 2 ≤ 330

16 * x 1 + 4 * x 2 ≤ 400

6 * x 1 + 6 * x 2 ≤ 240

Hãy xem xét một phương pháp đồ họa để giải một bài toán lập trình tuyến tính.

Phương pháp này chỉ thích hợp cho các bài toán có hai biến bắt buộc. Mô hình được xây dựng ở trên sẽ được sử dụng để chứng minh phương pháp.

Các trục trên đồ thị đại diện cho hai biến chưa biết (Hình 2). Không quan trọng biến nào được vẽ theo trục nào. Điều quan trọng là chọn một quy mô cuối cùng sẽ cho phép bạn xây dựng sơ đồ trực quan. Vì cả hai biến phải không âm, nên chỉ có góc phần tư thứ nhất được vẽ.

Cơm. 2. Trục đồ thị lập trình tuyến tính

Ví dụ, hãy xem xét ràng buộc đầu tiên: 3 * x 1 + 10 * x 2 ≤ 330. Bất đẳng thức này mô tả diện tích bên dưới đường: 3 * x 1 + 10 * x 2 = 330. Đường này giao với trục x 1 tại x 2 \ u003d 0, tức là, phương trình trông giống như sau: 3 * x 1 + 10 * 0 \ u003d 330 và nghiệm của nó: x 1 \ u003d 330/3 \ u003d 110

Tương tự, chúng ta tính các giao điểm với các trục x 1 và x 2 cho tất cả các điều kiện ràng buộc:

Phạm vi chấp nhận được	Giới hạn giá trị cho phép	Giao lộ với trục x 1	Giao lộ với trục x 2
3 * x 1 + 10 * x 2 ≤ 330	3 * x 1 + 10 * x 2 = 330	x 1 = 110; x 2 = 0	x 1 = 0; x 2 = 33
16 * x 1 + 4 * x 2 ≤ 400	16 * x 1 + 4 * x 2 = 400	x 1 = 25; x 2 = 0	x 1 = 0; x 2 = 100
6 * x 1 + 6 * x 2 ≤ 240	6 * x 1 + 6 * x 2 = 240	x 1 = 40; x 2 = 0	x 1 = 0; x 2 = 40
x 2 ≥ 12	x 2 = 12	không vượt qua; chạy song song với trục x 1	x 1 = 0; x 2 = 12

Về mặt đồ họa, hạn chế đầu tiên được thể hiện trong Hình. 3.

Cơm. 3. Xây dựng miền các giải pháp khả thi cho hạn chế đầu tiên

Bất kỳ điểm nào trong tam giác đã chọn hoặc trên các đường viền của nó sẽ tuân theo ràng buộc này. Các điểm như vậy được gọi là hợp lệ, và các điểm bên ngoài tam giác được gọi là không hợp lệ.

Tương tự, chúng tôi phản ánh phần còn lại của các hạn chế trên biểu đồ (Hình 4). Giá trị x 1 và x 2 trên hoặc bên trong vùng bóng mờ ABCDE sẽ tuân thủ tất cả các ràng buộc của mô hình. Một vùng như vậy được gọi là vùng của các giải pháp có thể chấp nhận được.

Cơm. 4. Lĩnh vực của các giải pháp khả thi cho toàn bộ mô hình

Bây giờ, trong lĩnh vực của các giải pháp khả thi, cần phải xác định các giá trị x 1 và x 2 lớn nhất Z. Để làm điều này, trong phương trình hàm mục tiêu:

Z = 2500 * x 1 + 3500 * x 2

chúng ta chia (hoặc nhân) các hệ số trước x 1 và x 2 cho cùng một số, để các giá trị thu được rơi vào phạm vi được hiển thị trên đồ thị; trong trường hợp của chúng tôi, phạm vi như vậy là từ 0 đến 120; vì vậy các hệ số có thể được chia cho 100 (hoặc 50):

Z = 25x 1 + 35x 2

sau đó gán giá trị Z ngang bằng với sản phẩm hệ số trước x 1 và x 2 (25 * 35 = 875):

875 = 25x 1 + 35x 2

và cuối cùng, tìm giao điểm của đường thẳng với các trục x 1 và x 2:

Hãy vẽ phương trình mục tiêu này trên biểu đồ theo cách tương tự như các ràng buộc (Hình 5):

Cơm. 5. Ứng dụng của hàm mục tiêu (đường chấm đen) vào lĩnh vực các giải pháp khả thi

Giá trị Z không đổi trong suốt đường hàm mục tiêu. Để tìm các giá trị x 1 và x 2 có giá trị cực đại Z, bạn cần chuyển song song đường thẳng của hàm mục tiêu đến một điểm nằm trong ranh giới của vùng nghiệm thu, điểm này nằm ở cực đại khoảng cách từ dòng ban đầu của hàm mục tiêu lên và sang phải, nghĩa là, đến điểm C (Hình 6).

Cơm. 6. Đường của hàm mục tiêu đạt cực đại trong vùng các giải pháp khả thi (tại điểm C)

Có thể kết luận rằng giải pháp tối ưu sẽ nằm ở một trong những điểm cực trị của vùng quyết định. Trong đó, nó sẽ phụ thuộc vào hệ số góc của hàm mục tiêu và vấn đề mà chúng ta đang giải quyết: tối đa hóa hay tối thiểu hóa. Do đó, không cần thiết phải vẽ một hàm mục tiêu - tất cả những gì cần thiết là xác định các giá trị của x 1 và x 2 tại mỗi điểm cực trị bằng cách đọc từ sơ đồ hoặc bằng cách giải các cặp phương trình tương ứng. Các giá trị tìm được của x 1 và x 2 sau đó được thay vào hàm mục tiêu để tính giá trị tương ứng của Z. Phương án tối ưu là phương án mà tại đó giá trị lớn nhất của Z đạt được khi giải bài toán cực đại và cực tiểu khi giải bài toán tối thiểu hóa.

Ví dụ, chúng ta hãy xác định giá trị của x 1 và x 2 tại điểm C. Lưu ý rằng điểm C nằm ở giao điểm của các đường: 3x 1 + 10x 2 = 330 và 6x 1 + 6x 2 = 240. nghiệm của hệ phương trình này cho: x 1 = 10, x 2 = 30. Kết quả tính tất cả các đỉnh của diện tích các nghiệm khả thi được cho trong bảng:

Chấm	Giá trị x 1	Giá trị x 2	Z \ u003d 2500x 1 + 3500x 2
NHƯNG	22	12	97 000
TẠI	20	20	120 000
TỪ	10	30	130 000
D	0	33	115 500
E	0	12	42 000

Vì vậy, Nikolai Kuznetsom phải lên kế hoạch sản xuất 10 mặt hàng A và 30 mặt hàng B cho tháng tới, điều này sẽ cho phép anh ta nhận được lợi nhuận cận biên là 130 nghìn rúp.

Tóm lại, bản chất của phương pháp đồ họa để giải các bài toán lập trình tuyến tính có thể được tóm tắt như sau:

1. Vẽ hai trục trên biểu đồ biểu diễn hai tham số quyết định; chỉ vẽ góc phần tư thứ nhất.
2. Xác định tọa độ của các giao điểm của tất cả các điều kiện biên với các trục, lần lượt thay các giá trị x 1 = 0 và x 2 = 0 vào phương trình của các điều kiện biên.
3. Vẽ các đường ràng buộc của mô hình trên biểu đồ.
4. Xác định khu vực trên đồ thị (được gọi là khu vực quyết định cho phép) đáp ứng tất cả các ràng buộc. Nếu không có vùng đó, thì mô hình không có giải pháp.
5. Xác định giá trị của các biến bắt buộc trong điểm cực đoan miền quyết định, và trong mỗi trường hợp, hãy tính giá trị tương ứng của biến mục tiêu Z.
6. Đối với các bài toán cực đại, nghiệm là điểm tại đó Z là cực đại; đối với các bài toán cực tiểu, nghiệm là điểm tại đó Z là cực tiểu.

CHỦ ĐỀ: LẬP TRÌNH TUYẾN TÍNH

NHIỆM VỤ 2.A. Giải bài toán lập trình tuyến tính bằng phương pháp đồ họa

Chú ý!

Đây là PHIÊN BẢN GIỚI THIỆU của tác phẩm số 2073, giá của bản gốc là 200 rúp. Đóng khung trong Chương trình của Microsoft từ.

Thanh toán. Liên lạc.

Tùy chọn 7. Tìm giá trị lớn nhất và nhỏ nhấthàm tuyến tính Ф \ u003d 2x 1 - 2 x 2với các giới hạn: x 1 + x 2 ≥ 4;

- x 1 + 2 x 2 ≤ 2;

x 1 + 2 x 2 ≤ 10;

x i ≥ 0, i = 1,2.

Dung dịch:

Thay dấu của bất phương trình có điều kiện bằng dấu bằng, ta được hệ phương trình x1 + x2 = 4;

- x1 + 2 x2 = 2;

x1 + 2 x2 = 10.

Ta dựng các đường thẳng theo các đẳng thức này, sau đó, theo các dấu hiệu của bất đẳng thức, ta chọn các nửa mặt phẳng và thu được phần chung của chúng - miền nghiệm của ODE - tứ giác MNPQ.

Giá trị nhỏ nhất của hàm

tsii - tại điểm M (2; 2)

Ф min = 2 2 - 2 2 = 0.

Giá trị lớn nhất đạt được tại điểm N (10; 0),

Ф max \ u003d 2 10 - 2 0 \ u003d 20.

Tùy chọn 8. Tìm giá trị lớn nhất và nhỏ nhất

hàm tuyến tính Ф \ u003d x 1 + x 2

với các giới hạn: x 1 - 4 x 2 - 4 ≤ 0;

3 x 1 - x 2 ≥ 0;

x 1 + x 2 - 4 ≥ 0;

x i ≥ 0, i = 1,2.

Dung dịch:

Thay dấu của bất phương trình có điều kiện bằng dấu bằng ta được hệ phương trình x1 - 4 x2 = 4;

3 x1 - x2 = 0;

Chúng ta dựng các đường thẳng theo các phương trình này, sau đó, theo các dấu hiệu của bất đẳng thức, chúng ta chọn các nửa mặt phẳng và thu được phần chung của chúng - miền nghiệm của ODE - một đa giác không giới hạn MNPQ.

Giá trị nhỏ nhất của hàm

tions - trên một đường thẳng NP, chẳng hạn

tại điểm Р (4; 0)

Ф min = 4 + 0 = 4.

ODE không bị giới hạn từ phía trên, do đó, Ф max = + ∞.

Tùy chọn 10. Tìm giá trị lớn nhất và nhỏ nhất

hàm tuyến tính Ф \ u003d 2 x 1 - 3 x 2

với các hạn chế: x 1 + 3 x 2 ≤ 18;

2 x 1 + x 2 ≤ 16;

x 2 ≤ 5;

x i ≥ 0, i = 1,2.

Thay dấu của bất đẳng thức có điều kiện bằng dấu bằng, ta được một hệ phương trình

x 1 + 3 x 2 = 18 (1);

2 x 1 + x 2 = 16 (2);

3 x 1 = 21 (4).

Ta dựng các đường thẳng theo các phương trình này, sau đó, theo các dấu hiệu của bất đẳng thức, ta chọn các nửa mặt phẳng và thu được phần chung của chúng - miền nghiệm của ODE - của đa giác MNPQRS.

Ta dựng vectơ Г (2; -3) và vẽ qua gốc tọa độ dòng cấp- dài.

Chúng tôi di chuyển đường mức theo hướng, trong khi giá trị của F tăng lên. Tại điểm S (7; 0), hàm mục tiêu đạt cực đại Ф max = 2 · 7–3 · 0 = = 14. Ta di chuyển đường mức có hướng thì giá trị của Ф giảm. Giá trị nhỏ nhất của hàm số tại điểm N (0; 5)

Ф min = 2 0 - 3 5 = –15.

NHIỆM VỤ 2.B. Giải bài toán lập trình tuyến tính

phương pháp phân tích đơn giản

Phương án 7. Thu nhỏ hàm mục tiêu Ф \ u003d x 1 - x 2 + x 3 + x 4 + x 5 - x 6

theo giới hạn: x 1 + x 4 +6 x 6 = 9,

3 x 1 + x 2 - 4 x 3 + 2 x 6 \ u003d 2,

x 1 + 2 x 3 + x 5 + 2 x 6 = 6.

Dung dịch:

Số ẩn số n = 6, số phương trình m = 3. Do đó, r = n-m = 3 ẩn số có thể được coi là tự do. Hãy chọn x 1, x 3 và x 6.

Chúng tôi biểu diễn các biến cơ bản x 2, x 4 và x 5 dưới dạng các biến tự do và đưa hệ thống về cơ sở đơn vị

x 2 \ u003d 2 - 3 x 1 + 4 x 3 - 2 x 6

x 4 \ u003d 9 - x 1 - 6 x 6 (*)

x 5 \ u003d 6 - x 1 - 2 x 3 - 2 x 6

Hàm mục tiêu sẽ giống như sau:

Ф \ u003d x 1 - 2 + 3 x 1 - 4 x 3 + 2 x 6 + x 3 + 9 - x 1 - 6 x 6 +6 - x 1 - 2 x 3 - 2 x 6 - x 6 =

13 + 2 x 1 - 5 x 3 - 7 x 6

Hãy đặt x 1 \ u003d x 3 \ u003d x 6 \ u003d 0, trong khi các biến cơ bản sẽ nhận các giá trị x 2 \ u003d 2; x 4 \ u003d 9; x 5 \ u003d 6, nghĩa là, nghiệm khả thi đầu tiên (0; 2; 0; 9; 6; 0), hàm mục tiêu Ф 1 \ u003d 13.

Các biến x 3 và x 6 được bao gồm trong hàm mục tiêu với hệ số âm, do đó, khi giá trị của chúng tăng lên, giá trị của Ф sẽ giảm. Lấy ví dụ, x 6. Từ phương trình thứ nhất của hệ (*) có thể thấy rằng giá trị của x 6 có thể tăng lên đến x 6 \ u003d 1 (miễn là x 2 ³ 0). Trong trường hợp này, x 1 và x 3 giữ nguyên các giá trị bằng không. Bây giờ, là các biến cơ bản, chúng ta lấy x 4, x 5, x 6, miễn phí - x 1, x 2, x 3. Hãy để chúng tôi diễn đạt các biến cơ bản mới theo các biến miễn phí mới. Lấy

x 6 \ u003d 1 - 3/2 x 1 - 1/2 x 2 + 2 x 3

x 4 \ u003d 3 + 8 x 1 + 3 x 2 - 12 x 3

x 5 \ u003d 4 + 2 x 1 + x 2 - 6 x 3

Ф \ u003d 6 + 25/2 x 1 + 7/2 x 2 - 19 x 3

Gán cho các biến tự do giá trị null, nghĩa là, x 1 \ u003d x 2 \ u003d x 3 \ u003d 0, trong khi x 6 \ u003d 1, x 4 \ u003d 3, x 5 \ u003d 4, tức là nghiệm hợp lệ thứ ba (0; 0; 0 ; 3; 4; 1). Trong trường hợp này, Ф 3 \ u003d 6.

Biến x 3 được bao gồm trong hàm mục tiêu với hệ số âm, do đó, tăng x 3 so với 0 sẽ dẫn đến giảm F. Từ phương trình thứ 2 có thể thấy rằng x 3 có thể tăng lên đến 1 / 4, từ phương trình thứ 3 - lên đến 2/3. Phương trình thứ hai quan trọng hơn. Ta chuyển biến x 3 thành số biến cơ bản, x 4 thành số biến tự do.

Bây giờ chúng ta lấy x 1, x 2 và x 4 là các biến miễn phí mới. Hãy biểu diễn các biến cơ bản mới x 3, x 5, x 6 dưới dạng chúng. Hãy lấy hệ thống

x 3 \ u003d 1/4 + 2/3 x 1 + 1/4 x 2 - 1/12 x 4

x 5 \ u003d 5/2 - 2 x 1 - 1/2 x 2 + 1/2 x 4

x 6 \ u003d 3/2 - 1/6 x 1 - 1/6 x 4

Hàm mục tiêu sẽ có dạng

Ф \ u003d 5/4 - 1/6 x 1 - 5/4 x 2 + 19/12 x 4

Các biến x 1 và x 2 được bao gồm trong hàm mục tiêu với hệ số âm, do đó, khi giá trị của chúng tăng lên, giá trị của Ф sẽ giảm. Lấy ví dụ, x 2. Từ phương trình thứ 2 của hệ, có thể thấy rằng giá trị của x 2 có thể tăng lên đến x 2 \ u003d 5 (miễn là x 5 ³ 0). Trong trường hợp này, x 1 và x 4 giữ nguyên giá trị 0, giá trị của các biến khác bằng x 3 = 3/2; x 5 \ u003d 0, x 6 \ u003d 3/2, tức là nghiệm hợp lệ thứ tư (0; 5; 3/2; 0; 0; 3/2). Trong trường hợp này, Ф 4 \ u003d 5/4.

Bây giờ chúng ta lấy x 1, x 4 và x 5 là các biến miễn phí mới. Hãy biểu diễn các biến cơ bản mới x 2, x 3, x 6 dưới dạng chúng. Hãy lấy hệ thống

x 2 \ u003d 5 - 4 x 1 + x 4 - 2 x 5

x 3 \ u003d 3/2 - 1/3 x 1 + 1/6 x 4 - 1/2 x 5

x 6 \ u003d 3/2 - 1/6 x 1 - 1/6 x 4

Hàm mục tiêu sẽ có dạng

F \ u003d - 5 + 29/6 x 1 + 1/3 x 4 + 5/2 x 5

Hệ số của cả hai biến trong biểu thức Ф đều dương, do đó, không thể giảm thêm giá trị của Ф.

Tức là giá trị nhỏ nhất của Ф min = - 5 thì nghiệm khả thi cuối cùng (0; 5; 3/2; 0; 0; 3/2) là tối ưu.

Phương án 8. Cực đại hàm mục tiêu Ф = 4 x 5 + 2 x 6

với các giới hạn: x 1 + x 5 + x 6 = 12;

x 2 + 5 x 5 - x 6 \ u003d 30;

x 3 + x 5 - 2 x 6 \ u003d 6;

2 x 4 + 3 x 5 - 2 x 6 \ u003d 18;

Dung dịch:

Số phương trình là 4, số ẩn số là 6. Do đó, r = n - m = 6 - 4 = 2 biến có thể được chọn là tự do, 4 biến là cơ bản. Chúng tôi chọn x 5 và x 6 là những cái miễn phí, x 1, x 2, x 3, x 4 là những cái cơ bản. Chúng tôi biểu diễn các biến cơ bản dưới dạng các biến số tự do và rút gọn hệ phương trình về cơ sở đơn vị

x 1 \ u003d 12 - x 5 - x 6;

x 2 \ u003d 30 - 5 x 5 + x 6;

x 3 \ u003d 6 - x 5 + 2 x 6;

x 4 \ u003d 9 - 3/2 x 5 + x 6;

Ta viết hàm mục tiêu dưới dạng Ф = 4 x 5 + 2 x 6. Chúng tôi gán giá trị 0 cho các biến tự do x 5 = x 6 = 0. Trong trường hợp này, các biến cơ bản sẽ nhận các giá trị x 1 = 12, x 2 = 30, x 3 = 6, x 4 = 9 , nghĩa là, chúng ta sẽ nhận được giải pháp khả thi đầu tiên (12, 30, 6, 9, 0,) và Ф 1 = 0.

Cả hai biến tự do đều nhập hàm mục tiêu với hệ số dương, nghĩa là có thể tăng thêm F. Ví dụ, hãy dịch x 6 thành số biến cơ bản. Phương trình (1) cho thấy x 1 = 0 tại x 5 = 12, trong (2) ÷ (4) x 6 nhập với hệ số dương. Hãy chuyển sang một cơ sở mới: các biến cơ bản - x 6, x 2, x 3, x 4, tự do - x 1, x 5. Hãy biểu diễn các biến cơ bản mới thông qua miễn phí mới

x 6 \ u003d 12 - x 1 - x 5;

x 2 \ u003d 42 - x 1 - 6 x 5;

x 3 \ u003d 30 - 2 x 1 - 3 x 5;

x 4 \ u003d 21 - x 1 - 5/2 x 5;

Hàm mục tiêu sẽ có dạng Ф = 24 - 2 x 1 + 2 x 5;

Chúng tôi gán giá trị 0 cho các biến tự do x 1 = x 5 = 0. Trong trường hợp này, các biến cơ bản sẽ nhận các giá trị x 6 = 12, x 2 = 42, x 3 = 30, x 4 = 21 nghĩa là, chúng ta sẽ thu được nghiệm khả thi thứ hai (0, 42, 30, 21, 0, 12) và Ф 2 = 24.

Hàm mục tiêu x 5 đi vào với hệ số dương, nghĩa là có thể tăng thêm F. Hãy chuyển sang cơ sở mới: các biến cơ bản - x 6, x 5, x 3, x 4, các biến tự do - x 1 , x 2. Hãy biểu diễn các biến cơ bản mới thông qua miễn phí mới

x 6 \ u003d 5 - 5/6 x 1 + 1/6 x 2;

x 5 \ u003d 7 - 1/6 x 1 - 1/6 x 2;

x 3 \ u003d 9 - 3/2 x 1 + 1/2 x 2;

x 4 \ u003d 7/2 - 7/12 x 1 + 5/12 x 5;

Hàm mục tiêu sẽ có dạng Ф = 38 - 7/2 x 1 - 1/3 x 2;

Gán các giá trị 0 x 1 = x 2 = 0 cho các biến tự do. Trong trường hợp này, các biến cơ bản sẽ nhận các giá trị x 6 = 5, x 5 = 7, x 3 = 9, x 4 = 7 / 2, tức là chúng ta sẽ nhận được nghiệm khả thi thứ ba là X 3 = (0, 0, 9, 7/2, 7, 5) và Ф 3 = 38.

Cả hai biến đều nhập hàm mục tiêu với hệ số âm, nghĩa là không thể tăng thêm Ф.

Do đó, giải pháp khả thi cuối cùng là tối ưu, đó là Х opt = (0, 0, 9, 7/2, 7, 5) và Ф max = 38.

Tùy chọn 10. Tối đa hóa hàm mục tiêu Ф \ u003d x 2 + x 3

theo các hạn chế: x 1 - x 2 + x 3 \ u003d 1,

x 2 - 2 x 3 + x 4 \ u003d 2.

Dung dịch:

Hệ phương trình - ràng buộc là nhất quán, vì bậc của ma trận của hệ phương trình và ma trận mở rộng là như nhau và bằng 2. Do đó, hai biến có thể được coi là tự do, hai biến khác - cơ bản - có thể là được thể hiện tuyến tính trong điều khoản của hai cái tự do.

Hãy coi x 2 và x 3 là các biến tự do. Khi đó, các biến x 1 và x 2 sẽ là các biến cơ bản, chúng ta sẽ biểu diễn dưới dạng miễn phí

x 1 \ u003d 1 + x 2 - x 3; (*)

x 4 \ u003d 2 - x 2 + 2 x 3;

Hàm mục tiêu đã được biểu diễn dưới dạng x 2 và x 3, tức là, Ф = x 2 + x 3.

Tại x 2 \ u003d 0 và x 3 \ u003d 0, các biến cơ bản sẽ bằng x 1 \ u003d 1, x 4 \ u003d 2.

Ta có nghiệm khả thi đầu tiên X 1 = (1, 0, 0, 2), trong khi Ф 1 = 0.

Có thể tăng Ф khi tăng, ví dụ, giá trị của x 3, giá trị này được đưa vào biểu thức cho Ф với hệ số dương (x 2 vẫn bằng 0). Trong phương trình đầu tiên của hệ (*), có thể thấy rằng x 3 có thể được tăng lên 1 (từ điều kiện x 1 ³0), tức là, phương trình này áp dụng một hạn chế về việc tăng giá trị của x 3. Phương trình đầu tiên của hệ thống (*) đang giải quyết. Trên cơ sở của phương trình này, chúng tôi chuyển sang một cơ sở mới, thay đổi x 1 và x 3 vị trí. Bây giờ các biến cơ bản sẽ là x 3 và x 4, tự do - x 1 và x 2. Bây giờ chúng ta biểu diễn x 3 và x 4 dưới dạng x 1 và x 2.

Ta nhận được: x 3 \ u003d 1 - x 1 + x 2; (**)

x 4 \ u003d 4 - 2 x 1 + x 2;

Ф \ u003d x 2 + 1 - x 1 + x 2 \ u003d 1 - x 1 + 2 x 2

Cân bằng các biến tự do bằng 0, ta thu được nghiệm cơ bản thứ hai X 2 = (0; 0; 1; 4), trong đó Ф 2 = 1.

Có thể tăng F khi tăng x 2. Độ phóng đại giống nhau x 2, đánh giá bằng hệ thống mới nhất phương trình (**), không giới hạn. Do đó, Ф sẽ lấy tất cả các giá trị tích cực, nghĩa là, Ф max = + ¥.

Vì vậy, hàm mục tiêu Ф không có giới hạn từ trên nên không có giải pháp tối ưu.

NHIỆM VỤ 2.D. Viết một bài toán kép cho một bài toán đã cho.

vấn đề ban đầu.

Phương án 7. Cực đại hàm mục tiêu Ф = 2× x 1 - x 4

với các hạn chế: x 1 + x 2 \ u003d 20,

x 2 + 2× x 4 ≥ 5,

x 1 + x 2 + x 3 ≤ 8,

x i ≥ 0 (i = 1, 2, 3, 4)

Dung dịch:

Chúng tôi đưa hệ thống các ràng buộc về một dạng duy nhất, ví dụ, dạng chuẩn bằng cách đưa các biến bổ sung vào các phương trình thứ 2 và thứ 3

x 1 + x 2 = 20,

x 2 + 2 × x 4 - x 5 \ u003d 5,

- x 1 + x 2 + x 3 + x 6 \ u003d 8.

Chúng tôi có một vấn đề bất đối xứng của loại thứ hai. Vấn đề kép sẽ giống như sau:

Giảm thiểu hàm mục tiêu F = 20 × y 1 + 5 × y 2 + 8 × y 3

cho y 1 - y 3 ≥ 2,

y1 + y2 + y3 ≥ 0,

y 3 ≥ 0,

2× y2 ≥ 1,

Y2 ≥ 0,

y 3 ≥ 0.

Tùy chọn 8. Tối đa hóa hàm mục tiêu Ф \ u003d x 2 - x 4 - 3× x 5

với các hạn chế: x 1 + 2× x 2 - x 4 + x 5 \ u003d 1,

— 4 × x 2 + x 3 + 2× x 4 - x 5 = 2,

3 × x 2 + x 5 + x 6 = 5,

x tôi ≥ 0, (tôi = 1, 6)

Dung dịch:

Ta có bài toán cực đại ban đầu với hệ thống các ràng buộc ở dạng phương trình, tức là một cặp bài toán đối ngẫu có dạng bất đối xứng thuộc loại 2, mô hình toán học mà ở dạng ma trận có dạng:

Sự cố ban đầu: Sự cố kép:

F = C × X tối đa F = B T × Ymin

tại A × X \ u003d B tại A T × Y ≥ C T

Trong bài toán ban đầu, ma trận-hàng hệ số cho các biến trong hàm mục tiêu có dạng С = (0; 1; 0; -1; -3; 0),

ma trận cột của các số hạng tự do và ma trận hệ số cho các biến trong hệ thống ràng buộc có dạng

B \ u003d 2, A \ u003d 0 - 4 1 2 -1 0

Tìm ma trận chuyển vị của các hệ số, ma trận-hàng hệ số cho các biến trong hàm mục tiêu và cột ma trận gồm các phần tử tự do

0 1 0 0 V T \ u003d (1; 2; 5)

A T = -1 2 0 C T = -1

Bài toán kép có thể được viết dưới dạng sau:

tìm giá trị nhỏ nhất của hàm mục tiêu F = y 1 + 2 × y 2 + 5 × y 3

dưới các hạn chế y 1 ≥ 0,

2× y 1-4 × y 2 + 3 × y 3 ≥ 1,

- y 1 + 2 × y 2 ≥ -1,

y 1 - y 2 + y 3 ≥ -3,

Phương án 10. Cực tiểu hàm Ф = x 1 + x 2 + x 3

giới hạn: 3× x 1 + 9× x 2 + 7× x 3 ≥ 2,

6 × x 1 + 4 x 2 + 5× x 3 ≥ 3,

8 × x 1 + 2 x 2 + 4× x 3 ≥ 4,

Dung dịch:

Ta có bài toán cực tiểu ban đầu với hệ thống các ràng buộc ở dạng bất phương trình, tức là một cặp bài toán đối ngẫu có dạng đối xứng loại 3, mô hình toán mà ở dạng ma trận có dạng:

Vấn đề ban đầu Vấn đề kép

F = C × X phút F \ u003d B T × Ymax

tại A × X ≥ B tại A T × Y ≤ C T

X ≥ 0 Y ≥ 0

Trong bài toán ban đầu, ma trận-hàng hệ số cho các biến trong hàm mục tiêu, ma trận cột các số hạng tự do và ma trận hệ số cho các biến trong hệ thống ràng buộc có dạng

C \ u003d (1; 1; 1), B \ u003d 3, A \ u003d 6 4 5

Hãy để chúng tôi tìm ma trận của bài toán kép

B T = (2; 3; 4) C T = 3 A T = 9 4 2

Bài toán kép được xây dựng dưới dạng:

Cực đại hàm mục tiêu F = 2y 1 + 3y 2 + 4y 3

dưới các hạn chế 3 × y 1 + 6 × y 2 + 8 × y 3 ≤ 1,

9× y 1 + 4 × y 2 + 2 × y 3 ≤ 1,

7× y 1 + 5 × y 2 + 4 × y 3 ≤ 1,

y i ≥ 0 (i = 1, 2, 3)

NHIỆM VỤ 2.C. Giải một bài toán lập trình tuyến tính bằng cách sử dụng bảng simplex.

Phương án 7. Cực đại của hàm mục tiêu Ф = 2 x 1 - x 2 + 3 x 3 + 2 x 4

dưới các hạn chế: 2 x 1 + 3 x 2 - x 3 + 2 x 4 ≤ 4,

x 1 - 2 x 2 + 5 x 3 - 3 x 4 ≥ 1,

4 x 1 + 10 x 2 +3 x 3 + x 4 ≤ 8.

Dung dịch:

Chúng tôi giảm bớt hệ thống ràng buộc xuống dạng chuẩn

2 x 1 + 3 x 2 - x 3 + 2 x 4 + z 1 = 4, (1)

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1, (2)

4 x 1 + 10 x 2 +3 x 3 + x 4 + z 3 = 8. (3)

Ta có hệ 3 phương trình với 7 ẩn số. Ta chọn x 1, z 1, z 3 làm 3 biến cơ bản, x 2, x 3, x 4, z 2 là biến tự do, ta biểu diễn các biến cơ bản thông qua chúng.

Từ (2) ta có x 1 = 1 + 2 x 2 - 5 x 3 + 3 x 4 + x 6

Thay thế ở (1) và (3), chúng tôi nhận được

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 \ u003d 1,

z 1 + 7 x 2 - 11 x 3 + 8 x 4 + 2 z 2 = 2,

z 3 + 18 x 2 - 17 x 3 + 13 x 4 + 4 z 2 = 4,

Ф - 3 x 2 + 7 x 3 - 8 x 4 - 2 z 2 \ u003d 2.

Soạn một bảng đơn giản

Tôi lặp lại Bảng 1

Nền tảng AC	Sự tự do. AC
x 1	1	1	— 2	5	— 3	0	— 1	0		3/8
z1	2	0	7	-11		1	2	0	1/ 4	1/8
z3	4	0	18	-17	13	0	4	1	4/13	13/8
F	2	0	— 3	7	— 8	0	— 2	0		1

X 1 \ u003d (1; 0; 0; 0; 2; 0; 4) F 1 \ u003d 2.

II Bảng lặp 2

x 1	14/8	1	5/8	7/8	0	3/8	-2/8	0	2	— 1
x4	1/ 4	0	7/8	-11/8	1	1/8	2/8	0		11/7
z3	6/8	0	53/8		0	-13/8	6/8	1	6/7	8/7
F	4	0	4	— 4	0	1	0	0		32/7

X 2 \ u003d (14/8; 0; 0; 1/4; 0; 0; 4) Ф 2 \ u003d 4.

III lặp lại Bảng 3

x 1	1	1	— 6	0	0		-1	— 1		1/2
x4	10/ 7	0	79/7	0	1	-17/7	10/7	11/7		11/7
x 3	6/7	0	53/7	1	0	-13/7	6/7	8/7		13/14
F	52/7	0	240/7	0	0	-45/7	24/7	32/7		45/14

X 3 \ u003d (1; 0; 6/7; 10/7; 0; 0; 0) Ф 3 \ u003d 52/7.

IV lần lặp Bảng 4

z1	1/ 2	1/2	— 3	0	0	1	-1/2	-1/2
x4	37/ 14	17/14	56/14	0	1	0	3/14	5/14
x 3	25/14	13/14	28/14	1	0	0	-1/14	3/14
F	149/14	45/14	15	0	0	0	3/14	19/14

X 4 \ u003d (0; 0; 25/14; 37/14; 1/2; 0; 0) F 4 \ u003d 149/14.

Trong dòng chỉ mục bàn cuối cùng Không số âm, nghĩa là, trong biểu thức cho hàm mục tiêu, tất cả Г i< 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.

Trả lời: Ф max = 149/14,

giải pháp tối ưu (0; 0; 25/14; 37/14; 1/2; 0; 0)

Phương án 8. Cực tiểu hàm mục tiêu Ф = 5 x 1 - x 3

theo các hạn chế: x 1 + x 2 + 2 x 3 - x 4 \ u003d 3,

x 2 + 2 x 4 \ u003d 1,

Dung dịch:

Số biến là 4, hạng của ma trận là 2, do đó số biến tự do là r \ u003d 4 - 2 \ u003d 2, số biến cơ bản cũng là 2. Ta lấy x 3, x 4 là biến tự do, chúng ta sẽ biểu diễn các biến cơ bản x 1, x 2 dưới dạng tự do và chúng ta đưa hệ về cơ sở đơn vị:

x 2 \ u003d 1 - 2 x 4,

x 1 \ u003d 3 - x 2 - 2 x 3 + x 4 \ u003d 3 - 1 + 2 x 4 - 2 x 3 + x 4 \ u003d 2 - 2 x 3 + 3 x 4

Ф \ u003d 5 x 1 - x 3 \ u003d 5 (2 - 2 x 3 + 3 x 4) - x 3 \ u003d 10 - 10 x 3 + 15 x 4 - x 3 \ u003d 10 - 11 x 3 + 15 x 4

Chúng ta viết hệ phương trình và hàm mục tiêu dưới dạng thuận tiện cho bảng đơn giản, nghĩa là x 2 + 2 x 4 = 1,

x 1 +2 x 3 - 3 x 4 = 2

Ф + 11 x 3 - 15 x 4 \ u003d 10

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

Tôi lặp lại Bảng 1

Nền tảng AC	Sự tự do. AC
x1	2	1	0		— 3		1/2
x2	1	0	1	0	2
F	10	0	0	11	— 15		— 11/2

X 1 \ u003d (2; 1; 0; 0) F 1 \ u003d 10.

II Bảng lặp 2

x3	1	1/2	0	1	-3/2		3/4
x2	1	0	1	0			1/2
F	— 1	— 11/2	0	0	3/2		— 3/4

X 2 \ u003d (0; 1; 1; 0) F 2 \ u003d -1.

III lặp lại Bảng 3

x3	7/4	1/2	3/4	1	0
x4	1/2	0	1/2	0	1
F	— 7/4	— 11/2	— 3/4	0	0

X 3 \ u003d (0; 0; 7/4; 1/2) F 3 \ u003d -7/4.

Không có bảng cuối cùng trong hàng chỉ mục số dương, nghĩa là, trong biểu thức cho hàm mục tiêu, mọi Г i> 0. Ta có trường hợp I, do đó, giải pháp cơ bản cuối cùng là tối ưu.

Đáp số: Ф min = -7/4, nghiệm tối ưu (0; 0; 7/4; 1/2)

********************

Tùy chọn 10. Thu nhỏ hàm mục tiêu Ф \ u003d x 1 + x 2,

với các hạn chế: x 1 -2 x 3 + x 4 \ u003d 2,

x 2 - x 3 + 2 x 4 \ u003d 1,

Dung dịch:

Số biến là 5, hạng của ma trận là 3, do đó số biến tự do là r \ u003d 6-3 \ u003d 2. Ta lấy x 3 và x 4 là biến tự do, x 1, x 2, x 5 như những cái cơ bản. Tất cả các phương trình của hệ thống đã được rút gọn thành một cơ sở duy nhất (các biến cơ bản được biểu thị dưới dạng các biến tự do), nhưng chúng được viết ở dạng không thuận tiện cho việc sử dụng bảng đơn giản. Ta viết hệ phương trình dưới dạng

x 1 - 2 x 3 + x 4 \ u003d 2

x 2 - x 3 +2 x 4 \ u003d 1

x 5 + x 3 - x 4. = 5

Chúng ta biểu diễn hàm mục tiêu dưới dạng các biến tự do và viết nó dưới dạng Ф - 3 x 3 +3 x 4 = 3

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

Tôi lặp lại Bảng 1

Nền tảng AC	Sự tự do. AC
x 1	2	1	0	-2	1	0	2	-1/2
x 2	1	0	1	-1		0	1/2	1/2
x 5	5	0	0	1	-1	1		1/2
F	3	0	0	-3	3	0		-3/2

X 1 \ u003d (2; 3; 0; 0; 5) F 1 \ u003d 3.

ban 2

x 1	3/2	1	-1/2	-3/2	0	0
x 4	1/2	0	1/2	-1/2	1	0
x 5	11/2	0	1/2	1/2	0	1
F	3/2	0	-3/2	-3/2	0	0

X 2 \ u003d (3/2; 0; 0; 1/2; 11/2) F 2 \ u003d 3/2.

Không có số dương nào trong hàng chỉ số của bảng cuối cùng, nghĩa là, trong biểu thức cho hàm mục tiêu, tất cả Гi> 0. Ta có trường hợp 1, do đó, giải pháp cơ bản cuối cùng là tối ưu.

Đáp số: Ф min = 3/2, nghiệm tối ưu là (3/2; 0; 0; 1/2; 11/2).

Dung dịch: tìm giá trị lớn nhất và nhỏ nhất của hàm \ (f (x, y) \) theo các ràng buộc sau $$ f (x, y) = (x-4) ^ 2 + (y-3) ^ 2 \ rightarrow tối đa, tối thiểu \ \ \ begin (trường hợp) 2x + 3y \ geq 6 \\ 3x-2y \ leq 18 \\ -x + 2y \ leq 8 \\ x, y \ geq0 \ end (trường hợp) $$
Cách đồ họa Có thể sử dụng lời giải của bài toán đối với các bài toán có hai biến được viết dưới dạng đối xứng, cũng như đối với các bài toán có nhiều biến, với điều kiện là ký hiệu chính tắc của chúng chứa không quá hai biến tự do.

TẠI trường hợp này nhiệm vụ với hai biến.

Thuật toán để giải quyết vấn đề "giải thích hình học của một bài toán lập trình tuyến tính":

1. Hãy dựng miền nghiệm trên mặt phẳng xOy.
2. Chọn khu vực của các nghiệm không âm.

4. Hãy để chúng tôi xây dựng một họ các hàm mục tiêu.
5. Tìm giá trị lớn nhất (nhỏ nhất) của hàm mục tiêu.

1. Chúng tôi xây dựng miền các giải pháp chấp nhận được của vấn đề \ (D \).

Xây dựng vùng các giải pháp khả thi:
1) Chúng tôi xây dựng các đường ranh giới:
chúng ta biến đổi các bất đẳng thức thành các phương trình bằng nhau, và sau đó thành phương trình của một đường thẳng trong các đoạn trên trục có dạng \ (\ frac (x) (a) + \ frac (y) (b) = 1 \), sau đó \ (x = a \) là đoạn bị cắt trên trục Ox, \ (y = b \) - trên trục Oy $$ \ begin (case) 2x + 3y = 6 \\ 3x-2y = 18 \\ - x + 2y = 8 \ end (các trường hợp) => \ begin (các trường hợp) \ frac (x) (3) + \ frac (y) (2) = 1 \\ \ frac (x) (8) - \ frac ( y) (9) = 1 \\ - \ frac (x) (6) + \ frac (y) (4) = 1 \ end (case) $$ Đối với mỗi dòng, dành các đoạn trên trục và nối chúng lại. Chúng tôi đã có những dòng phù hợp.

2) Ta tìm các nửa mặt phẳng thỏa mãn các bất đẳng thức đã cho:
Cho bất phương trình \ (2x + 3y \ geq 6 \) là nửa mặt phẳng nằm trên đường thẳng \ (2x + 3y = 6 \). AC trực tiếp
Cho bất phương trình \ (3x-2y \ leq 18 => -3x + 2y \ geq -18 \) là nửa mặt phẳng nằm trên đường thẳng \ (3x-2y = 18 \). CB trực tiếp
Đối với bất đẳng thức \ (- x + 2y \ leq 8 \) là nửa mặt phẳng nằm bên dưới đường thẳng \ (- x + 2y = 8 \). AB trực tiếp

Lĩnh vực của các giải pháp khả thi được xác định là một phần chung ba nửa mặt phẳng ứng với các bất đẳng thức đã cho. Khu vực này là một tam giác \ (ABC \)

Vùng \ (D \) là tam giác \ (ABC \) xem hình.

2. Chọn khu vực của các nghiệm không âm.

Khu vực của các giải pháp không tiêu cực nằm trong quý đầu tiên và là phần chung của tất cả năm nửa mặt phẳng, ba trong số đó là vùng \ (D \) thu được từ các bất đẳng thức và thêm hai bất đẳng thức \ (x \ geq 0 \) - nửa mặt phẳng trên (phần tư I và II) và \ (y \ geq 0 \) - nửa mặt phẳng bên phải (phần tư I và IV), biểu thị điều kiện không phủ định của các biến \ (x; y \). Có được vùng mong muốn của các giải pháp không âm \ (DEBFG \)

Tìm tọa độ các đỉnh của vùng.
Tọa độ của bốn đỉnh đã được biết trước (đây là giao điểm của các đường thẳng với các trục).
Hãy viết ra các tọa độ sau:
\ (D (0; 2) \), \ (E (0; 4) \), \ (F (6; 0) \), \ (G (3; 0) \)
Tìm tọa độ của điểm \ (B \), là giao điểm của các đường \ (- x + 2y = 8 \) và \ (3x-2y = 18 \). Giải hệ phương trình và tìm tọa độ của điểm này $$ \ begin (case) -x + 2y = 8 \\ 3x-2y = 18 \ end (case) => \ begin (case) 2x = 26 \\ 3x -2y = 18 \ end (các trường hợp) => \ begin (các trường hợp) x = 13 \\ y = 10.5 \ end (các trường hợp) $$
Chúng tôi đã có tọa độ của điểm \ (B (13; 10,5) \)

4. Chúng tôi xây dựng một họ các hàm mục tiêu.
Phương trình \ (f (x, y) = (x-4) ^ 2 + (y-3) ^ 2 \ rightarrow max, min \) xác định trên mặt phẳng xOy một họ các đường tròn đồng tâm tại điểm có tọa độ \ (Q (4; 3) \), mỗi trong số đó tương ứng giá trị nhất định tham số \ (f \). Như bạn đã biết, đối với phương trình của một đường tròn, tham số \ (f = R ^ 2 \).

Chúng ta hãy biểu diễn trong cùng một hệ tọa độ, một họ đường tròn đồng tâm \ (f \) và một họ đường thẳng. Vấn đề xác định điểm cực đại (cực tiểu) của điểm \ (f \) sẽ được rút gọn thành việc tìm trong khu vực cho phépđiểm mà vòng tròn của họ \ (f = const \) đi qua, chịu trách nhiệm cho giá trị lớn nhất (nhỏ nhất) của tham số \ (f \).

5. Tìm giá trị lớn nhất (nhỏ nhất) của hàm mục tiêu.

Giá trị hàm mục tiêu nhỏ nhất: đường tăng dần bán kính của đường tròn, chúng ta có đỉnh đầu tiên mà đường tròn đi qua là điểm \ (G (3; 0) \). Hàm mục tiêu tại thời điểm này sẽ là cực tiểu và bằng \ (f (3,0) = (3-4) ^ 2 + (0-3) ^ 2 = 10 \)

Giá trị lớn nhất của hàm mục tiêu: Bằng cách tăng thêm bán kính của đường tròn, chúng ta đã thu được rằng đỉnh cuối cùng mà đường tròn sẽ đi qua là điểm \ (B (13; 10,5) \). Hàm mục tiêu tại thời điểm này sẽ là cực đại và bằng \ (f (13,10,5) = (13-4) ^ 2 + (10,5-3) ^ 2 = 137,25 \)

Bạn có thể xác minh tính đúng đắn của giải pháp bằng cách thay thế tọa độ của các đỉnh còn lại vào phương trình hàm mục tiêu:
tại đỉnh \ (D (0; 2) \) giá trị của hàm mục tiêu bằng \ (f (0,2) = (0-4) ^ 2 + (2-3) ^ 2 = 17 \)
tại đỉnh \ (E (0; 4) \) giá trị của hàm mục tiêu bằng \ (f (0,4) = (0-4) ^ 2 + (4-3) ^ 2 = 17 \)
tại đỉnh \ (F (6; 0) \) giá trị của hàm mục tiêu là \ (f (6,4) = (6-4) ^ 2 + (0-3) ^ 2 = 13 \)
Hiểu rồi

Câu trả lời:
giá trị nhỏ nhất của hàm mục tiêu \ (f_ (min) = 10 \)
giá trị lớn nhất của hàm mục tiêu \ (f_ (max) = 137,25 \)

Tìm bằng phương pháp đồ thị giá trị lớn nhất của hàm mục tiêu

F = 2x 1 + 3x 2 ® tối đa

Với những hạn chế

Dung dịch bằng cách sử dụng Bảng Excel

Đầu tiên chúng ta hãy xây dựng trên một trang tính giải pháp excel hệ bất phương trình.

Xét bất đẳng thức đầu tiên.

Hãy xây dựng một đường ranh giới từ hai điểm. Ký hiệu dòng bằng (L1) (hoặc Row1). Tọa độ X 2 chúng tôi đếm theo công thức:

Để xây dựng, hãy chọn một biểu đồ phân tán

Chọn dữ liệu cho một đường thẳng

Thay đổi tên của dòng:

Chọn bố cục biểu đồ. Thay đổi tên của các trục tọa độ:

Đường thẳng (L1) trên biểu đồ:

Lời giải cho bất phương trình nghiêm ngặt có thể được tìm thấy bằng cách sử dụng một điểm kiểm tra duy nhất không thuộc đường thẳng (L1). Ví dụ, sử dụng điểm (0; 0) W (L1).

0 + 3 × 0< 18 или 0 < 18 .

Bất đẳng thức đúng, do đó, nghiệm của bất phương trình (1) sẽ là nửa mặt phẳng chứa điểm kiểm tra (trong hình bên dưới đường thẳng L1).

Khi đó ta giải bất phương trình (2).

Hãy để chúng tôi xây dựng đường ranh giới 2 từ hai điểm. Ký hiệu dòng bằng (L2).

Đường thẳng (L2) trên biểu đồ:

Lời giải của bất phương trình nghiêm ngặt 2 có thể được tìm thấy bằng cách sử dụng điểm kiểm tra duy nhất không thuộc đường thẳng (L2). Ví dụ, sử dụng điểm (0; 0) W (L2).

Thay vào tọa độ của điểm (0; 0), ta thu được bất phương trình

2 × 0 + 0< 16 или 0 < 16 .

Bất đẳng thức đúng, do đó, nghiệm của bất phương trình (2) sẽ là nửa mặt phẳng chứa điểm kiểm tra (trong hình dưới đây, đường thẳng L2).

Khi đó ta giải bất đẳng thức (3).

Hãy xây dựng một đường ranh giới từ hai điểm. Ký hiệu dòng bằng (L3).

Đường thẳng (L3) trên biểu đồ:

Lời giải của bất phương trình nghiêm ngặt 2 có thể được tìm thấy bằng cách sử dụng điểm kiểm tra duy nhất không thuộc đường thẳng (L3). Ví dụ, sử dụng điểm (0; 0) W (L3).

Thay vào tọa độ của điểm (0; 0), ta thu được bất phương trình

Bất đẳng thức đúng, do đó, nghiệm của bất phương trình (3) sẽ là nửa mặt phẳng chứa điểm kiểm tra (trong hình dưới đây, đường thẳng L3).

Khi đó ta giải bất đẳng thức (4).

Hãy xây dựng một đường ranh giới từ hai điểm. Ký hiệu dòng bằng (L4).

Thêm dữ liệu vào trang tính excel

Đường thẳng (L4) trên biểu đồ:

Giải pháp của Bất đẳng thức nghiêm ngặt 3 X 1 < 21 можно найти с помощью единственной пробной точки, не принадлежащей прямой (L4). Например, с помощью точки (0; 0)Ï(L4).

Thay vào tọa độ của điểm (0; 0), ta thu được bất phương trình

Bất đẳng thức đúng, do đó, nghiệm của bất phương trình (4) sẽ là nửa mặt phẳng chứa điểm kiểm tra (bên trái đường thẳng L4 trong hình).

Bằng cách giải hai bất phương trình (5) và (6)

là phần tư thứ nhất được giới hạn bởi các đường tọa độ và.

Hệ bất phương trình được giải. Bằng cách giải hệ bất phương trình (1) - (6) trong ví dụ này là một đa giác lồi ở góc dưới bên trái của hình, được giới hạn bởi các đường L1, L2, L3, L4 và các đường tọa độ và. Bạn có thể đảm bảo rằng đa giác được chọn chính xác bằng cách thay một điểm kiểm tra, ví dụ (1; 1) vào mỗi bất đẳng thức của hệ ban đầu. Thay điểm (1; 1), chúng ta nhận được rằng tất cả các bất đẳng thức, bao gồm cả các ràng buộc tự nhiên, đều đúng.

Bây giờ hãy xem xét hàm mục tiêu

F = 2x 1 + 3x 2 .

Hãy xây dựng các đường mức cho các giá trị hàm F = 0 và F = 12 (Giá trị kiểu sốđược lựa chọn tùy ý). Thêm dữ liệu vào trang tính excel

Các đường mức trên biểu đồ:

Hãy xây dựng một vectơ chỉ hướng (hoặc một gradient) (2; 3). Tọa độ vectơ trùng với các hệ số của hàm mục tiêu F.