principal D' autres disciplines livres Matiquement programuvannya mathématique - Nakonechny S.І.

Matiquement programuvannya mathématique - Nakonechny S.І.

6.4. vіdtinannya Metodi. méthode Gomorі

Le tsіlochislovogo programuvannya très dur іdeyu Dantsіga base metodіv. Acceptable, tâche rozv'yazuvati neobhіdno scho lіnіynogo programuvannya, OOO Tous abo chastina zmіnnih yakoї labeur Buti tsіlochislovimi. Mozhlivo, la tâche Yakscho de sans esprit vrahovuyuchi tsіlochislovostі, vipadkovo odrazu bude otrimano potrіbny rozv'yazok. Cependant, une telle maloymovіrna de situatsіya. Perevazhno rozv'yazok pas zadovolnyatime tsіlochislovostі esprits. Todі nakladayut dodatkove obmezhennya, yak pas vikonuєtsya pour otrimanogo le plan zadachі contre zadovolnyaє si Yaky tsіlochislovy rozv'yazok. Tacke dodatkove obmezhennya nazivayut vіdtinannyam correctement. Système lіnіynih obmezhen zadachі dopovnyuєtsya esprits par une nouvelle tâche i otrimana rozv'yazuєtsya Dali lіnіynogo programuvannya. Yakscho її rozv'yazok znovu pas zadovolnyaє esprits tsіlochislovostі alors buduєtsya base lіnіyne obmezhennya scho vіdtinaє otrimany rozv'yazok pas zachіpayuchi tsіlochislovih planіv. Processus priєdnannya dodatkovih obmezhen povtoryuyut Doty, docks pas bude znaydeno tsіlochislovogo plan optimal apporté abo scho Yogo pas іsnuє.

Géométrique Présentation dodatkovogo lіnіynogo obmezhennya oznachaє Lieu de gіperploschini (pryamoї), scho vіdtinaє od bagatogrannika (bagatokutnika) rozv'yazkіv admissibles zadachі le Chastain Yogo, netsіlochislovimi mіstit points les coordonnées de yak, mais pas torkaєtsya zhodnoї tsіlochislovoї point de danoї mnozhini. Otrimany Novi bagatogrannik rozv'yazkіv mіstit OAO Tout tsіlі Point SSMSC boule dans Pochatkova, i rozv'yazok scho bude otrimano sur nomu, tsіlochislovim bude (Fig. 6.3).

règles de viznachennya scho vіdmіtiti Slіd realіzatsії іdeї Dantsіga stosovno formuvannya dodatkovogo obmezhennya viyavilos dosit pliant zavdannyam i Perche qui uspіshno loin realіzuvati qiu іdeyu, CCB Gomorі.

Rozglyanemo algorithme zaproponovany Gomorі pour rozv'yazuvannya povnіstyu tsіlochislovoї zadachі lіnіynogo programuvannya scho ґruntuєtsya sur la méthode simplex vikoristannі i peredbachaє zastosuvannya dosit un moyen facile de corriger vіdtinannya pobudovi.

Nekhay tâche maєmo tsіlochislovogo programuvannya:

(6.5)

des esprits:

. (6.6)

. (6,7)

- Tsіlі nombre . (6.8)

Acceptable, scho paramétrique - Tsіlі nombre.

Non vrahovuyuchi esprits tsіlochislovostі, znahodimo rozv'yazok zadachі (6.5) - (6.7) Méthode simplex. Nekhay rozv'yazok іsnuє i mіstitsya dans takіy simpleksnіy tablitsі:

tableau 6.1

Zmіnnі - Bazisnі et - Vіlnі. Plan Optimal zadachі: . yakscho - numéros Tsіlі, puis rozv'yazok otrimany JE tsіlochislovim zadachі plans optimaux (6,5) - (6,8). Іnakshe de Hoch b odne de numéros de napríklad, - Prise de vue. Otzhe, neobhіdno pobuduvati correctement obmezhennya vіdtinaє scho de valeurs Chastain .

