Постановка задачи линейного программирования и двойственная задача линейного программирования.
    Линейное программирование является составной частью раздела математики, который изучает методы нахождения условного экстремума функции многих переменных и называется математическим программированием. В классическом математическом анализе рассматривается задача отыскания условного экстремума функции. Тем не менее, время показало, что для многих задач, возникающих под влиянием запросов практики, классические методы недостаточны. В связи с развитием техники, ростом промышленного производства и с появлением ЭВМ все большую роль начали играть задачи отыскания оптимальных решений в различных сферах человеческой деятельности. Основным инструментом при решении этих задач стало математическое моделирование - формальное описание изучаемого явления и исследование с помощью математического аппарата.
    Искусство математического моделирования состоит в том, чтобы учесть как можно больше факторов по возможности простыми средствами. Именно в силу этого процесс моделирования часто носит итеративный характер. На первой стадии строится относительно простая модель и проводится ее исследование, позволяющее понять, какие из существенных свойств изучаемого объекта не улавливаются данной формальной схемой. Затем происходит уточнение, усложнение модели.
    В большинстве случаев первой степенью приближения к реальности является модель, в которой все зависимости между переменными, характеризующими состояние объекта, предполагаются линейными. Здесь имеется полная аналогия с тем, как весьма важна и зачастую исчерпывающая информация о поведении произвольной функции получается на основе изучения ее производной - происходит замена этой функции в окрестности каждой точки линейной зависимостью. Значительное количество экономических, технических и других процессов достаточно хорошо и полно описывается линейными моделями.
    
    Основные формы задачи ЛП.
    Различают три основные формы задач линейного программирование в зависимости от наличия ограничений разного типа.
    Стандартная задача ЛП.
     или, в матричной записи,
     где - матрица коэффициентов. Вектор называется вектором коэффициентов линейной формы, - вектором ограничений.
    Стандартная задача важна ввиду наличия большого числа прикладных моделей, сводящихся наиболее естественным образом к этому классу задач ЛП.
    Каноническая задача ЛП.
     или, в матричной записи,
    
    Основные вычислительные схемы решения задач ЛП разработаны именно для канонической задачи.
    Общая задача ЛП.
    В этой задачи часть ограничений носит характер неравенств, а часть является уравнениями. Кроме того, не на все переменные наложено условие неотрицательности:
    
    Здесь . Ясно, что стандартная задача получается как частный случай общей при ; каноническая - при .
    Все три перечисленные задачи эквивалентны в том смысле, что каждую из них можно простыми преобразованиями привести к любой из двух остальных.
    При изучении задач ЛП сложилась определенная терминалогия. ............