Zavladala je tišina koju je prekinuo sam Švejk uzdahnuvši:
- ... Mora postojati disciplina u vojnoj službi - bez nje niko ni prstom ne bi mrdnuo za stvar. Naš glavni poručnik Makovets je uvek govorio: „Disciplina, idioti, neophodna je. Bez discipline, penjali biste se na drveće kao majmuni. Vojna služba će od vas napraviti ljude, bezumne budale!” Pa, zar nije tako? Zamislite trg, recimo, na Karlovom trgu, a na svakom drvetu sjedi po jedan vojnik bez ikakve discipline. Ovo me užasno plaši.
Jaroslav HASHEK AVANTURE DOBROGA VOJNIKA ŠVEJKA

Raspored časova je kombinacija u prostoru i vremenu discipline (predmet), nastavnika (nastavnika), publike i grupe (podgrupa, struja) učenika.

Formulacija problema

Biću kratak.

• Prilikom izvođenja nastave bilo koji učesnik može biti odsutan, na primjer, na sjednici odjeljenja, studenti po pravilu ne dolaze ili su studenti otišli na vojni odjel (imaju svoj raspored), a za tu vrstu nastave razred nema discipline, nastavnika i publike.
• Po pravilu, kontinuitet (bez prozora) je neophodan uslov za učenike i po mogućnosti za nastavnike.
• Raspored se može sastaviti za semestar/polusemestar po sedmici, po dvije sedmice i brojilac/imenilac (neparna sedmica/parna sedmica). Postoji i mjesečni raspored.
• Klase bi trebalo da se mogu postaviti u ručnom režimu (drugim rečima, u uređivaču). Na primjer, akademsko vijeće ili par velikih šefova, ili čak zanimanje samo dobre osobe.
• Mora postojati sistem zabrana za sve učesnike časa. Na primjer, sada skoro svi nastavnici zarađuju sa strane (inače nećete moći preživjeti) ili je fond učionica podijeljen između fakulteta i nastava se ne može održavati u dijelu učionica nakon ručka.
• Prisustvo sofisticiranih želja nastavnika, jednom daje 5 časova dnevno da oslobodi ostale dane, a drugom ne daju više od dva časa dnevno, premore se, a ako je predavanje onda jedan čas i svakako 2. ili 3. klase.
• Za nastavu u različitim zgradama potrebno je više vremena za prelaz od vremena pauze između časova. Uslov za minimiziranje pokreta je takođe prirodan.

Zaključak. Kako se vidi iz izjave, kvalitet rasporeda je moguće ocijeniti tek nakon što je u potpunosti sastavljen. Stoga, korištenje genetskih algoritama može omogućiti konstruiranje rješenja za željeni problem, pa čak i dobivanje, u određenom smislu, jednog od dobrih. Istovremeno, genetski algoritmi vrlo brzo konvergiraju do optimalnog na početku, što znači da praktično neće biti ograničenja u količini ulaznih podataka.

Slika je preuzeta odavde.

Genetski algoritam

Čisto retorički, ponoviću glavne faze genetskog algoritma:

1. Postavite ciljnu funkciju (fitness) za pojedince u populaciji
2. Napravite početnu populaciju
3. (Početak ciklusa)
   1. Razmnožavanje (ukrštanje)
   2. Mutacija
   3. Izračunajte vrijednost funkcije cilja za sve pojedince
   4. Formiranje nove generacije (selekcija)
   5. Ako su ispunjeni uslovi zaustavljanja, onda je kraj petlje, inače (početak petlje).

Najčešća greška u korištenju genetskih algoritama je u odabiru gena. Često su odabrani geni jednostavno samo rješenje. Izbor gena je najnetrivijalniji i najkreativniji element prilikom kreiranja genetskog algoritma. Lično smatram da izbor gena treba da zadovolji sljedeća dva osnovna zahtjeva.

1. Na osnovu skupa gena, rješenje željenog problema treba konstruirati brzo i nedvosmisleno.
2. Kada se ukrste, potomci moraju naslijediti karakteristike roditelja.

Komentar. Skup gena bi trebao pružiti cijeli skup (moguće optimalnih) rješenja problema. U principu, nije potrebno zahtijevati jedan na jedan, dovoljno je da je mapiranje gena na prostor rješenja on(surekcija).

Algoritam planiranja

Opisaću samo same gene, algoritam za konstruisanje rešenja na osnovu njih, ukrštanje i mutaciju.

Kako iskusni dispečer pravi raspored. Riječ iskusan znači da je dispečer već jednom sastavio raspored i poznaje njegova uska grla. Na primjer, nedostatak velike streaming publike ili računarskih časova. Prvi kurs, pošto imaju dosta striming predavanja i istovremeno nastavu u podgrupama na časovima računara, engleski/engleski od nule/nemački/francuski itd., a nadležni zahtevaju da prvi kurs ni u kom slučaju nema prozore i nema više od dva predavanja dnevno i dani su bili ravnomjerno opterećeni. Dakle, iskusan dispečer organizuje prve „uže razrede“, časove nadležnih na njihov zahtev i časove posebno dosadnih nastavnika. Zatim, koristeći dogovorene časove kao kostur, brzo završava raspored. Pokušajmo, na neki način, imitirati ovaj proces.

Neki od časova su već na našem rasporedu, ostali će biti numerisani redom. Niz brojeva zanimanja ćemo smatrati genomom, iako je u principu ovdje važan samo redoslijed zanimanja. Da bismo napravili raspored, mi ćemo uzastopno izdvojiti brojeve razreda i staviti odabrani razred u raspored, zadovoljavajući potrebne zahtjeve i maksimizirajući funkciju cilja za učenike, nastavnike i publiku (takođe imaju kriterije za zapošljavanje).
Ako se neophodni zahtjevi ne mogu ispuniti, onda se pojedinac s takvim genomom može odbaciti kao neodrživ. Ako nije moguće kreirati raspored, tada možete zamijeniti potrebne zahtjeve kaznom u funkciji cilja.

Prelazak se može organizirati na više načina. Na primjer jedan od njih. Hajde da imamo sledeće gene

3 1 2 5 6 4 7
2 3 5 7 1 4 6

Ovdje možete vidjeti da se aktivnost 3 javlja u oba gena do uključujući poziciju 2, a na primjer, od pozicije 2 do pozicije 5 postoji interval za 1 aktivnost. Napravimo sljedeći znak

_ * * * * _ _ za 1 lekciju
* * * _ _ _ _ za lekciju 2
* * _ _ _ _ _ za lekciju 3
_ _ _ _ _ * _ za lekciju 4
_ _ * * _ _ _ za lekciju 5
_ _ _ _ * * * za lekciju 6
_ _ _ * * * * za lekciju 7

ovdje zvjezdice označavaju moguće pozicije za brojeve zanimanja potomka. Možete birati između jednog ili više mogućih rješenja kao dijete ili djeca ovih roditelja. Za odabir gena potomka uvijek postoji rješenje, na primjer, oba roditelja ga zadovoljavaju. Prepišimo tabelu kroz skupove mogućih pozicija

1 pozicija (2, 3)
2. pozicija (1, 2, 3)
3. pozicija (1, 2, 5)
4. pozicija (1, 5, 7)
5 pozicija (1, 6, 7)
6. pozicija (4, 6, 7)
7 pozicija (6, 7)

Za konstruiranje rješenja možete koristiti sljedeći algoritam. Prvo ćemo staviti one brojeve klasa koje su manje uobičajene. Ako ih sortiramo uzlaznim redoslijedom, imat ćemo
1 put 4
2 puta 3.5
3 puta 2, 6
4 puta 1, 7
Stoga, prvo lekciju 4 stavljamo na 6. poziciju, zatim 3 ili 5 na pozicije (1, 2) odnosno (3, 4). Na svakom koraku možete baciti kutiju šibica. Kao rezultat, možete dobiti, na primjer, sljedeće korake za algoritam ukrštanja

* * * * * 4 *
3 * * * * 4 *
3 * * 5 * 4 *
3 * * 5 * 4 6
3 * 2 5 * 4 6
3 * 2 5 7 4 6
3 1 2 5 7 4 6

Budući da je moguće da se ne konstruiše ispravan niz, bolje je organizovati algoritam u obliku jednostavne rekurzije da bi se algoritam mogao ponoviti, tj. organizovanje neke pretrage.

Mutacija se može jednostavno organizirati nasumičnim preuređivanjem brojeva zanimanja.

Zaključak

Ovo je, u neku ruku, nastavak mojih postova Program za zakazivanje nastave na fakultetu i Proračun opterećenja za odsjek.

Ponovo predlažem sljedeće rješenje (skica).

• GUI na PyQt ili PySide
• PosgreSQL DBMS (ovdje imam oko 80% spreman), osim samog rasporeda, sadrži i aplikacije i opterećenja nastavnika, nastavne planove i programe i još mnogo toga (u tu svrhu ću objaviti jednu ili više tema)
• web sučelje na CherryPy+Cheetah (ali o tome se može raspravljati)
• izvoz bilo kakvih izveštaja (rasporeda, kartica sa zadacima za obuku, itd.) u OpenDocument formatu (GOST R ISO/IEC 26300-2010. Gosstandart Rusije (06.01.2011.)) preko ODFPY
• algoritmi za zakazivanje od mene (ova tema je o tome)
• proizvodnja od mene
• za zainteresovane, rad na zajedničkom jezgru
• za zainteresovane adaptacija na vlastiti fakultet i mogucnost da sve fleksibilno mijenjaju zivot ide dalje, a funkcioneri ne spavaju

Hvala svima koji su se odazvali, nakon diskusije na ovu temu biće moguće da se organizujemo.

Rasporedom časova reguliše se ritam školskog života, rada i odmora učenika i nastavnika.
Efikasnost cjelokupnog obrazovnog procesa u velikoj mjeri zavisi od njegovog kvaliteta.

Podobnost nastave i školski raspored

Školski obrazovni režim mora odgovarati funkcionalnim mogućnostima učenika. Obim, sadržaj i organizacija obrazovnog procesa moraju osigurati takvo stanje organizma u kojem bi umor potpuno nestao tokom odmora.

Glavni kriterijumi za ocjenjivanje nastave u smislu funkcionalnih sposobnosti učenika su težina i zamornost. Umor karakteriše promena u izvođenju, a težinu predmeta karakteriše nivo izvođenja, odnosno stepen savladanosti nastavnog materijala. Stoga, oba faktora treba podjednako uzeti u obzir prilikom planiranja.

U pravnom aspektu, problem sastavljanja školskog rasporeda ogleda se u novim higijenskim zahtjevima za sastavljanje rasporeda, koji su zasnovani na podacima savremenih naučnih istraživanja o bioritmologiji mentalnog rada i tabeli težine predmeta I.G. Sivkova. Međutim, za zamjenika direktora škole, koji sastavlja raspored, važno je ne samo da zna koliko je predmet težak, već i da zamisli snagu zamornog efekta nastave iz određenog predmeta na zdravlje učenika. . Nažalost, tabela težine I.G. Sivkova ne uzima u obzir takvu komponentu obuke kao što je zamornost predmeta, koja prvenstveno utiče na zdravlje učenika.

Savremena istraživanja pružaju uvid u odnos između zamornosti predmeta i težine, iako kod nekih predmeta ovi pokazatelji značajno variraju. Ovi prikazi omogućavaju kombinovanje dva indikatora u jedan – prihvatljivost stavke. Stoga, tabela I.G. Sivkova, moguće je predložiti alternativu – skalu prihvatljivosti predmeta, koja bi uzela u obzir komponente težine i zamornosti učenja, kao i karakteristike svake obrazovne ustanove i nastavnog plana i programa svakog razreda.

Skala prihvatljivosti se sastoji od kolone „Stavke po rangu“, u koju se upisuju stavke čiji su rangovi dobijeni na osnovu rezultata dijagnostikovanja stepena njihove težine i zamornosti metodom stručnih procena – njihov algoritam je prikazan u Prilogu 1. predložena skala je konstantna po svojoj strukturi, ali promjenjiva po sadržaju (vidi tabelu 1).

Tabela 1

Približna skala prihvatljivosti stavke

Kao što se vidi iz tabele 1, skala se sastoji od pet grupa težine. Svaka grupa ima rezultat - to je konstantna komponenta skale i nije podložna promjenama. Sadržaj (tj. skup stavki) svake grupe može se promijeniti ovisno o rezultatima dijagnostike. Predstavlja varijabilni dio skale.

U srednjoj školi br. 618 u Sankt Peterburgu dobili smo sljedeću skalu prihvatljivosti predmeta (vidi tabelu 2).

tabela 2

Skala prihvatljivosti predmeta

Algoritam planiranja

Pošto će svaka obrazovna ustanova imati svoju prihvatljivost predmeta, čitaoci ne bi trebali kopirati datu skalu jedan na jedan. Preporučljivo je dijagnosticirati stepen težine i zamornosti predmeta u vašoj školi metodom stručnih procjena.

Osim toga, pri sastavljanju rasporeda ima smisla voditi se tabelom u kojoj se rangiraju nivoi uspješnosti učenika u različitim razredima na različitim časovima tokom školske sedmice (vidi Dodatak 2).

Napravili smo algoritam za kreiranje fiziološki zasnovanog rasporeda koji uzima u obzir realne higijenske zahtjeve. Ovaj algoritam se može koristiti za kreiranje obrazovnog rasporeda kako u školi s velikim brojem odjeljenja drugog i trećeg razreda, tako iu relativno maloj obrazovnoj ustanovi. Algoritam je namijenjen stručnjacima koji kreiraju raspored bez korištenja kompjuterskog programa.

Kada koristite automatizirane programe, preporučljivo je rasporediti objekte pomoću automatiziranog programa u fazama na osnovu predloženog algoritma. Kao što pokazuje praksa, ovi se programi mogu koristiti samo kao pomoćni alat za:

• početno uređenje objekata nakon čega slijedi ručna dorada;
• čuvanje informacija i njihovo štampanje.

Nakon automatizirane distribucije objekata (program, u pravilu, raspoređuje od 40 do 70%), gotovo je nemoguće uzeti u obzir higijenske zahtjeve za raspored časova, jer je potrebno ne samo isporučiti preostale neuređene predmete , ali i značajno promijeniti (do 60%) automatizirani raspored objekata po principu „samo da to uredim“.

Stoga, kada koristite kompjuterski program za kreiranje racionalnog rasporeda, uzimajući u obzir realno izvodljive higijensko-pedagoške zahtjeve, te specifičnosti obrazovne ustanove, potrebno je nastavne predmete rasporediti po fazama koristeći gore predloženi algoritam. U ovom slučaju, svaka faza uređenja grupe objekata mora se završiti ručnom završnom obradom, fokusirajući se na gore navedene zahtjeve. To će vam omogućiti da napravite racionalniji raspored i, ako je moguće, uzmete u obzir sve potrebne uslove.

Procedura za promjenu rasporeda

Algoritam za prilagođavanje školskog rasporeda

Ako trebate promijeniti raspored u toku školske godine, što se dešava prilično često, morate poraditi na rasporedu stola. Da biste promijenili raspored na njemu, potrebno je izvršiti sljedeće proračune i preuređenja.

Predloženi način kreiranja rasporeda ne traje više vremena nego inače, ali vam omogućava da pravilno kreirate raspored, tj.:

• napravite sopstvenu skalu prihvatljivosti predmeta (teškoće i zamornosti) kako biste kreirali racionalniji školski raspored;
• držati dovoljno veliku količinu potrebnih informacija u vidnom polju zamjenika direktora škole;
• ravnomjerno rasporedite nastavu za svaki dan (izbjegavajte preveliki broj sedmih lekcija);
• svi časovi počinju od prvog časa, što omogućava učenje u istom ritmu, jer će učenici svaki dan počinjati nastavni dan u isto vreme;
• regulišu stepen težine školskog dana u zavisnosti od dinamike sedmičnih performansi učenika;
• organizirajte nastavu gotovo bez „prozora“ ili sa minimalnim brojem, što vam omogućava da održite ritam rada nastavnika i stvorite povoljno radno okruženje;
• racionalno izmjenjuju objekte različitih smjerova;
• racionalno organizovati potrebne duple lekcije;
• brzo mijenjati i prilagođavati raspored prema potrebama proizvodnje.

Osim toga, ova metoda ne zahtijeva značajnu količinu praznih papira (dodatne tabele, posebno ako škola ima mnogo odjeljenja drugog i trećeg razreda (30 ili više).

Da bi se pripremio kvalitetan raspored koji bi odgovarao mogućnostima određene obrazovne ustanove, potrebno je provesti vlastitu dijagnozu stepena težine i zamornosti predmeta u svakoj paraleli. Studenti bi trebali biti stručnjaci u ovom slučaju, jer niko ne može bolje od njih reći koji je predmet težak i zamoran.

Kriterijumi za higijensko ocjenjivanje školskog rasporeda

1. Broj odjeljenja osnovne škole je ______.

2. Broj odjeljenja u osnovnim i srednjim školama je ___________.

3. Ukupno korištenih učionica za nastavu – ___________.

4. Dostupnost skale prihvatljivosti za vašu obrazovnu ustanovu:

5. Uzimajući u obzir skalu prihvatljivosti predmeta u školskom programu:

6. Raspodjela časova po danu za učenike:

7. Svi razredi počinju svoje učenje sa prvim časom:

8. Racionalno izmjenjivanje predmeta različitih smjerova i složenosti:

9. Usklađenost sa učinkom učenika u rasporedu (sedmična dinamika):

10. Racionalno organizovanje nastave za nastavnike:

11. Maksimalan broj časova po nastavniku dnevno:

a) do 4 časa – za____ nastavnike – ______ (%);

b) 5 i 6 časova - ____ nastavnika - _____ (%);

c) 7 časova ili više - ___ nastavnika - ___ (%).

12. Dostupan metodički dan (navesti broj nastavnika):

a) sa opterećenjem do 24 sata sedmično – za____ nastavnike;

b) sa opterećenjem od 25 do 30 sati sedmično – za ___ nastavnika;

c) sa opterećenjem većim od 30 sati sedmično – za___ nastavnike.

1. Pripremite komplete sa nazivima predmeta od 5. do 11. razreda.
2. Dajte učenicima set kartica s nazivima predmeta i listove za odgovore.
3. Ponudite da odaberete kartice s nazivima onih predmeta koji se izučavaju u ovom razredu (pomoću dnevnika).
4. Pojasnite koncept „teškoće“ objekata.
5. Ponudite da samostalno odredite težinu svakog predmeta rangiranjem, tj. polaganje karata u opadajućem redoslijedu težine predmeta (položite karte odozgo prema dolje, tj. na prvom mjestu je karta sa najtežom temom, ispod je manje teška, itd.).
6. Dobijeni raspored stavki zapišite na listu za odgovore.
7. Nakon toga analizirajte i razjasnite pojam „zamornosti“ objekata.
8. Izvedite sličnu proceduru rangiranja i zapišite rezultirajuće poravnanje na listu za odgovore.
9. Prikupite i obradite listove za odgovore (pogledajte formular sa sažetkom tabele ispod).

– gdje je: mk – prosječna ocjena iz predmeta jednog razreda;

n – broj časova u paraleli koja se izučava;

ili po formuli:

– gdje je: Mk – zbir bodova iz predmeta jednog razreda;

n – broj studenata iste paralele koji učestvuju u studiji.

Na primjer, u paraleli 7. razreda ima pet odjeljenja, 130 ljudi je učestvovalo u dijagnostici. Zbir bodova na ruskom jeziku u paraleli bio je 469. Zamjenjujemo brojeve u formulu:

sri b. pr = (469/130) = 3,61 – prosječna ocjena iz ruskog jezika u 7. razredu bila je 3,61, djeca doživljavaju ovaj predmet kao prilično težak.

Na isti način se posebno izračunava prosječna ocjena svakog subjekta u pogledu umora.

Zatim se utvrđuje prosječna ocjena prihvatanja za svaki predmet. Da bi se to uradilo, dva indikatora se sabiraju: prosječna ocjena težine i prosječna ocjena zamornosti, a zatim se rezultat podijeli sa 2. Ovo daje prosječnu ocjenu prihvatljivosti subjekta.

Na osnovu dobijenih podataka za svaku paralelu sastavlja se individualna tabela podobnosti subjekata određene obrazovne ustanove.

Obrazac zaokretne tabele za obradu odgovora

Dodatak 2

Rangiranje sati učenja tokom sedmice
zavisno od nivoa uspješnosti učenika u različitim razredima

1 – najpovoljniji sati; 10 – najnepovoljnije.

6–7 – smanjen nivo izvođenja (nepovoljni sati za izvođenje nastave).

8–10 – nizak nivo izvođenja (nepovoljni sati za izvođenje nastave).

Tablica sedmične raspodjele radnog opterećenja nastavnika

Dodatak 3

Tehnologija za izvođenje izgleda tabele rasporeda časova

Da biste završili raspored potrebno je pripremiti:

• 4 lista kartona (debljina 1–2 mm, visina – 42 cm, širina – 22 cm; visina reda – 0,8 cm, širina kolone – 1 cm)*;
• 4 lista papira u boji (po mogućnosti svijetle boje) gustoće 200 g/cm i dimenzija sličnih kartonskim listovima;
• široka prozirna traka;
• lederin (papirni vinil) za lijepljenje kartona u fasciklu (trake širine 4-5 cm; dužine 49-50 cm);
• PVA ljepilo (prilično jako, poput "silakra").

Algoritam izvođenja rasporeda

1. Zalijepite listove kartona u "školjku na preklop":

2. Postavite sve potrebne informacije za izradu rasporeda na jedan list papira u boji (stavite na list kartona br. 1); primjer: tabela na str. 27.

3. Na sljedeća dva lista papira u boji nacrtajte mrežu, po tri dana na svakom listu, po 7 ćelija za svaki dan (stavite na 2. i 3. list kartona).

4. Na 4. listu nacrtajte kontinuiranu mrežu bez podjele na dane (ćelije su slične veličine).

5. Gotove obložene listove prekrijte selotejpom tako da ne bude podera prilikom rezanja ćelija.

6. Napravite proreze u ćelijama veličine od 0,5-0,6 cm.

7. Zalijepite papirne listove duž stranica kartonskih listova na gotovu „školjku na preklop“. Raspored je spreman.

8. Posebno napraviti raznobojne oznake sa slovom razreda (5. “A”, 7. “G” itd.), kolicina prema opterećenju 5- ili 6-dnevne sedmice + dodatno za nastavu gdje su razredi podijeljeni u podgrupe. Veličina oznake: širina – 8 mm; visina – 15 mm.

9. Pripremite oznake bilo koje boje bez natpisa razreda da biste izračunali sedmično opterećenje za svakog nastavnika. Dimenzije: širina 5 mm; visina 12–14 mm.

Ovaj raspored je zgodan za korištenje, jer su sve potrebne informacije uvijek pred očima zamjenika direktora. Može se sklopiti u fasciklu, što olakšava nošenje. U ovom slučaju, oznake će se držati u slotovima.

Informacije potrebne za kreiranje rasporeda

___________ * Dimenzije kartonskog lista su individualne, jer... Svaka škola ima različit broj nastavnika, različito radno vrijeme (5- i 6-dnevna školska sedmica). Predlažemo veličine rasporeda na osnovu 6-dnevne školske sedmice i škole sa 50-55 nastavnika.

Većina ovoga što čitate su gluposti. Ipak, na nekim mjestima, po mom mišljenju, ima zdravorazumskih razmišljanja, nažalost, nema toliko takvih mjesta. L Nemojte ni pomišljati da uzmete ovo tamo gdje se ozbiljno proučavaju problemi teorije rasporeda. Za svakoga ko želi da napiše nešto bolje od ovoga, toplo preporučujem čitanje Huove knjige. T. “Cjelobrojno programiranje i tokovi u mrežama”, osim toga, vjerovatno vrijedi pročitati i predavanja VMiK-a o teoriji optimizacije N.M. Novikova (ne sjećam se gdje je na internetu). Sada aktivno radim na problemima teorije optimizacije, tako da svako ko je takođe zainteresovan za ovu temu uvijek rado razgovara. Pisati [email protected].

Uvod. 8

1. Opis tehnološke oblasti. 10

1.1. Formulacija problema rasporeda. 10

