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

Сызықтық программалаудың жалпы есебін қарастырайық. Ол

(1.10)

функциясының максимальды мәнін

(1.11)

(1.12)

(1.13)

мұндағы а_ij, b_i, с_j — берілген тұрақты шамалар, шарт жағдайларында анықтау керек.

Анықтама 5.1. (1.10) функциясы (1.10)-(1.13) есептерінің мақсаттық функциясы деп, ал (1.11)-(1.13)- шарттары берілген есептің шектеулері деп аталады.

Анықтама 5.2. (1.11) және (1.13) () шарттары орындалатындай (1.10) функциясының максимальды мәнін анықтайтын есептерді сызықтық прграммалау есебінің стандартты (немесе симметриялық) есебі деп атайды.

Анықтама 5.3. (1.12) және (1.13) () шарттары орындалатындай (1.10) функциясының максимальды мәнін анықтайтын есептерді сызықтық программалау есебінің канондық (немесе негізгі) есебі деп аталады.

Анықтама 5.4. (1.11)-(1.13) есептерінің шектеулерін қанағаттандыратын Х = (х₁, x₂, ..., х_п), сандарының жиынтығы жоспар (немесе мүмкін шешімдер) деп аталады.

Анықтама 5.5. (1.10) функциясының максимальды мән қабылдайтын Х*=(х₁*, х₂*, ..., x_n*) жоспары тиімді жоспар деп аталады.

(1.10), (1.12) және (1.13) есептерін векторлық түрде жазамыз.

(1.14)

бұл функцияның максимумын төменгі шарттарды қанағаттандыратындай етіп табу керек:

(1.15)

(1.16)

мұндағы С= (с₁; c₂; ...; с_n), Х= (х₁; х₂; ...; х_n); (C, X) – скалярлық көбейтінді, Р₁, ..., Р_п – белгісіздердің алдыедағы коэффициенттерден құрылған m-өлшемді бағана – вектор және P₀ – есептің теңдеулер жүйесінің бос мүшесі:

.

Анықтама 5.6. Егер (1.15) жіктеуіне енетін х_j- оң коэффициенті бар Р_j векторлар жүйесі сызықты тәуелсіз болса, онда Х= (х₁; х₂; ...; х_n) - негізі сызықты программалау есебінің тіреулік жоспары деп аталады.

Анықтама 5.7. Егер тіреулік жоспар, дәл m оң компонент қабылдаса онда ол ерекше деп аталады, ал кері жағдайда ерекше емес деп аталады.

Теорема 1.1. (F→max болғанда, тіреулік жоспардың тиімділік белгісі). Егер шарттары орындалса, онда (1.10)-(1.13) есебінің X*=(x₁*, x₂*, …, x_n*, 0, 0, …,0) тіреулік жоспары тиімді жоспар болып табылады.

Сызықты программалау есебін шешу үшін стандартты есепті канондық түрде жазуымыз керек, мұнда қосымша айнымалыларды базистік, ал негізгі айнымалыларды бос айнымалылар деп аламыз. Осы арқылы бірінші тіреулік жоспар құрылады.

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

P₀ бағанасына (1.15) формуласындағы P₀ векторының компоненттерін жазамыз және есептеу нәтижесінде келесі тіреулік жоспарды содан аламыз.

Бастапқы m жол есептің алғашқы мәліметтерінен анықталады, ал (m+1)-ші көрсеткіштік жолын немесе бағалар жолын келесі формула бойынша есептейміз:

(1.17).

Бұл жолдағы Р₀ бағынасына берілген F=(C_Б, Р₀) тіреулік жоспарда қабылдайтын мақсаттық функцияның мәнін жазады.

Симплекс-кестенің жалпы сызбасы.

Егер болғанда, (1.14)-(1.16) есебінің канондық түрінің толық m-базистік векторлары бар болса онда (1.10)-(1.16) есепті шешу үшін тіреулік жоспарды тізбектей жақсарту(ТЖТЖ) әдісін қолданамыз [7, 11].

1-қадам. Бірінші симплекс кестеден X¹_Б тіреулік жоспарды, және осы тіреулік жоспардағы функцияның мәнің F(X¹_Б) анықтаймыз.

2-қадам. 1.1 теоремаға сүйеніп, табылған жоспарды тиімділікке тексереміз. Егер жоспар тиімді болса, онда жауабын жазамыз, кері жағдайда 3-қадамға көшеміз.

3-қадам.

(1.18)

4-қадам.

(1.19)

6-қадам. Гаусс кестелік әдісі бойынша жаңа симплекс кесте толтырамыз. Келесі базистік шешімді анықтаймыз және 2-ші қадамға қайта ораламыз.

Ескерту. Мақсаттық функция минимуға (F→min) ұмтылатын сызықтық программалау есебін екі тәсілмен шығаруға болады:

1-тәсіл. F→min –ді, F→max-ға ауыстырамыз, яғни

minF = -max(-F) (1.20)

2-тәсіл. 2 және 3-ші қадамды өзгерту арқылы ТЖТЖ әдісін қолданамыз.

2-қадам. Тіреулік жоспар тиімділікке тексеру үшін келесі теорема қолданылады.

Теорема 1.2. (Fmin болғандағы есептің тіреулік жоспарының тиімділік критері). (1.10)-(1.13) есебінің X*=(x₁*, x₂*, …, x_n*, 0,…,0) тіреулік жоспары тиімді жоспар болады, егер келесі шарттар орындалса:

(1.21)

