Tìm thấy phương pháp đồ họa tối đ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.

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 chức năng 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ô hình toán học và giải quyết nó bằng phương pháp simplex.
• 2. Lập mô hình toán học nhiệm vụ kép và viết ra giải pháp của nó dựa trên giải pháp của giải pháp 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.

Giới thiệu

Giai đoạn phát triển hiện đại của con người khác ở chỗ thế kỷ của năng lượng đang được thay thế bằng thời đại của tin học. Có sự giới thiệu chuyên sâu về các công nghệ mới trong tất cả các lĩnh vực hoạt động của con người. Đứng lên vấn đề thực sự chuyển đổi sang xã hội thông tin, trong đó sự phát triển của giáo dục nên trở thành một ưu tiên. Cơ cấu tri thức trong xã hội cũng đang thay đổi. Tất cả các giá trị lớn hơn vì Cuộc sống thực tế có được kiến ​​thức cơ bản góp phần vào phát triển sáng tạo tính cách. Tính xây dựng của kiến ​​thức thu được, khả năng cấu trúc nó phù hợp với mục tiêu cũng rất quan trọng. Dựa trên kiến ​​thức, mới nguồn thông tin xã hội. Việc hình thành và tiếp thu kiến ​​thức mới cần dựa trên một phương pháp luận chặt chẽ phương pháp tiếp cận hệ thống, trong đó phương pháp tiếp cận mô hình chiếm một vị trí riêng biệt. Các khả năng của phương pháp mô hình hóa là vô cùng đa dạng cả về các mô hình chính thức được sử dụng và cách thực hiện các phương pháp mô hình hóa. Mô hình vật lý làm cho nó có thể thu được kết quả đáng tin cậy cho các hệ thống khá đơn giản.

Hiện tại, không thể gọi tên một lĩnh vực hoạt động của con người mà ở mức độ này hay cách khác, các phương pháp mô hình hóa sẽ không được sử dụng. Điều này đặc biệt đúng trong lĩnh vực quản lý. các hệ thống khác nhau, trong đó những quy trình chính là các quá trình ra quyết định dựa trên thông tin nhận được.

1. Phát biểu vấn đề

hàm mục tiêu tối thiểu

Giải bài toán tìm điểm cực tiểu của hàm mục tiêu cho hệ thống các ràng buộc được xác định bởi đa giác quyết định theo phương án số 16 của nhiệm vụ. Đa giác quyết định được thể hiện trong Hình 1:

Hình 1 - Đa giác các giải pháp vấn đề

Hệ thống các ràng buộc và hàm mục tiêu của bài toán được trình bày dưới đây:

Nó là cần thiết để giải quyết vấn đề bằng cách sử dụng các phương pháp sau:

Phương pháp đồ thị để giải các bài toán LP;

Phương pháp đại số để giải các bài toán LP;

Phương pháp Simplex để giải các bài toán LP;

Phương pháp tìm giải pháp khả thi cho vấn đề LP;

Giải quyết vấn đề LP kép;

Phương pháp "nhánh và ranh giới" để giải các bài toán LP số nguyên;

Phương pháp Gomory để giải các bài toán LP số nguyên;

Phương pháp Balash để giải các bài toán Boolean LP.

So sánh kết quả của bài giải bằng các phương pháp khác nhau để rút ra kết luận phù hợp về bài làm.

2. Giải pháp đồ họa vấn đề lập trình tuyến tính

Phương pháp đồ họa để giải các bài toán lập trình tuyến tính được sử dụng trong trường hợp số ẩn số không vượt quá ba. Thuận tiện cho việc nghiên cứu định tính thuộc tính của các giải pháp và được sử dụng cùng với các phương pháp khác (đại số, rẽ nhánh và ràng buộc, v.v.). Ý tưởng của phương pháp dựa trên giải pháp đồ họa của một hệ bất phương trình tuyến tính.

Cơm. 2 Giải pháp đồ họa của vấn đề LP

Điểm thấp

Phương trình đường thẳng đi qua hai điểm A1 và A2:

AB: (0; 1); (3; 3)

CN: (3; 3); (4; 1)