1.1.1. Opća formulacija problema rasporeda. 10

1.1.2. Formulisanje zadatka izrade rasporeda u skladu sa rasporedom treninga. jedanaest

1.2. Analiza postojećeg softvera... 12

1.3. Formulacija problema. 15

2. Izrada matematičkog modela i praktična implementacija sistema automatskog rasporeda. 16

2.1. Matematički model rasporeda na univerzitetu. 16

2.1.1. Notacija. 16

2.1.2. Varijable. 18

2.1.3. Ograničenja. 19

2.1.4. Ciljna funkcija. 21

2.2. Metode rješavanja problema. 22

2.2.1. Potpuno cijeli algoritam. 23

2.2.2 Algoritam direktnog cjelobrojnog programiranja. 28

2.2.3. Tehnika dobijanja početne prihvatljive osnove. 32

2.3. Karakteristike praktične implementacije sistema.. 36

2.3.1. Izbor modela. 36

2.3.2. Opis ulaznih informacija. 39

2.3.3. Razvoj informacione podrške za zadatak. 41

2.3.4. Osobine formiranja ograničenja u matematičkom modelu problema raspoređivanja. 44

2.4. Rezultati programa.. 45

2.5. Analiza dobijenih rezultata. 49

Zaključci... 50

Književnost. 51

Dodatak 1. Mogućnosti softverskih proizvoda za sisteme raspoređivanja. 52

Dodatak 2. Popis softverskog modula metoda za rješavanje problema automatskog raspoređivanja. 61

Uvod

Kvalitet obuke specijalista na univerzitetima, a posebno efikasnost korišćenja naučnog i pedagoškog potencijala, u određenoj meri zavisi od nivoa organizacije obrazovnog procesa.

Jedna od glavnih komponenti ovog procesa - raspored časova - reguliše radni ritam i utiče na kreativni učinak nastavnika, pa se može smatrati faktorom u optimizaciji korišćenja ograničenih radnih resursa - nastavnog osoblja. Tehnologiju izrade rasporeda treba shvatiti ne samo kao radno intenzivan tehnički proces, objekt mehanizacije i automatizacije pomoću računara, već i kao akciju optimalnog upravljanja. Dakle, ovo je problem razvoja optimalnog rasporeda časova na univerzitetima sa očiglednim ekonomskim koristima. Budući da su interesovanja učesnika u obrazovnom procesu raznolika, zadatak izrade rasporeda je višekriterijumski.

Zadatak izrade rasporeda ne treba posmatrati samo kao neku vrstu programa koji ostvaruje funkciju mehaničke distribucije časova na početku semestra, na kojem se završava njegova (programska) upotreba. Ekonomski efekat od efikasnijeg korišćenja resursa rada može se postići samo kao rezultat mukotrpnog rada na upravljanju ovim radnim resursima. Raspored je ovdje samo alat za takvo upravljanje, a za njegovu potpunu upotrebu potrebno je da program kombinuje ne samo sredstva za kreiranje optimalnog rasporeda, već i sredstva za održavanje njegove optimalnosti u slučaju promjene nekih ulaznih podataka, koji su se u trenutku sastavljanja rasporeda smatrali stalnim . Osim toga, optimalno upravljanje tako složenim sistemom je nemoguće bez akumulacije statističkih informacija o procesima koji se odvijaju u sistemu. Stoga je i sam zadatak kreiranja optimalnog rasporeda samo dio složenog sistema upravljanja obrazovnim procesom.

Višekriterijumska priroda ovog problema i složenost objekta za koji se gradi matematički model zahtijeva ozbiljno matematičko proučavanje objekta kako bi se povećala funkcionalnost algoritama za raspoređivanje bez značajnog kompliciranja modela i, kao posljedica, povećanja količine iskorištene memorije i vremena potrebnog za rješavanje problema.

1. OPIS TEHNOLOŠKE OBLASTI 1.1. Formulacija problema rasporeda

Problem teorije rasporeda u svojoj opštoj formulaciji smatra se veoma atraktivnim, iako je postizanje čak i malog napretka ka rešenju obično povezano sa ogromnim poteškoćama. Uprkos činjenici da su se problemima teorije rasporeda bavili mnogi visokokvalifikovani stručnjaci, do sada niko nije uspeo da dobije značajnije rezultate. Neuspješni pokušaji dobivanja ovakvih rezultata po pravilu se ne objavljuju, a to je dijelom i zbog činjenice da problem i dalje privlači pažnju mnogih istraživača zbog svoje prividne jednostavnosti formulacije.

1.1.1. Opća formulacija problema rasporeda

U svojoj najopštijoj formulaciji, zadatak planiranja je sljedeći. Uz pomoć određenog skupa resursa ili uslužnih uređaja, mora se izvršiti određeni fiksni sistem zadataka. Cilj je pronaći efikasan algoritam za naručivanje zadataka koji optimiziraju ili imaju tendenciju da optimizuju potrebnu meru efikasnosti, s obzirom na svojstva zadataka i resursa i ograničenja koja su im nametnuta. Glavne mjere efikasnosti su dužina rasporeda i prosječno vrijeme boravka poslova u sistemu. Modeli ovih problema su deterministički u smislu da su sve informacije na osnovu kojih se donose odluke o naručivanju unaprijed poznate.

1.1.2. Formulisanje zadatka izrade rasporeda u skladu sa rasporedom treninga.

Opća teorija raspoređivanja pretpostavlja da svi opslužujući uređaji (ili procesori) ne mogu obavljati više od jednog zadatka u datom trenutku, što nije dovoljno za zakazivanje nastavne nastave ako se učionica uzima kao procesor prilikom distribucije zadataka. Tako se u nekim slučajevima nastava sa više grupa istovremeno može održavati u jednoj učionici, na primjer, opća predavanja za nekoliko tokova.

Dakle, pri prenošenju opšte teorije rasporeda na raspored treninga, napravljene su sledeće pretpostavke:

Svi procesori (tj. u slučaju obrazovnog rasporeda - učionica) imaju kapacitet - određeni broj C ≥ 1. Kapacitet procesora određuje broj zadataka koje može istovremeno "obraditi" u datom trenutku (sa s obzirom na nejedinstvo procesora, bilo bi zanimljivo razmotriti opciju, kada procesor nije publika, već nastavnik, a zadatak je tok iz jedne ili više obrazovnih grupa sa kojima radi);

Skup zadataka za distribuciju uključuje treninge nastavnika sa studijskim grupama;

Vremenski model u sistemu je diskretan; pretpostavlja se da se cjelokupna distribucija periodično ponavlja u određenom vremenskom intervalu;

Svi zadaci se izvršavaju u isto vrijeme, što se uzima kao jedinica diskretizacije vremenskog intervala;

Zadaci pripadaju objektima, a to su grupe za učenje i nastavnici.

Kao rezultat toga, formulacija problema zakazivanja treninga je sljedeća: „Za dati skup učionica (u ovom slučaju učionica znači širok spektar prostorija u kojima se održavaju sesije obuke (od kompjuterske do teretana)) i zadati skup vremenskih intervala (tj., u suštini, lekcije ili trenažni parovi) za konstruiranje takve distribucije treninga za sve objekte (nastavnike i grupe za obuku) za koje je odabrani kriterij optimalnosti najbolji."

1.2. Analiza postojećeg softvera

U ovom trenutku, sektor softverskog tržišta za sisteme za raspoređivanje klasa predstavlja veliki broj različitih softverskih proizvoda. Tabela 1 prikazuje samo neke od meni poznatih.

Iz objektivnih razloga, sistem rasporeda na univerzitetu (što znači veliki državni univerzitet) mora nužno implementirati niz osnovnih funkcija:

Uzimajući u obzir želje nastavnika;

Osiguravanje potrebne publike;

Određivanje željene publike;

Računovodstvo prijelaza između zgrada;

Kombiniranje grupa u tokove za bilo koji skup disciplina;

Podjela na podgrupe;

Nakon sastavljanja rasporeda, ako je potrebno, zamijenite nastavnike ili promijenite vrijeme održavanja časa.

Osim toga, postoje i specifični zahtjevi za svaki univerzitet za funkcionalnost softverskog proizvoda.

Mogućnosti, po mom mišljenju, najpopularnijih softverskih proizvoda na ruskom tržištu su date u Dodatku 1.

Iz gornje liste, možda samo program „Metodičar” manje-više odgovara potrebnoj funkcionalnosti softverskog proizvoda za zakazivanje na fakultetu. Ovakvo stanje stvari lako se objašnjava činjenicom da je školsko obrazovanje danas „standardizovanije“ (u smislu organizacije obrazovnog procesa) od univerzitetskog obrazovanja. Ova standardizacija dovodi do velikog potencijalnog tržišta za prodaju softvera i povrata razvoja prodajom velikog broja kopija proizvoda po relativno niskoj cijeni.

U slučaju univerziteta, potražnja za sistemima rasporeda je možda čak i veća nego za škole, ali stvar komplikuje velika specifičnost organizacije obrazovnog procesa na svakom pojedinačnom univerzitetu. Nije moguće stvoriti objedinjeni softver, a cijena stvaranja specijaliziranog proizvoda od programera trećih strana ispada nerazumno visoka. Uz to, preduslov je i postojanje „uređenog“ rasporeda, koji pretpostavlja mogućnost zamjene nastavnika ili promjenu termina nastave. Za sada, nijedan softverski proizvod vam ne dozvoljava da to učinite sasvim jednostavno (iako Methodist ima neke mogućnosti).

1.3. Formulacija problema.

Svrha ovog rada bila je kreiranje matematičkog modela univerzitetskog rasporeda koji bi omogućio da se efikasno (u zadatom vremenskom okviru i sa zadatim stepenom optimalnosti) riješi problem automatskog rasporeda i koji bi imao fleksibilnost (manje promjene u slučaj promena u ulaznim informacijama) za prilagođavanje sistema u okviru konkretnog praktičnog problema. Da bismo donekle pojednostavili zadatak, u početnoj fazi projektovanja napravljene su neke pretpostavke:

Raspored je baziran na ne više od dva para dnevno (što je sasvim prikladno za večernju nastavu);

Svi parovi se drže u jednoj zgradi;

Problem se postavlja u smislu linearnog programiranja;

Ne vrši se daljnja dekompozicija modela;

Svi koeficijenti modela i željene varijable su cijeli brojevi;

Postavljeni problem mora se riješiti jednom od univerzalnih (neovisno o cjelobrojnim vrijednostima koeficijenata) metoda cjelobrojnog linearnog programiranja.

2. Izrada matematičkog modela i praktična implementacija automatskog sistema raspoređivanja 2.1. Matematički model univerzitetskog rasporeda

Izgradimo matematički model univerzitetskog rasporeda u terminima linearnog programiranja. Hajde da uvedemo notaciju i definišemo varijable i ograničenja.

2.1.1. Oznake

Univerzitet ima N studijskih grupa, kombinovanih u R tokove; r – broj toka, r = 1, ..., R, k r – broj studijske grupe u toku r, k r = 1, ..., G r.

Podjela na grupe u niti se vrši na osnovu principa:

1. Korišćenje dve grupe istog učioničkog fonda za njihova predavanja automatski podrazumeva njihovo smeštanje u 1 tok (pretpostavlja se da se sva predavanja studijskih grupa održavaju zajedno).

2. Grupa (ili njen dio), kao jedinica obrazovnog procesa na univerzitetu, može biti uključena u različite tokove, ali samo jednom u svaki od njih.

3. Broj niti nije ograničen.

Nastava se održava radnim danima u intervalima od sat i po, koje ćemo zvati parovi.

Označimo:

t – broj radnog dana u sedmici, t Ê T kr, gdje

T kr – skup brojeva radnih dana za grupu k r;

j – broj para, j = 1 ,…, J;

J – ukupan broj parova.

Sa svakom nastavnom grupom k r tok r tokom sedmice, prema nastavnom planu i programu, izvodi se W kr nastava, od kojih S r predavanja i Q kr praktična. Označimo:

s r – broj discipline na listi nastavnih časova za tok r, s r = 1 ,…,S r ;

q kr – broj discipline u listi praktične nastave za grupu k r, q kr = 1,…, Q kr.

