Tóm tắt: Phương pháp đồ thị và phương pháp đơn hình giải các bài toán quy hoạch tuyến tính. Phương pháp đơn giản. Ý tưởng chính, các giai đoạn tìm lời giải, thuật toán của phương pháp

Tìm phương án tối ưu. Phương pháp này là phổ quát, nó cho phép bạn giải quyết vấn đề lập trình tuyến tính bất kỳ kích thước nào trong cài đặt chung. Tuy nhiên, phương pháp này đòi hỏi phải giảm vấn đề ban đầuĐẾN hình thức kinh điển.

Ý tưởng chính của phương pháp đơn hình là di chuyển từ đỉnh này sang đỉnh khác của ODR sao cho mỗi lần chuyển đổi giá trị của CF sẽ giảm đi. Đây là cách bạn có thể đi từ bất kỳ đỉnh nào đến đỉnh tối ưu và có được phương án tối ưu.

Ví dụ: Cho phương án tham chiếu X =(x1,x2,…,xm,0,0,…,0) và hệ liên kết các vectơ độc lập tuyến tính: A1,A2,…,Am được biết thì đối với phương án tham chiếu này bạn có thể tính giá trị CF Z=(c1x1+c2x2+…+cmxm) và viết ra các điều kiện giới hạn trong mẫu sau x1A1+x2A2+…+xmAm=b

Vì các vectơ A1,A2,…,Am độc lập tuyến tính nên bất kỳ vectơ Aj nào cũng có thể được mở rộng thành các vectơ sau: Aj=x1jA1+x2jA2+…+xmjAm (*) Hãy để chúng tôi giới thiệu các giá trị Zj Zj=x1jc1+x2jc2+…+ xmjcm, trong đó xij là hệ số tương ứng với Ai trong vectơ khai triển Aj theo vectơ cơ sở

Định lý 1: Cải thiện kế hoạch tham khảo

Nếu đối với một số chỉ số j điều kiện Zj-Cj>0 được thỏa mãn thì giá trị của CF có thể giảm đi và:

· nếu CF bị giới hạn từ bên dưới thì có thể xây dựng sơ đồ tham chiếu với giá trị CF nhỏ hơn, giống như trước đó

· Nếu TF không bị giới hạn từ bên dưới thì có thể xây dựng phương án tương ứng với giá trị TF nhỏ tùy ý

Định lý 2: tiêu chí tối ưu cho phương án tham chiếu

Nếu với một số chỉ số j trong sơ đồ tham chiếu có bất đẳng thức Zj-Cj0. Để đạt được mức tối thiểu này đối với vectơ Ak, thì vectơ này phải được suy ra từ cơ sở. Đường thẳng tương ứng với vectơ này được gọi là hướng dẫn và được ký hiệu là “à”.

4. Sau khi xác định các hướng dẫn cột và hàng, hãy điền vào một bảng đơn giản mới. Trong bảng như vậy, Ai sẽ xuất hiện ở vị trí của đường dẫn. đổ đầy bảng mới bắt đầu bằng một dòng hướng dẫn. Là một thành phần của sơ đồ tham chiếu, giá trị Ҩ0 X'l=Ҩ0=Xk/Xkl được viết ở đó, các phần tử còn lại của dòng này được xác định theo công thức X'lj X'lj=Xkj/Xkl trong đó Xkl là phần tử nằm ở giao điểm của các hướng dẫn hàng và cột, cụ thể trên đó tất cả các phần tử cũ của đường hướng dẫn đều được phân chia và một đơn vị tự động xuất hiện ở vị trí của phần tử Xkl trước đây. Nguyên tắc chungđể tính lại đường dẫn bạn có thể viết như sau: Ak (phần tử mới của đường dẫn) = (phần tử cũ của đường dẫn)/(phần tử đứng tại giao điểm của cột và hàng dẫn hướng)

5. Tất cả các phần tử của các hàng còn lại của bảng đều được tính toán lại, bao gồm cả hàng bổ sung dưới cùng. Việc tính toán lại được thực hiện theo công thức

· đối với các thành phần của phương án tham chiếu X'i=Xi-Ҩ0Xil=Xi-(Xk/Xkl)*Xil

· cho các thành phần được mở rộng trên cơ sở X'ij=Xij-(Xkj/Xkl)*Xil

· Vì dòng bổ sung Z'j-Cj=(Zj-Cj)-(Xkj/Xkl)*(Zl-Cl)

Tất cả các công thức này được xây dựng theo một quy tắc:

(email mới)=(email cũ)-(email hướng hàng mới)*(email hướng cột ở hàng tương ứng)

Sau khi điền vào bảng đơn giản mới, quá trình chuyển sang giai đoạn thứ hai của thuật toán sẽ diễn ra.

Phương pháp tự nhiên và cơ sở nhân tạo. Các khái niệm, thuật toán cơ bản của phương pháp.

Đối với hầu hết các bài toán quy hoạch tuyến tính, khó khăn nảy sinh khi giải chúng liên quan đến việc xác định sơ đồ tham chiếu ban đầu và bảng đơn giản ban đầu mà từ đó tất cả các phép lặp bắt đầu. Điều này là do trong các bài toán thực tế trong số các vectơ Ai không có vectơ nào chỉ chứa một thành phần khác 0, tức là các vectơ có dạng (0,0,0,…,0,1,0,…,0) hoặc số lượng của chúng không đủ để làm cơ sở. Tức là không thể hình thành cơ sở tự nhiên được.

Phương pháp cơ sở nhân tạo dựa trên giới thiệu giả tạo thành mô hình toán học của bài toán các vectơ đó.

Cho một ZLP có dạng chính tắc

F: C1X1=C2X2+…+CnXnàmin

a11x1+a21x2+…+an1xn=b1

a12x1+a22x2+…+an2xn=b2

…………………………

a1mx1+a2mx2+…+anmxn=bm

Sau đó nó được chuyển về dạng

F: C1X1+C2X2+…+CnXn+MXn=1+MXn+2+…+MXn+màmin

a11x1+a21x2+…+an1xn+xn+1=b1

a12x1+a22x2+…+an2xn+xn+2=b2

……………………………….

a1mx1+a2mx2+…+anmxn+xn+m=bm

Trong đó M là vô hạn số lượng lớn. Trong bài toán tìm được, cơ sở ban đầu được nhìn thấy ngay lập tức; các vectơ với các biến được đưa vào một cách giả tạo xn+1, xn+2,…, xn+m phải được coi là nó. Vì các vectơ này sẽ có dạng: (1,0,0,…,0),(0,1,0,…,0),(0,0,…,1). Sau đó, bài toán đã biến đổi sẽ được giải bằng thuật toán phương pháp đơn giản. Sơ đồ tham chiếu ban đầu của bài toán chuyển đổi có dạng (0,0,…,0,xn+1,xn+2,…,xn+m)=(0,0,…,0,b1,b2,…, bm). Bảng đơn giản ban đầu trông như thế này:

Nền tảng	hệ số CF	Kế hoạch	C1	C2	…	Cn	M	M	…	M
Nền tảng	hệ số CF	Kế hoạch	A1	A2	…	MỘT	An+1	An+2	…	An+m
An+1	M	b1	a11	a21	…	an1	1	0	…	0
An+2	M	b2	a12	a22	…	an2	0	1	…	0
…	…	…	…	…	…	…	…	…	…	…
An+m	M	bm	a1m	a2m	…	anm	0	0	…	1
			Z0

Chúng tôi xác định các phần tử của dòng bổ sung bằng cách sử dụng các công thức Z0=Mb1+Mb2+…+Mbm=∑mi=1Mbi=M∑ni=1bi

Để xác định sự khác biệt Zj=a11M+Ma12+…+Ma1m=M∑mj=1aij V i=1,n

Zj-Cj=M∑mj=1aij-Cj

Sau khi nhận được bảng đơn ban đầu, nó được biến đổi, cố gắng rút ra từ các vectơ cơ sở tương ứng với các biến bổ sung được đưa vào.

Vì M rất con số lớn, thì trong số các hiệu Zj-Cj sẽ có nhiều số dương. Nghĩa là sẽ có nhiều ứng cử viên để đưa vào cơ sở trong số các vectơ A1,A2,…,An

Nếu vectơ nào đó tương ứng với các biến được đưa vào giả tạo xn+1,xn+2,…,xn+m thì vectơ tương ứng được dẫn xuất từ cơ sở và cột đơn của bảng có vectơ này bị gạch bỏ và không được trả về đến nó một lần nữa. Khi kết thúc quá trình chuyển đổi bảng đơn giản, có thể có hai tùy chọn:

· Tất cả các vectơ tương ứng với các biến nhân tạo đã được suy ra từ cơ sở, trong trường hợp này tất cả các cột của bảng đơn tương ứng với các biến bổ sung sẽ biến mất, và bài toán ban đầu sẽ được giải quyết

· Phương án tối ưu thu được vẫn sẽ chứa một số biến bổ sung, điều này có nghĩa là ODD của bài toán ban đầu rỗng, tức là các ràng buộc của nó mâu thuẫn nhau, do đó bài toán ban đầu không có nghiệm nào cả.

Các bài toán quy hoạch tuyến tính kép. Tuyên bố các vấn đề, tính chất của họ.

Bài toán đối xứng kép:

Mẫu chuẩn đầu tiên

f(x)=c1x1+c2x2+…+cnxnàmin

a11x1+a21x2+…+an1xn>=b1

a12x1+a22x2+…+an2xn>=b2

…………………………………………..

a1mx1+a2mx2+…+anmxn>=bm

Vấn đề kép

d(y)=b1y1+b2y2+…+bmymàmax

a11y1+a12y2+…+a1mym=0, V j=1,m

Cặp bài toán kép không phân chia

Vấn đề ban đầu ở dạng chính tắc

f(x)=c1x1+c2x2+…+cnxnàmin

a11x1+a21x2+..+an1xn=b1

a12x1+a22x2+..+an2xn=b2

…………………………..

GIỚI THIỆU

Chủ đề công việc của tôi liên quan đến việc giải quyết các vấn đề phát sinh trong kinh tế. Điều này đặt ra câu hỏi về việc lựa chọn giải pháp tốt nhất, theo một nghĩa nào đó. Và để tìm kiếm tùy chọn có thể Thường bị ảnh hưởng bởi nhiều yếu tố khác nhau làm thu hẹp phạm vi lựa chọn. Nói cách khác, cần phải giải bài toán tối ưu hóa, trong đó cần phải chọn sự lựa chọn tốt nhất quyết định trong số một tập hợp nhất định, thường có giới hạn các lựa chọn khả thi.