CD: (4; 1); (3; 0)

EA: (1; 0); (0; 1)

CF: (0; 1); (5; 2)

với các hạn chế:

Giải một bài toán lập trình tuyến tính bằng phương pháp đại số đơn giản

Việc áp dụng phương pháp đại số để giải bài toán đòi hỏi sự tổng quát hóa biểu diễn của bài toán LP. Hệ thống ban đầu của các ràng buộc ở dạng bất đẳng thức được chuyển đổi thành ký hiệu chuẩn khi các ràng buộc được cho ở dạng bằng nhau. Chuyển đổi hệ thống ràng buộc thành mẫu bao gồm các bước sau:

Biến đổi các bất đẳng thức theo cách mà các biến và các phần tử tự do ở bên trái và 0 ở bên phải, tức là rằng phía bên trái lớn hơn hoặc bằng không;

Giới thiệu các biến bổ sung, số của chúng bằng số bất phương trình trong hệ thống các hạn chế;

Nhập cuộc hạn chế bổ sung về tính không phủ định của các biến được thêm vào, hãy thay dấu của bất đẳng thức bằng dấu của đẳng thức chặt chẽ.

Khi giải quyết vấn đề LP phương pháp đại số một điều kiện được thêm vào: hàm mục tiêu phải có xu hướng tối thiểu. Nếu điều kiện này không được đáp ứng, cần phải biến đổi một cách thích hợp hàm mục tiêu (nhân với -1) và giải bài toán cực tiểu. Sau khi giải pháp được tìm thấy, hãy thay thế các giá trị của các biến trong hàm ban đầu và tính giá trị của nó.

Lời giải của bài toán sử dụng phương pháp đại số được coi là tối ưu khi giá trị của tất cả các biến cơ bản không âm, và hệ số của các biến tự do trong phương trình hàm mục tiêu cũng không âm. Nếu không thỏa mãn các điều kiện này, cần biến đổi hệ bất phương trình, biểu diễn một số biến về dạng khác (đổi biến tự do và biến cơ bản) để đạt được các hạn chế trên. Giá trị của tất cả các biến tự do được giả định là không.

Phương pháp đại số để giải các bài toán lập trình tuyến tính là một trong những phương pháp phương pháp hiệu quả khi giải các bài toán có kích thước nhỏ bằng tay. không yêu cầu một số lượng lớn các phép tính số học. Việc triển khai máy của phương pháp này phức tạp hơn, ví dụ, đối với phương pháp simplex, bởi vì thuật toán để giải theo phương pháp đại số ở một mức độ nào đó là heuristic và hiệu quả của giải pháp phần lớn phụ thuộc vào kinh nghiệm cá nhân.

biến miễn phí

Ngõ St. - cộng. bộ dụng cụ

Do đó, các điều kiện không tiêu cực được thỏa mãn, chúng tôi đã tìm thấy giải pháp tối ưu.

3. Giải bài toán lập trình tuyến tính bằng bảng simplex

Giải pháp: Hãy đưa bài toán về dạng chuẩn để giải bằng bảng đơn giản.

Ta rút gọn tất cả các phương trình của hệ về dạng:

Chúng tôi xây dựng một bảng simplex:

TẠI góc trên với mỗi ô của bảng ta nhập các hệ số từ hệ phương trình;

Chúng tôi chọn phần tử dương lớn nhất trong hàng F, ngoại trừ đây sẽ là cột chung;

Để tìm phần tử chung, chúng tôi xây dựng một quan hệ cho tất cả các phần tử dương. 3/3; 9/1; - tỷ lệ nhỏ nhất trong dòng x3. Do đó - chuỗi chung và = 3 - phần tử chung.

Ta tìm được = 1 / = 1/3. Chúng tôi đưa vào góc dưới của ô, nơi chứa phần tử chung;

Trong tất cả các góc dưới không được điền của dòng chung, chúng tôi nhập tích số của giá trị ở góc trên của ô bằng;

Chọn các góc trên của đường chung;

Ở tất cả các góc dưới của cột chung, chúng ta nhập tích của giá trị ở góc trên bằng - và chọn các giá trị kết quả;

