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

    solution

    Đề bài: [Toán cho CNTT] Giải LP hai biến tổng quát

    Giải LP hai biến tổng quát

    Giải bài toán: MAX/MIN  z=c1x+c2y\text{MAX/MIN}\; z = c_1 x + c_2 yMAX/MINz=c1​x+c2​y với nnn ràng buộc có thể là ≤\le≤, ≥\ge≥ hoặc ===, cùng x,y≥0x,y \ge 0x,y≥0.

    Chuyển mọi ràng buộc về dạng ≤\le≤ (đổi dấu với ≥\ge≥; tách === thành hai bất đẳng thức), sinh mọi đỉnh, lọc khả thi và chọn tối ưu theo chiều bài toán.

    Ví dụ

    MAX 3 2 với x+y≤4x+y\le4x+y≤4, x≥1x\ge1x≥1: tối ưu z=12z=12z=12 tại (4,0)(4,0)(4,0).

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

      Dòng 1: SENSE c1 c2 (SENSE là MAX hoặc MIN). Dòng 2: n. n dòng a b rel c với rel ∈{\in\{∈{<=,>=,=}\}}.

    • 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 khi tối ưu tồn tại.

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

      Giá trị tối ưu (4 chữ số thập phân), hoặc INFEASIBLE.

    Ví dụ:

    Đầu vào:

    MAX 3 2
2
1 1 <= 4
1 0 >= 1

    Đầu ra:

    12.0000

    Giải thích:

    Mien x+y<=4, x>=1, y>=0. Dinh (4,0) cho z=12 la lon nhat.

    Đang tải editor...