Thực đơn
trang chủExcel

Phương pháp đồ họa là gì. Phương pháp đồ họa để giải bài toán

Phương pháp đơn giản và rõ ràng nhất để giải quyết vấn đề lập trình tuyến tính(ZLP) là một phương pháp đồ họa. Nó dựa trên việc giải thích hình học của bài toán quy hoạch tuyến tính và được sử dụng để giải ZLP với hai ẩn số:

Chúng ta sẽ xem xét giải pháp của vấn đề này trên máy bay. Mỗi bất đẳng thức của hệ ràng buộc hàm về mặt hình học xác định một nửa mặt phẳng với một đường biên một p x, + + a j2 x 2 = b n i = 1, T.Điều kiện không âm xác định nửa mặt phẳng với các đường biên X (= 0, x 2= 0 tương ứng. Nếu hệ nhất quán thì các nửa mặt phẳng giao nhau tạo thành một phần chung, là một tập lồi và biểu diễn một tập hợp các điểm; tọa độ của từng điểm này là một giải pháp cho hệ thống này. Tập hợp các điểm này được gọi là đa giác giải pháp. Nó có thể là một điểm, một đoạn, một tia, một đa giác giới hạn hoặc không giới hạn.

Về mặt hình học, ZLP là tìm điểm góc của đa giác nghiệm có tọa độ cung cấp giá trị tối đa (tối thiểu) của hàm mục tiêu tuyến tính, Hơn nữa, tất cả các điểm của đa giác nghiệm đều là nghiệm có thể chấp nhận được.

Phương trình đường thẳng mô tả một tập hợp các điểm nằm trên cùng một đường thẳng. Bất đẳng thức tuyến tính mô tả một số vùng trên mặt phẳng.

Hãy xác định phần nào của mặt phẳng mô tả bất đẳng thức 2x (+ 3x2 12.

Đầu tiên, hãy dựng một đường thẳng 2x, + Zx 2 = 12. Đi qua các điểm (6; 0) và (0; 4). Thứ hai, chúng ta xác định nửa mặt phẳng nào thỏa mãn bất đẳng thức. Để thực hiện việc này, hãy chọn bất kỳ điểm nào trên biểu đồ không thuộc đường thẳng và thay tọa độ của nó vào bất đẳng thức. Nếu bất đẳng thức xảy ra thì điểm nhất định là nghiệm chấp nhận được và nửa mặt phẳng chứa điểm thỏa mãn bất đẳng thức. Thật thuận tiện khi sử dụng gốc tọa độ để thay thế vào bất đẳng thức. Hãy thay thế x ( = x 2 = 0 đến bất đẳng thức 2x, + 3x 2 12. Chúng ta có 2 0 + 3 0

Tương tự, bạn có thể mô tả bằng đồ họa tất cả các ràng buộc của một bài toán quy hoạch tuyến tính.

Giải pháp cho mỗi bất đẳng thức của hệ ràng buộc ZLP là một nửa mặt phẳng chứa đường biên và nằm ở một phía của nó. Giao của các nửa mặt phẳng, mỗi nửa mặt phẳng được xác định bởi bất đẳng thức tương ứng của hệ, được gọi là lĩnh vực giải pháp khả thi(ODR) hoặc miền định nghĩa.

Cần phải nhớ rằng miền của các nghiệm khả thi thỏa mãn các điều kiện không âm (Xj > 0, j = 1, P). Tọa độ của bất kỳ điểm nào thuộc miền định nghĩa đều là nghiệm hợp lệ cho bài toán.

Để tìm giá trị cực trị của hàm mục tiêu khi giải ZLP bằng đồ thị, hãy sử dụng vectơ độ dốc, có tọa độ là đạo hàm riêng của hàm mục tiêu:

Vectơ này biểu thị hướng thay đổi nhanh nhất của hàm mục tiêu. Thẳng c [ x l + c 2 x 2 = f(x 0), vuông góc với vectơ gradient là đường mức hàm mục tiêu (Hình 2.2.2). Tại bất kỳ điểm nào trên đường mức, hàm mục tiêu có cùng giá trị. Hãy đánh đồng hàm mục tiêu giá trị hiện có MỘT. Thay đổi ý nghĩa MỘT, chúng ta thu được một họ các đường thẳng song song, mỗi đường thẳng đó là một đường mức của hàm mục tiêu.


Cơm. 2.2.2.

Tài sản quan trọngđường mức hàm tuyến tính là khi đường thẳng song song dịch chuyển sang một bên, mức độ chỉ là tăng và khi chuyển sang phía bên kia - chỉ giảm đi.

Phương pháp đồ họa để giải PLP bao gồm bốn giai đoạn:

  • 1. Xây dựng vùng giải pháp chấp nhận được (ADA) của PLP.
  • 2. Vectơ gradient của hàm mục tiêu (TF) được xây dựng với điểm bắt đầu là điểm x 0(0; 0): V = (s, từ 2).
  • 3. Đường cấp CjXj + c 2 x 2 = a (a - giá trị không đổi) - đường thẳng vuông góc với vectơ gradient V, - di chuyển theo hướng của vectơ gradient trong trường hợp cực đại hóa hàm mục tiêu f(x v x 2) cho đến khi nó rời khỏi ODR. Khi giảm thiểu /(*, x 2)đường mức di chuyển theo hướng ngược lại với vectơ độ dốc. Điểm cực trị (hoặc các điểm) của ODR trong quá trình di chuyển này là điểm tối đa (tối thiểu) f(x pjc 2).

Nếu đường thẳng tương ứng với đường mức không rời khỏi ODR trong quá trình di chuyển thì giá trị tối thiểu (tối đa) của hàm f(x p x 2) không tồn tại.

Nếu đường cấp độ chức năng mục tiêu song song với ràng buộc chức năng của nhiệm vụ mà tại đó giá trị tối ưu CF, thì giá trị CF tối ưu sẽ đạt được tại bất kỳ điểm nào của ràng buộc này nằm giữa hai điểm góc tối ưu và theo đó, bất kỳ điểm nào trong số này đều là nghiệm tối ưu của ZLP.

4. Xác định được tọa độ điểm cực đại (cực tiểu). Để làm được điều này, chỉ cần giải hệ phương trình đường thẳng cho điểm cực đại (tối thiểu) tại giao điểm là đủ. Nghĩa f(x ( , x 2),được tìm thấy tại điểm kết quả là giá trị tối đa (tối thiểu) của hàm mục tiêu.

Tình huống có thể xảy ra giải pháp đồ họa PAP được trình bày trong bảng. 2.2.1.

Bảng 2.2.1

Loại ODR

Loại giải pháp tối ưu

Giới hạn

Quyết định duy nhất

Giải pháp vô tận

Vô hạn

CF không bị giới hạn từ bên dưới

CF không bị giới hạn từ phía trên

Quyết định duy nhất

Giải pháp vô tận

Quyết định duy nhất

Giải pháp vô tận

Ví dụ 2.2.1. Lập kế hoạch sản xuất của doanh nghiệp may (vấn đề về trang phục).

Người ta dự định tung ra hai loại vest - nam và nữ. Bộ đồ của phụ nữ cần 1 m len, 2 m lavsan và 1 ngày lao động; đối với nam giới - 3,5 m len, 0,5 m lavsan và 1 ngày lao động. Tổng cộng có 350 m len, 240 m lavsan và 150 ngày công lao động.

Cần phải xác định cần may bao nhiêu bộ vest mỗi loại để đảm bảo lợi nhuận tối đa nếu lợi nhuận từ việc bán bộ vest nữ là 10 den. đơn vị, và từ nam giới - 20 den. các đơn vị Cần lưu ý rằng cần phải may ít nhất 60 bộ vest nam.

Mô hình kinh tế và toán học của bài toán

Biến: X, - số lượng bộ đồ của phụ nữ; x 2 - số lượng trang phục nam.

Hàm mục tiêu:

Những hạn chế:

Ràng buộc đầu tiên (đối với len) có dạng x (+ 3,5x 2 x (+ 3,5x 2 = 350 đi qua các điểm (350; 0) và (0; 100). Ràng buộc thứ hai (theo lavsan) có dạng 2x (+ 0,5x 2 2x x + 0,5x 2 = 240 đi qua các điểm (120; 0) và (0; 480). Hạn chế thứ ba (về lao động) có hình thức x y + x 2 150. Trực tiếp x (+ x 2 = 150 đi qua các điểm (150; 0) và (0; 150). Ràng buộc thứ tư (về số lượng vest nam) có dạng x 2> 60. Giải bất đẳng thức này là nửa mặt phẳng nằm phía trên đường thẳng x 2 = 60.

Nhờ sự giao nhau của bốn nửa mặt phẳng được xây dựng, chúng ta thu được một đa giác, đây là vùng chứa các lời giải khả thi cho bài toán của chúng ta. Bất kỳ điểm nào trên đa giác này đều thỏa mãn cả bốn bất đẳng thức hàm và đối với bất kỳ điểm nào nằm ngoài đa giác này thì ít nhất một bất đẳng thức sẽ bị vi phạm.

Trong bộ lễ phục. 2.2.3 vùng các giải pháp khả thi (ADA) được tô bóng. Để xác định hướng chuyển động theo hướng tối ưu, chúng ta xây dựng một vectơ gradient V, tọa độ của nó là đạo hàm riêng của hàm mục tiêu:

Để xây dựng một vectơ như vậy, bạn cần nối điểm (10; 20) với gốc tọa độ. Để thuận tiện, bạn có thể xây dựng một vectơ tỷ lệ với vectơ V. Như vậy, trong Hình. 2.2.3 biểu diễn vectơ (30; 60).

Sau đó chúng ta sẽ xây dựng một đường mức 10xj + 20x 2 = MỘT. Chúng ta hãy đánh đồng hàm mục tiêu với một giá trị không đổi MỘT. Thay đổi ý nghĩa MỘT, chúng ta thu được một họ các đường thẳng song song, mỗi đường thẳng đó là một đường mức của hàm mục tiêu.

Phương pháp đồ họa khá đơn giản và trực quan để giải các bài toán quy hoạch tuyến tính hai biến. Dựa theo hình học trình bày các giải pháp khả thi và TF của vấn đề.

Mỗi bất đẳng thức của bài toán quy hoạch tuyến tính (1.2) xác định một nửa mặt phẳng nhất định trên mặt phẳng tọa độ (Hình 2.1), và hệ bất đẳng thức nói chung xác định giao điểm của các mặt phẳng tương ứng. Tập hợp giao điểm của các nửa mặt phẳng này được gọi là lĩnh vực giải pháp khả thi(ODR). ODR luôn đại diện lồi hình, tức là có tính chất sau: nếu hai điểm A và B thuộc hình này thì toàn bộ đoạn AB cũng thuộc hình này. ODR có thể được biểu diễn bằng đồ họa bằng đa giác lồi, diện tích đa giác lồi không giới hạn, một đoạn, một tia hoặc một điểm. Nếu hệ thống ràng buộc trong bài toán (1.2) không nhất quán thì ODS là tập rỗng.

Tất cả những điều trên cũng áp dụng cho trường hợp hệ hạn chế (1.2) bao gồm các đẳng thức, vì mọi đẳng thức

có thể được biểu diễn dưới dạng hệ hai bất đẳng thức (xem hình 2.1)

CF tại giá trị cố định xác định đường thẳng trên mặt phẳng. Bằng cách thay đổi các giá trị của L, chúng ta thu được một họ các đường thẳng song song gọi là đường mức.

Điều này là do thực tế là việc thay đổi giá trị của L sẽ chỉ dẫn đến thay đổi độ dài của đoạn bị cắt bởi đường mức trên trục (tọa độ ban đầu) và hệ số góc của đường thẳng sẽ không đổi (xem Hình 2.1). Do đó, để giải nó, chỉ cần xây dựng một trong các đường mức bằng cách chọn tùy ý giá trị của L là đủ.

Vectơ có tọa độ từ các hệ số CF tại và vuông góc với từng đường mức (xem Hình 2.1). Hướng của vectơ trùng với hướng tăng dần CF, đó là tâm điểmđể giải quyết vấn đề. Phương hướng giảm dần CF ngược chiều với vectơ.

Bản chất của phương pháp đồ họa như sau. Theo hướng (ngược hướng) của vectơ trong ODR, điểm tối ưu được tìm kiếm. Điểm tối ưu là điểm mà đường mức đi qua, tương ứng với giá trị lớn nhất (nhỏ nhất) của hàm. Giải pháp tối ưu luôn nằm ở ranh giới của ODD, chẳng hạn như ở đỉnh cuối cùng của đa giác ODD mà đường mục tiêu sẽ đi qua hoặc trên toàn bộ cạnh của nó.

Khi tìm kiếm lời giải tối ưu cho các bài toán quy hoạch tuyến tính, có thể xảy ra các tình huống sau: có một lời giải duy nhất cho bài toán; có vô số giải pháp (thay thế); TF không bị giới hạn; vùng các giải pháp khả thi là một điểm duy nhất; vấn đề không có giải pháp.

Hình 2.1 Giải thích hình học các ràng buộc và CF của bài toán.

Các phương pháp giải bài toán LP bằng phương pháp đồ thị.

I. Trong ràng buộc của bài toán (1.2), thay dấu bất đẳng thức bằng dấu đẳng thức chính xác và dựng các đường thẳng tương ứng.

II. Tìm và tô màu các nửa mặt phẳng cho phép của mỗi ràng buộc bất đẳng thức của bài toán (1.2). Để làm điều này, bạn cần thay tọa độ của một điểm [ví dụ: (0;0)] vào một bất đẳng thức cụ thể và kiểm tra tính đúng đắn của bất đẳng thức thu được.

Nếu như bất đẳng thức là đúng

Cái đó cần tô bóng nửa mặt phẳng chứa điểm này;

nếu không thì(bất đẳng thức sai) chúng ta phải tô màu nửa mặt phẳng không chứa điểm đã cho.

Vì và phải không âm nên chúng giá trị hợp lệ sẽ luôn ở phía trên trục và ở bên phải trục, tức là trong góc phần tư thứ nhất.

Ràng buộc đẳng thức chỉ cho phép những điểm nằm trên đường thẳng tương ứng. Vì vậy, cần phải đánh dấu những đường thẳng như vậy trên đồ thị.

III. Xác định ODR là một phần của mặt phẳng đồng thời thuộc về tất cả các vùng được phép và chọn nó. Trong trường hợp không có ODD, vấn đề không có giải pháp.

IV. Nếu ODR không phải là tập trống thì bạn cần xây dựng đường mục tiêu, tức là. bất kỳ đường mức nào (trong đó L là số tùy ý, ví dụ: bội số và, tức là thuận tiện cho việc tính toán). Phương pháp xây dựng tương tự như xây dựng các ràng buộc trực tiếp.

V. Xây dựng một vectơ bắt đầu tại điểm (0;0) và kết thúc tại điểm đó. Nếu đường đích và vectơ được xây dựng chính xác thì chúng sẽ vuông góc.

VI. Khi tìm kiếm CF tối đa, bạn cần di chuyển dòng mục tiêu theo hướng vector, khi tìm kiếm CF tối thiểu - chống lại hướng vectơ. Đỉnh cuối cùng của ODR theo hướng chuyển động sẽ là điểm cực đại hoặc cực tiểu của CF. Nếu (các) điểm đó không tồn tại thì chúng ta có thể kết luận rằng TF không giới hạn trên nhiều gói từ phía trên (khi tìm giá trị lớn nhất) hoặc từ bên dưới (khi tìm giá trị nhỏ nhất).

VII. Xác định tọa độ điểm max (min) của bộ lọc số và tính giá trị của bộ lọc số. Để tính tọa độ của điểm tối ưu, cần phải giải hệ phương trình các đường thẳng tại giao điểm của nó.

Phương pháp lập trình tuyến tính (LP) đơn giản và trực quan nhất là phương pháp đồ họa. Nó được sử dụng để giải các bài toán LP có hai biến. Xét bài toán LP ở dạng chuẩn:

tối đa f(x 1 , x 2 , ..., x n) = ,

, tôi = 1, 2, …, m,

x j 0, j = 1, 2, …, n.

Chúng ta hãy đặt n=2 và chúng ta sẽ xem xét vấn đề trên máy bay. Cho hệ bất đẳng thức nhất quán (có ít nhất một nghiệm).

Mỗi bất đẳng thức của hệ này về mặt hình học xác định một nửa mặt phẳng có đường biên a i 1 x 1 + a i 2 x 2 = b i, i = 1, 2, …, m. Các điều kiện không âm xác định các nửa mặt phẳng có các đường thẳng biên lần lượt là x 1 = 0, x 2 = 0. Hệ thống nhất quán, do đó các nửa mặt phẳng, giống như các tập lồi, giao nhau, tạo thành một phần chung, là một tập lồi và là tập hợp các điểm, trong đó tọa độ của mỗi điểm là nghiệm của hệ này. Tập hợp các điểm này được gọi là đa giác nghiệm. Nó có thể là một điểm, một đoạn, một tia, một đa giác giới hạn hoặc không giới hạn.

Do đó, về mặt hình học, ZLP là việc tìm kiếm một điểm như vậy của đa giác nghiệm, tọa độ của nó cung cấp giá trị lớn nhất (tối thiểu) cho hàm tuyến tính của mục tiêu và tất cả các điểm của đa giác nghiệm đều là nghiệm có thể chấp nhận được.

Phương trình tuyến tính mô tả một tập hợp các điểm nằm trên cùng một đường thẳng. Bất đẳng thức tuyến tính mô tả một số vùng trên mặt phẳng. Hãy xác định phần nào của mặt phẳng được mô tả bởi bất đẳng thức 2x 1 + 3x 2 12.

Đầu tiên, hãy dựng một đường thẳng 2x 1 + 3x2= 12. Nó đi qua các điểm (6; 0) và (0; 4). Để xác định nửa mặt phẳng nào thỏa mãn bất đẳng thức, cần chọn điểm bất kỳ trên đồ thị không thuộc đường thẳng và thay tọa độ của nó vào bất đẳng thức. Nếu bất đẳng thức đúng thì điểm đã cho là nghiệm khả thi và nửa mặt phẳng chứa điểm thỏa mãn bất đẳng thức. Để thay thế vào bất đẳng thức, thuận tiện nhất là sử dụng điểm gốc. Thay x 1 = x 2 = 0 vào bất đẳng thức 2x 1 + 3x 2 12. Ta được 2x0 + 3x0 12. Mệnh đề này đúng nên bất đẳng thức 2x 1 + 3x 2 12 tương ứng với nửa mặt phẳng dưới chứa điểm (0; 0). Điều này được phản ánh trong biểu đồ hiển thị trong Hình. 1.1.

Tương tự, tất cả các ràng buộc của bài toán LP có thể được mô tả bằng đồ họa.

Giải pháp cho mỗi bất đẳng thức của hệ ràng buộc ZLP là một nửa mặt phẳng chứa đường biên và nằm ở một phía của nó. Giao của các nửa mặt phẳng, mỗi nửa mặt phẳng được xác định bởi bất đẳng thức tương ứng của hệ, được gọi là vùng nghiệm chấp nhận được hoặc vùng định nghĩa. Cần phải nhớ rằng vùng của các giải pháp khả thi thỏa mãn các điều kiện không âm ( x j 0, j = 1, 2, …, N). Tọa độ của bất kỳ điểm nào thuộc miền định nghĩa đều là nghiệm hợp lệ cho bài toán.

Để tìm giá trị cực trị của hàm mục tiêu khi giải các bài toán LP bằng đồ họa, một vectơ gradient được sử dụng, tọa độ của nó là đạo hàm riêng của hàm mục tiêu, tức là.


Vectơ này biểu thị hướng thay đổi nhanh nhất của hàm mục tiêu. Đường thẳng có 1 x 1 + có 2 x 2 = f(x 0), vuông góc với vectơ gradient, là đường mức của hàm mục tiêu. Tại bất kỳ điểm nào trên đường mức, hàm mục tiêu có cùng giá trị. Chúng ta hãy đánh đồng hàm mục tiêu với một giá trị không đổi "MỘT". Thay đổi giá trị của “a”, chúng ta thu được một họ các đường thẳng song song, mỗi đường thẳng đó là một đường mức của hàm mục tiêu.

Một tính chất quan trọng của đường mức của hàm tuyến tính là khi dịch chuyển song song theo một hướng thì mức chỉ tăng và khi dịch chuyển theo hướng khác thì chỉ giảm.

Từ quan điểm hình học, trong một bài toán quy hoạch tuyến tính, chúng ta đang tìm kiếm một điểm góc hoặc một tập hợp các điểm từ một tập hợp các giải pháp có thể chấp nhận được tại đó đạt tới đường mức cao nhất (thấp nhất), nằm xa hơn (gần) hơn còn lại theo hướng tăng trưởng nhanh nhất.

Phương pháp đồ họa để giải ZLP bao gồm các bước sau.

1. Một vùng đa giác của các giải pháp được chấp nhận (ADS) của PLP được xây dựng.

2. Vectơ gradient của hàm mục tiêu (TF) được xây dựng tại một số điểm x 0 thuộc ODR:

3. Đường mức c 1 x 1 + c 2 x 2 = a (a là giá trị không đổi) - là đường thẳng vuông góc với vectơ gradient - di chuyển theo hướng của vectơ này trong trường hợp cực đại hóa f (x 1, x 2) cho đến khi nó rời khỏi ODR. Điểm (hoặc các điểm) giới hạn của diện tích trong quá trình chuyển động này là điểm cực đại f(x 1, x 2).

4. Để tìm tọa độ của điểm cực đại, chỉ cần giải hai phương trình đường thẳng thu được từ các ràng buộc tương ứng và cho điểm cực đại tại giao điểm là đủ. Giá trị f(x 1, x 2) tìm được tại điểm thu được là giá trị lớn nhất.

Khi cực tiểu hóa (cực đại hóa) hàm f(x 1, x 2), đường mức di chuyển theo hướng ngược lại với vectơ gradient. Nếu đường thẳng tương ứng với đường mức không rời khỏi ODR trong quá trình chuyển động của nó thì giá trị tối thiểu (tối đa) của hàm f(x 1, x 2) không tồn tại.

Nếu đường mức song song với bất kỳ ràng buộc chức năng nào của bài toán thì giá trị tối ưu của CF sẽ đạt được tại bất kỳ điểm nào của ràng buộc này nằm giữa hai điểm góc tối ưu và theo đó, bất kỳ điểm nào trong số này là giải pháp tối ưu của ZLP. Các tình huống có thể xảy ra để giải các bài toán LP bằng đồ họa được trình bày trong Bảng. 1.3.

Bảng 1.3

№ Loại ODR Loại giải pháp tối ưu Ghi chú
Đa giác đóng Quyết định duy nhất
Quyết định duy nhất
Đa giác CF không bị giới hạn từ bên dưới
CF không bị giới hạn từ phía trên
Đa giác mở Quyết định duy nhất
Giải pháp vô tận
Đoạn đường Quyết định duy nhất

Hãy xem xét giải pháp đồ họa của các vấn đề quy hoạch tuyến tính bằng ví dụ sau.

Ví dụ 1.1. Lập kế hoạch sản xuất của doanh nghiệp may (vấn đề về trang phục).

Người ta dự định tung ra hai loại vest - nam và nữ. Bộ đồ của phụ nữ cần 1m len, 2m lavsan và 1 người/ngày lao động. Đối với bộ đồ nam - 3,5 m len, 0,5 m lavsan và 1 người/ngày lao động. Tổng cộng có 350 m len, 240 m lavsan và 150 người/ngày lao động. Cần xác định cần may bao nhiêu bộ vest mỗi loại để đảm bảo lợi nhuận tối đa, nếu lợi nhuận từ việc bán vest nữ là 10 đơn vị tiền tệ và từ vest nam - 20 đơn vị tiền tệ. Cần lưu ý rằng cần phải may ít nhất 60 bộ vest nam.

Chúng ta hãy đưa ra ký hiệu sau: x 1 - số bộ vest nữ; x 2 – số bộ vest nam. Lợi nhuận từ việc bán vest nữ là 10x1 và từ việc bán vest nam - 20x2, tức là. cần cực đại hóa hàm mục tiêu:

10x1 + 20x2

Các ràng buộc của nhiệm vụ có dạng:

x 1 + x 2 150,

2 x 1 + 0,5 x 2 240,

x 1 + 3,5x 2 350,

x 2 60,

x 1 0.

Giới hạn lao động thứ nhất là x 1 + x 2 150. Đường thẳng x 1 + x 2 = 150 đi qua các điểm (150; 0) và (0; 150) (Hình 1.2).

Ràng buộc thứ hai trên lavsan là 2 x 1 + 0,5x 2 240. Đường thẳng 2 x 1 + 0,5x 2 = 240 đi qua các điểm (120; 0) và (0; 480). Giới hạn thứ ba về len x 1 + 3,5x 2 350. Hãy thêm giới hạn thứ tư về số lượng bộ vest nam x 2 60. Nghiệm của bất đẳng thức này là nửa mặt phẳng nằm phía trên đường thẳng x 2 = 60. Trong hình. 1.3 vùng của các giải pháp khả thi được tô bóng. Để xác định hướng chuyển động theo hướng tối ưu, chúng ta xây dựng một vectơ gradient, tọa độ của nó là đạo hàm riêng của hàm mục tiêu, tức là

Để xây dựng một vectơ như vậy, bạn cần nối điểm (10;20) với gốc tọa độ. Khi cực đại hóa hàm mục tiêu cần di chuyển theo hướng của vectơ gradient, còn khi cực tiểu cần di chuyển theo hướng của vectơ gradient. theo hướng ngược lại. Để thuận tiện, bạn có thể xây dựng một vectơ tỷ lệ với vectơ . Vì vậy, trong hình. Hình 1.4 cho thấy vectơ gradient (30;60).

Để xác định hướng chuyển động theo hướng tối ưu, chúng ta xây dựng một vectơ gradient, tọa độ của nó là đạo hàm riêng của hàm mục tiêu, tức là

Trong trường hợp của chúng tôi, chúng tôi sẽ di chuyển đường mức cho đến khi nó rời khỏi vùng có các giải pháp khả thi. Tại điểm cực trị, hàm mục tiêu đạt được cực đại. Để tìm tọa độ của điểm này, chỉ cần giải hai phương trình đường thẳng thu được từ các ràng buộc tương ứng và cho điểm cực đại tại giao điểm là đủ:

x 1 + 3,5x 2 = 350,

x 1 + x 2 = 150.

Từ đây có thể dễ dàng viết ra lời giải cho ZLP ban đầu: tối đa f(x)= 2300 và đạt được ở x 1 = 70 và x 2 = 80 (xem Hình 1.4).

1.3. CÔNG NGHỆ GIẢI QUYẾT BÀI TẬP LẬP TRÌNH TUYẾN TÍNH SỬ DỤNG ADD-ON GIẢI PHÁP TÌM KIẾM TRONG MÔI TRƯỜNG EXCEL

1.3.1. Thông tin chung về làm việc với bảng tính bộ xử lý Excel

Hãy xem xét một số khía cạnh khi làm việc với bộ xử lý bảng tính Excel, điều này sẽ đơn giản hóa các phép tính cần thiết để giải quyết các vấn đề tối ưu hóa. Bộ xử lý bảng là phần mềm, được thiết kế để tự động hóa việc xử lý dữ liệu dạng bảng.

Các phần tử màn hình Excel. Sau đó khởi chạy Excel một bảng xuất hiện trên màn hình, hình thức của bảng này được hiển thị trong Hình 1.5.

Hình ảnh này được gọi là một bảng tính. Đó là một mạng lưới gồm các hàng và cột, các giao điểm của chúng tạo thành các hình chữ nhật gọi là ô. Bảng tính được thiết kế để nhập dữ liệu, thực hiện tính toán, tổ chức cơ sở thông tin, v.v. Cửa sổ Excel hiển thị chính yếu tố phần mềm: thanh tiêu đề, thanh menu, thanh trạng thái, các nút điều khiển cửa sổ.

Làm việc với các công thức. Trong các chương trình bảng tính công thức được sử dụng để thực hiện nhiều phép tính khác nhau. VỚI sử dụng Excel bạn có thể nhanh chóng tạo ra một công thức. Công thức bao gồm ba phần chính:

1) dấu bằng;

2) một tập hợp các giá trị hoặc tham chiếu trong các ô mà phép tính được thực hiện;

3) người vận hành.

4) Nếu không có dấu bằng thì Excel diễn giải dữ liệu không phải dưới dạng công thức mà dưới dạng dữ liệu được nhập vào ô. Công thức có thể được nhập trực tiếp vào một ô hoặc vào thanh công thức - văn bản hoặc số. Trong trường hợp này bạn cần phải làm những hành động sau:

· chọn ô chứa công thức và nhập dấu (=);

· nhập một toán tử hoặc dấu hiệu hành động;

· chọn một ô khác có trong công thức;

· nhấn phím Enter.

Công thức đã nhập sẽ xuất hiện trên thanh công thức và kết quả tính toán sẽ xuất hiện trong ô.

Sử dụng hàm trong công thức Để việc nhập công thức dễ dàng hơn, bạn có thể sử dụng các hàm Excel. Hàm là các công thức được tích hợp sẵn trong Excel. Excel chứa nhiều công thức. Chúng được nhóm theo nhiều loại khác nhau: logic, toán học, kỹ thuật, thống kê, v.v.

Để kích hoạt một công thức cụ thể, hãy nhấp vào nút Chèn, Hàm. Cửa sổ Function Wizard xuất hiện bên trái chứa danh sách các loại hàm. Sau khi chọn loại, danh sách các chức năng sẽ được đặt ở bên phải. Một chức năng được chọn bằng cách nhấp vào tên tương ứng.

Các chức năng khác nhau trình diễn các loại khác nhau tính toán theo những quy luật nhất định. Khi một hàm là một đối tượng duy nhất trong một ô trang tính, nó bắt đầu bằng dấu (=), theo sau là tên của hàm và sau đó là các đối số của hàm, được đặt trong dấu ngoặc đơn.

Tìm giải pháp là một phần bổ trợ của Excel cho phép bạn giải quyết các vấn đề tối ưu hóa. Nếu lệnh Tìm kiếm giải pháp không có trong menu Công cụ thì bạn cần tải xuống tiện ích bổ sung này. Chọn lệnh Công cụ => Tiện ích bổ sung và kích hoạt tiện ích bổ sung Tìm kiếm giải pháp. Nếu add-in này không có trong hộp thoại Add-ons thì bạn cần vào bảng điều khiển Quản lý Windows, hãy nhấp vào biểu tượng Thêm/Xóa Chương trình và sử dụng chương trình cài đặt Excel(hoặc Office) cài đặt phần bổ trợ Tìm kiếm Giải pháp.

Sau khi chọn lệnh Công cụ => Tìm kiếm giải pháp, hộp thoại Tìm kiếm giải pháp sẽ xuất hiện.

Có ba tùy chọn chính trong hộp thoại Tìm giải pháp;

Đặt ô mục tiêu.

Thay đổi tế bào.

Những hạn chế.

Đầu tiên bạn cần điền vào trường Đặt ô mục tiêu. Trong tất cả các tác vụ của công cụ Tìm giải pháp, kết quả ở một trong các ô trang tính đều được tối ưu hóa. Ô đích có liên quan đến các ô khác trong bảng tính đó bằng cách sử dụng các công thức. Công cụ Tìm Giải pháp sử dụng các công thức tạo ra kết quả trong ô đích để kiểm tra phương pháp khả thi. Bạn có thể chọn tìm kiếm nhỏ nhất hoặc giá trị cao nhất cho ô mục tiêu hoặc đặt một giá trị cụ thể.

Thứ hai tham số quan trọng Công cụ Tìm Giải pháp là tùy chọn Thay đổi Ô. Tại đây bạn chỉ định các ô có giá trị sẽ được thay đổi để tối ưu hóa kết quả trong ô đích. Bạn có thể chỉ định tối đa 200 ô có thể thay đổi để tìm giải pháp. Có hai yêu cầu chính đối với các ô này: chúng không được chứa công thức và những thay đổi về giá trị của chúng phải được phản ánh trong sự thay đổi kết quả trong ô đích. Nói cách khác, ô đích phụ thuộc vào ô được sửa đổi.

Tham số thứ ba phải được nhập vào tab Tìm kiếm giải pháp là các hạn chế.

Để giải quyết vấn đề bạn cần:

1) cho biết địa chỉ của các ô sẽ đặt kết quả của quyết định (các ô có thể thay đổi);

2) nhập dữ liệu ban đầu;

3) đưa ra sự phụ thuộc của hàm mục tiêu;

4) giới thiệu các phụ thuộc cho các hạn chế,

5) chạy lệnh Tìm kiếm giải pháp;

