Miundo kamili ya upangaji ya mstari. Mbinu ya Gomori ya kutatua matatizo kamili ya programu. Mifano ya kutatua matatizo ya kiuchumi

Ndani ya maana ya sehemu muhimu ya kazi za kiuchumi zinazohusiana na kazi programu ya mstari, vipengele vya suluhisho lazima vielezwe kwa integers, i.e. kuwa integer. Hizi ni pamoja na, kwa mfano, shida ambazo vigezo vinamaanisha idadi ya vitengo vya bidhaa zisizogawanyika, idadi ya mashine wakati wa kupakia vifaa, idadi ya meli wakati wa kusambaza kwa mistari, idadi ya turbine kwenye mfumo wa nguvu, nambari. kompyuta katika tata ya usimamizi na mengine mengi.

Tatizo la mstari programu kamili imeundwa kama ifuatavyo: pata suluhisho kama hilo (mpango) mimi, ambayo kazi ya mstari

inachukua upeo au thamani ya chini chini ya vikwazo

(8.2)

(8.3)

- nambari nzima. (8.4)

Ikumbukwe kwamba classic tatizo la usafiri na kazi zingine za aina ya usafiri hutolewa "otomatiki". suluhisho la tatizo kwa nambari kamili (ikiwa, kwa kweli, vigezo vya hali ni kamili). Walakini, katika hali ya jumla, hali kamili (8.4) imeongezwa kwa kazi za kawaida programu ya mstari, inachanganya sana suluhisho lake.

Njia kadhaa hutumiwa kutatua shida za upangaji wa nambari kamili. Rahisi kati yao ni njia ya kawaida programu ya mstari. Ikiwa vipengee vya suluhisho mojawapo si kamili, vinazungushwa hadi nambari kamili iliyo karibu. Njia hii hutumiwa wakati kitengo kimoja cha idadi ya watu kinajumuisha sehemu ndogo ya kiasi cha watu wote. Vinginevyo, kuzungusha kunaweza kusababisha suluhisho kamili ambalo ni mbali na bora, kwa hivyo njia maalum zilizotengenezwa hutumiwa.

Mbinu kamili za uboreshaji zinaweza kugawanywa katika vikundi vitatu kuu: a) njia za kupogoa; b) mbinu za kuchanganya; c) mbinu takriban. Hebu tuchunguze kwa undani zaidi njia za kukata.

Mbinu za kupiga picha. Mbinu ya Gori

Kiini cha mbinu za kupogoa ni kwamba tatizo hutatuliwa kwanza bila hali ya integer™. Ikiwa mpango unaotokana ni kamili, tatizo linatatuliwa. Vinginevyo, kizuizi kipya kinaongezwa kwa vizuizi vya kazi na sifa zifuatazo:

lazima iwe mstari;
inapaswa kukata mpango uliopatikana usio kamili;
haipaswi kukata mpango wowote kamili.

Kikwazo cha ziada na mali hizi kinaitwa kukata sahihi.

Kuongeza kila kijiometri kizuizi cha mstari inalingana na kuchora mstari ulionyooka (hyperplane) ambao hukata sehemu yake kutoka kwa poligoni ya suluhisho (polyhedron) pamoja na sehemu inayofaa na viwianishi visivyo na nambari kamili, lakini haiathiri alama yoyote kamili ya polihedron hii. Kama matokeo, polyhedron mpya ya suluhisho ina alama zote kamili zilizomo

katika polyhedron ya awali ya ufumbuzi, na ipasavyo suluhisho mojawapo iliyopatikana na polyhedron hii itakuwa integer (Mchoro 8.1).

Mojawapo ya kanuni za kutatua tatizo la upangaji nambari kamili (8.1)-(8.4), iliyopendekezwa na R. Gomori, inategemea mbinu rahisi na hutumia njia rahisi kwa ajili ya kuunda njia sahihi ya kukatisha.

Acha shida ya upangaji ya mstari (8.1)-(8.3) iwe na kiwango bora cha mwisho, na katika hatua ya mwisho ya suluhisho lake. njia rahisix milinganyo ifuatayo hupatikana ikionyesha vigeu kuu kupitia anuwai zisizo kuu za suluhisho bora:

(8.5)

kwa hivyo suluhisho bora la shida (8.1)-(8.3) ni i, ambayo, kwa mfano, β; - sehemu isiyo kamili. Katika kesi hii, inaweza kuthibitishwa kuwa usawa unaoundwa na i- kwa equation ya mfumo (8.5), ina mali yote ya cutoff ya kawaida.

Ili kutatua tatizo la upangaji la mstari kamili (8.1)-(8.4) kwa kutumia mbinu ya Gori, algorithm ifuatayo inatumika.

