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

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

Тема 4. Симплексные таблицы (2 ч)

1. Применение симплексных таблиц

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

Пусть решается задачи максимизации.

1. 
   После введения дополнительных переменных систему уравнений и целевую функцию записываем в виде, который называется расширенной системой:
   

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

a
_ 21^x1

 a₂₂ x₂

 ...  a_2nx_n

 b₂

_..............................................

a

x


_ m1 1

a_m2 x₂

• 
  ...  a_mnx_n
  

 bm

_F c₁ x₁  c₂ x₂  ...  c_nx_n 0
Предполагаем, что все дополнительные переменные имеют тот же знак, что и свободные члены, в противном случае используется M-метод, который рассмотрим позже.

2. 
   Исходную расширенную систему заносим в первую симплексную таблицу. Последняя строка таблицы, в которой приведено уравнение для целевой линейной функции, называется оце- ночной .
   

В ней указываются коэффициенты целевой функции с противопо-

ложным знаком

f_i  c_i.

В левом столбце таблицы записываются основные переменные (ба- зис), в первой строке таблицы – все переменные (отмечая при этом основные), во втором столбце - свободные члены расширенной си-

стемы ^{b1,b2 ,...,bm}.

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

В рабочую часть таблицы (начиная с третьего столбца и второй

строки) занесены коэффициенты

^aij

при переменных. Далее табли-

ца преобразуется по определенным правилам.

3. 
   Проверяем выполнение критерия оптимальности при реше- нии задачи максимизации - наличия в последней строке отри-
   

цательных коэффициентов

f_i  0(c_i

• 
  ^0).Если таких нет, то
  

решение оптимально, достигнут max F=C ₀ (в левом нижнем углу таблицы), основные переменные принимают значения

^ai0

(второй столбец - свободные члены), неосновные пере-

менные равны 0, то есть получено оптимальное базисное ре- шение.

4. 
   Если критерий оптимальности не выполнен, то наибольший
   

по модулю отрицательный коэффициент

f_i 0

в последней

строке определяет разрешающий столбецs.

Составим оценочные ограничения по следующим правилам :

1. 
   ∞, если ^bi
   

^{и a}is

имеют разные знаки;

2. 
   ∞, если
   
3. 
   ∞, если
   
4. 
   0, если
   

^b_i =0, ^a_is = 0 ^b_i=0,

^ais<0
^a_is>0

5. 
   если b_iи a_isимеют одинаковые знаки.
   




Определяем min ^{ }

 
Если конечного минимума нет, то задача не имеет конечного оптимума и

^Fmax

 _.

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

5. 
   Переходим к следующей таблице по правилам :
   

А) В левом столбце записываем новый базис: вместо основной переменной

^x_q-переменную

x_s.

Б) В строке функции F, клетках находящихся напротив основных перемен- ных из общего списка переменных, проставляем нули.

В) Проставляем единицы – в «своих» клетках (в клетках, находящихся на пересечении каждой основной переменной из столбца основных – базисных переменных с этой же переменной из строки переменных), нули в «чужих» клетках ( в клетках, находящихся на пересечении каждой основной перемен- ной из столбца базисных переменных с другой основной переменной из строки переменных);

Г) Новую строку с номером qполучаем из старой, делением на разрешаю-

щий элемент

^aqs_.

Д) все остальные элементы

^a_ijвычисляем по правилу прямоугольника, на

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

^ais^{ a}qj

^aij

 a_ij _a ^{ }

^qs    a a

  

• 
  ij ^ is
  

 

b ^  b

• 
  a_is b_q
  

   a a

  

ij i

^aqs

• 
  qj ^ qs
  

Далее переходим к пункту III алгоритма.

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

Решение.Расширенная система задачи имеет вид:

<sup>x1  3x2  x3  18

</sup>2x x x 16

_ 1 2 4

_x₂  x₅  5

^3x x 21

_ 1 6

^_F 2x₁  3x₂  0

Заполняем первую симплексную таблицу, в которой переменные. Смотрим пункт II алгоритма.
^{x3 , x4 , x5 , x6 } основные

Таблица №1

Базис	Свободный член	Переменные							Оценочное отношение
		Х1	Х2		Х3	Х4	Х5	Х6
