Hotuba ya 3. Meza rahisix. Algorithm njia rahisix.

§ NJIA 3 RAHISI

3.1. Wazo la jumla la njia rahisix. Tafsiri ya kijiometri

Njia ya picha inatumika kwa darasa nyembamba sana la shida programu ya mstari: inaweza kutatua kwa ufanisi matatizo yasiyo na zaidi ya vigezo viwili. Nadharia za msingi za programu ya mstari zilizingatiwa, ambayo inafuata kwamba ikiwa shida ya programu ya mstari ina suluhisho bora, basi inalingana na angalau sehemu moja ya kona ya suluhisho la polyhedron na sanjari, kulingana na angalau, na mojawapo ya ufumbuzi wa msingi unaokubalika wa mfumo wa vikwazo. Njia ya kutatua shida yoyote ya upangaji wa laini ilionyeshwa: kuhesabu idadi kamili ya suluhisho za msingi zinazowezekana za mfumo wa vikwazo na kuchagua kati yao moja ambayo kazi ya lengo hufanya suluhisho bora. Kijiometri, hii inalingana na kuorodhesha sehemu zote za kona za polihedron ya suluhisho. Utafutaji wa kina kama huo hatimaye utasababisha suluhisho bora (ikiwa lipo), lakini utekelezaji wake wa vitendo unahusishwa na shida kubwa, kwani kwa shida za kweli idadi ya suluhisho za kimsingi zinazowezekana, ingawa zina mwisho, zinaweza kuwa kubwa sana.

Idadi ya ufumbuzi wa msingi unaoruhusiwa wa kutafutwa inaweza kupunguzwa ikiwa utafutaji haufanyiki kwa nasibu, lakini kwa kuzingatia mabadiliko katika kazi ya mstari, i.e. kuhakikisha kwamba kila mtu suluhisho linalofuata ilikuwa "bora" (au angalau "hakuna mbaya zaidi") kuliko ile ya awali, kulingana na maadili ya kazi ya mstari (kuiongeza wakati wa kupata kiwango cha juu, kuipunguza wakati wa kupata kiwango cha chini.
). Utafutaji huu hukuruhusu kupunguza idadi ya hatua unapopata bora zaidi. Hebu tueleze hili kwa mfano wa picha.

Acha eneo la suluhisho zinazowezekana liwakilishwe na poligoni ABCDE. Wacha tufikirie kuwa sehemu yake ya kona A inalingana na suluhisho la msingi linalowezekana. Utafutaji wa nasibu utahitaji kujaribu masuluhisho matano yanayowezekana yanayolingana na sehemu tano za pembezoni. Hata hivyo, ni wazi kutoka kwa kuchora kwamba baada ya juu A ni faida kuhamia vertex jirani NDANI, na kisha kwa hatua mojawapo NA. Badala ya tano, tulipitia wima tatu tu, tukiboresha utendakazi wa mstari.

Wazo la kuboresha suluhisho kwa mafanikio liliunda msingi wa njia ya ulimwengu ya kutatua shida za programu - njia rahisix au njia ya uboreshaji mfuatano wa mpango.

Maana ya kijiometri ya njia sahili inajumuisha mpito wa mfuatano kutoka kwa kipeo kimoja cha polihedron ya kizuizi (inayoitwa ya kwanza) hadi ya jirani, ambayo kazi ya mstari inachukua thamani bora (angalau sio mbaya zaidi) kuhusiana na lengo la kazi; mpaka suluhisho mojawapo linapatikana - vertex wapi thamani mojawapo kazi ya lengo (ikiwa shida ina optimum ya mwisho).

Njia rahisi ilipendekezwa kwanza na mwanasayansi wa Marekani J. Danzig mwaka wa 1949, lakini nyuma mwaka wa 1939 mawazo ya njia hiyo yalitengenezwa na mwanasayansi wa Kirusi L.V. Kantorovich.

Njia rahisi, ambayo inaruhusu kutatua shida yoyote ya programu ya mstari, ni ya ulimwengu wote. Hivi sasa, hutumiwa kwa mahesabu ya kompyuta, lakini mifano rahisi kwa kutumia njia rahisi inaweza kutatuliwa kwa manually.

Ili kutekeleza njia rahisi - uboreshaji wa mlolongo wa suluhisho - ni muhimu kujua mambo makuu matatu:

njia ya kuamua suluhisho la msingi linalowezekana kwa shida;

utawala wa mpito kwa bora (zaidi kwa usahihi, si mbaya zaidi) ufumbuzi;

kigezo cha kuangalia ukamilifu wa suluhisho lililopatikana.

Ili kutumia njia rahisi, shida ya programu ya mstari lazima ipunguzwe hadi fomu ya kisheria, i.e. mfumo wa vikwazo lazima uwasilishwe kwa namna ya equations.

Maandiko yanaelezea kwa undani wa kutosha: kutafuta mpango wa msaada wa awali (suluhisho la msingi linalokubalika), pia kwa kutumia njia ya msingi ya bandia, kutafuta mpango bora wa usaidizi, kutatua matatizo kwa kutumia meza rahisi.

3.2. Algorithm ya njia rahisix.

Wacha tuzingatie suluhisho la ZLP kwa kutumia njia rahisi na tuwasilishe kuhusiana na shida ya kuongeza.