3-қадам. Шешуші бағананы келесі формула бойынша табамыз:

, (1.22)

ТЖТЖ әдісінің қалған қадамдары өзгеріссіз қалады.

Тіреулік жоспарды тізбектей жақсарту әдісін қолдануды келесі мысал арқылы қарастырайық.

Айталық, ағаш өндейтін кәсіпорын негізгі өндіретін өнімдерінен қалған қалдықтарды тиімді пайдалану үшін кітап сөрелері мен орындықтар шығаратын болсын. Кітап сөрелері мен орындықтар шығару үшін үш түрлі шикізат қолданылады: ағаш(м³), жұқа ағаш(фанера)(м²) және шыны(м²).

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

Шығарылған өнімді сату кезінде ең көп пайда беретін шығару жоспарын табу керек. Сату толығымен қамтамасыз етілген деп жорамалданады.

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

Бір орындықты шығару үшін 2м³ ағаш жұмсалынады, онда дана орындық шығару 2 болады, дана кітап сөрелерін шығару үшін 3 м² ағаш кетеді. Онда барлығы болады.

Кәсіпорында барлығы 180м³ ағаш бар, сондықтан шамасы 180-нен аспауы керек, яғни ағаш үшін келесі шектеуді аламыз:

.

Осыған ұқсас келесі екі ресурстардың (фанера және шыны) шектеулер жүйесін жазуға болады:

Экономикалық мағынасы бойынша және

Бір орындықты сатқаннан кейін кәсіпорын 16тг пайда табады, ал бір кітап сөресінен 12тг. Табыстардың қосындысы болады.

Берілген есепте жалпы табысты максимизациялау керек. Құрылған сызықтық функцияны F(X), мұндағы X=(x₁,x₂) арқылы белгілейміз. Сонымен осы есептің математикалық моделі келесі түрде болады:

(1.23)

(1.24)

шарттарды қанағаттандыратын және

(1.25)

мақсаттық функциясына максимум мәнің беретін векторын анықтаймыз.

Сонымен (1.23)-(1.25) формулалары қарастырылған есептің математикалық моделі болады.

(1.23)-(1.25) теңдеулер жүйесін канондық түрге келтіру үшін қосымша теріс емес айнымалыларын енгіземіз:

(1.26)

(5.17) шартын келесі векторлық түрде көрсетеміз

мұндағы

қосымша айнымалысы ағаштың, қосымша айнымалысы жұќа ағаштың(фанера), қосымша айнымалысы шынының қолданбайтын көлемін білдіреді.

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

ТЖТЖ алгоритмі арқылы келесі қадамдардан өтеміз.

1-қадам. Бірінші симплекс кестені құрамыз. (1.26) жүйедегі коэффициенттерді бірінші симплекстік кестеге енгіземіз. жолына мақсаттық функцияның коэффициенттерін қарама-қарсы таңбамен жазамыз.

1.4 кесте

2-қадам. бағанасындағы коэффициентінен басқа жолының барлық коэффициенттерін қарастырамыз. 1.1 теоремаға сәйкес бұл жоспар, яғни және . Онда 3-ші қадамға көшеміз.

3-қадам. Шешуші бағананы анықтаймыз

яғни .

Шешуші бағананы ретінде индекстік жолдың теріс элементтерінің ішінен абсолют шамасы бойынша ең үлкен коэффициенті бар бағананы тандаймыз. Бұл бағана келесі итерацияға қандай базис айнымалысы кіретінін көрсетеді. 1.4 кестесінде шешуші бағана сызықпен көрсетілген.

4-қадам. Шешуші жолды табамыз. бағанасындағы әрбір коэффициентті сәйкесінше шешуші бағананың әрбір оң коэффициенттеріне бөлеміз:

яғни .

Шешуші жол келесі итерацияда қандай базис айнымалысы шығатынын көрсетеді. Бізде шешуші жол

5-қадам. Шешуші элементті анықтаймыз:

Бірінші симплекстік кестеден шешуші элементті белгілейміз.

6-қадам. Жаңа 1.5 кестені толтыру үшін Гаусс таблицалық әдісін қолданамыз:

а) жаңа кестедегі шешуші элементтің орнына 1-санын қоямыз және бағананы нөлмен толтырамыз;

б) жаңа жолдың элементтерін табу үшін ескі жолдың элементтерін шешуші элементке бөлеміз;

в) егер жолда 0-ге тең элементтер кездессе онда осы элементтерге сәйкес «ескі» бағаналарды сол қалпында көшіреміз;

г) ал басқа элементтерді табу үшін тіктөртбұрыш ережесі бойынша есептейміз.

1.5 кесте

Осы кестеден келесі тіреулік жоспарды аламыз:

.

1.5 кестеде бағалар жолында теріс элемент бар болғандықтан, келесі итерацияны бастау үшін 2-қадамға ораламыз және барлық қадамдарды қайталау арқылы келесі кестені аламыз:

1.6 кесте

Барлық болғандықтан, 3-ші симплекстік кесте тиімді кесте болады. Осы кестеден қарастырылған есептің тиімді жоспары

.

ІV. Тиімді жоспардың экономикалық талдауы. Егер кәсіпорын 57 орындық және 12 кітап сөрелерін өндіріп сатса, онда кәсіпорын 1056тг пайда табады. Сонымен бірге кәсіпорын жұқа тақша мен шыныны толығымен қолданады () және кәсіпорында 30м² ағаш () қалады. Сонымен есеп толығымен шешілді.