Tìm bằng phương pháp đồ thị điểm cực tiểu của hàm mục tiêu. Tìm cực trị của hàm bằng phương pháp đồ thị

hàm mục tiêu- hàm thực hoặc nguyên của một số biến, tùy thuộc vào tối ưu hóa (tối thiểu hóa hoặc tối đa hóa) để giải quyết một số vấn đề tối ưu hóa. Thuật ngữ này được sử dụng trong lập trình toán học, nghiên cứu hoạt động, lập trình tuyến tính, lý thuyết quyết định thống kê và các lĩnh vực toán học khác, chủ yếu có tính chất ứng dụng, mặc dù mục tiêu tối ưu hóa cũng có thể là giải pháp của một vấn đề toán học thích hợp. Ngoại trừ hàm mục tiêu trong bài toán tối ưu hóa, các biến có thể bị ràng buộc dưới dạng một hệ phương trình bằng hoặc bất phương trình. TẠI trường hợp chung các đối số của hàm mục tiêu có thể được chỉ định trên các tập tùy ý.

Các ví dụ

Hàm trơn và hệ phương trình

Bài toán giải bất phương trình

(F 1 (x 1, x 2,…, x M) = 0 F 2 (x 1, x 2,…, x M) = 0… F N (x 1, x 2,…, x M) = 0 ( \ displaystyle \ left \ ((\ begin (matrix) F_ (1) (x_ (1), x_ (2), \ ldots, x_ (M)) = 0 \\ F_ (2) (x_ (1), x_ (2), \ ldots, x_ (M)) = 0 \\\ ldots \\ F_ (N) (x_ (1), x_ (2), \ ldots, x_ (M)) = 0 \ end (ma trận) )\bên phải.)

có thể được xây dựng như một bài toán giảm thiểu hàm mục tiêu

S = ∑ j = 1 N F j 2 (x 1, x 2,…, x M) (1) (\ displaystyle S = \ sum _ (j = 1) ^ (N) F_ (j) ^ (2) ( x_ (1), x_ (2), \ ldots, x_ (M)) \ qquad (1))

Nếu các chức năng hoạt động trơn tru, thì vấn đề tối thiểu hóa có thể được giải quyết bằng phương pháp gradient.

Đối với bất kỳ hàm mục tiêu trơn nào, người ta có thể tương đương với 0 (\ displaystyle 0) các đạo hàm riêng đối với tất cả các biến. Hàm mục tiêu tối ưu sẽ là một trong những nghiệm của một hệ phương trình như vậy. Trong trường hợp của hàm (1) (\ displaystyle (1)), đây sẽ là hệ phương trình của phương pháp bình phương nhỏ nhất(MNK). Bất kỳ nghiệm nào của hệ ban đầu là một nghiệm của hệ bình phương nhỏ nhất. Nếu hệ thống ban đầu không nhất quán, thì hệ thống LSM, luôn có một nghiệm, có thể thu được một nghiệm gần đúng của hệ thống ban đầu. Số lượng phương trình của hệ LSM trùng với số ẩn số, điều này đôi khi tạo điều kiện thuận lợi cho việc giải các hệ ban đầu chung.

Lập trình tuyến tính

Khác ví dụ nổi tiếng hàm mục tiêu là một hàm tuyến tính xảy ra trong các bài toán lập trình tuyến tính. Không giống như hàm mục tiêu bậc hai, tối ưu hóa hàm tuyến tính chỉ có thể thực hiện được nếu có những hạn chế dưới dạng một hệ các bất đẳng thức hoặc bất đẳng thức tuyến tính.

Tối ưu hóa kết hợp

Một ví dụ điển hình của hàm mục tiêu tổ hợp là hàm mục tiêu của bài toán nhân viên bán hàng lưu động. Hàm số này bằng độ dài của chu trình Hamilton trên đồ thị. Nó được đưa ra trên tập hoán vị n - 1 (\ displaystyle n-1) của các đỉnh đồ thị và được xác định bởi ma trận độ dài cạnh của đồ thị. Giải pháp chính xác của những vấn đề như vậy thường phụ thuộc vào việc liệt kê các phương án.

Chương 1. Phát biểu bài toán chính của lập trình tuyến tính

1. Lập trình tuyến tính

Lập trình tuyến tính là một nhánh của lập trình toán học nghiên cứu các phương pháp giải các bài toán cực trị được đặc trưng bởi phụ thuộc tuyến tính giữa các biến và một kiểm định tuyến tính. Những vấn đề như vậy tìm thấy các ứng dụng rộng rãi trong các lĩnh vực khác nhau hoạt động của con người. Một nghiên cứu có hệ thống về các vấn đề thuộc loại này bắt đầu vào năm 1939–1940. trong các tác phẩm của L.V. Kantorovich.

Các vấn đề toán học của lập trình tuyến tính bao gồm nghiên cứu các tình huống sản xuất và kinh tế cụ thể, dưới dạng này hay dạng khác được hiểu là các bài toán về việc sử dụng tối ưu các nguồn lực hạn chế.

Phạm vi các vấn đề được giải quyết bằng phương pháp lập trình tuyến tính là khá rộng, chẳng hạn như:

vấn đề sử dụng tối ưu các nguồn lực trong lập kế hoạch sản xuất;

vấn đề của hỗn hợp (lập kế hoạch thành phần của sản phẩm);

vấn đề tìm kiếm sự kết hợp tối ưu của các loại sản phẩm khác nhau để lưu trữ trong kho (quản lý hàng tồn kho hoặc);

nhiệm vụ vận tải (phân tích vị trí của xí nghiệp, sự di chuyển của hàng hoá).

Lập trình tuyến tính là phần được phát triển và sử dụng rộng rãi nhất của lập trình toán học (ngoài ra, phần này bao gồm: lập trình số nguyên, động, phi tuyến tính, tham số). Điều này được giải thích như sau:

mô hình toán học một số lượng lớn các vấn đề kinh tế là tuyến tính đối với các biến số yêu cầu;

loại vấn đề này hiện đang được nghiên cứu nhiều nhất. Được thiết kế cho anh ấy phương pháp đặc biệt, với sự trợ giúp của các nhiệm vụ này được giải quyết và các chương trình máy tính tương ứng;

nhiều vấn đề của lập trình tuyến tính, đang được giải quyết, có ứng dụng rộng rãi;

một số vấn đề không tuyến tính trong công thức ban đầu, sau một loạt hạn chế bổ sung và các giả định có thể trở thành tuyến tính hoặc có thể được rút gọn thành dạng sao cho chúng có thể được giải quyết bằng các phương pháp lập trình tuyến tính.

Mô hình kinh tế và toán học của bất kỳ bài toán lập trình tuyến tính nào bao gồm: một hàm mục tiêu, giá trị tối ưu của nó (lớn nhất hoặc nhỏ nhất) phải được tìm thấy; các hạn chế dưới dạng một hệ thống Các phương trình tuyến tính hoặc các bất bình đẳng; yêu cầu về tính không phủ định của các biến.

TẠI nhìn chung mô hình được viết như sau:

hàm mục tiêu

(1.1) theo các hạn chế

(1.2) yêu cầu không tiêu cực

(1.3) ở đâu x j- biến (ẩn số);

- Các hệ số của bài toán lập trình tuyến tính.

Vấn đề là tìm giá trị tối ưu của hàm (1.1) tuân theo các ràng buộc (1.2) và (1.3).

Hệ thống các ràng buộc (1.2) được gọi là các ràng buộc chức năng của bài toán, và các ràng buộc (1.3) được gọi là các ràng buộc trực tiếp.

Một vectơ thỏa mãn các ràng buộc (1.2) và (1.3) được gọi là phương án (phương án) khả thi của bài toán lập trình tuyến tính. Phương án mà hàm (1.1) đạt giá trị lớn nhất (nhỏ nhất) được gọi là tối ưu.

1.2. Phương pháp Simplex để giải các bài toán lập trình tuyến tính

Phương pháp simplex được phát triển và áp dụng lần đầu để giải các bài toán vào năm 1947 bởi nhà toán học người Mỹ J. Danzig.

Các bài toán lập trình tuyến tính hai chiều được giải quyết bằng đồ thị. Đối với trường hợp N = 3, chúng ta có thể coi là một không gian ba chiều và hàm mục tiêu sẽ đạt giá trị tối ưu tại một trong các đỉnh của hình đa diện.

Một phương án có thể chấp nhận được (một phương án có thể chấp nhận được) của một bài toán LP được cho ở dạng chuẩn là một bộ số có thứ tự (x1, x2, ..., xn) thỏa mãn các ràng buộc; là điểm trong không gian n chiều.

Nhiều giải pháp khả thi tạo thành miền các giải pháp chấp nhận được (ODS) của bài toán LP. ODR là một đa diện lồi (đa giác).

Nói một cách tổng quát, khi có N ẩn số liên quan đến vấn đề, chúng ta có thể nói rằng khu vực của các giải pháp khả thi, được đưa ra bởi hệ thống các điều kiện giới hạn, được biểu diễn bằng đa diện lồi trong không gian n chiều và giá trị tối ưu của hàm mục tiêu đạt được tại một hoặc nhiều đỉnh.

Một giải pháp được gọi là cơ bản nếu tất cả các biến tự do bằng không.

Một giải pháp tham chiếu là một giải pháp cơ bản không tiêu cực. Giải pháp hỗ trợ có thể là không thoái hóa và thoái hóa. Một giải pháp hỗ trợ được gọi là không suy biến nếu số các tọa độ khác 0 của nó bằng cấp của hệ thống, nếu không thì nó là suy biến.

Một giải pháp khả thi, trong đó hàm mục tiêu đạt giá trị cực trị của nó, được gọi là tối ưu và được ký hiệu là .

Rất khó để giải các bài toán này bằng đồ thị khi số biến nhiều hơn 3. Tồn tại cách phổ quát giải các bài toán lập trình tuyến tính, được gọi là phương pháp simplex.

Phương pháp simplex là một phương pháp phổ biến để giải các bài toán LP, là một quá trình lặp đi lặp lại bắt đầu với một giải pháp và, để tìm kiếm phương án tốt nhất, di chuyển dọc theo các điểm góc của vùng các giải pháp khả thi cho đến khi nó đạt đến giá trị tối ưu .

Nó có thể được sử dụng để giải quyết bất kỳ vấn đề lập trình tuyến tính nào.

Phương pháp simplex dựa trên ý tưởng cải tiến liên tiếp giải pháp thu được.

Ý nghĩa hình học của phương pháp simplex bao gồm chuyển tiếp liên tiếp từ một đỉnh của đa diện ràng buộc sang đỉnh lân cận, trong đó hàm mục tiêu nhận giá trị tốt nhất (hoặc ít nhất không phải là giá trị xấu nhất) cho đến khi nó được tìm thấy giải pháp tối ưu- đỉnh đạt đến giá trị tối ưu của hàm mục tiêu (nếu nhiệm vụ có giá trị tối ưu hữu hạn).

Do đó, có một hệ thống các ràng buộc được giảm xuống hình thức kinh điển(tất cả các ràng buộc chức năng đều ở dạng cân bằng), hãy tìm bất kỳ giải pháp cơ bản nào của hệ thống này, chỉ cẩn thận tìm nó càng đơn giản càng tốt. Nếu giải pháp cơ bản được tìm thấy đầu tiên trở nên khả thi, thì nó sẽ được kiểm tra về tính tối ưu. Nếu nó không phải là tối ưu, thì một sự chuyển đổi được thực hiện sang một giải pháp cơ bản khác, nhất thiết có thể chấp nhận được. Phương pháp simplex đảm bảo rằng, với giải pháp mới này, hàm mục tiêu, nếu nó không đạt đến mức tối ưu, thì sẽ tiếp cận nó (hoặc ít nhất là không di chuyển khỏi nó). Với một giải pháp cơ bản mới được chấp nhận, điều tương tự cũng được thực hiện cho đến khi tìm thấy một giải pháp tối ưu.

Quá trình áp dụng phương pháp simplex bao gồm việc thực hiện ba yếu tố chính của nó:

một phương pháp xác định một số giải pháp cơ bản khả thi ban đầu cho vấn đề;

quy luật chuyển đổi sang giải pháp tốt nhất (chính xác hơn, không phải là giải pháp tồi tệ nhất);

tiêu chí để kiểm tra tính tối ưu của giải pháp tìm được.

Phương pháp simplex bao gồm một số bước và có thể được xây dựng dưới dạng một thuật toán rõ ràng (một hướng dẫn rõ ràng về cách triển khai hoạt động liên tiếp). Điều này cho phép bạn lập trình và triển khai thành công trên máy tính. Các vấn đề với một số lượng nhỏ các biến và các ràng buộc có thể được giải quyết bằng phương pháp simplex theo cách thủ công.

6.1 Giới thiệu

Tối ưu hóa. Phần 1

Các phương pháp tối ưu hóa cho phép bạn chọn tùy chọn thiết kế tốt nhất trong số tất cả tùy chọn. TẠI những năm trước những phương pháp này đã được đưa ra sự chú ý lớn và kết quả là đã phát triển toàn bộ dòng các thuật toán hiệu quả cao để tìm lựa chọn tốt nhất thiết kế sử dụng máy tính. Chương này phác thảo các nguyên tắc cơ bản của lý thuyết tối ưu hóa, xem xét các nguyên tắc cơ bản của việc xây dựng các thuật toán cho các giải pháp tối ưu, mô tả các thuật toán nổi tiếng nhất và phân tích các ưu điểm và nhược điểm của chúng.

6.2. Các nguyên tắc cơ bản của lý thuyết tối ưu hóa

Thuật ngữ "tối ưu hóa" trong tài liệu đề cập đến một quy trình hoặc chuỗi hoạt động cho phép bạn có được một giải pháp tinh chỉnh. Mặc dù mục tiêu cuối cùng của việc tối ưu hóa là tìm ra giải pháp tốt nhất hoặc "tối ưu", bạn thường phải bằng lòng với việc cải thiện các giải pháp đã biết hơn là hoàn thiện chúng. Do đó, tối ưu hóa có nhiều khả năng được hiểu là theo đuổi sự hoàn hảo, mà có lẽ sẽ không đạt được.

Đang xem xét một số hệ thống tùy ý, được mô tả bởi m phương trình với n ẩn số, có ba dạng bài toán chính. Nếu m = n, bài toán được gọi là đại số. Một vấn đề như vậy thường có một giải pháp. Nếu m> n, thì bài toán được định nghĩa lại và theo quy luật, không có lời giải. Cuối cùng, đối với m

Trước khi tiếp tục thảo luận về các vấn đề tối ưu hóa, chúng tôi xin giới thiệu một số định nghĩa.

Thông số thiết kế

Thuật ngữ này đề cập đến độc lập tham số biến, xác định hoàn toàn và rõ ràng vấn đề thiết kế đang được giải quyết. Các thông số thiết kế là các đại lượng chưa biết, các giá trị của chúng được tính toán trong quá trình tối ưu hóa. Bất kỳ đại lượng cơ bản hoặc đạo hàm nào phục vụ cho việc mô tả định lượng hệ thống đều có thể dùng làm tham số thiết kế. Vì vậy, nó có thể là các giá trị chưa biết về chiều dài, khối lượng, thời gian, nhiệt độ. Số lượng các thông số thiết kế đặc trưng cho mức độ phức tạp của vấn đề thiết kế này. Thông thường số lượng các thông số thiết kế được ký hiệu là n, và các thông số thiết kế chính nó là x với các chỉ số tương ứng. Như vậy, n tham số thiết kế của bài toán này sẽ được ký hiệu là

X1, x2, x3, ..., xn.

hàm mục tiêu

Đây là biểu thức mà giá trị của nó mà kỹ sư tìm cách tối đa hóa hoặc giảm thiểu. Hàm mục tiêu cho phép bạn so sánh định lượng hai giải pháp thay thế. Từ quan điểm toán học, hàm mục tiêu mô tả một số (n + 1) bề mặt chiều. Giá trị của nó được xác định bởi các thông số thiết kế

M = M (x 1, x 2, ..., x n).

Ví dụ về hàm mục tiêu, thường gặp trong thực tế kỹ thuật, là chi phí, trọng lượng, sức mạnh, kích thước, hiệu quả. Nếu chỉ có một tham số thiết kế, thì hàm mục tiêu có thể được biểu diễn bằng một đường cong trên mặt phẳng (Hình 6.1). Nếu có hai tham số thiết kế, thì hàm mục tiêu sẽ được biểu diễn bằng một bề mặt trong không gian ba chiều (Hình 6.2). Với ba tham số thiết kế trở lên, các bề mặt được chỉ định bởi hàm mục tiêu được gọi là siêu bề mặt và không thể được mô tả.

zheniya phương tiện thông thường. Các thuộc tính tôpô của bề mặt hàm mục tiêu đóng một vai trò quan trọng trong quá trình tối ưu hóa, vì việc lựa chọn thuật toán hiệu quả nhất phụ thuộc vào chúng.

Hàm mục tiêu trong một số trường hợp có thể có những dạng không mong muốn nhất. Ví dụ, không phải lúc nào cũng có thể diễn đạt nó bằng

Hình 1. Hàm mục tiêu một chiều.

Hình.6.2. Hàm mục tiêu hai chiều.

đóng cửa dạng toán học, trong những trường hợp khác, nó có thể

là một chức năng mượt mà. Một chức năng mục tiêu đôi khi có thể yêu cầu một bảng dữ liệu kỹ thuật (ví dụ, một bảng trạng thái hơi nước) hoặc có thể cần tiến hành một thí nghiệm. Trong một số trường hợp, các tham số thiết kế chỉ nhận các giá trị nguyên. Một ví dụ sẽ là số lượng răng trong một bánh răng hoặc số lượng bu lông trong một mặt bích. Đôi khi các thông số thiết kế chỉ có hai giá trị - có hoặc không. Các thông số định tính, chẳng hạn như sự hài lòng của khách hàng, độ tin cậy, tính thẩm mỹ, rất khó để tính đến trong quá trình tối ưu hóa, vì chúng hầu như không thể định lượng được. Tuy nhiên, dưới bất kỳ hình thức nào, hàm mục tiêu được trình bày, nó phải là một hàm đơn giá trị của các tham số thiết kế.

Trong một số bài toán tối ưu hóa, cần có nhiều hơn một hàm mục tiêu. Đôi khi một trong số chúng có thể không tương thích với cái còn lại. Một ví dụ là thiết kế của máy bay, khi nó được yêu cầu đồng thời cung cấp sức mạnh tối đa, trọng lượng tối thiểu và chi phí tối thiểu. Trong những trường hợp như vậy, người thiết kế phải đưa ra một hệ thống ưu tiên và gán một số nhân không thứ nguyên cho mỗi hàm mục tiêu. Kết quả là, một "hàm thỏa hiệp" xuất hiện, cho phép một hàm mục tiêu tổng hợp được sử dụng trong quá trình tối ưu hóa.

Tìm mức tối thiểu và tối đa

Một số thuật toán tối ưu hóa được điều chỉnh để tìm giá trị tối đa, một số thuật toán khác để tìm giá trị tối thiểu. Tuy nhiên, bất kể loại bài toán cực trị nào được giải, người ta có thể sử dụng cùng một thuật toán, vì bài toán cực tiểu có thể dễ dàng biến thành bài toán tìm cực đại bằng cách đảo ngược dấu của hàm mục tiêu. Kỹ thuật này được minh họa trong Hình 6.3.

Không gian thiết kế

Đây là tên của khu vực được xác định bởi tất cả n tham số thiết kế. Không gian thiết kế không lớn như người ta tưởng, vì nó thường bị giới hạn ở một số

các điều kiện liên quan đến thực thể vật chất các nhiệm vụ. Ràng buộc có thể quá mạnh nên nhiệm vụ sẽ không có bất kỳ

Hình.6.3. Thay đổi dấu của hàm mục tiêu thành ngược lại

Nhiệm vụ tối đa trở thành nhiệm vụ tối thiểu.

giải pháp thỏa đáng. Các ràng buộc được chia thành hai nhóm: ràng buộc - bình đẳng và ràng buộc - bất bình đẳng.

Ràng buộc - bình đẳng

Ràng buộc - sự ngang bằng - là sự phụ thuộc giữa các thông số thiết kế phải được tính đến khi tìm giải pháp. Chúng phản ánh các quy luật tự nhiên, kinh tế, quyền lợi, thị hiếu thịnh hành và sự sẵn có của các vật liệu cần thiết. Số lượng các hạn chế - bằng nhau có thể là bất kỳ. Họ trông giống như

C 1 (x 1, x 2, ..., x n) = 0,

C 2 (x 1, x 2, ..., x n) = 0,

..................

C j (x 1, x 2, ..., x n) = 0.

Nếu bất kỳ mối quan hệ nào trong số này có thể được giải quyết đối với một trong các tham số thiết kế, thì điều này cho phép bạn loại trừ tham số này khỏi quá trình tối ưu hóa. Điều này làm giảm số lượng kích thước của không gian thiết kế và đơn giản hóa giải pháp của vấn đề.

Ràng buộc - bất bình đẳng

Đây là một loại ràng buộc đặc biệt được thể hiện bởi các bất bình đẳng. Trong trường hợp chung, có thể có bất kỳ số nào trong số chúng và tất cả chúng đều có dạng

z 1 r 1 (x 1, x 2, ..., x n) Z 1

z 2 r 2 (x 1, x 2, ..., x n) Z 2

.......................

z k r k (x 1, x 2, ..., x n) Z k

Cần lưu ý rằng rất thường xuyên, do những hạn chế, giá trị tối ưu của hàm mục tiêu không đạt được khi bề mặt của nó có gradient bằng không. Thường thì giải pháp tốt nhất là ở một trong các ranh giới của miền thiết kế.

Tối ưu cục bộ

Đây là tên của điểm trong không gian thiết kế mà tại đó hàm mục tiêu có giá trị lớn nhất so với các giá trị của nó tại tất cả các điểm khác trong vùng lân cận trực tiếp của nó.

Hình.6.4. Một hàm mục tiêu tùy ý có thể có một số

optima cục bộ.

Trên hình. Hình 6.4 cho thấy một hàm mục tiêu một chiều có hai optima cục bộ. Thường thì không gian thiết kế chứa nhiều optima cục bộ và phải cẩn thận để không nhầm lần đầu tiên với giải pháp tối ưu cho vấn đề.

Tối ưu toàn cầu

Toàn cầu là giải pháp tối ưu cho toàn bộ không gian thiết kế. Nó tốt hơn tất cả các giải pháp khác tương ứng với optima cục bộ và đây là những gì nhà thiết kế đang tìm kiếm. Trường hợp của một số optima toàn cầu bằng nhau nằm ở các bộ phận khác nhau không gian thiết kế. Làm thế nào vấn đề tối ưu hóa được đặt ra được minh họa tốt nhất bằng một ví dụ.

Ví dụ 6.1

Để yêu cầu thiết kế một thùng chứa hình chữ nhật có thể tích 1 m, được thiết kế để vận chuyển sợi không đóng gói. Điều mong muốn là việc sản xuất các thùng chứa như vậy nên được chi tiêu nhiều nhất có thể ít vật liệu hơn(giả sử độ dày của tường không đổi, điều này có nghĩa là diện tích bề mặt phải nhỏ nhất), vì nó sẽ rẻ hơn. Để thuận tiện cho việc lấy container bằng xe nâng, chiều rộng của nó ít nhất phải là 1,5 m.

Chúng ta hãy hình thành bài toán này dưới dạng thuận tiện cho việc áp dụng thuật toán tối ưu hóa.

Thông số thiết kế: x 1, x 2, x 3.

Hàm mục tiêu (cần được giảm thiểu) là diện tích bề mặt bên của thùng chứa:

A = 2 (x 1 x 2 + x 2 x 3 + x 1 x 3), m2.

Ràng buộc - bình đẳng:

Thể tích \ u003d x 1 x 2 x 3 \ u003d 1m3.

Ràng buộc - bất bình đẳng:

Các vấn đề về lập trình tuyến tính

Lập trình tuyến tính (LP) là một trong những phần của lập trình toán học - chuyên ngành nghiên cứu các vấn đề cực trị (tối ưu hóa) và phát triển các phương pháp giải chúng.

Vấn đề tối ưu hóa- đây là vấn đề toán học, bao gồm việc tìm giá trị tối ưu (tức là lớn nhất hoặc nhỏ nhất) của hàm mục tiêu và giá trị của các biến phải thuộc một khu vực nhất định giá trị cho phép(ODZ).

Nói chung, việc xây dựng một bài toán cực trị của lập trình toán học bao gồm việc xác định giá trị lớn nhất hoặc nhỏ nhất của hàm, được gọi là hàm mục tiêu, trong các điều kiện (hạn chế), ở đâu và - các chức năng được xác định trước, và được đưa ra hằng số. Đồng thời, các hạn chế dưới dạng bình đẳng và bất bình đẳng xác định tập hợp (vùng) các giải pháp khả thi (ODS), và được gọi là Thông số thiết kế.

Tùy thuộc vào loại chức năng và các vấn đề của lập trình toán học được chia thành một số lớp (tuyến tính, phi tuyến, lồi, nguyên, ngẫu nhiên, lập trình động, v.v.).

TẠI nhìn chung Vấn đề LP có lần xem tiếp theo:

, (5.1)

, , (5.2)

, , (5.3)

trong đó, là các hằng số đã cho.

Hàm (5.1) được gọi là hàm mục tiêu; hệ thống (5.2), (5.3) - bởi một hệ thống các ràng buộc; điều kiện (5.4) là điều kiện không tiêu cực của các thông số thiết kế.

Tập hợp các tham số thiết kế thỏa mãn các ràng buộc (5.2), (5.3) và (5.4) được gọi là giải pháp chấp nhận được hoặc kế hoạch.

Giải pháp tối ưu hoặc kế hoạch tối ưu Bài toán LP được gọi là một giải pháp khả thi, trong đó hàm mục tiêu (5.1) nhận giá trị tối ưu (lớn nhất hoặc nhỏ nhất).

Nhiệm vụ tiêu chuẩn LP được gọi là bài toán tìm giá trị lớn nhất (nhỏ nhất) của hàm mục tiêu (5.1) với điều kiện (5.2) và (5.4), trong đó, tức là những thứ kia. Chỉ hạn chế ở dạng bất đẳng thức (5.2) và tất cả các tham số thiết kế đều thỏa mãn điều kiện không tiêu cực và không có điều kiện nào ở dạng cân bằng:

,

, , (5.5)

.

Tác vụ chính tắc (chính) LP được gọi là bài toán tìm giá trị lớn nhất (nhỏ nhất) của hàm mục tiêu (5.1) với điều kiện (5.3) và (5.4), trong đó, tức là những thứ kia. Các hạn chế chỉ ở dạng cân bằng (5.3) và tất cả các tham số thiết kế đều thỏa mãn điều kiện không tiêu cực và không có điều kiện nào ở dạng bất đẳng thức:

,

.

Bài toán LP chính tắc cũng có thể được viết dưới dạng ma trận và vectơ.

Dạng ma trận của bài toán LP chính tắc có dạng sau:

Dạng vectơ của bài toán LP chính tắc.

KIỂM SOÁT CÔNG VIỆC TRÊN KỶ LUẬT:

"PHƯƠNG PHÁP GIẢI TOÁN TỐI ƯU"

Tùy chọn số 8

1. Giải một bài toán lập trình tuyến tính bằng phương pháp đồ họa. Tìm cực đại và cực tiểu của hàm  theo các ràng buộc cho trước:

,

.

Dung dịch

Cần phải tìm giá trị nhỏ nhất của hàm mục tiêu và giá trị lớn nhất, theo hệ thống các hạn chế:

9x1 + 3x2 ≥30, (1)

X 1 + x 2 ≤4, (2)

x 1 + x 2 ≤8, (3)

Hãy để chúng tôi xây dựng miền các giải pháp có thể chấp nhận được, tức là giải hệ bất phương trình bằng đồ thị. Để làm điều này, chúng tôi xây dựng mỗi đường thẳng và xác định các nửa mặt phẳng được cho bởi các bất đẳng thức (các nửa mặt phẳng được đánh dấu bằng một số nguyên tố).

Giao của các nửa mặt phẳng sẽ là diện tích, tọa độ của các điểm thỏa mãn điều kiện bất phương trình của hệ thức của bài toán. Hãy để chúng tôi biểu thị các ranh giới của vùng của đa giác giải pháp.

Hãy dựng một đường thẳng ứng với giá trị của hàm F = 0: F = 2x 1 + 3x 2 = 0. Vectơ gradient gồm các hệ số của hàm mục tiêu chỉ ra chiều cực tiểu của F (X). Điểm đầu của vectơ là điểm (0; 0), điểm cuối là điểm (2; 3). Hãy di chuyển đường thẳng này theo một cách song song. Vì chúng tôi quan tâm đến giải pháp tối thiểu, do đó, chúng tôi di chuyển đường thẳng cho đến khi chạm đầu tiên vào khu vực được chỉ định. Trên biểu đồ, đường này được biểu thị bằng một đường chấm.

Dài
cắt vùng tại điểm C. Vì điểm C nhận được là kết quả của giao điểm của đường (4) và (1), nên tọa độ của nó thỏa mãn phương trình của các đường này:
.

Giải hệ phương trình, ta được: x 1 = 3,3333, x 2 = 0.

Chúng ta có thể tìm giá trị nhỏ nhất của hàm mục tiêu ở đâu:.

Xem xét hàm mục tiêu của vấn đề.

Hãy dựng một đường thẳng ứng với giá trị của hàm F = 0: F = 2x 1 + 3x 2 = 0. Vectơ gradient gồm các hệ số của hàm mục tiêu cho biết hướng cực đại của F (X). Điểm đầu của vectơ là điểm (0; 0), điểm cuối là điểm (2; 3). Hãy di chuyển đường thẳng này theo một cách song song. Vì chúng tôi quan tâm đến giải pháp tối đa, chúng tôi di chuyển đường thẳng cho đến lần chạm cuối cùng của khu vực được chỉ định. Trên biểu đồ, đường này được biểu thị bằng một đường chấm.

Dài
cắt vùng tại điểm B. Vì điểm B nhận được là kết quả của giao điểm của đường (2) và (3), nên tọa độ của nó thỏa mãn phương trình của các đường này:

.

Chúng ta có thể tìm giá trị lớn nhất của hàm mục tiêu ở đâu:.

Câu trả lời:
và
.

2 . Giải một bài toán lập trình tuyến tính bằng phương pháp simplex:

.

Dung dịch

Hãy giải bài toán trực tiếp của lập trình tuyến tính bằng phương pháp simplex, sử dụng bảng simplex.

Hãy để chúng tôi xác định giá trị nhỏ nhất của hàm mục tiêu
theo các điều kiện-hạn chế sau:
.

Để xây dựng phương án tham chiếu đầu tiên, chúng tôi giảm hệ bất phương trình thành một hệ phương trình bằng cách đưa thêm các biến.

Trong bất đẳng thức thứ nhất có nghĩa (≥), chúng tôi giới thiệu biến cơ bản x 3 bằng dấu trừ. Trong bất đẳng thức thứ 2 có nghĩa (≤), chúng tôi giới thiệu biến cơ bản x 4 . Trong bất đẳng thức nghĩa thứ 3 (≤), chúng tôi giới thiệu biến cơ bản x 5.

Hãy giới thiệu các biến nhân tạo : trong đẳng thức thứ nhất, chúng tôi giới thiệu một biến x 6 ;

Để đặt nhiệm vụ cho giá trị nhỏ nhất, chúng ta viết hàm mục tiêu như sau:.

Đối với việc sử dụng các biến nhân tạo được đưa vào hàm mục tiêu, người ta áp dụng cái gọi là hình phạt của M, một số dương rất lớn, thường không được chỉ định.

Cơ sở kết quả được gọi là nhân tạo, và phương pháp giải được gọi là phương pháp cơ sở nhân tạo.

Hơn nữa, các biến nhân tạo không liên quan đến nội dung của nhiệm vụ, nhưng chúng cho phép bạn xây dựng điểm bắt đầu và quá trình tối ưu hóa buộc các biến này nhận giá trị bằng 0 và đảm bảo khả năng chấp nhận của giải pháp tối ưu.

Từ phương trình, chúng ta biểu diễn các biến nhân tạo: x 6 \ u003d 4-x 1 -x 2 + x 3, chúng ta thay thế vào hàm mục tiêu: hoặc.

Ma trận hệ số
hệ phương trình này có dạng:
.

Hãy giải hệ phương trình với các biến cơ bản: x 6 , x 4 , x 5.

Giả sử rằng các biến tự do là 0, chúng tôi nhận được đường cơ sở đầu tiên:

X1 = (0,0,0,2.10,4)

Một giải pháp cơ bản được gọi là có thể chấp nhận được nếu nó không âm.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Đường cơ sở hiện tại không phải là tối ưu vì có các hệ số dương trong hàng chỉ mục. Chúng ta sẽ chọn cột tương ứng với biến x 2 làm cột đứng đầu, vì đây là hệ số lớn nhất. Tính toán các giá trị D tôi và chọn giá trị nhỏ nhất trong số chúng: min (4: 1, 2: 2, 10: 2) = 1.

Do đó, dòng thứ 2 đang dẫn đầu.

Phần tử phân giải bằng (2) và nằm ở giao điểm của cột đầu tiên và hàng đầu tiên.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Chúng tôi tạo thành phần tiếp theo của bảng simplex. Thay vì biến x 4, biến x 2 sẽ vào phương án 1.

Dòng tương ứng với biến x 2 trong phương án 1 nhận được bằng cách chia tất cả các phần tử của dòng x 4 của phương án 0 cho phần tử cho phép RE = 2. Thay cho phần tử phân giải, chúng ta nhận được 1. Trong các ô còn lại của cột x 2, chúng ta viết số không.

Do đó, trong kế hoạch mới, 1 hàng x 2 và cột x 2 được lấp đầy. Tất cả các phần tử khác của phương án 1 mới, bao gồm các phần tử của hàng chỉ mục, được xác định bởi quy tắc hình chữ nhật.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 2
x 5
		1/2 +1 1/2 triệu

Đường cơ sở hiện tại không phải là tối ưu vì có các hệ số dương trong hàng chỉ mục. Chúng ta sẽ chọn cột tương ứng với biến x 1 làm cột đứng đầu, vì đây là hệ số lớn nhất. Tính toán các giá trị D tôi bởi các hàng như một thương số của phép chia: và từ chúng ta chọn giá trị nhỏ nhất: min (3: 1 1/2, -, 8: 2) = 2.

Do đó, tuyến 1 đang dẫn đầu.

Phần tử phân giải bằng (1/2) và nằm ở giao điểm của cột đầu tiên và hàng đầu tiên.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6		1 1 / 2
x 2
x 5
		-1 1 / 2 +1 1 / 2 M

Chúng tôi tạo thành phần tiếp theo của bảng simplex. Thay vì biến x 6, biến x 1 sẽ được đưa vào phương án 2.

Chúng tôi nhận được một bảng đơn giản mới:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Không có giá trị hàng chỉ mục nào là dương. Do đó, bảng này xác định kế hoạch nhiệm vụ tối ưu.

Phiên bản cuối cùng của bảng simplex:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Vì không có biến nhân tạo nào trong giải pháp tối ưu (chúng bằng 0), nên quyết định này là hợp lệ.

Phương án tối ưu có thể được viết như sau: x 1 \ u003d 2, x 2 \ u003d 2:.

Câu trả lời:
,
.

3. Công ty "Ba chàng béo" tham gia vào việc vận chuyển thịt hộp từ ba nhà kho nằm ở các khu vực khác nhau của thành phố đến ba cửa hàng. Dự trữ thực phẩm đóng hộp có sẵn trong kho, cũng như khối lượng đơn đặt hàng từ các cửa hàng và tỷ lệ giao hàng (có điều kiện đơn vị tiền tệ) được trình bày trong bảng vận chuyển.

Tìm một kế hoạch vận chuyển cung cấp ít chi phí tiền mặt nhất (thực hiện kế hoạch vận chuyển ban đầu bằng cách sử dụng phương pháp "góc tây bắc").

Dung dịch

Hãy để chúng tôi kiểm tra điều kiện cần và đủ cho khả năng giải quyết vấn đề:

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

Điều kiện cân bằng được đáp ứng. Cổ phiếu có nhu cầu bình đẳng. Do đó, mô hình bài toán vận tải bị đóng lại.

Hãy nhập dữ liệu ban đầu vào bảng phân phối.

Nhu cầu

Sử dụng phương pháp góc Tây Bắc, chúng ta sẽ xây dựng phương án cơ bản đầu tiên của bài toán vận.

Kế hoạch bắt đầu được điền từ góc trên bên trái.

Phần tử mong muốn là 4. Đối với phần tử này, cổ phiếu là 300, nhu cầu là 250. Vì mức tối thiểu là 250, chúng tôi trừ đi:.

			300 - 250 = 50
250 - 250 = 0

Phần tử mong muốn là 2. Đối với phần tử này, cổ phiếu là 50, nhu cầu là 400. Vì mức tối thiểu là 50, chúng tôi trừ đi:.

			50 - 50 = 0
	400 - 50 = 350

Phần tử mong muốn là 5. Đối với phần tử này, cổ phiếu là 300, nhu cầu là 350. Vì mức tối thiểu là 300, chúng tôi trừ đi:

			300 - 300 = 0
	350 - 300 = 50

Phần tử mong muốn là 3. Đối với phần tử này, cổ phiếu là 200, nhu cầu là 50. Vì mức tối thiểu là 50, chúng tôi trừ đi:

			200 - 50 = 150
	50 - 50 = 0

Phần tử mong muốn là 6. Đối với phần tử này, cổ phiếu là 150, nhu cầu là 150. Vì mức tối thiểu là 150, chúng tôi trừ đi:

			150 - 150 = 0
		150 - 150 = 0

Nhu cầu

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à về mặt hình học tìm giá trị nhỏ nhất của 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 một loạt các giải pháp khả thi là phần chung của nửa mặt phẳng kết quả là vùng được tô bóng.

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ờ tất cả các delta đều lớn hơn 0, 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ó hai biến trong một bài toán lập trình tuyến tính, thì nó có thể được giải quyết bằng đồ thị.

Hãy xem xét một bài toán lập trình tuyến tính với hai biến và:
(1.1) ;
(1.2)
Đây, là những con số tùy ý. Nhiệm vụ có thể vừa là tìm giá trị lớn nhất (max) vừa để tìm giá trị nhỏ nhất (min). Trong hệ thống hạn chế, cả biển báo và biển báo đều có thể có mặt.

Xây dựng lĩnh vực giải pháp khả thi

Phương pháp đồ họa để giải bài toán (1) như sau.
Đầu tiên, chúng ta vẽ các trục tọa độ và chọn tỷ lệ. Mỗi bất đẳng thức của hệ ràng buộc (1.2) xác định một nửa mặt phẳng giới hạn bởi đường thẳng tương ứng.

Vì vậy, bất đẳng thức đầu tiên
(1.2.1)
xác định một nửa mặt phẳng giới hạn bởi một đường thẳng. Ở một bên của dòng này, và ở bên kia. Trên đường thẳng nhất. Để tìm bất đẳng thức bên (1.2.1) thỏa mãn, chúng ta chọn điểm tùy ý không nằm trên một đường thẳng. Tiếp theo, chúng tôi thay thế tọa độ của điểm này trong (1.2.1). Nếu bất đẳng thức đúng, thì nửa mặt phẳng chứa điểm đã chọn. Nếu bất đẳng thức không được thoả mãn thì nửa mặt phẳng nằm ở phía bên kia (không chứa điểm đã chọn). Chúng tôi tô bóng nửa mặt phẳng mà bất đẳng thức (1.2.1) được thỏa mãn.

Ta làm tương tự đối với các bất phương trình còn lại của hệ (1.2). Vì vậy, chúng tôi nhận được các nửa mặt phẳng bóng mờ. Các điểm thuộc miền nghiệm thỏa mãn mọi bất đẳng thức (1.2). Do đó, về mặt đồ thị, diện tích các giải pháp khả thi (ODD) là giao của tất cả các nửa mặt phẳng đã xây dựng. Chúng tôi đánh bóng ODR. Nó là một đa giác lồi có các mặt thuộc các đường đã dựng. Ngoài ra, ODR có thể là một hình lồi không giới hạn, một đoạn thẳng, một tia hoặc một đường thẳng.

Trường hợp cũng có thể phát sinh rằng các nửa mặt phẳng không chứa điểm thông dụng. Khi đó miền của các nghiệm có thể chấp nhận là tập trống. Vấn đề này không có giải pháp.

Bạn có thể đơn giản hóa phương pháp. Bạn không thể tô bóng từng nửa mặt phẳng, nhưng trước tiên hãy xây dựng tất cả các đường
(2)
Tiếp theo, chọn một điểm tùy ý không thuộc bất kỳ đường nào trong số các đường này. Thay tọa độ của điểm này vào hệ bất phương trình (1.2). Nếu tất cả các bất đẳng thức được thỏa mãn, thì diện tích các giải pháp khả thi được giới hạn bởi các đường đã xây dựng và bao gồm điểm đã chọn. Chúng tôi tô bóng vùng của các giải pháp có thể chấp nhận dọc theo ranh giới của các đường để nó bao gồm điểm đã chọn.

Nếu ít nhất một bất đẳng thức không được thỏa mãn thì chọn điểm khác. Và cứ tiếp tục như vậy, cho đến khi một điểm được tìm thấy, tọa độ của điểm đó thỏa mãn hệ thức (1.2).

Tìm cực trị của hàm mục tiêu

Vì vậy, chúng ta có một vùng bóng mờ của các giải pháp khả thi (ODD). Nó được giới hạn bởi một đường đứt gãy bao gồm các đoạn và tia thuộc các đường đã xây dựng (2). ODR luôn tập hợp lồi. Nó có thể giống như bộ giới hạn, và không bị giới hạn dọc theo một số hướng.

Bây giờ chúng ta có thể tìm kiếm cực trị của hàm mục tiêu
(1.1) .

Để làm điều này, hãy chọn bất kỳ số nào và dựng một đường thẳng
(3) .
Để thuận tiện cho việc trình bày thêm, chúng tôi giả sử rằng đường thẳng này đi qua ODS. Trên đường thẳng này, hàm mục tiêu không đổi và bằng. một đường thẳng như vậy được gọi là đường mức của hàm số. Đường thẳng này chia mặt phẳng thành hai nửa mặt phẳng. Trên một nửa mặt phẳng
.
Ở nửa mặt phẳng còn lại
.
Tức là ở một phía của đường thẳng (3), hàm mục tiêu tăng. Và chúng ta càng di chuyển điểm ra xa dòng (3), giá trị sẽ càng lớn. Ở phía bên kia đường thẳng (3), hàm mục tiêu giảm dần. Và chúng ta càng di chuyển điểm ra khỏi dòng (3) về phía bên kia, giá trị sẽ càng nhỏ. Nếu chúng ta vẽ một đường song song với đường (3), thì đường mới cũng sẽ là đường mức hàm mục tiêu, nhưng với một giá trị khác.

Như vậy, để tìm giá trị lớn nhất của hàm mục tiêu, cần vẽ một đường thẳng song song với đường thẳng (3), càng xa nó càng tốt theo chiều tăng dần các giá trị của và đi qua ít nhất một điểm của ODT. Để tìm giá trị nhỏ nhất của hàm mục tiêu, cần vẽ một đường thẳng song song với đường thẳng (3) và càng xa nó càng tốt theo chiều giảm các giá trị của và đi qua ít nhất một điểm của ODT.

Nếu ODE không bị ràng buộc, thì một trường hợp có thể phát sinh khi không thể vẽ một đường thẳng như vậy. Nghĩa là, dù ta có xóa đường thẳng ra khỏi đường mức (3) theo chiều tăng (giảm) như thế nào thì đường thẳng vẫn luôn đi qua ODR. Trong trường hợp này, nó có thể lớn (nhỏ) tùy ý. Do đó, không có giá trị lớn nhất (nhỏ nhất). Vấn đề không có giải pháp.

Xét trường hợp đường cực trị song song với một đường thẳng tùy ý có dạng (3) đi qua một đỉnh của đa giác ODD. Từ đồ thị, ta xác định được tọa độ của đỉnh này. Khi đó giá trị lớn nhất (nhỏ nhất) của hàm mục tiêu được xác định theo công thức:
.
Giải pháp cho vấn đề là
.

Cũng có thể có trường hợp đường thẳng song song với một trong các mặt của ODD. Khi đó đường thẳng đi qua hai đỉnh của đa giác ODD. Chúng tôi xác định tọa độ của các đỉnh này. Để xác định giá trị lớn nhất (nhỏ nhất) của hàm mục tiêu, bạn có thể sử dụng tọa độ của bất kỳ đỉnh nào sau đây:
.
Vấn đề có vô số giải pháp. Giải pháp là bất kỳ điểm nào nằm trên đoạn giữa các điểm và, bao gồm cả chính các điểm và.

Một ví dụ về giải bài toán lập trình tuyến tính bằng phương pháp đồ họa

Nhiệm vụ

Công ty sản xuất áo dài với hai mẫu A và B. Ba loại vải được sử dụng. Để sản xuất một chiếc váy kiểu A, cần 2 m vải loại thứ nhất, 1 m vải loại thứ hai, 2 m vải loại thứ ba. Để sản xuất một chiếc váy kiểu B, cần 3 m vải loại thứ nhất, 1 m vải loại thứ hai, 2 m vải loại thứ ba. Kho vải loại thứ nhất là 21 m, loại thứ hai - 10 m, loại thứ ba - 16 m. Việc phát hành một sản phẩm loại A mang lại thu nhập 400 den. đơn vị, một sản phẩm loại B - 300 den. các đơn vị

Hãy lập một kế hoạch sản xuất mang lại thu nhập lớn nhất cho công ty. Giải quyết vấn đề bằng đồ thị.

Dung dịch

Gọi các biến và biểu thị số lượng váy được sản xuất của các kiểu A và B, tương ứng. Sau đó, lượng mô được sử dụng của loại đầu tiên sẽ là:
(m)
Lượng vải sử dụng của loại thứ hai sẽ là:
(m)
Lượng vải sử dụng của loại thứ ba sẽ là:
(m)
Vì số lượng váy được sản xuất không thể là số âm, nên
và .
Thu nhập từ những chiếc váy được sản xuất sẽ là:
(đơn vị den.)

Khi đó mô hình toán kinh tế của bài toán có dạng:

Chúng tôi giải quyết nó bằng đồ thị.
Vẽ các trục tọa độ và.

Chúng tôi xây dựng một đường thẳng.
Tại .
Tại .
Ta kẻ đường thẳng đi qua các điểm (0; 7) và (10,5; 0).

Chúng tôi xây dựng một đường thẳng.
Tại .
Tại .
Ta kẻ đường thẳng đi qua các điểm (0; 10) và (10; 0).

Chúng tôi xây dựng một đường thẳng.
Tại .
Tại .
Ta kẻ đường thẳng đi qua các điểm (0; 8) và (8; 0).

Chúng tôi tô bóng khu vực để điểm (2; 2) rơi vào phần được tô bóng. Ta được tứ giác OABC.

(P1.1) .
Tại .
Tại .
Ta kẻ đường thẳng đi qua các điểm (0; 4) và (3; 0).

Hơn nữa, chúng tôi lưu ý rằng vì các hệ số của và của hàm mục tiêu là dương (400 và 300), nên nó tăng khi tăng và. Ta kẻ một đường thẳng song song với đường thẳng (A1.1) càng xa nó càng tốt theo chiều tăng và đi qua ít nhất một điểm của tứ giác OABC. Đường thẳng như vậy đi qua điểm C. Từ cách dựng, ta xác định được tọa độ của nó.
.

Giải pháp của vấn đề :;

Câu trả lời

.
Tức là, để có được thu nhập lớn nhất, cần phải may 8 chiếc váy của người mẫu A. Thu nhập trong trường hợp này sẽ là 3200 den. các đơn vị

Ví dụ 2

Nhiệm vụ

Giải một bài toán lập trình tuyến tính bằng phương pháp đồ họa.

Dung dịch

Chúng tôi giải quyết nó bằng đồ thị.
Vẽ các trục tọa độ và.

Chúng tôi xây dựng một đường thẳng.
Tại .
Tại .
Ta kẻ đường thẳng đi qua các điểm (0; 6) và (6; 0).

Chúng tôi xây dựng một đường thẳng.
Từ đây.
Tại .
Tại .
Ta kẻ đường thẳng đi qua các điểm (3; 0) và (7; 2).

Chúng tôi xây dựng một đường thẳng.
Chúng tôi xây dựng một đường thẳng (trục abscissa).

Miền của các giải pháp chấp nhận được (DDR) được giới hạn bởi các đường thẳng được xây dựng. Để tìm ra mặt nào, chúng ta nhận thấy rằng điểm thuộc về ODT, vì nó thỏa mãn hệ bất phương trình:

Chúng tôi tô bóng khu vực dọc theo ranh giới của các đường đã xây dựng để điểm (4; 1) rơi vào phần được tô bóng. Chúng tôi nhận được tam giác ABC.

Chúng tôi xây dựng một đường mức tùy ý của hàm mục tiêu, ví dụ:
.
Tại .
Tại .
Ta kẻ đường thẳng cấp đi qua các điểm (0; 6) và (4; 0).
Vì hàm mục tiêu tăng khi tăng và, chúng tôi vẽ một đường thẳng, đường song song và càng xa nó càng tốt theo chiều tăng và đi qua ít nhất một điểm của tam giác ABC. Đường thẳng như vậy đi qua điểm C. Từ cách dựng, ta xác định được tọa độ của nó.
.

Giải pháp của vấn đề :;

Câu trả lời

Ví dụ về không có giải pháp

Nhiệm vụ

Giải quyết vấn đề lập trình tuyến tính bằng đồ thị. Tìm giá trị lớn nhất và nhỏ nhất của hàm mục tiêu.

Dung dịch

Chúng tôi giải quyết vấn đề bằng đồ thị.
Vẽ các trục tọa độ và.

Chúng tôi xây dựng một đường thẳng.
Tại .
Tại .
Ta kẻ đường thẳng đi qua các điểm (0; 8) và (2.667; 0).

Chúng tôi xây dựng một đường thẳng.
Tại .
Tại .
Ta kẻ đường thẳng đi qua các điểm (0; 3) và (6; 0).

Chúng tôi xây dựng một đường thẳng.
Tại .
Tại .
Ta kẻ đường thẳng đi qua các điểm (3; 0) và (6; 3).

Các đường thẳng và là các trục tọa độ.

Miền của các nghiệm có thể chấp nhận (SDR) được giới hạn bởi các đường thẳng và trục tọa độ đã xây dựng. Để tìm ra mặt nào, chúng ta nhận thấy rằng điểm thuộc về ODT, vì nó thỏa mãn hệ bất phương trình:

Chúng tôi tô bóng khu vực để điểm (3; 3) rơi vào phần được tô bóng. Chúng ta nhận được diện tích không giới hạn được giới hạn bởi đường đứt khúc ABCDE.

Chúng tôi xây dựng một đường mức tùy ý của hàm mục tiêu, ví dụ:
(P3.1) .
Tại .
Tại .
Ta kẻ đường thẳng đi qua các điểm (0; 7) và (7; 0).
Vì các hệ số tại và là dương, sau đó tăng khi tăng và.

Để tìm điểm cực đại, bạn cần vẽ một đường thẳng song song, càng xa càng tốt theo hướng tăng và đi qua ít nhất một điểm của vùng ABCDE. Tuy nhiên, vì khu vực này không bị giới hạn từ bên giá trị lớn và, khi đó không thể vẽ một đường thẳng như vậy. Dù chúng ta vẽ một đường thẳng nào thì sẽ luôn có các điểm trong vùng càng xa càng tốt theo hướng tăng và. Do đó, không có tối đa. bạn có thể làm cho nó lớn như bạn muốn.

Chúng tôi đang tìm kiếm mức tối thiểu. Ta kẻ một đường thẳng song song với đường thẳng (A3.1) và càng xa nó càng tốt theo chiều giảm và đi qua ít nhất một điểm của vùng ABCDE. Đường thẳng như vậy đi qua điểm C. Từ cách dựng, ta xác định được tọa độ của nó.
.
Giá trị tối thiểu chức năng mục tiêu:

Câu trả lời

Không có giá trị lớn nhất.
Giá trị tối thiểu
.