1. Kulingana na hali ya tatizo, mfano wake wa hisabati umeundwa.

2. Mfano uliokusanywa unabadilishwa kuwa fomu ya kisheria. Katika kesi hii, msingi na mpango wa kumbukumbu wa awali unaweza kutambuliwa.

3. Mfano wa kisheria wa tatizo umeandikwa kwa namna ya meza rahisi ili maneno yote ya bure yasiwe hasi. Ikiwa mpango wa awali wa marejeleo umechaguliwa, basi endelea hatua ya 5.

Jedwali la Simplex: mfumo wa milinganyo ya vizuizi na kazi ya lengo huingizwa kwa namna ya misemo iliyotatuliwa kuhusiana na msingi wa awali. Mstari ulio na coefficients kazi ya lengo
, kuitwa
– kamba au mfuatano wa kitendakazi lengwa.

4. Pata mpango wa awali wa kumbukumbu kwa kufanya mabadiliko ya simplex na vipengele vyema vya kutatua vinavyolingana na mahusiano ya kima cha chini cha simplex, na bila kuzingatia ishara za vipengele.
- mistari. Ikiwa wakati wa mabadiliko safu ya 0 inakabiliwa, vipengele vyote, isipokuwa kwa muda wa bure, ni zero, basi mfumo wa usawa wa vikwazo kwa tatizo haufanani. Ikiwa tunakutana na safu-0 ambayo, mbali na neno la bure, hakuna vipengele vingine vyema, basi mfumo wa usawa wa vikwazo hauna ufumbuzi usio na hasi.

Tutaita kupunguzwa kwa mfumo (2.55), (2.56) kwa msingi mpya rahisix mabadiliko . 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 algebra kama Hatua ya kuondoa Jordan.

5. Mpango wa awali wa usaidizi uliopatikana unachunguzwa kwa ukamilifu:

a) ikiwa ndani
- hakuna vipengele hasi katika safu (bila kuhesabu neno la bure), basi mpango huo ni bora. Ikiwa hakuna zero, basi kuna mpango mmoja tu mzuri; ikiwa kuna angalau sifuri moja, basi kuna idadi isiyo na kipimo ya mipango bora;

b) ikiwa c
- kuna angalau kipengele kimoja hasi kwenye safu, ambacho kinalingana na safu ya vitu visivyo chanya, basi
;

c) ikiwa ndani
- safu ina angalau kipengele kimoja hasi, na safu yake ina angalau kipengele kimoja chanya, basi unaweza kuhamia mpya. mpango wa kumbukumbu, karibu na mojawapo. Ili kufanya hivyo, safu iliyoainishwa lazima iteuliwe kama safu ya kusuluhisha, kwa kutumia uwiano wa chini wa sahili, pata safu ya kusuluhisha na ufanye mabadiliko rahisi. Mpango wa marejeleo unaotokana unachunguzwa tena kwa ukamilifu. Mchakato ulioelezewa unarudiwa hadi mpango mzuri unapatikana au hadi kutosuluhishwa kwa shida kuanzishwa.

Safu ya coefficients kwa variable iliyojumuishwa katika msingi inaitwa kutatua. Kwa hivyo, kuchagua tofauti iliyoingia kwenye msingi (au kuchagua safu ya kutatua) na kipengele hasi
-strings, tunatoa kazi inayoongezeka
.

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. Uchaguzi wa kigezo kisichojumuishwa kwenye msingi (au chaguo la mstari wa kusuluhisha) kulingana na dhamana ya kima cha chini cha uhusiano wa sahili, kama ilivyokwishaanzishwa, uchanya wa vipengele vya msingi katika mpango mpya wa marejeleo.

Katika hatua ya 3 ya algorithm, inachukuliwa kuwa vipengele vyote vya safu ya masharti ya bure sio hasi. Mahitaji haya sio lazima, lakini ikiwa yamefikiwa, basi mabadiliko yote ya simplex yanayofuata yanafanywa tu na vipengele vyema vya kutatua, ambavyo ni rahisi kwa mahesabu. Ikiwa kuna nambari hasi kwenye safu ya maneno ya bure, basi kipengele cha kutatua kinachaguliwa kama ifuatavyo:

1) angalia mstari unaolingana na neno hasi la bure, kwa mfano - safu, na uchague kitu chochote kibaya ndani yake, na safu inayolingana inachukuliwa kusuluhisha (tunadhani kuwa vikwazo vya shida ni sawa);

2) tengeneza mahusiano ya vipengele vya safu ya maneno ya bure kwa vipengele vinavyolingana vya safu ya kutatua ambayo ina ishara sawa (mahusiano rahisi);

3) chagua uhusiano mdogo zaidi wa rahisix. Hii itaamua kamba ya kuwezesha. Wacha iwe, kwa mfano, R- mstari;

4) katika makutano ya safu ya kutatua na safu, kipengele cha kutatua kinapatikana. Ikiwa kipengele kinaruhusu -strings, kisha baada ya mabadiliko ya simplex neno la bure la kamba hii litakuwa chanya. Vinginevyo, katika hatua inayofuata tunageuka tena - mstari. Ikiwa tatizo linaweza kutatuliwa, basi baada ya idadi fulani ya hatua hakutakuwa na vipengele hasi vilivyoachwa kwenye safu ya maneno ya bure.

