Подпишитесь на наши новости
Вернуться к началу с статьи up
 

ДИСКРЕ́ТНЫЕ МОДЕ́ЛИ

  • рубрика

    Рубрика: Математика

  • родственные статьи
  • image description

    В книжной версии

    Том 9. Москва, 2007, стр. 57

  • image description

    Скопировать библиографическую ссылку:




Авторы: И. Х. Сигал

ДИСКРЕ́ТНЫЕ МОДЕ́ЛИ, мо­де­ли, пе­ре­мен­ные и па­ра­мет­ры ко­то­рых яв­ля­ют­ся дис­крет­ны­ми ве­ли­чи­на­ми, т. е. ве­ли­чи­на­ми, при­ни­маю­щи­ми ко­неч­ное или счёт­ное чи­сло зна­че­ний; в за­да­чах, свя­зан­ных с та­ки­ми мо­де­ля­ми, мно­же­ст­во до­пус­ти­мых ре­ше­ний так­же дис­крет­но. При по­строе­нии и ана­ли­зе Д. м. ис­поль­зу­ют­ся ма­те­ма­тич. ме­то­ды дис­крет­ной ма­те­ма­ти­ки, ал­геб­ра­ич. и др. из­вест­ные ма­те­ма­тич. ме­то­ды, а ино­гда тре­бу­ет­ся раз­ра­бот­ка но­вых.

Д. м. воз­ни­ка­ют в свя­зи со мн. за­да­ча­ми в эко­но­ми­ке, управ­ле­нии, тех­ни­ке и др. при­клад­ных об­лас­тях. За­да­чи Д. м., как и ал­го­рит­мы их ре­ше­ния, но­сят, как пра­ви­ло, ком­би­на­тор­ный ха­рак­тер, что обу­слов­ле­но ко­неч­но­стью мно­же­ст­ва воз­мож­ных ва­ри­ан­тов ре­ше­ний. Сре­ди раз­ра­бо­тан­ных Д. м. мож­но вы­де­лить сле­дую­щие осн. клас­сы: Д. м. транс­порт­но­го ти­па и пла­ни­ро­ва­ния пе­ре­во­зок, се­те­вые и по­то­ко­вые Д. м., Д. м. управ­ле­ния за­па­са­ми, Д. м. раз­ме­ще­ния, Д. м. тео­рии рас­пи­са­ний, Д. м. ло­гич. про­ек­ти­ро­ва­ния, Д. м. рас­пре­де­ле­ния ре­сур­сов, Д. м. фор­ми­ро­ва­ния про­из­вод­ст­вен­ных сис­тем, Д. м. ран­жи­ро­ва­ния и кла­сте­ри­за­ции. В ка­че­ст­ве отд. клас­сов Д. м. рас­смат­ри­ва­ют­ся сто­хас­тич. и ди­на­мич. мо­де­ли. Боль­шое вни­ма­ние уде­ля­ет­ся раз­ра­бот­ке дис­крет­ных эко­но­ми­ко-ма­те­ма­тич. мо­де­лей.

При ис­сле­до­ва­нии Д. м. час­то рас­смат­ри­ва­ют­ся дис­крет­ные экс­тре­маль­ные за­да­чи, не­ре­гу­ляр­ные за­да­чи разл. ти­пов, за­да­чи с раз­рыв­ны­ми це­ле­вы­ми функ­ция­ми, мно­го­экс­тре­маль­ные за­да­чи, за­да­чи тео­рии гра­фов, за­да­чи о по­кры­ти­ях.

Ме­то­ды и ал­го­рит­мы ре­ше­ния дис­крет­ных за­дач обыч­но но­сят ком­би­на­тор­ный ха­рак­тер. Осн. идея этих ме­то­дов со­сто­ит в вы­де­ле­нии и от­се­ве (от­бра­сы­ва­нии) под­мно­жеств до­пус­ти­мых ре­ше­ний, за­ве­до­мо не со­дер­жа­щих оп­ти­маль­ных. Имен­но это со­став­ля­ет ос­но­ву мн. ис­поль­зуе­мых в Д. м. ал­го­рит­мов. Наи­бо­лее час­то при­ме­ня­ют­ся ме­тод по­сле­до­ва­тель­но­го ана­ли­за ва­ри­ан­тов, ме­тод вет­вей и гра­ниц, ме­тод ди­на­мич. про­грам­ми­ро­ва­ния, ме­тод по­сле­до­ва­тель­ных рас­чё­тов, ап­прок­си­ма­ци­он­но-ком­би­на­тор­ный ме­тод. Мн. совр. вер­сии ал­го­рит­мов яв­ля­ют­ся ком­би­ни­ро­ван­ны­ми, в рам­ках ко­то­рых при­ме­ня­ют­ся эле­мен­ты не­сколь­ких ал­го­рит­мов.

Лит.: Лих­тен­штейн В. Е. Мо­де­ли дис­крет­но­го про­грам­ми­ро­ва­ния. М., 1971; Ваг­нер Г. Ос­но­вы ис­сле­до­ва­ний опе­ра­ций: В 3 т. М., 1972–1973; Про­пой А. И. Эле­мен­ты тео­рии оп­ти­маль­ных дис­крет­ных про­цес­сов. М., 1973; Фин­кель­штейн Ю. Ю. При­бли­жен­ные ме­то­ды и при­клад­ные за­да­чи дис­крет­но­го про­грам­ми­ро­ва­ния. М., 1976; Мои­се­ев Н. Н. Ма­те­ма­ти­че­ские за­да­чи сис­тем­но­го ана­ли­за. М., 1981; Ком­би­на­тор­ные ме­то­ды и ал­го­рит­мы ре­ше­ния за­дач дис­крет­ной оп­ти­ми­за­ции боль­шой раз­мер­но­сти. М., 2000; Си­гал И. Х., Ива­но­ва АП. Вве­де­ние в при­клад­ное дис­крет­ное про­грам­ми­ро­ва­ние: Мо­де­ли и вы­чис­ли­тель­ные ал­го­рит­мы. М., 2002.

Вернуться к началу