Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Toán cho CNTT] Xác định đỉnh tối ưu

    Đỉnh tối ưu

    Cho bài toán max⁡ z=c1x+c2y\max\, z = c_1 x + c_2 ymaxz=c1​x+c2​y với aix+biy≤cia_i x + b_i y \le c_iai​x+bi​y≤ci​, x,y≥0x,y\ge0x,y≥0. Hãy tìm tọa độ đỉnh đạt giá trị tối ưu. Nếu nhiều đỉnh cùng đạt tối ưu, chọn đỉnh có xxx nhỏ nhất, rồi yyy nhỏ nhất.

    Ví dụ

    max⁡ 3x+2y\max\, 3x+2ymax3x+2y với x+y≤4x+y\le4x+y≤4, x,y≥0x,y\ge0x,y≥0: đỉnh tối ưu là (4,0)(4, 0)(4,0).

    • Định dạng đầu vào:

      Dòng 1: c1 c2. Dòng 2: n. n dòng a b c.

    • Ràng buộc đầu vào:

      1≤n≤201 \le n \le 201≤n≤20; hệ số nguyên trị tuyệt đối ≤100\le 100≤100; miền bị chặn.

    • Định dạng đầu ra:

      Tọa độ đỉnh tối ưu x y (4 chữ số thập phân).

    Ví dụ:

    Đầu vào:

    3 2
1
1 1 4

    Đầu ra:

    4.0000 0.0000

    Giải thích:

    Dinh (4,0) cho z=12, lon hon (0,4) cho z=8.

    Đang tải editor...