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

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).

Источник

6. Постановка задач линейного программирования. Примеры, различные формы задач и подходы решения. Постановка задач линейного программирования

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

В общей постановке задача линейного программирования (ЗЛП) формулируется следующим образом. Имеются какие-то переменные x = (x1, x2,…, xn) и линейная функция этих переменных, которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции при условии, что переменные x удовлетворяют системе линейных равенств и/или неравенств.

Функция цели в задаче линейного программирования обычно записывается так:

Или в сокращённом виде с сигмой:

Можно встретить обозначение целевой функции и через C, и через F.

Система ограничений в задаче линейного программирования в канонической форме записывается так:

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

Целевая функция. Её нужно максимизировать или минимизировать. Для того, чтобы функцию максимизировать, переменные, являющиеся её слагаемыми, должны принимать как можно большие значения в соответствии с условиями задачи. При минимизации — наоборот, меньшие. Обычно целевая функция выражает доходы или расходы.

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

Ограничения. Очень просто. Например, в каждом уравнении (неравенстве) заданы ограничения перечисленных выше или других запасов, используемых для производства определённого вида продукции.

Примеры, различные формы задач и подходы решения

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

Общей задачей ЛП называется задача, которая состоит в определении максимального (минимального) значения функции

Помимо общей формы, различают еще две частные задачи линейного программирования — стандартную и основную.

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

Ограничения основной задачи ЛП представляют собой линейные ограничения-равенства, а также условия неотрицательности на переменные:

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

Примеры решения задач линейного программирования:

Пример №1. Предприятие выпускает продукцию двух разновидностей. Каждый вид продукции проходит обработку на трёх станках. При обработке 1 т продукции I вида первый станок используется 0 ч, второй станок – 1 ч, третий станок – 1 ч. При обработке 1 т продукции II вида первый станок используется 1 ч, второй станок – 4 ч, третий станок – 1 ч. Время работы станков ограничено и не может превышать для первого станка 7 ч, для второго 29 ч, для третьего 11 ч. При реализации 1 т продукции I вида предприятие получает прибыль 2 руб., а при реализации 1 т продукции II вида – 5 руб. Найти оптимальный план выпуска продукции каждого вида, дающий максимальную прибыль от реализации всей продукции.

3. Решим прямую задачу графически:

Источник