לכל בעית תכנות לינארי קיימת בעיה הקשורה בה ונבנית ממנה , וזוהי הבעיה הדואלית . הבעיה המקורית תיקרא הבעיה הפרימאלית . נתונה הבעיה הפרימאלית הבאה : Max { Z « C x + C x + ... + C x } , , 2 2 n n nnn האילוצים : m n - 1 •• nV 12 V 2 n n < 2 •• 21 V 22 V a a x + a x < b m > V m 2 2 mn n - m x . > 0 ( j = 1 , 2 ,..., n ) n 7 y 1 n הדואלית לבעיה פרימאליח זו מתקבלת כך , טלכל אילוץ בבעיה הפרימאלית מתאימים משתנה דואלי y . ( חז - 1 , 2 ,..., י ו . ( הבעיה הדואלית לבעית מקסימום היא בעית מינימום על סכום המשתנים הדואליים , שמחיריהם הם האילוצים המתאימים בבעיה הפרימאלית . מערכת האילוצים נבנית ממטריצה הפוכה של מטריצת מקדמי הבעיה הפרימאלית : האילוצים משנים את כיוונם וצידם הימני של האילוצים הופכים למחירי הבעיה הפרימאלית . דהיינו , הבעיה הדואלית לבעיה הנתונה היא :
אל הספר