import scipy.optimize as so
from scipy.optimize import linprog
import numpy as np

# Trước hết, ta cần tạo các tham số cần thiết để truyền vào hàm.

# Định nghĩa c
# Do đây là bài toán tối đa hóa, ta lấy phần đối của c
c = - np.array([
    5,
    4,
    3,
])

# Định nghĩa A_ub và b_ub
A_ub = np.array([
    [3, 4, 2],
    [4, 1, 2],
    [2, 3, 1],
])
b_ub = np.array([
    8,
    11,
    5,
])

# Định nghĩa A_eq và b_eq
# Do bài toán không có điều kiện đẳng thức, ta không nhất thiết phải định nghĩa.
A_eq = None
b_eq = None

# Định nghĩa bounds
# Do các cận trùng với chế độ mặc định, ta không nhất thiết phải định nghĩa.
bounds = [
    (0, None)
    for i in range(len(c))
]

# Với đủ các tham số cần thiết, ta sử dụng hàm scipy.optimize.linprog
# để giải bài quy hoạch tuyến tính trên
result = linprog(
    c=c,
    A_ub=A_ub,
    b_ub=b_ub,
    A_eq=A_eq,
    b_eq=b_eq,
    bounds=bounds,
)
print(result)

        message: Optimization terminated successfully. (HiGHS Status 7: Optimal)
        success: True
         status: 0
            fun: -13.0
              x: [ 2.000e+00  0.000e+00  1.000e+00]
            nit: 2
          lower:  residual: [ 2.000e+00  0.000e+00  1.000e+00]
                 marginals: [ 0.000e+00  3.000e+00  0.000e+00]
          upper:  residual: [       inf        inf        inf]
                 marginals: [ 0.000e+00  0.000e+00  0.000e+00]
          eqlin:  residual: []
                 marginals: []
        ineqlin:  residual: [ 0.000e+00  1.000e+00  0.000e+00]
                 marginals: [-1.000e+00 -0.000e+00 -1.000e+00]
 mip_node_count: 0
 mip_dual_bound: 0.0
        mip_gap: 0.0

if result.success:
    print("Giá trị tối ưu:", result.fun)
    print("Nghiệm tối ưu:", result.x)
else:
    print("Lỗi:", result.message)

Giá trị tối ưu: -13.0
Nghiệm tối ưu: [2. 0. 1.]

def max_flow_sol(d):
    """
    Hàm tìm ra lưu lượng nước tối đa mà thành phố nguồn có thể gửi
    và lưu lượng nước ở từng thành phố ứng với lưu lượng tối đa này.

    Đầu vào:
      d (mảng 2 chiều):
        dung tích của các tuyến đường ống

    Đầu ra:
      best (số thực):
        lưu lượng nước tối đa mà thành phố nguồn có thể gửi
      f (mảng 2 chiều):
        lưu lượng nước của từng thành phố ứng với lưu lượng tối đa
    """
    n, _ = d.shape

    # Định nghĩa hàm mục tiêu
    c = np.zeros(n * n)
    for j in range(n):
        c[0 * n + j] = 1
    c = -c

    # Định nghĩa các điều kiện bất đẳng thức
    A_ub = None
    b_ub = None

    # Định nghĩa các điều kiện đẳng thức
    A_eq = np.zeros((n, n * n))
    for j in range(1, n - 1):
        for i in range(n):
            if d[i, j] > 0 or d[j, i] > 0:
                A_eq[j, i * n + j] = 1

        for k in range(n):
            if d[j, k] > 0 or d[k, j] > 0:
                A_eq[j, j * n + k] = -1

    b_eq = np.zeros(n)

    # Định nghĩa cận
    bounds = []
    for k in range(n * n):
        i = k // n
        j = k % n
        bounds.append(
            (0, d[i, j])
        )

    # Sử dụng scipy.optimize.linprog
    result = linprog(
        c=c,
        A_ub=A_ub,
        b_ub=b_ub,
        A_eq=A_eq,
        b_eq=b_eq,
        bounds=bounds,
    )

    # Chuyển đổi từ nghiệm sang lưu lượng
    best = -result.fun

    f = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            f[i, j] = result.x[i * n + j]

    return best, f

d = np.array([
    [0, 10, 5, 0],
    [0, 0, 15, 5],
    [0, 0, 0, 10],
    [0, 0, 0, 0],
])
best, f = max_flow_sol(d)
print("Lưu lượng nước tối đa:", best)
print("Lưu lượng nước ở từng thành phố:")
print(f)
assert best == 15, \
    "Kết quả trả về không đúng"