Ikiwa hali fulani ya uzalishaji halisi imewekwa katika mfumo wa PLP, basi vigezo vya ziada ambavyo vinapaswa kuletwa kwenye mfano katika mchakato wa kuibadilisha kuwa fomu ya kisheria daima huwa na maana fulani ya kiuchumi.

Mojawapo ya njia za kutatua shida za utoshelezaji ( kawaida huhusishwa na kupata kiwango cha chini au cha juu zaidi) upangaji wa mstari unaitwa . Njia rahisix inajumuisha kikundi kizima cha kanuni na mbinu za kutatua matatizo ya programu ya mstari. Moja ya njia hizi, ambayo inahusisha kurekodi data ya chanzo na kuhesabu upya katika meza maalum, inaitwa njia ya tabular simplex.

Wacha tuchunguze algorithm ya njia rahisi ya tabular kwa kutumia mfano wa suluhisho kazi ya uzalishaji, ambayo inakaribia kupata mpango wa uzalishaji ambao unahakikisha faida kubwa.

Ingiza data ya tatizo la mbinu rahisi

Kampuni hiyo inazalisha aina 4 za bidhaa, inazichakata kwenye mashine 3.

Viwango vya muda (min./piece) vya usindikaji wa bidhaa kwenye mashine vimebainishwa na matrix A:

Mfuko wa muda wa uendeshaji wa mashine (min.) umebainishwa katika matrix B:

Faida kutokana na mauzo ya kila kitengo cha bidhaa (RUB/kipande) hutolewa na matrix C:

Kusudi la kazi ya uzalishaji

Tengeneza mpango wa uzalishaji ambao utaongeza faida ya biashara.

Kutatua tatizo kwa kutumia njia ya tabular simplex

(1) Hebu tuonyeshe kwa X1, X2, X3, X4 idadi iliyopangwa ya bidhaa za kila aina. Kisha mpango unaotaka: ( X1, X2, X3, X4)

(2) Wacha tuandike vizuizi vya mpango kwa namna ya mfumo wa equations:

(3) Kisha faida inayolengwa ni:

Hiyo ni, faida kutoka kwa kutimiza mpango wa uzalishaji inapaswa kuwa ya juu.

(4) Ili kutatua tatizo lililokithiri la masharti, tunabadilisha mfumo wa kutofautiana na mfumo milinganyo ya mstari kwa kuanzisha viambishi vya ziada visivyo hasi ndani yake ( X5, X6, X7).

(5) Tukubali yafuatayo mpango wa kumbukumbu:

X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80

(6) Wacha tuingize data ndani meza rahisix:

Katika mstari wa mwisho tunaingia coefficients ya kazi ya lengo na thamani yake yenyewe na ishara kinyume;

(7) Chagua ndani mstari wa mwisho kubwa zaidi (moduli) nambari hasi.

Hebu tuhesabu b = N / Vipengee_vya_safu_iliyochaguliwa

Kati ya maadili yaliyohesabiwa ya b tunachagua angalau.

Makutano ya safu wima na safu iliyochaguliwa itatupa kipengee cha kusuluhisha. Tunabadilisha msingi kuwa tofauti inayolingana na kipengele cha kusuluhisha ( X5 hadi X1).

• Kipengele cha kusuluhisha chenyewe kinageuka kuwa 1.
• Kwa vipengele vya mstari wa azimio - ij (*) = ij / RE ( yaani, tunagawanya kila kipengele kwa thamani ya kipengele cha kutatua na kupata data mpya).
• Kwa vipengele vya safu wima ya azimio, huwekwa upya hadi sifuri.
• Tunahesabu tena vitu vilivyobaki vya meza kwa kutumia sheria ya mstatili.

a ij (*) = a ij – (A * B / RE)

Kama unavyoona, tunachukua kisanduku cha sasa kinachohesabiwa upya na kisanduku chenye kipengele cha kusuluhisha. Wanaunda pembe tofauti za mstatili. Ifuatayo, tunazidisha maadili kutoka kwa seli za pembe zingine 2 za mstatili huu. Kazi hii ( A * B) gawanya kwa kipengele cha kusuluhisha ( RE) Na toa kutoka kwa seli ya sasa inayohesabiwa upya ( ij) Nini kimetokea. Tunapata thamani mpya - ij (*).

(9) Angalia mstari wa mwisho tena ( c) kwenye uwepo wa nambari hasi. Ikiwa hawapo, mpango bora umepatikana, nenda kwa hatua ya mwisho kutatua tatizo. Ikiwa kuna, mpango bado haujawa sawa, na jedwali rahisi linahitaji kuhesabiwa tena.

Kwa kuwa tuna tena nambari hasi kwenye mstari wa mwisho, tunaanza urudiaji mpya wa mahesabu.

(10) Kwa kuwa hakuna vipengele hasi katika mstari wa mwisho, hii ina maana kwamba tumepata mpango bora wa uzalishaji! Yaani: tutazalisha bidhaa ambazo zimehamia kwenye safu ya "Msingi" - X1 na X2. Tunajua faida kutokana na uzalishaji wa kila kitengo cha pato ( matrix C) Inabakia kuzidisha kiasi cha uzalishaji kilichopatikana cha bidhaa 1 na 2 na faida kwa kipande 1, tunapata ya mwisho ( upeo! ) faida kwa mpango fulani wa uzalishaji.

