Метод линейного программирования, симплекс-метод и линейные оценки

Задачи линейного программирования в канонической форме широко распространены в инженерной практике, и для их решения разработана большая группа методов, основным из которых является симплекс-метод. Рассмотрим решение задачи линейного программирования в канонической форме.

Постановка задачи линейного программирования

Задача будет рассматриваться в форме, которая называется канонической. Известно, что путем введения дополнительных ограничений и переменных можно свести к канонической форме задачу линейного программирования, представленную в естественной форме.

Каноническая форма задачи линейного программирования имеет следующий вид: вычислить.

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

В операторе (2.4.1, б) векторы х* и х° - оптимальное решение задачи (2.4.1, а) и начальное приближение для симплекс-метода (2.4.1, б), которые в симплекс-методе являются базисными решениями, определяемыми ниже. Векторы х5+1 и хЛ' в (2.4.1, б) представляют собой последующее и предыдущее решения в симплекс-методе. При решении задачи линейного программирования необходимо решить следующие основные подзадачи.

Подзадача 1. Определение условий существования, единственности и ограниченности решений задачи линейного программирования (2.4.1, а):

Подзадача 2. Формулировка условий оптимальности базисных решений, вычисляемых на итерациях симплекс-метода (2.4.1, б).

Подзадача 3. Вычисление («пересчет») новых базисных решений хч+1 на основе известных базисных решений хЛ" с помощью алгоритма симплекс-метода (2.4.1, б).

Подзадача 4. Рекуррентное вычисление новой базисной матрицы и обратной для нее при формулировке вычислительной схемы симплекс-метода (2.4.1, б) в целом.

Как правило, последовательность (2.4.1, б) является конечной, и за конечное число итераций (шагов) алгоритма симплекс-метода вычисляется оптимальное базисное решение или определяется единственность или ограниченность решения. Это имеет место, если отсутствует явление " зацикливания" , которое требует специального рассмотрения и в ряде случаев исключается специальными методами, например известным методом Чарнса.

Задача линейного программирования (2.4.1) имеет специальную форму в силу линейности функционала и ограничений, задаваемых системой линейных равенств и неравенств. Это определяет соответствующий подход к формулировке условий оптимальности.

Канонические формы ограничений, базисные решения, существование, единственность и ограниченность решений

Рассмотрим ограничения задачи в трех канонических формах:

где х = (X], Хр хп) Т — вектор переменных задачи линейного программирования; А = (Л{, Ар А") € Ятхп — матрица ограничений задачи в первой форме вида (2.4.2, а), в которой — столбцы матрицы, используемые во второй форме векторно-столбцового задания ограничений (2.4.2, б); А = (а, я,-, а,)7″ е Я" '*" — матрица ограничений, используемая в третьей форме векторно-строчного задания ограничений (2.4.2, в); Ь = (Ьх, Ьр Ьт) Т — вектор правых частей ограничений типа равенств. Для вычисления допустимого решения системы (2.4.2) необходимо решить систему линейных алгебраических равенств и простейших неравенств, обеспечивающих неотрицательность переменных. Поэтому при решении задач (2.4.1, а) симплекс-методом используются базисные решения.

Определение 1.

Решение х* называется базисным решением, на 5-й итерации, если выполнены условия:

• а) все компоненты х).;'еБи вектора базисных решений на 5-й итерации симплекс-метода х! = (х (,…, х*,…, х*,)Т еЯ'" являются неотрицательными, где В8 — множество номеров компонент базисного решения на я-й итерации;
• б) небазисные компоненты вектора х — нулевые: .г, = 0,) е B¿
• в) матрица РЛ. = (А, Ау-, А")_, размера (т х т), образованная столбцами с номерами, соответствующими базисным компонентам вектора базисного решения на 5-й итерации метода, является не особенной матрицей, при этом уеВ^.

Определение 2.

Матрица Р, в определении 1 называется базисной матрицей на 5-й итерации симплекс-метода. С учетом определений ограничения (2.4.2) примут вид.

где первая сумма определяется номерами компонент базисного решения, а вторая сумма — номерами небазисных компонент вектора х, причем Ау- — у'-й столбец матрицы ограничений, т. е. использованы первая и вторая формы (2.4.2, а) и (2.4.2, б); Вц — множество номеров базисных компонент на 5-й итерации метода. Пусть исходная базисная матрица на 5-й итерации имеет вид: Р, = (А, А^,А")х.

Матрица Р. состоит из столбцов А; таких, что ] е В, где В5 — множество номеров базисных компонент вектора х, которые неотрицательны, им соответствуют линейно-независимые столбцы Aj матрицы А.

