Trang này được dịch bởi Cloud Translation API.

Làm quen với OR-Tools cho .Net

Các phần sau đây sẽ giúp bạn bắt đầu sử dụng OR-Tools cho .Net:

Vấn đề tối ưu hoá là gì?
Giải quyết vấn đề tối ưu hoá trong .Net
Ví dụ khác về miền .Net
Xác định loại vấn đề mà bạn muốn giải quyết

Vấn đề tối ưu hoá là gì?

Mục tiêu của tính năng tối ưu hoá là tìm ra giải pháp tốt nhất cho một vấn đề trong số một nhóm lớn các giải pháp khả thi. (Đôi khi bạn sẽ hài lòng với việc tìm thấy bất kỳ giải pháp khả thi nào; OR-Tools cũng có thể làm điều đó).

Dưới đây là một vấn đề thường gặp về tối ưu hoá. Giả sử rằng một công ty vận chuyển giao gói hàng cho khách hàng của họ bằng một đội xe tải. Mỗi ngày, công ty phải giao các gói hàng cho xe tải, sau đó chọn tuyến đường cho từng xe tải để giao các gói hàng đó. Mỗi lần chỉ định gói và tuyến đường có thể có chi phí, dựa trên tổng quãng đường đi của xe tải và cả các yếu tố khác. Vấn đề là phải chọn chỉ định các gói và tuyến có chi phí thấp nhất.

Giống như tất cả bài toán tối ưu hoá, vấn đề này có các yếu tố sau:

Mục tiêu: số lượng bạn muốn tối ưu hoá. Trong ví dụ trên, mục tiêu là để giảm thiểu chi phí. Để thiết lập một vấn đề tối ưu hoá, bạn cần xác định một hàm tính toán giá trị của mục tiêu cho mọi giải pháp khả thi. Hàm này được gọi là hàm mục tiêu. Trong ví dụ trước, hàm mục tiêu sẽ tính tổng chi phí của mọi hoạt động chỉ định gói và tuyến đường.

Giải pháp tối ưu là giải pháp mà trong đó giá trị của hàm mục tiêu là tốt nhất. ("Tốt nhất" có thể là giá trị tối đa hoặc tối thiểu.)
Các quy tắc ràng buộc – các hạn chế đối với tập hợp giải pháp có thể có, dựa trên yêu cầu cụ thể của vấn đề. Ví dụ: nếu công ty vận chuyển không thể chỉ định các gói hàng có trọng lượng lớn hơn một trọng lượng nhất định cho xe tải, thì điều này sẽ gây hạn chế cho các giải pháp.

Giải pháp khả thi là một giải pháp đáp ứng tất cả các hạn chế đặt ra cho vấn đề mà không nhất thiết phải là giải pháp tối ưu.

Bước đầu tiên để giải quyết một vấn đề tối ưu hoá là xác định mục tiêu và các hạn chế.

Giải bài tập tối ưu hoá trong .Net

Tiếp theo, chúng tôi sẽ đưa ra ví dụ về một vấn đề tối ưu hoá, cũng như hướng dẫn cách thiết lập và giải quyết vấn đề đó trong .Net.

Ví dụ về phương pháp tối ưu hoá tuyến tính

Một trong những phương pháp tối ưu hoá lâu đời và được sử dụng rộng rãi nhất là tối ưu hoá tuyến tính (hoặc lập trình tuyến tính), trong đó hàm mục tiêu và các quy tắc ràng buộc có thể được viết dưới dạng biểu thức tuyến tính. Dưới đây là ví dụ đơn giản về loại vấn đề này.

Tối đa hoá 3x + y tuân theo các điều kiện ràng buộc sau:

0 ≤ x ≤ 1
0 ≤ y ≤ 2
x + y ≤ 2

Hàm mục tiêu trong ví dụ này là 3x + y. Cả hàm mục tiêu và các quy tắc ràng buộc đều do biểu thức tuyến tính tính, khiến đây là bài toán tuyến tính.

Các bước chính trong việc giải bài tập

Đối với mỗi ngôn ngữ, các bước cơ bản để thiết lập và giải quyết một vấn đề đều giống nhau:

Nhập các thư viện bắt buộc,
Khai báo trình giải,
Tạo các biến,
Xác định các điều kiện ràng buộc,
Xác định hàm mục tiêu,
Gọi trình giải và
Hiện kết quả.

Chương trình .Net

Phần này giới thiệu về chương trình .Net để thiết lập và giải quyết vấn đề.

Sau đây là các bước:

Nhập các thư viện cần thiết.

using System;
using Google.OrTools.LinearSolver;

Khai báo trình giải toán.
```
// Create the linear solver with the GLOP backend.
Solver solver = Solver.CreateSolver("GLOP");
if (solver is null)
{
    return;
}
```
MPSolver là một trình bao bọc để giải quyết mọi vấn đề về lập trình tuyến tính hoặc lập trình số nguyên hỗn hợp.

Tạo các biến.

// Create the variables x and y.
Variable x = solver.MakeNumVar(0.0, 1.0, "x");
Variable y = solver.MakeNumVar(0.0, 2.0, "y");

Console.WriteLine("Number of variables = " + solver.NumVariables());

Xác định các điều kiện ràng buộc. Hai điều kiện ràng buộc đầu tiên, 0 &leq; x ≤ 1 và 0 &leq; y ≤ 2, đã được đặt trong định nghĩa của các biến. Mã sau đây xác định điều kiện ràng buộc x + y &leq; 2:
```
// Create a linear constraint, 0 <= x + y <= 2.
Constraint ct = solver.MakeConstraint(0.0, 2.0, "ct");
ct.SetCoefficient(x, 1);
ct.SetCoefficient(y, 1);

Console.WriteLine("Number of constraints = " + solver.NumConstraints());
```
Phương thức SetCoefficient đặt hệ số của x và y trong biểu thức cho quy tắc ràng buộc.

Xác định hàm mục tiêu.

// Create the objective function, 3 * x + y.
Objective objective = solver.Objective();
objective.SetCoefficient(x, 3);
objective.SetCoefficient(y, 1);
objective.SetMaximization();

