Jabarkan Dualitas dari Program linear

Setiap masalah program linear, yang juga dikenal dengan masalah primal, dapat diubah menjadi sebuah masalah dual. Masalah dual juga merupakan sebuah program linear, dan solusi masalah ini memberikan sebuah batas atas untuk nilai optimal dari masalah primal. Untuk mendapatkan dual dari masalah primal, ada cara sistematis yang perlu dilakukan:

Setiap variabel pada program linear primal akan menjadi kendala di program linear dual.

Setiap konstrain pada program linear primal akan menjadi konstrain di program linear dual.

Arah fungsi objektif akan berbalik—masalah memaksimumkan di primal akan menjadi masalah meminimumkan di dual, dan sebaliknya.

Dalam bentuk matriks, hubungan masalah primal dengan masalah dual dapat ditunjukkan dengan:

Maksimumkan  dengan kendala  dan ; akan memiliki masalah dual simetrik  Minimimumkan  dengan kendala  dan .

Maksimumkan  dengan kendala ; akan memiliki masalah dual asimetrik  Minimumkan   dengan kendala  dan .

Ada dua ide mendasar pada teori dualitas. Ide pertama adalah fakta bahwa (untuk kasus dual simetrik) dual dari masalah dual suatu program linear, adalah masalah primal asal dari program linear tersebut. Selain itu, setiap solusi feasibel dari program linear akan memberikan batas untuk nilai optimal dari fungsi objektif masalah dualnya. Teorema dualitas lemah menyatakan bahwa nilai fungsi objektif dari masalah dual pada setiap solusi feasibel, akan memberikan batas pada nilai fungsi objektif masalah primal pada setiap solusi feasibelnya. Jenis batas (batas atas atau batas bawah) yang terjadi bergantung pada jenis optimisasi yang dikerjakan (memaksimumkan atau meminimumkan). Teorema dualitas kuat menyatakan jika masalah primal memiliki sebuah solusi optimal , maka masalah dual juga memiliki sebuah solusi optimal , dan keduanya terikat oleh hubungan .

Bentuk kendala dari program linear juga dapat tidak terbatas (unbounded) atau tidak feasibel (infeasible). Teorema dualitas lemah menunjukkan bahwa jika masalah primal tidak terbatas maka masalah dual yang terbentuk akan tidak feasibel. Dan sebaliknya, jika masalah dual tidak terbatas maka masalah primalnya akan tidak feasibel. Namun, ada kasus kedua jenis masalah (primal dan dual) adalah masalah yang tidak feasibel.

Dualitas masalah pengepakan dan penutupan

Masalah pengepakan (packing) adalah kelas masalah optimisasi yang mencari cara menyusun (mengepak) objek-objek ke dalam sebuah kontainer. Sedangkan, masalah penutupan (covering) membahas apakah suatu kombinasi struktur "menutupi" sebuah objek, atau seberapa besar ukuran struktur yang diperlukan agar dapat melakukan hal tersebut. Masalah program linear terkait pengepakan dan penutupan sering muncul sebagai "relaksasi" dari sebuah masalah kombinatorial.

Masalah program linear penutupan memiliki bentuk: