Ví dụ về phương pháp đồ họa Zlp. Phương pháp đồ họa để giải các bài toán quy hoạch tuyến tính: sơ đồ và ví dụ

Phương pháp đồ thị để giải ZLP dựa trên các phát biểu trong đoạn 2.1. Theo Định lý 2, lời giải tối ưu nằm trên cùng của miền lời giải khả thi và do đó để giải ZLP là tìm đỉnh của miền lời giải khả thi, tọa độ của nó cho giá trị tối ưu hàm mục tiêu.

Phương pháp đồ họa được sử dụng để giải một lớp giới hạn các bài toán có hai biến, đôi khi có ba biến. Cần lưu ý rằng đối với ba biến, phạm vi này chưa đủ rõ ràng.

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

Chúng ta sẽ xem xét việc triển khai phương pháp đồ họa để giải ZLP bằng các ví dụ.

Ví dụ 2.2.1. Quyết định đồ họa ZLP phương pháp:

(2.2.1)

tối đa z=x 1 + 4x 2 (2.2.2)

Giải pháp.Để xây dựng một vùng nghiệm khả thi gồm giao của các nửa mặt phẳng ứng với từng bất đẳng thức của hệ ràng buộc (2.2.1), ta viết phương trình các đường thẳng biên:

tôi 1: x 1 + 5x 2 = 5; tôi 2: x 1 + x 2 = 6; tôi 3: 7x 1 + x 2 = 7.

tôi 1 thành dạng (2.2.3.) ta chia cả hai phần của nó cho 5:
. Như vậy, thẳng tôi 1 vết cắt trên trục Ồ 1 5 đơn vị, trên trục Ồ 2 1 đơn vị. Tương tự ta có cho tôi 2:
Và tôi 3:
.

Để xác định các nửa mặt phẳng thỏa mãn ràng buộc của hệ (2.2.1), cần thay tọa độ của điểm bất kỳ không nằm trên đường biên vào ràng buộc. Nếu chúng ta thu được một bất đẳng thức thực thì mọi điểm trên nửa mặt phẳng này đều là nghiệm của bất đẳng thức này. Ngược lại, chọn một nửa mặt phẳng khác.

Do đó, nửa mặt phẳng mong muốn thứ nhất và thứ hai nằm ở hướng ngược lại so với gốc tọa độ (0 – 5 0 - 5; 7 0 + 0 7), và giây – về gốc tọa độ (0 + 0 6). Vùng các giải pháp khả thi trong Hình 2.2.1 được tô đậm.

Hình 2.2.1 – Phạm vi các giải pháp khả thi

Để tìm ra phương án tối ưu nằm ở đỉnh của đa giác nghiệm, bạn cần xây dựng một vectơ chỉ hướng
=(Với 1 ,Với 2), cho biết hướng tăng lớn nhất của hàm mục tiêu z=Với 1 X 1 +Với 2 X 2 .

Trong bài toán này, vectơ chỉ phương
= (1, 4): bắt đầu tại điểm VỀ(0,0) và kết thúc tại điểm N(1, 4).

Tiếp theo, ta dựng đường thẳng đi qua miền nghiệm khả thi, vuông góc với vectơ và gọi là đường mức mục tiêu chức năng. Chúng ta di chuyển đường mức theo hướng của vectơ trong trường hợp cực đại hóa hàm mục tiêu z và theo hướng ngược lại, trong trường hợp giảm thiểu z, cho đến giao điểm cuối cùng với vùng giải pháp khả thi. Kết quả là, một hoặc nhiều điểm được xác định khi hàm mục tiêu đạt giá trị cực trị hoặc tính không giới hạn của hàm mục tiêu được thiết lập z về tập hợp các giải pháp cho vấn đề.

Như vậy, điểm cực đại của hàm mục tiêu z là điểm MỘT giao điểm đường tôi 2 và tôi 3 .

Để tính giá trị tối ưu của hàm mục tiêu z tìm tọa độ của điểm MỘT . Kể từ thời điểm MỘT là giao điểm của các đường tôi 2 và tôi 3 thì tọa độ của nó thỏa mãn hệ phương trình gồm phương trình của các đường biên tương ứng:

Vì vậy, điểm MỘT có tọa độ x 1 =1/6, x 2 = 35/6.

Để tính giá trị tối ưu của hàm mục tiêu, bạn cần thay tọa độ của điểm vào đó MỘT .

Thay tọa độ của điểm MỘT vào hàm mục tiêu (2.4), ta thu được

tối đa z = 1/6 + 4·(35/6) = 47/2.

Ví dụ 2.2.2. Xây dựng trên mặt phẳng vùng nghiệm khả thi của hệ bất đẳng thức tuyến tính (2.2.4) và tìm giá trị lớn nhất, nhỏ nhất của hàm mục tiêu (2.2.5):

(2.2.4)

z= –2x 1 –x 2 (2.2.5)

Giải pháp.Để xây dựng một vùng nghiệm khả thi gồm giao của các nửa mặt phẳng ứng với từng bất đẳng thức của hệ ràng buộc (2.2.4), ta viết phương trình các đường thẳng biên:

tôi 1: 4x 1 – x 2 = 0; tôi 2: x 1 + 3x 2 = 6; tôi 3: x 1 – 3x 2 = 6; tôi 4: x 2 = 1.

Thẳng tôi 1 đi qua điểm có tọa độ (0;0). Để xây dựng nó, chúng tôi bày tỏ x 2 đến x 1: x 2 = 4x 1 . Hãy tìm một điểm khác mà đường thẳng đi qua tôi 1, ví dụ (1;4). Qua điểm có tọa độ (0;0) và điểm có tọa độ (1;4) ta vẽ đường thẳng tôi 1 .

Để rút gọn phương trình đường thẳng tôi 2 thành dạng các đoạn trên trục (2.2.3), ta chia cả hai phần của nó cho 6:
. Như vậy, thẳng tôi 2 vết cắt trên trục Ồ 1 6 đơn vị, trên trục Ồ 2 - 2 chiếc. Tương tự ta có cho tôi 3:
và trực tiếp tôi 4 song song với trục Ồ 1 và đi qua điểm có tọa độ (0;1) .

