2015-06-30
620
Рассмотрим случай, когда число переменных n на 2 больше, чем число независимых уравнений m, которым они должны удовлетворять:
n-m=2.
Тогда. Как мы уже знаем, можно 2 из n переменных, скажем 
, выразить в качестве свободных, а остальные m сделать базисными и выразить их через свободные. Предположим, что это сделано. Получим m=n-2 уравнений вида:
(3.1)
Дадим задаче линейного программирования геометрическую интерпретацию. По осям 
будем откладывать значения свободных переменных 
и 
(рис. 2.2).
Рис. 2.2
Так как переменные и должны быть неотрицательными; допустимые значения свободных переменных лежат только выше оси 
и правее оси 
; отметим это штриховкой, обозначающей «допустимую сторону» каждой координатной оси.
Остальные переменные 
также должны быть неотрицательными, то есть должны выполняться условия:
(3.2)
Посмотрим, как изобразить эти условия геометрически. Возьмем одно из них, например, первое:
Рис. 2.3
Положим величину 
равной своему крайнему значению – нулю. Получим уравнение:
Это – уравнение прямой. На этой прямой 
(см. рис. 2.2); по одну сторону от нее 
, по другую 
(по какую – это зависит от коэффициентов уравнения). Отметим штриховкой ту сторону прямой , по которую .
Аналогичным образом построим и все остальные ограничивающие прямые: 
и отметим у каждой из них штриховкой “допустимую сторону”, где соответствующая переменная больше нуля (рис. 2.3).
Таким образом мы получили n прямых: две оси координат (
) и n-2прямых (
). Каждая из них определяет «допустимую полуплоскость», лежащую по одну ее сторону. Часть плоскости 
,принадлежащая одновременно всем этим полуплоскостям, образует область допустимых решений (ОДР). На рисунке область допустимых решений отмечена редкой штриховкой.
Нетрудно убедиться, что область допустимых решений всегда представляет собой выпуклый многоугольник. Как известно, выпуклой фигурой (рис. 2.4) называется фигура, обладающая следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ также принадлежит ей.
На рис. 2.3 показан такой пример, когда ОДР существует, то есть система уравнений ОЗЛП имеет неотрицательные решения.
Могут быть и случаи, когда неотрицательных решений системы не существует. Пример такого случая показан на рис. 2.5.Действительно, не существует области, лежащей по одну и ту же (заштрихованную) сторону от всех прямых: 
т.е. условия неотрицательности переменных противоречат друг другу и допустимых решений ОЗЛП не существует.
Таким образом, мы рассмотрели вопрос о существовании области допустимых решений ОЗЛП и (для случая m=n-2) дали ему геометрическую интерпретацию.
Теперь возникает вопрос о нахождении из числа допустимых оптимального решения, т. е. такого, которое обращает в максимум линейную функцию
(3.6)
Дадим и этой задаче геометрическую интерпретацию, причем снова для случая, когда m=n-2 (т.е. число свободных переменных равно 2, а число базисных m).
Предположим, что свободными переменными опять являются 
а базисными 
, выраженные через свободные формулами (3.2). Подставим выражения (3.2) в формулу (3.6), приведем подобные члены и выразим линейную функцию L всех n переменных: и 
Получим:
, ( 3.7 )
где 
– свободный член, которого в первоначальном виде у функции L не было; теперь, при переходе к переменным он мог появиться.
Очевидно, линейная функция (3.7) достигает максимума при тех же значениях что и функция
без свободного члена (линейная форма). Действительно, 
, где не зависит от 
и, очевидно, максимумы той и другой функции, отличающиеся на 
достигаются при одних и тех же значениях 
.
Найдем эти значения, пользуясь геометрической интерпретацией. Придадим 
некоторое постоянное значение C:
Получим уравнение прямой на плоскости (рис. 2.7).Угловой коэффициент этой прямой равен - 
, а отрезок, отсекаемый ею на оси (начальная ордината), равен 
. Очевидно, если мы заменим постоянную 
на некоторую другую 
, угловой коэффициент прямой не изменится; изменится только начальная ордината, и прямая переместится параллельно само себе в новое положение 
(см. рис. 2.7).
Таким образом, различным значениям соответствуют разные прямые на плоскости, но все они параллельны между собой. Очевидно, вместо всех этих прямых достаточно изобразить на плоскости одну основную прямую, например, 
, а затем можно мысленно перемещать ее параллельно самой себе. При перемещении этой прямой в одну сторону будет возрастать, в другую – убывать.
Построим основную прямую на плоскости (рис. 2.8). Мы знаем, что ее угловой коэффициент равен - ; чтобы построить прямую, проходящую через начало координат с угловым коэффициентом - , отложим по оси абсцисс отрезок 
, а по оси ординат отрезок - 
, и через точку А с такими координатами проведем прямую. Это и будет основная прямая .
Теперь остается только выяснить, в какую сторону (параллельно самой себе) надо двигать эту прямую, чтобы величина 
возрастала. В случае, показанном на рис. 2.8 (оба коэффициента 
и
положительны) направление убывания - вниз и налево (это показано стрелками, направленными от основной прямой в сторону убывания ). При других знаках коэффициентов и направление возрастания меняется. Случаи различных направлений убывания показаны на рис 2.9, 2.10, 2.11
Таким образом, и направление основной прямой , и направление возрастания линейной формы определяются величинами и знаками коэффициентов и при свободных переменных в выражении .
Дадим теперь геометрическую интерпретацию нахождения оптимального решения ОЗЛП среди допустимых.
Пусть имеется область допустимых решений ОДР (рис 2.12) и основная прямая ; известно (указано стрелками) направление убывания линейной формы .
При перемещении основной прямой в направлении, указанном стрелками, линейная форма будет возрастать. Очевидно, наибольшего значения она достигнет, когда прямая будет проходить через крайнюю точку ОДР, наиболее удаленную от начала координат в направлении стрелок (в нашем случае, точку А). Координаты этой точки 
, 
и определяют оптимальное решение ОЗЛП. Зная оптимальные значения свободных переменных , можно найти, подставляя их в уравнения (3.2), и оптимальные значения базисных переменных:
а также оптимальное (максимальное) значение линейной функции L:
(3.8)
Таким образом, если число независимых уравнений-ограничений, которым должны удовлетворять переменные 
, на два меньше, чем число переменных n (т. е. в ОЗЛП фигурируют две свободные переменные и любое число базисных), решение ОЗЛП может быть получено простым геометрическим построением.
Пример
Задача линейного программирования с семью переменными
,
Имеет m=5 уравнений-ограничений:
Найти оптимальное решение ОЗЛП, обращающее в минимум линейную функцию семи неизвестных
(3.9)
Решение
Уравнения-ограничения разрешены относительно базисных переменных 
, которые выражены через свободные 
:
(3.10)
Подставляя эти выражения в (3.9) и приводя подобные члены имеем:
. (3.11)
Область допустимых решений:
Отбрасывая свободный член в (3.11), имеем:
.
Строим основную прямую . Для этого откладываем отрезки 
по оси абсцисс и 
по оси ординат, проводим через точку В с координатами(-2, 5)прямую и отмечаем стрелками направление убывания 
Перемещая основную прямую параллельно самой себе в сторону убывания 
, наименьшее значение мы получим в точке А (наиболее удаленной от начала координат в направлении стрелок). Координаты этой точки , и дают оптимальное решение ОЗЛП. В точке А пересекаются две ограничивающие прямые: 
Приравнивая нулю выражения для 
и 
, получим два уравнения:
Решая их совместно, найдем 
Подставляя эти значения в (3.11), найдем оптимальные значения базисных переменных:
Что касается 
, то их оптимальные значения равны нулю: 
и 
.
Подставляя найденные оптимальные значения 
в линейную функцию (3.11), найдем минимальное значение (оптимум) линейной функции L:
Таким образом, мы научились решать ОЗЛП в частном случае m=n-2 при помощи геометрического построения.
Несмотря на то, что это построение относится к частному случаю, из него вытекают некоторые общие соображения, относящиеся вообще к свойствам решения ОЗЛП.
Отметим подмеченные нами закономерности для случая n-m=2:
1. Решение ОЗЛП, если оно существует, не может лежать внутри области допустимых решений, а только на ее границе.
2. Решение ОЗЛП может быть и не единственным (см. рис. 2.14).
Действительно, если основная прямая параллельна той стороне многоугольника допустимых решений, где достигается минимум , то он достигается не в одной точке, а на всей этой стороне. В этом случае ОЗЛП имеет бесчисленное множество оптимальных решений.
3. ОЗЛП может не иметь решений даже в случае, когда существует ОДР (рис. 2.15). Это бывает тогда, когда в направлении стрелок ОДР неограничена, т. е. в области допустимых решений линейная функция 
неограничена сверху. Перемещая основную прямую в направлении стрелок, мы будем получать все большие и большие значения , а значит и 
.
4. Решение ОЗЛП, максимизирующее функцию (оптимальное решение), всегда достигается в одной из вершин многоугольника допустимых решений (если оно достигается на целой стороне, то оно же
достигается и в каждой из вершин, через которые проходит эта сторона). Решение, лежащие в одной из вершин ОДР, называется опорным решением, а сама вершина – опорной точкой.
5. Для того, чтобы найти оптимальное решение, в принципе достаточно перебрать все вершины ОДР (опорные точки) и выбрать из них ту, где функция 
достигает максимума.
6. Если число свободных переменных в ОЗЛП равно 2, а число базисных – m и решение ОЗЛП существует, то оно всегда достигается в точке, где, по крайней мере, две из переменных обращаются в нуль. Действительно, в любой опорной точке пересекаются по крайней мере две из ограничивающих прямых; могут же в ней пересекаться и более двух (см. рис.2.16).
Случай, когда в оптимальном решении обращаются в нуль не две, а больше переменных, называется вырожденным. На рис. 2.16 показан вырожденный случай, когда в точке А, соответствующий оптимальному решению, обращаются в нуль три переменные: 
Рассмотрев подобную геометрическую для случая m=n-2, обратимся к случаю, когда число переменных превышает на 3 число независимых уравнений-ограничений: m=n-3.
В этом случае свободных переменных оказывается уже не две, а три (пусть это буду х1,х2,х3), а остальные m=n-3 базисных переменных могут быть выражены через свободные:
(3.12)
Требуется найти такие неотрицательные значения х1,х2,…,хn, которые, удовлетворяя уравнениям (3.12), одновременно обращали бы в минимум линейную функцию этих переменных:
(3.13)
Геометрическую интерпретацию этой задачи придется строить уже не на плоскости, а в пространстве (рис. 2.17). Каждое условие хk =0 для одной из базисных переменных хk (k=4,…,n) геометрически изобразится уже не прямой, а плоскостью. По одну сторону от этой плоскости хk>0, по другую хk <0. Координатные плоскости х20х3,х10х3 и х10х2 изображают условия х1=0, х2=0, х3=0 соответственно. Область допустимых решений (если она существует) представляет собой выпуклый многогранник, ограниченный этими плоскостями, т.е. часть пространства, для которой выполнены все условия:
х1≥0, х2≥0, х3 
0, …, хn≥0.
Роль «основной прямой» в этом случае будет играть «основная плоскость», уравнение которой L’=0, где
При перемещении этой плоскости параллельно самой себе в одну сторону L’ будет убывать, в другую – возрастать. Точка А, в которой достигается оптимальное решение (если оно существует), представляет собой ту вершину ОДР, которая находится дальше все от начала координат, считая по направлению возрастания L’. Может оказаться, как и при n-m=2, что ОЗЛП имеет бесчисленное множество решений, либо заполняющих целое ребро, либо – целую грань многогранника допустимых решений. Оптимальное решение х1*,х2*,х3* (если оно существует) совпадает с одной из опорных точек, т.е. вершин многогранника, в которой, по крайней мере, три переменных х1,х2,….,хn обращаются в ноль.
Пользоваться геометрической интерпретацией для непосредственного отыскания решения даже при n-m=3 затруднительно, при n-m=k>3 это вообще выведет нас за рамки трехмерного пространства, и геометрическая интерпретация потеряет наглядность. Однако соответствующая терминология может оказаться удобной: можно говорить об области допустимых решений, как о некотором «сверхмногограннике» в пространстве k измерений, ограниченном m «гиперплоскостями»; об оптимальном решении – как об одной из «вершин» этого многогранника, о каждой «вершине» - как об «опорной точке» и т.д. Такой геометрической терминологией можно, по желанию, пользоваться или не пользоваться. Можно сформулировать следующие свойства решения ОЗЛП при любых значениях числа переменных n и числа уравнений m<n:
1. Оптимальное решение, если оно существует, лежит не внутри, а на границе области допустимых решений, в одной из опорных точек, в каждой из которых, по крайней мере, k из переменных обращается в нуль.
2. Для того чтобы найти оптимальное решение, нужно, переходя от одной опорной точки к другой, двигаясь в направлении увеличения линейной функции L, которую требуется максимизировать.
На этих принципах и будут основаны решения ОЗЛП, которые изложены в дальнейшем.
