Fungsi obyektif suatu persoalan linear kemungkinan akan

Fungsi obyektif persoalan linear kemungkinan akan optimum pada titik sudut (titik ekstrem) dari daerah yang layak.

Pembahasan

Dalam pemrograman linear, fungsi obyektif adalah fungsi yang ingin kita maksimalkan atau minimalkan (misalnya, keuntungan atau biaya). Batasan-batasan dalam persoalan linear membentuk daerah yang layak (feasible region), yang merupakan himpunan semua solusi yang memenuhi semua batasan. Karena batasan-batasan tersebut linear, daerah yang layak akan berbentuk polihedron cembung (convex polyhedron).

Menurut Teorema Titik Ekstrem (atau Teorema Dasar Pemrograman Linear), jika suatu persoalan pemrograman linear memiliki solusi optimum (baik maksimum maupun minimum), maka solusi optimum tersebut pasti tercapai pada salah satu titik sudut (vertex) dari daerah yang layak. Titik sudut adalah tempat bertemunya dua atau lebih garis batasan.

Oleh karena itu, fungsi obyektif suatu persoalan linear kemungkinan akan optimum pada salah satu titik sudut (titik ekstrem) dari daerah yang layak.