Mtazamo wa jedwali wa PPP. Simplex - meza.
NJIA RAHISI YA KUTATUA ZLP
3.1. sifa za jumla na hatua kuu za njia rahisix
Waanzilishi wa njia rahisi ni mwanahisabati wa Soviet L.V. Kantorovich na mwanahisabati wa Marekani J. Dantzig.
Kutumia njia rahisi, unaweza kutatua shida yoyote au kugundua kutoweza kwake. Madarasa mengi maalum ya shida yanaweza kutatuliwa kwa njia zingine ambazo zinafaa zaidi kwa madarasa haya. Hata hivyo, faida ya njia rahisix ni versatility yake. Takriban kompyuta zote zimetengenezwa programu za kawaida kwa ufumbuzi ZLP rahisix- njia.
Hebu tueleze wazo la jumla njia rahisix.
Tunaamini kwamba ZLP imeandikwa katika mfumo wa kisheria na utendakazi wa lengo unahitaji kupunguzwa. Kama tunavyojua, mpango bora unapaswa kutafutwa kati ya mipango ya msingi ya ZLP. Njia rahisi haipitii mipango yote ya kumbukumbu (ambayo mara nyingi haitawezekana kwa sababu ya idadi kubwa), lakini, kuanzia mpango fulani wa marejeleo wa awali, inahamia kwa mipango mingine ya kumbukumbu na kupungua. kazi ya lengo. Njia rahisi huacha kufanya kazi wakati mpango bora wa kumbukumbu unapatikana au kutotatuliwa kwa shida kumeanzishwa.
Wakati wa kuamua ZLP kwa kutumia njia rahisi Hatua zifuatazo zinaweza kutofautishwa:
1) kuleta PAP kwa fomu ya kisheria;
2) kuleta mfumo wa milinganyo ya mstari kwa fomu ya Jordan na pande zisizo hasi za mkono wa kulia wakati huo huo kuangalia kutotatulika kwa ZLP kwa sababu ya kutofautiana kwa mfumo. vikwazo vya mstari;
3) utafiti wa mpango wa kumbukumbu kwa ufanisi;
4) utafiti wa ZLP kwa kutoamua kwa sababu ya kutokuwa na mipaka kutoka chini kwenye ODD ya kazi ya lengo;
5) mpito kwa mpango mpya wa kumbukumbu "bora".
Ili kupunguza na kuandaa rekodi wakati wa kutatua tatizo kwa kutumia njia rahisi, kinachojulikana kuwa meza rahisi hutumiwa. Ili kutumia jedwali rahisi, ZLP lazima ipunguzwe kwa fomu ya tabular. Imefanywa hivi.
Hebu ZLP iandikwe katika mfumo wa kisheria (2.3-2.5). Ili kupunguza ZLP kuwa fomu ya jedwali, mfumo (2.4) unapaswa kwanza kupunguzwa hadi fomu ya Yordani na pande zisizo hasi za mkono wa kulia. Hebu tuchukulie kwamba umbo hili la Yordani lina umbo (2.6). Wacha tuonyeshe kutoka kwa (2.6) anuwai za kimsingi kulingana na zile za bure:
Kwa kubadilisha katika kipengele cha kukokotoa (2.3) badala ya vigeu vya msingi vya usemi wao kupitia vigeu visivyolipishwa kulingana na fomula (3.1), kwa hivyo tunatenga vigeu vya msingi kutoka kwa chaguo za kukokotoa. Kazi ya lengo itachukua fomu:
KATIKA fomu ya jedwali kazi ya lengo imeandikwa kama ifuatavyo:
Wapi 
.
Kumbuka vipengele vifuatavyo muundo wa jedwali wa PPP:
a) mfumo wa milinganyo ya mstari umepunguzwa hadi umbo la Yordani na pande zisizo hasi za mkono wa kulia;
b) vigezo vya msingi vimetengwa na kazi ya lengo na imeandikwa kwa fomu (3.3).
Hebu sasa tuendelee kwenye maelezo ya jedwali la simplex. Acha ZLP iandikwe katika mfumo wa jedwali:
(3.4)
Kisha meza iliyokamilishwa ya simplex inaonekana kama hii.
Njia rahisi ya kutatua shida programu ya mstari
Njia rahisi ni njia ya uchambuzi Suluhisho za ZLP kutekeleza algorithm njia ya picha uchambuzi, bila kuchora kuchora.
Hivyo uhakika ni njia rahisix inajumuisha utafutaji ulioelekezwa wa ufumbuzi unaowezekana, ambapo thamani ya kazi ya lengo katika kila hatua ni bora kuliko ya awali. Mchakato huo unarudiwa hadi suluhisho ambalo ni bora kwa suala la thamani ya kazi ya lengo linapatikana.
Njia rahisi inaweza kutumika kutatua PLP na idadi yoyote ya haijulikani.
Utekelezaji wa kiufundi wa njia rahisix unahusishwa na mifumo ya kutatua equations ya mstari, ambayo njia ya Gauss hutumiwa, fomu za tabular na sheria za kubadilisha meza rahisix zimeandaliwa.
Njia rahisi na msingi wa asili inatumika ikiwa PIL imeainishwa ndani fomu ya kisheria rekodi, na matrix katika KZLP ina submatrix ya kitengo cha ukubwa mimi. Kwa uhakika, wacha tufikirie kuwa ya kwanza m Matrices ya vekta ya mfumo wa milinganyo huunda matrix ya utambulisho. Kisha mpango wa awali huchaguliwa kama ifuatavyo:
Ubora wa mpango wa marejeleo huangaliwa kwa kutumia ishara ya ukamilifu; mpito kwa mpango mwingine unafanywa kwa kutumia mageuzi ya Jordan-Gauss kwa kutumia ishara ya ukamilifu wa kihesabu. Mpango wa kumbukumbu unaosababishwa unaangaliwa tena kwa ukamilifu, nk.
Kigezo cha hisabati cha ukamilifu kinajumuisha nadharia mbili zifuatazo:
1. Ikiwa kwa vekta zote A 1 , A 2 , … , A n hali imeridhika wapi 
, basi mpango wa kumbukumbu unaotokana ni sawa. Kwa jumla kuamua Z j kushiriki m
masharti, yaani, sio coefficients zote za kazi ya lengo hushiriki ndani yake c j, lakini tu na nambari zinazolingana na nambari za vekta za msingi za sasa A i, idadi ambayo ni sawa m
.
2. Ikiwa kwa vekta fulani haijajumuishwa katika msingi hali imeridhika 
, basi unapaswa kutafuta mpango mpya wa marejeleo ambao thamani ya CF ni kubwa kuliko ya sasa. Katika kesi hii, kesi mbili zinawezekana:
a) ikiwa vipengele vyote vya vector A k, kuingizwa kwa msingi, sio chanya, basi LLP haina suluhisho (hakuna optimum ya mwisho);
b) ikiwa vekta ina angalau sehemu moja chanya A k, kuingizwa kwa msingi, basi mpango mpya wa kumbukumbu unaweza kupatikana.
Kulingana na kigezo cha ukamilifu, vekta huletwa ndani ya msingi A k, ambayo ilitoa thamani hasi ya chini ya tofauti rahisix:
Ili hali ya kutokuwa na hasi ya maadili ya mpango wa kumbukumbu kuridhika, vekta hutolewa kutoka kwa msingi. A r, ambayo inatoa uwiano wa chini wa tathmini chanya
Mstari A r, ambayo vector ya zamani ya msingi ilikuwa iko, inaitwa mwongozo, safu A k na kipengele rk- viongozi.
Vipengele vya mstari wa mwongozo kwenye jedwali mpya la simplex huhesabiwa kwa kutumia fomula:
na vipengele vingine vyovyote i mstari wa th - kulingana na fomula:
Thamani za mpango mpya wa kumbukumbu huhesabiwa kwa kutumia fomula zinazofanana:
,
Mchakato unaendelea ama hadi mpango mojawapo upatikane au hadi TF iwe na ukomo. Ikiwa kati ya tofauti Δ j , j=1, 2, … , n ya mpango bora, tofauti tu zinazofanana na veta za msingi ni sifuri, hii inaonyesha upekee wa mpango bora. Ikiwa makadirio ya sifuri yanafanana na vector isiyojumuishwa katika msingi, basi kwa hali ya jumla hii ina maana kwamba mpango bora sio pekee.
Mfano. Tatua ZLP kwa kutumia mfano:
tafuta 
,
chini ya vikwazo 
ZLP hii imepunguzwa hadi fomu ya kisheria kwa kuanzisha vigeu vya ziada x 3 Na x 4:
KZLP ina nambari inayotakiwa (mbili) ya safu wima sifuri kwenye x 3 Na x 4, yaani, ina mwanzo dhahiri mpango wa kumbukumbu (0,0,300,150).
Suluhisho hufanywa kwa kutumia njia rahisi na msingi wa asili na mahesabu yaliyoundwa katika jedwali rahisix:
| Nambari ya jedwali rahisix | Msingi | pamoja na j | pamoja na j | Q | ||||
| B | A 1 | A 2 | A 3 | A 4 | ||||
| ←A 3 | ||||||||
| A 4 | ||||||||
| Δ | - | -2 | -3 | - | ||||
| I | →A 2 | 1/3 | 1/3 | |||||
| ←A 4 | 2/3 | -1/3 | ||||||
| Δ | - | -1 | - | |||||
| II | A 2 | 1/2 | -1/2 | - | ||||
| →A 1 | -1/2 | 3/2 | - | |||||
| Δ | - | 1/2 | 3/2 | - |
Wacha tukae kwa undani zaidi juu ya kujaza meza rahisi na, ipasavyo, kupata suluhisho la KZLP.
KATIKA mstari wa juu coefficients iliyojumuishwa kwenye jedwali la jumla c j , j=1, 2, 3, 4 yenye vigeuzo katika utendaji wa kidijitali. Safu mbili za kwanza za jedwali la sifuri rahisix zina vekta za safu wima B, A 1, A 2, A 3, A 4, sambamba na fomu ya vector ya rekodi ya KZLP. Kwa kuwa msingi wa awali ni jozi ya vekta A 3, A 4, zimejumuishwa kwenye safu inayoitwa "Msingi" wa jedwali la zero simplex. Ambapo, A 3 imejumuishwa katika safu ya kwanza, ambayo imedhamiriwa na kitengo kuwa kipengele cha kwanza cha vector hii, na vector A 4- kwa mstari wa pili, kwa vector hii kitengo iko kwenye mstari wa pili. Katika safu inayoitwa " c i” viambajengo vya utendakazi wa lengo vinavyolingana na vekta za msingi huletwa A 3, A 4, hiyo ni c 3, c 4. Wote wawili ni sawa na sifuri. Ifuatayo, maadili ya tofauti Δ kwa vekta huhesabiwa B, A 1, A 2, A 3, A 4 na huingizwa kwenye safu ya tatu ya jedwali la sifuri. Kwa vector A 1:
kwa vekta:
Vivyo hivyo,.
Kwa vector B kuhesabu tofauti ni rahisi kwa kuwa hakuna mgawo unaolingana c j , j=1, 2, 3, 4 katika CF:
Sio kwa vekta zote A 1 , A 2 , A 3 , A 4 tofauti zinazotokea sio hasi, kwa hivyo mpango wa kumbukumbu ambao tumechagua sio bora. Tunahitaji kutafuta mpango mpya wa kumbukumbu, na kwa hili tunahitaji kuchukua nafasi ya moja ya vectors iliyojumuishwa katika msingi A 3, A 4.
Kuamua vector ambayo lazima tuingie, tunatafuta vector ambayo thamani ya tofauti ni ndogo. Hii ni vector A 2, inalingana nayo thamani ya chini tofauti: -3. Hiyo ni, index k kutoka kwa formula (8.4) ni sawa na 2. Kuamua vekta ambayo tutalazimika kupata kutoka kwa msingi, tunahesabu maadili. Q kwa kila mstari kulingana na fomula (8.5) na uziweke kwenye safu ya mwisho. KATIKA kwa kesi hii katika kila mstari tunahitaji thamani ya kipengele cha vector B kugawanya kwa ukubwa wa kipengele cha vector A 2. Katika mstari wa kwanza tunapata 300/3=100, kwa pili: 150/1=150. Uwiano katika safu ya kwanza ulikuwa mdogo; vekta ya msingi ililingana nayo A 3, kwa hiyo, index r katika fomula (8.5) ni sawa na 1, rk=3 (iliyoonyeshwa kwenye jedwali na sura), na tutapata vector kutoka kwa msingi A 3(imeonyeshwa na mshale kwenye meza).
Tangu kati ya vipengele vya vector A 2, ambayo lazima iingizwe katika msingi, kuna mazuri, basi mpango mpya wa kumbukumbu unaweza kupatikana na ufumbuzi unapaswa kuendelea.
Baada ya hayo, meza ya pili rahisi imejazwa. Ili kuhesabu upya vipengele vya vector B, A 1, A 2, A 3, A 4 fomula (8.6)-(8.8) zimetumika. Wao ni tofauti kidogo kwa kufafanua vipengele vya mstari wa mwongozo (kwa upande wetu, wa kwanza) na kwa kufafanua vipengele vya mistari mingine. Wacha tuandike mahesabu ya vitu kadhaa:
Vipengele vingine vya jedwali la kwanza la simplex vinahesabiwa kwa njia sawa na tulivyofanya kwa jedwali la sifuri. Kwa kuwa sio tofauti zote katika jedwali la kwanza la simplex sio hasi, inakuwa muhimu kuendelea na mahesabu.
Kama tunavyoona, kama matokeo ya mahesabu katika jedwali la pili rahisi na vekta za msingi A 2, A 1 tofauti zote ziligeuka kuwa zisizo hasi, ambayo ina maana ya kufikia mpango bora (75; 75; 0; 0). Tofauti rahisi kwa vekta KATIKA sawa na ile inayotakiwa thamani ya juu CF - 375.
Theorem (kuhusu ukomo wa algorithm rahisi).Ikiwa kuna mojawapo Uamuzi wa PPP, basi kuna suluhisho la msingi la mojawapo. Mwisho unaweza kupatikana kila wakati kwa kutumia njia rahisi, na unaweza kuanza kutoka kwa msingi wowote wa awali.
Mojawapo ya shida za kawaida na maarufu za uboreshaji katika vifaa ni tatizo la usafiri . KATIKA fomu ya classic inahusisha kupata mojawapo ( hizo. kuhusishwa na gharama ndogo ) mpango wa usafirishaji wa mizigo.
Kwa mfano, tuna mlolongo wa maduka ya rejareja ambayo yanahitaji kiasi fulani cha bidhaa. Pia kuna idadi ya maghala ya wasambazaji ambapo bidhaa zinazohitajika huhifadhiwa. Aidha, kila ghala ina kiasi tofauti cha hisa za bidhaa hizi. Kwa kuongeza, tunajua ushuru - gharama za kusafirisha bidhaa 1 kutoka kwa kila ghala hadi kila duka.
Kuna haja ya kutengeneza mpango wa usafirishaji ili maduka yapate kiasi kinachohitajika cha bidhaa na gharama ya chini zaidi ya usafirishaji. Ni katika hali kama hizi (na kwa zingine nyingi) kwamba shida ya usafirishaji inapaswa kutatuliwa.
Nyenzo za kinadharia juu ya shida ya usafirishaji
(Tatizo la Monge-Kantorovich) - tatizo la hisabati programu ya mstari aina maalum kuhusu utafutaji usambazaji bora vitu vyenye homogeneous kutoka kwa betri hadi kwa vipokezi huku ukipunguza gharama za usafiri.
Kwa urahisi wa kuelewa, inazingatiwa kama shida kwenye mpango bora wa usafirishaji wa bidhaa kutoka kwa sehemu za kuondoka ( kwa mfano, maghala) kwa pointi za matumizi ( kwa mfano, maduka), pamoja na gharama ndogo za jumla za usafirishaji.
Ina fomu ifuatayo:
Wapi: Z- gharama za usafirishaji wa bidhaa;
X- kiasi cha mizigo;
C- gharama (ushuru) wa kusafirisha kitengo cha mizigo;
A- hisa ya muuzaji;
B- ombi la watumiaji;
m- idadi ya wauzaji;
n- idadi ya watumiaji.
Mpango wa jumla wa kutatua shida ya usafirishaji kwa kutumia njia inayowezekana
Tatizo la usafiri linaweza kutatuliwa mbinu mbalimbali, kuanzia njia rahisix na hesabu rahisi, na kuishia na . Mojawapo ya njia zinazotumiwa zaidi na zinazofaa kwa kesi nyingi ni uboreshaji wa mara kwa mara wa mpango wa usafiri.
Kiini chake ni kama ifuatavyo: tunapata mpango fulani wa kumbukumbu na uangalie ukamilifu (Z → dakika) Ikiwa mpango ni bora, suluhisho limepatikana. Ikiwa sivyo, inaboresha mpango mara nyingi iwezekanavyo hadi mpango bora upatikane.
Chini ni algorithm ya kutatua shida ya usafirishaji kwa fomu ya jumla zaidi:
- Kujenga meza ya usafiri.
- Kuangalia tatizo kwa kufungwa.
- Kuchora mpango wa msingi.
- Kuangalia mpango wa usaidizi wa kuzorota.
- Uhesabuji wa uwezekano wa mpango wa usafirishaji.
- Kuangalia mpango wa marejeleo kwa ukamilifu.
- Ugawaji upya wa vifaa.
- Ikiwa suluhisho mojawapo litapatikana, nenda kwa hatua ya 9, ikiwa sivyo, nenda kwa hatua ya 5.
- Mahesabu ya jumla ya gharama za usafirishaji wa bidhaa.
- Ujenzi wa grafu ya usafirishaji.
Maagizo ya kina ya kutatua shida ya usafirishaji
1. Kujenga meza ya usafiri
Tunaunda meza ambapo tunaonyesha akiba ya vifaa vinavyopatikana kwenye ghala za wauzaji ( Ai na mahitaji ya viwanda ( Bj) katika nyenzo hizi.
Katika kona ya chini ya kulia ya seli za meza tunaingiza thamani ya ushuru kwa usafirishaji wa mizigo ( Cij).
Hebu tuonyeshe jumla ya hisa ya mizigo kutoka kwa wauzaji wote wenye alama A, na mahitaji ya jumla ya mizigo kwa watumiaji wote yanaonyeshwa B.
Tatizo la usafiri linaitwa imefungwa, Kama A=B. Kama A ≠ B, basi tatizo la usafiri linaitwa wazi. Lini tatizo lililofungwa Vifaa vyote vya shehena vitaondolewa kutoka kwa wauzaji, na maombi yote ya watumiaji yatatimizwa. Lini kazi wazi Ili kutatua hili, itabidi kuanzisha wauzaji wa uwongo au watumiaji.
Wacha tuangalie kazi kwa kufungwa:
A = 10 + 20 + 30 = 60
B = 15 + 20 + 25 = 60
A = B, kwa hiyo tatizo hili la usafiri limefungwa.
3. Kuchora mpango wa kumbukumbu
Inaunda utangulizi ( kuunga mkono) mpango wa usafiri. Sio lazima kuwa bora zaidi. Hii ni aina tu ya "rasimu", "mchoro", kuboresha ambayo hatua kwa hatua tutafika kwenye mpango bora.
Kuna tofauti njia za kupata mpango wa kumbukumbu. Ya kawaida zaidi ni yafuatayo:
a) Mbinu ya Pembe ya Kaskazini-Magharibi. Onyesha
Kiini cha njia ni rahisi - seli za jedwali la usafirishaji hujazwa sequentially na idadi kubwa ya trafiki inayowezekana katika mwelekeo. Juu chini Na kutoka kushoto kwenda kulia. Hiyo ni, seli ya juu kushoto inajazwa kwanza ( seli "kaskazini magharibi".), kisha inayofuata upande wa kulia, nk. Kisha nenda kwa mstari mpya na ujaze tena kutoka kushoto kwenda kulia. Na kadhalika mpaka meza imejaa kabisa.
Maelezo ya kina ya njia na mfano unaweza kupatikana.
b) Mbinu ya kipengele cha chini. Onyesha
Njia ni kwamba kujaza seli za meza ya usafiri, chagua kiini na Ndogo thamani ya ushuru. Kisha seli inayofuata iliyo na ushuru wa chini kabisa huchaguliwa na kadhalika hadi meza ijazwe ( hifadhi zote na mahitaji yatawekwa upya hadi sifuri).
c) Ukadiriaji wa Vogel. Onyesha
Msingi wa njia ni kutafuta tofauti(modulo) kati ya jozi ushuru wa chini katika kila safu na safu. Kisha katika safu au safu na kubwa zaidi tofauti hujaza seli mdogo zaidi ushuru. Kisha vitendo hivi vyote vinarudiwa tena, tu katika kesi hii seli zilizojaa hazizingatiwi tena.
Maelezo ya kina ya makadirio ya Vogel na mfano unaweza kupatikana
d) Mbinu ya upendeleo mara mbili. Onyesha
Kiini cha njia ni kwamba seli zilizo na ushuru wa chini kabisa zimewekwa alama kwenye safu na kisha kwenye safu. Kisha seli zinajazwa kwa utaratibu ufuatao: kwanza seli na alama mbili, kisha kwa moja, hatimaye bila alama.
Maelezo ya kina ya njia na mfano unaweza kupatikana
4. Kuangalia mpango wa usaidizi wa kuzorota
Seli za jedwali ambazo usafirishaji mwingine isipokuwa sifuri hurekodiwa huitwa msingi, na iliyobaki (tupu) - bure.
Mpango huo unaitwa kuzorota, ikiwa idadi ya seli za msingi ndani yake ni chini ya m + n -1. Ikiwa wakati wa suluhisho la shida mpango wa kuzorota unapatikana, basi lazima ujazwe tena kwa kuingiza usafirishaji wa sifuri katika idadi inayokosekana ya seli na kwa hivyo kugeuza seli hizi kuwa za msingi ( usawa wa jumla na gharama ya jumla ya usafiri wa mpango haitabadilika) Walakini, haiwezekani kujaza mpango huo kwa kuchagua seli kwa nasibu. Mpango lazima uwe wa acyclic!
Mpango unaitwa acyclic ikiwa seli zake za msingi hazina mizunguko. Mzunguko katika meza ya usafiri kuna seli kadhaa zilizounganishwa na polyline iliyofungwa ili wima mbili za karibu za polyline ziko kwenye safu moja au safu sawa. Chini ni mfano wa kitanzi:
Mstari uliovunjika unaweza kuwa na sehemu za makutano, lakini sio kwenye seli za mzunguko.
Idadi ya seli za msingi = 5
m + n – 1 = 3 + 3 – 1 = 5
Kwa hivyo, mpango wa asili wa usafirishaji hauharibiki.
5. Uhesabuji wa uwezekano wa mpango wa usafiri
Ili kuchambua mipango inayotokana na uboreshaji wao unaofuata, ni rahisi kuingia sifa za ziada pointi ya asili na lengwa, inayoitwa uwezo.
Njia hii ya kuboresha mipango ya usafiri inaitwa mbinu inayowezekana . Kuna njia zingine za kuboresha mara kwa mara mpango wa usafirishaji, lakini hatutazingatia hapa.
Kwa hivyo, hebu tulinganishe kila muuzaji Ai na kila mtumiaji Bj na maadili Ui Na Vj ipasavyo, ili kwa seli zote za msingi za mpango uhusiano ufuatao umeridhika:
Ui + Vj = Cij
Ongeza kwenye meza ya usafiri mstari wa ziada na safu ya Ui na Vj.
Wacha tufikirie kuwa U1 = 0.
Kisha tunaweza kupata V3 = C13 – U1 = 1 – 0 = 1.
Kwa kujua V3, sasa tunaweza kupata U3:
Kwa mlinganisho, tunahesabu uwezo wote uliobaki:
6. Kukagua mpango wa ukamilifu kwa kutumia mbinu inayowezekana
Kwa kila seli ya bure ya mpango, tunahesabu tofauti
ΔCij = Cij - (Ui + Vj)
na uandike maadili yanayotokana katika pembe za chini za kushoto za seli zinazolingana.
Mpango ni mojawapo, ikiwa tofauti zote ΔCij ≥ 0.
Katika kesi hii, mpango ni suboptimal(ΔC22< 0), и его следует улучшить путем перераспределения поставок.
7. Ugawaji wa vifaa
Wacha tupate seli iliyo na kubwa zaidi thamani kamili tofauti hasi ΔCij na uunda mzunguko ambao, isipokuwa kwa seli hii, zingine zote ni za msingi. Mzunguko kama huo daima ipo na ni ya kipekee.
Wacha tuweke alama kwenye seli na tofauti hasi ΔCij na ishara "+", inayofuata na ishara "-", na kadhalika, moja baada ya nyingine.
Kisha tunapata thamani ya chini ya mzigo katika seli za mzunguko na ishara "-" (hapa ni 5) na uingie kwenye kiini cha bure na ishara "+". Kisha tunapitia seli zote za mzunguko, kwa njia mbadala na kuongeza thamani ya chini kwao (kulingana na ishara ambazo seli hizi zimewekwa alama: ambapo minus inapunguza, ambapo plus inaongezwa).
Tunapata mpango mpya wa kumbukumbu usafiri:
Kwa kuwa kuna seli nyingi za msingi kuliko m + n - 1, basi kiini cha msingi na thamani ya sifuri iwe huru:
Tunahesabu tena maadili yanayowezekana na tofauti ΔCij:
Wakati huu tofauti zote za ΔCij za seli ni chanya, kwa hivyo, suluhisho mojawapo limepatikana.
8. Ikiwa suluhisho mojawapo litapatikana, nenda kwa hatua ya 9, ikiwa sivyo, nenda kwa hatua ya 5.
Tumepata suluhisho mojawapo, kwa hivyo endelea hadi nukta 9.
9. Hesabu ya jumla ya gharama za usafirishaji wa bidhaa
Hebu tuhesabu jumla ya gharama za usafirishaji mizigo ( Z), sambamba na mpango bora tuliopata, kulingana na fomula:
Zmin = 10 ∙ 1 + 15 ∙ 3 + 5 ∙ 2 + 15 ∙ 1 + 15 ∙ 2 = 110 shimo. vitengo
Jumla ya gharama za usafirishaji kwa bidhaa zote, kwa suluhisho mojawapo, make up 110 shimo. vitengo
10. Ujenzi wa grafu ya usafiri
Baada ya kupata mpango bora wa usafirishaji, tutaunda. Wima ya grafu itakuwa "maghala" na "maduka". Katika wima tunaonyesha idadi inayolingana ya akiba na mahitaji. Safu zinazounganisha wima za grafu zitalingana na usafirishaji usio na sufuri. Tutatia saini kila safu kama hiyo, ikionyesha kiasi cha mizigo iliyosafirishwa.
Matokeo yatakuwa grafu sawa na ile iliyoonyeshwa hapa chini:
Hiyo ndiyo yote, tatizo la usafiri linatatuliwa. Hongera!
Utumiaji wa shida wa usafirishaji kwa vitendo
Tatizo la usafiri hutumiwa katika matukio mengi. Huu ni uboreshaji wa usambazaji wa malighafi na vifaa kwa makampuni ya viwanda. Huu ni uboreshaji wa utoaji wa bidhaa kutoka kwa ghala hadi kwenye maduka ya rejareja. Huu ni utoshelezaji wa usafirishaji wa abiria, na mengi, mengi zaidi.
Galyautdinov R.R.
© Kunakili nyenzo inaruhusiwa tu ikiwa kiungo cha moja kwa moja kwa
Ishara ya ukamilifu wa mpango wa kumbukumbu
Ikiwa katika jedwali la simplex lililo na mpango fulani wa usaidizi, vipengele vyote vya f-row (isipokuwa kwa neno la bure) sio hasi, basi mpango huu wa usaidizi ni bora .. Hebu kwenye mstari wa mbele wa meza. 2.b 0j > (i=1, ..., n m). Katika mpango wa marejeleo x 0 ulio katika jedwali hili, maadili ya vigeu vyote vya bure x m+j ni sawa na sifuri na f(x 0) =b 00. Ikiwa unaongeza yoyote ya vigezo vya bure x m+ j, basi, kama inavyoweza kuonekana kutoka kwa usawa (2.5), kwa sababu ya kutokuwa na hasi ya b 0j, thamani ya f (x) itaanza kupungua. Kwa hivyo, kwa x o chaguo la kukokotoa f(x) hufikia thamani yake kuu, ambayo inamaanisha kuwa x 0 ndio mpango bora wa marejeleo.
Uwezo wa kuhama kutoka kwa mpango mmoja wa kumbukumbu hadi mwingine
Kama ilivyoelezwa hapo juu, kiini cha njia rahisi ni mchakato wa kudhibitisha kigezo kifuatacho: ikiwa katika safu-safu ya jedwali rahisi iliyo na mpango fulani wa kumbukumbu, kuna angalau kipengele kimoja hasi (bila kuhesabu neno la bure), ambalo. inalingana na safu iliyo na angalau kipengele kimoja chanya, basi unaweza, kwa kubadilisha msingi, kuhamia kwenye mpango mwingine wa kumbukumbu na thamani kubwa ya kazi ya lengo.
Hebu thibitisha ishara hii. Wacha tuanzishe sheria za kuchagua anuwai kwa mabadiliko kama haya ya msingi wa B o na mpango wa kumbukumbu x 0 katika msingi mpya B 1 yenye mpango wa kumbukumbu x 1 ambamo; thamani ya chaguo za kukokotoa f huongezeka, yaani f(x i)>f(x 0). Kisha, kwa mujibu wa sheria ya kuhesabu upya vipengele kutoka kwa meza ya simplex, tunawabadilisha kwa msingi mpya, ambayo itatuwezesha kupata vipengele vya mpango mpya wa kumbukumbu.
Wacha tuchukue hiyo kwenye meza. 2.1, kwa mfano, b 0s<0, а среди элементов b is s-го столбца есть хотя бы один положительный. Полагая в равенстве (2.5) все свободные переменные х m+j кроме x m+s , равными нулю, получаем f = b oo -- b os xm+s . Из этого равенства видно, что при увеличении x m+s значение f тоже возрастает. Таким образом, при указанных в признаке условиях действительно есть возможность увеличить f(x), переходя к планам, в которых x m+s принимает положительные значения, а все остальные компоненты x m+j по-прежнему равны нулю. Покажем, что среди таких планов существует и опорный. Тем самым будет найден путь направленного преобразования базиса Б о в новый базис Б 1 . В самом деле, если переменная x m+s принимает положительное значение в некотором опорном плане, значит, она является в нем базисной компонентой (в опорном плане x о она была свободной компонентой и равнялась нулю). Поэтому прежний базис следует преобразовать за счет включения в него переменной x m+s . Но здесь предстоит решить два вопроса:
1) ni ipi kati ya vigezo vinavyopaswa kuondolewa kutoka kwa msingi uliopita ili kufanya nafasi ya kutofautiana x m + s;
2) kigezo kipya cha msingi x m+s kichukue thamani gani katika mpango mpya wa marejeleo.
Ili kutatua maswali yaliyoulizwa, hebu tuchukulie kwamba katika usawa (2.4) zote x m+j, isipokuwa x m+s, ni sawa na sifuri. Kisha
x i = b io -b ni x m+s (i=l, ..., m)
Kutoka kwa usawa huu ni wazi kwamba kwa kuongezeka kwa x m+s maadili ya vigezo hivyo vya msingi x i ambayo coefficients b ni.<0, тоже будут расти, оставаясь положительными. Значит, на отрицательные коэффициенты b is можно внимания не обращать, так как они не влияют на знак базисных переменных. Иначе обстоит дело с базисными переменными, у которых b is >0. Kadiri x m+s inavyoongezeka, maadili ya vigeu hivi vitaanza kupungua, na muda utakuja baada ya hapo watachukua maadili hasi na hali (2.3) haitatosheka tena. Hii haiwezi kuruhusiwa. Kwa hiyo, hebu tujue ni nini kikomo cha thamani x m+s kinaweza kuongezeka bila kukiuka hali ya kutokuwa na hasi ya vigezo vya msingi. Kwa kusudi hili, tunaandika kutoka kwa mfumo (2.6) zile usawa ambazo b ni >0. Hebu tuchukulie kuwa hii inahusu usawa na nambari i=d,…,k,…,p:
x d =b fanya -- b ds x m+s ,
…………………..
x k =b k0 - b ks x m+s ,
………………….
x p =b p0 - b ps x m+s .
Vigezo vya msingi x d, ..., x k, ..., x p havitabaki kuwa hasi mradi x m+s inakidhi mfumo wa ukosefu wa usawa.
b fanya - b ds x m+s >0, x m+s
……………… ………………
b k0 - b ks x m +s >0 au x m+s< b ko /b ks
……………… ………………
b p0 - b ps x m+s >0 x m+s< b po /b ps
yaani saa x m+s Acha sehemu ndogo zaidi ya b io /b ilingane na i = k, i.e. dakika ( b io /b ni )= b k0 /b ks . Kisha tunaweza kusema kwamba mradi x m+s haizidi thamani b k0 /b ks , yaani x m+s 0, kisha kigezo x k kitakuwa sawa na risasi: x k = b k0 -- b ks b ko /b ks =0, na kwa hivyo msingi utabadilishwa B o = (x 1; ...; x k ; . x m Wakati huo huo, vigezo vingine vyote vya bure bado ni sawa na sifuri, na vigezo vya msingi vilivyobaki bado ni vyema. Kwa hiyo, mpango wa msingi x 1 katika msingi mpya B 1 = (x 1; ...; x m+s; ...; x m ) utakuwa na vipengele vya m vyema na m-n sifuri. Katika mpango wa x 1, vigezo vingine vya msingi vinaweza kuchukua maadili ya sifuri katika hali mbili: 1) wakati katika mpango x 0 kuna vigezo vya msingi sawa na sifuri; 2) wakati sehemu ndogo zaidi ya b io /b italingana na nambari mbili au zaidi i. Kwa upande wetu, inalingana tu na i = k. Tofauti itakayojumuishwa katika msingi imedhamiriwa na kipengele hasi cha f-string. Kutoka kwa usawa f =b oo - b os x m+s ni wazi kwamba wakati b 0s<0 и фиксированном x m+s >0, thamani ya f(x) inategemea thamani kamili ya mgawo b 0: kubwa |b 0 |, ndivyo thamani f(x) itapokea katika msingi mpya. Lakini kutokana na usawa huu pia ni wazi kwamba thamani ya kazi ya lengo katika msingi mpya pia inategemea thamani iliyochukuliwa na kutofautiana kwa msingi mpya x m+s. Tutachagua kutofautisha iliyoletwa ndani ya msingi, tukizingatia tu mambo hasi ya safu ya mbele. Kwa hiyo, kunapokuwa na vipengele kadhaa hasi katika safu-mlalo ya f, tutaanzisha katika msingi kigezo x m+j kinacholingana na kipengele hasi chenye thamani kubwa kabisa. Safu ya coefficients kwa variable iliyojumuishwa katika msingi inaitwa kutatua. Kwa hivyo, kwa kuchagua kigeugeu kilicholetwa kwenye msingi (au kuchagua safu wima ya kusuluhisha) kulingana na kipengele kibaya cha safu-mstari, tunahakikisha kwamba kazi f huongezeka. Ni ngumu zaidi kuamua kutofautisha kutengwa kutoka kwa msingi. Kwa kufanya hivyo, wao hujumuisha uwiano wa maneno ya bure kwa vipengele vyema vya safu ya kutatua (mahusiano hayo yanaitwa rahisix) na kupata ndogo kati yao, ambayo huamua safu (kutatua) iliyo na kutofautiana kutengwa. Chaguo la kigezo kisichojumuishwa kwenye msingi (au chaguo la mstari wa kusuluhisha) kulingana na uhusiano wa kima cha chini cha sahili huhakikisha uchanya wa vipengele vya msingi katika mpango mpya wa marejeleo. Kwa hivyo, tumethibitisha kuwa chini ya masharti yaliyoainishwa kwenye ishara kwa hakika inawezekana kuhama kutoka kwa mpango mmoja wa marejeleo hadi mwingine wenye thamani kubwa ya kazi ya lengo f(x). Kumbuka kwamba tayari tunajua thamani ya kigezo kipya cha msingi x m+s katika mpango mpya wa marejeleo: ni sawa na b ko /b ks . Kama ilivyo kwa nambari za nambari za anuwai za msingi zilizobaki katika mpango mpya wa kumbukumbu na dhamana inayolingana ya f (x), zinaweza kupatikana tu baada ya mfumo uliobadilishwa wa vijiti vya msingi x 1;..., x m+s. ; ...,x m itaonyeshwa kupitia mfumo uliorekebishwa wa vigeu vya bure x m+1,…,x k,…, x n. Ili kufanya hivyo, hebu tuweke; sheria ambazo hali za tatizo hubadilishwa kutoka msingi mmoja hadi mwingine. Mgawo b ks = 0 kwa x m+s katika equation hii inaitwa kipengele cha kutatua. Katika usawa (2.7), kigezo kipya cha msingi x m+s kinaonyeshwa kulingana na vigeu visivyolipishwa, kati ya ambavyo kigezo cha awali cha x k sasa kinapatikana. Kwa hivyo, vigezo vya x m+s na x k vilibadilishana majukumu. Wacha vivyo hivyo tueleze vigeu vya msingi vilivyobaki kupitia seti mpya ya vigeu vya bure. Kwa kusudi hili, tunabadilisha thamani x m+s kutoka kwa usawa uliosalia (tunaashiria f kwa x 0, kisha usawa utajumuishwa kwenye mfumo katika i = 0) Kuleta mfumo kwa msingi mpya huitwa mabadiliko ya simplex. Ikiwa mabadiliko ya sahili yanazingatiwa kama operesheni rasmi ya aljebra, basi mtu anaweza kugundua kuwa kama matokeo ya operesheni hii, majukumu yanagawanywa tena kati ya vijiti viwili vilivyojumuishwa katika mfumo fulani wa kazi za mstari: kigezo kimoja hutoka kwa tegemezi hadi huru, na nyingine. , kinyume chake, kutoka kwa kujitegemea hadi kwa tegemezi. Operesheni hii inajulikana katika aljebra kama hatua ya kuondoa Yordani. Kurasa 123 (Faili ya Neno) Tazama kurasa zote Mpito kutoka kwa mpango mmoja wa marejeleo hadi mwingine, thamani ya kazi ya lengo ambayo ni kubwa kuliko ile ya awali. 3. Kuangalia ubora wa mpango unaosababisha, kukuwezesha kuacha mara moja utafutaji wa mipango ya kumbukumbu au kuteka hitimisho kwamba hakuna mpango bora. Njia rahisi ni msingi wa nadharia zifuatazo, ambazo hutolewa bila uthibitisho. Nadharia 1.2 (juu ya uwepo wa mpango wa msaada) Ikiwa fomu ya mstari imefungwa kutoka juu kwenye seti isiyo tupu D, basi LLP inaweza kutatuliwa, yaani, kuna uhakika kwamba Nadharia 1.3 (jaribio la ukamilifu wa mpango wa usaidizi) Mpango wa msingi kuitwa rahisix - tofauti au tathmini. Nadharia 1.4 (jaribio la kutokuwepo kwa mpango bora) Ikiwa kwa baadhi ya k na kati ya nambari, hakuna chanya, i.e. yote, lengo la kazi ya tatizo si mdogo kwa seti ya ufumbuzi upembuzi yakinifu na haina ufumbuzi wa mwisho. Nadharia 1.5 (jaribio la kuwepo kwa mpango bora wa usaidizi) Ikiwa mpango wa kumbukumbu 1. Shida lazima ipunguzwe hadi fomu ya kisheria. Mfumo wa vikwazo hupunguzwa kwa msingi wa kitengo, i.e. inatatuliwa kwa kuzingatia baadhi ya vigezo vya msingi (bila kupoteza jumla, tutafikiri kwamba kwa heshima na vigezo vya kwanza vya m) kwa kutumia njia ya Jordan-Gauss (mfumo (1.19)). Suluhisho la kumbukumbu la awali linalolingana linapatikana. 2. Kwa urahisi wa mahesabu, tunaandika kila kitu kwenye meza rahisi (Jedwali 1.1). Safu ya Msingi ina orodha ya vigezo vya msingi; safu inayofuata "c j msingi" ina coefficients ya kazi ya lengo kwa vigezo vya msingi; safu zifuatazo zina coefficients ya mfumo wa vikwazo kwa vigezo vinavyolingana; safu "b i" ni safu ya wanachama huru wa mfumo wa vikwazo. Mstari wa mwisho una simplex - tofauti zilizohesabiwa kwa kutumia formula (1.21) na kiini cha mwisho kina thamani ya kazi ya lengo =. Kumbuka kwamba simplex - tofauti za vigezo vya msingi - daima ni sawa na sifuri. Jedwali 1.1 c j msingi 3. Ikiwa kila kitu ni rahisi, tofauti sio hasi, i.e. , basi mpango wa kumbukumbu ni bora. 4. Ikiwa angalau rahisix - tofauti ni hasi, , na hakuna vipengele vyema katika safu inayofanana, basi tatizo halina suluhisho mojawapo, i.e. . 5. Ikiwa angalau moja rahisi - tofauti ni hasi, , na katika kila safu ambayo ina alama hasi kuna angalau kipengele kimoja chanya, basi mpango wa kumbukumbu unaosababishwa unaweza kuboreshwa. 6. Chagua wezesha safu"p", ambayo inalingana na alama ndogo hasi. 7. Chagua safu ya ruhusa"k", ambayo inalingana na uwiano mdogo zaidi wa pande za kulia kwa vipengele vyema vya safu ya azimio. Kipengele kwenye makutano ya safu ya azimio na safu ya azimio inaitwa kipengele cha kuruhusu. 8. Tunaendelea kwenye jedwali jipya la simplex, ambalo kutakuwa na msingi mpya: kutofautiana kwa msingi kwenye mahali pa "k" katika msingi wa zamani hubadilishwa kuwa tofauti mpya. Vekta inayolingana ya kigeu kipya cha msingi lazima igeuzwe kuwa kitengo kimoja. Ili kufanya hivyo, gawanya mstari wa azimio ili kitengo kionekane mahali pa kipengele cha azimio. Kwa kuzidisha mstari wa azimio kwa nambari zinazofaa na kuiongeza na mistari mingine, tunapata zero kwenye safu ya azimio. Baada ya hayo, tunaandika mpango mpya wa kumbukumbu na kuhesabu tena mstari wa makadirio. Wacha tuendelee kwenye nukta ya 3. Ujumbe kuhusu mpango mbadala. Ikiwa makadirio yote ya vigezo vya bure katika jedwali rahisi la mwisho yanageuka kuwa kubwa zaidi kuliko sifuri, basi mpango bora ni wa kipekee. Ikiwa angalau makadirio moja ya kutofautisha bure ni sawa na sifuri, basi kuna chaguo bora zaidi (seti ya mipango bora). Ili kupata suluhisho mbadala, ni muhimu kuchukua hatua moja ya njia rahisi, kuchagua kama safu ya kutatua ya kutofautiana kwa bure, ambayo inalingana na alama ya sifuri. Katika kesi hii, seti ya mipango yote bora inaweza kuwakilishwa kama mchanganyiko wa laini wa kusaidia mipango bora: Mfano 5.
Tatua ZLP kwa kutumia njia rahisi: Tunapunguza mfumo wa usawa wa mstari (1.22) hadi fomu ya kisheria kwa kuanzisha kigezo cha ziada kisicho hasi katika kila ukosefu wa usawa. Tunapata mfumo wa milinganyo ya mstari: Kazi ya lengo itakuwa na fomu Tunaunda meza rahisix: Jedwali 1.2 c j msingi Mpango wa msingi 
Sehemu ya maandishi ya kazi
.
shida (1.18) ni sawa ikiwa kwa j yote ,
ni kuridhika, ambapo wingi
(1.21)
tatizo (1.18) sio kuharibika kwa baadhi ya k, lakini kati ya nambari, kuna angalau moja chanya, i.e. sio kila kitu, basi kuna mpango wa kumbukumbu 
, ambapo utendakazi wa lengo huchukua thamani isiyopungua katika mpango uliopita: 
.Njia rahisi ya algorithm
, Wapi 
.
(1.22)
(1.23)
sio bora, kwa sababu katika mstari wa ratings kuna vipengele hasi = - 3 na = - 2. Tunachagua safu ya kutatua - ya kwanza, kwa sababu inalingana na kiwango cha chini cha makadirio mabaya = - 3. Kwa vipengele vyote vyema vya safu ya kwanza, tunahesabu uwiano . Tunapata kiwango cha chini cha uwiano huu: 
. Inafanana na mstari wa pili, kwa hiyo itakuwa ya kuruhusiwa. Kwa hivyo, kipengele cha kutatua kinaonyesha kwamba kutofautiana x 4 inatokana na msingi, na badala yake kutakuwa na kutofautiana x 1 kwa msingi. Tunajaza jedwali mpya la simplex (Jedwali 1.3). Ili kufanya hivyo, tunageuza safu ya kwanza kwenye safu moja. Tunazidisha mstari wa pili na (-1/2) na kuiongeza na ya kwanza, andika matokeo kwenye mstari wa kwanza wa jedwali mpya la simplex; vivyo hivyo, zidisha mstari wa pili kwa (1/2) na uongeze kwa tatu; kugawanya mstari wa azimio na 2; Tunaandika tena ya nne bila mabadiliko.