1. Kwa kutumia njia rahisi, suluhisha tatizo (8.1)-(8.3) bila kuzingatia hali kamili. Ikiwa vipengee vyote vya mpango bora ni kamili, basi ni bora kwa shida kamili ya upangaji (8.1)-(8.4). Ikiwa tatizo la kwanza (8.1)-(8.3) haliwezi kutatuliwa (yaani, halina suluhu la mwisho au masharti yake yanapingana), basi tatizo la pili (8.1)-(8.4) nalo haliwezi kutatulika.
2. Ikiwa kati ya vipengele vya suluhisho mojawapo kuna zisizo kamili, basi chagua sehemu na kubwa zaidi. sehemu nzima na kwa mujibu wa equation sambamba ya mfumo (8.5) kuunda cutoff sahihi (8.6).
3. Kwa kuanzisha tofauti kamili isiyo hasi, badilisha usawa (8.6) kuwa mlingano sawa na uijumuishe katika mfumo wa vikwazo (8.2).
4. Tatua tatizo lililopanuliwa linalotokana kwa kutumia njia rahisi. Ikiwa mpango bora unaopatikana ni kamili, basi shida ya upangaji kamili (8.1) - (8.4) inatatuliwa. Vinginevyo, rudi kwenye hatua ya 2 ya algorithm.

Ikiwa shida inaweza kutatuliwa kwa nambari kamili, basi baada ya idadi kamili ya hatua (iterations) mpango kamili wa nambari utapatikana.

1 Katika ukosefu wa usawa (8.6) kuna ishara ( ), ikimaanisha sehemu ya sehemu ya nambari. Sehemu kamili ya nambari A ndio nambari kamili [katika] isiyozidi a, sehemu ya sehemu ya nambari- nambari (a), sawa na tofauti kati ya nambari hii na sehemu yake kamili, i.e. (a) = a-[b].

Kwa mfano, kwa (kumbuka, hasa -3, si -2) na

Ikiwa katika mchakato wa kutatua equation inaonekana (kuonyesha kutofautiana kuu kwa suala la zisizo za msingi) na neno la bure lisilo kamili na coefficients iliyobaki kamili, basi equation inayofanana haina ufumbuzi katika integers. Katika kesi hii na kazi hii haina suluhu kamili kamili.

8.1. Ili kununua vifaa vya kuchambua nafaka, mkulima hutenga pango 34. vitengo Vifaa vinapaswa kuwekwa kwenye eneo lisilozidi mita 60 za mraba. m. Mkulima anaweza kuagiza aina mbili za vifaa: mashine zisizo na nguvu kama A thamani ya 3 shimo. vitengo vinavyohitaji eneo la uzalishaji la 3 sq. m (pamoja na pasi), na tija kwa kila mabadiliko ya tani 2 za nafaka, na mashine zenye nguvu zaidi kama KATIKA thamani ya 4 den. vitengo vinavyochukua eneo la 5 sq. m, na tija kwa kila mabadiliko ya tani 3 za nafaka za ubora wa juu.

Inahitajika kuteka mpango bora wa ununuzi wa vifaa ambao unahakikisha kiwango cha juu utendaji wa jumla mradi mkulima anaweza kununua mashine zisizozidi 8 za aina hiyo KATIKA.

Suluhisho. Hebu tuonyeshe kwa idadi ya mashine, kwa mtiririko huo, aina A Na NDANI, kupitia Z - tija kwa ujumla. Kisha mfano wa hisabati wa tatizo utachukua fomu

(!!!8.8)

na vikwazo:

(8.2)

- nambari nzima. (8.4)

Wacha tulete tatizo kwenye mfumo wa kisheria kwa kuanzisha viambishi vya ziada visivyo hasi. Tunapata mfumo wa vikwazo:

(8.5)

Tunatatua tatizo kwa kutumia njia rahisi. Kwa uwazi, tunaonyesha suluhisho graphically (Mchoro 8.2).

Katika Mtini. 8.2 OKLM- eneo la suluhisho linalowezekana la shida (8.D)-(8.3"), lililopunguzwa na mistari iliyonyooka (1), (2), (3) na shoka za kuratibu; L(2/3; 8) - hatua ya mojawapo, lakini isiyo ya jumla ya ufumbuzi wa tatizo (8.1") - (8.3"); (4) - mstari wa moja kwa moja kukata ufumbuzi huu usio kamili; OKNM- eneo la suluhisho linalowezekana la shida iliyopanuliwa (8.1") - (8.3"), (8.6"); N( 2; 7) - hatua ya suluhisho kamili kamili.

Hatua ya I. Vigezo vya msingi Vigezo visivyo vya msingi

Suluhisho la kwanza la msingi ni kudhani

yangu. Thamani ya utendakazi ya mstari inayolingana

Tunabadilisha kuwa vigeu kuu vibadilishio ambavyo vimejumuishwa katika usemi wa kitendakazi cha mstari na mgawo chanya kikubwa zaidi. Tunapata thamani ya juu zaidi ya kutofautisha ambayo "inaruhusu"