Các ô còn lại của bảng được điền dưới dạng tích của các phần tử đã chọn tương ứng;

Sau đó, chúng tôi xây dựng một bảng mới, trong đó ký hiệu của các ô của các phần tử của cột và hàng chung được đảo ngược (x2 và x3);

Ở góc trên của hàng và cột chung trước đây, các giá trị \ u200b \ u200bt trước đó ở góc dưới được viết;

Tổng giá trị của góc trên và góc dưới của các ô này trong bảng trước đó được viết ở góc trên của các ô còn lại

4. Giải bài toán lập trình tuyến tính bằng cách tìm một giải pháp khả thi

Cho một hệ phương trình đại số tuyến tính được:

Chúng ta có thể cho rằng mọi thứ, nếu không thì chúng ta nhân phương trình tương ứng bởi 1.

Chúng tôi giới thiệu các biến phụ trợ:

Chúng tôi cũng giới thiệu một chức năng phụ trợ

Chúng tôi sẽ giảm thiểu hệ thống theo các ràng buộc (2) và các điều kiện.

QUY TẮC TÌM GIẢI PHÁP KHẢ NĂNG: Để tìm một giải pháp khả thi cho hệ (1), chúng ta thu nhỏ dạng (3) dưới các ràng buộc (2), dưới dạng ẩn số tự do, chúng ta lấy xj làm ẩn số cơ bản.

Khi giải một bài toán bằng phương pháp đơn giản, có thể phát sinh hai trường hợp:

min f = 0, thì tất cả i phải bằng không. Và các giá trị xj kết quả sẽ là giải pháp chấp nhận được hệ thống (1).

min f> 0, tức là hệ thống ban đầu không có một giải pháp khả thi.

Hệ thống nguồn:

Điều kiện của vấn đề của chủ đề trước được sử dụng.

Hãy thêm các biến bổ sung:

Một lời giải thích hợp cho bài toán ban đầu được tìm thấy: x1 = 3, x2 = 3, F = -12. Dựa trên giải pháp khả thi thu được, chúng tôi tìm ra giải pháp tối ưu cho bài toán ban đầu bằng phương pháp simplex. Để thực hiện việc này, chúng tôi sẽ xây dựng một bảng simplex mới từ bảng có được ở trên bằng cách xóa hàng và hàng có hàm mục tiêu của tác vụ phụ trợ:

Phân tích bảng simplex đã xây dựng, chúng ta thấy rằng đã tìm được giải pháp tối ưu cho bài toán ban đầu (các phần tử trong hàng tương ứng với hàm mục tiêu là số âm). Do đó, phương án khả thi tìm được khi giải bài toán phụ trùng với phương án tối ưu của bài toán ban đầu:

6. Bài toán kép của lập trình tuyến tính

Hệ thống các ràng buộc ban đầu và hàm mục tiêu của bài toán được thể hiện trong hình bên dưới.

với các hạn chế:

Giải pháp: Chúng tôi đưa hệ thống các hạn chế về dạng tiêu chuẩn:

Nhiệm vụ kép cho nhiệm vụ này sẽ giống như sau:

Bài toán kép sẽ được giải quyết bằng phương pháp simplex.

Chúng ta hãy biến đổi hàm mục tiêu để bài toán tối thiểu hóa được giải quyết và viết ra hệ thống các ràng buộc ở dạng chuẩn để giải bằng phương pháp đơn giản.

y6 = 1 - (-2 y1 + 2y2 + y3 + y4 + y5)

y7 = 5 - (-3y1 - y2 + y3 + y4)

Ф = 0 - (3y1 + 9y2 + 3y3 + y4) ?? min

Hãy để chúng tôi xây dựng hoạt cảnh đơn giản ban đầu để giải quyết vấn đề LP kép.

Bước thứ hai của phương pháp simplex

Vì vậy, ở bước thứ ba của phương pháp đơn giản, phương pháp tối ưu của bài toán tối thiểu hóa được tìm thấy với các kết quả sau: y2 = -7 / 8, y1 = -11/8, Ф = 12. Để tìm giá trị của hàm mục tiêu của bài toán đối ngẫu, chúng tôi thay thế các giá trị tìm được của các biến cơ bản và biến tự do vào hàm cực đại:

Фmax = - Фmin = 3 * (- 11/8) + 9 (-7/8) + 3 * 0 + 0 = -12

Vì giá trị của hàm mục tiêu của các bài toán trực tiếp và đối ngẫu là như nhau nên nghiệm của bài toán trực tiếp được tìm thấy và bằng 12.

Fmin \ u003d Fmax \ u003d -12

7. Giải bài toán lập trình tuyến tính số nguyên bằng phương pháp "nhánh và giới hạn"

Hãy biến đổi vấn đề ban đầu sao cho điều kiện nguyên không được thỏa mãn khi giải bằng phương pháp thông thường.

Đa giác ban đầu của các giải pháp cho một vấn đề lập trình số nguyên.

Đối với đa giác nghiệm đã biến đổi, chúng tôi xây dựng hệ thống mới những hạn chế.

Chúng tôi viết ra hệ thống các ràng buộc dưới dạng các đẳng thức, để giải bằng phương pháp đại số.

Kết quả của lời giải, phương án tối ưu được tìm thấy: x1 = 9/4, x2 = 5/2, F = -41/4. Lời giải này không thỏa mãn điều kiện tích phân đặt ra trong bài toán. Chúng tôi chia đa giác giải pháp ban đầu thành hai vùng, ngoại trừ vùng 3 khỏi nó

Đã thay đổi đa giác của các giải pháp vấn đề

Hãy để chúng tôi soạn các hệ thống hạn chế mới cho các vùng hình thành của đa giác giải pháp. Diện tích bên trái là hình tứ giác (hình thang). Hệ thống ràng buộc cho vùng bên trái của đa giác giải pháp được trình bày dưới đây.

Hệ thống hạn chế cho vùng bên trái

Vùng bên phải đại diện cho điểm C.

Hệ thống các ràng buộc cho khu vực quyết định đúng được trình bày dưới đây.

Các hệ thống ràng buộc mới là hai vấn đề phụ cần được giải quyết độc lập với nhau. Hãy giải quyết vấn đề lập trình số nguyên cho vùng bên trái của đa giác giải pháp.

Kết quả của lời giải, phương án tối ưu được tìm thấy: x1 = 3, x2 = 3, F = -12. Phương án này thỏa mãn điều kiện của các biến số nguyên trong bài toán và có thể được coi là phương án tham chiếu tối ưu cho bài toán lập trình tuyến tính số nguyên ban đầu. Không có ý nghĩa gì khi thực hiện giải pháp cho đúng vùng giải pháp. Hình dưới đây cho thấy tiến trình giải một bài toán lập trình tuyến tính số nguyên ở dạng cây.

Khóa học giải bài toán lập trình tuyến tính số nguyên bằng phương pháp Gomory.

Trong nhiều ứng dụng thực tế, bài toán lập trình số nguyên rất được quan tâm, trong đó đưa ra hệ bất phương trình tuyến tính và dạng tuyến tính

Yêu cầu tìm một nghiệm nguyên của hệ (1) tối thiểu hóa hàm mục tiêu F, và tất cả các hệ số đều là số nguyên.

Một trong những phương pháp để giải quyết vấn đề lập trình số nguyên được đề xuất bởi Gomory. Ý tưởng của phương pháp này là sử dụng các phương pháp lập trình tuyến tính liên tục, cụ thể là phương pháp simplex.

1) Sử dụng phương pháp đơn giản, lời giải cho bài toán (1), (2) được xác định, yêu cầu của lời giải là số nguyên được loại bỏ; nếu lời giải là số nguyên, thì lời giải mong muốn cho bài toán số nguyên cũng sẽ được tìm thấy;

2) Ngược lại, nếu một số tọa độ không phải là số nguyên, nghiệm thu được của bài toán được kiểm tra khả năng tồn tại nghiệm nguyên (sự hiện diện của các điểm nguyên trong một khối đa diện có thể chấp nhận được):