Bài toán tối ưu có thể được biểu diễn bằng ngôn ngữ toán học nếu tập hợp Tùy chọn có sẵn có thể được mô tả bằng các mối quan hệ toán học (bình đẳng, bất đẳng thức, phương trình) và mỗi giải pháp có thể được đánh giá định lượng bằng cách sử dụng một số chỉ số gọi là tiêu chí tối ưu hoặc hàm mục tiêu. Sau đó giải pháp tốt nhất sẽ là người mang lại hàm mục tiêu giá trị lớn nhất hoặc nhỏ nhất tùy theo ý nghĩa của bài toán. Ví dụ, khi đầu tư một lượng vốn hạn chế vào một số dự án, nhiệm vụ đương nhiên là chọn những dự án có thể mang lại lợi nhuận lớn nhất trong tương lai. Khi giao sản phẩm từ nhiều nhà cung cấp khác nhau đến cửa hàng, nhiệm vụ giảm thiểu chi phí vận chuyển phát sinh.

Quá trình hình thức hóa một bài toán được gọi là xây dựng mô hình toán học của nó. Nó bao gồm ba giai đoạn.

1. Lựa chọn các tham số của bài toán mà lời giải phụ thuộc vào. Các tham số này được gọi là biến điều khiển và được biểu thị bằng cách tạo thành một vectơ từ chúng . Đưa ra quyết định có nghĩa là thiết lập các giá trị cụ thể cho các biến.

2. Xây dựng tiêu chí bằng số để có thể so sánh Các tùy chọn khác nhau các quyết định. Tiêu chí như vậy thường được gọi là hàm mục tiêu và được ký hiệu là .

3. Mô tả trọn bộ X giá trị cho phép của các biến - hạn chế liên quan đến sự hiện diện nguồn nguyên liệu nguồn lực tài chính, năng lực công nghệ, v.v.

Bài toán tối ưu hóa là tìm ra lời giải khả thi như vậy , mang lại cho hàm mục tiêu giá trị lớn nhất hoặc nhỏ nhất trong số tất cả các nghiệm có thể.

1. Phương pháp hình học giải bài toán LP

Phương pháp này thường được sử dụng để giải các bài toán chỉ có hai đại lượng chưa biết. Hãy xem xét nó bằng các ví dụ sau:

Ví dụ 1.1. (Vấn đề về sản xuất sơn).

Một nhà máy nhỏ sản xuất hai loại sơn: INT- Vì công việc nội thất Và EXT- cho công việc ngoài trời. Trong sản xuất sơn người ta sử dụng hai sản phẩm ban đầu MỘT Và TRONG. Do diện tích kho nhỏ nên lượng tồn kho tối đa hàng ngày của các sản phẩm này lần lượt là 6 tấn và 8 tấn. Để sản xuất được 1 tấn sơn INT tiêu thụ hết 1 tấn sản phẩm MỘT và 2 tấn sản phẩm TRONG và để sản xuất 1 tấn sơn EXT có 2 tấn sản phẩm MỘT và 1 tấn sản phẩm TRONG. Nhà máy bán sơn với giá 3 nghìn. đô la mỗi tấn sơn INT và 2 nghìn đô la một tấn sơn EXT. Thật thuận tiện để tóm tắt dữ liệu ban đầu trong một bảng:

Nghiên cứu thị trường tiêu thụ cho thấy nhu cầu sơn hàng ngày EXT không bao giờ vượt quá nhu cầu về sơn INT, hơn 1 tấn. Nhà máy nên sản xuất bao nhiêu loại sơn mỗi ngày để tối đa hóa thu nhập từ việc bán sản phẩm?

Hãy xây dựng một mô hình toán học của vấn đề. Để làm được điều này cần xác định các biến bài toán, hàm mục tiêu và các ràng buộc mà các biến đó thỏa mãn. Hãy ký hiệu bằng x 1- khối lượng sản xuất sơn INT hàng ngày theo kế hoạch và sau đó x 2- khối lượng sản xuất sơn EXT hàng ngày. Hàm mục tiêu f(x) sẽ thể hiện thu nhập hàng ngày từ việc bán sơn bằng 3x1 + 2x2(nghìn đô la). Thu nhập này phải được tối đa hóa

f( x)= 3 x 1 + 2 x 2 ® tối đa.

Chúng ta hãy xây dựng các ràng buộc của bài toán liên quan đến nguồn cung sản phẩm hạn chế MỘT Và TRONG. Dùng cho sản xuất sơn INT về số lượng x 1(t) sẽ được sử dụng 1x1(t) của sản phẩm MỘT và sản xuất sơn EXT về khối lượng x 2(t) sẽ được chi tiêu 2x2(t) của sản phẩm MỘT. Vì việc cung cấp sản phẩm hàng ngày MỘT là 6 tấn thì lượng tiêu thụ sản phẩm MỘTđể sản xuất hai loại sơn không được vượt quá số lượng này mỗi ngày: 1x1 + 2x2 £6. Tương tự, chúng ta thu được ràng buộc liên quan đến tồn kho sản phẩm TRONG : 2x1 +1x2 £8. Sự ràng buộc về tỷ lệ nhu cầu về sơn có thể được mô tả bằng sự bất bình đẳng: x 2 - x 1 £1. Xét đến các điều kiện tự nhiên để khối lượng sản xuất không âm, cuối cùng chúng ta thu được bài toán quy hoạch tuyến tính sau

f(x) = 3 x 1 + 2 x 2 ® tối đa (1.1)

1 x 1 + 2 x 2 £ 6 , (1.2)

2x1 + 1x2 £ 8 , (1.3)

- x 1 + x 2 £1 , (1.4)

x 1 ³ 0, x 2 ³ 0 . (1.5)

Chúng ta hãy xây dựng một tập hợp các phương án bài toán được mô tả bằng các ràng buộc (1.2)-(1.5). Hãy xem xét bất đẳng thức đầu tiên. Nó chỉ định một nửa mặt phẳng nhất định nằm ở một phía của đường ranh giới

trang 1 : 1x1 +2x2 =6

Hãy dựng đường thẳng này trên mặt phẳng có trục tọa độ x 1 Và x 2. Để vẽ một đường thẳng, chỉ cần biết hai điểm của nó là đủ. Cách dễ nhất là tìm giao điểm của một đường thẳng với các trục tọa độ. tin tưởng x 1 = 0, từ phương trình đường thẳng ta có x 2 = 3, và khi x 2 = 0 chúng ta sẽ tìm thấy x 1 = 6. Như vậy thẳng trang 1 sẽ đi qua các điểm (0,3) Và ( 6,0) . Để xác định nửa mặt phẳng mong muốn nằm ở phía nào của đường thẳng, chỉ cần thay tọa độ của bất kỳ điểm nào trên mặt phẳng vào bất đẳng thức (1.2) là đủ. Nếu đường thẳng không đi qua gốc tọa độ thì lấy điểm là thuận lợi nhất (0, 0) . Rõ ràng, tại điểm này bất đẳng thức (1.2) được thỏa mãn nghiêm ngặt (1* 0 + 2* 0 < 6) , có nghĩa là nửa mặt phẳng xác định bởi bất đẳng thức này nằm bên dưới đường thẳng p1, kể cả nguồn gốc. Chúng tôi đánh dấu nửa mặt phẳng mong muốn bằng bóng ( Hình.1.1).

Tương tự, ta dựng nửa mặt phẳng xác định bởi bất đẳng thức (1.3) . Để làm điều này, hãy vẽ một đường ranh giới trên mặt phẳng tọa độ

p2 : 2x1 +x2 =8 ,

tìm giao điểm của nó với trục tọa độ: (0,8) Và (4,0) .

Tọa độ điểm thay thế (0,0) vào bất đẳng thức (2.3), ta thấy gốc tọa độ nằm trong nửa mặt phẳng mong muốn (2* 0 + 1* 0 < 8) , nghĩa là mọi điểm thỏa mãn bất đẳng thức (2.3) đều nằm bên trái đường thẳng p2. Hãy đánh dấu khu vực này bằng bóng ( Hình.1.1).

Các điểm được xác định bởi ràng buộc ( 4 ), nằm dưới đường thẳng

trang 3 : -x 1 +x 2 =1,

đi qua các điểm (0, 1) Và (-1, 0) .

Cuối cùng, điều kiện không âm: x 1 ³ 0, x 2³0 đặt tất cả các điểm của quý đầu tiên mà chúng tôi cũng đánh dấu bằng tô bóng.

Bây giờ, chọn các điểm của mặt phẳng thỏa mãn mọi ràng buộc của bài toán (1.1)-(1.5), nghĩa là nằm đồng thời trên tất cả các nửa mặt phẳng được tô bóng, chúng ta thu được một tập hợp các mặt phẳng X. Nó là một đa giác (trong bài toán này là một hình ngũ giác). Các cạnh của nó nằm trên những đường thẳng và phương trình của nó thu được từ hệ thống gốc bất đẳng thức (1.2)-(1.5) bằng cách thay dấu bất đẳng thức bằng đẳng thức chặt chẽ.

Vì biểu diễn đồ họa của hàm mục tiêu, chúng tôi giới thiệu khái niệm đường mức (hàm isoline).

Sự định nghĩa.Đường mức chức năng (isoline) f(x)được gọi là tập hợp điểm x = (x 1, x2), trong đó nó nhận cùng một giá trị không đổi f(x) = h, Ở đâu h- một số nào đó. Vì hàm tuyến tính hai biến f(x) = c 1 x 1 + c 2 x 2 vạch mức tương ứng với số h, sẽ biểu diễn một đường thẳng với phương trình

c 1 x 1 + c 2 x 2 = h (1.6)

Khi số thay đổi h chúng ta sẽ thu được một họ các đường đồng mức (các đường thẳng song song) có cùng vectơ chỉ phương c = =(c 1 , c 2), vuông góc với mọi đường thẳng. Được biết, vectơ c = (c 1 , c 2) cho hàm tuyến tính f(x) = c 1 x 1 +c 2 x 2 cho biết hướng tăng của nó. Về mặt hình học, điều này có nghĩa là khi chuyển động song song của đường thẳng (1.6) theo hướng của vectơ đích c giá trị của hàm mục tiêu tăng lên.