kukubali mfumo wa vizuizi kulingana na hali ya uhusiano wa chini unaolingana:

hizo. mlinganyo wa kusuluhisha (ulioangaziwa) ni wa tatu. Katika X. 2 = 8 katika mlingano huu X- = 0, na kutofautisha huenda kwa isiyo ya msingi X 5.

Hatua ya II. Vigezo Muhimu X 2, X 3, X 4.

Vigezo vidogo.k, xy

Baada ya mabadiliko tunapata

Badilisha kuwa tofauti kuu na katika zisizo kuu x4.

III hatua. Vigezo kuu x, X 2, X 3.

Vigezo visivyo vya msingi x4, x5.

Baada ya mabadiliko tunapata

Suluhisho la msingi X., bora kwa tatizo (8.1")–(8.3") (), kwani katika usemi wa kitendakazi cha mstari

hakuna vigezo visivyo vya msingi vilivyo na coefficients chanya.

Walakini, suluhisho X 3 haikidhi hali kamili (8.4") Kwa kutumia mlingano wa kwanza wenye kigezo cha x kinachopokea thamani isiyo kamili katika suluhu mojawapo (2/3), tunaunda kikwazo cha ziada (8.6):

Tafadhali kumbuka kuwa, kulingana na (8.5) na (8.6), tunachukua sehemu ya sehemu mwanachama huru na ishara sawa, ambayo anayo katika mlingano, na sehemu za sehemu coefficients kwa vigezo vidogo x 4 na x- - kwa ishara tofauti.

Tangu sehemu za sehemu ,

, tunaandika usawa wa mwisho

(8.6")

Kwa kutambulisha kigezo kamili cha ziada x6 ≥ 0, tunapata mlinganyo sawa na ukosefu wa usawa (8.6")

(8.7")

Mlinganyo (8.7") lazima ujumuishwe katika mfumo wa vikwazo (8.5") wa tatizo la awali la kisheria, na kisha kurudia mchakato wa kutatua tatizo kwa kutumia njia rahisi kuhusiana na tatizo lililopanuliwa. Katika kesi hii, ili kupunguza idadi ya hatua (iterations), inashauriwa kuanzisha equation ya ziada (8.7") kwenye mfumo uliopatikana katika hatua ya mwisho ya kutatua tatizo (bila hali ya integer).

IV hatua. Vigezo Muhimu x v X 2, x3, χβ.

Vigezo visivyo vya msingi x4, x5.

Suluhisho la msingi haliruhusiwi

yangu. (Kumbuka kwamba baada ya kujumuisha mlinganyo wa ziada unaolingana na mkato sahihi katika mfumo wa vizuizi, suluhu ya msingi batili itapatikana kila wakati.)

Ili kupata suluhisho la msingi linalokubalika, ni muhimu kubadili katika kutofautiana kuu, ambayo ni pamoja na mgawo mzuri katika equation ambayo neno la bure ni hasi, i.e. x, au x. (katika hatua hii hatuzingatii kazi ya mstari). Tunatafsiri kwa msingi, kwa mfano, kutofautiana x5.

Hatua ya V. Vigezo kuu ni x, x2, x3, x5.

Vigezo visivyo vya msingi x4, x6.

Tunapata baada ya mabadiliko

Kwa kuwa hakuna vigezo kuu vilivyo na coefficients chanya katika usemi wa kazi ya mstari, basi X 5 ndio suluhisho bora.

Kwa hivyo, Zmax = 25 kwa bora suluhisho kamili X* = X 5 = (2; 7; 19; 0; 1; 0), i.e. utendaji wa juu Tani 25 za nafaka za hali ya juu kwa kila zamu zinaweza kupatikana kwa kununua mashine 2 za aina ya L na mashine 7 za aina. KATIKA Wakati huo huo, eneo lisilo na mtu wa majengo litakuwa mita za mraba 19. m, usawa wa fedha zilizotengwa ni sifuri, hifadhi ya ununuzi ni mashine 1 ya aina KATIKA(sehemu ya sita haina maana ya maana).

Maoni. Kwa tafsiri ya kijiometri kwenye Ng'ombe, ndege ya x2 (ona Mchoro 8.2) ya cutoff (8.6"), vigezo vilivyojumuishwa ndani yake ni muhimu. X 4 na X- eleza kupitia viambishi x na x2. Tunapata (angalia milinganyo ya 2 na ya 3 ya mfumo wa vikwazo (8.5"))

(tazama mstari wa kukata (4) kwenye Mchoro 8.2).
8.2. Zipo za kutosha idadi kubwa ya magogo ya urefu wa m 3. Magogo yanapaswa kukatwa katika aina mbili za workpieces: urefu wa 1.2 na 0.9 m, na angalau vipande 50 na 81 vya kila aina ya workpiece inapaswa kupatikana. kwa mtiririko huo. Kila logi inaweza kukatwa katika vipande vilivyoainishwa kwa njia kadhaa: 1) katika vipande 2 lakini 1.2 m; 2) kwa kipande 1 cha 1.2 m na vipande 2 vya 0.9 m kila; 3) kwa vipande 3 vya 0.9 m kila mmoja Tafuta idadi ya magogo yaliyokatwa kwa kila njia ili vipande vya aina yoyote vipatikane kutoka kwa idadi ndogo ya magogo.

Suluhisho. Wacha tuonyeshe kwa X() x2, x3 idadi ya magogo yaliyokatwa kwa kutumia njia 1, 2 na 3, mtawalia. Kutoka kwa hizi unaweza kupata nafasi 2xj +x2 za 1.2 m kila moja na 2x x +3x2 nafasi zilizoachwa wazi za mita 0.9 kila moja. Hebu tuonyeshe jumla ya idadi ya kumbukumbu Z. Kisha mfano wa hisabati wa tatizo utachukua fomu

na vikwazo:

Kwa kuanzisha vigezo vya ziada

tunapunguza mfumo wa kukosekana kwa usawa kwa mfumo sawa wa milinganyo:

(8.5")

Kutatua yaliyopokelewa tatizo la kisheria(bila hali kamili) kwa kutumia njia rahisi, katika hatua ya mwisho, ya tatu, ya suluhu tutapata misemo ifuatayo ya viambishi kuu na kazi ya mstari kulingana na vigeu visivyo vya msingi (tunapendekeza wanafunzi wazipate peke yao).

III hatua. Vigezo Muhimu x v X 2.

Vigezo visivyo vya msingi X katika X A , X 5.

yaani na suluhisho mojawapo

Ilibadilika kuwa sehemu mbili za suluhisho bora usikidhishe hali kamili (8.4"), na kijenzi kina sehemu kamili zaidi X 2. Kwa mujibu wa ∏. algoriti 2 za kutatua tatizo kamili la upangaji programu (tazama uk. 166) kwa kutumia mlinganyo wa pili ulio na kigezo hiki. X 2, tunaunda kizuizi cha ziada (8.6):

Wacha tupate sehemu za sehemu

na uandike usawa wa mwisho katika fomu

(8.6")

Kwa kuanzisha kigezo cha ziada tunapata

mlinganyo sawa na ukosefu wa usawa (8.6"):

(8.7")

Wacha tuonyeshe kutoka (8.7") kigezo cha ziada cha x6 na tuanzishe equation inayotokana na mfumo wa vizuizi tuliokuwa nao mwishowe, III, hatua ya kutatua shida (8.1") - (8.3") (bila hali kamili. )

IV hatua. Vigezo Muhimu X{, X katika X 6.

Vigezo visivyo vya msingi X 3, x4, X 5.

Kutatua tatizo hili lililopanuliwa kwa kutumia mbinu rahisi (tunawaalika wanafunzi wafanye wenyewe), tunapata zifuatazo.

Hatua ya V. Vigezo kuu x); X 2, x3.

Vigezo visivyo vya msingi x4, x5, xb.

yaani na suluhisho mojawapo

Suluhisho bora zaidi la shida iliyopanuliwa (8.1") - (8.3"), (8.6") tena haikidhi hali kamili (8.4"). Kulingana na mlinganyo wa kwanza na kigezo cha Xj kinachopokea thamani isiyo kamili katika mojawapo

suluhisho (), tunaacha kikomo cha pili cha ziada

kusoma (8.6):

ambayo tunaleta akilini

Kwa kutumia kigezo cha ziada

Tunapunguza usawa huu kwa usawa sawa, ambao tunajumuisha katika mfumo wa vikwazo vilivyopatikana wakati wa mwisho, V, hatua ya kutatua tatizo lililopanuliwa (8.G") - (8.3"), (8.6") kwa kutumia njia rahisix.

Hatua ya VI. Vigezo Muhimu x v X 2, X katika X T

Vigezo visivyo vya msingi X 4, X-, x 6.

Kuacha suluhisho zaidi la tatizo kwa kutumia mbinu rahisi (tunapendekeza kwamba wanafunzi wafanye hivyo wenyewe), katika hatua ya mwisho, VII, tunayopata.

Hatua ya VII. Vigezo Muhimu x v X t x3, X G

Vigezo visivyo vya msingi x v X 6, X T

Kwa kuwa hakuna vigezo visivyo vya msingi vilivyo na coefficients hasi katika usemi wa kazi ya mstari, basi X 7 – suluhisho kamili kamili kwa shida asili.

Ikumbukwe kwamba katika usemi unaotokana wa kazi ya mstari Z hakuna vigezo vidogo X D) na X 6. Hii ina maana kwamba, kwa ujumla, kuna seti isiyo na mwisho ya ufumbuzi bora (yoyote, si lazima integer), ambayo Z" = Zmjn = 46. Suluhisho hizi zinapatikana kwa thamani ya kutofautiana isiyo kuu. X 7 (imejumuishwa katika usemi wa Z), sawa na sifuri(yaani lini X 7 = 0), na saa yoyote maadili ya vigezo visivyo vya msingi x5 na X 6 (haijajumuishwa katika usemi wa Z), ambayo mfumo wa vizuizi "unaruhusu" kukubalika: 0<лг5 X 5 ≤ 1 na 0< x(i ≤ 1. Lakini kwa sababu ya hali kamili, anuwai X- Na X(> inaweza tu kuchukua maadili 0 au 1. Kwa hivyo shida itakuwa na masuluhisho manne kamili wakati X. na *6 katika mchanganyiko wowote kuchukua maadili 0 au 1, na X 7 = 0. Kuweka maadili haya katika mfumo wa vikwazo katika hatua ya VII, tunapata masuluhisho haya mojawapo:

Uwepo wa ufumbuzi mbadala wa nambari kamili hufanya iwezekanavyo kuchagua mmoja wao, akiongozwa na vigezo vya ziada ambavyo hazizingatiwi katika mfano wa hisabati wa tatizo. Kwa mfano, kutokana na hali ya tatizo hili inafuata kwamba magogo ya kuona haitoi taka tu kwa kutumia njia ya 3, kwa hiyo, wakati wa kuchagua mojawapo ya ufumbuzi wa nne bora, ni kawaida kutoa upendeleo kwa ufumbuzi. X^ 3 ambapo idadi ya juu ya kumbukumbu ( X 2 = 41) hukatwa bila taka.

Kwa hivyo, Zmin=46 kwa masuluhisho kamili kamili (5; 41; 0), (6; 39; 1), (7; 36; 3), (6; 38; 2). Wakati wa kurekodi ufumbuzi bora, tuliacha vipengele vitatu vya kwanza tu, tukielezea idadi ya magogo yaliyokatwa kulingana na njia ya 1, ya 2 na ya 3, kwa mtiririko huo, na kuwatenga vipengele vinne vya mwisho, ambavyo havina maana ya semantic.

Ubaya wa njia ya Gomori ni hitaji la maadili kamili kwa anuwai zote - zote za msingi (zinazoelezea, kwa mfano, katika shida ya kutumia rasilimali ya kitengo cha uzalishaji) na ziada (kuonyesha kiasi cha rasilimali ambazo hazijatumika, ambazo zinaweza kuwa sehemu).

Unaweza kuona kwamba suluhisho la tatizo ni fupi zaidi.

Kiini cha njia za kupogoa ni kwamba shida hutatuliwa kwanza bila hali kamili. Ikiwa mpango unaotokana ni kamili, tatizo linatatuliwa. Vinginevyo, kizuizi kipya kinaongezwa kwa vizuizi vya kazi na sifa zifuatazo:

Inapaswa kuwa ya mstari;

Inapaswa kukata mpango uliopatikana usio kamili;

Haipaswi kupunguza mpango wowote kamili.

Kikwazo cha ziada ambacho kina mali hizi kinaitwa cutoff sahihi.

Kijiometri, nyongeza ya kila kizuizi cha mstari inalingana na kuchora mstari ulionyooka (hyperplane) ambao hukata sehemu yake kutoka kwa poligoni ya suluhisho (polyhedron) pamoja na sehemu bora na viwianishi visivyo kamili, lakini haiathiri nambari yoyote. pointi za polyhedron hii. Matokeo yake, polyhedron mpya ya ufumbuzi ina pointi zote za integer zilizomo katika polyhedron ya awali ya ufumbuzi na, ipasavyo, suluhisho mojawapo iliyopatikana na polyhedron hii itakuwa integer (Mchoro 8.1).

kubofya viambajengo kuu *1, *2, vigeu vipya Xm+1, Xm+2, ..., Xm+1, suluhu

Xt kupitia neo-x"optimal

(8.5)

sehemu isiyo kamili. Katika kesi hii inaweza kuthibitishwa kuwa ukosefu wa usawa

(P, ) - (a," m+\)xm+1 ■ -~(at )Xn ^ 0, (* )

iliyoundwa na /th equation ya mfumo (8.5), ina mali yote ya cutoff ya kawaida.

Ili kusuluhisha shida kamili ya upangaji wa mstari (8.1)-(8.4) kwa kutumia njia ya Gori, algorithm ifuatayo inatumika:

1. Kwa kutumia njia rahisi, suluhisha tatizo (8.1)-(8.3) bila kuzingatia hali kamili. Ikiwa vipengee vyote vya mpango bora ni kamili, basi ni bora kwa shida kamili ya upangaji (8.1)-(8.4). Ikiwa shida ya kwanza (8.1) -

(8.3) haiwezi kusuluhishwa (yaani, haina ukadiriaji wa mwisho au masharti yake yanapingana), basi tatizo la pili (8.1)-(8.4) pia haliwezi kusuluhishwa.

2. Ikiwa kati ya vipengele vya suluhisho mojawapo kuna zisizo kamili, kisha chagua sehemu na sehemu kubwa zaidi ya integer na, kwa kutumia equation inayofanana ya mfumo (8.5), tengeneza kukata sahihi (8.6).

3. Kwa kuanzisha kigezo cha ziada cha nambari kamili kisicho hasi, badilisha usawa (8.6) kuwa mlingano sawa.

(P() - |a/ t+1 )*t+1- ■-(a|"l )xn + xn+1 > (®*^)

na kuijumuisha katika mfumo wa vikwazo (8.2).

4. Tatua tatizo lililopanuliwa linalotokana kwa kutumia njia rahisi. Ikiwa mpango bora uliopatikana ni kamili,

basi tatizo la programu kamili (8.1)-(8.4) linatatuliwa. Vinginevyo, rudi kwenye hatua ya 2 ya algorithm.

Ikiwa shida inaweza kutatuliwa kwa nambari kamili, basi baada ya idadi kamili ya hatua (iterations) mpango kamili wa nambari utapatikana.

^8.1. Ili kununua vifaa vya kuchambua nafaka, mkulima hutenga pango 34. vitengo Vifaa vinapaswa kuwekwa kwenye eneo lisilozidi mita 60 za mraba. m. Mkulima anaweza kuagiza aina mbili za vifaa: mashine zisizo na nguvu za aina A zinazogharimu pango 3. vitengo vinavyohitaji eneo la uzalishaji la 3 sq. m (pamoja na pasi) na kutoa tija ya tani 2 za nafaka kwa zamu, na mashine zenye nguvu zaidi za aina B zinazogharimu pango 4. vitengo vinavyochukua eneo la 5 sq. m na kutoa tija ya tani 3 za nafaka za hali ya juu kwa kila zamu.

Inahitajika kuandaa mpango mzuri wa ununuzi wa vifaa ambavyo vinahakikisha tija ya jumla, mradi mkulima hawezi kununua zaidi ya mashine 8 za aina B.

Suluhisho. Wacha tuonyeshe kwa x\, x2 idadi ya mashine za aina A na B, mtawaliwa, na kwa Z jumla ya tija. Kisha mfano wa hisabati wa tatizo utachukua fomu:

Katika Mtini. 8.2 OKM - eneo la suluhisho zinazowezekana kwa shida (8.1") - (8.3"), iliyopunguzwa na mistari iliyonyooka (1), (2), (3) na shoka za kuratibu; /> (2/3; 8) - hatua ya suluhisho mojawapo, lakini isiyo kamili kwa tatizo (8.1") - (8.3"); (4) - mstari wa moja kwa moja kukata ufumbuzi huu usio kamili; 0№М - eneo la suluhisho linalowezekana la shida iliyopanuliwa (8.1') - (8.3'), (8.61); M2; 7) - hatua ya suluhisho kamili ya nambari.

Hatua ya I. Vigezo kuu x3, x4, *5; vigezo visivyo vya msingi X\, X2.

x3	= 60 -	Zh! -5x2,
x4	= 34 -	Zx) - 4x2,
x5	= 8	- *2>
	Z = 2x)	+ Zx2.

Suluhisho la kwanza la msingi X\ = (0; 0; 60; 34; 8) linakubalika. Thamani ya utendaji kazi wa mstari = 0.

Tunatafsiri katika vigezo kuu vya kutofautiana kwa XI, ambayo imejumuishwa katika usemi wa kazi ya mstari na mgawo mkubwa zaidi wa chanya. Tunapata dhamana ya juu inayowezekana ya kutofautisha xi, ambayo mfumo wa vizuizi "unaruhusu" kukubalika, kutoka kwa hali ya chini ya uhusiano unaolingana:

Хг = 1ШП|т;т;Т| = 8,

hizo. mlinganyo wa kusuluhisha (ulioangaziwa) ni wa tatu. Wakati *2 = 8 katika equation hii X5 = 0, na variable X5 inakuwa isiyo ya msingi.

Hatua ya II. Vigezo kuu x2, x3, x*; vigezo visivyo vya msingi Xx X5.

{

(8.6)

Kwa kutambulisha kigezo kamili cha ziada x6 > O, tunapata mlingano sawa na ukosefu wa usawa (8.6")

~1*5 + Xb = °" ^8"7 ^

IV hatua. Vigezo vya msingi X), *2, xs> *b‘> vigeu visivyo vya msingi *1, *2-

X1 = z - 3*4 +

x3 = 18 + x4 +___ x5,

x6 - + ^x4 + z"x5-

Suluhisho la msingi X4 = (y; 8; 18; 0; 0; -y) halikubaliki. (Kumbuka kwamba baada ya kujumuisha mlinganyo wa ziada unaolingana na mkato sahihi katika mfumo wa vizuizi, suluhu ya msingi batili itapatikana kila wakati.)

Ili kupata suluhisho la msingi linalokubalika, ni muhimu kubadili katika kutofautiana kuu, ambayo ni pamoja na mgawo mzuri katika equation ambayo neno la bure ni hasi, i.e. *1 au x$ (katika hatua hii hatuzingatii kazi ya mstari). Tunatafsiri kwa msingi, kwa mfano, kutofautiana kwa X5.

Hatua ya V. Vigezo kuu X\, X2, X3, X5; vigezo visivyo vya msingi R], X £

Baada ya mabadiliko tunapata:

LG| = 2 - x4 + 2x6,

*2 = 7 + 2х* ~ 2Х("

x3 = 19 + -x4 + -x6,

*5 = 1 - 2х* + 2Х6’

2 = 25-|x4--|x6.

^5 =(2; 7; 19; 0; 1;0);^ = 25.

Kwa kuwa hakuna vigezo kuu vilivyo na coefficients chanya katika usemi wa kazi ya mstari, X5 ni suluhisho mojawapo.

Kwa hivyo, 2max = 25 kwa suluhisho kamili la nambari X* - X$ =(2; 7; 19; 0; 1; 0), i.e. tija ya juu ya tani 25 za nafaka ya hali ya juu kwa kila zamu inaweza kupatikana kwa kununua mashine 2 za aina A na mashine 7 za aina B\ wakati eneo lisilokaliwa la majengo litakuwa 19 sq. m, usawa wa fedha zilizotengwa ni sawa na 0, katika hifadhi ya ununuzi kuna mashine 1 ya aina B (sehemu ya sita haina maana ya maana).

Maoni. Kwa tafsiri ya kijiometri kwenye ndege ya Ox \ Xr (ona Mchoro 8.2) ya cutoff (8.6"), ni muhimu kueleza vigezo x4 na x $ vilivyojumuishwa ndani yake kupitia vigezo XI na x2. Tunapata (tazama Milinganyo ya 2 na ya 3 ya mfumo wa vikwazo (8.5")):

y - y (34 - 3x, - 4x2) - y (8 - x2) £ 0 au x, + 2x2 £ 16.

(angalia mstari wa kukata (4) kwenye Mchoro 8.2)>

^8.2. Kuna idadi kubwa ya magogo yenye urefu wa m 3. Magogo yanapaswa kukatwa katika aina mbili za tupu: urefu wa 1.2 m na urefu wa 0.9 m, na angalau vipande 50 vya kila aina vinapaswa kupatikana. na pcs 81. kwa mtiririko huo. Kila logi inaweza kukatwa kwenye nafasi zilizoachwa wazi kwa njia kadhaa: 1) katika nafasi 2 za mita 1.2 kila moja; 2) kwa kipande 1 cha 1.2 m kila na vipande 2 vya 0.9 m kila; 3) kwa vipande 3 vya mita 0.9 kila moja. Tafuta idadi ya magogo,

sawn kwa kila njia, ili aina yoyote ya workpiece inaweza kupatikana kutoka kwa idadi ndogo ya magogo.

Suluhisho. Wacha tuonyeshe kwa х\, хі, хм, idadi ya magogo yaliyokatwa ipasavyo na njia 1, 2 na 3. Kutoka kwao unaweza kupata 2хі + *2 nafasi zilizo wazi za 1.2 m kila moja na 2l\ + 3x2 tupu za 0.9 m kila Hebu tunaashiria jumla ya idadi ya kumbukumbu kama I. Kisha mfano wa hisabati wa tatizo utachukua fomu:

I 2x, + x2 - x4 = 50,+ (?у), wapi [y] - sehemu nzima na (y) = U ~ [y] ~ sehemu.

[h] Tunapata suluhisho la msingi linalokubalika, tukizingatia mstari mpya ruhusa, i.e. I = P + 1.

a) Ikiwa coefficients zote uc> 0, basi shida haina suluhu (yaani, shida kamili imetatuliwa).
b) Vinginevyo, pata index Kwa vile vile

(kigezo cha kuingia msingi mpya) Kumbuka kwamba uchaguzi wa kipengele cha kutatua katikaNa* haibadilishi ishara ya vigezo Aj.

[4] Ikiwa ndani meza mpya kuna angalau moja x 3 s na kurudia taratibu hizi mara nyingi iwezekanavyo.

[~5~| Ikiwa suluhisho bora linalotokana ni kamili, basi shida hutatuliwa. Vinginevyo, unahitaji kurudi kwa uhakika.

Mfano 4.6.1. Tatua tatizo kamili kwa kutumia mbinu ya Gori

Suluhisho. Baada ya kuongeza viambatisho vya usaidizi, tunayo shida ifuatayo ya upangaji wa laini katika fomu ya kawaida:

na matrices

Jedwali 1


	X4

Kwa= T

Kwa kutumia njia ya mzunguko, jaza majedwali yafuatayo. Kipengele cha azimio - 6 *.

meza 2		X 2



	„ _ 1 NAZ ~_3_

k" = 2 T

Kipengele cha azimio - 1/2*.

X ndani^0). Kwa hivyo, programu (xi = 11/3, X 2 = 5) itatoa upeo wa kazi ya kiuchumi z, sawa na 1370/3 = 45b|, t.s. z= z max = 456§. "

Tangu hii programu mojawapo si nambari kamili, tunatumia algoriti ya Gomori ili kupata programu kamili kabisa. Kama kamba kwa msingi ambao tunaunda mstari wa ziada Kutoka kwa sehemu za sehemu za vipengele vyote, chagua mstari wa pili (index 7' = 1). Wacha tujaze jedwali 3", na kuongeza kwenye jedwali la 3 safu ya ziada (4.14) na sehemu za sehemu kwa tofauti ya ziada Ж5 na safu ya ziada.

k" = 4 T

Baada ya kuongeza mstari mpya, jedwali la simplex 3" haliwiani tena na suluhu la msingi linalokubalika kwa tatizo linaloeleza. Tunapata suluhisho la msingi linalokubalika, tukizingatia mstari mpya kuwa wa kusuluhisha, yaani /" = 5.

Tunapata safu ya kutatua, i.e. index Kwa" vile vile

(kigezo cha kuingia msingi mpya). Kipengele cha azimio - (-2/3*). Kumbuka kwamba uchaguzi huo wa kipengele cha kutatua haubadili ishara ya vigezo Aj.

Wacha tujaze jedwali la simplex 4.

Jedwali 4		X2

	X2

Maadili ya vigezo vyote ^ 0, ( X ndani^0). Kwa hivyo, mpango (xi = 3, x 2 = 6, x±= 1) inatoa upeo wa kazi ya kiuchumi r sawa na 450, t.s. z = zma^= 450. Programu hii mojawapo ni nambari kamili. ?

Mfano 4.6.2. Tatua tatizo kamili kwa kutumia mbinu ya Gori

Suluhisho. Kuna shida ya upangaji wa mstari na matrices

Wacha tujaze jedwali la simplex na programu ya awali.

Jedwali 1

Kwa= T

Kwa kutumia njia ya mzunguko, jaza majedwali yafuatayo. Kipengele cha azimio - 1 *.

meza 2				X2

Kipengele cha kuruhusu - 5 *.

Jedwali 3

Maadili ya vigezo vyote ^ 0, ( X ndani^0). Kwa hiyo, programu (xi = 12/5, 24 = 1/5, 25 = 28/5) inatoa kiwango cha chini cha kazi ya kiuchumi r sawa na -11/5 = -2.2, i.e. z =

~min = -2.2.

Kwa kuwa programu hii bora sio nambari kamili, tunatumia algoriti ya Gomori kupata programu kamili kabisa. Kama kamba kwa msingi ambao tunaunda kamba ya ziada kutoka kwa sehemu za sehemu za vitu vya ss, tunachagua, kwa mfano, safu ya tatu (index r = 5) na sehemu ya juu ya sehemu. Wacha tujaze jedwali la 3" kwa kuongeza laini ya ziada (4.14) kwenye jedwali la 3 na sehemu ndogo za safu ya tatu kwa utofauti wa ziada. xq (mstari huu hukuruhusu kukata sehemu za eneo la programu zilizo na alama na viwianishi visivyo vya nambari) na safu ya ziada. Tunapata

Jedwali 3"





		G - -NA

k" = 3 T

Baada ya kuongeza mstari mpya, jedwali la simplex 3 " halifanani tena na suluhisho la msingi linalokubalika kwa tatizo ambalo linaelezea. Tunapata suluhisho la msingi linalokubalika, kwa kuzingatia mstari mpya unaotatuliwa, i.e. Mimi" = 6.

Tunapata safu ya kutatua, i.e. index Kwa" vile vile

(kigezo cha kuingia msingi mpya). Kipengele cha azimio - (-3/5*). Kumbuka kwamba uchaguzi huo wa kipengele cha kutatua haubadili ishara ya vigezo Aj.

Wacha tujaze jedwali la simplex 4.

Jedwali 4

Maadili ya vigezo vyote ^ 0, ( X ndani^0). Kwa hivyo programu (x = 2, X2 = 0, xs = 1, X 4 = 0, f 5 = 5) itatoa kiwango cha chini cha kazi ya kiuchumi z 9 sawa na (-2), t.s. z =-min = - 2. Programu hii mojawapo ni nambari kamili. ?

Tatizo 4.6.1. Tatua tatizo kamili kwa kutumia mbinu ya Gori