Стандартная форма линейного программирования

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

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

Стандартная форма

В стандартной форме задаются ( n ) действительных чисел (с_1, c_2, ldots, c_n ); ( m ) действительных чисел ( b_1,b_2,ldots ,b_m ); и ( mn ) действительных чисел ( a_ ), где ( i=1,2, ldots, m ) и ( j = 1,2, ldots, n ).
Требуется найти ( n ) действительных чисел ( x_1,x_2,ldots,x_n ) которые:

Максимизируют целевую функцию ( sumlimits_^n c_j x_j ) при заданных ограничениях : ( sumlimits_^n a_ x_j le b_i) при ( i=1,2, ldots, m ) и ограничениях неотрицательности ( x_j ge 0 ) при ( j= 1,2,ldots,n )

Преобразование в стандартную форму

Задача находится не в стандартной форме если:

1. Целевая функция минимизируется, а не максимизируется
2. На имеющиеся переменные не наложены условия неотрицательности
3. Некоторые ограничения имеют форму равенства, т.е. имеют знак равенства вместо меньше или равно
4. Некоторые ограничения вместо знака “меньше или равно” имеют знак “больше или равно”.

Как получить стандартную форму в таких случаях? Рассмотрим по пунктам:

1. Достаточно поменять знаки целевой функции, например: ( -5x_1+2x_2 to min ) эквивалентно ( 5x_1-2x_2 to max ).
2. Если отсутствует ограничение неотрицательности для переменной (x_j), то заменяем эту переменную выражением ( x_j^<‘>-x_j^ <“>) из двух неотрицательных переменных (x_j^<‘>,x_j^ <“>ge 0 ).
3. Если ограничение имеет вид равенства, то заменяем его парой из двух неравеств “меньше или равно” и “больше или равно”.
4. Для смены смены выда неравенства с “больше или равно” на “меньше или равно” умножаем обе части неравества на -1 и меняем знак сравнения.

[-5x_1+3x_2 to min ]

Шаг 1. Меняем знак целевой функции

[5x_1-3x_2 to max ]

Шаг 2. Для второй переменной (x_2) ограничений неотрицательности нет. Заменим на выражение (x_2=x_2^<‘>-x_2^ <”>):

Шаг 3. Заменяем равенство на два неравенства:

Шаг 4. Изменяем знак неравества:

Получили задачу в стандартном виде.

Примечание:

В данной заметке рассмотрен основной подход к виду стандартной формы задачи ЛП. Существует и другой подход, например в книге Соколов А. В., Токарев В.В. Методы оптимальных решений. В 2-х т. Т 1. Общие положения. математическое программирование. – 3-е изд. – 564 с. на с. 423 выделяется стандартный вид задачи на максимум:

Однако в общепринят первый вариант из которого второй получается простым умножением обеих частей неравенств на -1.

Научная электронная библиотека

Бельков В. Н., Ланшаков В. Л.,

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

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

Задача ЛП в стандартной форме с m ограничениями и n переменными имеет следующий вид:

максимизировать или минимизировать

.

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

максимизировать или минимизировать

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

где A — матрица размерности mxn, x — вектор-столбец размерности nxl, b— вектор-столбец размерности mxl, а c — вектор-строка размерности .1xn.

Обычно A назначается матрицей коэффициентов, x — вектором переменных, b — вектором ресурсов, c — вектором оценок задачи ЛП.

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

• 1. При помощи введения дополнительных остаточных или избыточных переменных преобразовать неравенства в равенства.
• 2. Для получения неотрицательных переменных задачи неограниченные по знаку переменные заменить разностью двух неотрицательных.

При решении задач ЛП используются следующие основные понятия. Допустимым решением являются неотрицательные значения переменных, для которых выполняются ограничения, а допустимой областью — совокупность допустимых решений. Оптимальным решением называются такие допустимые значения переменных, при которых ЦФ экстремальна, т.е. имеет оптимальное значение. В ряде случаев, ЦФ имеет одно оптимальное значение при нескольких комбинаций значений переменных, следовательно, задача обладает неединственностью оптимума. Когда в задаче ЛП нет конечного оптимума, то в этом случае существует неограниченный оптимум.

Виды ЗЛП и способы перехода от одного вида к другому.

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

В канонической форме задача является задачей на максимум (минимум) некоторой линейной функции F, ее система ограничений состоит только из равенств (уравнений). При этом переменные задачи х₁, х₂, . х_n являются неотрицательными:

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

Правило приведения ЗЛП к каноническому виду:

1. Если в исходной задаче некоторое ограничение (например, первое) было неравенством, то оно преобразуется в равенство, введением в левую часть некоторой неотрицательной переменной, при чем в неравенства «≤» вводится дополнительная неотрицательная переменная со знаком «+»; в случаи неравенства «≥» — со знаком «-»

(32.1)

Тогда неравенство (32.1) запишется в виде:

В каждое из неравенств вводится своя “уравнивающая” переменная, после чего система ограничений становится системой уравнений.

Число вводимых дополнительных неотрицательных переменных при преобразовании ограничений-неравенств в ограничения-равенства равно числу преобразуемых неравенств.

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

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

3. Если в ограничениях правая часть отрицательна, то следует умножить это ограничение на (-1)