Hãy xây dựng các đường mức của hàm mục tiêu f(x) = 3x 1 + 2 x 2 trong nhiệm vụ của chúng tôi. Phương trình của chúng sẽ giống như 3x1 + 2x2 = h. Chúng xác định một họ các đường thẳng song song tùy thuộc vào tham số h. Tất cả các đường thẳng đều vuông góc với vectơ mục tiêu c = (3, 2), bao gồm các hệ số của hàm mục tiêu, do đó, để xây dựng một họ các đường cùng mức của hàm mục tiêu, chỉ cần xây dựng vectơ mục tiêu của nó và vẽ một số đường thẳng vuông góc với vectơ này là đủ. Chúng ta sẽ vẽ các đường mức trên nhiều phương án X, hãy nhớ rằng khi di chuyển các đường thẳng song song theo hướng của vectơ mục tiêu c = (3, 2) giá trị hàm f(x)= 3x 1 + 2x 2 sẽ tăng. Vì trong bài toán, phương án tối ưu phải mang lại giá trị lớn nhất có thể cho hàm mục tiêu, nên để giải bài toán bằng đồ thị cần phải có tất cả các điểm. x = (x 1, x2) nhiều kế hoạch X tìm một điểm như vậy x* = (x 1 * , x 2 *), qua đó đường mức cuối cùng sẽ đi theo hướng của vectơ mục tiêu c = (3,2). Từ Hình 1.2, rõ ràng điểm mong muốn sẽ là điểm nằm ở trên cùng của tập hợp X, được hình thành bởi giao điểm của các đường trang 1 Và p2. Giải hệ phương trình mô tả các đường thẳng ta tìm được kế hoạch tối ưu x 1 * = 3 1/3, x 2 * = 1 1/3. Trong trường hợp này, giá trị cực đại của hàm mục tiêu sẽ bằng f(x*) = 12 2 / 3 . Vì vậy, hàng ngày nhà máy phải sản xuất 3 1 / 3 tấn sơn INT Và 1 1 / 3 tấn sơn EXT khi nhận được thu nhập 12 2 / 3 nghìn đô la.

x 1 + 2 x 2 = 6,

2 x 1 + x 2 = 8,

Ví dụ 1.2. Doanh nghiệp y tế mua hai loại phức hợp vitamin tổng hợp “Sức khỏe” và “Tuổi thọ” chứa ba loại vitamin. Số đơn vị của các vitamin này trong một gam phức hợp đa phức, chỉ tiêu yêu cầu của chúng để sử dụng phòng ngừa và giá thành của một gam phức hợp “Sức khỏe” và “Tuổi thọ” được phản ánh trong bảng

Cần bao nhiêu gam phức hợp vitamin tổng hợp của mỗi loại cho một liều phòng ngừa để nhận được tất cả các vitamin ít nhất theo yêu cầu, đồng thời tổng chi phí của chúng là tối thiểu.

Hãy tạo một mô hình toán học của vấn đề. Để làm điều này, chúng tôi giới thiệu các biến: x 1– số lượng phức hợp “Sức khỏe” (gr.) , x 2– số lượng phức hợp “Tuổi thọ” (gr.) cần thiết cho việc sử dụng dự phòng. Hàm mục tiêu biểu thị tổng chi phí của phức hợp vitamin, nên càng thấp càng tốt

f( x)= 5 x 1 + 4 x 2 ® phút (1.7)

Các hạn chế mô tả việc tuân thủ các tiêu chuẩn về vitamin như sau:

Bằng vitamin V 1 : 3x1 + x2 ³ 9 , (1.8)

Bằng vitamin V 2 : x 1 + 2x 2 ³ 8, (1.9)

Bằng vitamin V 3 : x 1 + 6x 2 ³ 12 . (1.10)

Trong trường hợp này, các biến phải không âm: x j ³ 0, j = 1, 2.

Hãy bắt đầu lại giải pháp bằng cách xây dựng nhiều phương án X, trong đó chúng ta vẽ các đường thẳng biên, các phương trình của chúng thu được bằng cách thay thế các dấu bất đẳng thức trong các giới hạn bằng các đẳng thức

trang 1 : 3 x 1 + x 2 = 9,

p2 : x 1 + 2 x 2 = 8,

trang 3 : x 1 + 6 x 2 = 12.

Tọa độ điểm thay thế (0,0) trong bất đẳng thức (1.8)-(1.10) ta thấy gốc tọa độ không thỏa mãn chúng nên không nằm trong tập phương án X. Vì vậy, các cửa sập được hướng lên phía trên và bên phải của đường ranh giới. Bằng cách xác định các điểm thỏa mãn mọi bất đẳng thức và điều kiện không âm, chúng ta thu được tập hợp các kế hoạch như trong Hình 2. 1.2. TRONG trong ví dụ này nó không bị giới hạn.

Chúng ta hãy mô tả hàm mục tiêu (1.7) bằng cách sử dụng các đường mức. Để làm được điều này, chỉ cần xây dựng vectơ mục tiêu là đủ c = (5, 4) và vẽ một số đường thẳng vuông góc với nó trên tập hợp X. Vì vectơ mục tiêu chỉ ra hướng tăng của hàm mục tiêu và trong bài toán ăn kiêng cần phải tìm giá trị cực tiểu của nó, sau đó tìm giải pháp tối ưu chúng ta sẽ di chuyển đường mức song song với chính nó dọc theo tập hợp X theo hướng ngược lại với vectơ mục tiêu.

Điểm cuối cùng của tập hợp các mặt bằng mà đường đồng mức vẫn đi qua sẽ là giao điểm của các đường trang 1 Và p2. Giải hệ uranium (Hình 1.3).

3 x 1 + x 2 = 9

x 1 + 2 x 2 = 8

chúng tôi có được kế hoạch tối ưu x 1 * = 2, x 2 * = 3. Giá trị tối thiểu của hàm mục tiêu sẽ bằng

f(x*) = 5∙2 + 4∙3 = 22.

Vì vậy, bộ dụng cụ dự phòng rẻ nhất bao gồm 2 g. phức hợp A và 3 g. tổ hợp TRONG, và giá của nó là 22 chà xát.

Bây giờ thật dễ dàng để xây dựng một giải pháp hình học nhiệm vụ tiêu chuẩn LP với hai biến:

· một đa giác chấp nhận được được mô tả - giao điểm của các nửa mặt phẳng là nghiệm của các bất đẳng thức tương ứng;

· vectơ mục tiêu được mô tả;

· Đường vuông góc với vectơ mục tiêu được vẽ thông qua tập hợp chấp nhận được - đây là đường mức của hàm mục tiêu;

· bằng cách di chuyển đường mức song song với chính nó theo hướng của vectơ mục tiêu cho đến khi nó nằm về một phía của đường thẳng chuyển động, điểm (hoặc các điểm) cực đại được xác định bằng mắt;

· Tính tọa độ của điểm cực đại (bằng cách giải hệ phương trình tương ứng xác định đường thẳng, giao điểm của nó là điểm mong muốn) và giá trị cực đại của hàm mục tiêu.

Bình luận.Để xác định điểm tối thiểu, hãy di chuyển đường cô lập ngược hướng của vectơ mục tiêu.

Trong các ví dụ được phân tích, phương án tối ưu nằm ở đỉnh duy nhất của đa giác của các phương án khả thi. Tuy nhiên, khi giải bài toán LP, các trường hợp khác cũng có thể phát sinh.

Vô số phương án tối ưu. TRÊN Hình.1.4 hàm mục tiêu có cùng giá trị lớn nhất tại bất kỳ điểm nào trên đoạn AB nối hai đỉnh của một tập hợp các mặt bằng X. Tình huống này xảy ra nếu các đường mức song song với đường biên.

Không có giải pháp hạn chế. TRÊN Hình.1.5 Trường hợp được mô tả khi hàm mục tiêu không bị giới hạn ở trên trong tập kế hoạch và không tồn tại nghiệm của bài toán cực đại. Trong trường hợp này, có thể tồn tại một giải pháp cho vấn đề tối thiểu (như trong vấn đề vitamin).

Thiếu các kế hoạch hợp lệ. TRÊN Hình.1.6 Các khu vực được phép theo từng hạn chế không có điểm chung. Trong trường hợp này, họ nói rằng các ràng buộc không nhất quán, tập kế hoạch trống và bài toán LP không có lời giải.

Cơm. 1.4 Hình. 1.5 Hình. 1.6

2. Phương pháp đơn giản

2.1 Ý tưởng của phương pháp đơn hình

Hãy xem xét phương pháp phổ quát giải bài toán quy hoạch tuyến tính chuẩn tắc

, , ,

Với N biến và tôi các ràng buộc đẳng thức, được gọi là phương pháp đơn hình.

Tập các mặt phẳng của một bài toán chính tắc là một tập đa diện lồi với số hữu hạn các điểm góc. Và nếu bài toán này có lời giải tối ưu thì nó đạt được ít nhất ở một điểm góc.

Bất kỳ điểm góc nào cũng được liên kết với một mặt phẳng cơ bản của bài toán, trong đó các biến bằng 0 và các biến còn lại tương ứng với các cột độc lập tuyến tính của ma trận điều kiện. Các cột độc lập tuyến tính này tạo thành một ma trận cơ sở không đơn lẻ.

Việc lặp lại tất cả các điểm góc tốn kém về mặt tính toán và do đó không hiệu quả. Năm 1947, J. Danzig đề xuất một quy trình có trật tự để liệt kê các điểm góc, trong đó chỉ cần kiểm tra một phần nhỏ trong số đó là đủ để tìm ra giải pháp tối ưu. Thủ tục này được gọi là phương pháp đơn giản .

J. Danzig đề xuất chỉ thay thế một vectơ trong ma trận cơ sở khi chuyển từ điểm cực trị này sang điểm cực trị khác. Điều này có nghĩa là trong quá trình chuyển đổi như vậy, chúng ta phải loại trừ một trong các biến cơ bản - làm cho nó không cơ bản ( bằng 0) và thay vào đó là một biến mới trong số các biến không cơ bản (không) - biến nó thành cơ bản (dương).

Nó chỉ ra rằng về mặt hình học, sự thay thế như vậy dẫn đến sự chuyển đổi từ điểm góc này sang điểm liền kề, được kết nối với điểm trước đó bằng một cạnh chung.

Trong số tất cả các điểm lân cận, điểm mà hàm mục tiêu tăng nhiều nhất sẽ được chọn. Vì số lượng điểm góc là hữu hạn nên qua một số hữu hạn bước chuyển tiếp, đỉnh có giá trị cao nhất hàm mục tiêu, hoặc tính không giới hạn của hàm mục tiêu sẽ được thiết lập trên một tập kế hoạch không giới hạn.

Đề án chung Phương pháp đơn giản bao gồm các bước cơ bản sau.

· bước 0. Xác định cơ sở ban đầu và điểm góc ban đầu tương ứng (đường cơ sở).

· bước 1. Kiểm tra đường cơ sở hiện tại để tối ưu . Nếu tiêu chí tối ưu được đáp ứng thì phương án là tối ưu và giải pháp là hoàn chỉnh. Nếu không thì chuyển sang bước 2.

· bước 2. Tìm biến được đưa vào biến cơ bản. (Từ điều kiện tăng hàm mục tiêu).

· bước 3. Tìm một biến bị loại trừ khỏi các biến cơ bản (Từ điều kiện bảo toàn các ràng buộc của bài toán).

· bước chân 4 . Tìm tọa độ của đường cơ sở mới (điểm góc liền kề). Đi tới bước 1.

Các bước lặp lại từ 1–4 tạo thành một lần lặp của phương pháp đơn hình.