6) gán một ô cho hàm đích (đặt ô đích);

7) đưa ra các hạn chế;

8) nhập các tham số để giải PLP.

Hãy xem xét giải pháp công nghệ sử dụng các điều kiện của Ví dụ 1.1 (bài toán phù hợp).

Mô hình kinh tế và toán học của bài toán

Gọi x 1 là số bộ vest nữ; x 2 - số lượng bộ vest nam,

tối đa 10 x x 1 + 20 x x 2

Các ràng buộc của nhiệm vụ có dạng:

x 1 + x 2 150 - giới hạn lao động;

2 x x 1 + 0,5 x X 2.240 - giới hạn lavsan;

x 1 + 3,5 x x 2 350 - giới hạn len;

x 2 60 - giới hạn đối với bộ vest nam;

x 1 0 - hạn chế đối với trang phục của phụ nữ.

1. Chỉ định địa chỉ của các ô sẽ đặt kết quả giải pháp (các ô có thể thay đổi).

Ký hiệu x 1, x 2 là số lượng bộ quần áo của mỗi loại. Trong bài toán của chúng ta, các giá trị tối ưu của vectơ = (x 1, x 2) sẽ được đặt trong các ô A2:B2, giá trị tối ưu của hàm mục tiêu - trong ô S3.

2. Nhập dữ liệu ban đầu.

