лекции. Лекции_МО_20. Лекции по методам оптимизации Тема Общая постановка задачи линейного программирования (2часа)

• Название: Лекции по методам оптимизации Тема Общая постановка задачи линейного программирования (2часа)
• Анкор: лекции
• Дата: 12.02.2022
• Размер: 254.78 Kb.
• Имя файла: Лекции_МО_20.docx
• Тип: Лекции; #359380
• страница: 2 из 9



 a₂₂ x₂

 ...  a_2nx_n

• 
  ^xn2
  

 b₂
(16)

_... ... ... ... ... ... ...

_^a_m1 x₁  a_m2 x₂  ...  a_mnx_n x_nm

 b_m

Примечание. В общем случае в системе ограничений могут быть и неравен- ства виде « ≤ » и неравенство виде « ≥». Во втором случае (« ≥ ») дополни- тельные переменные следует ввести со знаком « - ».

Вопросы для контроля

1. 
   Что такое экономико-математическая модель (ЭММ) задачи?
   
2. 
   Какая функция называется целевой или критериальной?
   
3. 
   Что называют планом задачи?
   
4. 
   Какой вид задачи называется стандартным?
   
5. 
   Какой вид задачи называется каноническим?
   
6. 
   Для чего используются дополнительные неотрицательные перемен- ные?
   
7. 
   В каком случае дополнительные переменные вводятся со знаком « - », и в каком случае со знаком «+»?
   

Тема 2. Геометрический метод решения задач линейного программиро- вания (2часа)

1. 
   Система m линейных уравнений с n переменными. Система mлинейных уравнений с nпеременными имеют вид:
   


^{a11x1  a12 x2  ...  a1nxn b1}

a
^ 21^x1



 a₂₂ x₂

 ...  a_2nx_n

 b₂
(1)

_... ... ... ... ... ... ...

_^a_m1 x₁  a_m2 x₂  ...  a_mnx_n

или просто

 b_m

n
^aij^xjj1

 b_i

(i 1,2,..., m)

В задачах линейного программирования представляют интерес системы,

в которых ранг rматрицы системы ^{A (aij),i 1, m, j 1, n,}

меньше числа

переменных, т.е. r‹n. Предположим, что в системе (2.1) r=m, m‹n.Определение. Любые mпеременных, cистемы mлинейных уравнений с nпеременными (m‹n) называется основными(или базисными), если определитель матрицы, состоящий из коэффициентов при этих mпере-

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

Тогда остальные n-mпеременных называется неосновнымиили свобод-ными.

Основными могут быть разные группы из mпеременных. Максимально возможное число групп основных переменных равно числу способов

выбора mпеременных из n, т.е. числу сочетаний

^Cm. Но могут быть

n
случаи, когда определитель матрицы при m переменных равен нулю,

тогда общее число групп основных переменных не превосходит

_Cm_.

n
Пример 1. Найти все возможные группы основных переменных в систе- ме:

_x₁  x₂  2x₃  x₄  0


(n 4, m 2).

_2x₁  x₂  2x₃  x₄  0
Решение.Общее число групп основных переменных не более чем



C
₂ 4!


⁴ 2!2!

 ¹²  6,

2

т.е. возможные группы основных переменных;

x₁ , x₂ ;

x₁ , x₃ ;

x₁ , x₄ ;

x₂ , x₃ ;

x₂ , x₄ ;

x₃ , x₄ .

Выясним, могут ли быть основными переменными матрицы при этих переменных

^{1 1}  1  2  3  0

x₁ , x₂ .

Определитель

2 1

Следовательно,

x₁ , x₂

могут быть основными. Поступая аналогично с

другими группами, можно определить все группы основных перемен- ных.

Теорема. Если для системы m линейных уравнений с n переменными (m‹n) ранг матрицы коэффициентов при переменных равен m , т.е. су- ществует хотя бы одна группа основных переменных, то это система яв- ляется неопределенной, причем каждому набору неосновных перемен- ных соответствует одно решение системы.

Пусть, например,

x₁ , x₂ ,..., x_m

основные переменные, т.е., определитель

матрицы отличен от нуля:

a₁₁ a₁₂ ...

_A a₂₁ a₂₂ ...
^a1m

^a2m _{ 0}

... ... ... ...

a_m1 a_m2 ...
^amm

Оставим в левых частях уравнений системы (1) члены с основными пе-