Để xác định các nửa mặt phẳng thỏa mãn ràng buộc của hệ (2.2.4), cần thay tọa độ của điểm bất kỳ không nằm trên đường biên vào ràng buộc. Do những hạn chếX 1 0, X 2 0, vùng nghiệm chấp nhận được của ZLP nằm ở 1/4 mặt phẳng tọa độ.

VỀ
vùng các giải pháp khả thi trên Hình 2.2.2 được tô đậm.

Hình 2.2.2 – Phạm vi các giải pháp khả thi

Hãy xây dựng một vectơ chỉ hướng
= (–2,–1). Tiếp theo, chúng ta xây dựng một đường mức vuông góc với vectơ .

Để tìm giá trị cao nhất của hàm mục tiêu, ta di chuyển đường mức theo hướng của vectơ cho đến giao điểm cuối cùng với vùng nghiệm khả thi. Như vậy, điểm cực đại của hàm mục tiêu z là điểm MỘT(giao điểm của đường tôi 1 và tôi 2).

Để tính giá trị tối ưu của hàm mục tiêu z tìm tọa độ của điểm MỘT. Kể từ thời điểm MỘT là giao điểm của các đường tôi 1 và tôi 2 thì tọa độ của nó thỏa mãn hệ phương trình gồm các phương trình của đường biên tương ứng:

Vì vậy, điểm MỘT có tọa độ x 1 =6/13, x 2 = 24/13.

Thay tọa độ của điểm MỘT vào hàm mục tiêu (2.2.5), ta thu được giá trị tối ưu của hàm mục tiêu

tối đa z= – 2·(6/13) – (24/13) = – 36/13.

Để tìm giá trị nhỏ nhất của hàm mục tiêu, ta di chuyển đường mức theo hướng ngược với vectơ cho đến giao điểm cuối cùng với vùng nghiệm khả thi. Trong trường hợp này, hàm mục tiêu là không giới hạn trong miền các giải pháp khả thi, tức là ZLP không có mức tối thiểu.

Do quyết định của PPP, có thể xảy ra các trường hợp sau:

Hàm mục tiêu đạt giá trị tối ưu tại một đỉnh của đa giác nghiệm;

Hàm mục tiêu đạt giá trị tối ưu tại bất kỳ điểm nào trên cạnh của đa giác nghiệm (ZLP có các sơ đồ tham chiếu thay thế có cùng giá trị z );

PAP không có kế hoạch tối ưu;

ZLP có một kế hoạch tối ưu trong trường hợp có nhiều giải pháp khả thi không giới hạn.

Nhiệm vụ. Giải quyết vấn đề bằng đồ họa lập trình tuyến tính, sau khi xác định được giá trị cực trị của hàm mục tiêu:

dưới những hạn chế

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

Hãy xây dựng phương trình 3x 1 +x 2 = 9 tại hai điểm.
Để tìm điểm thứ nhất, ta đánh phương x 1 = 0. Ta tìm x 2 = 9. Để tìm điểm thứ hai, ta đánh phương x 2 = 0. Ta tìm x 1 = 3. Ta nối điểm (0;9) với (3;0) bằng một đường thẳng. Chúng ta hãy định nghĩa nửa mặt phẳng được xác định bởi bất đẳng thức. Sau khi chọn điểm (0; 0), chúng ta xác định dấu bất đẳng thức trong nửa mặt phẳng: 3. 0 + 1 . 0 - 9 0, tức là 3x 1 +x 2 - 9 ≥ 0 trong nửa mặt phẳng phía trên đường thẳng.
Hãy xây dựng phương trình x 1 +2x 2 = 8 tại hai điểm.
Để tìm điểm thứ nhất, ta đánh phương x 1 = 0. Ta tìm x 2 = 4. Để tìm điểm thứ hai, ta đánh phương x 2 = 0. Ta tìm x 1 = 8. Ta nối điểm (0;4) với (8;0) bằng một đường thẳng. Chúng ta hãy định nghĩa nửa mặt phẳng được xác định bởi bất đẳng thức. Sau khi chọn điểm (0; 0), chúng ta xác định dấu bất đẳng thức trong nửa mặt phẳng: 1. 0 + 2 . 0 - 8 ≤ 0, tức là x 1 +2x 2 - 8 ≥ 0 trong nửa mặt phẳng phía trên đường thẳng.
Hãy xây dựng phương trình x 1 + x 2 = 8 tại hai điểm.
Để tìm điểm thứ nhất, ta đánh phương x 1 = 0. Ta tìm x 2 = 8. Để tìm điểm thứ hai, ta đánh phương x 2 = 0. Ta tìm x 1 = 8. Ta nối điểm (0;8) với (8;0) bằng một đường thẳng. Chúng ta hãy định nghĩa nửa mặt phẳng được xác định bởi bất đẳng thức. Sau khi chọn điểm (0; 0), chúng ta xác định dấu bất đẳng thức trong nửa mặt phẳng: 1. 0 + 1 . 0 - 8 ≤ 0, tức là x 1 +x 2 - 8< 0 trong nửa mặt phẳng phía dưới đường thẳng.

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

Bạn có thể kiểm tra tính đúng đắn của việc xây dựng đồ thị hàm số bằng máy tính

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

Thẳng F(x) = 4x 1 +6x 2 cắt vùng tại điểm B. Vì điểm B có được là kết quả của giao điểm của các đường (1) Và (2) , thì tọa độ của nó thỏa mãn phương trình của các đường thẳng sau:
3x 1 + x 2 = 9
x 1 +2x 2 = 8

Giải hệ phương trình ta có: x 1 = 2, x 2 = 3
Chúng ta tìm thấy nó từ đâu? giá trị tối thiểu hàm mục tiêu:
F(X) = 4*2 + 6*3 = 26

Lý thuyết tóm tắt