JIBU:

X1 = pcs 32., X2 = pcs 20., X3 = pcs 0., X4 = 0 pcs.

P = 48 * 32 + 33 * 20 = 2,196 kusugua.

Galyautdinov R.R.

© Kunakili nyenzo inaruhusiwa tu ikiwa kiungo cha moja kwa moja kwa

. Njia rahisi ya algorithm

Mfano 5.1. Tatua shida ifuatayo ya upangaji wa laini kwa kutumia njia rahisix:

Suluhisho:

I kurudia:

x3, x4, x5, x6 x1,x2. Wacha tuonyeshe anuwai za kimsingi kwa suala la bure:

Wacha tupunguze kazi inayolengwa mtazamo unaofuata:

Kulingana na shida iliyopatikana, tutaunda jedwali la awali la simplex:

Jedwali 5.3

Jedwali la asili la simplex

				Mahusiano ya Tathmini

Kulingana na ufafanuzi wa suluhisho la msingi, anuwai za bure ni sawa na sifuri, na maadili ya anuwai ya msingi ni sawa na maadili yanayolingana ya nambari za bure, i.e.:

Hatua ya 3: kuangalia utangamano wa mfumo wa vikwazo vya PAP.

Katika marudio haya (katika Jedwali 5.3), ishara ya kutokwenda kwa mfumo wa kizuizi (ishara ya 1) haijatambuliwa (yaani, hakuna mstari na nambari hasi ya bure (isipokuwa safu ya kazi ya lengo) ambayo haingekuwa. kuwa angalau kipengele kimoja hasi (yaani . mgawo hasi wa kigezo kisicholipishwa)).

Katika marudio haya (katika Jedwali 5.3), ishara ya kutokuwa na mipaka ya kazi ya lengo (ishara ya 2) haikutambuliwa (yaani, hakuna safu iliyo na kipengele hasi katika safu ya kazi ya lengo (isipokuwa safu ya nambari za bure. ) ambamo kusingekuwa na angalau kipengele kimoja chanya) .

Kwa kuwa ufumbuzi wa msingi uliopatikana hauna vipengele vibaya, inaruhusiwa.

Hatua ya 6: ukaguzi wa ubora.

Suluhisho la msingi lililopatikana sio sawa, kwani kulingana na kigezo cha ukamilifu (ishara ya 4) haipaswi kuwa na vipengele hasi katika mstari wa kazi ya lengo ( nambari ya bure mstari huu hauzingatiwi wakati wa kuzingatia sifa hii). Kwa hivyo, kulingana na algorithm ya njia rahisi, tunaendelea hadi hatua ya 8.

Kwa kuwa suluhisho la msingi lililopatikana linakubalika, tutafuta safu ya kutatua kulingana na mpango wafuatayo: tunaamua nguzo zilizo na mambo mabaya katika safu ya kazi ya lengo (isipokuwa safu ya nambari za bure). Kulingana na Jedwali 5.3, kuna safu mbili kama hizi: safu " x1"na safu" x2" Kutoka kwa safu wima kama hizo, ile iliyo na kipengee kidogo zaidi kwenye safu ya kazi inayolengwa imechaguliwa. Yeye ndiye atakayeruhusu. Safu wima " x2" ina kipengele kidogo zaidi (–3) ikilinganishwa na safu " x1

Kuamua mstari wa kusuluhisha, tunapata makadirio chanya ya makadirio ya nambari za bure kwa vipengele vya safu wima ya kusuluhisha; mstari unaolingana na uwiano mdogo zaidi wa tathmini unakubaliwa kama kutatuliwa.

Jedwali 5.4

Jedwali la asili la simplex

Katika Jedwali 5.4, uhusiano mdogo kabisa wa tathmini unalingana na mstari ". x5", kwa hivyo, itakuwa inaruhusiwa.

Kipengele kilicho katika makutano ya safu wima inayowasha na safu mlalo kuwezesha kinakubaliwa kuwashwa. Katika mfano wetu, hii ndio kitu ambacho kiko kwenye makutano ya mstari " x5"na safu" x2».

Kipengele cha kusuluhisha kinaonyesha msingi mmoja na kigezo kimoja kisicholipishwa ambacho lazima kibadilishwe katika jedwali rahisi ili kuhamia kwenye suluhisho jipya la msingi "lililoboreshwa". KATIKA kwa kesi hii hizi ni vigezo x5 Na x2, katika jedwali jipya la simplex (Jedwali 5.5) tunawabadilisha.

9.1. Mabadiliko ya kipengele cha kutatua.

Kipengele cha azimio cha Jedwali 5.4 kinabadilishwa kama ifuatavyo:

Tunaingiza matokeo katika seli sawa katika Jedwali 5.5.

9.2. Ubadilishaji wa mfuatano wa azimio.

Tunagawanya vipengele vya mstari wa kutatua wa meza 5.4 kwa kipengele cha kutatua cha meza hii rahisi, matokeo yanafaa katika seli zinazofanana za jedwali jipya la simplex (meza 5.5). Mabadiliko ya vipengele vya kamba ya azimio hutolewa katika Jedwali 5.5.

