Simplex - kiểm định tỉ số (ratio test)

Sau khi chọn cột pivot, ta chọn biến ra bằng kiểm định tỉ số: với mỗi hàng $i$ có hệ số cột pivot $a_i > 0$ , tính tỉ số $\theta_i = b_i / a_i$ . Chọn hàng có $\theta_i$ nhỏ nhất. Nếu không hàng nào có $a_i > 0$ thì bài toán không bị chặn.

Ví dụ

Các hàng (b,a): $(12,2), (6,1), (8,4)$ cho tỉ số $6, 6, 2$ . Nhỏ nhất tại hàng 2 nên in 2.

Định dạng đầu vào:
Dòng 1: m. m dòng tiếp theo, mỗi dòng b a (RHS và hệ số cột pivot).
Ràng buộc đầu vào:
$1 \le m \le 100$ ; giá trị nguyên; nếu hòa tỉ số, chọn hàng chỉ số nhỏ hơn.
Định dạng đầu ra:
Chỉ số hàng pivot (0-based) có tỉ số nhỏ nhất, hoặc UNBOUNDED.

solution

Đề bài: [Toán cho CNTT] Simplex: kiểm định tỉ số (biến ra)

Simplex - kiểm định tỉ số (ratio test)

Ví dụ