Haupt- Andere Disziplinen Bücher Matisch mathematische programuvannya - Nakonechny S.І.

Matisch mathematische programuvannya - Nakonechny S.І.

6.7. Kolben zastosuvannya tsіlochislovih Aufgaben lіnіynogo programuvannya in planuvannі dass upravlіnnі virobnitstvom

Die Aufgabe , über Rucksack. Nayprostіshoyu tsіlochislovogo programuvannya Aufgaben und Aufgaben der Entbehrung ein obmezhennyam s Same, Je Aufgabe über Rucksack (Tornister abo). Eine solche Aufgabe Got Bagato prikladіv praktische zastosuvannya. Hosting-Projekt "Aufgabe über Rucksack 's pov'yazana іnterpretatsієyu zadachі Vibor naykraschogo Lager predmetіv scho zadovolnyayut pevnі Köpfen problemi Touristen schodo Vibor gіpotetichnoї optimalnoї kіlkostі Reden zu wandern.

Tourist Mauger vibirati potrіbnі rechі іz Liste z n predmetіv. Vіdoma Wagga Haut j- ten Thema . Viznachena takozh tsіnnіst Haut Geist predmetіv . Die maximale Wagga vsogo Vantage in einem Rucksack ist nicht Mauger perevischuvati zaznachenogo obsyagu M. Neobhіdno viznachiti, skіlki predmetіv Haut Anblick Tourist Got poklast Rucksack, Bewohner zagalna tsіnnіst sporyadzhennya Bula Maximum von Köpfen vikonannya obmezhennya Bar im Rucksack zu brechen.

Poznachimo durch - Menge predmetіv j-ten Ansicht in einem Rucksack. Todі matisch mathematisches Modell zadachі Matim viglyad:

;

. - Tsіlі Zahlen .

Landwirt Dünger zemelnoї dіlyanki neobhіdno pridbati 107 kg gut. Vіn dobriva Mauger in Packungen von 35 kg vartіstyu 14 d kaufen. od. abo 24 kg vartіstyu 12 d. od. Metoyu Bauer Je zakupіvlya nicht weniger dann, nіzh 107 kg Willkommen s mіnіmalnimi vitratami. Und potrіbno kupuvati abo tsіlu Verpackung, abo nicht kupuvati її zovsіm, mehr Chastain pridbati nemozhlivo Verpackung.

Rozv'yazannya. Poznachimo Menge Pakete vagoyu 35 kg 24 kg, die vagoyu vіdpovіdno zmіnnimi dass . Maєmo Modell tsієї zadachі:

;

. - Tsіlі Nummer.

In rezultatі rozv'yazuvannya zadachі ob Yakim s vischenavedenih metodіv otrimaєmo optimalen Plan: . . Otzhe für optimalen Plan naymenshі vitrati scho dorіvnyuyut 50 d. od., mozhlivі in razі zakupіvlі odnієї Verpackung Willkommen vagoyu 35 kg, die troh vagoyu bis 24 kg.

Das Problem der optimalen rozkroyu materіalіv. Auf pіdpriєmstvі zdіysnyuєtsya rozkrіy m rіznih partіy materіalіv in obsyagah odinits odnakovogo rozmіru in kozhnіy partії. Іz materіalіv usіh partіy potrіbno vigotoviti Maximale Menge komplektіv Z, in Leder s yakih p rіznih vidіv okremih Chastain in kіlkostі eingeben odinits, vrahovuyuchi, scho kutanen odinitsyu materіalu mozhna rozkroїti auf okremі Chastain n rіznimi Wege und haben razі rozkroyu odinitsі i -oї partії j -im Weg otrimuєmo Teile r th Geist.

Zapishemo matisch mathematische Modell zadachі. Poznachimo durch - Anzahl odinits materіalu i -oї partії, scho wird j -im Weg rozkroєnі. Todі s i -oї für j-ten Verfahren von rozkroyu otrimaєmo partії Teile r th Geist. W usієї Nun , ich habe -oї partії razі zastosuvannya zu neї vsіh n sposobіv rozkroyu otrimaєmo Teile r-ten Mittelwert und s m usіh partіy їh bude otrimano . Wir setzen Leder Got vhoditi Details zu vіdnoshennya viznachaє Menge komplektіv, SSMSC mozhna vigotoviti s Teile r th Geist. Menge Povny komplektіv für vsіh vidіv Teile viznachaєtsya naymenshim s Tsikh vіdnoshen.