Nhập dữ liệu nhiệm vụ ban đầu như trong Hình. 1.6.

3. Giới thiệu phần phụ thuộc của hàm mục tiêu.

· Đặt con trỏ vào ô “Tây Bắc”, ô đó sẽ được chọn.

· Đặt con trỏ vào nút Function Wizard nằm trên thanh công cụ.

· Nhập Nhập. Hộp thoại Function Wizard bước 1/2 xuất hiện trên màn hình.

· Trong cửa sổ Chức năng, chọn dòng TÓM TẮT (Hình 1.7). Trên màn hình

· Hộp thoại TỔNG HỢP xuất hiện (Hình 1.8).

· Nhập vào dòng Mảng 1 A2:B2.

· Nhập AZ:VZ vào dòng Mảng 2.

Mảng 1 sẽ được sử dụng khi nhập các phụ thuộc cho các ràng buộc nên trên mảng này bạn cần thực hiện liên kết tuyệt đối. Trong bộ lễ phục. Hình 1.9 cho thấy một hàm đã được đưa vào ô SZ.

5. Nhập các phụ thuộc cho các ràng buộc (Hình 1.10).

· Đặt con trỏ vào ô NW.

· Trên thanh công cụ có nút Copy to Clipboard.

· Đặt con trỏ vào ô C4.