Lập trình tuyến tính là một nhánh của lập trình toán học được sử dụng trong việc phát triển các phương pháp tìm cực trị của hàm tuyến tính của một số biến cho tuyến tính. hạn chế bổ sung, áp đặt lên các biến. Theo loại vấn đề được giải quyết, phương pháp của ông được chia thành phổ quát và đặc biệt. Bằng cách sử dụng phương pháp phổ quát Mọi vấn đề về quy hoạch tuyến tính (LPP) đều có thể được giải quyết. Các phương pháp đặc biệt có tính đến các đặc điểm của mô hình bài toán, hàm mục tiêu của nó và hệ thống các ràng buộc. Một đặc điểm của bài toán quy hoạch tuyến tính là hàm mục tiêu đạt đến cực trị tại biên của vùng lời giải khả thi.

Phương pháp đồ họa Việc giải các bài toán quy hoạch tuyến tính giúp có thể trực quan hóa cấu trúc của chúng, xác định các đặc điểm và mở ra cách nghiên cứu các tính chất phức tạp hơn. Một bài toán quy hoạch tuyến tính với hai biến luôn có thể được giải bằng đồ thị. Tuy nhiên, trong không gian ba chiều, giải pháp như vậy trở nên phức tạp hơn và trong không gian có kích thước lớn hơn ba chiều, nói chung, giải pháp đồ họa là không thể. Trường hợp hai biến không có bất kỳ ý nghĩa thực tế cụ thể nào, nhưng việc xem xét nó làm rõ các thuộc tính của ràng buộc LLP, dẫn đến ý tưởng giải quyết nó và làm cho các phương pháp giải cũng như cách thực hiện thực tế của chúng trở nên rõ ràng về mặt hình học.

Nếu các ràng buộc và hàm mục tiêu chứa nhiều hơn hai biến, thì điều đó là cần thiết (hoặc bằng phương pháp cải tiến tuần tự lời giải) - nó có tính phổ quát và có thể được sử dụng để giải quyết bất kỳ vấn đề nào. Đối với một số bài toán ứng dụng lập trình tuyến tính, chẳng hạn như các phương pháp giải đặc biệt đã được phát triển.

Ví dụ về giải pháp vấn đề

Nhiệm vụ

Doanh nghiệp sản xuất 2 loại sản phẩm: Sản phẩm 1 và Sản phẩm 2. Để sản xuất một đơn vị Sản phẩm 1 cần tiêu tốn kg nguyên liệu loại 1, kg nguyên liệu loại thứ hai, kg nguyên liệu loại thứ ba. Để sản xuất một đơn vị Sản phẩm 2 phải tiêu tốn kg nguyên liệu loại thứ nhất, nguyên liệu loại thứ hai và nguyên liệu loại thứ ba. Sản xuất được cung cấp nguyên liệu từng loại với số lượng kg, kg, kg tương ứng. Giá thị trường của một đơn vị Sản phẩm 1 là một nghìn rúp và một đơn vị Sản phẩm 2 là một nghìn rúp.

Yêu cầu:

• Xây dựng mô hình toán học của bài toán.
• Lập kế hoạch sản xuất các sản phẩm đảm bảo doanh thu tối đa từ việc bán chúng bằng phương pháp đồ họa để giải bài toán quy hoạch tuyến tính.

Để đảm bảo rằng lời giải cho bài toán quy hoạch tuyến tính là chính xác và chính xác nhất có thể, nhiều đơn đặt hàng với chi phí thấp Bài kiểm tra trên trang web đó. Bạn có thể đọc thêm chi tiết (cách gửi yêu cầu, giá cả, thời hạn, phương thức thanh toán) trên trang Mua bài kiểm tra lập trình tuyến tính...

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

Xây dựng mô hình

Gọi và biểu thị số lượng sản phẩm sản xuất được loại 1 và loại 2.

Sau đó hạn chế tài nguyên:

Ngoài ra, theo ý nghĩa của nhiệm vụ

Hàm mục tiêu của mô hình toán kinh tế, biểu thị doanh thu nhận được từ việc bán hàng:

Chúng ta có được mô hình kinh tế và toán học sau:

Xây dựng miền giải pháp khả thi

Hãy giải quyết vấn đề quy hoạch tuyến tính bằng đồ họa:

Để xây dựng miền nghiệm khả thi, ta xây dựng các đường biên tương ứng với các bất đẳng thức đó trong hệ tọa độ:

Hãy tìm những điểm mà các đường đi qua:

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ó.

Để xác định một nửa mặt phẳng, lấy bất kỳ điểm nào, ví dụ, không thuộc đường thẳng (1) và thay tọa độ (0;0) vào bất đẳng thức tương ứng. Bởi vì bất đẳng thức đúng:

Vùng nghiệm của bất đẳng thức 1 tương ứng ứng với nửa mặt phẳng bên trái

Ví dụ: lấy bất kỳ điểm nào không thuộc dòng (2) và thay tọa độ (0;0) vào bất đẳng thức tương ứng. Bởi vì bất đẳng thức đúng:

Ví dụ, hãy lấy bất kỳ điểm nào không thuộc dòng (3) và thay tọa độ (0;0) vào bất đẳng thức tương ứng. Bởi vì bất đẳng thức đúng:

Vùng nghiệm của bất đẳng thức thứ 2 tương ứng ứng với nửa mặt phẳng bên trái

Vùng của các giải pháp khả thi là hình vẽ.

Tìm giải pháp cho vấn đề LP

Chúng ta xây dựng một vectơ có tọa độ tỷ lệ thuận với các hệ số của hàm mục tiêu. Đây là hệ số tỷ lệ.

Vẽ một đường thẳng vuông góc với vectơ đã dựng.

Chúng ta di chuyển đường mức theo hướng của vectơ sao cho nó chạm vào vùng giải pháp khả thi tại điểm cực trị. Nghiệm tối đa là điểm , tọa độ của nó là giao điểm của đường thẳng (2) và (1).

Trả lời

Như vậy, cần sản xuất 56 sản phẩm loại 1 và 64 sản phẩm loại 2. Trong trường hợp này, doanh thu từ việc bán sản phẩm sẽ tối đa và lên tới 5104 đơn vị tiền tệ.

