Умк по инженерному проектированию

жүктеу 9,53 Mb.

бет	31/95
Дата	08.02.2018
өлшемі	9,53 Mb.
	#9080

1 ... 27 28 29 30 31 32 33 34 ... 95

Базиске енгізілген векторлар бағанында, яғни, бағана мен жолдың қиылысуында сәйкесінше табылған вектор болса, оны 1-ге, ал сол бағананың қалған элементтерін 0-ге тең деп аламыз.

Жаңа симплекс кестесінде базиске енгізілген, яғни, табылған вектор жазылған жолдағы P₀ және P_j векторларының элементтерін табу үшін, алғашқы таблицадағы осы жолдардың элементтерін шешуші элементке бөлеміз. С_б бағанындағы енгізілген вектор жазылған жолға, k – енгізілген вектордың индексі болғандағы c_k –ның мәні жазылады.

Жаңа симплекс кестесіндегі қалған P₀ және P_j векторларының элементтерін табу үшін ү ш б ұ р ы ш т а р ә д і с і н қолданамыз. Осы элементтердің кез-келгенін есептеу үшін үш сан табу керек:

жаңа симплекс кестесінде шешуші элементтің орнында, яғни, алғашқы симплекс кестеде тұрған сан;
векторға сәйкес базиске енгізілген және жаңа симплекс кестедегі шешуші элемент бар, қиылысқан бағана мен жолда тұрған алғашқы симплекс кестедегі сан;
базис векторына қайта енгізілген және жаңа симплекс кестедегі шешуші элемент бар, қиылысқан бағана мен жолда тұрған сан (жоғары да айтылып кеткендей, бұл жол, алғашқы симплекс кестедегі элементтерді шешуші элементке бөлгендегідей табылады).

Осы үш сан өзара үшбұрыш әдісін құрайды, алғашқы симплекс кестеде табылған екі сан - төбелері, ал үшіншісі жаңа симплекс кестеден табылған санға сәйкес келеді. Жаңа симплекс кестесінен шешуші элементті анықтау үшін бірінші саннан екінші және үшінші сандардың туындыларын алады.

Жаңа симплекс кестесін толтырғаннан кейін (m+1) –ші жолдағы элементтерді қарастырады. Егер барлығы

болса, онда жаңа тірек жоспары ең тиімді жоспар болады. Егер көрсетілген сандардың ішінде теріс сан болатын болса, онда жоғарда келтірілен мысалдарға сүйене отырып, жаңа тірек жоспарын табады. Бұл процесс ең тиімді жоспар алғанға дейін немесе ол есептің шешуі жоқ болғанға дейін жүргізіледі.

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

Сызықтық программалау есептерінің ең тиімді жоспарын симплекс әдісімен табу үшін мына қадамдарды орындау қажет:

Тірек жоспарын табады.
Симплекс кестені құрады.
_j сандарының арасында ең болмағанда бір теріс сан бар ма, жоқ па соны анықтайды. Егер болмаса, онда қарастырып отырған тірек жоспары ең тиімді жоспар болады. Ал егер сандарының арасында ең болмағанда бір теріс сан бар болса, онда келесі екі жағдайдың біреуі орындалады: а) есептің шешуі болмайды;

жүктеу 9,53 Mb.

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

1 ... 27 28 29 30 31 32 33 34 ... 95