Rozglyanemo dovіlny plan optimal zadachі (6,5) - (6,7). Virazimo dans tsomu planі le zmіnnu basale par zmіnnі vіlnі:

. (6.9)

Virazimo koefіtsієnti à zmіnnih danogo rіvnyannya dans viglyadі sumi їh tsіloї que drobovoї Chastain. Vvedemo poznachennya: - Numéro Tsіla chastina b, - Drobov chastina de b * 1. Otrimaєmo:

* 1: {Tsіloyu nombre Chastain et nazivaєtsya naybіlshe tsіle nombre Scho pas perevischuє bien. Chastain a tiré nombre Je , Yak dorіvnyuє rіznitsі mіzh propre numéro et que Yogo tsіloyu Chastain, tobto .

napríklad pour . ;

pour .

(6,10)

abo

. (6,11)

Otzhe, rіvnyannya (6.11) vikonuєtsya zadachі (6.5) pour savoir si yakogo plan acceptable - (6,7). Acceptable Teper régime scho rozglyanuty Plan zadachі optimal de Djé. Todі lіva chastina rіvnyannya numéros (6.11) de tsіlih s skladaєtsya privation i Je tsіlochislovim virazom. Otzhe, bon numéro tsіlim Yogo chastina takozh Je i spravdzhuєtsya rіvnіst:

(6,12)

de N - deyake nombre tsіle.

La valeur de N est pas Mauger Buti vіd'єmnoyu. yakscho b Puis s rіvnyannya (6.12) prihodimo à nerіvnostі:

.

Zvіdki . Tobto tse signifiait b, scho Drobov chastina perevischuє odinitsyu scho nemozhlivo. Dans Taqiy sposіb a scho entier N Je nevіd'єmnim.

Yakscho od lіvoї Chastain rіvnyannya (6.12) Numéro vіdnyati deyake nevіd'єmne, puis prihodimo à nerіvnostі:

(6,13)

yak vikonuєtsya pour l'admission si yakogo tsіlochislovogo zadachі régime (6,5) - (6,7). Dans viyavilosya scho de nerіvnіst de Taqiy (6.13) Je Shukanov vіdtinannyam correctement.

Otzhe pour les tâches rozv'yazuvannya de tsіlochislovih lіnіynogo programuvannya (6.1) - (6.4) par l'algorithme Gomorі zastosovuyut Taqiy:

1. Le problème de la méthode simplex rozv'yazuєtsya sans vimog tsіlochislovostі zmіnnih - (6.1) - (6.3).

Yakscho Sered régime elementіv umovno-optimal numéros de tir Absent, puis planifier Tsey Je rozv'yazkom zadachі tsіlochislovogo programuvannya (6.1) - (6.4).

problème Yakscho (6.1) - (6.3) n'a pas obtenu rozv'yazku (tsіlova funktsіya neobmezhena, obmezhen abo système nesumіsna), alors le problème (6.1) - (6.4) takozh pas rozv'yazku Got.

2. Coley en planі valeur Je drobovі de umovno-optimal, vibiraєtsya zmіnna, yack Got naybіlshu abattu Chastain. Sur bazі tsієї zmіnnoї (elementіv vіdpovіdnogo ligne ostannoї simpleksnoї tablitsі Où argent ne Won mіstitsya) buduєtsya dodatkove obmezhennya Gomorі:

.

3. Dodatkove obmezhennya pіslya Institution Yogo à kanonіchnogo viglyadu i Introduction aux éléments de base priєdnuєtsya ostannoї simpleksnoї tablitsі, yak mіstit régime umovno-optimal. La tâche Otrimanu de rozv'yazuyut i perevіryayut rozv'yazok її sur tsіlochislovіst. Yakscho tsіlochislovy pas vіn, la procédure povtoryuyut, povertayuchis à n. 2. Alors dіyut Doty, docks pas bude znaydeno tsіlochislovogo rozv'yazku apporté abo scho not Got défi sur la recevabilité rozv'yazkіv mnozhinі tsіlih numéros.

Dans lіteraturі [12, 27] a été apporté, scho pour les esprits Pevnyi algorithme Gomorі Je skіnchennim, les tâches des processus de bière de rozv'yazuvannya velikoї méthode rozmіrnostі Gomorі povіlno zbіzhny. Slіd takozh mère uvazі, scho i Quantité іteratsіy suttєvo dépôts od vіdtinannya préformé correctement. règle Hover (6.13) schodo formuvannya vіdtinannya droit de ne pas єdine. Іsnuyut efektivnіshі vіdtinannya, SSMSC vikoristovuyutsya ont un autre que troisième algorithmes Gomorі [12, 27], mais l'aspect pratique nayavny dosvіd fente se daє pas zmogi vidіliti s naykraschy eux.

Zagalom, Gomorі algorithme obchislyuvalnomu aspektі Je peu vivchenim. Yakscho dans lіnіynomu programuvannі sposterіgaєtsya vіdnosno zhorstka zalezhnіst mіzh kіlkіstyu obmezhen zadachі que kіlkіstyu neobhіdna scho іteratsіy pour її rozv'yazuvannya, puis tsіlochislovih tâches takoї zalezhnostі pas іsnuє. Quantité zmіnnih takozh peu vplivaє sur trudomіstkіst obchislen. De toute évidence, les processus rozv'yazannya tsіlochislovoї zadachі viznachaєtsya pas une privation її rozmіrnіstyu et takozh Surtout bagatogrannika recevabilité rozv'yazkіv scho lui yavlyaє nabіr іzolovanih tochok.

Yak généralement des tâches rozv'yazuvannya tsіlochislovogo programuvannya potrebuє grande obsyagu obchislen. Tom au stvorennі programme pour l'AMR Surtout uwagi slіd pridіlyati zasobam scho donner zmogu zmenshiti pomilki arrondi SSMSC mozhut prizvesti avant scho plan de tsіlochislovy otrimany bude pas optimale.

Rozglyanemo fesses rozv'yazuvannya tsіlochislovoї zadachі lіnіynogo programuvannya méthode Gomorі.

Sіlskogospodarske pіdpriєmstvo planuє vіdkriti département de séchage à virobnichіy ploschі 190 m2 mayuchi pour Tsogo 100 tis. UAH i mozhlivіst pridbati ustatkuvannya dvoh tipіv: A i B. Tehnіko-ekonomіchnu іnformatsіyu stosovno odinitsі esprit de la peau ustatkuvannya soumis à onglet. 6.2:

tableau 6.2

Rozv'yazannya. Nekhay x 1 x 2 i -kіlkіst komplektіv ustatkuvannya vіdpovіdno type A i B.

modèle Zapishemo ekonomіko-matiquement mathématique zadachі:

.

;

;

.

Je - Tsіlі nombre.

tâche Rozv'yazuєmo nehtuyuchi tsіlochislovostі esprits. Arrêtez simplex tableau Naboodah viglyadu:

tableau 6.3

Signification zmіnnoї Druha Je nombre abattu, scho pas zadovolnyaє pochatkovі zadachі esprits. Pobuduєmo pour une autre ligne navedenoї simpleksnoї tablitsі dodatkove obmezhennya esprit :

.

Oskіlki . . Puis dodatkove obmezhennya nabuvaє viglyadu:

.

Zvedemo Yogo à kanonіchnoї FORMES que vvedemo zmіnnu en boîte:

.

obmezhennya otrimane Priєdnavshi à simpleksnoї tablitsі H umovno-optimal plan dіstanemo (tableau 6.3.):

tableau 6.4

Rozv'yazavshi tâche d'orientation znahodimo tsіlochislovy plan optimal: . .