Лекция: Методы условной минимизации.

Задача линейного программирования

Нередко задачи оптимизации, а именно, задачи планирования и управления сводятся к поиску условного минимума (об условном экстремуме – см. далее в этом разделе, в пункте «численные методы оптимизации») целевой функции, которая является линейной. При этом допустимые значения параметров также подчинены линейным равенствам или неравенствам. В этом случае для получения оптимального решения решается задача линейного программирования.

Задача линейного программирования сводится к определению минимума (максимума) линейной функции

с учетом ограничений вида:

,;,;, .

Такие xi, которые доставляют минимум (максимум) целевой функции при заданных ограничениях называются оптимальным планом. Обычно, исходя из реального смысла задачи (стоимость, физические переменные и т.п.), накладываются еще ограничения,. Ограничения в виде равенств легко исключить: неизвестные можно исключить с помощью равенств и подставить в целевую функцию. Неравенства, содержащие знак ³, легко преобразовать к неравенствам со знаком £, умножив их на (-1). Таким образом, минимизация (максимизация) целевой функции без нарушения общности задачи находится при ограничениях:

, .

Указанные неравенства можно преобразовать к равенствам, вводя дополнительные переменные :

, .

При этом целевую функцию можно записать так:

, где если .

Определение 1. Максимальная совокупность U значений x1, x2, ..., xn , удовлетворяющая всем неравенствам, называется областью допустимых значений задачи линейного программирования.

Определение 2. Точка x(0), не лежащая ни на каком отрезке, соединяющем любые две точки множества U, называется угловой точкой.

Имеет место следующая теорема.

Теорема. Линейная целевая функция может достигать своего строгого экстремума лишь в угловых точках допустимой области.

Возможны следующие случаи: 1) оптимальное решение находится в одной вершине многогранника; 2) оптимальное решение находится в более, чем в одной угловой точке. В этом случае функция достигает того же значения в любой точке, являющейся выпуклой комбинацией этих точек. Соответственно, можно получить как бесконечно много оптимальных решений, так и, то есть, фактически, ни одного оптимального решения. Во втором случае задача линейного программирования называется вырожденной.

Будем далее предполагать, что решение единственно, то есть имеет место первый случай, который и представляет наибольший интерес. Приведем пример задачи линейного программирования. Пусть требуется найти минимум линейной функции при следующих ограничениях:,,,,. Область, ограниченная соответствующими равенствами, изображена на рис. 6.1. Проведя вычисления, получим, что, где точка имеет координаты (0, 2).

Рис. 6.1. Область, ограниченная уравнениями:,, .

В общем случае, решение ищется в пространстве Rn, поэтому перебор вершин многогранника оказывается не простой задачей и для определения оптимального решения используется специальный метод, который получил название симплекс–метода. Этот метод позволяет по известному базисному решению построить другое базисное решение, для которого значение линейной формы меньше (больше), чем для исходного. Название метода связано с понятием симплекса — выпуклого многогранника в n–мерном пространстве с вершинами на осях координат в точках .

Симплексный метод

Запишем систему уравнений в векторной форме, где,,, T вверху означает транспонирование. Пусть некоторые m векторов линейно независимы. Тогда их можно принять в качестве базисных векторов. Любой другой вектор можно разложить по базисным векторам: (здесь — коэффициенты разложения, причем нумерация векторов может отличаться от исходной, так как зависит от выбора базисных векторов).

Пусть известно какое-нибудь базисное решение системы,. Это решение удовлетворяет векторному уравнению:

. (6.1)

Учтем, что — базисные, и, следовательно, для некоторого вектора можно записать:

. (6.2)

Умножим (6.2.) на произвольную постоянную и вычтем полученное выражение из (6.1.):

. (6.3.)

Обозначим,. Переменные, где, удовлетворяют ограничению, так как величина может быть выбрана как угодно малой. Вместе с тем полученное решение не является базисным, так как вектор содержит компоненту. Для того чтобы решение стало базисным необходимо сделать так, чтобы одно из было равным нулю. Это можно сделать путем выбора. Ясно, что если все отрицательны, то всегда получим и, следовательно, вектор не дает возможности получения нового базисного решения. Пусть найден такой вектор, среди коэффициентов разложения которого есть хотя бы один положительный. В этом случае удается получить для некоторого . В общем случае таких положительных коэффициентов разложения может быть несколько. И, следовательно, из возможных значений нужно выбрать одно, а именно минимальное значение, иначе говоря

, .

Действительно, если взять, то некоторые из окажутся отрицательными.

Полагая для определенности, что соответствует, получим следующее базисное решение:

,

,

, (6.4.)

Таким образом, один из базисных векторов теперь заменен на вектор то есть сделан переход к новому базису.

Далее необходимо выяснить, целесообразен ли переход к новому базису. Подставляя старое и новое решения в линейную форму, можно определить, будет ли она уменьшаться (увеличиваться, если ищется максимум) при таком переходе. После подстановки получим

, (6.5.)

где .

Из (6.5.) следует, что в случае целевая функция уменьшается, а в случае возрастает (величины в линейном программировании имеют специальное название: маргинальные значения). Следовательно, определив знак маргинального значения, можно сделать вывод о том, имеет ли смысл переход к новому базису. Переходя к новым базисам, можно последовательно улучшать решение. Симплекс–метод относится к итерационным методам, однако, он приятно отличается от большинства из них тем, что на последнем шаге позволяет получить точное решение.

Подставим коэффициенты разложения вектора Ak в целевую функцию:

fk = f(xjk) = x1kc1+ x2k c2 + ...+ xmk cm, j=1 n,

где ci – коэффициенты линейной функции, соответствующие векторам базиса.

При решении задачи на отыскание минимума справедлива следующая теорема.

Теорема. Если для некоторого вектора Ak выполняется условие

fk -ck> 0, то соответствующий план не является оптимальным.

Из теоремы следует, что план * является оптимальным, если разложение всех векторов Ak в данном базисе удовлетворяет следующему условию оптимальности:

fk -ck < 0.

Для определения начального базисного решения часто используют метод искусственного базиса. В методе строится единичная подматрица порядка и получается начальное базисное решение. Для этого приравниваются значения переменных, образующих ее, правым частям соответствующих уравнений. Так, если в ограничениях вида величины, каждое из неравенств можно преобразовать в равенство путем введения дополнительной переменной:

, .

Матрица этих переменных представляет собой единичную подматрицу системы порядка, то есть подматрицу вида

.

Таким образом, дополнительные переменные можно использовать для определения начального базисного решения:

, ,

, .

Другие случаи ограничений, а также алгоритм симплекс–метода подробно рассмотрены, например, в литературе, указанной для данного раздела.

Типичной задачей линейного программирования является задача об оптимальном раскрое материалов.

Пусть на некоторое предприятие или объединение предприятий поступает партий материалов (полуфабрикатов). Пусть далее – тая партия содержит единиц, а комплект, который производит предприятие, состоит из различных деталей, причем из них деталей – того типа. Для получения комплекта единица каждой партии может быть раскроена способами. Введем следующие обозначения: — число деталей типа, которое получается при – том способе раскроя одной единицы из – той партии, – единицы партии, которые раскроены – тым способом. Тогда количество комплектов, обеспеченных деталями, определится так:

. (6.6)

Задача заключается в максимизации, при выполнении ограничений:

, ,

, ,

,, .

Типовой задачей также является задача использования сырья. Пусть при выпуске n видов продукции используется m видов сырья. Введем следующие обозначения: – виды сырья, – запасы сырья i-вида, – виды продукции, – количество i-го сырья, идущего на изготовление единицы j-той продукции, – величина прибыли получаемой при реализации единицы j-той продукции, – количество единиц j-той продукции, которое необходимо произвести, f – прибыль, получаемая при реализации продукции. Требуется составить оптимальный план выпуска продукции, который позволил бы при ее реализации получить максимальную прибыль. Математическая модель, соответствующая данной задаче, может быть представлена в следующем виде:

.

Методами линейного программирования решаются также задачи организации снабжения, транспортные, расхода ресурсов на выпуск изделий и многие другие.

Нередко при решении технических, экономических или других конкретных задач вместо минимума той или иной величины оказывается удобнее найти максимум другой величины, непосредственно связанной с первой, или наоборот. Например, вместо минимума стоимости максимум полезного объема и т.п.

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

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

Решая исходную задачу линейного программирования или двойственную ей, получим одно и тоже оптимальное решение.

Пример. В заключении данного пункта приведем пример решения задачи линейного программирования (например, задачи использования сырья) симплекс-методом:

.

Перейдем от неравенств к равенствам, прибавляя к левым частям дополнительные переменные :

Запишем систему в векторной форме:

,

где

,,,,,, .

В качестве базиса первоначального опорного плана выберем единичные векторы,,. Тогда получим следующий первоначальный опорный план:

.

Для поиска минимума перейдем к функции :

.

Найдем значение и оценки. Получим ,

,,,,,. Для векторов базиса оценки равны нулю. Составляем первую симплексную таблицу (таблица 6.1).

Таблица 6.1.

Первая симплексная таблица

Все оценки положительны, следовательно, первоначальный опорный план не оптимален и может быть улучшен путем перехода к базису.

Найдем значения;;,;;;. Т.о., необходимо включить в базис вектор или .

Поскольку, то будем включать вектор. При этом вектор исключаем из базиса. Разрешающим элементом является число 1, стоящее на пересечение второй строки и третьего столбца.

Составим вторую симплексную таблицу, используя метод исключений Жордана-Гуасса. Для этого элементы направляющей строки (в данном случае, второй) разделим на разрешающий элемент. Далее вычтем вторую строку из первой, из третьей, умножим на 4 и вычтем результат из строки ( ). Полученные результаты приведены в (Таблице 6.2).

Таблица 6.2.

Вторая симплексная таблица

В Таблице 6.2 (столбец ) получен второй опорный план. Этому плану соответствует значение целевой функции. В ( ) строке, следовательно, план не является оптимальным, и вектор необходимо включить в базис. Найдем. Размещающим элементом является единица, стоящая на пересечение первой строки и второго столбца. Используя метод исключений, получаем третью симплексную таблицу (Таблица 6.3).

Таблица 6.3.

Третья симплексная таблица

В Таблице 6.3 получен третий опорный план. Данному плану соответствует значение, и, следовательно, максимальное значение целевой функции. Поскольку в ( )-ой строке все оценки не положительны, то план является оптимальным.