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

    solution

    Đề bài: [Toán cho CNTT] Tối thiểu hai biến với ràng buộc lớn hơn hoặc bằng

    Tối thiểu hóa (ràng buộc ≥\ge≥)

    Bài toán khẩu phần thường có dạng: min⁡  z=c1x+c2yvới aix+biy≥ci,  x,y≥0\min\; z = c_1 x + c_2 y \quad \text{với } a_i x + b_i y \ge c_i,\; x,y \ge 0minz=c1​x+c2​yvới ai​x+bi​y≥ci​,x,y≥0

    Hãy tìm giá trị nhỏ nhất của zzz tại các đỉnh của miền khả thi.

    Ví dụ

    min⁡ 2x+3y\min\, 2x+3ymin2x+3y với x+y≥4x+y\ge4x+y≥4, x,y≥0x,y\ge0x,y≥0: tối ưu z=8z=8z=8 tại (4,0)(4,0)(4,0).

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

      Dòng 1: c1 c2. Dòng 2: n. n dòng tiếp a b c cho ràng buộc ax+by≥cax+by\ge cax+by≥c. Ngầm định x,y≥0x,y\ge0x,y≥0.

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

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

      Giá trị tối ưu nhỏ nhất (4 chữ số thập phân), hoặc NONE nếu miền rỗng.

    Ví dụ:

    Đầu vào:

    2 3
1
1 1 4

    Đầu ra:

    8.0000

    Giải thích:

    Mien x+y>=4, x,y>=0. Nho nhat cua 2x+3y tai (4,0) la 8.

    Đang tải editor...