ременными

x₁,..., x_m,

а члены с неосновными переменными

x_m1 ,..., x_n

перенесем в правые части:

^a11^x1 ^{ a}12 ^x2 ^{...  a}1m^xm^{  b}1 ^{ a}1,m1 ^xm1 ^{ a}1,m2 ^xm2 ^{... a}1n^xn

^ax a x... a x  b a x  a x ... a x

 ^{21 1}



22 2

2m m

2 2,m1

m1

2,m2 m2

2n n

_... ... ... ...

... ... ... ... ... ... ... ... ... ... ... ... ... ...


^am1 ^x1 ^{ a}m2 ^x2

^{... a}mm^xm ^{ b}m^{ a}m,m1 ^xm1 ^{ a}m,m2 ^xm2 ^{... a}mn^xn

Задавая неосновным (свободным) переменным

x_m1 ,..., x_n

произволь-

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

стему с новыми свободными членами

b^' ,b^' ,...,b^' .

Каждая из полученных

1 2 m

систем будет иметь один и тот же определитель

^{A 0} , следовательно,

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

Пример 2. Решить систему уравнений:
^{x1  x2  2x3  x4  0}



_2x₁  x₂  2x₃  x₄  0

Решение. Выше установили, что переменные основными, поэтому возьмем их в качестве основных.

x₁ , x₂

могут быть

Тогда переменные x₃и x₄являются неосновными ( свобод-

ными).Члены с неосновными переменными перенесем в правую часть системы.
х₁-x₂=2x₃-x₄2x₁+x₂=-2x₃+x₄+2

Решая эту систему любым способом, получим:
х₁=
х₂=²₃ -2x₃-x₄

Задавая неосновным переменным х_3,х₄произвольные зна- ^{чения, например, x}3^=c1^{и x}4^=c2^{,получим бесконечное множество} решение этой системы:

^х1^{=2 3}
х₂=2 3 -2c₁+c₄

Решение x=(x₁…,x_n )системы (1) называется допустимым , если оно содержит лишь неотрицательные компоненты, т.е.x_j 0,j=1,n. В противном случае решение называется недопустимым. Так в данной

задаче решение системы при c₁=2,c₂=5,получим x=(2/3;⁵ ;2;5)является

3

допустимым, а при c₁=2,c₂=1,x=( 2 3 ;- ⁷ ;2;1) является недопустимым.

3
Определение. Базисным решением системы m линейных урав- нений с nпеременными называется решение, в котором все n-mнеос- новных переменных равны нулю. Допустимые базисные решения еще называются опорными.

Число базисных решений конечное, т.к. оно равно числу груп-

пы основных переменных, не превосходящему

^Cm.Базисное решение,

n
в котором хотя бы одна из основных переменных равна нулю, называ- ется вырожденным.

Пример 3. Найти все базисные решения системы, приведенной

выше.

Решение. Было установлено, что существует три группы основ-

ных переменных x₁,x₂;x₁,x₃;x₁,x₄, т. е, число базисных решений рав- но трем.

1. 
   Основные переменные - x₁,x₂, неосновные переменные - x₃,x₄.
   

x₁-x₂=0 x₁=x₂2x₁+x₂=2 x₂=2\3,x₁=2/3

Первое базисное решение Х₁=(2/3;2/3;0;0) допустимое.

2. 
   Основные переменные x₁,x₃; неосновные переменные x₂,x₄x₁-2х₃=0 x₁=2x₃
   

2x₁+2x₃=2 6x₃=2; x₃=¹ ; x₁=²

3 3

2. 
   е базисное решение Х₂=(2/3;0;1/3;0) .
   

3. 
   Основные переменные x₁,x_4;
   

Неосновные переменныеx₂,x₃.x₁+x₄=0 x₁= -x₄

2x₁-x₄=2 -2x₄-x₄=2;x₄=-² ;x₁=²

3 3

2. 
   е базисное решение Х₃=( ² ;0;0;- ² ) является недопустимым
   

3 3

решением.

2. 
   Выпуклые множества точек
   

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

Примеры:

Теорема.Пересечение (общая часть) любого числа выпуклых множеств также есть выпуклое множество.

Среди точек выпуклого множества можно выделить внут- ренние, граничные и угловые точки.

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

ему. Особый интерес в линейном программировании вызывают угловые точки.

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

Если множество есть многоугольник, то его вершины являются угло- выми точками.

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