· Đặt con trỏ vào ô C5.

· Trên thanh công cụ, nút Dán từ Clipboard.

· Đặt con trỏ vào ô Sat.

· Trên thanh công cụ, nút Dán từ Clipboard.

· Đặt con trỏ vào ô C7.

· Trên thanh công cụ, nhấp vào nút Dán từ Clipboard. (Nội dung của các ô C4-C7 phải được kiểm tra. Chúng phải chứa thông tin, như minh họa trong Hình 1.11; nội dung của ô C5 được trình bày làm ví dụ.)

· Tại dòng Menu đặt con trỏ chuột vào Service. Trong menu mở rộng, chọn lệnh Tìm kiếm giải pháp. Hộp thoại Tìm kiếm Giải pháp xuất hiện (Hình 1.12).

5. Chạy lệnh Tìm kiếm giải pháp.

6. Gán một ô cho hàm đích (đặt ô đích), cho biết địa chỉ các ô cần thay đổi.

· Đặt con trỏ vào dòng Đặt ô mục tiêu.

· Nhập địa chỉ ô $С$3.

· Nhập loại hàm mục tiêu tùy theo điều kiện của bài toán. Để thực hiện việc này, hãy lưu ý hàm mục tiêu bằng - Giá trị tối đa hoặc Giá trị tối thiểu.

