Phương pháp giải bài toán quy hoạch lồi

Tập lồi và tính chất của tập lồi

1.1.1 Tập lồi Định nghĩa Tập M ℝ n đ-ợc gọi là tập lồi nếu với bất kì X, Y M và

Cho hệ số hữu hạn điểm X 1 , X 2 ,…,X n khi đó với

Ta nói X là tổ hợp lồi của hệ điểm đã cho

X 1 X 2 đ-ợc gọi là đoạn thẳng nối 2 điểm X 1 ,X 2

Tập hợp M được coi là tập lồi nếu và chỉ nếu đoạn thẳng nối giữa hai điểm bất kỳ trong tập hợp hoàn toàn nằm trong tập hợp đó.

Thì ta nói X 1 X 2 là đoạn thẳng nối 2 điểm X 1 ,X 2

Tập hợp M ℝ n đ-ợc gọi là đa tạp tuyến tính nếu với bất kì X, Y M,

Cho tập hợp lồi M ℝ n , điểm X M đ-ợc gọi là điểm cực biên của M nếu

X không thể biểu diễn thành tổ hợp lồi thực sự của 2 điểm khác nhau thuộc M Nghĩa là không thể tồn tại X 1 và X 2 thuộc M sao cho

1.1.2 Tính chất của tập lồi

Tính chất 1 Giao của các tập lồi là tập lồi

Tính chất 2 Cho D 1 và D 2 là các tập lồi Khi đó hiệu D = D 1 - D 2 và tổng

D = D 1 + D 2 là các tập hợp lồi (hiệu và tổng nghĩa là hiệu và tổng các vecto t-ơng ứng thuộc tập hợp)

Cho tập lồi M, tập đóng nhỏ nhất chứa M đ-ợc gọi là bao đóng của M

Tính chất 3 Bao đóng của tập lồi là tập lồi

Cho tập hợp M ℝ n , tập hợp tất cả các điểm là tổ hợp lồi của các điểm thuộc M đ-ợc gọi là bao lồi của M

Tính chất 4 co(M) là tổ hợp lồi bé nhất chứa M và là giao của tất cả các tập lồi chứa M

Tính chất 5 Tổ hợp lồi của các tập lồi là lồi

Tập M được coi là lồi nếu và chỉ nếu mọi tổ hợp lồi của hữu hạn điểm thuộc M cũng nằm trong M Định nghĩa siêu phẳng trong không gian ℝ^n là tập hợp các điểm X thỏa mãn điều kiện α, với C thuộc ℝ^n và α thuộc ℝ.

Tính chất 7 Cho M và Q là các tập hợp lồi thuộc ℝ n , MQ=, khi đó tồn tại siêu phẳng  C, X  = tách M và Q, nghĩa là tồn tại C  ℝ n và ℝ n sao cho:

  i   , m } là tập lồi Trong tr-ờng hợp này tập M đ-ợc gọi là tập lồi đa diện thuộc không gian ℝ n

 n  j i j ij x b a thì ta nói X thõa mãn chặt điều kiện thứ i của M

Tính chất 9 (Định lí biểu diễn tập lồi)

Tập lồi đa diện M có hữu hạn điểm cực biên X 1 , X 2 ,…, X k và mọi X  M đ-ợc biÓu diÔn i k i i i k i i X Z

Trong đó Z i , (i=1, 2,…,s) là các ph-ơng vô tận của M,

 , , Định nghĩa Cho tập lồi đa diện M, điểm X (x j )M đ-ợc gọi là bị chặn nếu tồn tại số thực L sao cho x j L, j = 1, 2, , n

Tập lồi đa diện M đ-ợc gọi là bị chặn nếu X M đều bị chặn

Tập lồi đa diện khác rỗng và bị chặn đ-ợc gọi là đa diện lồi

Nh- vậy ta có hệ quả sau:

Tính chất 10, hay còn gọi là định lý biểu diễn đa diện lồi, khẳng định rằng một đa diện lồi có hữu hạn điểm cực biên X1, X2, , Xk Mọi điểm thuộc đa diện lồi và tổ hợp lồi của các điểm cực biên đều có thể được biểu diễn, tức là mọi điểm X thuộc tập M đều nằm trong đa diện lồi này.

1.2 Hàm lồi và các tính chất của hàm lồi

1.2.1 Hàm lồi Định nghĩa Cho hàm lồi f xác định trên tập lồi M Hàm f đ-ợc gọi là hàm lồi nếu với X,YM và [ 0,1] ta có