Từ sơ đồ này, trước tiên, để bắt đầu phương pháp đơn hình, bạn cần phải có một số loại điểm góc - một sơ đồ cơ bản ban đầu, và thứ hai, bạn cần có khả năng kiểm tra điểm góc hiện tại để tìm mức tối ưu mà không cần tính toán tất cả các điểm liền kề đỉnh. Những vấn đề này có thể giải quyết dễ dàng nếu bài toán LP chuẩn có một loại đặc biệt.

Sự định nghĩa. Chúng ta sẽ nói rằng bài toán LP chuẩn có “dạng ưa thích” nếu

1. vế phải của các phương trình , .

2. ma trận điều kiện chứa ma trận con đơn vị có kích thước

Nói cách khác, trong bất kỳ phương trình nào cũng có một biến có hệ số bằng một, bị thiếu trong các phương trình khác. Điều kiện đầu tiên không nặng nề, vì trong trường hợp vế phải âm của một phương trình nào đó, chỉ cần nhân nó với (–1). Trong bài toán loại ưu tiên, việc tìm đường cơ sở ban đầu rất đơn giản.

Ví dụ 2.1.

Ma trận điều kiện MỘT và vectơ vế phải của các ràng buộc b trông giống như

, ,

và vectơ mục tiêu c = (1, -3, 0, 4, 2).

Một ma trận cơ sở là rõ ràng ngay lập tức: với vectơ đơn vị của điều kiện.

Vì vậy, việc chọn làm biến cơ bản x 1 , x 3 ,x 5 và đưa vào hệ phương trình x 2 = x 4 = 0 (biến không cơ bản) , chúng tôi tìm thấy nó ngay lập tức x 1 = 10,x 3 = 20,x 5 = 8, vậy đường cơ sở ban đầu x 0= (10, 0, 20, 0, 8). Ta thấy giá trị của các biến cơ bản bằng vế phải của ràng buộc. Từ đó rõ ràng là vế phải phải dương b tôi.

Trong tương lai chúng ta sẽ kết hợp các biến cơ bản thành một vector xB.

Như vậy, trong bài toán chính tắc dạng ưu tiên, ma trận con đẳng thức được lấy làm ma trận cơ sở ban đầu A B = E và các biến cơ sở tương ứng bằng vế phải của các ràng buộc:

x B = b .

Đối với một kế hoạch cơ bản thuộc loại này, có thể xây dựng được một tiêu chí tối ưu đủ đơn giản để kiểm tra. Hãy giới thiệu số lượng

∆j =< с Б, A j >– c j , j = 1,...,n, (2.1)

Ở đâu với B– vectơ hệ số của hàm mục tiêu cho các biến cơ bản x B , Aj – j- cột của ma trận điều kiện, cj – j- hệ số thứ của hàm mục tiêu. Sự khác biệt ∆jđược gọi là sai phân đơn giản hoặc ước lượng đơn giản.

Tiêu chí tối ưu cho phương án cơ bản. Nếu đối với một kế hoạch cơ bản có ma trận cơ sở đơn vị, tất cả các ước lượng đơn đều không âm thì kế hoạch này là tối ưu.

Chúng ta hãy áp dụng tiêu chí này để kiểm tra tính tối ưu của phương án cơ bản x 0= (10, 0, 20, 0, 8) từ ví dụ 2.1.

Vì về mặt này vectơ của các biến cơ bản x B =(x 1 , x 3 ,x 5), Cái đó với B = (c 1 , c 3 ,c 5) = (1, 0, 2).

Kể từ đây,

∆ 1 = < с Б, A 1 >- từ 1 =1∙1 + 0∙0 + 2∙0 – 1= 0,

∆ 2 = < с Б, A 2 >– c 2 =1∙3 + 0∙1 + 2∙2 – (-3) = 10,

∆ 3 = < с Б, A 3 >– c 3 =1∙0 + 0∙1 + 2∙0 – 0= 0,

∆ 4 = < с Б, A 4 >– c 4 =1∙(-1) + 0∙5 + 2∙1 – 4= -3,

∆ 5 = < с Б, A 5 >– từ 5 =1∙0 + 0∙0 + 2∙1 – 2= 0.

Kể từ khi đánh giá ∆ 4 < 0, то базисный план x 0 không tối ưu. Lưu ý rằng các ước lượng đơn tương ứng với các biến cơ bản luôn bằng 0, do đó chỉ cần kiểm tra các ước lượng không cơ bản là đủ.

2.2 Thực hiện phương pháp đơn hình bằng ví dụ

Hãy để chúng tôi chứng minh việc sử dụng phương pháp đơn giản bằng một ví dụ. Hãy xem xét vấn đề kinh điển LP

f(x) = x 1 + 2x 2 + 0x 3 + 0x 4 → tối đa	(2.2)
–x 1 + 2x 2 +x 3 = 4,	(2.3)
3x 1 + 2x 2 +x 4 = 12,	(2.4)
x j ≥ 0, j = 1,2,3,4.	(2.5)

Ma trận điều kiện MỘT = (MỘT 1 , MỘT 2 , MỘT 3 , MỘT 4), ở đâu

Vectơ mục tiêu c =(c 1, c2, c 3, c 4) = (1, 2, 0, 0); vector phần bên phải b =(b 1 , b 2) = (4, 12).

Bước 0. Tìm điểm góc bắt đầu (đường cơ sở).

Bài toán có dạng thích hợp hơn, vì vế phải của phương trình là dương và các cột của ma trận điều kiện MỘT 3, MỘT 4 tạo thành một ma trận con đơn vị. Điều này có nghĩa là ma trận cơ sở ban đầu = (MỘT 3 ,A 4); x 3 và x 4 – biến cơ bản x 1 và x 2 - các biến không cơ bản, c B = (c 3, c 4) = = (0, 0).

Đường cơ sở ban đầu trông giống như x 0 = (0, 0, x 3 , x 4) = (0, 0, 4, 12); f( x o)= 0.

Bước 1. Kiểm tra kế hoạch cơ bản để tối ưu.

Hãy tính ước lượng đơn giản cho các biến không cơ bản bằng công thức (5.1)

 1 = < c B, MỘT 1 > – c 1 = 0 ·(–1) + 0 ·3 – 1 = –1 .

 2 = < c B, MỘT 2 > – c 2 = 0 2 + 0 2 – 2 = –2 .

Vì các ước tính là âm nên kế hoạch x – không tối ưu. Chúng ta sẽ tìm một đường cơ sở mới (điểm góc liền kề) với giá trị lớn hơn của hàm mục tiêu.

Bước 2. Tìm biến được đưa vào cơ sở.

Hàm mục tiêu có thể được tăng lên bằng cách đưa một trong các biến không cơ bản vào các biến cơ bản (làm cho nó dương) x 1 hoặc x 2, vì cả hai ước tính  j < 0. Обычно в состав базисных вводят небазисную переменную с наибольшей по модулю отрицательной оценкой, поэтому будем вводить в базис переменную x 2.

Bước 3.Định nghĩa của một biến xuất phát từ cơ sở.

Sau khi nhập biến vào cơ sở x 2 kế hoạch mới sẽ như thế nào

x" = (0, x 2, x 3 , x 4).

Kế hoạch này không phải là kế hoạch cơ bản, vì nó chỉ chứa một tọa độ 0, có nghĩa là cần phải tạo một trong các biến bằng 0 (loại trừ khỏi cơ sở) x 3 hoặc x 4 . Hãy thay thế tọa độ của kế hoạch x" = (0, x 2, x 3 ,x 4) trong các ràng buộc của vấn đề. Chúng tôi nhận được

2x 2 + x 3 = 4,

2x 2 + x 4 = 12.

Hãy để chúng tôi thể hiện các biến cơ bản từ đây x 3 và x 4 thông qua biến x 2 , được đưa vào cơ sở.

Làm sao nhiều giá trị hơn x 2 , hàm mục tiêu càng tăng. Hãy tìm giá trị lớn nhất của biến cơ sở mới không vi phạm ràng buộc của bài toán, tức là thỏa mãn điều kiện (2.8), (2.9).

Hãy viết lại các bất đẳng thức cuối cùng dưới dạng

2x 2 ≤ 4,

2x 2 ≤ 12,

giá trị tối đa đến từ đâu? x 2 = min ( 4/2, 12/2 ) = 2. Thay giá trị này vào các biểu thức (2.6), (2.7) cho x 3 và x 4, chúng tôi nhận được x 3 = 0. Do đó x 3 xuất phát từ cơ sở .

Bước 4. Xác định tọa độ của đường cơ sở mới.

Đường cơ sở mới (điểm góc liền kề) là:

x" = (0, x 2, 0, x 4)

Cơ sở của điểm này bao gồm các cột MỘT 2 và MỘT 4 , vậy =( MỘT 2, MỘT 4). Cơ sở này không đơn nhất, vì vectơ MỘT 2 = (2,2), và do đó bài toán (2.2)–(2.5) không có dạng ưu tiên đối với cơ sở mới. Ta biến đổi điều kiện của bài toán (2.3), (2.4) sao cho nó có dạng ưu tiên đối với các biến cơ bản mới x 2, x 4, nghĩa là, sao cho biến x 2 được đưa vào phương trình thứ nhất với hệ số bằng 1 và không có trong phương trình thứ hai. Hãy viết lại các phương trình của bài toán

– x 1 + 2 x 2 + x 3 = 4, (P 1)

3x 1 +2 x 2 + x 4 = 12. (P 2)

Hãy chia phương trình đầu tiên cho hệ số tại x 2. Hãy tìm một phương trình mới = p 1/2 tương đương với bản gốc

– 1/2 x 1 + x 2 + 1/2 x 3 = 2. ( )

Chúng tôi sử dụng phương trình này, mà chúng tôi gọi là giải quyết, để loại bỏ biến x 2 từ phương trình thứ hai. Để làm được điều này chúng ta cần phương trình nhân với 2 và trừ từ P 2 . Chúng tôi nhận được = p 2 – 2= p 2 -P 1:

4 x 1 – x 3 + x 4 = 8. ( )

Kết quả là chúng ta thu được một cách biểu diễn “ưu tiên” mới của bài toán ban đầu đối với các biến cơ bản mới. x 2 , x 4:

f (x) = x 1 + 2 x 2 + 0 x 3 + 0 x 4  tối đa

– 1/2 x 1 + x 2 + 1/2 x 3 = 2 ( )

4 x 1 – x 3 + x 4 = 8 ( )

x j 0, j = 1,2,3,4

Thay thế ở đây bằng cách thể hiện đường cơ sở mới x 1 = (0, x 2, 0, x 4), chúng ta sẽ tìm ngay tọa độ của nó, vì giá trị của các biến cơ bản bằng vế phải của phương trình