· Đặt con trỏ vào một hàng bằng cách thay đổi ô.

· Nhập địa chỉ của các biến yêu cầu A$2:B$2 (Hình 1.13).

7. Đưa ra những hạn chế.

· Đặt con trỏ chuột vào nút Thêm. Hộp thoại Thêm ràng buộc xuất hiện.

· Nhập biển báo hạn chế.

· Tại dòng Hạn chế, nhập địa chỉ $D$4 (Hình 1.14).

· Đặt con trỏ chuột vào nút Thêm. Hộp thoại Thêm hạn chế sẽ xuất hiện lại.

· Nhập các ràng buộc còn lại của bài toán bằng thuật toán mô tả ở trên.

· Sau khi dùng thuốc hạn chế cuối cùng Bấm vào nút OK. Hộp thoại Tìm kiếm Giải pháp với các điều kiện đã nhập sẽ xuất hiện trên màn hình (Hình 1.15).

8. Nhập các tham số để giải bài toán quy hoạch tuyến tính.

· Trong hộp thoại, đặt con trỏ chuột vào nút Options. Hộp thoại Tùy chọn Tìm kiếm Giải pháp sẽ xuất hiện trên màn hình (Hình 1.16).

· Đặt hộp kiểm trong windows mô hình tuyến tính(điều này sẽ đảm bảo việc sử dụng phương pháp đơn hình) và các giá trị Không âm.