( X Y f X f Y f       Nếu có bất đẳng thức ng-ợc lại f(X ()Y)f(X)()f(Y) thì f là hàm lõm

Chú ý rằng: nếu f(X) là hàm lồi thì hàm g(X)=- f(X) là hàm lõm

Ví dụ: + Hàm y= ax 2 + bx + c là hàm lồi

+ Hàm y=sin x, x,là hàm lồi

1.2.2 Tính chất của hàm lồi

Tính chất 1 Hàm tuyến tính là hàm vừa lồi vừa lõm

Tính chất 2 (Bất đẳng thức Jensen) Hàm f xác định trên tập lồi M, là hàm lồi khi và chỉ khi f X f X X i M k i i i k i i i   

Giả sử có bất đẳng thức (*) Khi đó với k = 2, theo định nghĩa thì f là hàm lồi

Ng-ợc lại, giả sử f(x) là hàm lồi trên M, ta chứng minh bất đẳng thức (*) XÐt:

Rõ ràng do M lồi nên X M Để chứng minh (*), ta qui nạp theo k

Với k=2, bất đẳng thức đúng

Giả sử bất đẳng thức đúng với k-1, ta chứng minh đứng với k

Không mất tính tổng quát, giả sử 00 mà x ij  ?

NÕu cã chuyÓn sang b-íc 6

Nếu không chuyển sang b-ớc 3

B-ớc 5 Xây dựng ph-ơng án cực biên X 1

Gán X 0 : = X 1 rồi trở lại b-ớc 1

B-ớc 6 Dừng lại, trả lời có hay không ph-ơng án tối -u.

Bài toán qui hoạch lồi

Trong đó D là tập lồi thuộc ℝ n và f 1 (x), f 2 (x),…, f k (x): ℝ n ℝ là các hàm lồi

Khi đó bài toán (1.7), (1.8), (1.9) đ-ợc gọi là bài toán qui hoạch lồi

Điểm x thuộc tập D và thỏa mãn điều kiện (1.9) được gọi là phương án hoặc điểm chấp nhận của bài toán Tập hợp các phương án được ký hiệu là M, và rõ ràng M là một tập lồi.

 Ph-ơng án x * thỏa mãn: f(x * ) = min f(x), xM đ-ợc gọi là ph-ơng án tối -u (hay lời giải, hay nghiệm) của bài toán

Nếu hàm f(x) là hàm lõm và tập phương án M lồi, bài toán (1.7), (1.8), (1.9) được gọi là bài toán quy hoạch lõm Bài toán này thỏa mãn điều kiện chính quy khi tồn tại ít nhất một điểm x₀ thuộc D sao cho f₁(x₀) < 0, …, fₖ(x₀) < 0.

Lúc này ta cũng nói tập ph-ơng án M thỏa mãn điều kiện chính qui

1.4.2 Tính chất của bài toán qui hoạch lồi

Tính chất 1 Bài toán qui hoạch lồi có cực tiểu địa ph-ơng trùng với cực tiểu tuyệt đối

Giả sử x₀ thuộc M là điểm cực tiểu địa phương của hàm f trên M, thì tồn tại một lân cận ω x₀ sao cho f(x₀) ≤ f(x) với mọi x thuộc M ∩ ω x₀ Chọn bất kỳ x thuộc M, ta xét y = λx + (1 - λ)x₀ với 0 ≤ λ ≤ 1 Khi λ đủ nhỏ, y sẽ nằm trong lân cận của x₀, đồng thời do M lồi nên y cũng thuộc M.

Từ đó suy ra y M x  Do vậy f(x  )  f(y) Nh-ng f là hàm lồi nên:

) (x  f  f(y)f(x)()f(x  ),xM. Suy ra f(x  )  f(x),xM x 0 là cực tiểu tuyệt đối.

Tính chất 2 Nếu hàm lồi f đạt cực đại tại điểm trong x 0 của tập lồi M thì f không đổi trên tập M

Chứng minh Giả sử x 0 là điểm trong của M mà f đạt cực đại, tức là: f(x), f(y)  f(x  ),x,yM (*) Vì x 0 là điểm trong nên với mỗi x M thì tồn tại y M mà: x 0 = x()y,.

Vì 01, nên f(x  ) f(x),xM So sánh với (*) ta đ-ợc

Tính chất 3 Cho hàm lồi f, khả vi xác định trên tập hợp lồi, M ℝ n , điều kiện cần và đủ để hàm f đạt cực tiểu toàn cục tại x * M là

Chứng minh Giả sử có f(x * ),xx * ,xM.

Khi đó theo tính chất 6 hàm lồi ta có:

Rõ ràng tại x=x * , ta cũng có:

Do vậy nếu x * thỏa mãn:

 thì điều đó nói lên rằng

 ( ) ( * ), hay f(x * ) f(y),yM, nghĩa là x * là ph-ơng án tối -u

Ng-ợc lại, cho x * tối -u, ta cần chứng minh (1.10) (xem tài liệu tham khảo).

Tính chất 4 Cho hàm lồi f xác định trên tập hợp lồi M ℝ n , điều kiện cần và đủ để hàm f đạt cực tiểu toàn cục tại điểm trong x * M là f(x * )

 Cho bài toán qui hoạch lồi (1.7)-(1.9) Kí hiệu y =(y i )ℝ k , y 

Hàm L(x,y) nh- vậy gọi là hàm Lagrange của bài toán qui hoạch lồi

 Điểm (x * , y * ), với x * M và y * =(y  * ,y  * , ,y k * ) đ-ợc gọi là điểm yên ngựa của hàm Lagrange nếu nó thỏa mãn

Tính chất 5 (Định lí điểm yên ngựa)

Hàm lồi f đạt cực tiểu tại điểm x * M khi và chỉ khi tồn tại điểm y * ℝ k ,

 y * sao cho (x * , y * ) điểm yên ngựa của hàm Lagrange L(x, y)

Nhận xét: Ng-ời ta đã chứng minh rằng nếu bài toán qui hoạch lồi thỏa mãn điều kiện chính qui thì luôn luôn tồn tại điểm yên ngựa

Tính chất 6 (Định lí Frarkas-Minlkowski mở rộng) Cho hàm f(x), f i (x) (i=1, 2,…, k) là những hàm lồi, xác định trên tập lồi D ℝ n , hệ

D x k i x f i ( ) , , , , có nghiệm, đồng thời hệ

, , k , i x f i vô nghiệm trong M, thì tồn tại những số thực  i , i=1, 2,…, k sao cho D x

Thuật toán giải bài toán qui hoạch lồi

Thuật toán Frank-Wolfe là một phương pháp quan trọng để giải quyết bài toán quy hoạch lồi, với nhiều phương pháp chính xác đã được phát triển Bài viết này sẽ trình bày chi tiết về phương pháp Frank-Wolfe, bắt đầu từ những giả thiết cơ bản.

1 D là tập lồi đa diện, các hàm f i (x) là tuyến tính, điều đó cho thấy rằng M là tập lồi đa diện

2 Hàm f(x) lồi, khả vi liên tục trên M

Phương pháp này bắt đầu từ một phương án x0 bất kỳ và xây dựng một dãy các phương án x0, x1,…, xk, trong đó giá trị của hàm f(x) giảm dần đến một giá trị giới hạn Điều kiện cần thiết là đạo hàm của f tại điểm x và hướng s phải bị chặn dưới trên tập M cho mọi x thuộc M và mọi hướng s chấp nhận được.

Dựa trên tính chất 3, giả sử đã biết ph-ơng án x k Khi đó nếu

Ng-ợc lại, nếu có x mà f(x k ),xx k , ta đi xây dựng ph-ơng án x k+1 theo một h-ớng tụt xác định để có f(x k+1 ) f(x k )

Từ đó ta có thuật toán:

B-ớc 0 chọn x 0 bất kỳ thuộc M

Giả sử đã biết phương án x k, chúng ta giải bài toán quy hoạch tuyến tính với mục tiêu tối thiểu hóa ∇f(x k) tại điểm x k, trong đó x thuộc tập M Bài toán tương đương sẽ là tối thiểu hóa f(x k) với x cũng thuộc tập M Dựa trên các giả thuyết đã nêu, bài toán này có phương án tối ưu x ~k.

Lúc này có 2 khả năng xảy ra: a) Nếu f(x),x~ k x k  tức là