Pretpostavlja se da se predavanja održavaju za sve grupe toka istovremeno iu istoj učionici. Zatim, ako se tokom sedmice predaje više od jedne lekcije u disciplini, ova disciplina se spominje u spisku predavanja ili praktične nastave onoliko puta koliko je predviđeno nastavnim planom i programom za svaki smjer ili grupu.

UČITELJI

Neka je p broj (ime) nastavnika, p = 1,…, P. Uvedemo Booleove vrijednosti i :

Nastavno opterećenje nastavnika planira se prije sastavljanja rasporeda časova, zbog čega se u ovoj fazi vrijednosti mogu smatrati datim. Za svakog nastavnika p, p = 1 ,…,P, naznačeno je i njegovo opterećenje u učionici - N p sati sedmično.

REVIZORNI FOND

Nastava u svakom toku može se održavati samo u određenim učionicama (na primjer, praktična nastava informatike može se održavati samo u izložbenim časovima). neka bude:

(A 1 r ) – skup publike za predavanja na streamu r;

(A 2 r) – komplet učionica za praktičnu obuku na toku r;

A 1 r – broj elemenata skupa (A 1 r);

A 2 r – broj elemenata skupa (A 2 r);

A 1 r + A 2 r – broj publike unije skupova (A 1 r )∩(A 2 r ).

Fond publike se utvrđuje prije početka zakazivanja, tako da se setovi mogu smatrati datim.

2.1.2. Varijable

Zadatak zakazivanja je da se za svako predavanje (na streamu) i praktičnu lekciju (u grupi) odredi dan u sedmici i par na ovaj dan, uzimajući u obzir ispunjenje dolje konstruiranih ograničenja i minimiziranje određene ciljne funkcije.

Hajde da uvedemo sljedeće potrebne Booleove varijable:

=

U slučaju rasporeda za grupe večernjih časova J=2. Za generalizaciju modela na sve oblike učenja, pogledajte stranicu 669.

2.1.3. Ograničenja

Za svaku grupu k r sve vrste rada u učionici moraju se obaviti tokom sedmice:

Svako predavanje s r i praktična lekcija q kr, respektivno, za sve tokove r i sve grupe k r mogu se održati najviše jednom svakog dana t:

Ako varijable povezuju sve vrste aktivnosti sa vremenom njihove implementacije, onda su proizvodi i povežite vrijeme sa imenom nastavnika.

Svakog dana t i u svakom paru j, nastavnik p može predavati najviše jednu lekciju iz jedne discipline u jednom toku ili u jednoj grupi:

Konačno, svakog dana u svakoj nastavi, broj predavanja i praktične nastave ne bi trebao biti veći od fonda učionice koji je dostupan na univerzitetu:

Pored toga, za sve skupove skupova koji se seku (A 1 r) i (A 2 r) moraju biti ispunjeni sledeći uslovi:

Prikazani odnosi iscrpljuju bezuslovna ograničenja koja se uvijek uzimaju u obzir pri izradi rasporeda. Međutim, mogu postojati specifični uslovi, prije svega, obavljanje određenih vrsta poslova u „gornjoj“ ili „donjoj“ sedmici (tj. jedan akademski sat sedmično). Drugi posebni uslovi se ne mogu isključiti, ali za pojednostavljenje modela oni nisu uzeti u obzir.

2.1.4. Objektivna funkcija

Kako bi u potpunosti obavljao naučni, nastavni i metodički rad i pripremao se za nastavu, univerzitetski nastavnik mora imati slobodno vrijeme. Ovaj uslov nije dovoljan, ali neophodan. Očigledno, slobodno vrijeme bi trebao imati ne u „pokrcanom“ načinu rada, kao što su, na primjer, „prozori“ između časova sa učenicima, već, ako je moguće, potpuno slobodnim radnim danima. Ovo je ekvivalentno maksimiziranju radnog opterećenja nastavnika u danima kada ga imaju (vidi (5)). Međutim, u isto vrijeme nastavnici imaju nejednaka prava na slobodno vrijeme, jer imaju različite kreativne potencijale. Stoga je potrebno uvesti ponderske koeficijente po kojima bi se vodio računa o odgovarajućem statusu nastavnika – njegov akademski stepen i zvanje, radno mjesto, naučna i društvena aktivnost itd. U nekim slučajevima, na osnovu stručnih procjena, moguće je koristiti individualne težinske koeficijente koji uzimaju u obzir druge faktore.

Dakle, biraćemo kriterijum za kvalitet zakazivanja nastave u vidu maksimiziranja ponderisanog broja dana slobodnih od rada u učionici za sve nastavnike, što je, s obzirom na fiksnu dužinu radne nedelje, ekvivalentno maksimalnoj ukupnoj zbijenosti nastave. opterećenje učionice.

Razmotrimo izraz za vrijednost opterećenja učionice na dan t nastavnika p:

gdje je M proizvoljan pozitivan dovoljno veliki broj; - željenu Booleovu varijablu.

Iz (10) slijedi da ako je , tada je = 1, a ako je , onda je = 0.

Uzimajući u obzir gore navedeno suštinsko značenje kriterija optimizacije u dodatnim ograničenjima (10), kao i uvođenje težinskih koeficijenata statusa nastavnika, dobijamo traženi kriterij optimalnosti:

Uvedena funkcija cilja nije jedina moguća. Uvođenje drugih funkcija cilja ne mijenja ograničenja matematičkog modela i metoda za rješavanje problema, ali može značajno uticati na rezultate proračuna.

2.2. METODE ZA RJEŠAVANJE PROBLEMA

Problem maksimiziranja linearne ciljne funkcije postavljen u prethodnom pasusu pod datim sistemom ograničenja je problem linearnog cjelobrojnog Bulovog programiranja, budući da su svi koeficijenti ograničenja cijeli brojevi zbog diskretne prirode početnih podataka problema; Osim toga, tražene varijable matematičkog modela mogu imati samo dvije vrijednosti. U ovom trenutku postoji nekoliko mogućih metoda za rješavanje ove vrste problema.

B – opisane su metode redoslednog indeksiranja i modifikovane oznake, zasnovane na Lagranževoj dekompoziciji originalnog modela na više jednolinijskih zadataka rešenih, odnosno metodama redosleda indeksiranja ili modifikovanih oznaka. Nažalost, broj operacija svake metode ne dozvoljava polinomsku procjenu; Osim toga, dimenzija tabele skupova (međuvrijednosti) metoda naglo raste sa povećanjem dimenzije problema koji se rješava, što je u našem slučaju neprihvatljivo. Možda će promjena algoritma dekompozicije za određeni matematički model smanjiti veličinu tablica, ali takav algoritam još ne postoji.

S tim u vezi, odabrane su metode rješenja opisane u modifikaciji simpleks metode za slučaj cjelobrojnog problema linearnog programiranja. U opštem slučaju, broj operacija simpleks metode ne dozvoljava polinomsku procenu (čak je prikazana klasa problema za koju je broj operacija O(e n)), ali za slučaj našeg problema, prosječan broj operacija omogućava polinomsku procjenu: O(n 3 m 1/( n-1)) (n – broj varijabli; m – broj ograničenja).

2.2.1. ALGORITAM POTPUNOG CJELOVOG CIJELA

Ovaj algoritam se naziva potpuno cijelim jer ako se originalna tablica sastoji od cjelobrojnih elemenata, onda sve tablice koje rezultiraju iz algoritma sadrže samo cjelobrojne elemente. Kao i dual simplex metoda, algoritam počinje od dvostruko prihvatljive tablice. Ako su a i 0 (i = 1 ,..., n+m; a i 0 koeficijenti ciljne funkcije) nenegativni cijeli brojevi, tada je problem riješen. Ako je za neki niz a i 0

Neka je zadan cjelobrojni problem linearnog programiranja:

maksimizirati

pod uslovima

Uslovi (12) se mogu zapisati kao

Pretpostavimo da su za t=0 (tj. za originalnu tabelu) svi a ij cijeli brojevi, a stupci (j = 1,...,n) su leksikografski pozitivni. Tada svi stupci ostaju leksikografski pozitivni tokom izračunavanja.

Prije predstavljanja metode za dobivanje dodatnog ograničenja iz generiranog niza, uvodimo novi prikaz brojeva. Neka [x] označava najveći cijeli broj koji nije veći od x. Za bilo koji broj y (pozitivan ili negativan) i pozitivan možemo napisati:

gdje je (r y nenegativan ostatak kada se y dijeli sa ). posebno, . Dakle, ako je , onda je r = 1. Ako je , onda je r = 0.

Uvedena dodatna nejednakost mora biti zadovoljena za bilo koje cjelobrojno rješenje problema (12). Razmotrite neku jednačinu u t-tabelu (izostavljajući indeks reda) sa 0

gdje je x odgovarajuća komponenta vektora i trenutne nebazične varijable. Možemo izraziti x, a 0 i a j koristeći prikaz (14) koji je uveden gore:

Zamjenom izraza (16) i (17) u (15) i preuređivanjem pojmova dobijamo:

Budući da , i varijable x i podliježu zahtjevu nenegativnosti, lijeva strana jednačine (18) je uvijek nenegativna. Razmotrite izraz na desnoj strani, zatvoren u vitičaste zagrade. Koeficijenti u ovom izrazu su cijeli brojevi, a varijable podliježu zahtjevu za cijeli broj. Stoga, cijeli izraz u zagradama mora biti cijeli broj. Označimo to sa s, tj.:

.

Celobrojna slaba varijabla s nije negativna. Zaista, ako je s negativan, tj. bi uzeo vrijednosti -1, -2, ..., a zatim bi množenjem s cijelom desnom stranom jednadžbe (18) bila negativna, dok bi lijeva strana bila nenegativna.

Razmotrimo dva slučaja i . Za i . Zamjenom izraza za x iz (15) u jednačinu (19) dobijamo:

Jednačina (21) mora biti zadovoljena za bilo koje cjelobrojno rješenje problema (12). Imajte na umu da ako je 0 u jednačini (21). Stoga se jednadžba (21) može koristiti kao vodeća linija u simpleks metodi. Konkretno, uvijek možete odabrati dovoljno velik tako da vodeći element u redu (21) postane jednak –1, što će sačuvati cijeli broj tablice. Izbor odgovarajućeg će uticati na brzinu konvergencije algoritma. Prije svega, hajde da opišemo sam algoritam. Kao početno potrebno je uzeti dualno izvodljivo rješenje, koje se može dobiti dodavanjem ograničenja x n + m+1 =M – x 1 - - … - x n 0, gdje je M dovoljno velika konstanta, a nosi jedna iteracija sa dodanim redom i sa leksikografski minimalnom kolonom , uzetim kao vodećim. Algoritam se sastoji od sljedećih koraka:

Korak 0. Počnite s dvojno prihvatljivom matricom A 0 u jednačini (13), čiji su elementi cijeli brojevi (matrica A 0 može sadržavati i necijele elemente, pogledajte o tome, stranica 306).

Korak 1. Među redovima sa a i 0 0 (i=1, ..., n+m), tada je problem riješen.)

Korak 2. Odaberite (pravilo odabira će biti opisano kasnije) i napišite dodatni red na dnu tabele

Ova linija je odabrana kao vodeća linija.

Korak 3. Izvedite korak dual simplex metode, precrtajte dodatnu liniju i vratite se na korak 1.

Za dokaz konačnosti algoritma, vidi str. 303-304.

Pravilo odabira je formulirano na sljedeći način.

Korak 0. Neka se generira red s brojem v.

Korak 1. Neka je leksikografski minimalna kolona među stupcima sa vj

Korak 2. Za svaki a vj je najveći cijeli broj takav da (leksikografski manje).

Korak 3. Neka je , a (red v se generira). Onda

.

Korak 4. Stavite za vj

Gore opisano pravilo odabira vam omogućava da vodeći element učinite jednakim -1, uz zadržavanje dvostruke valjanosti tablice, a istovremeno će nulti stupac biti leksikografski smanjen što je više moguće.

2.2.2 Algoritam direktnog cjelobrojnog programiranja