· Đặt con trỏ chuột vào nút OK. Hộp thoại Tìm kiếm Giải pháp sẽ xuất hiện trên màn hình.

· Đặt con trỏ chuột vào nút Run.

Sau một thời gian ngắn, hộp thoại Kết quả Tìm kiếm Giải pháp và bảng ban đầu chứa các ô AZ:VZ được điền cho các giá trị x i và ô SZ có giá trị lớn nhất của hàm mục tiêu sẽ xuất hiện (Hình 1.17).

Nếu bạn chỉ định loại báo cáo Độ ổn định, bạn có thể nhận thêm thông tin về giải pháp tối ưu (Hình 1.18).

Kết quả của việc giải quyết vấn đề là đã nhận được câu trả lời: cần phải may 70 miếng. bộ vest nữ và 80 chiếc. bộ đồ nam để có được lợi nhuận tối đa 2300 USD.

1.4. Tính đối ngẫu trong các bài toán lập trình tuyến tính. PHÂN TÍCH GIẢI PHÁP TỐI ƯU ĐẠT ĐƯỢC

Năm 1975, đồng hương của chúng tôi L.V. Kantorovich đã được trao giải Nobel Kinh tế (cùng với nhà kinh tế học người Mỹ T. Koopmans) vì đã phát triển lý thuyết sử dụng tối ưu nguồn lực (xem Phụ lục 1).

Mỗi bài toán quy hoạch tuyến tính có liên quan chặt chẽ với một bài toán khác vấn đề tuyến tính, được gọi là kép; vấn đề ban đầu được gọi là nguyên bản hoặc trực tiếp. Mối liên hệ giữa bài toán gốc và bài toán kép đặc biệt nằm ở chỗ lời giải của một trong số chúng có thể thu được trực tiếp từ lời giải của bài toán kia.

Biến vấn đề kép y được gọi là ước tính được xác định một cách khách quan, hay ước tính kép, hay “giá” của tài nguyên, hay giá bóng.

Mỗi bài toán cặp đôi thực sự là một bài toán quy hoạch tuyến tính độc lập và có thể được giải độc lập với bài toán kia.

Bài toán đối ngẫu liên quan đến bài toán ban đầu được soạn theo các quy tắc sau:

1) hàm mục tiêu vấn đề ban đầuđược xây dựng ở mức tối đa và hàm mục tiêu của bài toán kép được xây dựng ở mức tối thiểu, trong khi ở bài toán tối đa, tất cả các bất đẳng thức trong ràng buộc hàm đều có dạng (), trong bài toán tối thiểu - dạng ( );

2) ma trận A, bao gồm các hệ số cho các ràng buộc chưa biết trong hệ thống của bài toán ban đầu và ma trận A T tương tự trong bài toán kép được lấy từ nhau bằng cách hoán vị;

3) số biến trong bài toán kép bằng số ràng buộc hàm trong bài toán ban đầu và số ràng buộc trong hệ của bài toán kép bằng số biến trong bài toán ban đầu;

4) các hệ số của ẩn số trong hàm mục tiêu của bài toán đối ngẫu là các số hạng tự do trong hệ ràng buộc của bài toán ban đầu, vế phải trong các ràng buộc của bài toán đối ngẫu là các hệ số của ẩn số trong bài toán đối ngẫu. chức năng khách quan của bản gốc; j 0.

Hai bài toán được trình bày tạo thành một cặp bài toán đối ngẫu. Những phát biểu chính về các vấn đề đối ngẫu lẫn nhau được chứa đựng trong hai định lý sau đây.

Định lý nhị nguyên đầu tiên. Đối với các vấn đề đối ngẫu lẫn nhau, một trong các trường hợp loại trừ lẫn nhau xảy ra.

1. Trong bài toán trực tiếp và bài toán kép đều có lời giải tối ưu,
trong trường hợp này, các giá trị của hàm mục tiêu trên nghiệm tối ưu
cuộc thi đấu

