Симплекстік түрлендіру



Дата18.04.2023
өлшемі20,36 Kb.
#83684
Байланысты:
лекция 7


Симплекстік түрлендіру

Мәселені шешу теріс симплекс айырмашылықтары жойылғанға дейін бір тірек жоспарынан екіншісіне ауысудан тұрады. Бұл ауысу Джордан-Гаусс түрлендірулері арқылы жүзеге асырылады. Бұл ретте симплекс-айырмашылықтар жолы басқа жолдар сияқты ережелер бойынша қайта есептеледі.


Мүмкіндік-шешуші элементті таңдау әдісі.
Рұқсат етілген баған ретінде теріс симплекс айырмашылығы бар баған таңдалады(бұл L сызықтық формасының өсу шарты).
Егер (-) белгісі бар бірнеше симплекс айырмашылықтары болса, онда модуль бойынша ең үлкен мәні бар ∆ ( - ) баған таңдалады.
Рұқсат етілген жол ретінде bi/aik қатынасы таңдалған баған үшін ең аз мәнге ие болады (бұл жоспардың анықтамалығын сақтау шарты).
Бұл жағдайда тек оң жақтары ескеріледі aik .
Теріс симплекс айырмашылықтары бар барлық бағандарда оң aik элементтерінің болмауы L сызықтық формасының шектеусіздігін көрсетеді.
Тапсырманы симплексті әдіспен шешудің мысалы.
Функцияны барынша арттыру L = x1 + 7x2 +2x3 + x4 – x5max
шектеу кезінде 6x1 + 3x2 +x3 + x4 + x5 = 20
4x1 + 3x2 +x4 = 12
3x1 - 2x2 + x5 = 6
xi ≥ 0 , i=1÷5
Шешім. Кестеге жазайық

 A1 

A2 

A3 

A4 

A5 

B

6

3

1

1

1

20

4

3

0

1

0

12

3

-2

0

0

1

6

Рұқсат етуші элемент ретінде a24=1 алыңыз, өйткені
min{12/1 и 20/1}=12.
Джордан-Гаусс әдісімен барлық элементтерді түрлендіре отырып, біз келесі кестені аламыз:
Рұқсат етуші элемент ретінде a35=1алыңыз. біз кесте аламыз:
Анықтамалық шешім:
X = (0,0,2,12,6)



A1 

A2 

A3 

A4 

A5 

B

2

0

1

0

1

8

4

3

0

1

0

12

3

-2

0

0

1

6


A1 

A2 

A3 

A4 

A5 

B

-1

2

1

0

1

2

4

3

0

1

0

12

3

-2

0

0

1

6

Алынған анықтамалық шешім үшін бірінші симплекс кестесін құрайық:

 Баз.

Сбаз 

B

1
A1 

7
A2 

2
A3 

1
A4

-1
A

A3

2

2

-1

2

1

0

0

A4 

1

12

4

3

0

1

0

A5 

-1

6

3

-2

0

0

1


L=

10

-2

2

0

0

0

Соңғы жолда теріс сан бар  алынған тірек жоспары оңтайлы емес.
(-)бағандағы симплекс жолындағы сан A1. Бұл x1 айнымалысын негізге енгізу керек дегенді білдіреді.
Ал негізден қандай айнымалы алу керек?
min{12/4;6/3}=2 табамыз  айнымалыны шығару x5 . Р.Э. a31=3
 Аламыз L = 6x1 - x2 +2x3 - М x5max
4x1 + x2 +x3 + x5 = 8
2x1 - x2 +x3 + x4 = 6
xi ≥ 0 , i=1÷5
Симплекс кестесін құру
Жоспар оңтайлы емес, өйткені симплекс жолында ( - ) элементтер бар. Модуль бойынша ең үлкені ретінде A1 рұқсат бағанын таңдаңыз
теріс симплекс айырмашылығы. Біз қатынасты табамыз bi / ai1 : 8/4 < 6/2 
Рұқсат жолы бірінші, ал рұқсат элементі а11 =4. Бұл
 бұл жаңа жоспарда х5 негізден шығады, ал x1 негізге енеді дегенді білдіреді.
 Симплекс түрлендірулер жаңа тірек жоспарын береді:

Баз

Сбаз 



6
A1 

-1
A2 

2
A3 

0
A4 

-M
A5 

A

-M

8

4

1

1

0

1

A

0

6

2

-1

1

1

0



-M 

-4M-6

-M+1

-M-2

0

0


Сызықтық пішін өсті (L=12), Бірақ алынған жоспар әлі оңтайлы емес. Теріс симплекс айырмашылығы бар. Жаңа рұқсат элементін таңдаңыз a23 =1/2. Жасанды X5 айнымалысы негізден шықты5 бағанын қарастырудан алып тастауға болады. Симплекс түрлендірулер жаңа тірек жоспарын береді:
Симплекс-жол-оң. Алынған жоспар оңтайлы.
X = (1;0;4;0) , L = 14 нәтиже болып табылады.

Баз

Сбаз 



6
A1 

-1
A2 

2
A3 

0
A4 

A1 

6

1

1

1

0

-1/2

A3 

2

4

0

-3

1

2


L= 

14

0

0

0

1


Достарыңызбен бөлісу:




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет