Общая задача линейного программирования

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

принимает наименьшее или наибольшее значение. Подобные задачи во введении были определены как задачи линейного программирования (ЗЛП).

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

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

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

В зависимости от вида системы ограничений, ЗЛП имеет три различные формы: каноническую, стандартную и общую. Они эквивалентны в том смысле, что каждую из них можно простыми преобразованиями привести к любой из двух остальных форм.

1. Каноническая задача линейного программирования

Дана система линейных уравнений:

(1)

и линейная функция

(2)

Требуется среди неотрицательных решений системы уравнений (1) найти такое решение :

(3) , при котором функцияпринимает

наименьшее значение: .

В задаче о распределении ресурсов из §1 отыскивается не наименьшее, а наибольшее значение целевой функции. Однако, это не существенно в теоретическом плане, так как если

, то для некоторой окрестности точки n–мерного пространства выполняется неравенство: .

Но отсюда следует, что , т.е. противоположная функцияпринимает в точкенаибольшее значение:

.

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

Так, вместо того, чтобы во второй задаче из §1 искать наибольшее значение функции , достаточно найти наименьшее значение функциии изменить его знак.

2. Стандартная задача линейного программирования

Дана система линейных неравенств:

(4)

и линейная функция

(5)

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

Как на практике, так и в теории часто требуется перейти от одной формы записи ЗЛП к другой. Оказывается, что это всегда можно сделать.

Так, переход от канонической формы к стандартной осуществляется заменой каждого уравнения системы (1)

равносильной ему системой двух неравенств

(6)

Переход от стандартной формы ЗЛП к канонической основывается на следующей теореме.

Теорема. Если неравенство (7)

имеет неотрицательное решение (8) , то уравнение (9)имеет неотрицательное решение (10).

Обратно, если уравнение (9) имеет неотрицательное решение , то неравенство (7) имеет неотрицательное решение .

Доказательство. Пусть – неотрицательное решение неравенства (7), тогда.

Перенесем все члены из левой части в правую и полученную разность обозначим :.

Это равенство перепишем иначе: .

Из последнего равенства следует, что – неотрицательное решение уравнения (9).

Обратно, пусть – неотрицательное решение уравнения (9):. Так как, то

, поэтому выполняется неравенство , что означает, что– неотрицательное решение неравенства (7). Теорема доказана.

Таким образом, если не обращать внимания на вспомогательную переменную , то можно считать, что неравенство (7) и уравнение (9) имеют одни и те же неотрицательные решения, т.е. неравенство (7) и уравнение (9) равносильны в указанном смысле. Если в левую часть каждогоi – того неравенства системы (7) добавим свою вспомогательную переменную и заменим знак знаком =, получим равносильную задачу в канонической форме.

Очевидно, при переходе от неравенства к уравнению следует вводить новую переменнуюсо знаком минус.

Пример. Написать задачу о распределении ресурсов из §1 в канонической форме.

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

Среди неотрицательных решений системы уравнений

найти такое решение, при котором функция принимает наименьшее значение.

В общем случае система ограничений ЗЛП может содержать одновременно линейные уравнения и линейные неравенства. Такую форму задачи называют общей задачей линейного программирования. Каноническая и стандартная формы являются частными случаями общей задачи линейного программирования. Указанными ранее способами легко перейти от общей формы к канонической или стандартной.

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