Izraz “direktan” kada se primjenjuje na algoritam cjelobrojnog programiranja odnosi se na metodu koja dovodi do optimalnog rješenja dobivanjem sukcesivnih “poboljšanih” rješenja. Svako od ovih rješenja vrijedi u smislu da zadovoljava i linearna ograničenja i cjelobrojni uvjet. Jedna od vjerovatnih prednosti algoritma je mogućnost prekida proračuna prije nego što se dobije optimalno rješenje i korištenje najboljeg dobivenog rješenja kao približnog. Osim toga, direktni algoritam se može koristiti u kombinaciji s dualnim algoritmima za proizvodnju različitih kompozitnih algoritama koji se mogu kretati od faze koja proizvodi dvostruko izvodljiva rješenja u fazu koja proizvodi direktno izvodljiva rješenja.

Prirodni presedan za direktni algoritam je potpuno cijeli Gomori algoritam, budući da proces ovog algoritma proizvodi niz dualno izvodljivih cjelobrojnih rješenja. Treba podsjetiti da je potpuno cijeli Gomori algoritam modifikacija dual simplex metode. Glavna razlika s ovim algoritmom je u tome što je vodeći niz Gomori rez sa vodećim elementom od -1. Ovaj rez se dobija iz generišućeg niza, koji je definisan kao jedan od mogućih vodećih nizova u dual simpleks metodi. Korištenje takvog rezanja kao vodećeg reda će očuvati dvostruku valjanost i integritet tabele nakon iteracije.

Ispostavilo se da na sličan način možete modificirati simpleks metodu na način da dobijete algoritam koji čuva direktnu prihvatljivost i cjelovitost tablica. Da biste opisali postupak izračunavanja, razmotrite sljedeći problem cjelobrojnog programiranja:

maksimizirati

Pretpostavimo da je stupac odabran kao vodeći, a red v vodeći red u iteraciji simpleks metode, tj. za sve redove I u kojima je a >0. Prije izvođenja postupka Gaussove eliminacije u simpleks metodi, dodajemo u tablicu Gomorijevu graničnu vrijednost dobivenu iz reda v:

gdje je J skup indeksa nebazičnih varijabli u (22), s k je nova (osnovna) slaba varijabla i neodređena (privremeno) pozitivna konstanta.

Imajte na umu da ako postavimo = a vs , cutoff (23) će imati dva važna svojstva. prvo,

To znači da je direktna validnost tabele sačuvana ako koristimo odsecanje (23) kao vodeći red. Drugo, tj. vodeći element je 1 (ako se klip koristi kao vodeći niz). Lako je provjeriti (ispitujući formule za promjenu osnovnih varijabli) da transformacija simpleks tablice sa jednim vodećim elementom čuva cijeli broj elemenata simpleks tablice.

Ove ideje poslužile su kao osnova za direktni algoritam u cjelobrojnom programiranju:

Korak 0. Počnite sa kolonskom tablicom u kojoj su a i 0 0 (i 1) i svi elementi a 0 j, a ij i a i 0 cijeli brojevi.

Korak 1. Provjerite da li su uslovi a 0 j 0 (j 1); ako su zadovoljni, onda je krajnje, trenutno osnovno rješenje optimalno; ako ne, idite na korak 2.

Korak 2. Odaberite vodeću kolonu s sa 0 s 0. Ovaj red služi kao generator za Gomori rez.

Korak 3. Uzmite Gomori rez sa linije za generisanje i dodajte ga na dno tabele, tj. dodati jednačinu (23) ograničenjima problema, gdje je .

Korak 4. Pretvorite tabelu koristeći rez (23) kao vodeći red. Slaba varijabla s k u (23) će postati nebazna. Vratite se na korak 1.

Za dokaz konačnosti algoritma, vidi str. 346-353.

Budući da odabir generirajućeg niza nije trivijalan zadatak, čini se da mora postojati nekoliko nizova koji mogu poslužiti kao generirajući nizovi. U preliminarnim argumentima, vodeća linija simpleks metode korištena je kao generirajuća linija. Ova linija uvijek proizvodi graničnu vrijednost koja je vodeća linija s vodećim elementom jednakim jedan. Očigledno, postoje i drugi redovi u tabeli iz kojih se mogu dobiti rezovi sa istim svojstvima. Pretpostavimo da je granična vrijednost dobivena prema formuli:

gdje se određuje iz uslova

Definirajmo skup V(s) kao skup redova koji zadovoljavaju uvjet (25).

Sljedeća dva pravila su primjeri valjanih pravila za odabir nizova za generiranje:

Pravilo 1.

1. Sastavite sekvencijalnu konačnu listu indeksa reda tako da se indeks svakog reda pojavi u njoj barem jednom. Idite na 2.

2. Ako je lista prazna ili ne sadrži nijedan indeks od V(ova), vratite se na 1.; inače, pronađite prvi indeks v V(s) na listi. Odaberite red v kao proizvodnju. Izlaz indeks v i sve prethodne indekse sa liste. Idite na 3.

3. Konzistentno birajte niz v preuzet u 2. kao generirajući do v V(s). Jednom v V(s), vratite se na 2.

Pravilo 2.

1. Neka je V t (s) skup V(s) koji odgovara t-toj ​​tabeli. Ako V t (s) sadrži više od jednog elementa: V t (s) = (v 1, v 2, ..., v k +2), tada kao generator odaberite red takav da u nizu skupova V 1 (s 1), V 2 (s 2), ..., V t (s) linija se pojavila ranije (ne kasnije) od ostalih i zatim ostala do V t (s); idi na 2.

2. Dosljedno birajte niz v preuzet u 1. do . Jednom, vratite se na 1.

2.2.3. TEHNIKA ZA DOBIJANJE POČETNE DOZVOLJENE OSNOVE

Svaka od gore navedenih metoda može se riješiti samo ako je problem linearnog programiranja direktno ili dualno izvodljiv. Takva prihvatljivost znači prisustvo početne prihvatljive osnove u izvornom problemu. Ako je problem izvodljiv i direktno i dvojno, onda je rezultirajuće rješenje optimalno. U većini slučajeva, nakon postavljanja problema, ispostavi se da to nije dopušteno ni direktno ni dvojno. Stoga predstavljamo algoritam za dobijanje početne prihvatljive osnove.

Neka je problem linearnog programiranja napisan u kanonskom obliku:

minimizirati

pod uslovima

Svi b i mogu se učiniti nenegativnim množenjem, ako je potrebno, odgovarajuće jednačine sa –1. Zatim možete dodati umjetnu varijablu svakoj jednadžbi (vještačke varijable moraju biti nenegativne) na takav način da formirate početnu osnovu od umjetnih varijabli:

Vještačke varijable se mogu izvesti iz slabih varijabli koje se koriste za pretvaranje nejednakosti u jednačine. Zaista, ako su početna ograničenja problema linearnog programiranja data u obliku nejednačina:

tada, dodajući slabu varijablu svakoj nejednakosti, dobijamo:

Ako je b i 0, tada se s i može koristiti kao početne osnovne varijable.

Razlika između umjetnih varijabli i slabih varijabli s i je sljedeća. U optimalnom rješenju problema, sve umjetne varijable moraju biti jednake nuli, jer takve varijable ne postoje u izvornom problemu. S druge strane, sasvim je moguće da će u optimalnom rješenju slabe varijable imati pozitivne vrijednosti. Da bi umjetne varijable postale nula, funkcija cilja se može predstaviti na sljedeći način:

gdje su M i dovoljno veliki pozitivni brojevi. Ideja metode odgovara činjenici da se umjetnim varijablama daju očito visoke cijene. Ova metoda dovodi do nulte vrijednosti umjetnih varijabli u optimalnom rješenju.

Postoji još jedan način da se dobije početna prihvatljiva osnova. U ovoj metodi, kao iu prvoj, kao početne osnovne varijable koriste se umjetne varijable. Razmatra se nova funkcija cilja, koja je zbir umjetnih varijabli. Potrebno je minimizirati korištenje z-jednačine kao jednog od ograničenja. Ako originalni sistem jednačina ima izvodljivo rješenje, tada sve umjetne varijable moraju postati jednake nuli. Prema tome, minimalna vrijednost mora postati nula. Ako je , tada originalni sistem jednadžbi nema dopuštenih rješenja. Ako je , onda možemo izostaviti ciljnu funkciju i koristiti optimalni osnovni oblik kao početnu izvedivu osnovu za minimiziranje z. U literaturi se ova metoda naziva dvofazna simpleks metoda. U prvoj fazi metode minimiziranjem se pronalazi prihvatljiva osnova, u drugoj se minimizira z i dobiva se optimalna baza.

Razmotrite sljedeći problem linearnog programiranja kao primjer:

minimizirati

pod uslovima

gdje su svi b i nenegativni.

Ako uvedemo umjetne varijable i novu ciljnu funkciju, dobivamo sljedeći problem:

minimizirati

,

pod uslovima

Ako od -forme oduzmemo sve jednadžbe koje sadrže b i, dobićemo:

-z

gdje je Sistem (26) dijagonala u odnosu na Prva faza simpleks metode sastoji se od minimizacije pod uslovima (26). Nema ograničenja za znak z. U procesu proračuna, čim vještačka varijabla postane nebazična, a njen koeficijent u -formi pozitivan, sama varijabla i odgovarajući vektor stupaca se isključuju iz daljih proračuna.

2.3. OSOBINE PRAKTIČNE IMPLEMENTACIJE SISTEMA

U praksi, nije baš zgodno raditi sa informacijama u obliku u kojem su definisane u matematičkom modelu. Stoga, prije svega, odlučimo se o načinu organiziranja podataka ili modelu podataka.

2.3.1. IZBOR MODELA

Model podataka je skup sporazuma o metodama i sredstvima formalizacije opisa objekata i njihovih odnosa koji se odnose na automatizaciju procesa sistema. Tip modela i tipovi struktura podataka koji se u njemu koriste odražavaju koncept organizacije i obrade podataka koji se koristi u DBMS-u koji podržava model, odnosno u jeziku programskog sistema u kojem je kreiran aplikativni program za obradu podataka.

Za rješavanje ovog problema potrebno je kreirati model podataka u kojem bi količina pomoćnih informacija bila minimalna, postojala bi fundamentalna mogućnost višekorisničkog pristupa podacima, te bi se osigurao visok nivo zaštite podataka.

Trenutno postoje tri glavna pristupa formiranju modela podataka: hijerarhijski, mrežni i relacioni.

HIJERARHIJSKI METODA ORGANIZACIJE

Hijerarhijska baza podataka se sastoji od uređenog skupa stabala; tačnije, iz uređenog skupa višestrukih instanci istog tipa stabla. Tip stabla se sastoji od jednog "korijenskog" tipa zapisa i uređenog skupa nula ili više tipova podstabla (od kojih je svaki tip stabla). Tip stabla općenito je hijerarhijski organizirana zbirka tipova zapisa.

Integritet veza između predaka i potomaka se automatski održava. Osnovno pravilo: nijedno dijete ne može postojati bez svog roditelja. Imajte na umu da slično održavanje referentnog integriteta između zapisa koji nisu dio iste hijerarhije nije podržano.

MREŽNI NAČIN ORGANIZACIJE

Mrežni pristup organizaciji podataka je produžetak hijerarhijskog. U hijerarhijskim strukturama, podređeni zapis mora imati tačno jednog pretka; u strukturi mrežnih podataka, dijete može imati bilo koji broj predaka.

Mrežna baza podataka sastoji se od skupa zapisa i skupa veza između tih zapisa, tačnije, skupa instanci svakog tipa iz skupa tipova zapisa navedenih u šemi baze podataka i skupa instanci svakog tipa iz dati skup tipova povezivanja.

Tip odnosa je definiran za dvije vrste zapisa: predak i potomak. Instanca tipa odnosa sastoji se od jedne instance tipa zapisa pretka i uređenog skupa instanci tipa podređenog zapisa. Za dati tip veze L sa tipom zapisa pretka P i podređenim tipom zapisa C moraju biti ispunjena sljedeća dva uslova:

1. Svaka instanca tipa P je predak samo jedne instance L;

2. Svaka instanca C je dijete od najviše jedne instance L.

RELACIJSKI NAČIN ORGANIZACIJE

Glavni nedostaci hijerarhijskih i mrežnih tipova modela podataka su:

1. Previše teško za korištenje;

2. Poznavanje fizičke organizacije je zapravo potrebno;

3. Sistemi aplikacija zavise od ove organizacije;

4. Njihova logika je preopterećena detaljima organizacije pristupa bazi podataka.

Čini se da je najčešća interpretacija relacionog modela podataka ona Data, koji ga reproducira (sa raznim preciziranjem) u gotovo svim svojim knjigama. Prema Dateu, relacijski model se sastoji od tri dijela koji opisuju različite aspekte relacijskog pristupa: strukturni dio, manipulacijski dio i holistički dio.

Strukturni dio modela navodi da je jedina struktura podataka koja se koristi u relacijskim bazama podataka normalizirana n-arna relacija.

Manipulacioni dio modela afirmiše dva fundamentalna mehanizma za manipulaciju relacionim bazama podataka – relacionu algebru i relacioni račun. Prvi mehanizam je baziran uglavnom na klasičnoj teoriji skupova (sa nekim poboljšanjima), a drugi je zasnovan na klasičnom logičkom aparatu predikatskog računa prvog reda. Glavna funkcija manipulacionog dijela relacionog modela je da obezbijedi mjeru relacije bilo kojeg specifičnog jezika relacijske baze podataka: jezik se naziva relacijskim ako nije ništa manje izražajan i moćan od relacijske algebre ili relacionog računa.

Konačno, sastavni dio relacionog modela podataka fiksira dva osnovna zahtjeva integriteta koji moraju biti podržani u bilo kojem relacijskom DBMS-u. Prvi zahtjev se zove zahtjev integriteta entiteta. Drugi zahtjev se naziva zahtjevom referentnog integriteta.

Nakon preliminarne analize matematičkog modela sistema i metoda organizovanja podataka, kao i softvera dostupnog na tržištu (hijerarhijske i mrežne metode organizacije sugerišu objektno orijentisani pristup organizovanju podataka, a danas postoje takvi DBMS-ovi (npr. na primjer, Jasmin ili Informix Dynamic Server), ali na U vrijeme razvoja nije bilo mogućnosti njihovog korištenja, u isto vrijeme postoje vrlo „moćni“ relacijski DBMS-ovi (npr. Oracle 8i)) izbor je napravljen u korist relacionog metoda organizacije skladištenja podataka.

2.3.2. OPIS ULAZNIH INFORMACIJA

Sve informacije potrebne za rješavanje problema specificiraju se prije početka iteracija metoda za rješavanje problema rasporeda. Radi jednostavnosti, pretpostavlja se da su navedene informacije konstantne tokom perioda za koji se plan priprema.

Bez gubljenja određenog stepena uopštenosti zadatka, moguće je odrediti određeni skup ulaznih podataka neophodnih za formiranje ograničenja i rešavanje problema, a istovremeno zajednički za sve varijante praktičnih implementacija sistema. Zbog specifičnosti zadatka (mogućnost relativno lake adaptacije matematičkog modela za slučaj praktične implementacije u okviru određenog univerziteta) nisu razvijeni oblici dokumenata ulaznih informacija. Detalji ulaznih informacija opisani su u tabeli 2.

Tabela 2. Opis detalja ulaznih informacija

Naziv detalja	Karakteristike detalja
ulazni dokumenti	Tip	Max. dužina	Preciznost
Prezime, ime, patronim nastavnika; Kontakt telefon nastavnika; Fakultetska diploma; Akademsko zvanje; Naziv grupe; Broj članova grupe; Naziv predmeta koji se predaje; Broj sati u učionici; Broj publike; Informacije o publici; Naziv predmeta koji predaje nastavnik; Broj grupe u kojoj se predmet čita; Informacije o publici u kojoj se predmet čita.

Pored ovih podataka, matematički model zahtijeva prisustvo nekih dodatnih podataka, koji se mogu dobiti programskom analizom ulaznih informacija.

2.3.3. RAZVOJ INFORMACIONE PODRŠKE ZA ZADATAK

Analiziraćemo izvorne informacije kako bismo odredili sastav i strukturu informacija za kasniju formalizaciju i konstrukciju informaciono-logičkog modela podataka (ILM). Navedeni matematički model, kao i dodatne informacije iz opisa predmetne oblasti, omogućavaju nam da odredimo ulogu detalja u međusobno povezanim informacijama sadržanim u dokumentu. Na osnovu ove analize ustanovićemo funkcionalne zavisnosti detalja u skladu sa preporukama i zahtevima za normalizaciju podataka, nakon čega ćemo izvršiti samu normalizaciju. Svrha normalizacije je smanjiti (ali ne nužno eliminirati) redundantnost podataka. Međutim, ponekad se namjerno kreira neka redundantnost podataka kako bi se poboljšala efikasnost programa. Hajde da definišemo tri oblika normalizacije baze podataka.

Tablica je u prvom normalnom obliku (1NF) ako ima primarni ključ, svi atributi su jednostavni tipovi podataka i nema duplih atributa. Da bi bili u skladu sa 1NF, domene atributa moraju biti atomske vrijednosti i ne smije biti duplih grupa atributa. Sve duplirane grupe atributa moraju se premjestiti u novu tablicu.

Tablica je u drugom normalnom obliku (2NF) kada je u prvom normalnom obliku i svaki atribut koji nije ključ je potpuno funkcionalno ovisan o primarnom ključu (tj. u 2NF, svaki atribut koji nije ključ mora u potpunosti ovisiti o poljima primarnog ključa ključ).

Tabela je u trećem normalnom obliku (3NF) ako je u 2NF i nema tranzitivnih zavisnosti. Tranzitivne zavisnosti su funkcionalne zavisnosti između ne-ključnih atributa. Svaki ne-ključni atribut koji je funkcionalno ovisan o drugom ne-ključnom atributu iste tablice stvara tranzitivnu ovisnost i mora se premjestiti u drugu tablicu.

Rezultirajuće funkcionalne zavisnosti su prilično trivijalne i očito slijede iz matematičkog modela, pa nisu date u daljem opisu. Također, u sljedećem prikazu, srednji stupnjevi normalizacije su izostavljeni. Stoga predstavljamo samo konačni infološki model baze podataka (vidi sliku 1.).

Fig.1. Infološki model baze podataka za zadatak zakazivanja nastave

2.3.4. KARAKTERISTIKE OGRANIČENJA FORMIRANJA MATEMATIČKOG MODELA PROBLEMA RASPOREDA

Izrada ograničenja (1) – (7) matematičkog modela problema raspoređivanja je prilično trivijalan zadatak koji se može riješiti korištenjem jednostavnih SQL upita i ne zahtijeva preliminarnu analizu ulaznih informacija. Stoga ćemo se samo detaljnije zadržati na ograničenjima oblika (8).

Imajte na umu da je u matematičkom modelu sistema predmet koji se čita „vezan“ ne za određenu publiku, već za određeni skup publike. Postavljanje određenih brojeva publike vrši se nakon što je zadatak riješen. Ograničenja oblika (8) imaju smisla samo kada se skupovi publike ukrštaju. U matematičkom modelu sistema predlaže se da se uzmu u obzir svi jedinstveni parovi koji se seku u obliku ograničenja. Broj ovih raskrsnica može biti veliki, što može dovesti do velikog broja dodatnih ograničenja koja negativno utiču na brzinu optimizacijskih algoritama. Međutim, broj dodatnih ograničenja može se značajno smanjiti.

Razmotrimo slučaj linearnog rasporeda skupova koji se seku (vidi sliku 2).

Fig.2. Linearno seci skupovi

U slučaju ovakvog rasporeda kompleta učionica za izvođenje nastave, ukupan broj ograničenja oblika (8) biće n-1, gdje je n broj kompleta. Gore opisani raspored skupova koji se seku može se nazvati linearnim, jer je u ovom slučaju n skupova koji se seku raspoređeni kao da su u liniji. Možemo razmotriti slučaj kada se skupovi sijeku jedan drugog na proizvoljan način (vidi sliku 3.).

Fig.3. Proizvoljno sekući skupovi

Broj ograničenja oblika (8) u ovom slučaju može se smanjiti formiranjem ovih ograničenja po analogiji sa slučajem linearnog rasporeda skupova. Da biste to učinili, potrebno je pretpostaviti da su, na primjer, skupovi B i D koji se sijeku sa A jedan skup, odrediti područje presjeka takvog skupa sa skupom A, a zatim izvršiti iste radnje s rezultirajućim područje raskrsnice.

Za više informacija o tome, pogledajte stranicu 210.

2.4. Rezultati programa

Prilikom praktične implementacije sistema posebna pažnja je posvećena zadatku pisanja „jezgra“ sistema – metoda za rješavanje problema i procedura za formiranje ograničenja. Kako cilj nije bio pisanje komercijalnog proizvoda sa svim mogućnostima, dio interfejsa je napisan u svrhu testiranja kernela i određivanja granica primjenjivosti algoritama, stoga uključuje minimum funkcionalnosti i ne sadrži module za pretprocesiranje ulaznih podataka .

Jezgro sistema i interfejs su napisani u Delphi 6.0. Metode rješavanja i algoritmi za formiranje ograničenja napisani su korištenjem objektno orijentisanih tehnologija, što će u budućnosti omogućiti njihovo jednostavno inkapsuliranje u dalje modifikacije sistema bez narušavanja integriteta interakcije različitih algoritama. Tekst objektnih metoda za rješavanje problema dat je u Dodatku 2. Baza je implementirana na Oracle 8i DBMS, upiti prema njoj se vrše u PL/SQL jeziku.

Početni podaci zadatka unose se u tabele baze podataka pomoću obrazaca zahtjeva. Jedan od ovih oblika prikazan je na sl. 3.

Fig.3. Obrazac za unos početnih podataka

Podaci dobijeni kao rezultat rješavanja problema nisu dovoljni za prikaz rasporeda časova odmah nakon rješavanja zadatka, pa je napisan modul za naknadnu obradu podataka. Konačni raspored časova je prikazan u obliku tabele, čiji je primer prikazan na Sl. 4.

Rice. 4. Primjer rasporeda časova

Algoritmi za rješavanje problema testirani su na različitim uzorcima izvornih podataka. Testiranje je obavljeno na računaru sa Intel Pentium 350 MHz procesorom, Oracle 8i DBMS je instaliran na dual-procesor serveru: 2 CPU Intel Pentium II 350 MHz, RAM 384 MB; Kao komunikacioni kanal korišten je LAN sa propusnim opsegom do 100 Mbit/s. Kao izvorne podatke testa koristili smo kako stvarne podatke o grupama, nastavnicima i predmetima lektire večernjeg oblika obrazovanja na ChSU za školske 1999/2000. godine, tako i nasumično generisane izvorne podatke (čitljivi predmeti su bili nasumično dodijeljena publika za nastavu). U prosjeku je obavljeno od 5 do 10 testova za svaku testiranu dimenziju izvornih podataka. Kao rezultat, dobili smo podatke prikazane u tabeli 2. Na slici 5 prikazan je graf zavisnosti prosečnog vremena rešavanja zadatka od broja pročitanih subjekata i broja grupa.

2.5. Analiza dobijenih rezultata

Analizom dobijenih podataka možemo izvući neke zaključke o funkcionalnosti algoritama rješenja i matematičkog modela, njihovim nedostacima i područjima primjene.

Prvo, korišteni matematički model sadrži “dodatna” ograničenja, čije postojanje je posljedica linearnog cjelobrojnog modela; osim toga, svakom predmetu koji se čita na streamu (stream se može sastojati od jedne grupe) dodjeljuje se 12 (za večernje studente) varijable, od kojih je svaka Boolean varijabla. Drugo, vrijeme potrebno za rješavanje problema naglo raste kako se povećavaju ulazni podaci. To se događa zbog naglog povećanja broja varijabli i ograničenja u modelu, zbog čega se povećava dimenzija nizova i, shodno tome, vrijeme potrebno za rješavanje problema. Treće, matematički formalizirani problem pokriva samo zadatak kreiranja rasporeda za večernje studente bez uzimanja u obzir prijelaza između zgrada. Uzimanje u obzir dodatnih zahtjeva će povećati broj ograničenja problema, što će negativno utjecati na brzinu algoritama rješenja.