9.3. Ubadilishaji wa safu wima ya mwonekano.

Tunagawanya vipengele vya safu ya azimio la Jedwali 5.4 kwa kipengele cha azimio la meza hii rahisi, na matokeo yanachukuliwa kwa ishara kinyume. Matokeo yaliyopatikana yanafaa katika seli zinazofanana za jedwali jipya la simplex (Jedwali 5.5). Mabadiliko ya vipengele vya safu ya azimio hutolewa katika Jedwali 5.5.

9.4. Mabadiliko ya vipengele vilivyobaki vya meza ya simplex.

Mabadiliko ya vipengele vilivyobaki vya meza ya simplex (yaani, vipengele ambavyo haviko kwenye safu ya kutatua na safu ya kutatua) hufanyika kulingana na utawala wa "mstatili".

Kwa mfano, fikiria kubadilisha kipengee kilicho kwenye makutano ya mstari " x3" na safuwima "", tutaashiria kwa masharti " x3" Katika Jedwali 5.4, kiakili tunachora mstatili, kipeo kimoja ambacho kiko kwenye seli ambayo thamani yake tunabadilisha (yaani, kwenye seli " x3"), na nyingine (kipeo cha mshazari) iko kwenye seli iliyo na kipengele cha kusuluhisha. Vipeo vingine viwili (vya ulalo wa pili) vimedhamiriwa kipekee. Kisha thamani iliyobadilishwa ya seli " x3" itakuwa sawa na thamani ya awali ya seli hii ukiondoa sehemu, katika dhehebu ambayo ni kipengele cha kusuluhisha (kutoka Jedwali 5.4), na katika nambari ni bidhaa ya vipeo vingine viwili ambavyo havijatumika, yaani:

« x3»: .

Thamani za seli zingine hubadilishwa vile vile:

« x3 x1»: ;

« x4»: ;

« x4 x1»: ;

« x6»: ;

« x6 x1»: ;

«»: ;

« x1»: .

Kama matokeo ya mabadiliko haya, tulipokea mpya meza rahisix(Jedwali 5.5).

II kurudia:

Hatua ya 1: kuchora meza rahisix.

Jedwali 5.5

Jedwali rahisixII marudio

				Inakadiriwa uhusiano

Hatua ya 2: uamuzi wa suluhisho la msingi.

Kama matokeo ya mabadiliko rahisi, suluhisho mpya la msingi lilipatikana (Jedwali 5.5):

Kama unaweza kuona, na suluhisho hili la msingi thamani ya kazi ya lengo = 15, ambayo ni kubwa zaidi kuliko suluhisho la msingi la awali.

Kutokubaliana kwa mfumo wa vikwazo kwa mujibu wa kipengele 1 katika Jedwali 5.5 haijatambuliwa.

Hatua ya 4: kuangalia mipaka ya utendaji wa lengo.

Ukomo wa kazi ya lengo kwa mujibu wa kigezo cha 2 katika Jedwali 5.5 haijafunuliwa.

Hatua ya 5: kuangalia kuruhusiwa kwa suluhisho la msingi lililopatikana.

Suluhisho la msingi lililopatikana kwa mujibu wa kigezo cha 4 sio sawa, kwani mstari wa kazi ya lengo la jedwali rahisi (Jedwali 5.5) lina kipengele hasi: -2 (nambari ya bure ya mstari huu haijazingatiwa wakati wa kuzingatia hili. tabia). Kwa hivyo, tunaendelea hadi hatua ya 8.

Hatua ya 8: uamuzi wa kipengele cha kutatua.

8.1. Ufafanuzi wa safu wima ya azimio.

Suluhisho la msingi lililopatikana linakubalika; tunaamua safu wima zilizo na vitu hasi kwenye safu ya chaguo la kukokotoa (isipokuwa safu ya nambari za bure). Kulingana na Jedwali 5.5, kuna safu moja tu kama hii: " x1" Kwa hivyo, tunaikubali kama inavyoruhusiwa.

8.2. Ufafanuzi wa mfuatano wa kuwezesha.

Kulingana na maadili yaliyopatikana ya uhusiano mzuri wa tathmini katika Jedwali 5.6, kiwango cha chini ni uhusiano unaolingana na mstari " x3" Kwa hivyo, tunaikubali kama inavyoruhusiwa.

Jedwali 5.6

Jedwali rahisixII marudio

				Inakadiriwa uhusiano
				3/1=3 – dakika

Hatua ya 9: mabadiliko ya jedwali rahisi.

Mabadiliko ya jedwali la simplex (Jedwali 5.6) hufanywa kwa njia sawa na iteration ya awali. Matokeo ya mabadiliko ya vipengele vya jedwali rahisi yanatolewa katika Jedwali 5.7.

III kurudia

Kulingana na matokeo ya mabadiliko ya simplex ya iteration ya awali, tunaunda jedwali jipya la simplex:

Jedwali 5.7

Jedwali rahisixIII marudio

				Inakadiriwa uhusiano

Hatua ya 2: uamuzi wa suluhisho la msingi.

Kama matokeo ya mabadiliko ya kawaida, suluhisho mpya la msingi lilipatikana (Jedwali 5.7):

Hatua ya 3: kuangalia utangamano wa mfumo wa vikwazo.