Мы рассмотрим выпуклые множества точек на плоскости и в пространстве, т.е. такие точки изображаются парой чисел (x₁,x₂).или тройкой чисел(x_1,x_2,x₃).Теперь обобщим это понятие для n - мерных то- чек (x₁,x₂,…,x_n). Обобщением понятия отрезка для нескольких точек яв- ляется их выпуклая комбинация.

Определение. Точка Xназывается выпуклой линейной комбина- цией точек x₁,x_2,…,,x_n, если выполняется условие:


n

X= ₁x₁+_{ 2}x₂+….+ _nx_n,
 _{j 0},j=1,2…,n,_ a 1

j1
В частном случае, при n=2 выпуклой линейной комбинацией двух точек является соединяющий их отрезок.

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

3. 
   Свойства задачи линейного программирования
   

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

F c₁x₁  c₂ x₂  ...  c_nx_n max

при ограничениях

^{a11x1  a12x2  ...  a1nxn b1}

(min) (1)

^ax a x ...  a x b

(2)

^ 21 1



22 2

2n n 2

_... ... ... ... ... ... ...

^_a_m1 x₁  a_m2 x₂  ...  a_mnx_n b_m.

Матричная форма записи

F=C·X max (min) (3)

при ограничениях

AX=B, (4)

X 0. (5)

где С=(с₁,с₂,…,с_n),

 ^{a ... a} 

 ^x₁ 

 ^b₁ 

_ 11

1n _

   

x b


_A ^{ a}21

...

...

...
...

^a2n <sup>

</sup> ,

 ₂ 






^X _.  <sub>,

B</sub>  ₂ 

_. .



a ...



...a

   

x b

 m1

mn 

 n

 m

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

ной угловой точке, то она принимает его в любой точке, являющейся выпук- лой комбинацией этих точек.

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

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

Геометрический метод удобен при n=2или n=3.Нам известно, что множество допустимых решений (многогранник решений) задачи линейного программирования представляет собой выпуклый много- гранник, а оптимальное решение задачи находится в одной из угловых точек многогранника.

Геометрический метод имеет два подхода:

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

Определение. Линия уровня функции - это линия, на которой данная функция имеет постоянное значение.

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

F

при

 c₁x₁  c₂ x₂  max (min)

(1)

^^a11x1



 a₁₂x b₁
(2)

^_a₂₁x₁  a₂₂x₂  b₂

и x₁^ 0, x₂^ 0 (3)

При n>m,к такой форме может быть приведена и задача в основной форме. Пусть в геометрическом изображении системы ограничений есть многоугольник ABCDE:


Пример. Решить геометрически задачу:

2x₁+3x₂ max
при ограничениях:

x₁+3x₂ 18

2x₁+ x₂ 16

х₂ 5, 3x₁ 21,х₁≥0,х₂≥0.

Данные ограничения геометрически образуют следующую область:


Пусть начальная линия уровня

^{F 2x1  3x2  0.} ,

т.е. она проходит через начало координат. Теперь зададим,

например, F=6,и построим линию уровня

2x₁  3x₂

^{ 6} .

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

x₁  3x₂ 2x₁  x₂

 18

 16

x₁  18  3x₂ 36  6x₂  x₂

 16 

x₁  6,
x₂  4

Максимум Fпри этом

^Fmax

^{ 2  6  3 4  24} .

Вопросы для контроля

1. 
   Что такое ранг матрицы?
   
2. 
   Какие переменные называются основными (базисными)?
   
3. 
   Какие переменные называются неосновными (свободными)?
   
4. 
   Что такое допустимое решение задачи линейного программирова- ния?
   
5. 
   Какое решение называется базисным?
   
6. 
   Какое решение называется вырожденным?
   
7. 
   Среди каких решений находится оптимальное решение задачи ЛП?
   
8. 
   Что такое многогранник решений?
   
9. 
   Где находятся базисные решения задачи ЛП относительно много- гранника решений?
   
10. 
    Какая область является выпуклой?
    

1. 
   В каких случаях удобно пользоваться геометрическим методом решения задач ЛП?
   
2. 
   Что такое линия уровня?
   
3. 
   В какой точке многогранника (многоугольника) решений нахо- дится оптимальное решение задачи ЛП?
   
4. 
   Как можно найти направление возрастания (убывания) целе- вой линейной функции?