Nếu trong bất kỳ dòng nào có phần tử tự do phân số, tất cả các hệ số khác đều là số nguyên, thì không có số nguyên, điểm trong một khối đa diện có thể chấp nhận được và bài toán lập trình số nguyên không có lời giải;

Nếu không, một ràng buộc tuyến tính bổ sung được đưa ra, điều này sẽ cắt khỏi khối đa diện có thể chấp nhận được một phần không gây cản trở cho việc tìm kiếm giải pháp cho một bài toán lập trình số nguyên;

3) Để xây dựng một ràng buộc tuyến tính bổ sung, hãy chọn hàng thứ l có phần tử tự do phân số và viết ra ràng buộc bổ sung

trong đó và tương ứng là các phần nhỏ của hệ số và tự do

thành viên. Hãy để chúng tôi giới thiệu một biến phụ trợ vào ràng buộc (3):

Hãy để chúng tôi xác định các hệ số và bao gồm trong ràng buộc (4):

trong đó và là các số nguyên thấp hơn gần nhất cho và, tương ứng.

Gomory đã chứng minh rằng một số lượng hữu hạn các bước như vậy dẫn đến một bài toán lập trình tuyến tính có lời giải là số nguyên và do đó, giải pháp mong muốn.

Giải pháp: Chúng tôi giảm hệ thống các ràng buộc tuyến tính và hàm mục tiêu về dạng chính tắc:

Chúng ta hãy xác định nghiệm tối ưu của hệ thống các ràng buộc tuyến tính, tạm thời loại bỏ điều kiện nguyên. Chúng tôi sử dụng phương pháp simplex cho việc này. Các bảng dưới đây trình bày tuần tự lời giải ban đầu của bài toán và các phép biến đổi của bảng gốc được đưa ra để có được lời giải tối ưu cho bài toán:

Giải bài toán Boolean LP bằng phương pháp Balash.

Soạn biến thể của riêng bạn cho bài toán lập trình tuyến tính số nguyên với các biến Boolean, có tính đến các quy tắc sau: bài toán sử dụng ít nhất 5 biến, ít nhất 4 ràng buộc, hệ số ràng buộc và hàm mục tiêu được chọn tùy ý, nhưng trong trường hợp đó cách mà hệ thống ràng buộc tương thích. Nhiệm vụ là giải ZCLP với các biến Boolean bằng cách sử dụng thuật toán Balash và xác định mức giảm độ phức tạp tính toán liên quan đến việc giải quyết vấn đề bằng cách tìm kiếm toàn diện.

Thực hiện các hạn chế

Giá trị F

Ràng buộc bộ lọc:

Xác định giảm tính toán

Lời giải của bài toán bằng phương pháp tìm kiếm toàn diện là 6 * 25 = 192 biểu thức được tính toán. Lời giải của bài toán theo phương pháp Balash là 3 * 6 + (25-3) = 47 biểu thức tính được. Tổng mức giảm độ phức tạp của các phép tính liên quan đến việc giải quyết vấn đề bằng phương pháp tìm kiếm toàn diện là.

Sự kết luận

Quá trình thiết kế hệ thống thông tin ứng dụng công nghệ thông tin mới không ngừng được cải tiến. Các hệ thống ngày càng phức tạp đang trở thành tâm điểm chú ý của các kỹ sư hệ thống, điều này gây khó khăn cho việc sử dụng các mô hình vật lý và làm tăng tầm quan trọng của các mô hình toán học và mô phỏng máy tính của hệ thống. Mô hình hóa máy đã trở thành một công cụ hữu hiệu để nghiên cứu và thiết kế các hệ thống phức tạp. Mức độ phù hợp của các mô hình toán học không ngừng tăng lên do tính linh hoạt của chúng, phù hợp với các quy trình thực tế, chi phí thực hiện thấp trên cơ sở máy tính hiện đại. Ngày càng có nhiều cơ hội được cung cấp cho người dùng, tức là, một chuyên gia về mô hình hóa hệ thống bằng công nghệ máy tính. Việc sử dụng mô hình đặc biệt hiệu quả trong giai đoạn đầu của việc thiết kế các hệ thống tự động, khi chi phí cho các quyết định sai lầm là đáng kể nhất.