Nếu ∇f(x_k), x~_k - x_k ≥ 0 với mọi x ∈ M, thì phương án tối ưu đã được tìm thấy và thuật toán kết thúc Ngược lại, nếu ∇f(x_k), x~_k - x_k < 0, điều này chứng tỏ rằng f(x) giảm theo hướng s = x~_k - x_k, tức là f(x) giảm trên đoạn [x_k, x~_k] Chúng ta sẽ tiếp tục giải bài toán cực tiểu của hàm một biến.

Chú ý rằng, g()là hàm lồi xác định trên đoạn [0, 1] Do vậy ta chỉ cần giải ph-ơng trình

Nếu nghiệm ph-ơng trình (*) không thuộc [0, 1] thì ta xét min  g(),g(). Đặt

( ) (x k f x k f    Gán x k : = x k+1 trở lại b-ớc k Định lí Với các giả thiết đã nêu và M compact, khi đó ta có a) f(x k ) giảm dần đến minf(x),xM. b)  f(x k )  f(x k ),x k ~x k

Gọi I là tập hợp các đỉnh của M có mặt trong dãy \( \{ x_k \} \) Dãy \( x_0, x_1, \ldots, x_k, \ldots \) nằm trong bao lồi của \( \{ x_0 \} \cup I \) Tập hợp \( \{ x_0 \} \cup I \) gồm hữu hạn điểm, do đó nó là tập compact.