Phương pháp giải pháp đồ họa, nếu một bài toán có hai biến có ràng buộc tuyến tính và hàm mục tiêu là bậc hai, được thảo luận chi tiết tại đây
Trang thảo luận chi tiết lời giải của bài toán quy hoạch tuyến tính phương pháp đơn giản Ngoài ra, việc xây dựng được thể hiện vấn đề kép quy hoạch tuyến tính và tìm lời giải của nó bằng cách giải một bài toán trực tiếp.

Vấn đề vận chuyển và phương pháp tiềm năng
Bài toán vận tải, mô hình toán học và phương pháp giải của nó được xem xét chi tiết - tìm phương án tham chiếu bằng phương pháp phần tử tối thiểu và tìm kiếm lời giải tối ưu bằng phương pháp thế năng.

Lập trình lồi - phương pháp đồ họa
Một ví dụ về giải bài toán quy hoạch lồi bậc hai bằng phương pháp đồ họa được đưa ra.

Giải bài toán quy hoạch tuyến tính (LPP) bằng phương pháp đồ họa

Công thức chung của cốt truyện

Tìm các giá trị của n biến x 1 , x 2 , …, x n thỏa mãn cực trị (tối thiểu hoặc tối đa) hàm tuyến tính Z=C 1 x 1 ,+ C 2 x 2+…+ C n x n

và đồng thời thỏa m điều kiện có dạng

a 1,1 x 1 +a 1,2 x 2 +…+a 1.n x n£ = ≥b 1 ,

a 2,1 x 1 +a 2,2 x 2 +…+a 2.n x n£ = ≥b 2 ,

. . . . . . . . . . . . . . . . . . . . . . .,

a m,1 x 1 +a m,2 x 2 +…+a m,n x n£ = ≥b m ,

với a i,j , b i, C j (i=1,2,…,m; j=1,2,…,n). Dấu quan hệ có thể nhận bất kỳ giá trị nào trong ba giá trị đã cho.

Ví dụ về bài toán quy hoạch tuyến tính

Chúng ta hãy xem xét vấn đề sau đây. Người quản lý của một công ty sản xuất hai loại sơn đã mô tả cho một nhà nghiên cứu hoạt động về tình hình sản xuất và tiếp thị sơn. Hóa ra nhà máy sản xuất hai loại sơn: sơn nội thất và sơn công việc làm thêm. Cả hai màu đều có bán sỉ. Để sản xuất sơn, hai sản phẩm ban đầu được sử dụng - A và B. Lượng dự trữ tối đa hàng ngày của các sản phẩm này lần lượt là 6 và 8 tấn. Kinh nghiệm cho thấy nhu cầu sơn bên ngoài hàng ngày không bao giờ vượt quá nhu cầu sơn bên trong quá 1 tấn. Ngoài ra, người ta nhận thấy nhu cầu sơn ngoại thất không bao giờ vượt quá 2 tấn/ngày. Giá bán buôn cho một tấn sơn như sau: 3 nghìn rúp cho sơn bên ngoài và 2 nghìn rúp cho sơn bên trong. Nhà máy nên sản xuất bao nhiêu loại sơn để tối đa hóa doanh thu bán hàng?

Để giải quyết vấn đề đặt ra cho người nghiên cứu, trước tiên cần xây dựng mô hình toán học của tình huống được mô tả.

Khi xây dựng một mô hình toán học, nhà nghiên cứu hoạt động tự hỏi mình ba câu hỏi.

• Mô hình nên được xây dựng với số lượng bao nhiêu? Nói cách khác, bạn cần xác định các biến nhiệm vụ.
• Những hạn chế nào phải được đặt ra đối với các biến để đáp ứng được các điều kiện đặc trưng của hệ thống đang được mô hình hóa?
• Mục tiêu là gì, để đạt được mục tiêu nào, trong số tất cả các giá trị có thể (có thể chấp nhận được) của các biến, cần phải chọn những giá trị nào tương ứng với giải pháp tối ưu (tốt nhất) cho vấn đề?

Hãy giới thiệu các biến:

x 1 – sản lượng sơn ngoài trời sản xuất hàng ngày (tấn),

x 2 – sản lượng sơn nội thất sản xuất hàng ngày (tấn).

Đang xem xét Giá bán buôn trên mỗi tấn sơn, thu nhập hàng ngày từ việc bán sản phẩm sản xuất được cho bởi hàm mục tiêu tuyến tính Z = 3x 1 + 2x 2.

Mục tiêu của sản xuất là thu được lợi nhuận tối đa, nghĩa là cần tìm các giá trị x 1 và x 2 sao cho hàm mục tiêu Z tối đa hóa.

Vì nhà sản xuất sơn không thể kiểm soát được giá trị của các biến ngẫu nhiên, vì vậy cần xác định tập hợp các giá trị có thể có của các biến này, được xác định bởi các điều kiện sản xuất, kinh doanh cụ thể. Tập hợp này được gọi là vùng giá trị chấp nhận được.

Loại hạn chế đầu tiên được xác định bởi lượng tồn kho sản phẩm A và B dùng để sản xuất sơn. Từ công nghệ sản xuất được biết, hai phần của sản phẩm A dùng để sản xuất một tấn sơn ngoại thất, một phần dùng để sản xuất một tấn sơn nội thất. Đối với sản phẩm B mối quan hệ bị đảo ngược. Những điều kiện công nghệ này được mô tả bởi các bất đẳng thức

2x 1 + x 2 £ 6 (6 tấn sản phẩm A còn hàng),

x 1 + 2x 2 £ 8 (có 8 tấn sản phẩm B trong kho).

Hai hạn chế cuối cùng có nghĩa là một tình huống hiển nhiên: bạn không thể sử dụng nhiều sản phẩm A và B để sản xuất sơn hơn số lượng thực tế có trong kho.

Tình trạng bán sơn trên thị trường dẫn đến những hạn chế sau: x 1 – x 2 £ 1 (sơn bên ngoài bán nhiều hơn sơn bên trong không quá một tấn), x 1 £ 2 (sơn bên ngoài bán không quá 1 tấn) hơn hai tấn mỗi ngày).

Tóm tắt tất cả những gì đã nói, một mô hình toán học mô tả tình hình sản xuất hiện tại có thể được chỉ định theo dạng sau:

tìm thấy® tối đa( Z=2× x 1 + 3× x 2 ) tại hạn chế sau đây về giá trị của các biến x 1 và x 2