2. Trong bài toán trực tiếp, tập hợp được chấp nhận không rỗng và hàm mục tiêu của tập hợp này không bị chặn ở trên. Trong trường hợp này, bài toán đối ngẫu sẽ có tập chấp nhận được trống.

3. Trong bài toán đối ngẫu, tập hợp chấp nhận được không trống và hàm mục tiêu của tập hợp này không bị chặn từ dưới lên. Trong trường hợp này, tập chấp nhận được của bài toán trực tiếp hóa ra là tập rỗng.

4. Cả hai bài toán đang xét đều có tập chấp nhận được trống.

Định lý đối ngẫu thứ hai (định lý không cứng nhắc bổ sung). Hãy để = ( x 1 , x 2,..., x n) là nghiệm chấp nhận được của bài toán trực tiếp, a = (y 1,y 2,...,y t) là nghiệm chấp nhận được của bài toán đối ngẫu. Để chúng trở thành lời giải tối ưu cho các bài toán trực tiếp và bài toán kép, điều cần thiết và đủ là các mối quan hệ sau đây:

(1.4)

(1.5)

Điều kiện (1.4) và (1.5) cho phép, biết giải pháp tối ưu một trong những vấn đề kép, tìm giải pháp tối ưu cho vấn đề khác.

Chúng ta hãy xem xét một định lý khác, kết luận của nó sẽ được sử dụng sau này.

Định lý ước lượng. Các giá trị của các biến y i trong lời giải tối ưu của bài toán đối ngẫu biểu diễn ước lượng ảnh hưởng của các số hạng tự do b i của hệ ràng buộc (bất đẳng thức) của bài toán trực tiếp lên giá trị

Quyết định ZLP sử dụng phương pháp đơn giản, chúng tôi đồng thời giải quyết ZLP kép. Các biến của bài toán kép y i được gọi là ước lượng xác định khách quan.

Chúng ta hãy xem xét cách diễn giải kinh tế của bài toán kép bằng cách sử dụng bài toán tấm thảm làm ví dụ.

ví dụ 1 .2. Sử dụng phát biểu về vấn đề của tấm thảm, hãy hoàn thành các nhiệm vụ sau.

1. Xây dựng mô hình toán kinh tế của bài toán thảm để có tổng chi phí sản xuất tối đa, sử dụng số liệu trong Bảng. 1.1.

2. Sử dụng Tìm kiếm giải pháp, tìm kế hoạch sản xuất sao cho tổng chi phí sản xuất đạt mức tối đa.

3. Xây dựng mô hình toán kinh tế của bài toán đối ngẫu với bài toán tấm thảm.

4. Tìm phương án tối ưu cho bài toán đối ngẫu, sử dụng định lý đối ngẫu, giải thích đẳng thức về 0 của X 1 và X 4.

5. Sử dụng các giao thức Tìm kiếm Giải pháp, thực hiện phân tích giải pháp tối ưu thu được cho vấn đề ban đầu.

6. Xác định tổng chi phí và kế hoạch sản xuất sẽ thay đổi như thế nào khi tuổi thọ đường ống tăng thêm 12 đơn vị.

1. Chúng ta hãy xây dựng mô hình kinh tế và toán học của bài toán.

Ta ký hiệu X 1, X 2, X 3, X 4 số lượng thảm mỗi loại. Hàm mục tiêu có dạng

F(X) = 3X 1 + 4X 2 + 3X 3 + X 4 tối đa,

và hạn chế về nguồn lực

7Х 1 + 2Х 2 + 2Х 3 + 6X4 80,

5Х 1 + 8Х 2 + 4 X3 + ZH 4 480,

2X 1 + 4 X 2 + X 3 + 8X 4 130,

X1, X2, X3, X4 0.

2. Tìm kiếm kế hoạch phát hành tối ưu.

Hãy giải quyết vấn đề bằng cách sử dụng tiện ích bổ sung Tìm kiếm Excel các giải pháp. Công nghệ giải quyết vấn đề đã được thảo luận chi tiết trong bài toán trang phục. Trong bài toán của chúng ta, các giá trị tối ưu của vectơ X = (X 1, X 2, X 3, X 4) sẽ được đặt trong các ô VZ:EZ, giá trị tối ưu của hàm mục tiêu - trong ô F4.

Hãy nhập dữ liệu ban đầu. Đầu tiên, chúng ta mô tả hàm mục tiêu bằng hàm - SUMPRODVEL (Hình 1.19). Và sau đó chúng ta sẽ nhập dữ liệu cho các phần bên trái của hạn chế. Trong phần Tìm lời giải, chúng ta sẽ nhập hướng của hàm mục tiêu, địa chỉ của các biến cần tìm và thêm các ràng buộc. Hộp thoại Tìm kiếm Giải pháp với các điều kiện đã nhập sẽ xuất hiện trên màn hình (Hình 1.20).

Sau khi nhập các thông số để giải bài toán, nhấn nút Thực thi. Một thông báo sẽ xuất hiện trên màn hình cho biết giải pháp đã được tìm thấy (Hình 1.21).

Giải pháp thu được có nghĩa là thu nhập tối đa là 150 nghìn rúp. một nhà máy có thể nhận được 30 tấm thảm loại thứ hai và 10 tấm thảm loại thứ ba khi sản xuất. Trong trường hợp này, nguồn lực “lao động” và “thiết bị” sẽ được sử dụng hết và trong số 480 kg sợi (tài nguyên “nguyên liệu thô”) sẽ được sử dụng 280 kg.

Tạo báo cáo dựa trên kết quả tìm kiếm giải pháp. Excel cho phép trình bày kết quả tìm kiếm giải pháp dưới dạng báo cáo (Bảng 1.4). Có ba loại báo cáo như vậy:

· Kết quả (Trả lời). Báo cáo bao gồm các giá trị ban đầu và cuối cùng của ô đích và ô được sửa đổi cũng như thông tin bổ sung về các hạn chế.

· Tính ổn định (Độ nhạy). Một báo cáo chứa thông tin về độ nhạy của giải pháp đối với những thay đổi nhỏ trong các ô đang được sửa đổi hoặc trong các công thức ràng buộc.

· Hạn mức. Ngoài bản gốc và giá trị cuối cùng các ô đang được sửa đổi và các ô mục tiêu, báo cáo bao gồm các giới hạn trên và dưới của các giá trị mà các ô ảnh hưởng có thể chấp nhận nếu đáp ứng các ràng buộc.

Trước tiên hãy xem xét trường hợp đơn giản nhất, khi có chính xác hai biến được đưa vào ZLP:

Mỗi bất đẳng thức (a)-(b) của hệ ràng buộc của bài toán (3.8) về mặt hình học xác định một nửa mặt phẳng tương ứng với các đường thẳng biên X 1 = 0 và X 2 = 0. Mỗi đường biên chia mặt phẳng x 1 Ox 2 thành hai nửa mặt phẳng. Tất cả nghiệm của bất đẳng thức ban đầu đều nằm ở một trong các nửa mặt phẳng được tạo thành (tất cả các điểm của nửa mặt phẳng) và do đó, việc thay tọa độ của bất kỳ điểm nào của nó vào bất đẳng thức tương ứng sẽ biến nó thành một đẳng thức thực sự. Khi tính đến điều này, nửa mặt phẳng trong đó nghiệm của bất đẳng thức nằm trong đó được xác định, tức là bằng cách chọn bất kỳ điểm nào từ nửa mặt phẳng bất kỳ và thay tọa độ của nó vào bất đẳng thức tương ứng. Nếu bất đẳng thức đúng với một điểm cho trước thì nó đúng với bất kỳ điểm nào khác trên cùng một nửa mặt phẳng. Ngược lại, nghiệm của bất đẳng thức nằm ở một nửa mặt phẳng khác.

Nếu hệ bất đẳng thức (a)-(b) là nhất quán thì miền nghiệm của nó là tập hợp các điểm thuộc tất cả các nửa mặt phẳng được chỉ định. Vì tập giao điểm của các nửa mặt phẳng này là lồi nên tập nghiệm chấp nhận được của bài toán (3.8) là một tập lồi, được gọi là đa giác nghiệm (thuật ngữ được giới thiệu trước đó “đa diện nghiệm” thường được sử dụng nếu n 3 ). Các cạnh của đa giác này nằm trên các đường thẳng, phương trình của chúng thu được từ hệ thống gốc hạn chế bằng cách thay thế dấu bất đẳng thức bằng dấu đẳng thức chính xác.

Do đó, ZLP ban đầu bao gồm việc tìm một điểm trong đa giác quyết định mà tại đó hàm mục tiêu F đạt giá trị lớn nhất (tối thiểu).

Điểm này tồn tại khi đa giác nghiệm không trống và hàm mục tiêu trên đó được giới hạn từ phía trên. Trong các điều kiện xác định, tại một trong các đỉnh của đa giác nghiệm, hàm mục tiêu sẽ đạt giá trị lớn nhất. Để xác định đỉnh này, hãy dựng một đường mức L: c 1 x 1 +c 2 x 2 =h (trong đó h là một hằng số nào đó), vuông góc với vectơ gradient và đi qua đa giác nghiệm và di chuyển nó song song dọc theo vectơ gradient cho đến khi nó đi qua giao điểm chung cuối cùng của nó với đa giác nghiệm (khi dựng vectơ gradient, một điểm (c 1 ; c 2) được đặt trong mặt phẳng x 1 Ox 2 và một đoạn có hướng được vẽ tới nó từ gốc tọa độ). Tọa độ của điểm được chỉ định sẽ xác định phương án tối ưu cho nhiệm vụ này.

Tóm tắt tất cả những điều trên, chúng tôi trình bày một thuật toán cho phương pháp đồ họa để giải ZLP.

Thuật toán cho phương pháp đồ họa giải ZLP

1. Xây dựng đa giác nghiệm xác định theo hệ thống giới hạn của ZLP gốc.


2. Nếu đa giác được dựng của các nghiệm là một tập rỗng thì ZLP ban đầu không có nghiệm nào. Ngược lại, hãy xây dựng một vectơ gradient và thực hiện bất kỳ dòng nào mức L, di chuyển khi giải bài toán đến mức tối đa theo hướng của vectơ (hoặc theo hướng hướng ngược lạiđối với bài toán cực tiểu) xác định điểm cực trị của đa giác nghiệm, tại đó đạt được cực đại (cực tiểu) của hàm mục tiêu của bài toán.

3. Tính tọa độ điểm tối ưu tìm được , giải hệ phương trình gồm hai đường biên cắt nhau trong đó.

4. Bằng cách thay thế nghiệm tối ưu tìm được vào hàm mục tiêu của bài toán, hãy tính giá trị tối ưu của nó, tức là: .

Tại xây dựng đồ họa của tập nghiệm chấp nhận được của PLP (đa giác nghiệm), có thể xảy ra các trường hợp sau.

Trong bài học này chúng ta sẽ làm quen với phương pháp đồ họa các giải pháp các bài toán quy hoạch tuyến tính, tức là những bài toán cần tìm lời giải của hệ phương trình tuyến tính và (hoặc) bất đẳng thức (hệ ràng buộc) trong đó hàm mục tiêu - hàm tuyến tính - nhận giá trị tối ưu.

Do thực tế là sự rõ ràng của giải pháp đồ họa chỉ đạt được trên mặt phẳng, chúng ta có thể làm quen với biểu diễn đồ họa chỉ có vấn đề trong không gian hai chiều. Biểu diễn này phù hợp với hệ ràng buộc bất đẳng thức có hai biến hoặc cho hệ phương trình trong đó số biến lớn hơn số phương trình 2, nghĩa là số biến tự do là hai.

Do đó, phương pháp đồ họa có phạm vi ứng dụng hẹp đến mức không thể coi nó là một phương pháp đặc biệt để giải các bài toán quy hoạch tuyến tính.

Tuy nhiên, để sản xuất biểu diễn trực quanĐể giải các bài toán quy hoạch tuyến tính, phương pháp đồ họa được quan tâm. Ngoài ra, nó cho phép chúng ta xác nhận tính hợp lệ về mặt hình học định lý quy hoạch tuyến tính .

Cơ sở lý thuyết của phương pháp đồ họa

Vì vậy, đây là một bài toán quy hoạch tuyến tính. Cần tìm giá trị không âm của các biến và thỏa mãn hệ bất đẳng thức

tại đó dạng tuyến tính đạt giá trị tối ưu.

Ví dụ 3.

Ví dụ 4. Giải bài toán quy hoạch tuyến tính bằng phương pháp đồ họa trong đó bạn cần tìm giá trị nhỏ nhất của hàm dưới các ràng buộc

Chúng ta tiếp tục giải quyết các vấn đề bằng phương pháp đồ họa cùng nhau

Các kết luận đạt được cho đến nay đều dựa trên thực tế là tập nghiệm của một bài toán quy hoạch tuyến tính được cấu hình sao cho giải pháp tối ưu là hữu hạn và duy nhất. Bây giờ hãy xem các ví dụ trong đó điều kiện này bị vi phạm. Trong các ví dụ này, đa giác nghiệm được xây dựng như trong các ví dụ trước; chúng ta hãy tập trung vào các đặc điểm để phân biệt các ví dụ đặc biệt này.

Ví dụ 5. Giải bài toán quy hoạch tuyến tính bằng phương pháp đồ họa trong đó bạn cần tìm giá trị lớn nhất của hàm dưới các ràng buộc

Giải pháp. Hình vẽ cho thấy: vùng giải đa diện không giới hạn cho hệ ràng buộc này, đường mức ban đầu (màu đen), vectơ (màu đỏ tía) biểu thị hướng chuyển động của đường mức ban đầu để tìm cực đại của hàm mục tiêu.

Dễ dàng nhận thấy rằng hàm F có thể tăng không giới hạn với hệ thống nhất định hạn chế, vì vậy chúng ta có thể viết điều kiện đó .

Ví dụ 6. Giải bài toán quy hoạch tuyến tính bằng phương pháp đồ họa trong đó bạn cần tìm giá trị lớn nhất của hàm dưới các ràng buộc