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

    solution

    Đề bài: [Toán cho CNTT] Kiểm chứng đối ngẫu mạnh

    Định lý đối ngẫu mạnh

    Nếu x∗x^*x∗ là nghiệm tối ưu của primal (max⁡cTx\max c^T xmaxcTx) và w∗w^*w∗ là nghiệm tối ưu của dual (min⁡bTw\min b^T wminbTw) thì theo định lý đối ngẫu mạnh: cTx∗=bTw∗c^T x^* = b^T w^*cTx∗=bTw∗

    Cho các vector c,b,x,wc, b, x, wc,b,x,w, hãy kiểm tra cTxc^T xcTx có bằng bTwb^T wbTw hay không (khoảng chênh lệch đối ngẫu = duality gap).

    Ví dụ

    Nếu cTx=bTw=24c^T x = b^T w = 24cTx=bTw=24 thì in STRONG 24.0000.

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

      Dòng 1: n m. Dòng 2: n số ccc. Dòng 3: m số bbb. Dòng 4: n số xxx. Dòng 5: m số www.

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

      1≤n,m≤1001 \le n,m \le 1001≤n,m≤100; giá trị nguyên hoặc thập phân đơn giản.

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

      STRONG v nếu bằng nhau (v là giá trị chung); ngược lại GAP g với g=bTw−cTxg = b^Tw - c^Txg=bTw−cTx.

    Ví dụ:

    Đầu vào:

    2 2
3 5
4 12
8 0
6 0

    Đầu ra:

    STRONG 24.0000

    Giải thích:

    z_primal = 3*8+5*0=24; z_dual = 4*6+12*0=24. Bang nhau -> doi ngau manh.

    Đang tải editor...