2 × x 1 + x 2 £ 6 hạn chế (1),

X 1 + 2 × x 2 £ 8 hạn chế (2),

X 1 - x 2 £ 1 hạn chế (3),

Ràng buộc X 1 £ 2 (4)

và yêu cầu các biến x 1 ³ 0 (5), x 2 ³ 0 (6) không âm.

Đã nhận mô hình toán học là bài toán quy hoạch tuyến tính.

Phương pháp đồ họa giải pháp cho vấn đề

Phương pháp đồ họa để giải bài toán chỉ có thể được thực hiện trong trường hợp hai chiều.

Mô hình toán học thu được cho bài toán tiêu chuẩn đã được xây dựng đòi hỏi phải nghiên cứu, vì người ta không biết trước liệu nó có (làm thế nào bài toán) giải pháp. Chúng tôi sẽ tiến hành nghiên cứu bằng cách sử dụng công trình đồ họa. Đồng thời với việc nghiên cứu như vậy, chúng ta sẽ tìm ra (nếu có) giải pháp.

Giai đoạn 1. Xây dựng miền giải pháp khả thi

Mục tiêu là xây dựng một vùng trong đó mọi điểm đều thỏa mãn tất cả các ràng buộc.

Mỗi ràng buộc trong số sáu ràng buộc về mặt hình học xác định một nửa mặt phẳng. Để xây dựng nó, bạn cần:

• · Thay dấu bất đẳng thức trong ràng buộc bằng đẳng thức (ta được phương trình đường thẳng);

• · dựng đường thẳng qua hai điểm;

• · xác định nửa mặt phẳng nào được xác định bằng dấu bất đẳng thức. Để làm điều này, hãy thay thế một số điểm vào bất đẳng thức (ví dụ: gốc tọa độ). Nếu nó thỏa mãn bất đẳng thức thì vẽ nửa mặt phẳng chứa nó.

Chúng tôi thực hiện những hành động này cho tất cả các hạn chế. Chúng tôi biểu thị từng dòng bằng các số được áp dụng khi đánh số các hạn chế (xem hình).

Lĩnh vực giải pháp khả thi (thỏa mãn mọi ràng buộc) là tập hợp các điểm thuộc góc phần tư thứ nhất của mặt phẳng tọa độ (x 1, x 2), là giao điểm của tất cả các nửa mặt phẳng được xác định bởi các bất đẳng thức của các ràng buộc.

Tập hợp các điểm thỏa mãn cả sáu ràng buộc của bài toán là đa giác AFEDCB.

Giai đoạn 2: Xây dựng đường mức hàm mục tiêu và xác định điểm cực đại

Mục tiêu là tìm trong đa giác được dựng AFEDCB là điểm mà tại đó hàm mục tiêu Z=2x 1 + 3x 2 đạt giá trị cực đại.

Hãy vẽ đường thẳng 2x 1 + 3x 2 = Const (đường đồng mức) sao cho nó cắt đa giác AFEDCB (ví dụ Const = 10). Đường mức này được thể hiện dưới dạng đường chấm trong hình.

Nếu ta xét các giá trị của hàm mục tiêu tuyến tính Z trên một tập hợp các điểm (x 1, x 2) thuộc một đoạn đường chấm nằm bên trong hình lục giác thì chúng đều có cùng một giá trị (Const = 10).

Hãy xác định chiều tăng của hàm số. Để làm điều này, chúng ta sẽ xây dựng một đường mức với Giá trị cao hơn. Đây sẽ là một đường thẳng, song song với đường thẳng đã xây dựng nhưng nằm ở bên phải. Điều này có nghĩa là theo một hướng nhất định, giá trị của hàm mục tiêu tăng lên và lợi ích của chúng ta là di chuyển nó càng xa càng tốt theo hướng này.

Sự dịch chuyển có thể được tiếp tục miễn là đường thẳng chuyển động cắt đa giác của các giải pháp khả thi. Vị trí cuối cùng của đường thẳng khi có một điểm chung với đa giác AFEDCB (điểm C) ứng với giá trị lớn nhất của hàm mục tiêu Z và đạt được tại điểm C có tọa độ x 1 = 4/3 (“1.333) , x 2 = 10/3 (" 3,333). Trong trường hợp này, Z = 38/3 (» 12,667).

Nhiệm vụ đã được giải quyết hoàn toàn. Từ lý luận hình học được thực hiện, rõ ràng nghiệm này là duy nhất. Chúng ta hãy đưa ra một số khái quát hóa phát sinh từ việc giải thích hình học của bài toán.

Đầu tiên. Vùng của các giải pháp khả thi là một đa giác lồi ( Tại sao lồi? Vùng của các lời giải khả thi có thể là một tập rỗng không? Giai đoạn? Đoạn đường? Cá đuối? Trực tiếp? Nếu có, hãy cho ví dụ về hệ thống hạn chế).

Thứ hai. Hàm mục tiêu đạt cực đại tại đỉnh của đa giác nghiệm khả thi ( Nhưng có lẽ không chỉ có một giải pháp? Có thể không có giải pháp?)

Bài tập 1 (hoàn thành trên lớp, đưa cho giáo viên)

Giải bằng đồ họa

A) x1=6 x2=4 F=24

B) x1=2 x2=3 F=26

C) x1О x2=8-x1 F=24

Bài 2 (hoàn thành trên lớp, nộp cho giáo viên)

Trả lời các câu hỏi in nghiêng.

Nhiệm vụ 3 (bài tập về nhà)

Viết một chương trình.

Dân tập tin văn bản loại

2 3 (hệ số hàm mục tiêu)

4 (số lượng hạn chế)

2 2 12 (hạn chế)

1 2 8

4 0 16

0 4 12

Vẽ các đường thẳng sao cho đa giác của các giải pháp khả thi nằm hoàn toàn trên màn hình (để biết định nghĩa về tỷ lệ, xem sách của Onegov). Đường thẳng có thể song song với trục!

Xây dựng một số đường ở cấp độ của hàm mục tiêu (nhấn phím - đường thẳng di chuyển, giá trị của hàm mục tiêu được hiển thị). Hiển thị quy mô.

