Общая ЗЛП

Если ЗЛП не может быть отнесена ни к классу стандартных, ни к классу канонических задач, она называется общей ЗЛП.

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

(1.1)

на некотором множестве D Ì Rⁿ,где x Î D удовлетворяют сис­теме ограничений

(1.2)

и, возможно, ограничениям

(1.3)

He умаляя общности, можно считать, что в системе (1.2) пер­вые т ограничений являются неравенствами, а последующие — l -уравнениями. Очевидно, этого всегда можно добиться за счет простого переупорядочения ограничений. Относительно направ­ления знака неравенства будем предполагать, что левая часть меньше или равна правой. Добиться этого можно, умножив на (-1) обе части тех неравенств, которые имеют противопо­ложный знак. Ограничения (1.3), вообще говоря, могут быть рассмотрены как частный случай ограничений в форме нера­венств, но в силу особой структуры их обычно выделяют от­дельно и называют условиями неотрицательности (или три­виальными ограничениями).

Дополнительно следует заметить, что выбор типа искомого экстремума (максимума или минимума) также носит относитель­ный характер. Так, задача поиска максимума функции

(1.4)

эквивалентна задаче поиска минимума функции

(1.5)

Часто условия задачи (1.1) - (1.3), содержащей ограничения только типа неравенств, бывает удобно записывать в сокращен­ной матричной форме

(1.6)

где с и x — векторы из пространства Rⁿ, b — вектор из простран­ства R^m, a А — матрица размерности m ´ п.

Задачу линейного программирования, записанную в форме (1.1) - (1.3), называют общей задачей линейного програм­мирования (ОЗЛП).

Если все ограничения в задаче линейного программирования являются уравнениями и на все переменные x_j наложены усло­вия неотрицательности, то она называется задачей линейного программирования в канонической форме, или канонической задачей линейного программирования (КЗЛП). В матрич­ной форме КЗЛП можно записать в следующем виде:

(1.7)

Поскольку любая оптимизационная задача однозначно оп­ределяется целевой функцией f и областью D, на которой отыс­кивается оптимум (максимум), будем обозначать эту задачу парой (D, f).

Условимся относительно терминологии, которая использу­ется в дальнейшем и является общепринятой в теории линейно­го программирования.

Планом ЗЛП называется всякий вектор х из пространства Rⁿ.

Допустимым планом называется такой план ЗЛП, кото­рый удовлетворяет ограничениям (1.2)-(1.3), т. е. содержится в области D. Сама область D называется при этом областью допустимых планов. Оптимальным планом х^* называется такой допустимый план, при котором целевая функция достига­ет оптимального (в нашем случае — максимального) значения, т. е. план, удовлетворяющий условию

max f(x) = f(x^*).

Величина f^* = f(x^*) называется оптимальным значением целевой функции.

Решением задачи называется пара (х^*, f^*), состоящая из оптимального плана и оптимального значения целевой функ­ции, а процесс решения заключается в отыскании множества всех решений ЗЛП.

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

Общая идея перехода от ОЗЛП к КЗЛП достаточно проста:

Ø ограничения в виде неравенств преобразуются в уравне­ния за счет добавления фиктивных неотрицательных переменных , которые одновременно входят в целевую функцию с коэффициентом 0, т. е. не оказывают влияния на ее значение;

Ø переменные, на которые не наложено условие неотрица­тельности, представляются в виде разности двух новых неотрицательных переменных:

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

и множеством допустимых планов D, определенным системой уравнений и неравенств,

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

а множество определено как:

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

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

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

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

(1)

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

Требуется найти такую совокупность неотрицательных значений х₁, х₂,..., х_п, которая удовлетворяла бы неравенствам (1), и, кроме того, обращала бы в минимум линейную функцию: (2) От поставленной таким образом задачи легко перейти к основной задаче линейного программирования. Действительно, введем новые («дополнительные») переменные у₁, у₂,..., у_m как: (3)

(3)

Согласно условиям (1), эти дополнительные переменные так же, как и х₁, х₂,..., х_п должны быть неотрицательными. Таким образом, может быть сформулирована следующая задача линейного программирования: найти такие неотрицательные значения п + т переменных х₁, х₂,..., х_п у₁, у₂,..., у_m, чтобы они удовлетворяли системе уравнений (3) и одновременно обращалив минимум линейную функцию этих переменных (2).

Как видно, перед нами основная задача линейного программирования (03). Уравнения (3) заданы в форме, разрешенной относительно базисных переменных у₁, у₂,..., у_m, которые выражены через свободные переменные х₁, х₂,..., х_п. Общее количество переменных равно п + т, из них п «основные» и т «дополнительные». Функция F выражена только через исходные переменные (коэффициенты при «дополнительных» переменных в ней равны нулю).

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

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

11. Основные теоремы линейного программирования.

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

Теорема 1.1. Если целевая функция f принимает мак­симальное значение в некоторой точке множества до­пустимых планов D, то она принимает это значение и в некоторой угловой точке данного множества.