X3	18	1	3		1	0	0	0
X4	16	2	1		0	1	0	0
X5	5	0	1		0	0	1	0
X6	21	3	0		0	0	0	1
F	0	-2	-3		0	0	0	0

В соответствии с п. III алгоритма, проверяем критерий оптимальности (нали- чие отрицательных коэффициентов в последней строке таблицы). В послед- ней строке таблицы имеются отрицательные коэффициенты. Выбираем из них наибольший по модулю (-3), поэтому второй столбец разрешающий: пе- ременная х₂переходит в основные. В соответствии с п. IV находим оценоч-

ное отношение и х₂=

Третья строка является разрешающей (отмечена горизонтальной стрелкой). На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент а₃₂=1.

Строим таблицу 2 в соответствии с п. V алгоритма:

А) Новое деление переменных: основные переменные x₃, x₄,x₂,x₆; неоснов- ные x₁,x₅.

Б) В последней строке, в клетки находящиеся напротив основных перемен- ных x₃,x₄,x₂,x₆, вставляем нули.

В) Каждый элемент 3-й строки (разрешающей строки) делится на разрешаю- щий элемент и пишутся в эту строку новой таблицы ( табл.№2).

Г).Все остальные элементы находим по правилу прямоугольников:

b'₁

 18  ^{5  3}  3,

1

^'  16  ^{5 1}  11,


b
2 ₁

^'  21  ^{5  0}  21.


b
4 ₁

a^'  1  ^{0 1}  1, a^'  2  ^{0 1}  2, a^'  3  ^{0  0}  3, f^'  2  ^{(3)  0}  2.

1 ₁ 2 ₁ 4 ₁ 1 ₁

F 0  ^{(3)  5}  15.

1 ₁
Таким образом, получим следующую таблицу, соответствующую второму базисному допустимому решению:

Таблица №2

Базис	Свободный член	Переменные								Оценочное отношение
		Х1			Х2	Х3	Х4	Х5	Х6
X3	3		1		0	1	0	0	0
X4	11	2			0	0	1	0	0
X2	5	0			1	0	0	1	0		
X6	21	3			0	0	0	0	1		27 3 =7
F	15	-2			0	0	0	3	0

↑

Критерий оптимальности не выполнен, так как в последней строке имеется

отрицательный элемент, поэтому 1-й столбец разрешающий; основные.

^x₁  min{3;5;5;7}  3_,

^x₁ переходит в

Это достигается в первой строке, поэтому 1-я строка разрешающая – х_3пе- реходит в неосновные.

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

2. 
   М-метод (Метод искусственного базиса)
   

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

В каждое уравнение, дающее отрицательную компоненту в базисном реше- нии, вводим свою новую неотрицательную искусственную переменную

y₁, y₂ ,..., y_к , которое имеет тот же знак, что и свободный член в правой части уравнения. В первой таблице, включаем в число основных все искусственные переменные и те обычные дополнительные переменные, которые определя- ют неотрицательные компоненты базисного решения.

Составляем новую линейную функцию.

T F  M( y₁  y₂  ...  y_к),

где М - произвольное большое число, и ищем максимум функции Т. Это

называется еще Т- задачей. Выражение функцией.

Имеет место следующая теорема:

M( y₁  y₂  ...  y_k)

называется М –

1. 
   Если в оптимальном решении Т – задачи все искусственные пере- менные равны 0, то соответствующие значения остальных переменных дают
   

оптимальное решение исходной задачи, т.е. т.е. min M – функции равен 0.

^Tmax ^{ F}max ^,

если

y₁  y₂  ...  y_R 0.

2. 
   Если имеется оптимальное решение Т – задачи, в котором хотя бы
   

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

3. 
   Если T_max  , то исходная задача также неразрешима, причем либо
   

F_max  , либо условия значения противоречивы.

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

Пример: Пусть решается задача

F x₁  2x₂  max

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

<sup>x1  x2  1

</sup>x x 3

^ 1 2

^x 3

 ¹

x₁ , x₂  0
_x₁  x₂  x₃  1

^x x  x  3

^ 1 2 4

^x x 3

 ^{1 5}
X₁  (0;0;1;3;3) _-

