Источник: http://www.apmath.spbu.ru/ru/education/final/question33.pdf
Формулировка задачи линейного программирования. Напомним, что математически
задача ЛП — это задача нахождения наибольшего (наименьшего) значения линейной
функции многих переменных при линейных ограничениях типа равенств (неравенств), когда
на переменные задачи есть (нет) ограничений на знак.
Аналогично можно написать общую постановку для задачи минимизации
Однако решаются такие задачи, когда они записаны в одном из специальных видов. Для
задачи максимизации имеется 4 специальных вида задачи ЛП: стандартная и каноническая
формы.
1.2. Стандартная форма задачи ЛП максимизации/
В матричном и векторном виде эта задача может быть записана так
1.3. Каноническая форма задачи ЛП максимизации:
В матричном и векторном виде эта задача может быть записана так
2. Алгебраические основы симплекс-метода
2.1. Множество допустимых решений для канонической задачи
Рассмотрим каноническую задачу ЛП максимизации
Множество допустимых решений задачи имеет вид
M = {X AX = B, X > 0}
называется многогранным и является выпуклым и замкнутым.
2.2. Понятие решения для системы линейных уравнений (СЛУ), зависящего от
множества индексов
Mножество индексов (подмножество множества номеров столбцов
матрицы) и пусть дана система линейных уравнений
Говорят, что решение СЛУ зависит от множества индексов S, если xj*Sj = 0.
2.3. Понятие базисного решения СЛУ.
Говорят, что решение СЛУ базисное, если оно зависит от такого множества
индексов S, что векторы j S
Aj - образуют столбцовый базис матрицы A.
2.4. Понятие допустимого базисного решения
Говорят, что решение СЛУ является базисным допустимым, если оно
базисное для СЛУ и X > 0, т.е. оно базисное и допустимое для задачи ЛП в канонической
форме.
2.5. Совместность и неизбыточность СЛУ
совместна и неизбыточна, если
rank(A) = rank([A, B]) = m,m < n
Если СЛУ удовлетворяет данному условию, то допустимое базисное решение существует и
совпадает с экстремальной (угловой, крайней) точкой множества допустимых решений
задачи ЛП в канонической форме.
2.6. Нахождение базисного решения
Предположим, что СЛУ находится в условиях п. 2.5.
Рассматриваем систему линейных уравнений
Для нахождения базисного решения, зависящего от множества индексов S = {1,m}
надо привести данную систему к диагональной форме по базисным переменным
(используя метод Гаусса).
Полагая переменные, не вошедшие в диагональную форму (небазисные переменные)
равными нулю, олучаем - значения для базисных
переменных.
3. Процедура симплекс-метода
3.1. Понятие базисного решения – основа симплекс-метода
Оказывается, что для нахождения оптимального решения достаточно ограничиться
рассмотрением только базисных (допустимых базисных) решений в силу справедливости
следующих утверждений (теорем).
1. Если у системы линейных уравнений (СЛУ) существует решение (СЛУ - совместна), то
существует и базисное решение этой СЛУ.
2. Если задача ЛП в канонической форме имеет допустимое решение, то она имеет и
допустимое базисное решение
3. Если задача ЛП имеет оптимальное решение, то она имеет и оптимальное базисное
решение.
В силу справедливости последнего утверждения, вычислительный алгоритм линейного
программирования (симплекс-метод) основан на нахождении именно оптимального
базисного решения и оперирует только с допустимыми базисными решениями.
3.2. Прямой симплекс-метод решения ЛП задачи (вспомогательные построения)
Рассмотрим задачу линейного программирования в канонической.
По этой задаче ЛП запишем систему линейных уравнений, соответствующую этой
задаче.
Приведем данную систему к диагональной форме.
Составим таблицу коэффициентов данной диагональной формы (симплексная
таблица, сокращенно С-Т):
z x1 ... xr ... xm xm+1 ... xs ... xn
z z0 0 ... 0 ... 0 cm+1 ... cs ... cn
x1 b1 1 0 0 a1m+1 a1s a1n
... ... ... ... ... ... ... ... ... ...
xr br 0 ... 1 ... 0 arm+1 ... ars ... arn
... ... ... ... ... ... ... ... ... ...
xm bm 0 ... 0 ... 1 amm+1 ... ams ... amn
Симплексная таблица – основной элемент вычислительной процедуры симплекс-метода.
3.5. Классификация симплексных таблиц.
Симплексная таблица называется прямо допустимой, если b i m i > 0, = 1, . Прямодопустимая С-Т соответствует допустимому базисному решению.
Симплексная таблица называется двойственно допустимой, если c j n j > 0, = 1.
Симплексная таблица называется оптимальной, если она одновременно и прямо
допустимая, и двойственно допустимая. Оптимальная С-Т соответствует
оптимальному базисному решению.
3.6. Алгоритм прямого симплекс-метода (максимизации).
0. Начать вычисления с прямо-допустимой симплексной таблицы.
Вычисления по алгоритму состоят в выполнении следующих однотипных итераций. Каждая
такая итерация состоит из трех последовательно выполняемых шагов.
ИТЕРАЦИЯ
1. Проверка оптимальности или нахождение ведущего столбца С-Т.
Если все коэффициенты в выделенной строке при небазисных переменных
неотрицательны (коэффициенты в z-уравнении), то текущее базисное решение
является оптимальным.
В противном случае на следующей итерации в число базисных переменных
вводим небазисную переменную xs, номер которой находится.
Столбец под номером s называется ведущим столбцом симплексной таблицы.
2. Проверка условия неограниченности решения задачи ЛП и нахождение ведущей
строки (ведущего элемента) С-Т.
Если в ведущем столбце симплексной таблицы s нет положительных
коэффициентов, то значение задачи ЛП неограниченно (нет оптимального
решения)
В противном случае (в ведущем столбце имеются положительные элементы) в
качестве базисной переменной, которая исключается из числа базисных,
выбирается та переменная xr.
Строка под номером r называется ведущей строкой С-Т, а элемент ars>0 –
ведущим элементом С-Т.
3. Преобразование симплексной таблицы.
Используя эквивалентные преобразования таблицы (процедуру Гаусса)
пересчитываем таблицу так, чтобы ведущий элемент новой С-Т стал равным 1,
а все остальные элементы ведущего столбца – равными 0.
Обозначим верхним индексом 1 элементы новой симплексной таблицы. Тогда