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

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

Задачи, рассмотренные в §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 вспомогательных переменных. Кроме того, в рассматриваемой задаче требуется найти наибольшее значение функции , поэтому в канонической форме будем искать наименьшее значение противоположной функции. Каноническая форма задачи такова:

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

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

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

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

Источник

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

Определение 1. Общей задачей ЛП называется задача нахождения максимального (минимального) значения линейной целевой функции (1) при условиях , (2) , (3) , ,(4), где ,,— заданные постоянные величины и. Определение.2. Функция Z называется целевой функцией задачи (1 — 4), —проектными параметрами задачи, а условия (2 — 4) ограничениями данной задачи. Определение 3. Стандартной задачей ЛП называется задача нахождения целевой функции (1) при выполнении условий (2), (4), где k=m,l=n, т.е. когда ограничения заданы только в виде неравенств (2), и все проектные параметры удовлетворяют условиям неотрицательности (4), а условия в виде равенств отсутствуют: , , . Определение 4. Канонической (или основной) задачей ЛП называется задача нахождения максимального (минимального) значения функции (1) при выполнении условий (3), (4), где k=0,l=n,mn, т.е. когда ограничения заданы только в виде равенств (3), и все проектные параметры удовлетворяют условиям неотрицательности (4), а условия в виде неравенств (2) отсутствуют: , , ,. Определение 5. Совокупность значений проектных параметров , удовлетворяющих ограничениям задачи (2-4), называетсядопустимым решением, или планом. Определение 6. План , при котором целевая функция (1) принимает свое максимальное (минимальное) значение, называетсяоптимальным, т.е. . Все три формы задачи ЛП эквивалентны, ибо каждая из них с помощью некоторых преобразований может быть переписана в форме другой задачи. При этом необходимо пользоваться следующими правилами:

1. Задачу минимизации функции можно свести к задаче максимизации, и, наоборот, путем замены знаков коэффициентов на противоположные, поскольку.
2. Ограничения-неравенства (2) можно заменить эквивалентными ограничениями-равенствами путем введения дополнительных неотрицательных переменных следующим образом:

Ограничение-неравенство вида преобразуется в ограничение-равенство,, а ограничение-неравенство вида— в ограничение-равенство,. При этом число дополнительных переменных равно числу преобразуемых неравенств. Вводимые дополнительные переменные имеют вполне определенный смысл. Так, например, для задачи распределения ресурсов числовое значение дополнительной переменной равно объему неиспользованного соответствующего ресурса. С математической точки зрения основные и дополнительные переменные играют одинаковую роль. Поэтому целесообразно их единообразное обозначение.

1. Каждое ограничение-равенство вида (3) можно записать в виде двух неравенств .
2. Переменная , неограниченная условием неотрицательности вида (4), можно заменить разностью двух дополнительных неотрицательных переменных:,,.

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

Рассмотрим задачу, состоящую в определении максимального значения функции: (5) при условиях , (6) , (7). Эта задача ЛП в стандартной форме с двумя переменными. Каждое неравенство вида (6), (7) геометрически определяет полуплоскость соответственно с граничными прямыми (8). При этом вектор , как градиента функции, указывает ту полуплоскость, которая определяется неравенством, а вектор— полуплоскость, определяемую неравенством. Если система неравенств (6), (7) совместна, то область её решений есть множество точек, принадлежащих всем указанным полуплоскостям. Пересечение этих полуплоскостей образует выпуклый многоугольник решений, или область допустимых решений (ОДР). Таким образом, исходная задача ЛП состоит в нахождении таких точек многоугольника решений, в которых целевая функция Z принимает максимальное (минимальное) значение. Эта точка существует тогда, когда многоугольник решений не пуст, и на нем целевая функция ограничена. Линейная целевая функция достигает точек экстремума только на границе выпуклого многоугольника. Рассмотрим градиент функции цели . Это будет вектор(см. рис.2.), указывающий направление возрастания функции цели. Очевидно, если взять обратное направление, то это будет направлением убывания функции цели. Если построить произвольную прямую— const, то её движение параллельно самой себе в направлении вектора приведет к возрастанию функции цели. При этом для допустимости решения эта прямая должна иметь хотя бы одну общую точку с многоугольником решений. Два крайних положения этой прямой в ОДР соответствуют наименьшему и наибольшему значениям целевой функции. При этом могут встретиться случаи, изображенные на рис.2-5, когда исходная задача имеет единственное решение (минимальное и максимальное значение) (рис.2), множество решений (координаты любой точки прямойна рис.3), и решение исходной задачи не существует в силу неограниченности целевой функции (рис.4) или несовместности системы неравенств (6), (7) (рис.5).

Источник

Читайте также:  Вычисления арифметического выражения программирование