Данная лекция раскрывает ряд вопросов, посвященных линейному программированию как одному из разделов математического программи

Форма записи задачи ЛП. Задачу линейного программирования можно сформулировать так:

(3.11)

при условиях

(3.12)

(3.13)

Ограничения (3.13) называют условиями неотрицательности переменных. В рассматриваемом случае все ограничения имеют вид неравенств.
Иногда они могут быть смешанными, то есть неравенства и равенства:

(3.14)

Если все ограничения задачи ЛП имеют вид строгих равенств

(3.15)

то данная форма записи называется канонической.
В матричной форме задача ЛП записывается следующим образом:

(3.16)

при ограничениях

(3.17)

где А - матрица ограничений размером (m x n); b^(m*1) - вектор-столбец свободных членов; x^(n*1) - вектор переменных; с=[c1, c2,.,cn]-вектор (строка) коэффициентов целевой функции.
В векторной форме ограничения (3.14) записывают так:

(3.18)

Допустимым множеством решений задачи (3.11)-(3.13) называется множество R(х) всех векторов x, удовлетворяющих условиям (3.12) и (3.13).
Множество R(х) представляет собой выпуклое многогранное множество или выпуклый многогранник.
Решение x₀ называется оптимальным, если оно удовлетворяет условию

для всех .
Поскольку поиск эквивалентен поиску , то задачу ЛП всегда можно свести к эквивалентной задаче максимизации.

4. Решение задач линейного программирования симплекс–методом

Симплекс-метод, известный также под названием метода последовательного улучшения плана, впервые разработал Г.Данциг в 1947 г. Этот метод позволяет переходить от одного допустимого базисного решения к другому, причем так, что значения целевой функции непрерывно возрастают. В результате оптимальное решение находят за конечное число шагов.
Алгоритмы симплекса-метода позволяют также установить, является ли задача ЛП разрешимой.
Запишем ограничения задачи ЛП в таком виде:
A₁x₁ + A₂x₂ + ... + A_nx_n + A_n+1x_n+1 + ... + A_n+mx_n+m = A₀.
Пусть A₁,...,A_m - множество линейно независимых векторов.
Тогда уравнение

(4.1)

определяет базисное решение ,
Предположим, что это решение допустимо, то есть . Базис {A₁,.,A_m} образует m-мерное пространство, а потому каждый из векторов A_m+1,.,A_m+n единственным образом выражается через этот базис. Если A_r не входит в базис, то

(4.2)

где x_ir - соответствующие коэффициенты (i = 1, 2, ..., m).
Предположим, что хотя бы одна из величин x_ir больше нуля.
Решение уравнения

(4.3)

обозначим как
Тогда, очевидно:

(4.4)

Умножив уравнение (4.2) на x_r и вычтя полученное уравнение из уравнения (4.1), получим

(4.5)

Сравнив уравнения (4.5) и (4.4), находим связь нового решения со старым базисным решением :

(4.6)

Решение (4.6), во-первых, не будет базисным, так как содержит m + 1 переменную, а во-вторых, будет допустимым не для всех значений x_r.
Чтобы новое решение оставалось допустимым, нужно выбрать значение x_r таким, чтобы ни одна из величин не стала меньше нуля. Следовательно, максимальное значение переменной x_r определяется соотношением

(4.7)

где x_ir > 0.
Чтобы сделать новое допустимое решение базисным, нужно одну переменную x_i вывести из базисного решения, а соответствующий вектор из базиса. В этом случае новый базис будет содержать также m векторов.
Для этого выбираем значения в соответствии с (4.7). Тогда новое базисное решение имеет вид

а новый базис - (A₁, A₂, ., A_j-1, A_j+1, ., A_m, A_r).
Такой переход от одного базиса к другому позволяет находить решения почти всех задач ЛП. Определив все крайние точки, можно вычислить значения целевой функции и найти оптимальное решение. Однако для больших значений m и n это практически невозможно. Поэтому для перехода от текущего решения к новому допустимому базисному решению, которому отвечает большее значение целевой функции, используют соответствующий критерий (симплекс-разность).
Новому ДБР соответствует следующее значение целевой функции

(4.8)

где z₀ - значение целевой функции для начального ДБР;
с_r-с₁x_1r - с₂x_2r - ... - с_mx_mr - симплекс-разность для переменной х_r.
Симплекс-разность вычисляют для каждой переменной, не входящей в базисное решение, и выбирают такую небазисную переменную х_r, для которой симплекс-разность положительна и максимальна.
Таким образом, алгоритм симплекс-метода состоит из следующих этапов:

1. 
   находят начальный базис и связанное с ним допустимое базисное решение;
   
2. 
   вычисляют симплекс-разность для каждой переменной, не входящей в базисное решение;
   
3. 
   вводят в базис наиболее 'выгодную' переменную с максимальной положительной симплекс-разностью; ее значение определяют из соотношения
   

для всех x_ir > 0;

4. 
   выводят из базисного решения переменную x_j, соответствующую
   

а из базиса - вектор A_j;

5. 
   переходят к этапу 2 новой итерации.
   

Этапы 2 - 4 повторяют до тех пор, пока симплекс-разности для всех переменных, не входящих в базис, не станут отрицательными.
Это и есть признак оптимальности текущего базисного решения.