Kutokubaliana kwa mfumo wa vikwazo kwa mujibu wa kipengele 1 katika Jedwali 5.7 haijatambuliwa.

Hatua ya 4: kuangalia mipaka ya utendaji wa lengo.

Ukomo wa kazi ya lengo kwa mujibu wa kigezo cha 2 katika Jedwali 5.7 haijafunuliwa.

Hatua ya 5: kuangalia kuruhusiwa kwa suluhisho la msingi lililopatikana.

Suluhisho la msingi lililopatikana kwa mujibu wa kigezo cha 3 linakubalika, kwani haina vipengele vibaya.

Hatua ya 6: kuangalia ubora wa suluhisho la msingi lililopatikana.

Suluhisho la msingi lililopatikana kwa mujibu wa kigezo cha 4 sio sawa, kwani mstari wa kazi ya lengo la jedwali rahisi (Jedwali 5.7) lina kipengele hasi: -3 (nambari ya bure ya mstari huu haijazingatiwa wakati wa kuzingatia hili. tabia). Kwa hivyo, tunaendelea hadi hatua ya 8.

Hatua ya 8: uamuzi wa kipengele cha kutatua.

8.1. Ufafanuzi wa safu wima ya azimio.

Suluhisho la msingi lililopatikana linakubalika; tunaamua safu wima zilizo na vitu hasi kwenye safu ya chaguo la kukokotoa (isipokuwa safu ya nambari za bure). Kulingana na Jedwali 5.7, kuna safu moja tu kama hii: " x5" Kwa hivyo, tunaikubali kama inavyoruhusiwa.

8.2. Ufafanuzi wa mfuatano wa kuwezesha.

Kulingana na maadili yaliyopatikana ya uhusiano mzuri wa tathmini katika Jedwali 5.8, kiwango cha chini ni uhusiano unaolingana na mstari " x4" Kwa hivyo, tunaikubali kama inavyoruhusiwa.

Jedwali 5.8

Jedwali rahisixIII marudio

				Inakadiriwa uhusiano
				5/5=1 – dakika

Hatua ya 9: mabadiliko ya jedwali rahisi.

Mabadiliko ya jedwali la simplex (Jedwali 5.8) hufanywa kwa njia sawa na iteration ya awali. Matokeo ya mabadiliko ya vipengele vya jedwali rahisi yanatolewa katika Jedwali 5.9.

IV kurudia

Hatua ya 1: ujenzi wa jedwali mpya la simplex.

Kulingana na matokeo ya mabadiliko ya simplex ya iteration ya awali, tunaunda jedwali jipya la simplex:

Jedwali 5.9

Jedwali rahisixIV marudio

				Inakadiriwa uhusiano
			–(–3/5)=3/5
			–(1/5)=–1/5
			–(9/5)=–9/5
			–(–3/5)=3/5

Hatua ya 2: uamuzi wa suluhisho la msingi.

Kama matokeo ya mabadiliko rahisi, suluhisho mpya la msingi lilipatikana; kulingana na Jedwali 5.9, suluhisho ni kama ifuatavyo.

Hatua ya 3: kuangalia utangamano wa mfumo wa vikwazo.

Kutokubaliana kwa mfumo wa vikwazo kwa mujibu wa kipengele 1 katika Jedwali 5.9 haijatambuliwa.

Hatua ya 4: kuangalia mipaka ya utendaji wa lengo.

Ukomo wa kazi ya lengo kwa mujibu wa kigezo cha 2 katika Jedwali 5.9 haijafunuliwa.

Hatua ya 5: kuangalia kuruhusiwa kwa suluhisho la msingi lililopatikana.

Suluhisho la msingi lililopatikana kwa mujibu wa kigezo cha 3 linakubalika, kwani haina vipengele vibaya.

Hatua ya 6: kuangalia ubora wa suluhisho la msingi lililopatikana.

Suluhisho la msingi lililopatikana kwa mujibu wa kipengele cha 4 ni mojawapo, kwa kuwa hakuna vipengele hasi katika mstari wa kazi ya lengo la jedwali la simplex (Jedwali 5.9) (nambari ya bure ya mstari huu haijazingatiwa wakati wa kuzingatia kipengele hiki) .

Hatua ya 7: kuangalia mbadala wa suluhisho.

Suluhisho lililopatikana ni la pekee, kwani mstari wa kazi ya lengo (Jedwali 5.9) haijumuishi vipengele sifuri(nambari ya bure ya mstari huu haijazingatiwa wakati wa kuzingatia tabia hii).

Jibu: thamani bora ya kazi ya lengo la tatizo linalozingatiwa =24, ambalo linapatikana kwa.

Mfano 5.2. Tatua tatizo la upangaji la mstari hapo juu mradi tu utendakazi wa lengo umepunguzwa:

Suluhisho:

I kurudia:

Hatua ya 1: uundaji wa jedwali la awali la simplex.

Tatizo asili upangaji wa mstari umebainishwa ndani fomu ya kawaida. Hebu tulete kwa fomu ya kisheria kwa kuanzisha kutofautiana kwa ziada isiyo ya hasi katika kila vikwazo vya kutofautiana, i.e.

Katika mfumo unaotokana wa equations, tunachukua vigezo vinavyoruhusiwa (msingi). x3, x4, x5, x6, basi vigezo vya bure vitakuwa x1,x2. Hebu tueleze vigezo vya msingi kwa suala la bure.