assert np.allclose(
    f,
    np.array([
        [0, 10, 5, 0],
        [0, 0, 5, 5],
        [0, 0, 0, 10],
        [0, 0, 0, 0],
    ])
), \
    "Kết quả trả về không đúng"

Lưu lượng nước tối đa: 15.0
Lưu lượng nước ở từng thành phố:
[[ 0. 10.  5.  0.]
 [ 0.  0.  5.  5.]
 [ 0.  0.  0. 10.]
 [ 0.  0.  0.  0.]]

def project_assignment_sol(m, k, preference):
    '''
    Hàm tìm cách sắp xếp dự án cho các bạn trại sinh.

    Đầu vào:
      m (số nguyên):
        số lượng dự án. Các dự án được đánh số từ 0 đến m - 1.
      k (số nguyên):
        giới hạn số trại sinh cho 1 dự án
      preference (danh sách các danh sách):
        với mỗi trại sinh, lưu danh sách các dự án mà trại sinh thích

    Đầu ra:
      is_able (luận lý):
        liệu có cách sắp xếp cho mọi trại sinh hay không
      assignment (danh sách các số nguyên):
        chỉ số của dự án mà mỗi trại sinh được giao
    '''
    # Số lượng thành phố loại I
    n = len(preference)

    # Các thành phố bao gồm thành phố nguồn,
    # các thành phố loại I, loại II,
    # và thành phố đích
    n_v = 1 + n + m + 1

    # Khởi tạo dung tích hệ thống ống nước
    # bằng 0 cho mọi đường ống
    d = np.zeros((n_v, n_v))

    # Đối với các đường ống loại A
    for i in range(n):
        d[0, 1 + i] = 1

    # Đối với các đường ống loại B
    for i, preferred_projects in enumerate(preference):
        for j in preferred_projects:
            d[1 + i, 1 + n + j] = 1

    # Đối với các đường ống loại C
    for i in range(m):
        d[1 + n + i, n_v - 1] = k

    # Tìm lưu lượng cực đại và giá trị
    # lưu lượng của mỗi đường ống cho
    # hệ thống ống nước trên
    best, f = max_flow_sol(d)

    # Chuyển đổi từ lưu lượng sang giải pháp
    is_able = (best == n)

    assignment = [None for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if f[1 + i, 1 + n + j] == 1:
                assignment[i] = j

    return is_able, assignment

print("== Test 1")

m = 6
k = 3
preference = [
    [2, 4],
    [1, 3, 4, 5],
    [2, 3, 5],
    [1, 3, 4],
    [0, 1, 2, 3, 5],
    [0, 2, 3, 4],
    [0, 1, 2, 3],
    [1, 4, 5],
    [1, 3, 4],
    [3, 4, 5],
    [1, 2, 3],
    [1],
    [2, 3, 4, 5],
    [2, 3, 4, 5],
    [1, 2, 3, 4, 5],
]
test = (m, k, preference)
is_able, assignment = project_assignment_sol(*test)
print("Tính khả thi:", is_able)
print("Kết quả:")
print(assignment)
print("Diễn giải:")
assignment_dict = dict()
unassigned = set()
for i, j in enumerate(assignment):
    if j is None:
        unassigned.add(i)
    else:
        assignment_dict.setdefault(j, []).append(i)
for i in range(m):
    print(f"Dự án {i}: {assignment_dict.get(i, [])}")
print("Các trại sinh không được giao dự án:", unassigned)

assert is_able, \
    "Kết quả trả về không đúng"

count = dict()
for i, j in enumerate(assignment):
    assert j in preference[i], \
      "Kết quả trả về không đúng"

    count.setdefault(j, 0)
    count[j] += 1
    assert count[j] <= k, \
      "Kết quả trả về không đúng"

print("== Test 1: thành công")

print()

print("== Test 2")

m = 2
k = 1
preference = [
    [1],
    [1],
]
test = (m, k, preference)
is_able, assignment = project_assignment_sol(*test)
print("Tính khả thi:", is_able)
print("Kết quả:")
print(assignment)
print("Diễn giải:")
assignment_dict = dict()
unassigned = set()
for i, j in enumerate(assignment):
    if j is None:
        unassigned.add(i)
    else:
        assignment_dict.setdefault(j, []).append(i)
for i in range(m):
    print(f"Dự án {i}: {assignment_dict.get(i, [])}")
print("Các trại sinh không được giao dự án:", unassigned)

assert not is_able, \
    "Kết quả trả về không đúng"

count = dict()
for i, j in enumerate(assignment):
    if i not in preference:
        continue

    assert j in preference[i], \
      "Kết quả trả về không đúng"

    count.setdefault(j, 0)
    count[j] += 1
    assert count[j] <= k, \
      "Kết quả trả về không đúng"

print("== Test 2: thành công")

== Test 1
Tính khả thi: True
Kết quả:
[4, 5, 2, 1, 0, 0, 0, 1, 3, 4, 3, 1, 5, 3, 5]
Diễn giải:
Dự án 0: [4, 5, 6]
Dự án 1: [3, 7, 11]
Dự án 2: [2]
Dự án 3: [8, 10, 13]
Dự án 4: [0, 9]
Dự án 5: [1, 12, 14]
Các trại sinh không được giao dự án: set()
== Test 1: thành công

== Test 2
Tính khả thi: False
Kết quả:
[1, None]
Diễn giải:
Dự án 0: []
Dự án 1: [0]
Các trại sinh không được giao dự án: {1}
== Test 2: thành công

def party_arrange_sol(n, k, friends):
    '''
    Hàm tìm cách sắp xếp cho các bạn cựu trại sinh nói chuyện với nhau
    trong buổi tiệc.

    Đầu vào:
      n (số nguyên):
        số lượng cựu trại sinh
      k (số nguyên):
        giới hạn số lần bắt chuyện
      friends (tập hợp):
        tập hợp các cặp người quen

    Đầu ra:
      is_able (luận lý):
        liệu có cách sắp xếp hay không
      arrangement (tập hợp):
        các cặp người quen được sắp xếp tối đa
    '''

    # Số lượng thành phố loại I
    m = len(friends)

    # Các thành phố bao gồm thành phố nguồn,
    # các thành phố loại I, loại II,
    # và thành phố đích
    n_v = 1 + m + n + 1

    d = np.zeros((n_v, n_v))

    for i in range(m):
        d[0, 1 + i] = 1

    for t, (i, j) in enumerate(friends):
        d[1 + t, 1 + m + i] = 1
        d[1 + t, 1 + m + j] = 1

    for i in range(n):
        d[1 + m + i, n_v - 1] = k

    best, f = max_flow_sol(d)

    is_able = (best == m)

    arrangement = []
    for t, (i, j) in enumerate(friends):
        if f[1 + t, 1 + m + i] == 1:
            arrangement.append((i, j))
        elif f[1 + t, 1 + m + j] == 1:
            arrangement.append((j, i))

    return is_able, arrangement

print("== Test 1")

n = 5
k = 2
friends = [
    (0, 1), (0, 2),
    (1, 2), (1, 3), (1, 4),
    (2, 3), (2, 4),
    (3, 4),
]
test = (n, k, friends)
is_able, arrangement = party_arrange_sol(*test)
print("Tính khả thi:", is_able)
print("Kết quả:")
print(arrangement)

assert is_able, \
    "Kết quả trả về không đúng"

count = dict()
for i, j in arrangement:
    count.setdefault(i, 0)
    count[i] += 1
    assert count[i] <= k, \
      "Kết quả trả về không đúng"

print("== Test 1: thành công")

print()

print("== Test 2")

n = 5
k = 1
friends = [
    (0, 1), (0, 2),
    (1, 2), (1, 3), (1, 4),
    (2, 3), (2, 4),
    (3, 4),
]
test = (n, k, friends)
is_able, arrangement = party_arrange_sol(*test)
print("Tính khả thi:", is_able)
print("Kết quả:")
print(arrangement)

assert not is_able, \
    "Kết quả trả về không đúng"

count = dict()
for i, j in arrangement:
    count.setdefault(i, 0)
    count[i] += 1
    assert count[i] <= k, \
      "Kết quả trả về không đúng"

print("== Test 2: thành công")

== Test 1
Tính khả thi: True
Kết quả:
[(0, 1), (0, 2), (2, 1), (3, 1), (1, 4), (3, 2), (2, 4), (4, 3)]
== Test 1: thành công

== Test 2
Tính khả thi: False
Kết quả:
[(0, 1), (1, 3), (2, 3), (4, 2), (3, 4)]
== Test 2: thành công

def party_arrange_sol2(n, k, friends):
    '''
    Hàm tìm cách sắp xếp cho các bạn cựu trại sinh nói chuyện với nhau
    trong buổi tiệc.

    Đầu vào:
      n (số nguyên):
        số lượng cựu trại sinh
      k (số nguyên):
        giới hạn số lần bắt chuyện
      friends (tập hợp):
        tập hợp các cặp người quen

    Đầu ra:
      is_able (luận lý):
        liệu có cách sắp xếp hay không
      arrangement (tập hợp):
        các cặp người quen được sắp xếp tối đa
    '''

    # Số lượng "dự án" = số lượng cặp người quen
    m = len(friends)

    # Giới hạn số "trại sinh" cho mỗi "dự án"
    # = giới hạn số lần bắt chuyện
    k = k

    # Mỗi "trại sinh" chỉ "yêu thích" 2 "dự án"
    preference = [
        [i, j]
        for i, j in friends
    ]

    # Giải bài toán xếp dự án
    is_able_p, assignment_p = project_assignment_sol(m, k, preference)
    print(assignment_p)

    # Chuyển kết quả thành giải pháp
    is_able = is_able_p

    arrangement = []
    for i, j in enumerate(assignment_p):
        if j is None:
            continue
        u, v = friends[i]
        if j == u:
            arrangement.append((u, v))
        else:
            arrangement.append((v, u))

    return is_able, arrangement

print("== Test 1")

n = 5
k = 2
friends = [
    (0, 1), (0, 2),
    (1, 2), (1, 3), (1, 4),
    (2, 3), (2, 4),
    (3, 4),
]
test = (n, k, friends)
is_able, arrangement = party_arrange_sol(*test)
print("Tính khả thi:", is_able)
print("Kết quả:")
print(arrangement)

assert is_able, \
    "Kết quả trả về không đúng"

count = dict()
for i, j in arrangement:
    count.setdefault(i, 0)
    count[i] += 1
    assert count[i] <= k, \
      "Kết quả trả về không đúng"

print("== Test 1: thành công")

print()

print("== Test 2")

n = 5
k = 1
friends = [
    (0, 1), (0, 2),
    (1, 2), (1, 3), (1, 4),
    (2, 3), (2, 4),
    (3, 4),
]
test = (n, k, friends)
is_able, arrangement = party_arrange_sol(*test)
print("Tính khả thi:", is_able)
print("Kết quả:")
print(arrangement)

assert not is_able, \
    "Kết quả trả về không đúng"

count = dict()
for i, j in arrangement:
    count.setdefault(i, 0)
    count[i] += 1
    assert count[i] <= k, \
      "Kết quả trả về không đúng"

print("== Test 2: thành công")

== Test 1
Tính khả thi: True
Kết quả:
[(0, 1), (0, 2), (2, 1), (3, 1), (1, 4), (3, 2), (2, 4), (4, 3)]
== Test 1: thành công

== Test 2
Tính khả thi: False
Kết quả:
[(0, 1), (1, 3), (2, 3), (4, 2), (3, 4)]
== Test 2: thành công

def schedule(p, h, P):
    nt = len(p)
    n = (nt + 1) ** 3

    c = np.ones(n)

    A_eq = np.zeros((nt, n))
    for ii in range(nt):
        ai = np.zeros((nt + 1, nt + 1, nt + 1))
        for i in range(nt + 1):
            for j in range(nt + 1):
                for k in range(nt + 1):
                    if i == (ii + 1) or j == (ii + 1) or k == (ii + 1):
                        ai[i, j, k] = 1
        A_eq[ii] = ai.reshape(-1)
    b_eq = h.copy()

    l = np.zeros(n)

    u = np.full((nt + 1, nt + 1, nt + 1), -1)

    for i in range(1, nt + 1):
        for j in range(1, nt + 1):
            for k in range(1, nt + 1):
                if i == j or j == k or i == k:
                    u[i, j, k] = 0

    p_aux = p.copy()
    p_aux.insert(0, 0)
    for i in range(nt + 1):
        for j in range(nt + 1):
            for k in range(nt + 1):
                if p_aux[i] + p_aux[j] + p_aux[k] > P:
                    u[i, j, k] = 0

    u = u.reshape(-1)

    bounds = [
        (
            0,
            None if u[i] == -1 else u[i]
        )
        for i in range(n)
    ]

    result = linprog(
        c=c,
        A_eq=A_eq,
        b_eq=b_eq,
        bounds=bounds,
    )

    return result.fun, result.x

p = [10, 20, 60, 80, 90]
h = [8.5, 9, 4, 3.5, 2]
P = 100
best, _ = schedule(p, h, P)
print("Thời gian ngắn nhất:", best)

Thời gian ngắn nhất: 11.5

def schedule_interpret(p, h, P):
    nt = len(p)
    n = (nt + 1) ** 3

    best, x = schedule(p, h, P)

    sched = []
    x = x.reshape(nt + 1, nt + 1, nt + 1)
    for i in range(nt, -1, -1):
        for j in range(nt, -1, -1):
            for k in range(nt, -1, -1):
                if x[i, j, k] > 0:
                    sched.append([x[i, j, k], i, j, k])

    print(f'Thời gian tối thiểu: {best} giờ')
    for t, *tasks in sched:
        tasks = [
            i
            for i in tasks
            if i != 0
        ]
        print(f'Trong {t} giờ, làm {tasks}')

p = [10, 20, 60, 80, 90]
h = [8.5, 9, 4, 3.5, 2]
P = 100
schedule_interpret(p, h, P)

Thời gian tối thiểu: 11.5 giờ
Trong 4.0 giờ, làm [1, 2, 3]
Trong 3.0 giờ, làm [2, 4]
Trong 2.0 giờ, làm [1, 5]
Trong 0.5 giờ, làm [1, 4]
Trong 2.0 giờ, làm [1, 2]

def pima_assign(limit, scores):
    n, m = scores.shape

    c = - np.array([
        scores[i, j]
        for j in range(m)
        for i in range(n)
    ])

    # each project has limit mentees
    A1 = np.array([
        [
            1 if k == j else 0
            for k in range(m)
            for i in range(n)
        ]
        for j in range(m)
    ])
    bl1 = np.array([
        0
        for j in range(m)
    ])
    bu1 = np.array([
        limit
        for j in range(m)
    ])

    # each mentee has 1 project
    A2 = np.array([
        [
            1 if k == i else 0
            for j in range(m)
            for k in range(n)
        ]
        for i in range(n)
    ])
    bl2 = np.array([
        1
        for i in range(n)
    ])
    bu2 = np.array([
        1
        for i in range(n)
    ])

    A = np.vstack([
        A1,
        A2,
    ])
    bl = np.concatenate([
        bl1,
        bl2,
    ])
    bu = np.concatenate([
        bu1,
        bu2,
    ])

    l = np.array([
        0
        for j in range(m)
        for i in range(n)
    ])
    u = np.array([
        1
        for j in range(m)
        for i in range(n)
    ])

    constraints = so.LinearConstraint(A, bl, bu)
    bounds = so.Bounds(l, u, keep_feasible=True)
    integrality = np.ones_like(c)

    res = so.milp(c=c, constraints=constraints, bounds=bounds, integrality=integrality)
    return res

import io
import pandas as pd

limit = 4
df_scores = pd.read_csv(io.StringIO('''
1,1,3,1,2,1
1,3,1,3,2,2
3,1,2,3,0,2
1,3,0,3,2,0
2,3,3,2,1,2
3,1,2,2,2,1
3,2,2,3,1,1
1,3,0,1,3,2
1,3,1,2,2,1
1,1,1,3,2,2
1,3,3,2,1,1
1,3,0,1,1,1
0,1,3,2,2,3
1,1,2,2,2,2
2,2,2,3,2,2
2,3,2,2,2,3
2,1,3,3,2,1
3,1,2,2,3,3
2,2,3,3,2,2
3,3,3,2,2,3
3,2,2,1,0,2
1,2,2,3,3,1
2,2,3,3,3,2
3,2,2,2,2,2
'''), header=None)
scores = df_scores.to_numpy()

res = pima_assign(limit, scores)

n, m = scores.shape
a = dict()
for j in range(m):
  print(f'==> Dự án {j + 1} <==')
  for i in range(n):
    if res.x[j * n + i] == 1.0:
      print(
          f'Trại sinh {i}: '
          + ' '.join([
              f'({x})' if k == j else str(x)
              for k, x in enumerate(df_scores.iloc[i])
          ]),
        )
      a[i] = j
  print()

==> Dự án 1 <==
Trại sinh 2: (3) 1 2 3 0 2
Trại sinh 5: (3) 1 2 2 2 1
Trại sinh 20: (3) 2 2 1 0 2
Trại sinh 23: (3) 2 2 2 2 2

==> Dự án 2 <==
Trại sinh 1: 1 (3) 1 3 2 2
Trại sinh 3: 1 (3) 0 3 2 0
Trại sinh 8: 1 (3) 1 2 2 1
Trại sinh 11: 1 (3) 0 1 1 1

==> Dự án 3 <==
Trại sinh 0: 1 1 (3) 1 2 1
Trại sinh 4: 2 3 (3) 2 1 2
Trại sinh 10: 1 3 (3) 2 1 1
Trại sinh 18: 2 2 (3) 3 2 2

==> Dự án 4 <==
Trại sinh 6: 3 2 2 (3) 1 1
Trại sinh 9: 1 1 1 (3) 2 2
Trại sinh 14: 2 2 2 (3) 2 2
Trại sinh 16: 2 1 3 (3) 2 1

==> Dự án 5 <==
Trại sinh 7: 1 3 0 1 (3) 2
Trại sinh 13: 1 1 2 2 (2) 2
Trại sinh 21: 1 2 2 3 (3) 1
Trại sinh 22: 2 2 3 3 (3) 2

==> Dự án 6 <==
Trại sinh 12: 0 1 3 2 2 (3)
Trại sinh 15: 2 3 2 2 2 (3)
Trại sinh 17: 3 1 2 2 3 (3)
Trại sinh 19: 3 3 3 2 2 (3)

def pima_assign_ext1(limit, scores, sex):
    n, m = scores.shape

    c = - np.array([
        scores[i, j]
        for j in range(m)
        for i in range(n)
    ])

    # each project has limit mentees
    A1 = np.array([
        [
            1 if k == j else 0
            for k in range(m)
            for i in range(n)
        ]
        for j in range(m)
    ])
    bl1 = np.array([
        0
        for j in range(m)
    ])
    bu1 = np.array([
        limit
        for j in range(m)
    ])

    # each mentee has 1 project
    A2 = np.array([
        [
            1 if k == i else 0
            for j in range(m)
            for k in range(n)
        ]
        for i in range(n)
    ])
    bl2 = np.array([
        1
        for i in range(n)
    ])
    bu2 = np.array([
        1
        for i in range(n)
    ])

    # each team has at least 1 and at most 2 female
    A3 = np.array([
        [
            sex[i] == 'Nữ'
            if k == j else 0
            for k in range(m)
            for i in range(n)
        ]
        for j in range(m)
    ])
    bl3 = np.array([
        1
        for j in range(m)
    ])
    bu3 = np.array([
        2
        for j in range(m)
    ])

    A = np.vstack([
        A1,
        A2,
        A3,
    ])
    bl = np.concatenate([
        bl1,
        bl2,
        bl3,
    ])
    bu = np.concatenate([
        bu1,
        bu2,
        bu3,
    ])

    l = np.array([
        0
        for j in range(m)
        for i in range(n)
    ])
    u = np.array([
        1
        for j in range(m)
        for i in range(n)
    ])

    constraints = so.LinearConstraint(A, bl, bu)
    bounds = so.Bounds(l, u, keep_feasible=True)
    integrality = np.ones_like(c)

    res = so.milp(c=c, constraints=constraints, bounds=bounds, integrality=integrality)
    return res

import io
import pandas as pd

limit = 4

df_scores = pd.read_csv(io.StringIO('''
1,1,3,1,2,1
1,3,1,3,2,2
3,1,2,3,0,2
1,3,0,3,2,0
2,3,3,2,1,2
3,1,2,2,2,1
3,2,2,3,1,1
1,3,0,1,3,2
1,3,1,2,2,1
1,1,1,3,2,2
1,3,3,2,1,1
1,3,0,1,1,1
0,1,3,2,2,3
1,1,2,2,2,2
2,2,2,3,2,2
2,3,2,2,2,3
2,1,3,3,2,1
3,1,2,2,3,3
2,2,3,3,2,2
3,3,3,2,2,3
3,2,2,1,0,2
1,2,2,3,3,1
2,2,3,3,3,2
3,2,2,2,2,2
'''), header=None)
scores = df_scores.to_numpy()

df_sex = pd.read_csv(io.StringIO('''
Nữ
Nữ
Nam
Nam
Nữ
Nữ
Nam
Nữ
Nam
Nữ
Nữ
Nam
Nam
Nữ
Nam
Nam
Nam
Nữ
Nam
Nam
Nữ
Nam
Nam
Nam
'''), header=None)
sex = df_sex[0].tolist()

res = pima_assign_ext1(limit, scores, sex)

n, m = scores.shape
a = dict()
for j in range(m):
  print(f'==> Dự án {j + 1} <==')
  for i in range(n):
    if res.x[j * n + i] == 1.0:
      print(
          f'Trại sinh {i}: '
          + ' '.join([
              f'({x})' if k == j else str(x)
              for k, x in enumerate(df_scores.iloc[i])
          ]),
        )
      a[i] = j
  print()

==> Dự án 1 <==
Trại sinh 2: (3) 1 2 3 0 2
Trại sinh 5: (3) 1 2 2 2 1
Trại sinh 20: (3) 2 2 1 0 2
Trại sinh 23: (3) 2 2 2 2 2

==> Dự án 2 <==
Trại sinh 3: 1 (3) 0 3 2 0
Trại sinh 8: 1 (3) 1 2 2 1
Trại sinh 10: 1 (3) 3 2 1 1
Trại sinh 11: 1 (3) 0 1 1 1

==> Dự án 3 <==
Trại sinh 0: 1 1 (3) 1 2 1
Trại sinh 4: 2 3 (3) 2 1 2
Trại sinh 16: 2 1 (3) 3 2 1
Trại sinh 18: 2 2 (3) 3 2 2

==> Dự án 4 <==
Trại sinh 1: 1 3 1 (3) 2 2
Trại sinh 6: 3 2 2 (3) 1 1
Trại sinh 9: 1 1 1 (3) 2 2
Trại sinh 14: 2 2 2 (3) 2 2

==> Dự án 5 <==
Trại sinh 7: 1 3 0 1 (3) 2
Trại sinh 17: 3 1 2 2 (3) 3
Trại sinh 21: 1 2 2 3 (3) 1
Trại sinh 22: 2 2 3 3 (3) 2

==> Dự án 6 <==
Trại sinh 12: 0 1 3 2 2 (3)
Trại sinh 13: 1 1 2 2 2 (2)
Trại sinh 15: 2 3 2 2 2 (3)
Trại sinh 19: 3 3 3 2 2 (3)

def pima_assign_ext2(limit, scores, sex, black_list):
    n, m = scores.shape

    c = - np.array([
        scores[i, j]
        for j in range(m)
        for i in range(n)
    ])

    # each project has limit mentees
    A1 = np.array([
        [
            1 if k == j else 0
            for k in range(m)
            for i in range(n)
        ]
        for j in range(m)
    ])
    bl1 = np.array([
        0
        for j in range(m)
    ])
    bu1 = np.array([
        limit
        for j in range(m)
    ])

    # each mentee has 1 project
    A2 = np.array([
        [
            1 if k == i else 0
            for j in range(m)
            for k in range(n)
        ]
        for i in range(n)
    ])
    bl2 = np.array([
        1
        for i in range(n)
    ])
    bu2 = np.array([
        1
        for i in range(n)
    ])

    # each team has at least 1 and at most 2 female
    A3 = np.array([
        [
            sex[i] == 'Nữ'
            if k == j else 0
            for k in range(m)
            for i in range(n)
        ]
        for j in range(m)
    ])
    bl3 = np.array([
        1
        for j in range(m)
    ])
    bu3 = np.array([
        2
        for j in range(m)
    ])

    A = np.vstack([
        A1,
        A2,
        A3,
    ])
    bl = np.concatenate([
        bl1,
        bl2,
        bl3,
    ])
    bu = np.concatenate([
        bu1,
        bu2,
        bu3,
    ])

    l = np.array([
        0
        for j in range(m)
        for i in range(n)
    ])
    u = np.array([
        0
        if j in black_list.get(i, [])
        else 1
        for j in range(m)
        for i in range(n)
    ])

    constraints = so.LinearConstraint(A, bl, bu)
    bounds = so.Bounds(l, u, keep_feasible=True)
    integrality = np.ones_like(c)

    res = so.milp(c=c, constraints=constraints, bounds=bounds, integrality=integrality)
    return res

import io
import pandas as pd

limit = 4

df_scores = pd.read_csv(io.StringIO('''
1,1,3,1,2,1
1,3,1,3,2,2
3,1,2,3,0,2
1,3,0,3,2,0
2,3,3,2,1,2
3,1,2,2,2,1
3,2,2,3,1,1
1,3,0,1,3,2
1,3,1,2,2,1
1,1,1,3,2,2
1,3,3,2,1,1
1,3,0,1,1,1
0,1,3,2,2,3
1,1,2,2,2,2
2,2,2,3,2,2
2,3,2,2,2,3
2,1,3,3,2,1
3,1,2,2,3,3
2,2,3,3,2,2
3,3,3,2,2,3
3,2,2,1,0,2
1,2,2,3,3,1
2,2,3,3,3,2
3,2,2,2,2,2
'''), header=None)
scores = df_scores.to_numpy()

pd.read_csv(io.StringIO('''
Nữ
Nữ
Nam
Nam
Nữ
Nữ
Nam
Nữ
Nam
Nữ
Nữ
Nam
Nam
Nữ
Nam
Nam
Nam
Nữ
Nam
Nam
Nữ
Nam
Nam
Nam
'''), header=None)
sex = df_sex[0].tolist()

black_list = {
    i: {
        j
        for j in range(m)
        if scores[i, j] <= 1 # lọc tất cả điểm <= 1
    }
    for i in range(n)
}
black_list_update = {
    2: [0, 5],
    14: [0, 1, 2, 4, 5],
    17: [4, 5],
    18: [0, 1, 3, 4],
}

res = pima_assign_ext2(limit, scores, sex, black_list)

n, m = scores.shape
a = dict()
for j in range(m):
  print(f'==> Dự án {j + 1} <==')
  for i in range(n):
    if res.x[j * n + i] == 1.0:
      print(
          f'Trại sinh {i}: '
          + ' '.join([
              f'({x})' if k == j else str(x)
              for k, x in enumerate(df_scores.iloc[i])
          ]),
        )
      a[i] = j
  print()

==> Dự án 1 <==
Trại sinh 5: (3) 1 2 2 2 1
Trại sinh 6: (3) 2 2 3 1 1
Trại sinh 20: (3) 2 2 1 0 2
Trại sinh 23: (3) 2 2 2 2 2

==> Dự án 2 <==
Trại sinh 3: 1 (3) 0 3 2 0
Trại sinh 8: 1 (3) 1 2 2 1
Trại sinh 10: 1 (3) 3 2 1 1
Trại sinh 11: 1 (3) 0 1 1 1

==> Dự án 3 <==
Trại sinh 0: 1 1 (3) 1 2 1
Trại sinh 4: 2 3 (3) 2 1 2
Trại sinh 16: 2 1 (3) 3 2 1
Trại sinh 18: 2 2 (3) 3 2 2

==> Dự án 4 <==
Trại sinh 1: 1 3 1 (3) 2 2
Trại sinh 2: 3 1 2 (3) 0 2
Trại sinh 9: 1 1 1 (3) 2 2
Trại sinh 14: 2 2 2 (3) 2 2

==> Dự án 5 <==
Trại sinh 7: 1 3 0 1 (3) 2
Trại sinh 13: 1 1 2 2 (2) 2
Trại sinh 21: 1 2 2 3 (3) 1
Trại sinh 22: 2 2 3 3 (3) 2

==> Dự án 6 <==
Trại sinh 12: 0 1 3 2 2 (3)
Trại sinh 15: 2 3 2 2 2 (3)
Trại sinh 17: 3 1 2 2 3 (3)
Trại sinh 19: 3 3 3 2 2 (3)

1. Sử dụng scipy và ví dụ¶

1.1. Ví dụ¶

1.2. Tham số đầu vào¶

1.3. Kết quả trả về¶

2. Bài tập¶

Bài tập 1: Luồng cực đại¶

Câu hỏi 0¶

Câu hỏi 1¶

Đáp án Câu hỏi 1¶

Câu hỏi 2¶

Đáp án Câu hỏi 2¶

Câu hỏi 3¶

Đáp án Câu hỏi 3¶

Bài tập 2: Lập lịch¶

Câu hỏi 0¶

Câu hỏi 1¶

Đáp án Câu hỏi 1¶

Câu hỏi 2¶

Đáp án Câu hỏi 2¶

Bài tập 3: Quy hoạch tuyến tính nguyên và bài toán xếp nhóm¶

Câu hỏi 0¶

Câu hỏi 1¶

Đáp án Câu hỏi 1¶

Câu hỏi 2¶

Đáp án Câu hỏi 2¶

Câu hỏi 3¶

Đáp án Câu hỏi 3¶

Câu hỏi 4+ (tự do)¶