Các công cụ tính toán hiện đại đã giúp tăng đáng kể độ phức tạp của các mô hình được sử dụng trong nghiên cứu hệ thống, có thể xây dựng các mô hình kết hợp, phân tích và mô phỏng có tính đến toàn bộ các yếu tố diễn ra trong các hệ thống thực, tức là, việc sử dụng các mô hình phù hợp hơn với các hiện tượng đang nghiên cứu.

Văn chương:

1. Lyashchenko I.N. Lập trình tuyến tính và phi tuyến tính / I.N. Lyashchenko, E.A. Karagodova, N.V. Chernikova, N.Z. Shor. - K .: "Trường Cao đẳng", 1975, 372 tr.

2. Hướng dẫn thực hiện dự án môn học chuyên ngành “Toán ứng dụng” cho sinh viên chuyên ngành “Hệ thống và mạng máy tính” hình thức giáo dục toàn thời gian và bán thời gian / Biên soạn bởi: I.A. Balakireva, A.V. Skatkov - Sevastopol: Nhà xuất bản SevNTU, 2003. - 15 tr.

3. Hướng dẫn học môn "Toán ứng dụng", phần "Phương pháp tìm kiếm toàn cục và tối thiểu hóa một chiều" / Comp. A.V. Skatkov, I.A. Balakireva, L.A. Litvinova - Sevastopol: Nhà xuất bản SevGTU, 2000. - 31s.

4. Hướng dẫn học môn “Toán ứng dụng” dành cho sinh viên chuyên ngành “Hệ thống và mạng máy tính” Phần “Giải các bài toán lập trình tuyến tính số nguyên” của các dạng giáo dục toàn thời gian và tương ứng / Biên soạn bởi: I.A. Balakireva, A.V. Skatkov - Sevastopol : Nhà xuất bản SevNTU, 2000. - 13 tr.

5. Akulich I.L. Lập trình toán học trong các ví dụ và nhiệm vụ:

6. Proc. phụ cấp kinh tế sinh viên. chuyên gia. các trường đại học.-M.: Cao hơn. trường học, 1986.- 319s., ốm.

7. Andronov S.A. Các phương pháp thiết kế tối ưu: Văn bản bài giảng / SPbGUAP. SPb., 2001. 169 tr.: Bệnh.

Tài liệu tương tự

Thuật toán giải các bài toán lập trình tuyến tính theo phương pháp đơn giản. Xây dựng mô hình toán học của một bài toán lập trình tuyến tính. Giải một bài toán lập trình tuyến tính trong Excel. Tìm kiếm lợi nhuận và phương án sản xuất tối ưu.

hạn giấy, bổ sung 21/03/2012


Giải quyết vấn đề bằng đồ thị. Vẽ một mô hình toán học. Xác định giá trị lớn nhất của hàm mục tiêu. Giải bằng phương pháp đơn giản với cơ sở nhân tạo của một bài toán lập trình tuyến tính chính tắc. Kiểm tra tính tối ưu của giải pháp.

kiểm tra, bổ sung 04/05/2016


Cơ sở lý thuyết của lập trình tuyến tính. Các bài toán về lập trình tuyến tính, các phương pháp giải. Phân tích giải pháp tối ưu. Lời giải của một bài toán lập trình tuyến tính chỉ số đơn. Tuyên bố sự cố và nhập dữ liệu. Các bước xây dựng mô hình và giải pháp.

hạn giấy, bổ sung 12/09/2008


Xây dựng một mô hình toán học. Lựa chọn, luận chứng và mô tả phương pháp giải các bài toán trực tiếp của lập trình tuyến tính bằng phương pháp đơn giản, sử dụng bảng đơn giản. Công thức và giải pháp của một vấn đề kép. Phân tích độ nhạy của mô hình.

hạn giấy, bổ sung 31/10/2014


Xây dựng một mô hình toán học nhằm tối đa hóa lợi nhuận của doanh nghiệp, một giải pháp đồ họa cho bài toán. Giải quyết vấn đề bằng tiện ích bổ sung SOLVER. Phân tích sự thay đổi của trữ lượng tài nguyên. Xác định giới hạn thay đổi của các hệ số của hàm mục tiêu.