In razі Povny Kit Got vikonuvatisya rіvnіst vіdnoshen:

.

zvіdki p - 1 vіdnoshennya mozhna viraziti durch , ob Yak s ihnen napríklad durch Pershe:

abo .

Zamіnivshi dass їh Wert otrimaєmo p - 1 obmezhennya stosovno komplektіv:

;

Vrahovuyuchi nayavnu Menge odinits materіalu in partіyah, zapishemo m obmezhen schodo resursіv:

.

(Obmezhennya schodo vikoristannya resursіv Formgebung kann Buti rіvnyannyami chi nerіvnostyami Brach od von povnіstyu chi nicht povnіstyu neobhіdno vikoristati nayavny obsyag resursіv).

OAO Alle mayutsya zadovolnyati Köpfe nevіd'єmnostі: dass tsіlochislovostі.

Otzhe, neobhіdno wissen naybіlshe funktsії Werte:

für obmezhen:

.

- Tsіlі Nummer .

Rozglyanemo Hintern zadachі optimale rozkroyu materіalіv.

Auf dem Workshop rozrіzuyut Prouty zavdovzhki 6 m zagotіvki dovzhinoyu 1.4, i 2,5 m 2 Shop obslugovuє dvoh zamovnikіv für Haut s yakih okremo neobhіdno wissen .:

1. Yak rozrіzati 200 prutіv, Bewohner otrimati nicht weniger als Yak 40, 60 i 50 zagotіvok zavdovzhki vіdpovіdno 1,4; . 2 i 2,5 m Kriterіy optimіzatsії - mіnіmum vіdhodіv;
2. Yak rozrіzati 200 prutіv für formuvannya s otrimanih zagotіvok komplektіv scho skladayutsya s dvoh zagotіvok dovzhinoyu 1,4 m, das auf odnіy dovzhinoyu 2 i 2,5 m Kriterіy optimіzatsії -. Höchstmenge komplektіv.

Rozv'yazannya.

1) rozv'yazhemo Aufgabe für Persha Köpfe zamovnika. Maєmo partіyu prutіv in kіlkostі Stücke. Vіdoma untere Begrenzung kіlkostі zagotіvok kutane Form. Vvedemo takі poznachennya:

- Blick zagotіvki;

- Sposіb rozrіzannya Stab;

- Vihіd in razі rozrіzuvannya Stange j -im Weg zagotіvok r th Geist;

cj - vіdhodi in razі rozrіzuvannya Stange j -im Weg;

- Menge nayavnih prutіv;

Dr - untere Grenze in der r erforderlich -іy zagotіvtsі;

xj - Menge prutіv, SSMSC rozrіzanі für j -im Weg.

Zapishemo matisch mathematisches Modell für rozv'yazuvannya Perche Absatz zadachі optimale rozkroyu.

Kriterієm optimalnostі Je mіnіmalna vіdhodіv Menge: .

Menge otrimanih zagotіvok Haut dagegen Got Booty nicht weniger als od zaznachenih Notwendigkeit:

Sumarno Menge prutіv, SSMSC rozrіzanі rіznimi Wege nicht Mauger Buti bіlshoyu od kіlkostі nayavnih prutіv:

.

Zmіnnі zadachі - Nevіd'єmnі i tsіlі Nummer. Otzhe, maєmo matisch mathematische Modell:

.

- Tsіlі Nummer .

Pobuduєmo numerische ekonomіko-matisch mathematische Modell rozrіzuvannya prutіv, rozglyanuvshi mozhlivі varіanti їh rozrіzuvannya:

Tabelle 6.5

Bajan, Bewohner in mnozhinu vvіyshli OAO Alle mozhlivі varіanti, navіt takі, SSMSC auf Purshia Poglyad zdayutsya neefektivnimi, napriklad X 6.

Zapishemo numerische ekonomіko-matisch mathematische Modell rozrіzuvannya prutіv:

der Geister:

a) Menge zagotіvok zavdovzhki 1,4 m:

;

b) Menge zagotіvok zavdovzhki 2 m:

;

c) Anzahl zagotіvok zavdovzhki 2,5 m:

;

g) Menge nayavnih prutіv:

;

d) nevіd'єmnіst zmіnnih:

;

h) tsіlochislovіst zmіnnih:

- Tsіlі Nummer .

Otzhe, zagalom maєmo matisch mathematische Modell des Geistes:

.

- Tsіlі Nummer .

Rozv'yazuyuchi Aufgabe ein іz metodіv tsіlochislovogo programuvannya, otrimuєmo nabіr alternative planіv optimal (zagalnoyu kіlkіstyu 146). Napríklad, Taqiy Plan zabezpechuє vigotovlennya vsіh vidіv zagotіvok in mіnіmalno mozhlivіy kіlkostі für naymenshogo zagalnogo obsyagu vіdhodіv und Entzugs tsogo vikoristovuyutsya Prouty 54: . , Tobto 4 Prouty neobhіdno rozrіzati andere Art und Weise (drei zagotіvki dovzhinoyu 2 m) ist der 50 prutіv vierte Methode (für odnіy kutane Form zagotіvtsі). Sumarno dovzhina zalishkіv dorіvnyuє p'yati Meter. Analogіchne Werte tsіlovoї funktsії ( ) Daє optimalen Plan für vigotovlyaєtsya bіlsha Menge Yakima kіntsevoї produktsії dass vitrachaєtsya alle nayavny materіal:

.

Otrimanі optimalnі nabіr Pläne bieten eine Alternative upravlіnskih rіshen Akzeptanz für spezifische virobnichih Köpfe varіantіv.

Uskladnimo rozglyanuty Hintern zadachі optimale rozkroyu materіalіv scho peredbachaє tіlki einen Typ materіalu dass vіdsutnіst formuvannya komplektіv kіntsevoї produktsії.

2) rozv'yazhemo Problem in den Köpfen der anderen zamovnika. Oskіlki in einem anderen punktі zadachі vіdsutnі obmezhennya schodo kіlkostі zagotіvok gegen vimagaєtsya formuvannya komplektіv, neobhіdno descho zmіniti poznachennya:

- Blick zagotіvki;

- Sposіb rozrіzuvannya Stab;

- Vihіd in razі rozrіzuvannya Stange j -im Weg zagotіvok r th Geist;

- Menge nayavnih prutіv;

xj - Menge prutіv, SSMSC rozrіzanі für j -im varіantom;

- Menge r-ten Mittel zagotіvok in komplektі;

- Menge vsіh r th Geist zagotіvok.

Matisch mathematisches Modell in tsomu razі suttєvo vіdrіznyaєtsya od modelі scho rozglyanuta Vische.

W usogo materіalu Mauger Buti otrimano zagotіvok r th Geist. We Got vhoditi Leather Kit Dvi zagotіvki Perche Typ , Um vіdnoshennya viznachaє Menge komplektіv, SSMSC mozhna sklasti s zagotіvok Perche Geist. Analogіchno mozhna viznachiti Menge komplektіv für іnshih vidіv zagotіvok dass . Menge mozhlivih Povny komplektіv viznachaєtsya naymenshim s Tsikh vіdnoshen: . Bevor der Brunnen bei razі Got Povny Kit vikonuvatisya rіvnіst vіdnoshen: Zwei zvіdki s vіdnoshen mozhna viraziti, napríklad durch Pershe:

, zvіdki . .

Zamіnimo dass їh Wert:

abo ;

abo .

Vrahovuyuchi nayavnu Menge odinits materіalu, zapishemo obmezhennya schodo vikoristannya resursіv:

.

OAO Alle mayutsya zadovolnyati Köpfe nevіd'єmnostі: dass tsіlochislovostі.

Otzhe, neobhіdno wissen naybіlshe funktsії Werte:

für obmezhen:

.

- Tsіlі Nummer .

Zapishemo numerische matisch mathematische Modell skoristavshis poperednіmi danimi rozrahunkіv mozhlivih varіantіv rozrіzuvannya prutіv (Tab. 6.5).

Іz Köpfen formuvannya komplektіv maєmo: Tobto zagotіvok Perche, Got Geist Beute vdvіchі bіlshe, nіzh eine andere, die dritte Art zagotіvok. Zvіdsi viplivaє, scho für mіnіmalnu Menge komplektіv Mauger Buti priynyate odne s dvoh vіdnoshen: chi . Viberemo, napriklad, . Vikoristovuyuchi danі tablitsі, zapishemo viraz für tsіlovoї funktsії:

.

Obmezhennya schodo formuvannya komplektіv matimut viglyad: , abo

.

zvіdsi

.

analogіchno für :

, abo

.

Obmezhennya schodo vikoristannya nayavnih prutіv:

.

Obmezhennya stosovno nevіd'єmnostі dass tsіlochislovostі zmіnnih:

;

- Tsіlі Nummer .

Otzhe, zagalom maєmo Taku matisch mathematische Modell:

max

- Tsіlі Nummer .

Rozv'yazavshi Problem, ob Yakim s vischeopisanih metodіv, otrimaєmo optimalen Plan: .

komplektіv.

Aufgabe komіvoyazhera. Rozglyadaєtsya mіst n A 1, A 2, ..., An sind, scho pov'yazanі mіzh ihn trammel Transport. Vіdoma Matrix vіdstaney od Mista Haut usіh іnshih:

.

Und in zagalnomu vipadku nicht zavzhdi . Komіvoyazher schuldig pobuvati in Haut mіstі tіlki einmal ich in jenen Misto drehen, s yakogo Pocha ruhatisya. Neobhіdno vіdshukati Taqiy zamkneny Route, scho durch die Haut Misto Deprivation passieren, wenn ich dovzhina yakogo mіnіmalna.

Poznachimo:

Otzhe, hij Mauger Deprivation nabuvati dvoh Wert: odinitsі abo Null. Takі zmіnnі Mühsal Titel bulovih zmіnnih. Offensichtlich scho stinken Yea tsіlochislovimi. Tsіlovoyu funktsієyu tsієї zadachі Je mіnіmіzatsіya vsogo komіvoyazhera Route:

.

de Sij - vіdstan mіzh mіstami dass i j.

Obmezhennya schodo Einweg v'їzdu in Haut Misto:

.

Obmezhennya schodo Einweg viїzdu Haut Mista:

.

Zaznachenі obmezhennya nicht povnіstyu opisuyut dopustimі Routen i nicht viklyuchayut mozhlivostі rozrivu Route. Dwellers usunuti Tsey nedolіk, vvedemo nevіd'єmnі tsіlochislovі zmіnnі , SSMSC in protsesі rozv'yazuvannya zadachі nabuvatimut Werte der Ordnung nomerіv mіst für eine optimale Routen pryamuvannya komіvoyazhera. Zapishemo obmezhennya, SSMSC usuvayut mozhlivіst іsnuvannya pіdmarshrutіv:

.

Dovedemo, scho für dovіlnogo Route, yaky pochinaєtsya in A punktі 1 takі wissen kann , Scho zadovolnyayut nerіvnіst Führung. Nekhay komіvoyazher pereїzhdzhaє s Mista Mista Aі zu Aj in der p-ten krotsі i erlaubt takozh, scho , Todі s Mista Aj komіvoyazher virushit am folgenden (p + 1) -ten i krotsі . Zvіdsi viplivaє scho:

.

Solche nerіvnіst vikonuєtsya dafür , ob yakih Wert von i j , die razі haben, wenn , Während nerіvnіst vikonuєtsya Yak streng rіvnyannya. Otzhe, Yakscho VIBRAT Route peresuvannya h i-ten bis j-ten Mista, dann zgadana nerіvnіst fіksuє zwei pіdryad Sequenznummer Tsikh mіst.

Otzhe, maєmo Taku matisch mathematische Modell:

In ekonomіchnomu regіonі rozmіscheno 6 punktіv (mіst). Komіvoyazher, yaky viїzhdzhaє s Mista 1, Got pobuvati in Haut mіstі einmal drehen i Artikel zu vihіdnogo. Wissen naykorotshy Strecke Yakscho vіdstanі mіzh mіstami vіdomі (in km navedenі in Abb. 6.7).

Fig. 6.7

Rozv'yazannya. Maєmo 6 punktіv de Got pobuvati komіvoyazher.

Poznachimo:

Otzhe, hij - bulovі (tsіlochislovі) zmіnnі. Zapishemo numerische ekonomіko-matisch mathematische Modell zadachі komіvoyazhera für danih Köpfe.