Kwa uuzaji wa vikundi vitatu vya bidhaa biashara ya kibiashara ina aina tatu za nyenzo ndogo na rasilimali za fedha kwa kiasi cha b 1 = 240, b 2 = 200, b 3 = 160 vitengo. Wakati huo huo, kwa uuzaji wa kikundi 1 cha bidhaa kwa rubles elfu 1. mauzo ya bidhaa, rasilimali ya aina ya kwanza hutumiwa kwa kiasi cha vitengo 11 = 2, rasilimali ya aina ya pili kwa kiasi cha vitengo 21 = 4, rasilimali ya aina ya tatu kwa kiasi cha 31 = 4 vitengo. Kwa uuzaji wa vikundi 2 na 3 vya bidhaa kwa rubles elfu 1. mauzo hutumika kulingana na rasilimali ya aina ya kwanza kwa kiasi cha 12 = 3, 13 = 6 vitengo, rasilimali ya aina ya pili kwa kiasi cha 22 = 2, 23 = 4 vitengo, rasilimali ya aina ya tatu kwa kiasi cha 32 = 6, a 33 = vitengo 8 . Faida kutoka kwa uuzaji wa vikundi vitatu vya bidhaa kwa rubles elfu 1. mauzo ni kwa mtiririko huo c 1 = 4, c 2 = 5, c 3 = 4 (rubles elfu). Amua kiasi kilichopangwa na muundo wa mauzo ya biashara ili faida hiyo biashara ya biashara ilikuwa kiwango cha juu.

Kwa shida ya moja kwa moja ya mipango ya mauzo, kutatuliwa kwa njia rahisix, tunga tatizo mbili programu ya mstari.
Sakinisha kuunganisha jozi za vigezo moja kwa moja na tatizo mbili.
Kwa mujibu wa jozi za kuunganisha za vigezo, kutoka kwa suluhisho la tatizo la moja kwa moja tunalopata suluhisho la shida mbili, ambayo huzalishwa tathmini ya rasilimali, zilizotumika kwa uuzaji wa bidhaa.

Kutatua tatizo kwa kutumia njia rahisix

Hebu x 1, x 2, x 3 iwe idadi ya bidhaa zinazouzwa, katika rubles elfu, 1, 2, vikundi 3, kwa mtiririko huo. Kisha mfano wa hisabati kazi ina fomu:

F = 4 x 1 + 5 x 2 + 4 x 3 -> upeo

0)))(~)" title="delim(lbrace)(matrix(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}

Tunatatua njia rahisix.

Tunaanzisha vigezo vya ziada x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 ili kubadilisha usawa katika usawa.

Wacha tuchukue x 4 = 240 kama msingi; x 5 = 200; x 6 = 160.

Tunaingiza data ndani meza rahisix

Jedwali la Simplex Nambari 1

Utendaji wa lengo:

0 240 + 0 200 + 0 160 = 0

Tunahesabu makadirio kwa kutumia formula:

Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0

Kwa kuwa kuna makadirio mabaya, mpango sio bora. Alama ya chini kabisa:

Tunaanzisha kutofautiana x 2 kwenye msingi.

Tunafafanua kutofautiana kujitokeza kutoka kwa msingi. Ili kufanya hivyo, tunapata uwiano mdogo usio hasi kwa safu ya x2.

= 26.667

Ndogo isiyo hasi: Q 3 = 26.667. Tunapata variable x 6 kutoka kwa msingi

Gawanya mstari wa 3 na 6.
Kutoka kwa mstari wa 1, toa mstari wa 3, ukizidishwa na 3
Kutoka kwa mstari wa 2, toa mstari wa 3, ukizidishwa na 2

Tunahesabu:

Tunapata meza mpya:

Jedwali la Simplex nambari 2

Utendaji wa lengo:

0 160 + 0 440/3 + 5 80/3 = 400/3

Tunahesabu makadirio kwa kutumia formula:

Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1)/3 + 5 1/6 - 0 = 5/6

Kwa kuwa kuna makadirio hasi Δ 1 = - 2/3, mpango sio bora.

Tunaanzisha kutofautiana x 1 kwenye msingi.

Tunafafanua kutofautiana kujitokeza kutoka kwa msingi. Ili kufanya hivyo, tunapata uwiano mdogo zaidi usio hasi kwa safu x 1.

Ndogo isiyo hasi: Q 3 = 40. Tunapata kigezo x 2 kutoka kwa msingi.

Gawanya mstari wa 3 kwa 2/3.
Kutoka kwa mstari wa 2, toa mstari wa 3, ukizidishwa na 8/3

Tunahesabu:

Tunapata meza mpya:

Jedwali la Simplex nambari 3

Utendaji wa lengo:

0 160 + 0 40 + 4 40 = 160

Tunahesabu makadirio kwa kutumia formula:

Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1) + 4 1/4 - 0 = 1

Kwa kuwa hakuna ukadiriaji hasi, mpango huo ni bora.

Suluhisho la shida:

Jibu

x 1 = 40; x2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x6 = 0; Kiwango cha juu cha F = 160