Do vậy dãy   x k có một điểm tụ x * và tốt dần, nghĩa là

) ( ) (x   f x    f x k  f , ngoài ra f(x) là hàm liên tục nên

Hay đổi dấu hai vế ta có:

  Định lí đ-ợc chứng minh 

Giải bài toán qui hoạch lồi sau bằng thuật toán Frank-Wolfe min f  x   x  y | z ( x , y ) M  với điều kiện:

Lấy ph-ơng án xuất phát (x 0 , y 0 ) = (4, 1)

Bài toán đã cho là bài toán qui hoạch lồi Ta có f(z) (x;)

Chọn z 0 =(4, 1), khi đó f(z  )(;) Suy ra f(z  ),z xy

Giải bài toán qui hoạch tuyến tính min f ( z  ), z | z ( x , y ) M 

Tức là bài toán min f xy|(x,y)M  với điều kiện:

Dạng chính tắc của bài toán min f xy|(x,y,t,k,l)M  với điều kiện:

Chọn cơ sở A 3 A 4 A 5  ph-ơng án cực biên xuất phát là: z = (0, 0, 2, 2, 5)

Ta có bảng đơn hình:

Tại bảng III ta thấy  j , vậy ph-ơng án tối -u là: z * = (1, 4, 9, 0, 0) suy ra ~z  (,)

 Xây dựng ph-ơng án mới

Giải bài toán một biến  min f(z  (~z  z  )| ; tức là bài toán min           |      ;   ,

Ta có f(z  )(;-2).Ta lại đi giải bài toán qui hoạch tuyến tính min xy |(x,y)M  với điều kiện:

Dạng chính tắc min xy |(x,y,t,k,l)M  với điều kiện:

Chọn cơ sở A 3 A 4 A 5 , ph-ơng án cực biên xuất phát là: z 0 =( 0, 0, 2, 2, 5)

Ta có bảng đơn hình

Tại bảng III ta thấy  j , vậy ph-ơng án tối -u là: z * = (4, 1, 0, 9, 0) suy ra ~z  (,)

 là ph-ơng án tối -u cần tìm

Ch-ơng 2 giải bài toán qui hoạch lồi bằng ngôn ngữ

Ngôn ngữ Visual Basic

2.1.1 Giới thiệu vài nét về ngôn ngữ Visual Basic

Visual Basic is a comprehensive programming language that operates on an event-driven model, while also sharing similarities with structured programming languages.

Nó cũng hỗ trợ các cấu trúc:

CÊu tróc IF…THEN…ELSE

Cấu trúc rẽ nhánh (Select Case)

Hàm (Function) và ch-ơng trình con (Subroutines)

Visual Basic đã giới thiệu một phương pháp lập trình mới, giúp tăng tốc độ phát triển ứng dụng Mỗi phiên bản mới của Visual Basic đều mang đến những tính năng cải tiến Ví dụ, Visual Basic 2.0 cung cấp cách đơn giản để quản lý các cơ sở dữ liệu mạnh mẽ, trong khi Visual Basic 6.0 bổ sung hỗ trợ phát triển 32 bit và bắt đầu chuyển mình thành một ngôn ngữ lập trình hướng đối tượng hoàn chỉnh.

Visual Basic cung cấp nhiều công cụ hữu ích như hộp văn bản, nút lệnh, nút tùy chọn, hộp kiểm tra, hộp liệt kê, thanh cuộn và hộp thư mục Người dùng có thể sử dụng các khung kẻ ô để quản lý dữ liệu theo dạng bảng, kết nối với các ứng dụng Windows khác và truy cập cơ sở dữ liệu thông qua công nghệ OLE của Microsoft.

Visual Basic hỗ trợ lập trình viên bằng cách hiển thị tất cả các thuộc tính của đối tượng khi cần sử dụng, điều này thể hiện sức mạnh của các ngôn ngữ lập trình hiện đại.

Các b-ớc thiết kế một ứng dụng Visual Basic:

Xây dựng các cửa sổ mà ng-ời dùng có thể nhìn thấy

Qui định những sự kiện mà các điều khiển trên cửa sổ sẽ nhận ra

Viết các thủ tục sự kiện cho các sự kiện đó (các thủ tục con khiến cho các thủ tục đó làm việc)

Các nội dung diễn ra khi ứng dụng đang chạy

Visual Basic theo dõi các cửa sổ và các điều khiển bên trong, ghi nhận mọi sự kiện mà từng điều khiển có thể tiếp nhận, bao gồm các chuyển động chuột và các thao tác khác.

Khi Visual Basic phát hiện một sự kiện, nó sẽ kiểm tra xem người dùng đã viết thủ tục cho sự kiện đó hay chưa Nếu có, Visual Basic sẽ thực thi thủ tục và quay lại bước đầu tiên Quá trình này tiếp tục lặp lại cho đến khi ứng dụng kết thúc.

Sau khi tìm hiểu về hoạt động lập trình theo kiểu điều khiển bởi sự kiện và các hỗ trợ từ Visual Basic, chúng ta nhận thấy đây là một công cụ lập trình dễ sử dụng với nhiều ứng dụng phong phú.

2.1.2 Một số hàm, thủ tục và cấu trúc điều khiển trong Visual Basic 2.1.2.1 Hàm và thủ tục a Thủ tục không trả về giá trị

[Private | Public | Static] Sub (tham số)

End sub b Hàm luôn trả về giá trị

[Private | Public | Static] Function (tham số) [As ]

Trong tr-ờng hợp không khai báo As , mặc định, Visual Basic hiểu là kiểu variant c Thủ tục thuộc tính

Có thể trả về và gán giá trị, hay tham chiếu đến đối t-ợng

Thoát khỏi thủ tục / hàm

Exit sub dùng để thoát khỏi thủ tục, Exit Function dung để thoát khỏi hàm

2.1.2.2 CÊu tróc ®iÒu khiÓn a Cấu trúc chọn

Một dòng lệnh: If Then

Nhiều dòng lệnh: If Then

Câu lệnh "End If" trong Visual Basic được sử dụng để kết thúc một cấu trúc điều kiện, trong đó điều kiện là một biểu thức có giá trị số Visual Basic sẽ đánh giá điều kiện này thành True hoặc False; nếu kết quả là True, chương trình sẽ thực hiện các lệnh sau từ khóa Then.

Các biểu thức so sánh

Else If Then

Câu lệnh Select Case đ-ợc dùng để tránh tr-ờng hợp có quá nhiều Else If đ-ợc dùng

Select Case

Case

Khối lệnh 1 Case

Mỗi danh sách biểu thức bao gồm một hoặc nhiều giá trị, được phân tách bằng dấu phẩy Mỗi khối lệnh có thể chứa từ 0 đến nhiều dòng lệnh, với điều kiện rằng nếu có nhiều Case, thì Case đầu tiên sẽ được thực hiện Case else không bắt buộc phải có, nhưng thường được sử dụng để xử lý các trường hợp còn lại của các Case trước đó.

Thực hiện một khối lệnh với số lần lặp không xác định trước, sử dụng một biểu thức điều kiện để so sánh và quyết định xem vòng lặp có tiếp tục hay không Điều kiện này cần được quy về giá trị True hoặc False.

Kiểu 1: Do While

Kiểu 2: Vòng lặp luôn có ít nhất một lần thi hành khối lệnh

Kiểu 3: Lặp trong khi điều kiện là False

Kiểu 4: Lặp trong khi điều kiện là False và có ít nhất một lần thi hành khối lệnh

Biết tr-ớc số lần lặp, ta dùng biến tăng dần hoặc giảm dần trong vòng lặp For = To [Step ]

Biến đếm, điểm đầu, điểm cuối, b-ớc nhảy là những giá trị số

Bước nhảy có thể là dương hoặc âm Nếu bước nhảy dương, điểm đầu phải nhỏ hơn hoặc bằng điểm cuối; ngược lại, nếu bước nhảy âm, điểm đầu phải lớn hơn hoặc bằng điểm cuối.

Vòng lặp For…Next tương tự như vòng lặp truyền thống, nhưng nó lặp lại khối lệnh dựa trên số lượng phần tử trong một tập hợp hoặc mảng, thay vì theo số lần lặp cố định Loại vòng lặp này rất hữu ích khi bạn không biết chính xác số lượng phần tử trong tập hợp.

For Each In

Vòng lặp Do…While tương tự như các vòng lặp khác, nhưng không thể thoát ra bằng lệnh Exit Thay vào đó, vòng lặp này chỉ kết thúc khi biểu thức điều kiện trở thành sai.

5 Câu lệnh GoTo Đ-ợc dùng cho bẫy lỗi

Khi có lỗi, ch-ơng trình sẽ nhảy đến nhãn ErrorHandler và thi hành ở lệnh đó.

Sử dụng ngôn ngữ VB để viết ch-ơng trình giải bài toán qui hoạch lồi

Để viết một chương trình giải bài toán quy hoạch lồi bằng ngôn ngữ Visual Basic, trước tiên bạn cần cài đặt Visual Basic 6.0 trên máy tính Bạn có thể tham khảo các giáo trình về Visual Basic hoặc tìm kiếm thông tin trên internet để thực hiện việc cài đặt Sau khi hoàn tất, hãy nhấn vào Start, sau đó chọn All Programs và tìm đến MiscoSoft Visual Basic.

6.0 -> MicroSoft Visual Basic 6.0 để khởi động ch-ơng trình Visual Basic 6.0.( h×nh 1)

Hình 1 Khởi động ch-ơng trình Visual Basic 6.0

Bây giờ ta có thể làm việc trực tiếp thông qua giao diện chính và các công cụ đã đ-ợc tích hợp sẵn của Visual Basic 6.0

The interface of Visual Basic, known as the Integrated Development Environment (IDE), is where VB programs are created The IDE serves as a comprehensive platform for developing applications using Visual Basic.

Hình 2 Giao diện làm việc của Visual Basic

IDE là môi trường phát triển tích hợp, bao gồm menu, thanh công cụ và cửa sổ, giúp lập trình viên tạo ra chương trình một cách hiệu quả Mỗi phần trong IDE cung cấp các tính năng khác nhau, ảnh hưởng đến quá trình lập trình Thanh menu cho phép quản lý và tương tác với toàn bộ ứng dụng, trong khi thanh công cụ cung cấp truy cập nhanh đến các chức năng của thanh menu thông qua các nút tiện lợi.

Tác giả đã phát triển một chương trình giải bài toán sử dụng thuật toán Frank-Wolfe bằng ngôn ngữ lập trình Visual Basic Chương trình bao gồm bốn form chính: frmAbout, frmQuiHoachLoi, mdiMain, và frmAboutFrankWolfe.

Trong đó frmQuiHoachLoi là form hiển thị giao diện chính của ch-ơng trình (hình 3)

Hình 3 Giao diện chính của ch-ơng trình frmAbout là form giới thiệu về ch-ơng trình (hình 4)

Hình 4 Giới thiệu về ch-ơng trình mdiMain (hình 5) là một form chứa hai menu con: menu “bài toán qui hoạch lồi”

Hình 5 mdiMain và menu “hệ thống” bao gồm form giới thiệu chương trình (hình 4) cùng với nút điều khiển để tắt và thoát khỏi chương trình giải bài toán quy hoạch lồi.

Và cuối cùng là frmAboutFrankWolfe là form giới thiệu Thuật toán Frank- Wolfe (h×nh 6)

Hình 6 Giới thiệu Thuật toán Frank-Wolfe

Do giới hạn về số lượng trang, tác giả không thể đưa toàn bộ đoạn code của chương trình vào luận văn Dưới đây là một đoạn code minh họa cho thuật toán Frank-Wolfe nhằm giải quyết bài toán quy hoạch lồi.

Private Sub FrankWolfe() Dim i, solan As Integer Dim Fx, Fy As Double Dim sStr As String Dim bFlag As Boolean Dim xmin, ymin, fmin As Double Me.lstKetQua.Clear

Me.lstKetQua.AddItem ("0 F'x(z) = " + Trim(GetFx)) Me.lstKetQua.AddItem (" F'y(z) = " + Trim(GetFy)) i = 0 solan = 0

Do While True i = i + 1 Me.lstKetQua.AddItem ("") sStr = Trim(Str(i)) + " x(" + Trim(Str(i - 1)) + ") = " + Trim(Format(x(i - 1),

Fy = Fy_z0(y(i - 1)) sStr = " F'x(z" + Trim(Str(i - 1)) + ") = " + Trim(Format(Fx, "##0.##0")) sStr = sStr + ", F'y(z" + Trim(Str(i - 1)) + ") = " + Trim(Format(Fy,

Me.lstKetQua.AddItem (sStr) sStr = " Giải bài toán quy hoạch tuyến tính:"

Me.lstKetQua.AddItem (sStr) sStr = " min{ Fx * x0 + Fy * y0) Then xmin = x0 ymin = y0 fmin = Fx * x0 + Fy * y0

If (Not bFlag) Then bFlag = True xmin = x0 ymin = y0 fmin = Fx * x0 + Fy * y0

If (fmin > Fx * x0 + Fy * y0) Then xmin = x0 ymin = y0 fmin = Fx * x0 + Fy * y0

If (Not bFlag) Then bFlag = True xmin = x0 ymin = y0 fmin = Fx * x0 + Fy * y0

If (fmin > Fx * x0 + Fy * y0) Then xmin = x0 ymin = y0 fmin = Fx * x0 + Fy * y0

If (Not bFlag) Then bFlag = True xmin = x0 ymin = y0 fmin = Fx * x0 + Fy * y0

If (fmin > Fx * x0 + Fy * y0) Then xmin = x0 ymin = y0 fmin = Fx * x0 + Fy * y0

If (Not bFlag) Then bFlag = True xmin = x0 ymin = y0 fmin = Fx * x0 + Fy * y0

If (fmin > Fx * x0 + Fy * y0) Then xmin = x0 ymin = y0 fmin = Fx * x0 + Fy * y0

If (Not bFlag) Then bFlag = True xmin = x0 ymin = y0 fmin = Fx * x0 + Fy * y0

If (fmin > Fx * x0 + Fy * y0) Then xmin = x0 ymin = y0 fmin = Fx * x0 + Fy * y0

If (Not bFlag) Then bFlag = True xmin = x0 ymin = y0 fmin = Fx * x0 + Fy * y0

If (fmin > Fx * x0 + Fy * y0) Then xmin = x0 ymin = y0 fmin = Fx * x0 + Fy * y0

If (Not bFlag) Then bFlag = True xmin = x0 ymin = y0 fmin = Fx * x0 + Fy * y0

If (fmin > Fx * x0 + Fy * y0) Then xmin = x0 ymin = y0 fmin = Fx * x0 + Fy * y0

If (Not bFlag) Then bFlag = True xmin = x0 ymin = y0 fmin = Fx * x0 + Fy * y0

If (fmin > Fx * x0 + Fy * y0) Then xmin = x0 ymin = y0 fmin = Fx * x0 + Fy * y0

Me.lstKetQua.AddItem (" Có nghiệm là: z" + Trim(Str(i - 1)) + "' = (x, y) (" + Trim(Format(xmin, "##0.##0")) + ", " + Trim(Format(ymin, "##0.##0")) +

Me.lstKetQua.AddItem ("Bài toán QHTT trên không có nghiệm!")

If (Fx * (xmin - x(i - 1)) + Fy * (ymin - y(i - 1)) >= 0) Then

Me.lstKetQua.AddItem (" Do = " + Trim(Format(Fx * (xmin - x(i - 1)) + Fy

Me.lstKetQua.AddItem (" PATU là: (x, y) = (" + Trim(Format(x(i - 1),

Me.lstKetQua.AddItem (" Với giá trị HMT Fmin = " +

Me.lbKetQua.Caption = "Nghiệm là: (" + Trim(Format(x(i - 1), "##0.##0")) + ", " + Trim(Format(y(i - 1), "##0.##0")) + ")"

If (solan >= Val(Me.txtSoLanLap.Text)) Then

Me.lstKetQua.AddItem (" Do số nghiệm chọn là " +

Me.lstKetQua.AddItem (" PATU gần đúng là: (x, y) = (" + Trim(Format(x(i

Me.lstKetQua.AddItem (" Với giá trị HMT F = " +

Me.lbKetQua.Caption = "Nghiệm gần đúng là: (" + Trim(Format(x(i - 1),

Me.lstKetQua.AddItem (" Do = " + Trim(Format(Fx * (xmin - x(i - 1)) + Fy

Đoạn mã trên thực hiện giải bài toán một biến theo biến b, trong đó các biến ax, bx, ay, và by được tính toán dựa trên các giá trị x và y Công thức tính c bao gồm các hệ số C0, C1X, C2X, C1Y, và C2Y, trong khi b và a được tính toán từ các biến ax, ay, bx, và by.

Dim nghiem, min As Double

If (nghiem >= 0) And (nghiem a * 1 * 1 + b * 1 + c) Then nghiem = 1 x(i) = ax + nghiem * bx y(i) = ay + nghiem * by

If (a * 0 * 0 + b * 0 + c > a * 1 * 1 + b * 1 + c) Then nghiem = 1 x(i) = ax + nghiem * bx y(i) = ay + nghiem * by

Me.lstKetQua.AddItem (" Có nghiệm là b = " + Trim(Format(nghiem,

Me.lstKetQua.AddItem ("") solan = solan + 1

Sau khi hoàn thiện chương trình giải bài toán quy hoạch lồi bằng ngôn ngữ Visual Basic, tác giả đã đóng gói phần mềm thành một Setup để người dùng dễ dàng sử dụng Sau khi sao chép thư mục Setup về máy và cài đặt, người dùng có thể giải quyết các bài toán quy hoạch lồi một cách nhanh chóng và chính xác trên máy tính của mình.

Tác giả đặt tên cho phần mềm giải bài toán qui hoạch lồi này là – Qui

ứng dụng của phần mềm “Qui Ho³ch Lồi

2.3.1.Hướng dẫn c¯i đặt phần mềm –Qui Hoạch Lồi–

Sau khi tải bộ cài phần mềm về máy hoặc cài đặt trực tiếp từ đĩa, bạn cần thực hiện các bước cài đặt chương trình theo hướng dẫn.

B-ớc 1 Click vào biểu tượng “setup” trong bộ c¯i đ± t°i về m²y

B-íc 2 Click v¯o nót “ok” (h×nh 7)

B-ớc 3 Click v¯o biểu tượng “máy tính” (hình 8)

B-íc 4 Click v¯o nót “Continue” (h×nh 9)

B-ớc 5 Click vào nút “Yes” (hình 10)

B-ớc 6 Chờ dữ liệu chạy trong giây lát Sau khi hiện ra thông báo (hình

Quá trình cài đặt phần mềm "Qui Hoạch Lồi" trên máy tính của bạn đã hoàn tất Để chạy chương trình giải bài toán quy hoạch lồi, bạn chỉ cần vào Start -> Programs -> LTTU -> LTTU.

2.3.2 Một số nút lệnh trong ch-ơng trình

Done : Thực hiện ch-ơng trình

Refresh : Làm sạch ch-ơng trình

About : Giới thiệu về thuật toán Frank-Wofle Khi bạn click vào nút này sẽ hiện ra form giới thiệu về thuật toán Frank-Wofle (hình 6)

LoadFile : Mở các file đã đ-ợc l-u trong hệ thống

SaveFile : L-u lại file vừa nhập

Close : đóng ch-ơng trình

Giải bài toán qui hoạch lồi sau min f  x    x   y   | z  ( x , y )  M 

Lấy ph-ơng án xuất phát (x 0 , y 0 ) = (4, 1)

Trên giao diện chính của phần mềm bạn thực hiện nhập lần l-ợt hàm mục tiêu, các điều kiện ràng buộc của bài toán và nhập số nghiệm (hình 12)

Hình 12 Nhập giả thiết bài toán

Sau đó click vào nút done để thực hiện giải bài toán Kết quả sẽ đ-ợc nh- h×nh d-íi (h×nh 13)

Hình 13 Kết quả của bài toán ở bên cửa sổ kết quả sẽ cho ta thấy tóm tắt về các b-ớc giải và nghiệm của bài toán cần tìm

Vậy ph-ơng án tối -u của bài toán là: (x,y) = (1.5, 3.5)

Kết quả của luận văn bao gồm các nội dung sau

1) Hệ thống đ-ợc các kiến thức cơ bản về tập lồi, hàm lồi và bài toán qui hoạch lồi, phục vụ cho nghiên cứu

2) Viết ch-ơng trình thuật toán Frank – Wolfe giải bài toán qui hoạch lồi, bằng ngôn ngữ Visual Basic 6.0

3) Ch-ơng trình có tính mở (nhập dữ liệu từ bàn phím), đã đóng gói, chạy trên đĩa CD, tiện sử dụng cho mọi đối t-ợng sinh viên

4) Thể hiện chạy thử bằng số, cho kết quả khả thi

Vấn đề cần tiếp tục nghiên cứu:

Tác giả sẽ tiếp tục cải tiến chương trình giải bài toán quy hoạch lồi bằng thuật toán Frank-Wolfe và đồng thời nỗ lực xây dựng chương trình giải bài toán quy hoạch lồi bằng thuật toán Rosen trong tương lai.

Chương trình hiện tại vẫn còn nhiều điểm yếu và thiếu sót cần được cải thiện trong thời gian tới Tôi rất mong nhận được ý kiến đóng góp từ các thầy cô và bạn bè quan tâm đến vấn đề này.