Obratimo pažnju na sve veću razliku između minimalne i prosječne vrijednosti vremena za rješavanje problema kako se povećava dimenzija problema. Ova razlika odgovara tome koliko je “uspješno” (najbliže optimalnom) pronađeno početno izvodljivo osnovno rješenje problema. Stoga se vrijeme potrebno za rješavanje problema može značajno smanjiti “uspješnim” pronalaženjem početnog osnovnog izvodljivog rješenja. Za pronalaženje takvog rješenja najbolje je koristiti heurističke i dekompozicione algoritme.

Zaključci U toku rada izgrađen je matematički model univerzitetskog rasporeda za slučaj večernjeg obrazovanja bez prijelaza između zgrada, odabrane su metode rješavanja problema i razvijen model za pohranjivanje početnih podataka problema. Model skladištenja izvornih podataka, algoritam za matematičku formalizaciju modela i metode rješenja implementirani su u obliku softverskih modula. Brzina algoritama je testirana na heterogenim skupovima početnih podataka, na osnovu čega su određene mogućnosti i područja primjene algoritama.

Na osnovu rezultata testiranja utvrđeno je da brzina rada algoritama za rješavanje problema jako ovisi o količini ulaznih informacija i početno dopuštenom osnovnom rješenju, te je stoga značajno inferiorna u odnosu na heurističke i dekompozicione algoritme. Ali u slučaju heurističkog rješenja, njegova optimalnost (ili postizanje globalnog maksimuma) može se dokazati samo potpunim pretraživanjem svih mogućih opcija (jasno je da će u ovom slučaju vrijeme rada algoritma biti jako dugo) , stoga se iteracije heurističkih algoritama zaustavljaju po dostizanju određenog maksimuma (nemoguće je reći da li je lokalni ili globalni) značaja. Rješenje takvog algoritma može biti blizu optimalnog, ali ne i optimalno. U ovom slučaju, za postizanje globalnog maksimuma, možete koristiti metodu rješenja koja se razmatra u radu, jer se optimum može postići u nekoliko iteracija opisanih metoda rješenja.

LITERATURA

1. Lagosha B.A., Petropavlovskaya A.V. Skup modela i metoda za optimizaciju rasporeda časova na sveučilištu // Ekonomija i matematika. metode. 1993. T. 29. Br. 4.

2. Hu T. Cjelobrojno programiranje i tokovi u mrežama. M.: Mir, 1979.

3. Lebedev S.S. Modifikacija Bendersove metode parcijalnog cjelobrojnog linearnog programiranja // Economics and Math. metode. 1994. T. 30. Br. 2.

4. Lebedev S.S., Zaslavsky A.A. Upotreba posebne metode grananja i veze za rješavanje cjelobrojnog generaliziranog transportnog problema // Ekonomija i matematika. metode. 1995. T. 31. Br. 2.

5. Zaslavsky A.A. Korištenje strategije varijabilne stratifikacije u općim problemima cjelobrojnog linearnog programiranja // Economics and Math. metode. 1997. T. 33. Br. 2.

6. Lebedev S.S. O metodi redoslijednog indeksiranja cjelobrojnog linearnog programiranja // Ekonomija i matematika. metode. 1997. T. 33. Br. 2.

7. Lebedev S.S., Zaslavsky A.A. Modificirana metoda označavanja za probleme Booleovog programiranja // Ekonomija i matematika. metode. 1998. T. 34. Br. 4.

8. Zaslavsky A.A. Kombinirana metoda rješavanja problema ruksaka // Ekonomija i matematika. metode. 1999. T. 35. Br. 1.

Dodatak 1. Mogućnosti softverskih proizvoda za sisteme raspoređivanja.

WITH AUTOR-2+ sistem je dizajniran za brzo i praktično kreiranje rasporeda časova i njihovo održavanje tokom cele školske godine.
A VTOR-2+ je univerzalni sistem. Postoji nekoliko verzija programa dizajniranih za bilo koju obrazovnu ustanovu:

Srednje i specijalizovane (matematičke, jezičke, itd.) škole, liceji, gimnazije;

Tehničke škole, škole i fakulteti;

Univerziteti sa jednom akademskom zgradom;

Univerziteti sa nekoliko akademskih zgrada (uključujući transfere između zgrada).

A VTOR-2+ omogućava da se što više pojednostavi i automatizuje složeni rad kreatora rasporeda. Sistem vam pomaže da jednostavno napravite, uredite i štampate u obliku praktičnih i vizuelnih dokumenata:

Raspored nastave (studijske grupe);

Rasporedi rada nastavnika;

Raspored učionica (kancelarija);

Obrazovni planovi;

Tarifiranje.

A VTOR-2+ ima lijep dizajn i ljubaznu uslugu. Program je prilično jednostavan za učenje. Postoji detaljan priručnik koji opisuje sve karakteristike i metode rada sa programom.
P Program radi na bilo kojem IBM kompatibilnom računaru, počevši od 486DX sa 4Mb RAM-a (i više), zauzima oko 1Mb na tvrdom disku. Operativni sistem: MS DOS ili WINDOWS 95/98.
IN Vrijeme rada zavisi od veličine obrazovne ustanove i snage računara. Kompletan proračun i optimizacija rasporeda za srednju školu (30 odeljenja, 60 nastavnika, dve smene) traje oko 15 minuta na računaru Celeron-400.

P Program se odlikuje jedinstvenim i veoma moćnim algoritmom za konstruisanje i optimizaciju rasporeda. Rezultirajući automatski raspored ne zahtijeva praktički nikakve ručne izmjene, odnosno, čak i uz vrlo složena i stroga ograničenja, sve moguće klase se automatski postavljaju. Ako postoje nerješive kontradikcije u izvornim podacima, one se mogu otkriti i eliminirati pomoću posebne jedinice za analizu.

A VTOR-2+ vam omogućava da:

Optimizirajte „prozore“ u rasporedu;

Uzmite u obzir potreban raspon dana/časova i za razrede i za nastavnike;

Optimalno je nastavu postaviti u učionice (auditorije), uzimajući u obzir karakteristike odjeljenja, predmeta, nastavnika i kapacitet učionice;

Voditi računa o prirodi posla i željama zaposlenih sa punim radnim vremenom i sa skraćenim radnim vremenom;

Lako je povezati („upariti“) nekoliko razreda (studijskih grupa) u tokove prilikom izvođenja bilo koje nastave;

Podijelite nastavu prilikom izvođenja nastave stranog jezika, fizičkog vaspitanja, rada, informatike (i svih drugih predmeta) u bilo koji broj podgrupa (do deset!);

Uvesti (pored glavnih predmeta) specijalne kurseve i izborne predmete;

Optimizirajte ujednačenost i radni intenzitet rasporeda.

2. Sistem “Raspored” verzija 4.0 Moskva – LinTech

Odmah treba napomenuti da je program „Raspored“ fokusiran na sastavljanje školskog rasporeda, korištenje na univerzitetima i fakultetima moguće je samo uz određene rezervacije. Zakazivanje se vrši u okviru skupa uslova koji se određuju u koracima unosa početnih podataka. Potpuna lista mogućih uslova je data u nastavku:

- O maksimalan broj lekcija je ograničen – tj. maksimalni dozvoljeni broj časova dnevno;

- R ujednačena raspodjela opterećenja nastavnika između dana rasporeda;

- R ujednačena raspodjela opterećenja nastave između dana rasporeda;

- TO praćenje prozora u rasporedu nastavnika;

