Materi
Pada program linear dua variabel, setiap kendala ax + by ≤ c membagi bidang menjadi dua bagian dengan garis batas ax + by = c. Sekhon dan Bloom (§3.1–3.2) memilih sisi yang benar dengan titik uji yang tidak terletak di garis: masukkan koordinatnya ke pertidaksamaan, dan bila hasilnya benar, sisi yang memuat titik itu termasuk daerah layak. Titik (0, 0) paling mudah dipakai selama tidak berada di garis batas. Irisan semua sisi yang terpilih adalah daerah layak.
Titik sudut (critical point) adalah titik tempat dua garis batas berpotongan dan yang tetap memenuhi semua kendala lain. Koordinatnya diperoleh dengan menyelesaikan sistem dua persamaan linear, misalnya dengan np.linalg.solve. Perpotongan yang melanggar salah satu kendala bukan titik sudut, karena letaknya di luar daerah layak.
Untuk mencari semua titik sudut secara sistematis, pasangkan setiap dua kendala dengan itertools.combinations, selesaikan persamaannya, lalu simpan hanya perpotongan yang layak. Kendala nonnegatif ikut dipasangkan dan ditulis dalam bentuk yang sama: x ≥ 0 menjadi −x + 0y ≤ 0.
import numpy as np
# oven: 3a + 2b = 36 dan tepung: a + 2b = 20
A = np.array([[3, 2], [1, 2]])
print(np.linalg.solve(A, [36, 20])) # [8. 6.]
print(np.linalg.det(A)) # sekitar 4, bukan nol -> garisnya berpotongan