Vihodyachi s Abb. 6.5 visnovuєmo scho vsіh mozhlivih marshrutіv Je 12. Mista G Perche mozhna potrapiti die Haut s іnshih p'yati, vіdpovіdnі Routen poznachimo zmіnnimi . . . . . Freund von Misto pov'yazane Deprivation s troma іnshimi und das Gleiche, s Perche, der vierte ist die p'yatim, Otzhe, maєmo takі drei zmіnnі: . . . Analogіchno poznachaєmo zmіnnі scho vіdpovіdayut mozhlivim Routen peresuvan dritte, vierte, das Shostya mіst p'yatogo:

s Third - . . .

s vierte - . . . . .

s p'yatogo - . . . .

s Shostya - . . . .

Zagalom otrimali 24 zmіnnі. Jedoch deyakі zmіnnі, napriklad, dass . dass opisuyut eine Strecke dovzhina yakogo für Köpfe zadachі zmіnyuєtsya od napryamku peresuvannya (bei razі pereїzdu s Persha Mista zum anderen chi s eine andere Perche neobhіdno podolati 50 km) nicht brach. Otzhe, koefіtsієnt in tsіlovіy funktsії unter solchen zmіnnih bude odnakovim.

Kriterіy optimalnostі - mіnіmіzatsіya dovzhini vsogo komіvoyazhera Route:

;

a) obmezhennya schodo Einweg v'їzdu in Haut Misto:

b) obmezhennya schodo Einweg viїzdu Haut Mista:

;

;

;

;

;

c) obmezhennya schodo usunennya pіdmarshrutіv:

;

;

;

;

;

;

;

;

;

;

;

;

;

;

ui (uj) - tsіlі Nummer .

Takі zadachі rozv'yazuyutsya spetsіalnimi Methoden.

In rezultatі otrimuєmo varіant optimal peresuvannya dieser Strecke (Abb. 6.8).

Tobto s Persha Mista für optimalen Plan die vierte neobhіdno pereїzhdzhati, s vierte - bis zu einem Drittel, der dritt - zu Shostya, s Shostya - zu p'yatogo, s p'yatogo - zum anderen, und das andere s - bis Perche. Dovzhina tsogo Route, Yak Yea mіnіmalnoyu, dorіvnyuє 300 km.

Zauvazhimo scho analogіchnі zadachі nerіdko vinikayut auf praktitsі, vor allem in drіbnomu bіznesі. Typen Mauger Buti, napriklad, TAKE zavdannya "Firma haben mіstі Got 25 kіoskіv, SSMSC torguyut nicht-alkoholischen Napo. Schodenno s bazi avtomobіlem rozvozyat, um ihre Waren. Yak optimal organіzuvati rozvezennya Pevnyi obsyagu Produkt? ".

Problem s postіynimi vitrat Einige der Elemente. Vіdomo scho vitrati vigotovlennya, ob yakoї produktsії skladayutsya s dvoh Chastain: postіynih die zmіnnih vitrat.

Nekhay rozglyadaєtsya Prozesse virobnitstva produktsії von Köpfen vikoristannya m vidіv resursіv. Vіdomі obsyagi Haut Geist resursіv Und takozh i-te normalisierte vikoristannya bezieht odinitsyu vigotovlennya j - ten zu resursіv Geist produktsії .

Minds vikoristannya resursіv auf vigotovlennya produktsії mozhna zapisati in viglyadі solche obmezhen:

.

Vitrati auf vigotovlennya produktsії podіlyayut zwei Vidi: postіynі vitrati - , SSMSC nicht abgestanden od obsyagu virobnitstva, i zmіnnі - Cj, scho rozrahovuyutsya auf odinitsyu vigotovlenoї produktsії de j - Art produktsії. Neobhіdno viznachiti optimalnі obsyagi virobnitstva produktsії Für yakih boule b zagalnі vitrati mіnіmalnimi.

Zauvazhimo scho vigotovlennya ob yakoї kіlkostі produktsії potrebuє Pevnyi fіksovanih dass zmіnnih vitrat, tobto zagalna Scrip vitrat auf vigotovlennya produktsії obsyagom viznachaєtsya der Formel: . Allerdings razі, Yakscho (Produkciya vipuskaєtsya nicht), die Formel für rozrahunok vitrat im Allgemeinen produziert dodatnogo Wert scho falsch auf. Um ausreichend vіdobrazhennya funktsіonalnoї zalezhnostі zagalnih vitrat od obsyagu viroblenoї produktsії j-ten Form kann mit einer solchen nelіnіynoyu funktsієyu skoristatisya:

.

de Je bulovimi zmіnnimi Geist:

Taku Köpfe mozhna zapisati in viglyadі lіnіynoї nerіvnostі. Akzeptabel, scho Takeo іsnuє dosit große Anzahl M für yakogo Umov vikonuvatimetsya für vsіh zulässigen Wert . Todі obmezhennya Geist:

zavzhdi vikonuєtsya bei , I, krіm von Yakscho - Tsіle Nummer, dann mіnіmіzatsіya tsіlovoї funktsії zabezpechuє naymenshe Werte . Yakscho Dann nerіvnіst zabezpechit .

Otzhe, maєmo Taku matisch mathematische Modell:

tsіlova funktsіya scho opisuє mіnіmalnі zagalnі vitrati auf virobnitstvo vsіh vidіv produktsії, nabuvaє viglyadu:

der Geister:

;

;

- Tsіlі Nummer .

Farmer planuє viroblyati drei Vidi produktsії: Winterweizen, tsukrovі Buriak die Milch. Zagalnі vitrati skladayutsya s dvoh Chastain: postіynih die zmіnnih. Vіdpovіdnі danі navedenі Tabelle. 6.6:

Tabelle 6.6

Neobhіdno viznachiti optimalen Plan virobnitstva produktsії Haut für Geist gemeint, Got scho ein Landwirt von 100 Hektar rіllі.

Rozv'yazannya. Nekhay xj - obsyag virobnitstva j-ten Mittel produktsії m, .

Funktsіya zagalnih vitrat virobnitstvo auf den j-ten Mittel produktsії Got viglyad:

.

Tsіlovoyu funktsієyu in tsomu Mauger Buti prikladі maksimіzatsіya pributku:

.

de rj - Bewerten odinitsі j -ї produktsії.

zapishemo obmezhennya schodo vikoristannya rіllі wie folgt:

.

AJ de - Rate Nachfrage von rіllі auf virobnitstvo odinitsі j -ї produktsії; A - Ploscha rіllі.

Zagalom maєmo Taku matisch mathematische Modell:

;

;

- Tsіlі Nummer .

Zapishemo numerische ekonomіko-matisch mathematische Modell tsієї zadachі. Offensichtlich scho maximale mozhlivy obsyag virobnitstva pshenitsі immer = 500 m, tsukrovih buryakіv - = 5000 Tonnen Milch - = 400 t Otzhe, M Mauger dorіvnyuvati 5000. Zvіdsi maєmo .:

der Geister:

;

;

;

;

;

- Tsіlі Nummer .

Rozv'yazavshi Aufgabe otrimaєmo optimalen Plan:

. .

Mozhna visnovuvati, Bauer scho Tsikh Köpfe für nayvigіdnіshe zaynyatisya viroschuvannyam auf vsіy ploschі rіllі tіlki tsukrovih buryakіv.

Zvichayno have realnіy situatsії іsnuє bіlshy nabіr mozhlivih vidіv produktsії und takozh bіlshe obmezhen schodo vikoristannya resursіv.

Aufgabe planuvannya virobnichoї lіnії. Rozglyadaєtsya verarbeitet funktsіonuvannya virobnichoї lіnії. Vіdoma Schema Yak zobrazhaє poslіdovnіst robіt für vigotovlennya k vidіv produktsії . Vіdomі takozh: aj - trivalіst vikonannya j -ї operatsії ; - Termіn für den k - ten virobu neobhіdno abgeschlossen operatsіyu j zu yakogo; xj - Zeit cob j -ї operatsії; t - trivalіst vikonannya vsіh operatsіy. Dopuskaєtsya, scho an, ob yaky Zeit auf verstatі vikonuєtsya tіlki ein operatsіya.

Neobhіdno viznachiti optimalnі Momente cob kozhnoї operatsії.

Ekonomіko-matisch mathematisches Modell virobnichoї lіnії mіstitime takі Groupies obmezhen:

1. Poslіdovnіst vikonannya j -ї operatsії zapisuєtsya für vsіh operatsіy Paare wie folgt aus : Yakscho -ma j operatsіya pereduє i- th operatsії.