hạn giấy, bổ sung 17/12/2014


Lập trình toán học. Lập trình tuyến tính. Các vấn đề của lập trình tuyến tính. Phương pháp đồ thị để giải một bài toán lập trình tuyến tính. Công thức kinh tế của bài toán lập trình tuyến tính. Xây dựng một mô hình toán học.

hạn giấy, bổ sung 13/10/2008


Giải một bài toán lập trình tuyến tính bằng phương pháp đồ họa, xác minh nó trong MS Excel. Phân tích cấu trúc bên trong của lời giải bài toán trong chương trình. Tối ưu hóa kế hoạch sản xuất. Lời giải của bài toán bằng phương pháp đơn giản. Hệ thống xếp hàng đa kênh.

kiểm tra, thêm 05/02/2012


Giải bài toán lập trình tuyến tính theo phương pháp đơn giản: đặt vấn đề, xây dựng mô hình toán kinh tế. Giải bài toán vận tải bằng phương pháp tiềm tàng: xây dựng phương án tham chiếu ban đầu, xác định giá trị tối ưu của nó.

kiểm tra, thêm 04/11/2012


Phát biểu bài toán lập trình phi tuyến. Xác định điểm đứng yên và loại của chúng. Xây dựng các đường mức, một đồ thị ba chiều của hàm mục tiêu và các hạn chế. Giải pháp đồ họa và phân tích của vấn đề. Hướng dẫn sử dụng và lược đồ thuật toán.

hạn giấy, bổ sung 17/12/2012


Phân tích lời giải của một bài toán lập trình tuyến tính. Phương pháp đơn giản bằng cách sử dụng bảng đơn giản. Mô hình hóa và giải pháp vấn đề LP trên máy tính. Giải thích kinh tế của giải pháp tối ưu của vấn đề. Công thức toán học của bài toán vận tải.

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. Được thiết kế trong Microsoft Word.

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 giá trị 0 cho các biến tự do, 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à thứ ba nghiệm hợp lệ (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. Sự gia tăng x 2, xét theo hệ phương trình cuối cùng (**), là không giới hạn. Do đó, Ф sẽ nhận tất cả các giá trị dương lớn, tức 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.

nhiệm vụ 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 loại 2, mô hình toán 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

theo giới hạn: 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.

Không có số âm nào trong hàng chỉ mục 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. Имеем случай 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ó 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 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 về 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).

Chúng tôi chia hàng thứ ba cho phần tử chính bằng 5, chúng tôi nhận được hàng thứ ba của bảng mới.

Các cột cơ sở tương ứng với các cột đơn.

Tính toán các giá trị còn lại của bảng:

"BP - Gói cơ bản":

; ;

"x1": ; ;

"x5": ; .

Các giá trị của hàng chỉ mục không âm, do đó chúng tôi thu được giải pháp tối ưu:,; .

Câu trả lời: lợi nhuận tối đa từ việc bán các sản phẩm đã sản xuất, bằng 160/3 đơn vị, được đảm bảo bằng cách chỉ phát hành sản phẩm loại hai với số lượng 80/9 đơn vị.

Nhiệm vụ số 2

Bài toán lập trình phi tuyến được đưa ra. Tìm cực đại và cực tiểu của hàm mục tiêu bằng phương pháp phân tích đồ thị. Soạn hàm Lagrange và chỉ ra rằng tại các điểm cực trị điều kiện đủ tối thiểu (tối đa).

Tại vì chữ số cuối cùng của mật mã là 8 thì A = 2; B = 5.

Tại vì chữ số áp chót của mật mã là 1, thì bạn nên chọn nhiệm vụ số 1.

Dung dịch:

1) Hãy vẽ diện tích mà hệ bất phương trình xác định.

Khu vực này là tam giác ABC có tọa độ các đỉnh là: A (0; 2); B (4; 6) và C (16/3; 14/3).