Một phương pháp quan trọng để phân tích khoa học tài liệu thống kê là hình ảnh đồ họa. Những nỗ lực đầu tiên sử dụng phương pháp đồ họa trong nghiên cứu kinh tế bắt đầu vào những năm 1780. Tuy nhiên, phương pháp đồ họa đã được sử dụng rộng rãi hơn sau đó - vào giữa thế kỷ 18, đặc biệt là sau báo cáo của đại diện Cục thống kê Berlin Schwabe, “Lý thuyết”, được đưa ra lần đầu tiên trong lịch sử thống kê. Hình ảnh đồ hoạ"tại Đại hội Thống kê Quốc tế lần thứ 8 (St. Petersburg, 1872). Theo cách diễn đạt nổi tiếng của nhà vật lý người Đức F. Auerbach, thế kỷ 20 được đánh dấu bằng "sự tiến bộ thắng lợi của phương pháp đồ họa trong khoa học."

Lịch trình là gì? Đồ thị là một dạng đại diện trực quan số liệu thống kê về các hiện tượng, quá trình kinh tế - xã hội thông qua hình ảnh hình học, hình vẽ hoặc sơ đồ Bản đồ địa lý và lời giải thích cho chúng.

Một biểu đồ có năm phần tử chính Thiết kế chung: trường, lưới tọa độ, ký hiệu đồ họa và vị trí của chúng trong trường đồ họa, tỷ lệ và chú giải (Hình 10.3).

Cơm. 10.3. Các thành phần cơ bản của biểu đồ

Mỗi yếu tố này đều có mục đích riêng và đóng vai trò tương ứng trong việc xây dựng và diễn giải. Trường đồ họa là không gian đặt các ký hiệu hình học và các dấu hiệu khác tạo nên hình ảnh đồ họa.

Hình ảnh đồ họa là một tập hợp các dấu hiệu tượng trưng khác nhau với sự trợ giúp của dữ liệu thống kê được phản ánh. Những dấu hiệu này có thể được mô tả dưới các dạng sau: đường, dấu chấm, hình học, đồ họa và đôi khi là hình phi hình học.

Lưới tọa độ là một hệ tọa độ hình chữ nhật trong đó thời gian được vẽ trên trục hoành và các chỉ số định lượng của tỷ lệ được vẽ trên trục tọa độ.

Thang đo là thước đo có điều kiện để chuyển đổi giá trị số của một hiện tượng thống kê thành giá trị đồ họa và ngược lại. Nó được sử dụng để cài đặt Giá trị kiểu số hiện tượng biểu diễn trên đồ thị.

Giải thích biểu đồ là giải thích bằng lời về nội dung cụ thể của nó, thường bao gồm:

1) tiêu đề kèm theo những giải thích bổ sung cần thiết;

2) một lời giải thích chính xác về bản chất, được cung cấp có điều kiện trong biểu đồ này dấu hiệu đồ họa của nó (hình học, hình ảnh, nền, hoàn toàn thông thường)

3) các giải thích, ghi chú khác, v.v.

Ngoài ra, bạn có thể đặt một số thông tin thêm, ví dụ: dữ liệu số được phản ánh trong một số ký hiệu đồ họa và lặp lại chúng ở dạng kỹ thuật số giá trị chính xác, được thể hiện bằng đồ họa.

Đồ thị đóng một vai trò đặc biệt quan trọng trong việc nghiên cứu các mối tương quan phức tạp của các hiện tượng và quá trình kinh tế xã hội, xác định xu hướng, mô hình và những thay đổi về động lực cũng như trong phân tích đang diễn ra. Sự khác biệt và ưu điểm chính của phương pháp đồ họa so với các phương pháp khác là: khả năng hiển thị tốt hơn; khả năng bao quát chung dữ liệu của những người được nghiên cứu; khả năng thể hiện một số phụ thuộc phân tích không rõ ràng và khó xác định bằng các phương pháp trình bày dữ liệu khác.

Với sự trợ giúp của lịch trình, bạn có thể thực hiện kiểm soát hoạt động đối với hoạt động sản xuất, bán sản phẩm, thực hiện nghĩa vụ hợp đồng và nhiệm vụ được giao. Vì vậy, lịch trình được phân công:

Tóm tắt và phân tích dữ liệu;

Hình ảnh phân phối dữ liệu;

Xác định mô hình phát triển của các hiện tượng và quá trình nghiên cứu trong động lực học;

Phản ánh mối tương quan giữa các chỉ số;

Giám sát sản xuất, thực hiện hợp đồng mua bán…

Có nhiều cách phân loại đồ thị khác nhau - theo hình dạng Hình ảnh đồ hoạ về nội dung và tính chất của nhiệm vụ.

Dựa vào hình dạng của hình ảnh đồ họa, chúng được phân biệt các loại sauđồ thị:

1 điểm;

2) tuyến tính;

3) phẳng;

4) thể tích;

5) nghệ thuật (hình ảnh, thông thường).

Trong biểu đồ phân tán, thể tích của quần thể được biểu thị bằng một điểm duy nhất hoặc bằng sự tích lũy các điểm. Một điểm có thể có nghĩa là một hoặc nhiều trường hợp (ví dụ: một nhà máy, 500 công nhân).

Đồ thị tuyến tính chỉ bao gồm các đường: đoạn thẳng, đường gãy, bậc thang, đường cong trơn (chủ yếu để truyền tải động thái của dân số). Các đoạn thẳng thường được thay thế bằng các dải cùng chiều rộng, cũng hoạt động như các dấu hiệu đồ họa nhưng có một chiều (chiều dài). Trong những trường hợp như vậy, đồ thị được gọi là biểu đồ thanh nếu các sọc được đặt theo chiều dọc hoặc biểu đồ dải khi các sọc nằm ngang.

Đổi lại, biểu đồ cột được chia thành biểu đồ cột: đơn giản và liền mạch, từ các nhóm cột, v.v., và biểu đồ dải được chia thành biểu đồ dải: đơn giản và từng bước, theo thành phần, trượt, hướng song phương (ví dụ: “ tháp tuổi” của cơ cấu dân số).