x" = (0, 2, 0, 8); f (x 1)=4.

Điều này hoàn thành lần lặp đầu tiên phương pháp đơn giản. Tiếp theo, quá trình giải quyết vấn đề tiếp tục từ bước 1, bao gồm việc kiểm tra phương án tìm được ở mức tối ưu. Giải pháp kết thúc khi tất cả các ước tính đơn giản của kế hoạch cơ bản hiện tại hóa ra không âm.

Chúng tôi sẽ không thực hiện lần lặp thứ hai theo sơ đồ của lần lặp đầu tiên, vì sẽ thuận tiện hơn khi thực hiện tất cả các phép tính của phương pháp đơn hình trong dạng bảng.

2.3 Triển khai dạng bảng của một phương pháp đơn giản

Chúng ta sẽ chứng minh cách triển khai dạng bảng bằng cách sử dụng cùng một ví dụ (2.2)–(2.5).

Bước 0. Giải pháp bắt đầu bằng cách xây dựng một bảng đơn giản ban đầu. Điền vào đầu tiên phần bên phải bảng từ cột thứ ba. Trong hai dòng trên cùng tên được ghi lại biến vấn đề (x 1, ...,x 4) và các hệ số của hàm mục tiêu cho các biến này. Dưới đây là các hệ số của các phương trình - phần tử của ma trận điều kiện MỘT, do đó dưới biến x 1 là cột định vị MỘT 1, dưới biến x 2 – cột MỘT 2, v.v. Vế phải của các ràng buộc (số) được nhập vào cột bên phải tôi > 0).

Sau đó, chúng ta tìm các cột của ma trận điều kiện tạo thành cơ sở đơn vị - trong ví dụ của chúng ta đây là MỘT 3 và MỘT 4 và các biến cơ bản tương ứng x 3, x 4 được viết ở cột thứ hai. Cuối cùng, ở cột đầu tiên chúng ta viết các hệ số của hàm mục tiêu cho các biến cơ bản.

Bảng 1 - Bảng đơn giản ban đầu

S B	Biến cơ bản	với 1 = 1	với 2 = 2	với 3 = 0	với 4 = 0	Giá trị biến cơ bản ( x B = b)
S B	Biến cơ bản	*x 1*	*x 2*	*x 3*	*x 4*	Giá trị biến cơ bản ( x B = b)
c 3 = 0	*x 3*	một 11 =-1	một 12 = 2	một 13 = 1	một 14 = 0	b 1 = 4
c 4 = 0	*x 4*	21 = 3	một 22 = 2	một 23 = 0	một 24 = 1	b 2 =12
Dòng đánh giá  j		 1 = -1	 2 = -2	 3 = 0	 4 = 0	f(x)= 0

Vì bài toán có dạng ưu tiên nên giá trị của các biến cơ bản bằng vế phải của các phương trình nằm ở cột cuối cùng. Vì các biến phi cơ sở bằng 0 nên đường cơ sở ban đầu là

x o = (0, 0, x 3 , x 4) = (0, 0, 4, 12).

Bước 1.Để kiểm tra kế hoạch x o để tối ưu, chúng tôi tính toán ước tính đơn giản cho các biến không cơ bản x 1 và x 2 theo công thức

 j =< c Б , A j > – c j .

 1 = < c Б , MỘT 1 > – c 1 = 0 ·(–1) + 0 ·3 – 1 = –1 .

Với cách triển khai dạng bảng để tính điểm  1 chúng ta cần tìm tổng tích của các phần tử ở cột đầu tiên ( c B)đến các phần tử cột tương ứng MỘT 1 cho biến không cơ bản x 1 . Điểm được tính tương tự  2 , là tích vô hướng của cột đầu tiên ( c B) mỗi cột tại biến x 2 .

 2 = < c B, MỘT 2 > – c 2 = 0 2 + 0 2 – 2 = –2 .

Các ước lượng đơn giản được viết ở hàng cuối cùng của bảng đơn giản, được gọi là hàng delta. Trong trường hợp này, không chỉ các ô cho các biến không cơ bản được điền mà còn cả các ô cơ bản. Dễ dàng kiểm tra xem đối với các cột đơn vị cơ bản của ma trận điều kiện, các ước lượng đơn giản có bằng 0 hay không. Trong ô cuối cùng của dòng đánh giá, chúng ta viết giá trị của hàm mục tiêu tại điểm xo. Lưu ý rằng vì tọa độ không cơ bản của sơ đồ cơ bản bằng 0 nên việc tính hàm mục tiêu bằng công thức sẽ rất thuận tiện

f (x)= < c B ,x B >,

nhân vô hướng các cột đầu tiên và cuối cùng của bảng.

Vì trong số các ước tính  j có tiêu cực , sau đó kế hoạch x o không tối ưu và cần phải tìm ra một phương án cơ bản mới bằng cách thay thế một trong các biến cơ bản bằng một biến mới trong số các biến không cơ bản.

Bước 2. Vì cả hai ước tính  1 và  2 < 0,то в базис можно включить любую из переменных x 1, x 2 . Hãy để chúng tôi đưa vào cơ sở biến có ước tính âm tuyệt đối lớn nhất, đó là x 2 .

Cột của bảng đơn chứa biến được nhập vào cơ sở được gọi là cột dẫn đầu .

Trong ví dụ, cột đầu tiên sẽ ở x2 .

Bước 3. Nếu tất cả các phần tử ở cột đầu đều âm thì không có giải pháp nào cho vấn đề và giá trị tối đa f (x) . Trong ví dụ, tất cả các phần tử của cột đầu đều dương, do đó, chúng ta có thể tìm thấy giá trị lớn nhất x 2 , tại đó một trong các biến cơ bản cũ sẽ bằng 0. Hãy nhớ rằng giá trị tối đa x 2 = phút(4/2, 12/2)=2.

Theo bảng, giá trị này được tính như sau tỷ lệ nhỏ nhất của các thành phần của đường cơ sở (từ cột cuối cùng) với thành phần tương ứng tích cực các phần tử của cột đầu.

Tỷ lệ nhỏ nhất nằm ở hàng có biến cơ sở x3. Vì vậy biến x 3 loại trừ khỏi các biến cơ bản ( x 3 = 0).

Dòng chứa biến bị loại khỏi cơ sở được gọi là dòng dẫn đầu.

Trong ví dụ, dòng dẫn đầu sẽ là dòng đầu tiên.

Phần tử nằm ở giao điểm của hàng đầu và cột đầu được gọi là phần tử đầu.

Trong trường hợp của chúng tôi, phần tử hàng đầu Một 12 = 2.

Bàn 2 - Bảng đơn giản ban đầu có hàng và cột ở đầu

c B	Những thay đổi cơ bản.	với 1 = 1	với 2 = 2	với 3 = 0	C 4 = 0	Giá trị biến cơ bản	phương trình
c B	Những thay đổi cơ bản.	x 1	*x 2*	x 3	x 4	Giá trị biến cơ bản	phương trình
*c 3 = 0*	x 3	–1	2	1	0	4	trang 1
c 4 = 0	x 4	3	2	0	1	12	p2
Dòng đánh giá  j		 1 = –1	 2 = –2	 3 = 0	 4 = 0	f(x)= 0

Bước 4. Để có được một kế hoạch cơ bản mới, chúng ta quy bài toán về một dạng ưu tiên mới đối với các biến cơ bản mới.

Để làm điều này, hãy xây dựng một bảng đơn giản mới, trong cột thứ hai thay vì biến bị loại trừ x 3 hãy viết một biến cơ bản mới x 2, và trong cột đầu tiên ( với B) thay vì từ 3 Hãy viết hệ số của hàm mục tiêu tại x 2 : c 2 =2. Trong bảng đơn giản mới, cột tại x 2 phải trở thành một (phần tử đứng đầu phải bằng 1 và tất cả các phần tử khác phải bằng 0). Điều này đạt được bằng các phép biến đổi hàng trong bảng sau.

Một. Chúng ta chia tất cả các phần tử của hàng đầu cho phần tử đầu và viết chúng vào cùng một hàng của bảng đơn giản mới.

Chuỗi kết quả p 1" Hãy gọi nó là sự cho phép.

b. Đối với dòng thứ hai còn lại, chúng ta thêm dòng phân giải, nhân với một số sao cho phần tử ở cột đầu bằng 0.

p 2 "= p 2 + (- 2) p 1 "= p 2 - p 1.

c. Hãy điền vào dòng cuối cùng bằng cách tính toán các ước tính  j " =< c Б ", A j " >- - cj,Ở đâu c B", A j " - các cột tương ứng của bảng đơn giản mới và giá trị của hàm mục tiêu f(x)=< c Б ", x Б " >.

Chúng ta thu được bảng đơn thứ hai với cơ sở mới.

Bảng 3 - Kết quả của lần lặp đầu tiên

c B"	Những thay đổi cơ bản.	với 1 = 1	với 2 = 2	với 3 = 0	với 4 = 0	Giá trị biến cơ bản	phương trình
c B"	Những thay đổi cơ bản.	x 1	x 2	x 3	x 4	Giá trị biến cơ bản	phương trình
c 2 =2	x 2	*–1/2*	1	1/2	0	2	p 1" =p 1/2
c 4 = 0	*x 4*	4	0	-1	1	8	p 2 " =p 2 - p 1
ước tính j"		–2	0	1	0	f(x")=4

Kế hoạch cơ bản mới x " = (0, x 2, 0, x 4) = (0, 2, 0, 8 ).

Kể từ khi đánh giá  1 = -2 < 0, sau đó kế hoạch x " không tối ưu. Để chuyển sang một sơ đồ cơ bản mới (của điểm góc lân cận), chúng ta sẽ thực hiện một phép lặp khác của phương pháp đơn hình.

Bởi vì  1 < 0, sau đó một biến được đưa vào cơ sở x 1 . Cột đầu tiên chứa x 1 - dẫn đầu.

Chúng tôi tìm thấy mối quan hệ giữa các thành phần của kế hoạch cơ bản và tương ứng tích cực phần tử của cột đầu tiên và lấy hàng có tỷ lệ nhỏ nhất làm hàng đầu. Trong Bảng 2, ở cột đầu tiên chỉ có phần tử thứ hai lớn hơn 0 (= 4), do đó dòng thứ hai sẽ là dòng dẫn đầu, và cơ sở nằm trong đó Biến đổi x 4 bị loại khỏi cơ sở .

Chúng tôi chọn cột đầu tiên và hàng đầu tiên và tại giao điểm của chúng, chúng tôi tìm thấy phần tử dẫn đầu (= 4) .

