В двойственной задаче имеется по одной нормальной случайной переменной для каждого ограничения в виде неравенства основ­ной задачи, по одной свободной переменной для каждого огра­ничения в виде равенства, по одному ограничению в виде нера­венства для каждой нормальной случайной переменной и по одному ограничению в виде равенства для каждой свободной переменной. Между основной и двойственной задачами могут существо­вать самые различные соответствия. Для обсуждаемой проблемы важное значение имеют соответствия двух типов. Во-первых, легко показать, что задача, двойственная по отношению к двойственной задаче, есть основная задача. Во-вторых, можно показать, что если основная (двойственная) задача имеет опти­мальное решение, то двойственная (основная) задача также имеет оптимальное решение. Таким образом, двойственность позволяет дать две формули­ровки любой задачи линейной оптимизации. Часто более выгод­но решать задачу в одной формулировке и менее выгодно — в другой. В этом мы очень скоро убедимся. Задачи линейного программирования решают с помощью алгоритма, называемого симплексным. Большая часть подробного описания этого алгоритма в данном контексте не представляет интереса. Следует только отметить, что алгоритм может дать один из трех взаимно исключающих результатов. Первый результат — оптимальное решение (если задача имеет конечное оптимальное решение); второй результат — указание на то, что задача решаема, но оптимальное решение не имеет границ; третий результат—указание на то, что задача нерешае-ма. Задача имеет решение, если при некотором (не обязательно оптимальном) выборе переменных можно одновременно удов­летворить условиям всех ограничений. Задача не имеет решения, если при любом выборе переменных невозможно одновременно удовлетворить условиям всех ограничений. В процессе прибли­жения к искомому результату в задачу вводятся дополнитель­ные переменные, называемые произвольными.