ĐẾN loại đặc biệtđồ thị tuyến tính bao gồm đồ thị xoắn ốc (đối với các hiện tượng phát triển vô hạn theo thời gian và với cường độ ngày càng tăng), sơ đồ xuyên tâm(để hiển thị các mẫu hiện tượng lặp lại định kỳ, nhịp điệu, tính thời vụ của chúng).

Đồ thị phẳng là đồ thị có hai chiều ở dạng các mặt phẳng có hình dạng hình học khác nhau. Tùy thuộc vào điều này, chúng có thể là hình vuông, hình tròn, hình cung. Nên sử dụng các biểu đồ này để so sánh các hiện tượng được biểu thị bằng giá trị tuyệt đối và tương đối.

Các tính năng quan trọng của biểu đồ phẳng là "dấu hiệu Warzar" hai chiều, biểu đồ dải hoặc biểu đồ hiện tại và biểu đồ cân bằng.

“Dấu hiệu Varzar” hai chiều (được đặt theo tên người phát minh ra nó, nhà thống kê người Nga V.E. Varzar) là một hình chữ nhật có đáy a, chiều cao b và diện tích Sab, rất hữu ích để biểu thị bằng đồ họa các mối quan hệ tương tự khá phổ biến giữa ba đại lượng a, bởi S.

Biểu đồ dải hoặc dòng điện được sử dụng để thể hiện dưới dạng sơ đồ khối lượng và thành phần của dòng hàng hóa giữa hai điểm theo hướng một và hướng thứ hai.

Biểu đồ bảng cân đối kế toán là biểu đồ dải hai mặt, các dải băng phân nhánh theo hai hướng thành các dải hẹp hơn, chiều rộng của chúng biểu thị các giá trị tương ứng của các mục thu nhập và chi phí, các mục tài sản và nợ phải trả, v.v.

thể tích - đồ họa 3D, hiếm khi được sử dụng vì chúng ít biểu cảm hơn so với tuyến tính và phẳng.

Nghệ thuật (trực quan, thông thường) - đồ thị có dấu hiệu đồ họa thông thường phản ánh tổng thể hoặc ý nghĩa riêng của nó dưới dạng hình người, đường viền động vật, bản vẽ sơ đồ của đồ vật, v.v.

Việc phân loại đồ thị theo nội dung của chúng có tầm quan trọng rất lớn. Khi tính đến điều này, đồ thị được chia thành hai lớp - sơ đồ và bản đồ thống kê.

Sơ đồ là sự biểu thị đồ họa về khối lượng và đặc điểm của một hoặc nhiều tập hợp bằng cách sử dụng các ký hiệu đồ họa định lượng (hình học, nghệ thuật, nền tảng, hoàn toàn thông thường).

Tuy nhiên, sơ đồ không cung cấp biểu diễn đồ họa o vị trí lãnh thổ của các quần thể được mô tả hoặc những thay đổi về lãnh thổ trong đặc điểm của chúng. Với mục đích này, các bản đồ thống kê được sử dụng, được thiết kế để mô tả sự phân bố lãnh thổ của quần thể hoặc những thay đổi về đặc điểm lãnh thổ của chúng. Chúng được chia thành hai lớp - bản đồ và sơ đồ bản đồ.

Bản đồ là bản đồ địa lý đường viền trên đó các đặc điểm lãnh thổ định lượng của dân số được thể hiện bằng các ký hiệu đồ họa.

Sơ đồ bản đồ là bản đồ địa lý đường viền, trong đó các khu vực (vùng, điểm) riêng lẻ của một lãnh thổ được vẽ bằng cùng một loại sơ đồ (một hoặc nhiều), mô tả khối lượng và đặc điểm lãnh thổ của các quần thể tương tự ở những khu vực này. Vì vậy, ví dụ, dòng hàng hóa, hành khách được vận chuyển, dân cư di cư và những thứ tương tự được mô tả.

Sơ đồ, bản đồ thống kê thực hiện những nhiệm vụ quan trọng sau đây trong nghiên cứu dân số:

So sánh chung về chúng;

Nghiên cứu cấu trúc;

Nghiên cứu động lực học;

Nghiên cứu mối quan hệ giữa các đặc điểm của chúng;

Đo lường mức độ thực hiện kế hoạch kinh tế và nghĩa vụ hợp đồng trong thực tiễn lập kế hoạch kinh tế.

Ngược lại, cả sơ đồ và bản đồ, tùy theo mục đích của chúng, được chia thành các lớp con, nhóm và dạng (Bảng 10.27).

Khi xây dựng đồ thị phải tuân thủ các yêu cầu sau:

1) dựa vào dữ liệu số đáng tin cậy;

2) đồ thị phải có ý nghĩa về mặt thiết kế và thú vị về nội dung;

3) phải được xây dựng phù hợp với nhiệm vụ được giao và mục đích thực tiễn của chúng;

4) cực kỳ tiết kiệm - chứa tối đa thông tin và ý tưởng với tối thiểu phương tiện biểu đạt đồ họa, đơn giản, rõ ràng, dễ hiểu;

5) được thực hiện tốt về mặt kỹ thuật.

Chúng ta hãy xem xét kỹ hơn các loại và hình thức chính của sơ đồ và bản đồ thống kê, thường được sử dụng nhất trong thực hành công việc phân tích.

Sơ đồ đường là một trong những loại biểu đồ phổ biến nhất dùng để mô tả động lực học của các hiện tượng đang được nghiên cứu. Để xây dựng nó, một hệ tọa độ hình chữ nhật được sử dụng. Các phân đoạn bằng nhau được bố trí trên trục hoành - các khoảng thời gian (ngày, tháng, năm, v.v.) và trên trục tọa độ, một thang đo được sử dụng để mô tả các đơn vị đo lường. Các điểm được vẽ trên trường tọa độ bằng giá trị của chỉ báo trên Thời kỳ nhất định. Khi đó tất cả các điểm được nối với nhau bằng các đường thẳng, tạo thành một đường đứt nét đặc trưng cho sự thay đổi của hiện tượng đang được nghiên cứu trong một khoảng thời gian nhất định (Bảng 10.28, Hình 10.4).