Chúng tôi xây dựng một bảng đơn giản (thứ ba) mới, thay thế biến cơ bản trong đó x 4 TRÊN x 1 , đồng thời biến đổi lại các hàng của bảng sao cho phần tử đứng đầu bằng 1 và các phần tử còn lại của cột dẫn đầu trở thành 0. Để thực hiện việc này, hãy chia dòng đầu tiên (thứ hai) cho 4 và thêm dòng thứ hai chia cho 2 vào dòng đầu tiên. Dòng cuối cùng tính toán bằng cách sử dụng các công thức ước tính đơn giản  j "" = < c Б "", Aj ""> - c j,Ở đâu c B "", Aj "" - các cột tương ứng của bảng đơn giản mới. Giá trị của hàm mục tiêu trên đường cơ sở mới được tìm thấy bằng công thức f(x "")= < c Б "", x B "" >.

Bảng 4 - Kết quả của lần lặp thứ hai

c B ""	Nền tảng thay đổi.	với 1 = 1	với 2 = 2	với 3 = 0	với 4 = 0	Giá trị biến cơ bản	phương trình
c B ""	Nền tảng thay đổi.	x 1	x 2	x 3	x 4	Giá trị biến cơ bản	phương trình
c 2 =2	x 2	0	1	3/8	1/8	3	trang 1 "" = p 1 "+p 2 ""/2
c 1 = 1	x 1	1	0	-1/4	1/4	2	p 2 "" = p 2 "/4
ước tính  j ""		0	0	1/2	1/2	f(x "")= 8

Kế hoạch cơ bản mới x "" = (x 1 , x 2 , 0, 0) = (2, 3, 0, 0 ). Vì tất cả các ước lượng đều không âm nên kế hoạch x ""- phương án tối ưu.

Như vậy, x* = (2, 3, 0, 0 ), f(x*) = 8.

PHẦN KẾT LUẬN

Các phương pháp được xem xét để giải các bài toán quy hoạch tuyến tính được sử dụng rộng rãi trong thực tế. Tuy nhiên, cần lưu ý rằng mô hình toán học luôn kém hơn mô hình thực tế hệ thống kinh tế. Nó chỉ mô tả hệ thống này một cách gần đúng, làm nổi bật một số thuộc tính và bỏ qua những thuộc tính khác. Để bù đắp cho sự thiếu sót này trong kinh tế toán học, một số loại mô hình đang được phát triển, mỗi loại được thiết kế để phản ánh một khía cạnh cụ thể của thực tế kinh tế để khi giải quyết một vấn đề cụ thể vấn đề kinh tế có thể chọn một mô hình phù hợp nhất với nó.

DANH MỤC TÀI LIỆU THAM KHẢO ĐƯỢC SỬ DỤNG

1. Ashmanov SA Lập trình tuyến tính. – M.: Nauka, 1981.

2. Kuznetsov Yu.N., Kuzubov V.I., Voloshchenko A.B. Lập trình toán học. – M.: trường sau đại học, 1980.

3. Kalikhman I.L. Đại số tuyến tính và lập trình. – M.: Trường Cao Đẳng, 1967.

4. Nit I.V. Lập trình tuyến tính. – M.: Nhà xuất bản Đại học Quốc gia Mátxcơva, 1978.

5. Yudin D.B., Golshtein E.G. Lập trình tuyến tính. Lý thuyết và phương pháp cuối cùng. – M.: Fizmatiz, 1963.

6. Tarasenko N.V. Toán-2. Lập trình tuyến tính: Giáo trình. – Irkutsk: nhà xuất bản BGUEP, 2003.

7. Lập trình toán học trong các ví dụ và bài toán: Proc. trợ cấp. – tái bản lần thứ 2, tái bản. và bổ sung – M.: Cao hơn. trường học, 1993. – 336 tr.

8. www.yandex.ru

9. www.mathematica.ru

Ý tưởng của phương pháp đơn giản

Phương pháp đơn giản

Ở phần trước đã chỉ ra rằng nếu một bài toán quy hoạch tuyến tính có một lời giải tối ưu thì một trong những lời giải tối ưu là lời giải có thể chấp nhận được. giải pháp cơ bản hệ thống các hạn chế của nó, tương ứng với một điểm góc nhất định của khối đa diện của các nghiệm chấp nhận được của hệ thống. Nó đã chỉ ra cách tìm nghiệm tối ưu này bằng cách sử dụng tìm kiếm hữu hạn các nghiệm cơ bản của hệ ràng buộc của bài toán. Tuy nhiên, khi chiều n của hệ ràng buộc bài toán tăng lên, khối lượng tính toán giải bài toán bằng phương pháp liệt kê đầy đủ các nghiệm cơ bản tăng theo cấp số nhân và trở nên không phù hợp trong thực tế. Có thể tổ chức liệt kê chỉ các giải pháp cơ bản khả thi và giảm mạnh số lượng giải pháp liệt kê nếu mỗi giải pháp cơ bản được chấp nhận tiếp theo được chọn sao cho giá trị tương ứng của hàm mục tiêu được cải thiện hoặc ít nhất không bị suy giảm. Cách tiếp cận này cho phép bạn giảm số bước khi tìm giải pháp cơ bản tối ưu. Hãy để chúng tôi giải thích ý tưởng này bằng đồ họa.

Cho đa giác ABCDEFGH biểu diễn tập nghiệm chấp nhận được của PLP với hai biến và vectơ – gradient của hàm mục tiêu.

Chúng ta cần tìm điểm của đa giác này mà tại đó hàm mục tiêu có giá trị nhỏ nhất. Hãy xác định nghiệm cơ bản được chấp nhận ban đầu của bài toán tương ứng với điểm góc B. Sau khi tìm kiếm đầy đủ tất cả các nghiệm cơ bản được chấp nhận, cần phải kiểm tra tám nghiệm như vậy tương ứng với tám điểm góc của đa giác. Tuy nhiên, có thể thấy rõ từ hình vẽ rằng, có tính đến hướng của gradient, sẽ có lợi hơn nếu đi đến đỉnh C lân cận, sau đó đến đỉnh D lân cận, tương ứng với lời giải cơ bản tối ưu của bài toán. Như vậy, thay vì 8 giải pháp thì chỉ cần xem xét 3 giải pháp cơ bản khả thi.

Ý tưởng cải tiến tuần tự lời giải là cơ sở của phương pháp phổ quát để giải các bài toán quy hoạch tuyến tính – phương pháp đơn giản.

Ý nghĩa hình học của phương pháp đơn hình là việc chuyển đổi tuần tự được thực hiện từ một đỉnh của khối đa diện có lời giải khả thi sang bài toán lân cận, trong đó hàm mục tiêu nhận giá trị không kém hơn ở đỉnh trước đó. Quá trình chuyển đổi này tiếp tục cho đến khi tìm được giải pháp tối ưu hoặc phát hiện ra rằng bài toán không có giải pháp tối ưu.

Phương pháp đơn hình và tên của nó được đề xuất lần đầu tiên bởi nhà toán học người Mỹ John Danzig vào năm 1947, mặc dù ý tưởng của phương pháp này đã được nhà toán học người Nga L.V. Kantorovich trở lại năm 1939 trong bài viết “ Phương pháp toán học tổ chức và lập kế hoạch sản xuất.”

Phương pháp đơn giản bao gồm ba yếu tố chính.

Hãy xem xét một phương pháp phổ quát để giải bài toán quy hoạch tuyến tính chuẩn

Với N biến và tôi các ràng buộc đẳng thức, được gọi là phương pháp đơn hình.

J. Danzig đề xuất chỉ thay thế một vectơ trong ma trận cơ sở khi chuyển từ điểm cực trị này sang điểm cực trị khác. Điều này có nghĩa là trong quá trình chuyển đổi như vậy, chúng ta phải loại trừ một trong các biến cơ bản - làm cho nó không cơ bản (bằng 0) và thay vào đó đưa vào một biến mới trong số các biến không cơ bản (không) - làm cho nó trở thành cơ bản (dương) ).

Trong số tất cả các điểm lân cận, điểm mà hàm mục tiêu tăng nhiều nhất sẽ được chọn. Vì số lượng điểm góc là hữu hạn nên thông qua một số hữu hạn các chuyển đổi sẽ tìm được đỉnh có giá trị lớn nhất của hàm mục tiêu hoặc tính không giới hạn của hàm mục tiêu sẽ được thiết lập trên một tập hợp kế hoạch không giới hạn.

Sơ đồ chung của phương pháp đơn hình bao gồm các bước chính sau.

· bước 0. Xác định cơ sở ban đầu và điểm góc ban đầu tương ứng (đường cơ sở).

· bước 1. Kiểm tra đường cơ sở hiện tại để tối ưu . Nếu tiêu chí tối ưu được thỏa mãn thì Cái đó kế hoạch là tối ưu và giải pháp đã hoàn tất. Nếu không thì chuyển sang bước 2.

· bước 2. Tìm biến được đưa vào biến cơ bản. (Từ điều kiện tăng hàm mục tiêu).

· bước 3. Tìm một biến bị loại trừ khỏi các biến cơ bản (Từ điều kiện bảo toàn các ràng buộc của bài toán).

· bước chân 4 . Tìm tọa độ của đường cơ sở mới (điểm góc liền kề). Đi tới bước 1.

Các bước lặp lại từ 1 đến 4 tạo thành một lần lặp của phương pháp đơn hình.

Sự định nghĩa. Chúng ta sẽ nói rằng bài toán LP chuẩn có “dạng ưa thích” nếu

1. vế phải của phương trình, .

2. ma trận điều kiện chứa ma trận con đơn vị có kích thước

Nói cách khác, trong bất kỳ phương trình nào cũng có một biến có hệ số bằng 1, hệ số này không có trong các phương trình khác. Điều kiện đầu tiên không nặng nề, vì trong trường hợp vế phải âm của một phương trình nào đó, chỉ cần nhân nó với (-1) là đủ. Trong bài toán loại ưu tiên, việc tìm đường cơ sở ban đầu rất đơn giản.

Ví dụ 2.1.

Ma trận điều kiện MỘT và vectơ vế phải của các ràng buộc b trông giống như

và vectơ mục tiêu c = (1, -3, 0, 4, 2).

Một ma trận cơ sở là rõ ràng ngay lập tức: với các vectơ đơn vị của các điều kiện.

Vì vậy, việc chọn làm biến cơ bản x 1 , x 3 ,x 5 , và đưa vào hệ phương trình x 2 = x 4 = 0 (biến không cơ bản) , chúng tôi tìm thấy nó ngay lập tức x 1 = 10,x 3 = 20,x 5 = 8, vậy đường cơ sở ban đầu x 0 = (10, 0, 20, 0, 8). Ta thấy giá trị của các biến cơ bản bằng vế phải của các ràng buộc. Từ đó rõ ràng là vế phải phải dương b Tôi .

Trong tương lai chúng ta sẽ kết hợp các biến cơ bản thành một vector x B.

