Транспорттық есептің бірінші тіреулік жоспарын тапқаннан кейін берілген жоспардың тиімді екендігін келесі теоремаларды пайдаланып тексереміз [5, 7, 10, 11].

Теорема 3.1 (ерекше еместік шарт). Егер келесі шарттар орындалатын болса, онда транспорттық есептің шешімі бар болады: бос емес торлардың саны k-ға тең болу керек,

(3.6)

мұндағы, m – кестенің жолдарының саны, n – кестенің бағанасының саны.

Теорема 3.2. (тиімділік критериі). Транспорттық есептің тіреулік жоспарын тиімді жоспар дейміз, егер келесі шарттар орындалса:

1. барлық бос емес тор үшін, (3.7)

2. барлық бос торлар үшін, (3.8)

мұндағы потенциалдар деп атайды.

(3.8) формуласын баға түрінде қолдансақ, онда баға бойынша тиімділік критерийін аламыз.

Теорема 3.3. (Баға бойынша жоспардың тиімділігі). Егер барлық бағалар оң емес болса, яғни , онда транспорттық есептің тіреулік жоспары тиімді болады.

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

1-қадам Тіреулік жоспардын ерекше еместігін тексереміз (теорема 3.1).

2-қадам. Алынған жоспардың тиімділігін келесі ережемен тексереміз:

1) Барлық бос емес (базистік) айнымалылар үшін (3.7) жүйесін шешеміз, ол (m+n) айнымалыдан және (m+n –1) теңдеуден тұрады, онда жүйенің шексіз көп шешімі бар болады. Егер бір айнымалыға кез келген мән берсек, онда басқа айнымалыларды да анықтауға болады. Есептеуге ыңғайлы болу үшін деп алады. Басқа потенциалдарды анықтаймыз.

2) Барлық бос торларды, тиімділік критерийінің негізінде бағалаймыз.

Ескерту. Егер теңсіздік орындалса, онда "+" белгісін қоямыз, әйтпесе "-" белгісін қоямыз. Егер барлық теңсіздік орындалса, онда жоспар тиімді жоспар болады.

3) Барлық мәндерін қарастырамыз, егер болса, онда жоспар тиімді болады және тиімді жоспар арқылы () сызықтық формасының мәнің есептейміз:

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

3-қадам Жаңа таблицаны толтыру үшін төмендегі ережелерді қолданамыз.

1) Барлық оң -дың ең кішісін табамыз және осы тор үшін цикл құрамыз.

Анықтама 3.4. Цикл – бұл бір төбесінен басқасының барлық төбелері (З) бос емес торларда болатын тұйық сынықтар. Бұл сынықтар берілген кестенің жолдары мен бағаналарына паралелль орналасады (* бос торды білдіреді).

Қарапайым циклдардың кейбір түрі:

Мұндағы "-" белгісі тордың минустығын білдіреді.

Циклдің бір төбесі бос торда орналасса, ал қалған басқасы тікбұрыштық контурдың бос емес торында орналасқан.

2) Бос емес торда орналасқан төбеге (+) белгісің қоямыз, одан кейін таңбасы ауысып отырады. Кез келген цикл төбесі жұп саннан тұратындықтан, контурды сағат тіліне бағыттас немесе сағат тіліне қарсы бағытта айналып өткеннің айырмашылығы жоқ.

3) Барлық теріс таңбалы төбелердің ішінен ең кішісін таңдаймыз.

4) мәнің барлық контур бойынша қайтадан бөлеміз: төбесі оң болса мәнің қосамыз, теріс болса мәнін аламыз. Циклге қатыспайтын қалған барлық торларды өзгеріссіз қалдырамыз.. Сонымен жаңа тіреулік жоспар аламыз және алгоритмнің 1-қадамына келеміз.

Тиімді жоспар алынғанша 1, 2, 3 қадамдарын қайталай береміз.

«Cолтүстік-батыс бұрыш» әдісімен табылған тіреулік жоспарды тиімділікке тексереміз. 3.3-кестесі 3.1-кестесіне сәйкес келеді.

Бірінші тіреулік жоспарды келесі түрде аламыз

.

Осындай жоспардағы мақсаттық функцияның мәні келесідей болады

3.2 теореманың қасиеті бойынша бос емес торлар үшін потенциалдар жүйесін құраймыз:

2). Келесі жүйені аламыз

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

3). Тиімділік критерийдің (3.2 немесе 3.3 теоремасы) негізінде бос орындарды бағалаймыз:

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

3-қадам Жаңа кестені толтыру

1) х₂₁ торы үшін циклін құрамыз.

2) х₂₁ торына + белгісін қоямыз, одан таңбалар кезектеседі.

3) Теріс таңбалы төбелердің ішінен ең кішісін таңдаймыз:

=min { минус торлардан}= min {30,10}=10.

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

Жүкті бөлгенннен кейін 3.4 кестесін аламыз.

3.4 ксетесінен жаңа тіреулік жоспарды және мақсаттық функцияның мәнің келесі түрде аламыз:

;

Тіреулік жоспарды тиімділікке тексереміз, яғни 1-қадамға ораламыз.

1-қадам. k=4, яғни жоспар ерекше емес болады.

2-қадам. Бос емес тор үшін потенциалдар жүйесін құрамыз және дербес шешімді табамыз.

Келесі дербес шешімдерді аламыз:

Бос торларға келесі теңсіздіктерді құрып, оларды ақиқаттыққа тексереміз:

3-қадам. 1). 3.4 кестесінде х₁₃ –ке цикл құрамыз.

.

2). х₁₃ торына + таңбасын қойып, таңбаларды кезектестіріп отырамыз .

3). мәнін анықтаймыз:

: = min {20,40}=20.

Кесте 3.5

Келесі мақсаттық функция мәні мен үшінші базистік шешімін аламыз:

; F(X₃) = 250 ш.б.

Берілген шешімдерді тиімділікке тексереміз.

1-қадам. Бос емес торлар саны k=4, жоспар ерекше емес.

2-қадам. Бос емес торлар үшін теңдеулер жүйесін құрамыз:

Бір дербес шешімін табамыз:

Бос торлар үшін теңсіздіктер құрып, тексереміз:

Барлық теңсіздіктер ақиқат мәнін қабылдағандықтан, онда ең ақырғы жоспар тиімді болады.