недопустимое базисное решение

В 1-е уравнение введем переменную у₁, с тем же знаком, что и сво- бодный член:

^{x x  x  y}

 1

^{ x1  x2  x3  y 1}

1 2 3 1

^ x x x 3

^x x  x  3

_или ^ 1 2 4

^ 1 2 4

^x x 3

^x x  3

 ^{1 5}

 ^{1 5}

F x₁  2x₂  0 ^{T x}₁ ^{ 2x}₂ ^{ My}₁ ^{ max}

Базис	Сво б. член	Переменные
		x1	x2	x3	x4	x5	y1
y1	1	-1	1	-1	0	0	1	1
x4	3	-1	1	0	1	0	0	3
x5	3	1	0	0	0	1	0	
F	0	-1	-2	0	0	0	0	max
Mф	-M	M	-М	M	0	0	-M	max



Последняя строка (-М) функция равна (- ^(M_ф^{)  y}₁

Последняя строка это (-М) функция, т.е

• 
  M_ф y₁
  

. Заполняем ее,

умножая строку

^y₁ на (-М).

Проверяем выполнение критерия оптимальности при максимизации (-М) функции. В строке для –M_фимеется отрицательный элемент во вто-

ром столбце, он и разрешающий , переменная

^x₂ переходит в основные.

Находим оценочное отношение: минимальное отношение находятся в первой

строке, она и разрешающая. Разрешающий элемент

a₁₂  1, переменная

y₁ пе-

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

В соответствии с общим алгоритмом получим следующую таблицу:

Базис	Св. чле- ны	Переменные
		x1	x2	x3	x4	x5	Оц. Отн

x2	1	-1	1	-1	0	0	
x4	2	0	0	1	1	0	
x5	3	1	0	0	0	1	3 
F	2	-3	0	-2	0	0
Mф	0	0	0	0	0	0

Последняя строка показывает, что критерий оптимальности при мак-

симизации - M_ф выполнен: max (- M_ф)=0, значит min M_ф=0, далее эту строку

не рассматриваем.

Получено допустимое базисное решение
X₁  (0;1;0;2;3) .

Начиная с этого решаем задачу по обычному алгоритму. Критерий оп- тимальности для F не выполнен, имеются два отрицательных элемента; Возьмем столбец, в котором коэффициент при х₁отрицательный: -3 он и

разрешающий, следовательно

^x1 переходит в основные. Строка, в которой

минимальная оценка (3) – разрешающая, разрешающий элемент

a₃₂  1

Как видно, переменная

^x5 переходит в неосновные.

Получим следующую таблицу:

Ба- зис	Св. член	Переменные
		x1	x2	x3	x4	x5	Оцен . отн-е
x2	3	0	1	- 1	0	1	
x4	2	0	0	1	1	0	2
x1	3	1	0	0	0	1	
F	11	0	0	- 2	0	3

x₃ - в основные,



x₄ - в неосновные.
a₂₃  1.

Ба- зис	Св. член	Переменные
		x1	x2	x3	x4	x5	Оцен .

							отн-е
x2	5	0	1	0	1	1
x3	2	0	0	1	1	0
x1	3	1	0	0	0	1
F	15	0	0	0	2	3

Т.о. получили оптимальное решение:

F_max=15;

X=(3;5; 2;0; 0).

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

1. 
   Как составляется расширенная система ограничений?
   
2. 
   Каким образом заполняем первую симплексную таблицу?
   
3. 
   Как проверяется критерий оптимальности решения?
   
4. 
   Какой столбец называется разрешающим столбцом?
   
5. 
   Какая строка является разрешающей?
   
6. 
   Что такое «свои» и «чужие» клетки?
   
7. 
   Расскажите о правиле прямоугольников при заполнении некото- рых клеток новой симплексной таблицы.
   
8. 
   В каких случаях используется М – метод?
   
9. 
   Для чего применяются искусственные переменные? 10.Что такое Т – задача?
   

11. 
    Как составляется М – функция?
    
12. 
    При каких значениях искусственных переменных, Т – задача имеет оптимальное решение?
    
13. 
    В каком случае система ограничений задачи является несовмест- ной?
    
14. 
    Когда исходная задача является неразрешимой?