Основная задача линейного программирования
Линейное программирование — это раздел прикладной математики о методах исследования и отыскания наибольших или наименьших значений линейной функции, на неизвестные которой наложены линейные ограничения.
В общем виде задача линейного программирования может быть сформулирована следующим образом.
система линейных ограничений
и условия неотрицательности переменных
где aij, bi и cj — заданные постоянные величины.
Задача: найти такие значения x1, x2, xn, удовлетворяющие системе ограничений (3.2), условиям неотрицательности (3.3) и обеспечивающие минимум (максимум) линейной функции (3.1).
Задача в такой постановке называется основной задачей линейного программирования (ОЗЛП). В системе ограничений (3.2) все bi можно считать неотрицательными. Линейная функция (3.1) называется функцией цели или целевой функцией и совместно с системой ограничений образует математическую модель рассматриваемой задачи.
К задаче линейного программирования сводится большой класс задач, встречающихся в практической деятельности человека. Особенно широкое распространение линейное программирование получило в экономике, так как зависимости между величинами, встречающимися в экономических задачах, зачастую приводят к линейной функции с линейными ограничениями, наложенными на неизвестные.
В качестве примеров простейших экономических задач можно привести:
а) задача об использовании сырья при изготовлении разнородной продукции, где в роли целевой функции выступает суммарная стоимость изготовленной продукции, которую требуется максимизировать, а в качестве ограничений — имеющееся в наличии количество сырья разного типа, необходимого для изготовления продукции. Здесь x j – требуемый объем выпуска продукции j-го типа, aij – объем ресурса i-го типа, необходимого для выпуска единицы продукции j-го типа, bi –имеющийся запас ресурса i-го типа;
б) задача о разработке дневного рациона, например, при откорме животных, либо при составлении меню на предприятии питания. Цель задачи — добиться минимальных затрат на дневной рацион при условии, что количество питательных веществ каждого типа в составе применяемых видов кормов (продуктов) должно быть не менее заданной величины. Здесь x j – количество продуктов j-го типа в составе меню, aij – количество питательного вещества i-го типа в единице продукта j-го типа, bi – потребный объем питательного вещества i-го типа;
Подробнее с примерами математических моделей некоторых задач линейного программирования ознакомимся в следующих разделах.
Термин «линейное программирование» появился в 1951 году в работах американских ученых Дж. Б. Данцига, Тьяллинга Купманса (Koopmans). Слово «программирование» объясняется тем, что набор искомых переменных определяет программу (план) работы некоторого экономического объекта.
Первые исследования по линейному программированию (основные задачи и приложения, критерии оптимальности, геометрическая интерпретация и экономическая трактовка задачи ЛП) были проведены в 30-е годы в Ленинградском университете (Л.В. Канторович). Наиболее интенсивно линейное программирование развивалось в 1955-1965 гг. в СССР и США, когда оно было одним из наиболее «модных» разделов прикладной математики.
Канторович Леонид Витальевич (6.01.1912-1986), академик, лауреат Государственной и Ленинской премий, Нобелевской премии в 1975 г. вместе с Купмансом.
Приведенная выше в виде линейной функции (3.1) и системы ограничений (3.2), (3.3) запись называется развернутой формой записи основной задачи линейного программирования. Эта форма может быть представлена в компактном виде: минимизировать линейную функцию Ф = cj · x j
Основная задача линейного программирования, кроме вышеприведенной развернутой (3.1¸3.3) или компактной (3.4), имеет еще несколько форм записи.
Векторная форма записи. Минимизировать линейную функцию Ф = С · Х при ограничениях A1 · x1 + A2 · x 2 + An · x n = В, X ³ 0, (3.5)
где X = (х1, х2, xn), C = (с1, c2, сn) – векторы-строки, которые состоят, соответственно, из неизвестных переменных и коэффициентов при них в целевой функции, С·Х — скалярное произведение этих векторов, а векторы
состоят, соответственно, из коэффициентов при неизвестных переменных в системе ограничений и свободных членов.
Матричная форма записи. Минимизировать линейную функцию Ф = С·Х при ограничениях A·X = В, Х ³ О, (3.6)
где А = ij> — матрица коэффициентов при неизвестных переменных в системе ограничений размерности m x n; С = (с1, с2, cn) — матрица – строка коэффициентов при неизвестных переменных в целевой функции,
Х = матрица-столбец B = — матрица-столбец, неизвестных, свободных xn переменных bm членов, в системе ограничений,
В зависимости от конкретной задачи система ограничений ОЗЛП могут быть представлены как уравнениями вида (3.2), так и неравенствами. ОЗЛП в этом случае формулируется в следующем виде:
минимизировать линейную функцию Ф = cj · x j
Если при условии, что все неизвестные переменные неотрицательны (то есть, х j ³ 0, j =1,n), система ограничений состоит лишь из одних уравнений, задача линейного программирования называется канонической, если система ограничений состоит лишь из одних неравенств, то задача называется стандартной. Если система ограничений имеет смешанный вид, то имеем дело с общейзадачей ЛП.
Любая задача ЛП может быть сведена к стандартной, канонической или общей задаче. Однако, при решении систем линейных неравенств с n неизвестными приходится сталкиваться с большими трудностями, поэтому при решении задач на практике от неравенств переходят равенствам путем введения в левые части неравенств некоторых неотрицательных величин zi ≥ 0 (либо x n+i ≥ 0), называемых дополнительными или фиктивными переменными. Знаки при этих переменных могут быть как положительными, так и отрицательными в зависимости от вида неравенства (³ или £).
достаточно добавить к левой части некоторую величину zi ³ 0 и получим
В результате получим систему линейных уравнений, содержащих n+m неизвестных: aij· x j + z i = bi, i = 1,m
Теорема 3.1. Каждому решению X* = (x*1, x*2, x*n) систем неравенств (3.7) и (3.8) соответствует единственное решение Y* = (x*1, x*2, x*n, z*1, z*m) системы уравнений (3.9) и неравенства (3.10) и, наоборот, каждому решению Y* системы уравнений (3.9) и неравенства (3.10) соответствует единственное решение Х* систем неравенств (3.7) и (3.8).
В задачах ЛП представляют интерес системы, в которых ранг матрицы системы А = ij>, (i =1, m; j = 1, n,) или, что то же самое, максимальное число независимых уравнений системы R меньше числа переменных, то есть, R < n. Будем полагать, что в системе (3.2) все m уравнений системы независимы, то есть, R = m. Тогда, соответственно, m < n.
Любые m переменных системы m линейных уравнений с n переменными (m < n) называются базисными (или основными), если определитель матрицы коэффициентов при них отличен от нуля. Тогда остальные r = n- m переменных называются свободными (или неосновными).
Выше показали, как от задачи линейного программирования с ограничениями-неравенствами можно перейти к задаче ограничениями-равенствами (ОЗЛП). Всегда возможен и обратный переход – от ОЗЛП к задаче с ограничениями-неравенствами. Для этого базисные переменные выразим через свободные, затем, исходя из условия неотрицательности базисных переменных, запишем условия неотрицательности полученных выражений, в результате чего получим систему неравенств. Если в первом случае мы увеличивали число переменных, введя дополнительные переменные, то во втором случае будем его уменьшать, устраняя базисные переменные и оставляя только свободные. Однако, при этом существенно усложняется решение задачи.
Общая и основная задачи линейного программирования.
Общая задача. Найти максимальное значение линейной целевой функции. z = c1x1+ c2x2+ … + cnxn при линейных ограничениях xj>= 0,j= 1,n= n> Определение 1.1. Совокупность чисел х = (х1, х2. хn), удовлетворяющих ограничениям (1.2), называется допустимым решением или планом. Определение 1.2. План х* =(х1 * , х2 * . хn*), при котором целевая функция (1.1) принимает свое максимальное значение, называется оптимальным.Каноническая форма. Задачу линейного программирования будем считать приведенной к каноническому виду, если 1) требуется найти максимум целевой функции; 2) система ограничений (1.2) содержи! только равенства; 3) правые части системы ограничений неотрицательны. Переход от общей формы к канонической: 1) если в задаче требуется найти минимум целевой функции, то вводим новую целевую функцию z1 = -z, тогда max z1 = -min z; 2) чтобы перейти от неравенства к равенству в системе ограничений, необходимо прибавить (вычесть) дополнительную неотрицательную переменную к левой части неравенства; 3) если в правой части системы ограничений имеются отрицательные числа, то необходимо умножить на «-1» обе части равенства, в котором в правой части стоит отрицательное число. Задачу линейного программирования в канонической форме называют основной задачей.
Свойства задач линейного программирования. Графический метод решения задач линейного программирования.
Свойства задач линейного программирования. Рассмотрим следующую основную задачу линейного программирования: z = c1x1+ c2x2+ …+cnxnmax при ограничениях 
,
Перепишем ограничения этой задачи к немирной форме: x1Р,+х2Р2+. + хnРn,(1.3) где Р1, . Рnи Р0 — k-мерные вектор-столбцы, составленные из коэффициентов при неизвестных и свободных членах системы ограничений основной задачи: 
Определение 1. План х = (x1,х2. хn) называется опорным планом основной задачи линейного программирования, если его положительные коэффициенты (хj >0) стоят при линейно независимых векторах Рj. Так как векторы Р: являются k-мерными, то из определения опорного плана следует, что число его положительных компонент не может быть больше числа К. Определение 2. Опорный план называется невырожденным, если он содержит ровно k положительных компонент, в противном случае он называется вырожденным. Свойства задач линейного программирования тесным образом связаны со свойствами выпуклых множеств. Определение 3. Пусть х(|). х(m) — произвольные точки евклидова пространства Rn . Выпуклой линейной комбинацией этих точек называется сумма: а,х(|) + . + аmх(m) , где аi; -произвольные неотрицательные числа, сумма которых равна 1. Определение 4. Множество называется выпуклым, если вместе с любыми двумя своими точками оно содержит и отрезок прямой, соединяющий эти точки. Определение 5. Точка х выпуклого множества называется угловой, если она не может быть представлена в виде выпуклой линейной комбинации каких-нибудь двух других различных точек данного множества. Сформулируем первое свойство задач ЛП. Теорема 1.1. Множество планов любой задачи линейного программирования является выпуклым (если оно не пусто). Определение 7. Непустое множество планов задачи линейного программирования называется многогранником решений, а всякая угловая точка многогранника решений — вершиной. Сформулируем второе свойство задач ЛП. Теорема 1.2. Если задача линейного программирования имеет оптимальный план, то экстремальное значение целевая функция задачи принимает в одной из вершин многогранника решений. Если экстремальное значение целевая функция принимает более чем в одной вершине, то она принимает его на ребре (грани), содержащем эти вершины. Теорема 1.3. Если система векторов Р1. Рm(
) линейно независима и такова, что х1Р1+. + хmРm=Р0, где все хj>= 0, то точка х = (х,, х2. хт,0. 0) является вершиной многогранника решений. Теорема 1.4. Если х = (х,,х2. хп) — вершина многогранника решений, то векторы Рj , соответствующие положительным хj > 0, линейно независимы.