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

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

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

(4)

(где можно считать, что , изменяя, если нужно, знак в соответствующем уравнении (4)) и линейная функция

. (1)

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

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

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

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

В этом случае минимум также равен .

В ряде практических задач (например, в задаче о диете) ограничения носят вид неравенств

. (5)

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

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

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

(6)

Здесь — ранг матрицы коэффициентов системы (4).

Подставляя эти выражения в функцию , получаем

После этого исходная задача может быть сформулирована следующим образом. Даны система

(7)

линейных неравенств с неизвестными и линейная функция

(8)

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

Эта задача эквивалентна исходной. В самом деле, если мы нашли решение задачи (7), (8) , то, находя по формулам (6) неотрицательные значения , мы получим систему чисел

которая служит решением задачи (1), (4).

Таким образом, задачу линейного программирования можно ставить с ограничениями типа неравенств. Из такой постановки видно, что область , в которой мы ищем минимум , представляет собой «многогранник» в неотрицательном угле (т. е. когда ), а ее граница состоит из «плоских граней», находящихся в плоскостях пространства :

. (9)

Множество называется выпуклым, если .

Из системы неравенств (7) ясно, что «многогранник» выпуклый и находится по одну сторону от любой из своих граней.

Слово «многогранник» мы пишем в кавычках, так как могут быть случаи, когда этот «многогранник» будет неограниченной частью неотрицательного угла .

Например, при и при тех ограничениях типа неравенств «многоугольник» может быть неограниченным в первой четверти . На рис. 54 - заштрихованная часть.

Рис.54

В дальнейшем кавычки у слова «многогранник» мы будем опускать.

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

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

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

Замечание 1. Если функция , где - постоянное число, то мы исследуем сначала линейную форму , и если , то .

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

Рассмотрим плоскости уровня функции :

. (10)

Уравнение (10) при различных в пространстве изображает семейство параллельных плоскостей (см. § 27). Будем непрерывно и монотонно изменять от до . Тогда плоскость (10) будет передвигаться в в направлении вектора , который, как мы знаем, перпендикулярен плоскости (10). Очевидно, что если , то плоскость (10) поднимается вверх относительно оси при изменении от до ; если же , то плоскость (10) опускается вниз относительно оси . При плоскость (10) движется вправо или влево относительно оси в зависимости от знака числа . Если и при всех , где - некоторое действительное число, плоскость (10) пересекает область , то .

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

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

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

Этот геометрический метод решения поставленной задачи эффективен лишь при , т. е. когда плоскости (10) — прямые и - многоугольник, ограниченный или нет. При взаимное расположение плоскостей и многоугольника трудноуловимо, а при мы просто не можем прибегнуть к наглядным графическим изображениям.

Пример 1. Найти минимум функции при ограничениях (рис. 55)

Ясно, что область есть треугольник с вершинами в точках . Прямая уровня функции :

при возрастании от до опускается относительно оси (коэффициент при отрицателен); ее первая точка встречи с есть вершина . Значение функции в этой точке равно нулю . Итак, решение задачи есть .

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

Рис. 55 Рис. 56

Пример 2. Найти минимум функции при тех же ограничениях, что и в примере 1.

В данном случае прямая уровня функции

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