При формулировке симплекс-метода предполагается, что в матрице ограничений, А имеется базисная матрица РЛ, которая единичная. В противном случае используется метод искусственного базиса для преобразования задачи введением новых неотрицательных искусственных переменных Xj>0,jiBs, jeN — множество искусственных переменных. Сущность метода состоит в элементарном преобразовании ограничений введением новых искусственных переменных, которым соответствуют единичные столбцы матрицы ограничений. Искусственные переменные включаются также в минимизируемую целевую функцию с достаточно большими положительными коэффициентами (весами). Если в процессе вычислений симплекс-методом искусственные переменные выводятся из базиса, то это является критерием существования решения исходной задачи линейного программирования. Если искусственные переменные в процессе итераций симплекс-метода присутствуют в базисном решении, то решения исходной задачи линейного программирования не существует, т. е. ограничения задачи (2.4.1) несовместны. Запишем ограничения (2.4.3) в виде.

где столбцы Aj, jeN являются дополнительными единичными столбцами. Эти столбцы образуют единичную базисную матрицу на нулевой итерации симплекс-метода Р = Е е /?'ях'", 5 = 0, для которой обратная базисная матрица также единичная. В результате в ограничениях задачи существует базисная матрица, которой соответствуют искусственные переменные. В методе искусственного базиса целевая функция преобразуется к виду.

где вектор х — вектор ограничений исходной задачи (2.4.1, а), а Хдг — вектор искусственных переменных.

Преобразования ограничений задачи в методе искусственного базиса к виду (2.4.3, б) и целевой функции к виду (2.4.3, в) иллюстрируют сохранение структуры задачи линейного программирования (2.4.1, а) и отражают качественные свойства столбцов матрицы ограничений второй формы (2.4.3, б). Эти качественные свойства связаны наличием единичной базисной матрицы, что позволяет далее определить оценки оптимальности решений на первой итерации симплекс-метода, сформировать алгоритм рекуррентного вычисления обратной базисной матрицы и разработать в целом алгоритм метода. Исходная задача (2.4.1, а) и новая задача — с ограничениями (2.4.3, б) и функционалом (2.4.3, е) могут быть решены симплекс-методом.

Ограничения задачи можно представить в форме.

где х5 = (х?, х%у — вектор базисного решения на 5-й итерации.

Представление базисного решения через небазисные переменные на 5-й итерации симплекс-метода имеет вид.

Выделим в функционале ср (х) = сх, с = (с, с,-, с") два слагаемых, соответствующих базисным и небазисным компонентам на 5-й итерации метода. Тогда.

где с5 =(с (,с|,с^У — вектор коэффициентов целевой функции для базисного решения на 5-й итерации, который в силу (2.4.4) имеет вид.

Из последнего соотношения следует критерий оптимальности для задачи на минимум: если все Д^ < 0, то полученное на 5-й итерации решение оптимально, поскольку введение в базис небазисных компонент с оценками Ду 0, то значение функционала можно уменьшить, перейдя к новому базисному решению1. Иногда в новое базисное множество вводят компоненту с номером к таким, что.

Можно вводить в базис компоненты с положительными оценками. Тогда критерий оптимальности в задаче на минимум имеет вид.

Критерий (2.4.5, в) используется в рассматриваемом ниже алгоритме симплекс-метода. Для максимизации функционала в (2.4.1) критерий (2.4.5, я) принимает инверсный вид: Д, >0, У/еВ5. Эти критерии отличают алгоритмы симплекс-метода для решения задач на минимум и максимум функционала. Другие этапы вычислений совпадают.