4. Наконец, если исходная задача была задачей на минимум, то введением новой целевой функции F₁ = -F мы преобразуем нашу задачу на минимум функции F в задачу на максимум функции F₁.

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

В стандартной формезадача линейного программирования является задачей на максимум (минимум) линейной целевой функции. Система ограничений ее состоит из одних линейных неравенств типа « = »). Все переменные задачи неотрицательны.

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

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

— перейти от минимизации целевой функции к ее максимизации;

— изменить знаки правых частей ограничений;

— перейти от ограничений-равенств к неравенствам;

— избавиться от переменных, не имеющих ограничений на знак..

Примеры:

1. Привести к каноническому виду задачу

Введем дополнительные переменные x₃ , x₄ , x₅ . Причем в первое неравенство введем неотрицательную переменную x₃ со знаком минус, а во второе и в третье – со знаком плюс переменные x₄ , x₅ запишем задачу в виде:

что и дает эквивалентную задачу в канонической форме.

2. Привести к стандартному виду задачу

Выразим через и остальные переменные:

Целевая функция будет выглядеть следующим образом:

Или, после упрощения:

Так как , то перепишем нашу систему следующим образом: .

Итак, эквивалентная задача в стандартной форме будет выглядеть следующим образом:

Лекция 4. Задачи линейное программирование

4.1. Формы задач линейного программирования.

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

4.1. Формы задач линейного программирования и их эквивалентные преобразования[15]

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

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

, или

;

. .

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

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

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

;

.

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

Основные вычислительные методы (симплекс-метод и его модификации) решения задач линейного программирования разработаны именно для канонической задачи.

3. Общая задача линейного программирования. Необходимо максимизировать (или минимизировать) линейную функцию от n переменных x_1, ¼, x_n вида

,

,

.

Стандартная задача получается как частный случай общей при k = m, l = n; каноническая задача получается как частный случай общей при k = 0, l = n.

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

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

— переход от задачи на минимум к задаче на максимум и обратно;

— переход от ограничения в виде неравенства «больше или равно» к ограничению в виде неравенства «меньше или равно»;

— переход от ограничения в виде неравенства к ограничению в виде равенства;

— переход от переменных любого знака к неотрицательным переменным.

Переход от задачи на минимум функции g(`X) к задаче на максимум заключается в рассмотрении задачи на максимум функции — g(`X):

.

И наоборот переход от задачи на максимум функции f(`X) к задаче на минимум заключается в рассмотрении задачи на минимум функции — f(`X):

.

Если система ограничений какой-либо задачи включает неравенства разного вида, то необходимо привести исходную ЗЛП к стандартной форме записи, т.е. для ЗЛП на максимум привести все неравенства функциональных ограничений к виду «меньше или равно», а для ЗЛП на минимум – к виду «больше или равно». Для этого используются следующие эквивалентные преобразования:

В задаче на максимум все члены слева и справа от неравенства умножают на (-1), а знак неравенства меняют на противоположный:

исходные неравенства: ;

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

Аналогичным образом поступают и в задаче на минимум:

исходные неравенства: ;

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

Для решения ЗЛП в стандартной форме записи необходимо перейти к эквивалентной ЗЛП в канонической форме записи. Переход от неканонической модели (хотя бы одно ограничение является неравенством) к канонической осуществляется введением в каждое неравенство балансовой переменной x_n+k. При знаке неравенства £ балансовая переменная вводится в неравенство со знаком плюс, т.к. левая часть неравенства меньше правой. Если знак неравенства ³, то балансовая переменная вводится в неравенство со знаком минус, т.к. левая часть неравенства больше правой. При этом для всех балансовых переменных вводится условие неотрицательности. В целевую функцию балансовые переменные не вводятся.

Если сходные неравенства имеют вид , тогда в результате преобразования получают равенства и неравенства , отражающие условие неотрицательности балансовых переменных.

Если сходные неравенства имеют вид , тогда в результате преобразования получают равенства и неравенства , отражающие условие неотрицательности балансовых переменных.

Если на переменную x_j общей задачи не накладывается ограничение неотрицательности, то для того, чтобы общую задачу свести к стандартной, необходимо ввести новые переменные и и положить . Таким образом неотрицательное значение – 5 можно заменить двумя положительными значениями 10 и 15: – 5 = 10 – 15.

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

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

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

Приведение задач к стандартной форме производится по следующим правилам:

2. Ограничение в виде неравенств, например 4×x₁ + 5×x₂ 800, может быть при­ведено к стандартной форме 4×x₁ + 5×x₂ + x₃ = 800, где x₃ — новая неотрицательная переменная.

Ограничение может быть приведено к стандартной форме , где новая переменная x₅ неотрицательна.

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

, где и .

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

Приведем к стандартной форме задачу, рассмотренную в примере 1.

Эта задача может быть представлена в следующем виде:

минимизировать функцию Z = — 20x₁ — 40x₂

, i = 1, … ,4.

В матричной форме ограничения можно записать следующим образом:

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

Конечно, имея два уравнения с четырьмя неизвестными, можно получить

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

Переменные, приравненные нулю, называются небазисными переменными.

Остальные называются базисными и образуют базис.