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

 

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

Начнем рассмотрение геометрического отображения с одного уравнения с двумя переменными:

2х1+х2=2.

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

Для нахождения точек пересечения прямой с осями координат можно, поочередно, прировнять каждую из переменных к нулю и вычислить значение второй, а затем проделать эту процедуру в обратном порядке. Для рассматриваемого уравнения имеем: х1=1; х2=2. Эти координаты определяют на графике положение искомой прямой (рис 2.1).

       
 
   
Возможен и другой путь нахождения значений координат. Для этого нужно просто разделить обе части уравнения на его свободный член. Применительно к рассматриваемому примеру: При такой форме записи в значениях переменных показаны отрезки, которые отсекает прямая на осях координат. Если от рассмотренного уравнения перейти к неравенству вида: 2х1+х2 ≤ 2, (2.15) то его можно представить графически, как это показано на рис. 2.2  
 

х2

 

 


 

х1

 

0 1 2 3

 

Рис.2.1

 

 

Из приведенных рисунков видно, что если линейное уравнение с двумя неизвестными представляет собой прямую линию, то линейное неравенство – полуплоскость. На рисунке 2.2 часть плоскости, которая удовлетворяет неравенству и расположена ниже прямой, заштрихована. Координаты всех точек, принадлежащих заштрихованной плоскости, имеют такие значения х1 и х2, которые удовлетворяют заданному неравенству. Эта полуплоскость является областью допустимых решений (ОДР). Введем в рассматриваемый пример дополнительное условие неотрицательности переменных присущее задачам линейного программирования, т.е. х1≥0; х2≥0. в этом случае ОДР ограничится площадью заштрихованного треугольника (рис 2.3).  
2

 

3

 


 

1

х1


0 1 2 3

 

Рис. 2.2

 

х2

Зададимся теперь системой неравенств: 2х1+2х2 ≤ 12 х1+2х2 ≤ 8 (2.16) 4х1 ≤ 16 4х2 ≤ 12 х1≥0; х2≥0 Для удобства графического построения перепишем систему, разделив каждое неравенство на его свободный член:  

3

 


 

1

х1


0 1 2 3

Рис. 2.3

 

(а)

(б)

(в)

(г)

х1≥0; х2≥0

В результате построения (рис 2.4) определилась область допустимых решений системы, представленная в виде заштрихованного выпуклого многоугольника с вершинами АВСDЕ. Поскольку в ОДР бесчисленное множество точек, то рассматриваемая система имеет бесчисленное множество допустимых решений. Для нахождения оптимального решения нужно задаться уравнением целевой функции.  
2

 

7

6

а

5 в

3 Е D г

С

2

1 б х1

А В

1 2 3 4 5 6 7 8 9

Рис. 2.4

 

Пусть:

Z = 20х1 + 30х2 Зададимся некоторым произвольным значением целевой функции, вычислим относительно него значения х1 и х2, а затем построим на графике линию целевой функции: 20х1+30х2=90; х1=4,5; х2=3. При задании других значений целевой функции на графике проводились бы соответствующие им прямые, параллельные изображенной. Исходя из этого, для нахождения максимума (оптимального решения), следует перемещать параллельно самой себе прямую целевой функции до соприкосновения ее с наиболее удаленной от начала координат вершиной многоугольника ОДР. В нашем примере это вершина С, для которой Z=140 (х1=4, х2=2). Можно было бы найти оптимальный вариант решения и другим способом. С этой целью следовало бы вычислить значения целевых функций для всех вершин многоугольника, а затем выбрать из них наибольшую. Для условий нашего примера ZA=0 (х1=0, х2=0); ZВ=80 (х1=4, х2=0); ZС=140; ZD=130 (х1=2, х2=3); ZЕ=90 (х1=0, х2=3). Оптимальное решение может быть и не единственным. При изменении величины коэффициента при х2 с 30 на 40 в уравнении целевой функции, наибольшие и равные между собой значения целевой функции будут получены в вершинах С и D (ZC=ZD=160). Такой же результат может быть найден для любой точки стороны многоугольника, соединяющей названные вершины. Эти варианты решений будут различаться значениями входящих в них переменных, но будут характеризоваться одной и той же величиной целевой функции. Такие решения называются равнооптимальными. В заключение приведем обобщенное обоснование возможности применения графического метода решения задач линейного программирования. Такой метод может быть использован при выполнении условия n-m=2, применительно к канонической форме записи системы ограничений. Например, приведение неравенства (2.15) к указанной форме потребовало бы введения одной дополнительной переменной. При этом будет одно уравнение (m=1) и три переменных (n=3), т.е. n-m=2. Аналогично, при приведении системы (2.16) к канонической форме – m=3, n=5 и n-m=2. В общем случае, для любого количества уравнений и переменных, выполнение указанного условия обеспечит получение графического решения на плоскости. При этом две любые переменные принимаются в качестве свободных. Все остальные переменные рассматриваются как базисные и выражаются через свободные. В результате обеспечивается построение многоугольника ОДР в системе прямоугольных координат.  

 

 

 

 

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

1. Представить графически систему ограничений:

х1+х2≤2 х1≥0, х2≥0 Преобразуем систему: х1≥1, х2≥0
2

 

3

 


 

1

х1


0 1 2 3

Рис. 2.5

 

На рисунке 2.5 видно, что нет таких значений х1 и х2, которые бы удовлетворяли заданной системе ограничений. Следовательно, в данной системе отсутствует ОДР. Системы ограничений, подобные рассматриваемой, называют несовместимыми.

2. Построить систему:

х1 + х2 ≥ 1

х1 ≥ 0, х2 ≥ 0

х2

 

3

 

2


1

х1

1 2 3

Рис. 2.6

 

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

Решение общих задач линейного программирования при m-n=2 является частным практически крайне ограниченным случаем. Пользоваться геометрической интерпретацией для отыскания решения даже при n-m=3, т.е. в трехмерном пространстве, затруднительно. При n-m=k>3 геометрическая интерпретация теряет наглядность. Однако соответствующая терминология может оказаться удобной: можно говорить об области допустимых решений, как о некотором «сверхмногограннике» в пространстве k измерений, ограниченном m «гиперплоскостями»; об оптимальном решении – как об одной из «вершин» этого многогранника, о каждой «вершине» — как об «опорной точке» и т.д.

Несмотря на то, что построение для m-n=2 относится к частному случаю, из него вытекают определенные выводы, относящиеся вообще к свойствам решения основной задачи линейного программирования.

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

2. Оптимальное решение всегда достигается в одной из вершин многоугольника допустимых решений (если оно достигается на целой стороне, то оно же достигается и в каждой из вершин, через которые проходит эта сторона). Решение, лежащее в одной из вершин ОДР, называется опорным решением, а сама вершина – опорной точкой.

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

4. Задача может не иметь решения даже в случае, когда существует ОДР.

 

еще рефераты
Еще работы по информатике