Các mức hàm mục tiêu là các đường tròn có tâm tại điểm (2; 5). Bình phương của bán kính sẽ là giá trị của hàm mục tiêu. Khi đó hình vẽ cho thấy giá trị nhỏ nhất của hàm mục tiêu đạt được tại điểm H, giá trị lớn nhất tại điểm A hoặc điểm C.

Giá trị của hàm mục tiêu tại điểm A :;

Giá trị của hàm mục tiêu tại điểm C :;

Điều này có nghĩa là giá trị lớn nhất của hàm số đạt được tại điểm A (0; 2) và bằng 13.

Hãy tìm tọa độ điểm H.

Để làm điều này, hãy xem xét hệ thống:

ó

ó

Một đường thẳng là tiếp tuyến của một đường tròn nếu phương trình có nghiệm duy nhất. Phương trình bậc hai có một nghiệm duy nhất nếu số phân biệt là 0.

sau đó ; ; - giá trị nhỏ nhất của hàm.

2) Soạn hàm Lagrange để tìm nghiệm nhỏ nhất:

Tại x 1 =2.5; x 2 =4.5 chúng tôi nhận được:

ó

Hệ thống có một giải pháp cho, tức là thỏa mãn điều kiện cực trị đủ.

Chúng tôi soạn hàm Lagrange để tìm giải pháp tối đa:

Điều kiện đủ cho một điểm cực trị:

Tại x 1 =0; x 2 =2 chúng tôi nhận được:

ó ó

Hệ thống cũng có một giải pháp, tức là thỏa mãn điều kiện cực trị đủ.

Câu trả lời: mức tối thiểu của hàm mục tiêu đạt được tại ; ; hàm mục tiêu tối đa đạt được khi ; .

Nhiệm vụ số 3

Hai doanh nghiệp được cấp vốn với số tiền d các đơn vị. Khi được phân bổ cho doanh nghiệp đầu tiên trong một năm xđơn vị quỹ nó cung cấp thu nhập k 1 xđơn vị, và khi được phân bổ cho doanh nghiệp thứ hai yđơn vị quỹ, nó cung cấp thu nhập k 1 y các đơn vị. Số dư quỹ cuối năm của doanh nghiệp thứ nhất bằng nx, và thứ hai của tôi. Làm thế nào để phân phối tất cả các quỹ trong vòng 4 năm để tổng thu nhập là lớn nhất? Giải quyết vấn đề bằng lập trình động.

i = 8, k = 1.

A = 2200; k 1 = 6; k2 = 1; n = 0,2; m = 0,5.

Dung dịch:

Toàn bộ thời gian 4 năm được chia thành 4 giai đoạn, mỗi giai đoạn bằng một năm. Hãy đánh số các giai đoạn bắt đầu từ năm đầu tiên. Gọi X k và Y k lần lượt là vốn được phân bổ cho các doanh nghiệp A và B ở giai đoạn thứ k. Khi đó tổng X k + Y k = a k là tổng số tiền được sử dụng ở giai đoạn k - đó và còn lại từ giai đoạn trước k - 1. ở giai đoạn đầu tiên, tất cả các quỹ được phân bổ đều được sử dụng và 1 = 2200 đơn vị. thu nhập sẽ nhận được ở giai đoạn k - giai đoạn đó, khi phân bổ đơn vị X k và Y k, sẽ là 6X k + 1Y k. để thu nhập tối đa nhận được ở các giai đoạn cuối cùng bắt đầu từ giai đoạn k - giai đoạn đó là f k (a k) đơn vị. Hãy để chúng tôi viết phương trình Bellman chức năng thể hiện nguyên tắc tối ưu: bất kể trạng thái ban đầu và giải pháp ban đầu giải pháp tiếp theo phải tối ưu đối với trạng thái phát sinh từ trạng thái ban đầu:

Đối với mỗi giai đoạn, bạn cần chọn giá trị X k và giá trị Y k= ak- Xk. Với ý nghĩ này, chúng tôi sẽ tìm thu nhập ở giai đoạn thứ k:

Phương trình Bellman chức năng sẽ giống như sau:

Xem xét tất cả các giai đoạn, bắt đầu với cuối cùng.

(kể từ khi đạt cực đại của hàm tuyến tính ở cuối đoạn là x 4 = a 4);