Materi
Teorema dasar program linear, sebagaimana ditulis Sekhon dan Bloom (§3.1), menyatakan bahwa nilai maksimum atau minimum fungsi tujuan selalu tercapai di titik sudut daerah layak. Akibatnya, pencarian di antara tak hingga banyak titik layak cukup diganti dengan memeriksa beberapa titik sudut: hitung nilai tujuan di setiap titik sudut, lalu ambil yang terbesar untuk maksimasi atau yang terkecil untuk minimasi.
Buku yang sama menjelaskan gambaran geometrisnya dengan garis laba: garis 25a + 30b = P digeser sejajar menjauhi titik asal, dan titik sudut terakhir yang masih disentuh garis itu adalah titik optimum maksimasi. Coffelt dan Hendrickson (§5.2) menambahkan bahwa daerah layak program linear selalu cembung, sehingga optimum yang ditemukan bersifat global, bukan hanya lokal.
Minimasi dengan kendala ≥ sering menghasilkan daerah layak yang tidak tertutup ke arah kanan atas. Sekhon dan Bloom (§3.2) mencatat bahwa minimasi di daerah seperti itu tetap bisa punya optimum di titik sudut, tetapi maksimasi di daerah yang sama tidak punya solusi optimum: selalu ada titik lain dengan nilai tujuan lebih besar.
# toko roti: titik sudut dari pelajaran sebelumnya
sudut = [(0, 0), (0, 10), (8, 6), (12, 0)]
for a, b in sudut:
print((a, b), 25*a + 30*b)
# (8, 6) memberi 380, nilai terbesar -> optimum