Hiyo ni, ni muhimu kuuza aina ya kwanza ya bidhaa kwa kiasi cha rubles elfu 40. Hakuna haja ya kuuza bidhaa za aina 2 na 3. Ambapo faida kubwa itakuwa F max = 160,000 rubles.

Suluhisho la shida mbili

Shida mbili ina fomu:

Z = 240 y 1 + 200 y 2 + 160 y 3 ->dakika

Title="delim(lbrace)(matrix(4)(1)((2y_1 + 4y_2 + 4y_3>=4) (3y_1 + 2y_2 + 6y_3>=5) (6y_1 + 4y_2 + 8y_3>=4) (y_1, y_2, y_3>= 0)))(~)">!}

Tunaanzisha vigezo vya ziada y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 ili kubadilisha usawa katika usawa.

Jozi zilizounganishwa za vijiti vya shida za moja kwa moja na mbili zina fomu:

Kutoka kwa jedwali la mwisho la simplex namba 3 la tatizo la moja kwa moja, tunapata suluhisho la tatizo mbili:

Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;

Matatizo ya programu ya mstari. Iko katika muundo unaofuatana unaoashiria mchakato unaozingatiwa. Suluhisho limegawanywa katika hatua tatu kuu: uteuzi wa vigezo, ujenzi wa mfumo wa vikwazo na kutafuta kazi ya lengo.

Kulingana na mgawanyiko huu, hali ya shida inaweza kusemwa upya kama ifuatavyo: mwisho wa kazi ya lengo Z(X) = f(x1, x2, ... ,xn) → max (min) na vigezo vinavyolingana, ikiwa inajulikana kuwa kukidhi mfumo wa vikwazo: Φ_i ( x1, x2, ... ,xn) = 0 kwa i = 1, 2, ..., k;Φ_i (x1, x2, ... ,xn)) 0 kwa i = k+1, k+ 2, ..., m.

Mfumo wa vikwazo lazima uletwe kwa fomu ya kisheria, i.e. kwa mfumo wa milinganyo ya mstari, ambapo idadi ya vigezo nambari zaidi milinganyo (m > k). Katika mfumo huu hakika kutakuwa na vigezo vinavyoweza kuonyeshwa kwa njia ya vigezo vingine, na ikiwa sivyo, basi vinaweza kuletwa kwa njia ya bandia. Katika kesi hii, wale wa kwanza huitwa msingi au msingi wa bandia, na za pili ni bure.

Ni rahisi zaidi kuzingatia njia rahisix mfano maalum. Acha kazi ya mstari f(x) = 6x1 + 5x2 + 9x3 na mfumo wa vikwazo upewe: 5x1 + 2x2 + 3x3 ≤ 25; x1 + 6x2 + 2x3 ≤ 20; 4x1 + 3x3 ≤ 18. Tunahitaji kupata thamani ya juu kazi f(x).

Suluhisho Katika hatua ya kwanza, taja ufumbuzi wa awali (rejea) wa mfumo wa equations kwa njia ya kiholela kabisa, ambayo inapaswa kukidhi mfumo uliopewa wa vikwazo. Katika kesi hiyo, kuanzishwa kwa bandia kunahitajika, i.e. vigezo vya msingi x4, x5 na x6 kama ifuatavyo: 5x1 + 2x2 + 3x3 + x4 = 25; x1 + 6x2 + 2x3 + x5 = 20; 4x1 + 3x3 + x6 = 18.

Kama unaweza kuona, kukosekana kwa usawa kumebadilishwa kuwa usawa shukrani kwa vigeu vilivyoongezwa x4, x5, x6, ambavyo ni idadi isiyo hasi. Kwa hivyo, umeleta mfumo kwa fomu yake ya kisheria. Tofauti x4 imejumuishwa katika equation ya kwanza na mgawo wa 1, na katika equation ya pili na mgawo wa 0, sawa ni sawa kwa vigezo x5, x6 na equations sambamba, ambayo inalingana na ufafanuzi wa msingi.

Umetayarisha mfumo na umepata ufumbuzi wa awali wa kumbukumbu - X0 = (0, 0, 0, 25, 20, 18). Sasa wasilisha coefficients ya vigezo na masharti ya bure ya equations (nambari zilizo upande wa kulia wa ishara "=") kwa namna ya jedwali ili kuboresha mahesabu zaidi (angalia takwimu).

Kiini cha njia rahisi ni kuleta jedwali hili kwa fomu ambayo nambari zote katika safu L zitakuwa maadili zisizo hasi. Ikiwa inageuka kuwa hii haiwezekani, basi mfumo hauna suluhisho mojawapo. Kuanza, chagua zaidi kipengele cha chini ya mstari huu, ni -9. Nambari iko kwenye safu ya tatu. Badilisha kigezo sambamba cha x3 kuwa kigezo cha msingi. Ili kufanya hivyo, gawanya mstari na 3 ili seli imalize na 1.

Sasa unahitaji seli na kurejea kwa 0. Ili kufanya hivyo, toa kutoka kwa nambari zinazofanana za mstari wa tatu na 3. Kutoka kwa vipengele vya mstari wa pili - vipengele vya tatu, kuzidishwa na 2. Na, hatimaye, kutoka vipengele vya safu ya L - kuzidishwa na (-9). Umepata suluhisho la pili la kumbukumbu: f(x) = L = 54 na x1 = (0, 0, 6, 7, 8, 0).