- P Program uzima u obzir činjenicu da se odeljenja mogu proizvoljno ujedinjavati i razdvajati (odeljenja se mogu kombinovati u tokove ili podeliti u manje podgrupe, a ove podgrupe, zauzvrat, mogu poslužiti kao osnova za kombinovanje u veće grupe. Primer: u školi br. 1859 Postoje 2 viša razreda, ali u svakom od ovih razreda postoje po dve podgrupe za specijalizaciju, nastava iz opštih predmeta se održava za ceo razred odjednom, a predmeti na specijalizaciji - posebno.Ali pošto su podgrupe za specijalizaciju premale a nema dovoljno nastavnika, u nekim predmetima se mogu kombinovati i podgrupe 11a i 11b (npr. na stranom jeziku) - to otežava obezbjeđivanje kontinuiteta rasporeda časova (potrebno je osigurati kontinuitet rasporeda za svaku od podgrupa);

- N prisustvo nekoliko smjena - u ovom slučaju pojedinačna odeljenja moraju stići kasnije od grupa prve smjene; ​​osim toga, postaje teže kontrolisati prozorčiće u rasporedu nastavnika, ako postoje nastavnici koji rade u obje smjene - u ovom slučaju slučaju, u rasporedu ovih nastavnika, njihovi časovi moraju biti „ugovoreni” oko raskrsnice smjena;

- U uslov povezivanja nastavnika sa publikom - pojedini nastavnici imaju „svoju“ publiku u kojoj izvode sve svoje časove;

- N prisutnost „plutajuće“ smjene - kada vrijeme početka prve lekcije nije precizno određeno, jer formira se dinamički, ovisno o izdanju srodnih razreda, nastavnika i publike;

- TO praćenje da li raspored nekog objekta (razred, nastavnik, publika) spada u dozvoljeni radni opseg (na mapi vremenskih ograničenja). Na primjer, za nastavnika, mapa vremenskih ograničenja obično označava metodičke dane, ponekad i pojedinačne brojeve lekcija - jednom riječju, naznačene su one pozicije za koje je nemoguće postaviti nastavu uz sudjelovanje određenog objekta;

- N prisustvo kombinovanih predmeta – kao što su „strani jezici/informatika“, „informatika/rad“ itd. - kada je razred podijeljen u podgrupe;

- U uslov povezivanja predmeta sa učionicama - izvođenje nastave iz pojedinih predmeta moguće je samo u strogo određenoj učionici ili spisku učionica (fizičko vaspitanje, rad i sl.);

- WITH ostavljajući raspored uzimajući u obzir činjenicu da u nekim predmetima na čas ne dolazi cijeli razred, već njegova podgrupa. Kako bi spriječili da druga podgrupa luta školom u ovom trenutku, takvi časovi mogu biti striktno samo prvi ili posljednji razredi u rasporedu časova;

- “IN održavati paralele” - za neke nastavnike potrebno je uzeti u obzir činjenicu da izvođenje nastave zahtijeva dugotrajnu pripremu (na primjer, časovi hemije), u ovom slučaju se časovi u dnevnom rasporedu nastavnika nastoje rasporediti u blokovima. paralele, na primjer, prvi 5. razred, zatim 7. -y, itd., ili prilikom raspodjele između dana, rasporedite razrede u različitim paralelama u različite dane;

- I Ponekad je prilikom sastavljanja rasporeda potrebno uzeti u obzir nijansu da je za neke predmete raspored unaprijed poznat - u ovom slučaju se takvi razredi uvode kao nepomični (fiksni);

- TO kontrola zabranjenih kombinacija predmeta koji spadaju u isti dan u rasporedu časova – na primjer, nepoželjno je da se „fizičko vaspitanje“ i „rad“ izvode istog dana;

- IN ispunjavanje uslova potrebnih redosleda predmeta - kada je potrebno obezbediti ugradnju grupa časova u kojima se nastava mora odvijati određenim redosledom, na primer fizika-astronomija i sl.;

- N prisustvo časova vezanih za učionice - najveći deo časova za takve časove se održava u ovoj učionici, sa izuzetkom onih časova koji zahtevaju specijalizovanu učionicu;

- N potreba da se nastava iz pojedinih predmeta rasporedi u dva razreda za redom („u paru“, „iskri“), a ovaj uslov može biti strog (ni u kom slučaju ne razbijati „iskrice“ časova), ili može biti poželjniji (ako nije moguće pomjeriti dva razreda, može se slomiti „iskra“);

Ima se u vidu da je u nekim predmetima polaganje dozvoljeno samo u pojedinačnim razredima.

3. Sistem “metodista”.

Dostupan u dvije verzije.

Virtuelna verzija.

Dostupno bez modula za automatsko planiranje. Karakteristike virtuelne verzije:

Brza pretraga po listama nastavnika, učionica, razreda (grupa), disciplina, zgrada;

Pribavljanje referentnih informacija za svaki pronađeni element liste (kapacitet slušalaca, sve zgrade auditorijuma X, adresa i broj telefona nastavnika, spisak odjeljenja, broj sati u disciplini, nastavno opterećenje nastavnika i sl.);

Kontrola i mogućnost preraspodjele sati između sedmica u bilo kojoj akademskoj disciplini. grupe;

Automatska provjera mogućih grešaka u unosu podataka (podudarnost ukupnog broja sati i vrsta časova, neraspoređenost nastavnika u podgrupe, vremenski budžet studijske grupe i nastavnika, nesklad između sati u tokovnim grupama, itd.);

Mogućnost sistematskog pohranjivanja (i brzog pretraživanja) dodatnih (nisu potrebnih za zakazivanje) informacija: fotografije nastavnika, kustosa studijskih grupa (razrednih starešina), informacije o predstavnicima roditeljskih odbora, pozicijama, akademskim titulama i zvanjima odgovornim za publiku, ...

Brzo dobiti potpunu informaciju o kombinaciji faktora (sve grupe toka, sve discipline nastavnika X, sa naznakom opterećenja po sedmicama i vrste časova, koje discipline je dozvoljeno predavati u računarskoj nastavi, lične želje za izvođenje časovi bilo kojeg nastavnika, spisak praznika u sirijskoj grupi i još mnogo toga itd.);

Mogućnost pregleda, štampanja i uređivanja gotovog rasporeda sa provjerom ispravnosti izmjena (popunjenost učionica, nastavnika, grupa/podgrupa,...);

U svakom trenutku možete naručiti modul za generiranje rasporeda za pripremljene podatke;

Raspored se generiše na vašem računaru sa mogućnošću promene postavki, kontrole, uređivanja itd. (bez mogućnosti promjene sati, disciplina, nastavnika,...);

Ako se otkrije potreba za manjom (do 10%) izmjenom izvornih podataka (pronađene su greške, iznenadni dodaci), moguće je ponovno naručiti modul za generiranje rasporeda uz malu naknadu;

Možete se prebaciti na standardnu ​​verziju u bilo kojem trenutku;

Metodist - standard.

Pored karakteristika virtuelne verzije, uključuje:

Modul za automatsko planiranje;

Raspodjela i kontrola nastavnog opterećenja;

Strogo pridržavanje redoslijeda discipline (predavanja - 2 sata, vježbe - 4 sata, laboratorij...);

Izrada rasporeda za bilo koju vrstu obrazovne ustanove: sedmično ili semestralno (od 1 do 23 sedmice);

Računovodstvo za kombinovanje grupa (klasa) u tokove i/ili njihovo dijeljenje u podgrupe;

Dodjela posebnih učionica (kompjuterske nastave, jezičke laboratorije, bazen,...);

Obračun zapošljavanja nastavnika i učionica (nepuno radno vrijeme, korištenje zajedničke obrazovne baze);

Obračun vremena prijelaza između zgrada;

Vikendi i praznici - opšti i za pojedinačne studijske grupe (državni, vjerski, državni praznici);

Navođenje razloga za „neuspešnu raspodelu“ časova (učionica je zauzeta, nastavnik je raspoređen na nepoželjan dan u nedelji) sa mogućnošću njihove „ručne“ korekcije;

Mogućnost ponovnog automatskog “poboljšanja” rasporeda;

Mogućnost promjene značaja faktora koji se uzimaju u obzir pri izradi rasporeda;

Mogućnost uvođenja prioriteta nastavnika - stepen u kojem se uvažavaju njihove individualne želje;

Ograničenja funkcije “Metodista”:

Raspored u više smjena je ograničen na maksimalan broj časova dnevno - 7;

Nastava uvijek počinje prvom lekcijom/parom (ako je potrebno, moguće je dodijeliti „besplatnu lekciju“ prvom paru);

Vrijeme promjene se ne uzima u obzir (na primjer, za provjeru mogućnosti kretanja između zgrada);

„Nivo težine“ časova se ne uzima u obzir za njihovu racionalnu distribuciju tokom sedmice (iako je to moguće učiniti indirektno);

Trajanje nastave je konstantno (nemoguće je napraviti raspored za 30-minutni čas u srednjoj školi i 45-minutni čas u srednjoj školi).

Dodatak 2. Popis softverskog modula metoda za rješavanje problema automatskog raspoređivanja

type MyArray= niz realnih nizova;

MyArray_X = niz longinta;

procedure Step_Dual_simplex(var a:MyArray; m,n,i1,j1:integer);

(izvodi jedan korak dual simplex metode,

vodeći element - a)

var i,j:integer;

b,b1:niz realnih;

SetLength(b,m);SetLength(b1,n);

za i:=0 do m-1 uradi b[i]:=a;

za i:=0 do n-1 uradi b1[i]:=a;

za i:=0 do m-1 do

za j:=0 do n-1 počinje

ako je (i=i1) i (j=j1) onda a:=1/b

ako (i=i1) onda a:=b1[j]/b

ako (j=j1) onda a:=-b[i]/b

ostalo a:=a-b[i]*b1[j]/b;

za i:=0 do n-1 uradi a:=0;a:=-1;

Završi(b);Završi(b1);

funkcija Lexikogr_few(a:MyArray; m,n:integer;i,i1:integer):boolean;

(prvi stupac je leksikografski manji od drugog)

Lexikogr_few:=false;

dok (a=a) i (j

funkcija Find_nu(a:MyArray;m,n:integer; i,i1:integer):longint;

(i je indeks leksikografski minimalne kolone)

dok (a=a) i (j

if (j 0) onda Find_nu:=Round(Int(a/a));

procedura Full_Integer_Simplex(var x:MyArray_X; a:MyArray; m,n:integer);

(Potpuno cjelobrojni algoritam za linearni cjelobrojni problem

programiranje,

vidi Hu T. "Cjelobrojno programiranje i tokovi u mrežama", str. 300-309,

a je matrica veličine m+n+2*n+1, po analogiji:

Moramo pronaći maksimum

z= - 10x1 - 14x2 - 21x3

2x1 + 2x2 + 7x3 >= 14

8x1 + 11x2 + 9x3 >= 12

9x1 + 6x2 + 3x3 >=10,

procedura vraća vektor X, čijih je prvih m komponenti željeno rješenje,

ako je zadnja komponenta vektora = 1, tada rješenje ne postoji ili je ono = beskonačno)

var i,i1:integer;

dok (i =0) radi Inc(i); (proizvodnja žice)

dok (j =0) do Inc(j);

za i1:=1 do n-1 uradi ako (a

minimalna kolona)

(alfa izbor)

(Napiši(i," ",j);čitaj;)

za i1:=1 do n-1 uradi ako a

j1:=Pronađi_nu(a,m,n,j,i1);

ako (j1>0) i (-a/j1>alfa) onda alfa:=-a/j1;

(writeln(alfa," ",i," ",j);readln;)

(primam Gomori rez)

za i1:=0 do n-1 uradi ako je a>0 onda a:=okruglo(Int(a/alfa))

a:=okruglo(Int(a/alfa));

ako je Frac(a/alfa)0 onda a:=a-1;

Korak_Dual_simplex(a,m,n,m-1,j);

dok (i>=m-1) ili (j>=n);

za i:=0 do m-1 do x[i]:=round(a);

ako je j>=n onda x:=1 else x:=0;

procedure Step_One_Simplex(var a:MyArray; m,n,i:integer);

var i1,i2:integer;

(Jedan korak direktne cjelobrojne metode (proizvodna linija je zadnja

i - generirajuća kolona))

za i1:=0 do m-2 uradite a:=a/(-a);

za i2:=0 do n-1 do

za i1:=0 do m-2 do

ako je i2i onda a:=a+a*a;

procedura Direct_Integer_Simplex(var x:MyArray_X; a:MyArray; m,n:integer);

(Direktni cjelobrojni algoritam za cjelobrojni problem linearnog programiranja,

vidi Hu T. "Cjelobrojno programiranje i tokovi u mrežama", str. 344-370,

a je matrica veličine m+n+3*n+1 po analogiji:

treba maksimizirati

z = x1 + x2 + x3

4x1 + 5x2 + 2x3

tada će matrica a izgledati ovako:

10 1 1 1 - u ovom redu prvi broj je grubi maksimalni zbroj nebazičnih varijabli

0 0 0 0 - konac za odsijecanje Gomorija,

algoritam radi samo kada je a>=0

vraća vektor X - umjesto matrice identiteta željeno rješenje,

ako zadnja komponenta sadrži jedinicu, postoji greška u proračunima)

var i,j,i1,j1:integer;

b,b1,b2:niz bajtova;

SetLength(b,m);SetLength(b1,m);

za i:=0 do m-1 uradi b1[i]:=0;

(provjera uvjeta optimalnosti)

za j:=1 do n-1 uradi ako a

dok bool počinje

(traži kolonu za generiranje)

bool:=false;j1:=0;

za j:=1 do n-1 počinje

ako je a>0 onda

za i:=0 do m-3 uradi a:=a/a;

ako nije bool onda počinje j1:=j;bool:=true;kraj inače ako Lexikogr_few(a,m,n,j,j1)

(traži generiranje niza)

za j:=1 do n-1 do

ako je a>0 onda

za i:=0 do m-3 uradi a:=a*a;

Pretpostavimo da postoji skup n identični procesori, određeni i m nezavisnih zadataka
koje treba završiti. Procesori mogu raditi istovremeno, a bilo koji zadatak se može izvršiti na bilo kojem procesoru. Jednom kada se posao učita u procesor, on ostaje tamo do kraja obrade. Vrijeme obrade posla poznati i jednaki
Organizirajte obradu zadataka na način da se cijeli set zadataka završi što je brže moguće.

Sistem radi na sljedeći način: prvi slobodni procesor preuzima sljedeći zadatak sa liste. Ako se dva ili više procesora oslobode u isto vrijeme, tada će procesor s najmanjim brojem izvršiti sljedeći zadatak sa liste.

Primjer. Neka postoje tri procesora i šest poslova, od kojih je vrijeme izvršenja jednako:

Razmotrite raspored U početnom trenutku T=0, procesor započinje obradu posla , procesor - zadaci , i procesor - zadaci . CPU završava zadatak u određenom trenutku
, dok su procesori I i dalje rade na svojim prvobitnim zadacima. At T=3 CPU ponovo završava zadatak i započinje obradu zadatka , koji se trenutno završava T=4. Tada počinje da izvršava poslednji zadatak . Procesori I završiti zadatke kada T=5, ali pošto je lista L prazne, zaustavljaju se. CPU završi zadatak at T=12. Razmatrani raspored je ilustrovan na slici 1. vremenski dijagram poznat kao Gantov grafikon. Očigledno da raspored nije optimalan. Možete "odabrati", na primjer, raspored koji vam omogućava da izvršite sve zadatke T* = 8 jedinice vremena (slika 2.).

Pogledajmo sada drugu vrstu problema planiranja za višeprocesorske sisteme. Umjesto pitanja o najbržem završetku skupa poslova za fiksni broj procesora, sada postavljamo pitanje o minimalnom broju procesora koji je potreban da se određeni skup poslova završi u određenom vremenu. . Naravno da je vreme neće biti manje od vremena potrebnog da se izvrši najintenzivniji zadatak.

U ovoj formulaciji, problem raspoređivanja je ekvivalentan sljedećem problemu pakiranja. Neka svaki procesor odgovara kutiji veličina . Neka svaki zadatak odgovara veličini artikla , jednako vremenu izvršenja zadatka , Gdje
Sada, da biste riješili problem zakazivanja, morate izgraditi algoritam koji vam omogućava da sve stavke stavite u minimalan broj kutija. Naravno, ne možete puniti kutije preko njihovog kapaciteta. , a objekti se ne mogu podijeliti na dijelove.

Književnost

1. T. Cormen, C. Leiserson, R. Rivest

Algoritmi: konstrukcija i analiza. M.: MTsNMO, 2000.

2. D. Knuth Umetnost programiranja, tom 1. Osnovni algoritmi. Uch. selo M.: Ed. Kuća Williams, 2000.

3. Wirth N. Algoritmi i strukture podataka.: Per. Sa engleskog - M.: Mir, 2001.

4. Khusainov B.S. Strukture i algoritmi za obradu podataka. Primjeri na

C jezik Udžbenik dodatak. M: Finansije i statistika, 2004.

5. A. Aho, J. Hopcroft, J. Ullman, Strukture podataka i algoritmi M: Sankt Peterburg: Kijev: Williams, 2001.