Phương thức setMaximization khai báo đây là vấn đề tối đa hoá. (Phương thức C++ cơ bản là SetMaximization.

Gọi trình giải và hiện kết quả.

solver.Solve();
Console.WriteLine("Solution:");
Console.WriteLine("Objective value = " + solver.Objective().Value());
Console.WriteLine("x = " + x.SolutionValue());
Console.WriteLine("y = " + y.SolutionValue());

Hoàn thành chương trình

Chương trình hoàn chỉnh được hiển thị dưới đây.

using System;
using Google.OrTools.LinearSolver;

public class BasicExample
{
    static void Main()
    {
        // Create the linear solver with the GLOP backend.
        Solver solver = Solver.CreateSolver("GLOP");
        if (solver is null)
        {
            return;
        }

        // Create the variables x and y.
        Variable x = solver.MakeNumVar(0.0, 1.0, "x");
        Variable y = solver.MakeNumVar(0.0, 2.0, "y");

        Console.WriteLine("Number of variables = " + solver.NumVariables());

        // Create a linear constraint, 0 <= x + y <= 2.
        Constraint ct = solver.MakeConstraint(0.0, 2.0, "ct");
        ct.SetCoefficient(x, 1);
        ct.SetCoefficient(y, 1);

        Console.WriteLine("Number of constraints = " + solver.NumConstraints());

        // Create the objective function, 3 * x + y.
        Objective objective = solver.Objective();
        objective.SetCoefficient(x, 3);
        objective.SetCoefficient(y, 1);
        objective.SetMaximization();

        solver.Solve();

        Console.WriteLine("Solution:");
        Console.WriteLine("Objective value = " + solver.Objective().Value());
        Console.WriteLine("x = " + x.SolutionValue());
        Console.WriteLine("y = " + y.SolutionValue());
    }
}

Chạy chương trình .Net

Bạn có thể chạy chương trình ở trên như sau:

Sao chép và dán mã ở trên vào tệp mới và lưu mã đó dưới dạng BasicExample.cs. trong thư mục con examples/dotnet của thư mục mà bạn đã cài đặt OR-Tools.

Trong chính thư mục đó, hãy tạo một tệp mới, BasicExample.csproj và thêm mã sau:

<Project Sdk="Microsoft.NET.Sdk">
  <PropertyGroup>
    <OutputType>Exe</OutputType>
    <LangVersion>7.3</LangVersion>
    <TargetFramework>netcoreapp3.1</TargetFramework>
    <EnableDefaultItems>false</EnableDefaultItems>
    <!-- see https://github.com/dotnet/docs/issues/12237 -->
    <RollForward>LatestMajor</RollForward>
    <RestoreSources>../../../temp_dotnet/packages;$(RestoreSources);https://api.nuget.org/v3/index.json</RestoreSources>
    <AssemblyName>Google.OrTools.BasicExample</AssemblyName>
    <IsPackable>true</IsPackable>
  </PropertyGroup>

  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
    <DebugType>full</DebugType>
    <Optimize>true</Optimize>
    <GenerateTailCalls>true</GenerateTailCalls>
  </PropertyGroup>

  <ItemGroup>
    <Compile Include="BasicExample.cs" />
    <PackageReference Include="Google.OrTools" Version="9.1.*" />
  </ItemGroup>
</Project>

Ở cấp cao nhất của thư mục nơi bạn đã cài đặt OR-Tools, hãy mở một cửa sổ lệnh và nhập:
```
make run SOURCE=examples/dotnet/BasicExample.cs
```

Bạn có thể lưu và chạy các chương trình .Net trong một thư mục khác với examples/dotnet/, nhưng việc này phức tạp hơn một chút: bạn phải sửa đổi dòng sau của tệp csproj, như minh hoạ ở trên:

../../../packages;$(RestoreSources);https://api.nuget.org/v3/index.json

để có đường dẫn chính xác đến thư mục packages.

Cách dễ nhất là đặt các chương trình .Net trong thư mục examples/dotnet/.

Chương trình này trả về các giá trị của x và y giúp tăng tối đa hàm mục tiêu:

Solution:
x =  1.0
y =  1.0

Để chỉ biên dịch mà không cần chạy chương trình, hãy nhập:

make build SOURCE=relative/path/to/SimpleProgram.cs

Nếu thay đổi chương trình, bạn cần phải biên dịch lại như trên.

Ví dụ khác về miền .Net

Để xem thêm các ví dụ về .Net minh hoạ cách giải quyết nhiều loại vấn đề tối ưu hoá, hãy xem phần Ví dụ.

Xác định loại vấn đề bạn muốn giải quyết

Có nhiều loại bài tập tối ưu hoá trên thế giới. Đối với mỗi loại bài toán, sẽ có nhiều phương pháp và thuật toán khác nhau để tìm ra một giải pháp tối ưu.

Trước khi có thể bắt đầu viết một chương trình để giải quyết một vấn đề tối ưu hoá, bạn cần xác định loại vấn đề mình đang gặp phải, sau đó chọn một trình giải quyết phù hợp — một thuật toán để tìm ra giải pháp tối ưu.

Dưới đây là thông tin tổng quan ngắn gọn về các loại vấn đề mà Công cụ OR có thể giải quyết, cũng như các đường liên kết đến các phần trong hướng dẫn này để giải thích cách giải quyết từng loại vấn đề.

Tối ưu hoá tuyến tính
Tối ưu hoá quy tắc ràng buộc
Tối ưu hoá cho cả số nguyên
Bài tập
Lập lịch
Đóng gói
Định tuyến
Luồng mạng

Tối ưu hoá tuyến tính

Như bạn đã tìm hiểu trong phần trước, bài toán tối ưu hoá tuyến tính là bài toán khi hàm mục tiêu và các giới hạn là biểu thức tuyến tính trong các biến.

Trình giải quyết chính trong OR-Tools cho loại vấn đề này là trình giải quyết tối ưu hoá tuyến tính. Trình giải quyết này thực sự là một trình bao bọc cho một số thư viện khác nhau để tối ưu hoá tuyến tính và hỗn hợp số nguyên, bao gồm cả các thư viện của bên thứ ba.

Tìm hiểu thêm về tính năng tối ưu hoá tuyến tính

Tối ưu hoá hỗn hợp số nguyên

Vấn đề tối ưu hoá số nguyên hỗn hợp là vấn đề trong đó một số hoặc tất cả các biến bắt buộc phải là số nguyên. Ví dụ như vấn đề về chỉ định, trong đó, một nhóm worker cần được chỉ định cho một nhóm tác vụ. Đối với mỗi trình thực thi và tác vụ, bạn xác định một biến có giá trị là 1 nếu trình thực thi đó được chỉ định cho tác vụ nhất định và là 0 nếu không. Trong trường hợp này, các biến chỉ có thể nhận giá trị 0 hoặc 1.

Tìm hiểu thêm về tính năng tối ưu hoá kết hợp số nguyên

Tối ưu hoá hạn chế

Tối ưu hoá quy tắc ràng buộc, hay lập trình ràng buộc (CP), xác định các giải pháp khả thi trong số một nhóm đề xuất rất lớn, trong đó vấn đề có thể được mô hình hoá dưới dạng các quy tắc ràng buộc tuỳ ý. CP dựa trên tính khả thi (tìm một giải pháp khả thi) thay vì tối ưu hoá (tìm một giải pháp tối ưu) và tập trung vào các quy tắc ràng buộc và biến thay vì hàm mục tiêu. Tuy nhiên, bạn có thể dùng CP để giải các vấn đề tối ưu hoá chỉ bằng cách so sánh giá trị của hàm mục tiêu với tất cả các giải pháp khả thi.

Tìm hiểu thêm về việc tối ưu hoá quy tắc ràng buộc

Assignment

Bài tập gán liên quan đến việc chỉ định một nhóm tác nhân (chẳng hạn như worker hoặc máy) cho một tập hợp tác vụ, trong đó có chi phí cố định để chỉ định từng tác nhân cho một tác vụ cụ thể. Vấn đề là tìm bài tập có tổng chi phí thấp nhất. Sự cố gán thực sự là một trường hợp đặc biệt của vấn đề về luồng mạng.

Tìm hiểu thêm về việc chỉ định số điện thoại

Đóng hàng

Đóng gói trong thùng là vấn đề khi phải đóng gói một tập hợp đối tượng có kích thước khác nhau vào các vùng chứa có dung lượng khác nhau. Mục tiêu là đóng gói nhiều đối tượng nhất có thể, tuỳ thuộc vào dung lượng của các vùng chứa. Một trường hợp đặc biệt của trường hợp này là vấn đề Knapsack, trong đó chỉ có một vùng chứa.

Tìm hiểu thêm về cách đóng gói thùng rác

Lập lịch

Vấn đề về lịch trình liên quan đến việc chỉ định tài nguyên để thực hiện một nhóm tác vụ vào các thời điểm cụ thể. Một ví dụ quan trọng là vấn đề về cửa hàng việc làm, trong đó nhiều công việc được xử lý trên một số máy. Mỗi công việc bao gồm một chuỗi các tác vụ phải được thực hiện theo thứ tự nhất định và phải xử lý mỗi tác vụ trên một máy cụ thể. Vấn đề là chỉ định lịch biểu để tất cả các công việc được hoàn thành trong khoảng thời gian ngắn nhất có thể.

Tìm hiểu thêm về cách lên lịch

Đang định tuyến

Vấn đề định tuyến liên quan đến việc tìm tuyến đường tối ưu cho một nhóm xe để đi qua mạng, được xác định bằng biểu đồ có hướng. Vấn đề chỉ định gói hàng cho xe giao hàng, được mô tả trong phần Vấn đề tối ưu hoá là gì? là một ví dụ về sự cố định tuyến. Một vấn đề khác là vấn đề nhân viên bán hàng đi lại.

Tìm hiểu thêm về cách định tuyến

Luồng mạng

Nhiều bài toán tối ưu hoá có thể được biểu thị bằng một biểu đồ có hướng bao gồm các nút và vòng cung định hướng giữa chúng. Ví dụ: các vấn đề về vận tải, trong đó hàng hoá được vận chuyển qua mạng lưới đường sắt, có thể được biểu thị bằng một biểu đồ, trong đó các vòng cung là các tuyến đường sắt và các nút là các trung tâm phân phối.

Trong bài toán về luồng tối đa, mỗi cung có sức chứa tối đa có thể được truyền tải qua nó. Vấn đề là chỉ định số lượng hàng hoá cần vận chuyển qua mỗi vòng cung để tổng số lượng hàng được vận chuyển càng lớn càng tốt.

Tìm hiểu thêm về các luồng mạng