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

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

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

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

Рис. 2.2

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

Остальные переменные также должны быть неотрицательными, т. е. должны выполняться условия:

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

Рис. 2.3

Положим величину равной своему крайнему значению — нулю. Получим уравнение

Это — уравнение прямой. На этой прямой (см. рис. 2.2); по одну сторону от нее по другую (по какую — это зависит от коэффициентов уравнения). Отметим штриховкой ту сторону прямой по которую

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

«допустимую сторону», где соответствующая переменная больше нуля (рис. 2.3).

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

прямых Каждая из них определяет «допустимую полуплоскость», лежащую по одну ее сторону. Часть плоскости принадлежащая одновременно всем этим полуплоскостям, образует область допустимых решений (ОДР). На рис. 2.3 область допустимых решений отмечена редкой штриховкой.

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

Докажем, что ОДР всегда является выпуклой фигурой. Предположим противное: точки А и В принадлежат ОДР, а какая-то точка С между ними не принадлежит (см. рис. 2.4). Тогда между точкой А, принадлежащей ОДР, и точкой С, не принадлежащей ей, непременно должна проходить какая-то из прямых по одну сторону этой прямой точки удовлетворяют условию, по другую — не удовлетворяют. Пусть эта прямая пересекает отрезок АВ в какой-то точке D. Тогда точки А и В, лежащие по разные стороны от прямой, не могут одновременно принадлежать ОДР (для нее все неотрицательны), что противоречит условию.

Рис. 2.4

Рис. 2,5

На рис. 2.3 показан такой пример, когда ОДР существует, т. е. система уравнений ОЗЛП имеет неотрицательные решения.

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

Пример 1 Задача линейного программирования с семью переменными

имеет уравнений-ограничений:

Требуется дать ее геометрическую интерпретацию и построить ОДР, если она существует.

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

Из третьего:

Из четвертого:

Подставляя (3.4) во второе уравнение (3.3) и (3.5) — в последнее и разрешая относительно имеем:

Геометрическая интерпретация задачи представлена на рис. 2.6 (прямые -оси координат; остальные ограничивающие прямые короткой штриховкой помечены допустимые полуплоскости).

Как видно из расположения прямых и отмеченных полуплоскостей, допустимые решения для рассмотренной задачи существуют; они заполняют ОДР, которая на рис. 2.6 показана редкой штриховкой.

Рис. 2.6

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

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

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

Предположим, что свободными переменными опять являются а базисными выраженные через свободные формулами (3.2). Подставим выражения (3.2) в формулу (3.6), приведем подобные члены и выразим линейную функцию L всех переменных как линейную функцию только двух свободных переменных: Получим:

где — свободный член, которого в первоначальном виде у функции L не было; теперь, при переходе к переменным он мог появиться.

Рис. 2.7

Рис. 2.8

Очевидно, линейная функция (3.7) достигает минимума при тех же значениях что и функция

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

Найдем эти значения, пользуясь геометрической интерпретацией. Придадим L некоторое постоянное значение С:

получим уравнение прямой на плоскости (рис. 2.7). Угловой коэффициент этой прямой равен — а отрезок, отсекаемый ею на оси (начальная ордината), равен Очевидно, если мы заменим постоянную С на некоторую другую угловой коэффициент прямой не изменится; изменится только начальная ордината, и прямая переместится параллельно самой себе в новое положение (см. рис. 2.7).

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

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

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

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

Рис. 2.9

Рис. 2.10

Рис. 2.11

При других знаках коэффициентов направление убывания меняется. Случаи различных направлений убывания показаны на рис. 2.9, 2.10 и 2.11.

Таким образом, и направление основной прямой, и направление убывания линейной формы L определяются величинами и знаками коэффициентов при свободных переменных в выражении V.

Дадим теперь геометрическую интерпретацию нахождения оптимального решения ОЗЛП среди допустимых.

Пусть имеется область допустимых решений ОДР (рис. 2.12) и основная прямая; известно (указано стрелками) направление убывания линейной формы

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

а также оптимальное (минимальное) значение линейной функции

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

Рис. 2.12

Пример 2. В условиях примера 1 найти оптимальное решение ОЗЛП, обращающее в минимум линейную функцию семи неизвестных:

Уравнения-ограничения те же, что и в примере 1.

Решение. В примере 1 уравнения-ограничения (3.3) были разрешены относительно базисных переменных которые были выражены через свободные

Подставляя эти выражения в (3.9) и приводя подобные члены, имеем:

Воспроизведем область допустимых решений, ранее построенную на рис. 2.6 (см рис. 2.13).

Отбрасывая свободный член в (3.11), имеем:

Строим основную прямую. Для этого откладываем отрезки по оси абсцисс и по оси ординат, проводим через точку В с координатами) прямую и отмечаем стрелками направление убывания V. Перемещая основную прямую параллельно самой себе в сторону убывания V, наименьшее значение L мы получим в точке А (наиболее удаленной от начала координат в направлении стрелок).

Координаты этой точки t, 2 и дают оптимальное решение ОЗЛП В точке А пересекаются две ограничивающие прямые: Приравнивая нулю выражения для в и 7, получим два уравнения:

Решая их совместно, найдем

Рис. 2.13

Подставляя эти значения в (3 11), найдем оптимальные значения базисных переменных:

Что касается и, то их оптимальные значения равны нулю:

Подставляя найденные оптимальные значения в линейную функцию (3.11), иайдем минимальное значение (оптимум) линейной функции

Таким образом, мы научились решать ОЗЛП в частном случае — при помощи геометрического построения.

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

Отметим подмеченные нами закономерности для случая

1. Решение ОЗЛП, если оно существует, не может лежать внутри области допустимых решений, а только на ее границе.

2. Решение ОЗЛП может быть и не единственным (см. рис. 2.14). Действительно, если основная прямая параллельна той стороне многоугольника допустимых решений, где достигается минимум L, то он достигается не в одной точке, а на всей этой стороне.

В этом случае ОЗЛП имеет бесчисленное множество оптимальных решений.

3. ОЗЛП может не иметь решения даже в случае, когда существует ОДР (рис. 2.15). Это бывает тогда, когда в направлении стрелок ОДР неограничена, т. е. в области допустимых решений линейная функция L неограничена снизу. Перемещая основную прямую в направлении стрелок, мы будем получать все меньшие и меньшие значения V, а значит, и L.

Рис. 2.14

Рис.

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

5. Для того, чтобы найти оптимальное решение, в принципе достаточно перебрать все вершины ОДР (опорные точки) и выбрать из них ту, где функция L достигает минимума.

6. Если число свободных переменных в ОЗЛП равно 2, а число базисных — и решение ОЗЛП существует, то оно всегда достигается в точке, где по крайней мере две из переменных обращаются в нуль. Действительно, в любой опорной точке пересекаются по крайней мере две из ограничивающих прямых; могут же в ней пересекаться и более двух (см. рис. 2.16).

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

Рассмотрев подробно геометрическую интерпретацию для случая обратимся к случаю, когда число переменных превышает на 3 число независимых уравнений-ограничений:

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

Требуется найти такие неотрицательные значения которые, удовлетворяя уравнениям (3.12), одновременно обращали бы в минимум линейную функцию этих переменных:

Рис. 2.16

Рис. 2.17

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

Роль «основной прямой» в этом случае будет играть «основная плоскость», уравнение которой, где

При перемещении этой плоскости параллельно самой себе в одну сторону L будет убывать, в другую — возрастать. Точка А, в которой достигается оптимальное решение (если оно существует), представляет собой ту вершину ОДР, которая находится дальше всего от начала координат, считая по направлению убывания L.

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

Пользоваться геометрической интерпретацией для непосредственного отыскания решения даже при затруднительно; при это вообще выведет нас за рамки трехмерного пространства и геометрическая интерпретация потеряет наглядность. Однако соответствующая терминология может оказаться удобной; можно говорить об области допустимых решений, как о некотором «сверхмногограннике» в пространстве k измерений, ограниченном «гиперплоскостями»; об оптимальном решении — как об одной из «вершин» этого многогранника, о каждой «вершине» — как об «опорной точке» и т. д. Такой геометрической терминологией можно, по желанию, пользоваться или не пользоваться. Нам геометрическая интерпретация понадобилась для того, чтобы обосновать следующие свойства решения ОЗЛП при любых значениях числа переменных и числа уравнений

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

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

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