2. obmezhennya schodo nerozgaluzhenostі virobnichogo Prozesse für operatsіy dass i j, SSMSC nicht vikonuyutsya odnochasno (i ≠ j), Got viglyad:

abo xi - xj = aj, j Yakscho operatsіya pereduє operatsії i;

abo xj - xi = ai, i Yakscho operatsіya pereduє operatsії j.

Zauvazhimo scho logіchnі obmezhennya bedeuten "Abo-abo" mozhut vhoditi nicht zu ekonomіko-matematichnoї modelі zadachі lіnіynogo programuvannya, oskіlki stinken porodzhuyut neopuklu mnozhinu Zulässigkeit rozv'yazkіv. Тому необхідно ввести допоміжні змінні, які уможливлюють запис наведених вище логічних умов у вигляді лінійних обмежень. Це такі бульові змінні:

Скориставшись прийомом з попереднього прикладу 6.6. (введення досить великого числа М ), запишемо обмеження:

;

.

де М — досить велике число.

3. Обмеження щодо термінів виготовлення кожного виробу:

.

де j — остання операція для k -го виробу.

4. Усі операції мають бути виконані до моменту t :

. .

Критерій оптимальності:

.

тобто ставиться завдання, щоб тривалість виготовлення всіх видів виробів була мінімальною.

Отже, маємо таку математичну модель:

. — цілі числа .

Потрібно оптимізувати функціонування виробничої лінії, яка охоплює 11 операцій з виготовлення двох виробів. Лінію обладнано одним багатоопераційним верстатом. Послідовність і тривалість (у хвилинах) виконання операцій відображені на рис. 6.9.

Fig. 6.9

Визначені тривалості виготовлення виробів А та В відповідно дорівнюють 120 і 150 хв. Передбачається, що в кожний момент часу на верстаті може виконуватися тільки одна операція. Визначити оптимальні моменти початку кожної операції.

Rozv'yazannya. Позначивши через хj момент початку j -ої операції, запишемо числову економіко-математичну модель функціонування виробничої лінії:

за наведених нижче умов.

1. Обмеження стосовно послідовності виконання операцій:

;

;

;

;

;

;

;

;

;

;

;

.

2. Обмеження щодо нерозгалуженості виробничого процесу:

;

;

;

;

.........................................

;

;

...........................................

;

.

3. Обмеження щодо тривалостей виготовлення виробів:

;

.

4. Усі операції мають бути виконані до моменту t :

;

;

;

...................

;

..................

.

5. Обмеження щодо невід'ємності змінних:

;

. — цілі .

Отже, маємо частково цілочислову задачу з бульовими змінними.

Задача про призначення . Ця задача була розглянута в розділі 5 як така, що зводиться до транспортної і може бути розв'язана одним з відомих методів знаходження оптимального плану транспортної задачі. Проте такий вид задач належить до задач цілочислового програмування, оскільки їх змінні є бульовими і оптимальний план може бути знайденим також методами цілочислового програмування. Не повертаючись до загальної постановки задачі та побудови її математичної моделі (див. § 5.10), наведемо ще один приклад задачі про призначення.

Необхідно розподілити чотирьох робітників за чотирма видами устаткування так, щоб їх загальна продуктивність праці була максимальною. Дані стосовно продуктивності праці кожного робітника на устаткуванні кожному виду наведено в табл. 6.7:

Таблиця 6.7

Rozv'yazannya. Зазначимо, що дану задачу можна розглядати як транспортну, в якій робітники ототожнюються з постачальниками вантажів, а види устаткування — зі споживачами цих вантажів. Обсяги пропозиції та попиту в кожному разі дорівнюють одиниці. Отже, змінні будуть бульовими:

Якщо відома продуктивність праці і -го робітника на j -му устаткуванні, то числова модель про призначення набуває вигляду:

за умов:

;

;

;

;

;

;

;

.

;

— цілі числа .

З огляду на особливу структуру цієї задачі, зокрема на її «транспортний» характер та рівність правих частин обмежень, для її розв'язування можна застосувати ефективніший алгоритм, ніж для звичайної задачі цілочислового програмування з бульовими змінними. Пропонуємо читачеві ознайомитися з такими алгоритмами, які детально описані в літературі [12].