Bảng 10.28. Đầu tư vào vốn cố định trong xây dựng nhà ở ở Ukraina năm 2000-2005 trang, theo giá thực tế, triệu UAH

Dữ liệu biểu đồ cho thấy khối lượng đầu tư vào vốn cố định vào xây dựng nhà ở ở Ukraine theo giá thực tế đã tăng từ năm 2000 đến năm 2005

Cơm. 10.4. Động lực của khối lượng đầu tư vào vốn cố định trong xây dựng nhà ở ở Ukraina năm 2000-2005, theo giá thực tế, triệu UAH

Đồ thị đường kế hoạch được xây dựng trên một lưới được thiết kế đặc biệt, trong đó các đơn vị thời gian được sắp xếp theo chiều ngang và các đối tượng nghiên cứu được đặt theo chiều dọc. Hơn nữa, mỗi phân đoạn ngang tương ứng với việc hoàn thành 100% nhiệm vụ theo kế hoạch. Các phân đoạn này được chia thành 5 phần bằng nhau, mỗi phần tương ứng với 20% nhiệm vụ kế hoạch.

Mức độ thực hiện kế hoạch trên biểu đồ được thể hiện bằng hai đường: một đường đứt nét mảnh - trên một đơn vị thời gian (ngày, thập kỷ) và một đường đậm nét - cho cả kỳ báo cáo.

Chúng ta hãy xem quy trình xây dựng biểu đồ tuyến tính có kế hoạch bằng một ví dụ.

Ví dụ. Xây dựng đồ thị đường nhóm công nhân thi công xây lắp hoàn thành nhiệm vụ theo kế hoạch, sử dụng số liệu trong Bảng. 29/10.

Bảng 10.29. Đội ngũ công nhân thi công xây dựng hoàn thành nhiệm vụ theo kế hoạch

Tiến độ hoàn thành nhiệm vụ dự kiến ​​của đội thi công xây dựng và lắp đặt được trình bày trên Hình 2. 10,5.

Đường mỏng liên tục của ngày đầu tiên tương ứng với 90% kế hoạch và chiếm 4 ô rưỡi, còn đường của ngày thứ hai - 80% và chiếm 4 ô, đường của ngày thứ ba kéo dài đúng 5 ô, và đường của ngày thứ ba kéo dài đúng 5 ô. thứ tư - năm ô (100%) cộng với một ô bổ sung ở đoạn bên dưới, chiếm 20%, v.v.

Việc mô tả mức độ thực hiện kế hoạch trên cơ sở dồn tích đòi hỏi một số tính toán bổ sung. Vì vậy, vào ngày đầu tiên, vạch đậm nét liền sẽ có chiều dài bằng vạch mỏng liên tục - 90% và sẽ chiếm 4 ô rưỡi. Tiếp theo, cần thực hiện các tính toán sau: trong hai ngày, 513 m2 (225 + 288) đã thực sự hoàn thành. Trong đó, 250 m2 được cấp để thực hiện kế hoạch ngày đầu tiên. Sau đó, vào ngày thứ hai, sẽ còn lại 263 m2, theo kế hoạch, vào ngày này là 91% (263.288).

Theo dòng in đậm, nó chiếm năm ô của ngày đầu tiên và 91% của ngày thứ hai. Trong 3 ngày, 923 m2 (225 + 288 + 410) đã thực sự hoàn thành. 610 m2 được ghi nhận hoàn thành kế hoạch trong 2 ngày đầu và 313 m2 cho ngày thứ 3, theo kế hoạch ngày này là 76% (313:410). Đường dày sẽ chiếm 5 ô của ngày đầu tiên và ngày thứ hai và 76% của ngày thứ ba. Tất cả các tính toán tiếp theo được thực hiện tương tự. Mức độ thực hiện kế hoạch từng ngày được biểu thị bằng các dấu chấm trên đường đậm.

Biểu đồ cột- một loại biểu đồ một chiều rất phổ biến do tính rõ ràng và đơn giản của chúng. Dữ liệu thống kê trong đó được mô tả dưới dạng hình chữ nhật có cùng chiều rộng, nằm dọc theo một đường ngang (Hình 10.6).

Chiều cao của các cột phải tương ứng với độ lớn của hiện tượng được mô tả. Nếu các thanh được đặt theo chiều ngang thì đồ thị như vậy được gọi là đồ thị dải (Hình 10.7).

Biểu đồ cột và dải cho phép bạn so sánh các giá trị những nghĩa khác nhau, mô tả hiện tượng tương tự trong động lực học; đặc trưng cho dân số.

Biểu đồ hình tròn (hoặc biểu đồ tròn) là sơ đồ được thiết kế để hiển thị cấu trúc của các hiện tượng và quá trình đang được nghiên cứu. Chúng được mô tả dưới dạng một vòng tròn được chia thành các khu vực, kích thước của chúng tương ứng với kích thước của hiện tượng được mô tả (Hình 10.8).

Như được minh họa bằng biểu đồ (Hình 10.8), nguồn tài chính chính cho hoạt động cho thuê ở Ukraine là các khoản vay ngân hàng (80,9%), sau đó là vốn tự có (16,1%). Vốn vay pháp nhân chỉ chiếm 3,6%.

Cơm. 10.6. Động lực của khối lượng đầu tư vào vốn cố định trong xây dựng nhà ở ở Ukraina năm 2000-2005 trang, theo giá thực tế, triệu UAH

Cơm. 10.7. Động lực của khối lượng đầu tư vào vốn cố định trong xây dựng nhà ở ở Ukraina năm 2000-2005 trang, theo giá thực tế, triệu UAH

TRONG điều kiện hiện đại phát triển của hệ thống thông tin và máy tính, người ta có thể xây dựng đồ thị bằng cách sử dụng các gói chương trình máy tính, bao gồm cả điện tử bảng EXCEL, "Statistica-6", v.v. Chúng rất dễ sử dụng và đơn giản hóa công việc này rất nhiều.

Cơm. 10.8. Cơ cấu nguồn tài chính cho hoạt động cho thuê ở Ukraina vào đầu năm 2005 p.,%