Như vậy, trong bài toán chính tắc dạng ưu tiên, ma trận con đẳng thức được lấy làm ma trận cơ sở ban đầu MỘT B = E và các biến cơ sở tương ứng bằng vế phải của các ràng buộc:

x B = b.

Đối với một kế hoạch cơ bản thuộc loại này, có thể xây dựng được một tiêu chí tối ưu đủ đơn giản để kiểm tra. Hãy giới thiệu số lượng

? j = < с B , MỘT j > - c j , j = 1,...,n,(2.1)

Ở đâu Với B- vectơ hệ số của hàm mục tiêu cho các biến cơ bản x B , MỘT j -j- th cột ma trận điều kiện, c j -j- hệ số thứ của hàm mục tiêu. Sự khác biệt ? jđược gọi là sai phân đơn giản hoặc ước lượng đơn giản.

Chúng ta hãy áp dụng tiêu chí này để kiểm tra tính tối ưu của phương án cơ bản x 0 = (10, 0, 20, 0, 8) từ ví dụ 2.1.

Vì về mặt này vectơ của các biến cơ bản x B =(x 1 , x 3 ,x 5 ), Cái đó Với B = (c 1 , c 3 ,c 5 ) = (1, 0, 2).

Kể từ đây,

? 1 = < с B , MỘT 1 > - c 1 = 1 1 + 0 0 + 2 0 - 1= 0,

2 = < сБ, A2 >- c2 = 1 3 + 0 1 + 2 2 - (-3) = 10,

? 3 = < с B , MỘT 3 > - c 3 = 1 0 + 0 1 + 2 0 - 0= 0,

? 4 = < с B , MỘT 4 > - c 4 = 1 (-1) + 0 5 + 2 1 - 4= -3,

? 5 = < с B , MỘT 5 > - c 5 = 1 0 + 0 0 + 2 1 - 2= 0.

Kể từ khi đánh giá ? 4 < 0, то базисный план x 0 không tối ưu. Lưu ý rằng các ước lượng đơn giản tương ứng với các biến cơ bản luôn bằng 0, do đó chỉ cần kiểm tra các ước lượng không cơ bản là đủ.

Học viện Dịch vụ Nhà nước và Thành phố Kursk

Cục An ninh thông tin và công nghệ

Tiểu luận

theo kỷ luật “Phương pháp giải quyết tối ưu”

về chủ đề "Ý tưởng của phương pháp đơn giản"

Người hoàn thành: Sinh viên năm 2

Chuyên ngành "Kinh tế"

Moskaleva O. S.

Người kiểm tra: Tiến sĩ, Phó Giáo sư Pogosyan S. L.

Vòng cung – 2012

Lời giới thiệu………………………………………..3

1. Ý tưởng của phương pháp đơn hình………………….…4

2. Thực hiện phương pháp đơn hình bằng ví dụ……………..……6

3. Triển khai dạng bảng của một phương pháp đơn giản đơn giản………….10

Kết luận…………………………………….15

Danh mục tài liệu đã sử dụng…………..…….16

Giới thiệu.

Phương pháp Simplex là một ví dụ điển hình của phép tính lặp được sử dụng để giải hầu hết các bài toán tối ưu hóa.

Trong sơ đồ tính toán của phương pháp đơn hình, một quy trình có thứ tự được thực hiện trong đó, bắt đầu từ một số điểm góc chấp nhận được ban đầu (thường là gốc tọa độ), các chuyển đổi liên tiếp được thực hiện từ điểm cực trị chấp nhận này sang điểm cực trị chấp nhận khác cho đến khi một điểm tương ứng với nghiệm tối ưu được xác định. thành lập.

Ý tưởng của phương pháp đơn giản

Hãy xem xét một phương pháp phổ quát để giải bài toán quy hoạch tuyến tính chuẩn tắc, với N biến và tôi các ràng buộc đẳng thức, được gọi là phương pháp đơn hình.

J. Danzig đề xuất chỉ thay thế một vectơ trong ma trận cơ sở khi chuyển từ điểm cực trị này sang điểm cực trị khác. Điều này có nghĩa là trong quá trình chuyển đổi như vậy, chúng ta phải loại trừ một trong các biến cơ bản - làm cho nó không cơ bản (bằng 0) và thay vào đó đưa vào một biến mới trong số các biến không cơ bản (không) - làm cho nó trở thành cơ bản (dương) ).

Sơ đồ chung của phương pháp đơn hình bao gồm các bước chính sau: bước 0. Xác định cơ sở ban đầu và điểm góc ban đầu tương ứng (đường cơ sở).

bước 1. Kiểm tra đường cơ sở hiện tại để tối ưu . Nếu tiêu chí tối ưu được thỏa mãn thì Cái đó kế hoạch là tối ưu và giải pháp đã hoàn tất. Nếu không thì chuyển sang bước 2.

bước 2. Tìm biến được đưa vào biến cơ bản. (Từ điều kiện tăng hàm mục tiêu).

bước 3. Tìm một biến bị loại trừ khỏi các biến cơ bản (Từ điều kiện bảo toàn các ràng buộc của bài toán).

bước chân 4 . Tìm tọa độ của đường cơ sở mới (điểm góc liền kề). Đi tới bước 1.

Các bước lặp lại từ 1 đến 4 tạo thành một lần lặp của phương pháp đơn hình.

Sự định nghĩa. Chúng ta sẽ nói rằng bài toán LP chính tắc có “dạng ưa thích” nếu: vế phải của phương trình; ma trận điều kiện chứa một ma trận con có kích thước đơn vị.

Thực hiện phương pháp đơn giản bằng một ví dụ

Hãy để chúng tôi chứng minh việc sử dụng phương pháp đơn giản bằng một ví dụ. Xét bài toán LP chuẩn


f(x) = x 1 + 2x 2 + 0x 3 + 0x 4 > tối đa
-x 1 + 2x 2 +x 3 = 4,
3x 1 + 2x 2 +x 4 = 12,
x j? 0, j = 1,2,3,4.

Ma trận điều kiện MỘT = (MỘT 1 , MỘT 2 , MỘT 3 , MỘT 4), ở đâu

Vectơ mục tiêu c =(c 1, c 2, c 3, c 4) = (1, 2, 0, 0); vector phần bên phải b=(b 1 , b 2) = (4, 12).

Bước 0. Tìm điểm góc bắt đầu (đường cơ sở).

Bài toán có dạng thích hợp hơn, vì vế phải của phương trình là dương và các cột của ma trận điều kiện MỘT 3, MỘT 4 tạo thành một ma trận con đơn vị. Điều này có nghĩa là ma trận cơ sở ban đầu = (MỘT 3 ,A 4); x 3 Và x 4 - biến cơ bản x 1 Và x 2 - các biến không cơ bản, c B = (c 3, c 4) = = (0, 0).

Đường cơ sở ban đầu trông giống như x 0 =(0, 0, x 3 , x 4) = (0, 0, 4, 12); f(x o) = 0.

Bước 1. Kiểm tra kế hoạch cơ bản để tối ưu.

Hãy tính ước lượng đơn giản cho các biến không cơ bản bằng công thức (5.1)

? 1 = 1 > - c 1 = 0·(-1) + 0 ·3 - 1 = -1 .

? 2 = 2 > - c 2 = 0 2 + 0 2 - 2 = -2 .

Vì các ước tính là âm nên kế hoạch x- không tối ưu. Chúng ta sẽ tìm một đường cơ sở mới (điểm góc liền kề) với giá trị lớn hơn của hàm mục tiêu.

Bước 2. Tìm biến được đưa vào cơ sở.

Hàm mục tiêu có thể được tăng lên bằng cách đưa một trong các biến không cơ bản vào các biến cơ bản (làm cho nó dương) x 1 hoặc x 2, vì cả hai ước tính ? j x2.

Bước 3.Định nghĩa của một biến xuất phát từ cơ sở.

Sau khi nhập biến vào cơ sở x 2 kế hoạch mới sẽ như thế nào

x" =(0, x 2, x 3 , x 4).

Kế hoạch này không phải là kế hoạch cơ bản, vì nó chỉ chứa một tọa độ 0, có nghĩa là cần phải tạo một trong các biến bằng 0 (loại trừ khỏi cơ sở) x 3 hoặc x 4 . Hãy thay thế tọa độ của kế hoạch x" =(0, x 2, x 3 ,x 4) trong các ràng buộc của vấn đề. Chúng tôi nhận được

2x 2 +x 3 = 4,

2x 2 + x 4 = 12.

Hãy để chúng tôi thể hiện các biến cơ bản từ đây x 3 Và x 4 thông qua biến x 2 , được đưa vào cơ sở.


x 3 = 4 - 2x 2,
x 4 = 12 - 2x 2 .

Vì vậy các biến x 3 Và x 4 phải không âm, ta thu được hệ bất đẳng thức


4 - 2x 2 ? 0,
12 - 2x 2 ? 0.

Giá trị càng cao x 2 , hàm mục tiêu càng tăng. Hãy tìm giá trị lớn nhất của biến cơ sở mới không vi phạm ràng buộc của bài toán, tức là thỏa mãn điều kiện (2.8), (2.9).

Hãy viết lại các bất đẳng thức cuối cùng dưới dạng

2x 2 ? 4,

2x 2 ? 12,

giá trị tối đa đến từ đâu? x 2 = min ( 4/2, 12/2 ) = 2. Thay giá trị này vào các biểu thức (2.6), (2.7) cho x 3 Và x 4 , chúng tôi nhận được x 3 = 0. Vì vậy x 3 xuất phát từ cơ sở .

Bước 4. Xác định tọa độ của đường cơ sở mới.

Đường cơ sở mới (điểm góc liền kề) là:

x" = (0, x 2, 0, x 4)

Cơ sở của điểm này bao gồm các cột MỘT 2 và MỘT 4 , vậy =( MỘT 2, MỘT 4). Cơ sở này không đơn nhất, vì vectơ MỘT 2 = (2,2), và do đó bài toán (2.2)-(2.5) không có dạng ưu tiên đối với cơ sở mới. Ta biến đổi điều kiện của bài toán (2.3), (2.4) sao cho nó có dạng ưu tiên đối với các biến cơ bản mới x 2, x 4, nghĩa là, sao cho biến x 2 được đưa vào phương trình thứ nhất với hệ số bằng 1 và không có trong phương trình thứ hai. Hãy viết lại các phương trình của bài toán

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

3x 1 +2 x 2 + x 4 = 12. (P 2)

Hãy chia phương trình đầu tiên cho hệ số tại x 2 . Chúng ta nhận được một phương trình mới = p 1/2 tương đương với bản gốc

1/2 x 1 + x 2 + 1/2 x 3 = 2. ()

Chúng tôi sử dụng phương trình này, mà chúng tôi gọi là giải quyết, để loại bỏ biến x 2 từ phương trình thứ hai. Để làm điều này, bạn cần nhân phương trình với 2 và trừ từ P 2 . Chúng tôi nhận được = p 2 - 2= p 2 -P 1:

4 x 1 - x 3 + x 4 = 8. ()

Kết quả là chúng ta thu được một cách biểu diễn “ưu tiên” mới của bài toán ban đầu đối với các biến cơ bản mới. x 2 , x 4:

f(x) = x 1 + 2 x 2 + 0 x 3 + 0 x 4 ? tối đa

1/2 x 1 + x 2 + 1/2 x 3 = 2 ()

4 x 1 - x 3 + x 4 = 8 ()

x j? 0, j = 1,2,3,4

x" = (0, 2, 0, 8); f(x 1)=4.

Điều này hoàn thành lần lặp đầu tiên của phương pháp đơn giản. Tiếp theo, quá trình giải quyết vấn đề tiếp tục từ bước 1, bao gồm việc kiểm tra phương án tìm được ở mức tối ưu. Giải pháp kết thúc khi tất cả các ước tính đơn giản của kế hoạch cơ bản hiện tại hóa ra không âm.

Chúng tôi sẽ không thực hiện lần lặp thứ hai theo sơ đồ của lần lặp đầu tiên, vì sẽ thuận tiện hơn khi thực hiện tất cả các phép tính của phương pháp đơn hình ở dạng bảng.

Triển khai dạng bảng của một phương pháp đơn giản đơn giản

Chúng ta sẽ chứng minh việc triển khai dạng bảng bằng cách sử dụng cùng một ví dụ (2.2)-(2.5).

Bước 0. Giải pháp bắt đầu bằng cách xây dựng một bảng đơn giản ban đầu. Đầu tiên, phía bên phải của bảng được điền từ cột thứ ba. Hai dòng trên cùng chứa tên của các biến nhiệm vụ ( x 1, ...,x 4) và các hệ số của hàm mục tiêu cho các biến này. Dưới đây là các hệ số của các phương trình - phần tử của ma trận điều kiện MỘT, do đó dưới biến x 1 xác định vị trí cột MỘT 1, dưới biến x 2 - cột MỘT 2 vân vân. Vế phải của các ràng buộc (số) được nhập vào cột bên phải tôi > 0).

Sau đó, chúng ta tìm các cột của ma trận điều kiện tạo thành cơ sở đơn vị - trong ví dụ của chúng ta đây là MỘT 3 và MỘT 4 - và các biến cơ sở tương ứng của chúng x 3, x 4 viết vào cột thứ hai. Cuối cùng, ở cột đầu tiên chúng ta viết các hệ số của hàm mục tiêu cho các biến cơ bản.

Bảng 1- Bảng đơn giản ban đầu

	Biến cơ bản					Giá trị biến cơ bản ( xB =b)
		*x 1*	*x 2*	*x 3*	*x 4*
	*x 3*	một 11 =-1
	*x 4*
Dòng đánh giá ? j	? 1 = -1	? 2 = -2

x o = (0, 0, x 3 , x 4) = (0, 0, 4, 12).

Bước 1.Để kiểm tra kế hoạch xồ để tối ưu, chúng tôi tính toán ước tính đơn giản cho các biến không cơ bản x 1 Và x 2 theo công thức

? j = B, A j > - c j .

? 1 = B, MỘT 1 > - c 1 = 0·(-1) + 0 ·3 - 1 = -1 .

Với cách triển khai dạng bảng để tính điểm ? 1 chúng ta cần tìm tổng tích của các phần tử ở cột đầu tiên ( c B) vào các phần tử cột tương ứng MỘT 1 đối với một biến không cơ bản x 1 . Điểm được tính tương tự ? 2 , là tích vô hướng của cột đầu tiên ( c B) trên mỗi cột tại biến x 2.

? 2 = 2 > - c 2 = 0 2 + 0 2 - 2 = -2 .

f(x)= c B, x B >,

nhân vô hướng các cột đầu tiên và cuối cùng của bảng.

Vì trong số các ước tính ? j Có tiêu cực , sau đó kế hoạch x o không tối ưu và cần phải tìm ra một phương án cơ bản mới bằng cách thay thế một trong các biến cơ bản bằng một biến mới trong số các biến không cơ bản.

Bước 2. Vì cả hai ước tính ? 1 Và ? 2 thì bất kỳ biến nào cũng có thể được đưa vào cơ sở x 1, x 2 . Hãy để chúng tôi đưa vào cơ sở biến có ước tính âm tuyệt đối lớn nhất, đó là x 2 .

Cột của bảng đơn chứa biến được nhập vào cơ sở được gọi là cột dẫn đầu.

Trong ví dụ, cột đầu tiên sẽ ở x2 .

Bước 3. Nếu tất cả các phần tử ở cột đầu đều âm thì không có giải pháp nào cho vấn đề và giá trị tối đa f(x) ???. Trong ví dụ, tất cả các phần tử của cột đầu đều dương, do đó, chúng ta có thể tìm thấy giá trị lớn nhất x 2 , tại đó một trong các biến cơ bản cũ sẽ bằng 0. Hãy nhớ rằng giá trị tối đa x 2 = phút(4/2, 12/2)=2.

Tỷ lệ nhỏ nhất nằm ở hàng có biến cơ sở x3. Vì vậy biến x 3 loại trừ khỏi các biến cơ bản ( x 3 = 0).

Dòng chứa biến bị loại khỏi cơ sở được gọi là dòng dẫn đầu.

Trong ví dụ, dòng dẫn đầu sẽ là dòng đầu tiên.

Phần tử nằm ở giao điểm của hàng đầu và cột đầu được gọi là phần tử đầu.

Trong trường hợp của chúng tôi, phần tử hàng đầu Một 12 = 2.

Bàn 2- Bảng đơn giản ban đầu với hàng và cột đầu tiên


	Những thay đổi cơ bản.					Giá trị biến cơ bản	phương trình
			*x 2*
*c 3 = 0*	*x 3*	-1	2	1	0	4
			2
Dòng đánh giá ? j	? 1 = -1	? 2 = -2

Bước 4. Để có được một kế hoạch cơ bản mới, chúng ta quy bài toán về một dạng ưu tiên mới đối với các biến cơ bản mới.

Để làm điều này, hãy xây dựng một bảng đơn giản mới, trong cột thứ hai thay vì biến bị loại trừ x 3 hãy viết một biến cơ bản mới x 2, và trong cột đầu tiên ( với B) thay vì từ 3 Hãy viết hệ số của hàm mục tiêu tại x 2: c 2 =2. Trong bảng đơn giản mới, cột tại x 2 phải trở thành một (phần tử đứng đầu phải bằng 1 và tất cả các phần tử khác phải bằng 0). Điều này đạt được bằng các phép biến đổi hàng trong bảng sau.

Một. Chúng ta chia tất cả các phần tử của hàng đầu cho phần tử đầu và viết chúng vào cùng một hàng của bảng đơn giản mới.

Chuỗi kết quả p 1" Hãy gọi nó là sự cho phép.

b.Đối với dòng thứ hai còn lại, chúng ta thêm dòng phân giải, nhân với một số sao cho phần tử ở cột đầu bằng 0.

p 2 " = p 2 + (- 2) p 1 " = p 2 - p 1.

c. Hãy điền vào dòng cuối cùng bằng cách tính toán các ước tính ? j " = - - c j, Ở đâu c B", A j " - các cột tương ứng của bảng đơn giản mới và giá trị của hàm mục tiêu f(x)= .

Chúng ta thu được bảng đơn thứ hai với cơ sở mới.

bàn số 3- Kết quả của lần lặp đầu tiên


	Những thay đổi cơ bản.					Giá trị biến cơ bản	phương trình

		-*1/2*
	*x 4*	4	0	-1	1	8	p 2 " =p 2 - p 1
ước tính ? j"	-2

Kế hoạch cơ bản mới x " = (0, x 2, 0, x 4) = (0, 2, 0, 8 ). Kể từ khi đánh giá ? 1 = -2 thì lập kế hoạch x " không tối ưu. Để chuyển sang một sơ đồ cơ bản mới (của điểm góc lân cận), chúng ta sẽ thực hiện một phép lặp khác của phương pháp đơn hình.

Bởi vì? 1 sau đó một biến được đưa vào cơ sở x 1. Cột đầu tiên chứa x 1 - dẫn đầu.

Chúng tôi chọn cột đầu tiên và hàng đầu tiên và tại giao điểm của chúng, chúng tôi tìm thấy phần tử dẫn đầu (= 4).

Chúng tôi xây dựng một bảng đơn giản (thứ ba) mới, thay thế biến cơ bản trong đó x 4 TRÊN x 1 , đồng thời biến đổi lại các hàng của bảng sao cho phần tử đứng đầu bằng 1 và các phần tử còn lại của cột dẫn đầu trở thành 0. Để thực hiện việc này, hãy chia dòng đầu tiên (thứ hai) cho 4 và thêm dòng thứ hai thu được vào dòng đầu tiên, chia cho 2. Chúng tôi tính toán dòng cuối cùng bằng cách sử dụng các công thức ước tính đơn giản ? j"" = "", Aj""> - c j, Ở đâu c B"", Aj"" - các cột tương ứng của bảng đơn giản mới. Giá trị của hàm mục tiêu trên đường cơ sở mới được tìm thấy bằng công thức f(x"")= "", x B"" >.

Bảng 4- Kết quả của lần lặp thứ hai


	Nền tảng thay đổi.		Giá trị biến cơ bản	phương trình

				trang 1 "" = p 1 "+p 2 ""/2
				p 2 "" = p 2 "/4
ước tính ? j ""		f(x"")= 8

Kế hoạch cơ bản mới x "" = (x 1 , x 2 , 0, 0) = (2, 3, 0, 0 ). Vì tất cả các ước lượng đều không âm nên kế hoạch x ""- phương án tối ưu.

Như vậy, x* = (2, 3, 0, 0 ), f(x*) = 8.

PHẦN KẾT LUẬN

Các phương pháp được xem xét để giải các bài toán quy hoạch tuyến tính được sử dụng rộng rãi trong thực tế. Tuy nhiên, cần lưu ý rằng

một mô hình toán học luôn kém hơn một hệ thống kinh tế thực. Nó chỉ mô tả hệ thống này một cách gần đúng, làm nổi bật một số thuộc tính và bỏ qua những thuộc tính khác. Để bù đắp cho thiếu sót này trong kinh tế toán học, một số loại mô hình đang được phát triển, mỗi loại được thiết kế để phản ánh một khía cạnh cụ thể của thực tế kinh tế để khi giải một bài toán kinh tế cụ thể, có thể chọn một mô hình phù hợp nhất với nó. .

DANH MỤC TÀI LIỆU THAM KHẢO ĐƯỢC SỬ DỤNG

1. Ashmanov SA Lập trình tuyến tính. - M.: Nauka, 1981.