Т математикалық программалау пәнін оқытуда әдістемелік нұсқаулар

жүктеу 5,07 Mb.

бет	7/46
Дата	08.02.2018
өлшемі	5,07 Mb.
	#9050
түрі	Программа

1 2 3 4 5 6 7 8 9 10 ... 46

Теорема 1.2. Егер сызықтық программалаудың негізгі есебінің ең тиімді жоспары бар болса онда ол шешімдер көпбұрышының қандай да бір төбесінде орналасқан. Егер мақсаттық функция өзінің максималды мәнін шешімдер көпбұрышының екі төбенің дөңес сызықты комбинациясы болатын кез-келген нүктеде де өзінің максимум мәнін қабылдайды.

Теорема 1.3. Егер P₁, P₂,…, P_k (k

n) векторлар жүйесі (9) теңсіздікте сызықты тәуелсіз және

х₁Р₁+х₂Р₂+...+х_кР_к=Р₀

болса, мұндағы барлық x_j0, онда X=(X₁; X₂;…;X_n; 0;...;0) нүктесі шешімдер көпбұрышының төбесі болып табылады.

Теорема 1.4. егер X=(X₁; X₂;…;X_n) шешімдер көпбұрышының төбесі болса, онда (10) теңсіздік дұрыс x_j –ге сәйкес P_jвекторлары сызықты тәуелсіз.

Сызықты программалау есебінің геометриялық түсінігі
Құрастырылған теоремалар келесі қорытындыларды жасауға мүмкіндік береді.

Сызықтық программалаудың негізгі есебінің жоспарының жиыны бос жиын болмаса, онда ол дөңес көпжақты құрайды. Осы дөңес көпжақтың әрбір төбесі тірек жоспарына сәйкес келеді. Осы аталған төбелердің бірінде яғни қандай да бір тірек жоспары үшін мақсаттық функцияның мәні оның максимумына тең болады. Демек бұл төбе оң тиімді жоспарды анықтайды.

Мақсаттық функция максимал мәнге ие болатын шешімдер көпбұрышының төбесін салыстрмалы түрде табу оңай, егер стандарттық түрде жазылған есептің екеуден көп емес айнымалысы бар болса немесе негізгі түрде жазылған есептің екеуден көп емес бос айнымалысы, яғни шектелген есептің жүйесінің коэфициенттерінен құралған n-r

2, мұндағы n- айнымалылар саны, r-матрица рангі, бар болса.

Мынандай есепті қарастырайық:

F=c₁x₁+c₂x₂

max (11)

шарттары

a_i1x₁+a_i2x₂b_i (i=

), (12)

(13)

(12) және (13) теңсіздіктің әрқайсысы геометрия тілінде жартылай жазықтықты анықтайды. Сондықтан (12), (13) теңсіздіктің жүйесінің шешуі бар болса, онда ол жоғарыда тұрған әрбір жартылай жазықтыққа тиісті болады. Жартылай жазықтықтың қиылысуы дөңес жиын болады. Бұл жиынды шешімдер көпбұрышы деп атайды. Бұл көпбұрыштың қабырғалары жататын түзудің теңдеуі (11)-(12) теңсіздіктерді теңдікке айналдыруда шығатын формуламен анықтайды. Демек, сызықтық программалаудың (12)-(13) есебінің шешуі дегеніміз шешімдер көпбұрышы бос жиын болмауы керек және мақсаттық функция осы шешімдер көпбұрышы жоғарыдан шектелуі керек. Осы шарттар орындалғанда шешімдер көпбұрышының ең болмағанда бір төбесінде мақсаттық функция өзінің максимум мәнін қабылдады. Осы ең тиімді жоспарға сәйкес төбені анықтау үшін мына сызықты c₁x₁+c₂x₂=h сызамыз және бұл сызықты

= {c₁; c₂} векторлары бағытында параллель жылжытамыз. Нәтижесінде ол осы түзумен көпбұрыштың ең соңғы қиылысатын нүктесі ең тиімді жоспарға сәйкес нүкте болады.

(12), (13) есептерінің геометриялық интерпретациясын қарастыруды анықтай отырып, оның шешімін табу кезінде 1.1-1.4 суреттердегі көрсетілген жағдайлар кездесуі мүмкін.

B F_max

F_max

A
c

x₁x₁
1.1 сурет 1.2 сурет
1.1 суретте ең тиімді жоспарға сәйкес бір ғана нүкте төбесі болады. 1.2 суреттен мақсаттық функция максимал мәнді АВ кесіндісінің кез-келген бөлігінде қабылдай алатындығы көрініп тұр. 1.3 суретте есептің шешімі болмайды. Себебі мақсаттық функция шешімдер көпбұрышында жоғарыдан шектелмеген. 1.4 суретте есептің шешімі болмайды. Себебі шешімдер көпбұрышы бос жиын.

1.3 сурет 1.4 сурет

Берілген шектелген жүйедегі сызықтық функцияның минималды мәнін табу оның осындай шектеудегі максимал мәнін табудан айырмашылығы c₁x₁+c₂x₂=h сызығы

= {c₁; c₂} векторының бойымен емес, оған қарама-қарсы бағытта жылжуында. Осылайша мақсаттық функцияның максималды мәнін табуда кездесетін жоғарыда көрсетілген жағдайлар сол мақсаттық функцияның минимал мәнін тапқанда да орын алады.

3. Геометриялық интерпретация негізінде сызықты программалау есебінің шешу алгоритмі.

Сонымен, сызықтық программалау есептерінің (11), (13) геометриялық мағынасына сүйеніп, графиктік әдіспен шешу мынадай қадамдардан тұрады:

1. Теңдеуі (12), (13) шарттардағы теңсіздік белгісін теңдікпен алмастырғанда шығатын түзулер сызады.

2. Есептің шартындағы әрбір теңсіздіктің шешуі болатын жартылай жазықтықтар табады.

3. Шешімдер көпбұрышын анықтайды.

= {c₁; c₂} сызады.

5. c₁x₁+c₂x₂=h түзуін сызады. Бұл түзу с векторына перпендикуляр орналасады.

6. c₁x₁+c₂x₂=h түзуін с векторы бағытында параллель жылжыта береді. Нәтижесінде мақсаттық функцияның максимум мәнін қабылдайтын нүктені табады немесе есептің шешімі болмайтындығын анықтайды.

7. Ең тиімді жоспардың координаталарын анықтап, мақсаттық функцияның сол нүктедегі мәнін есептейді.

жүктеу 5,07 Mb.

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

1 2 3 4 5 6 7 8 9 10 ... 46