Design of combinatorics tasks on columns in terms of task mathematical programming

S. N. Semenets, S. S. Nasonova


Raising of problem. To the decision of combinatorics tasks on columns distinguish three basic approaches. The first envisages development of corresponding algorithms on the basis of methods of theory of the graphs. Second and third approaches are based on bringing the initial task over, set forth in terms of counts, to the task of optimization. Thus for the decision of the got task of optimization within the framework of the second approach the proper algorithms of optimization are developed, and within the framework of the third – the applied computer technologies the instrumental environment of which is adapted to the decision of tasks of optimization are used. For computer realization of the first and second approaches the special software development of which is accessible to far not every user is required. In addition, in the case of clarification of raising of one or another model task on columns (for example, by introduction of additional limitations) usually modification of the known algorithms of its decision and proper revision of software appears necessary. All this makes it very difficult in practice, the implementation of numerical experiments on a graph model. The most convenient for a wide range of users is a third approach to the solution of combinatorial problems on graphs, since it does not require for its computer implementation, the development of specific algorithms and software. However, issues of harmonization and optimization of the resulting model the ability to apply computer technology require further research and practical study. In this article one of possible methods of realization of the third going is examined near the decision of combinatorics tasks on columns, envisaging bringing an initial count model over to the task of the mathematical programming and subsequent decision of the last in an instrumental environment building on of Excel "Solver".

Purpose of the article – to show effectiveness and sufficient community of such method of decision of combinatorics tasks on columns.

Conclusion. The results got in the article show that many combinatorics tasks set forth in terms of counts, it is undifficult reformulate as a task of the mathematical programming. The optimization model got here, as a rule, appears linear relatively unknown. For numeral realization of such models building on of MS Excel is well adjusted "Solver", that does the tabular processor of Excel effective computer technology of decision of combinatorics tasks on columns even in case of their large enough dimension.


graph; model; optimization; combinatorial problems on graphs; mathematical programming problem


Johnson J.C., Wood D.F., Vordlou D.L. and Murphy-ml P.R. Sovremennaya logistika [Modern Logistics]. Moskow: Vil'yams, 2002, 615 p. (in Russian).

Lovas L. and Plammer M. Prikladnye zadachi teorii grafov. Teoriya parosochetaniy v matematike, fizike, khimii [Applicated tasks of graph theory. Matchings theory in mathematics, physics, chemistry]. Moskow: Mir, 1998, 653 p. (in Russian).

Kas'yanov V.N. and Evstigneev V.A Grafy v programmirovanii: obrabotka, vizualizatsiya i primenenie [Graphs in pro- gramming: processing, visualization and application]. Sankt-Peterburg: BKHV Peterburg, 2003, 1104 p. (in Russian).

Kostyukova N.I. Grafy i ikh primenenie. Kombinatornye algoritmy dlya programmistov [Graphs and their application. Combinatorial algorithms for programmers]. Moskow, 2007, 310 p. (in Russian).

Majnika E. Algoritmy optimizatsii na setyakh i grafakh [Optimization algorithms on networks and graphs]. Moskow: Mir, 1981, 323 p. (in Russian).

Kormen T., Lejzerson Ch., Rivest R. and Shtain K. Algoritmy: postroenie i analiz [The algorithms for working with graphs]. Moskow: Vil'yams, 2006, 1296 p. (in Russian).

Zykov A.A. Osnovy teorii grafov [Fundamentals of graph theory]. Moskva: Vuzovskaya kniga, 2004, 664 p. (in Russian).

Gorbatov V.A. Fundamental'nye osnovy diskretnoy matematiki. Informatsionnaya matematika [Fundamentals of dis- crete mathematics. Information Mathematics]. Moskow: Nauka, Fizmatlit, 2000, 544 p. (in Russian).

Berzh K. Teoriya grafov i ee primenenie [Graph theory and its applications]. Moskow: Inostran. lit., 1962, 319 p. (in Russian).

Kofman A. Vvedenie v prikladnuyu kombinatoriku [Introduction to applied combinatorics]. Moskow: Nauka, 1975, 479 p. (in Russian).

Akho A., Khopkroft D. and Ul'man D. Postroenie i analiz vychislitel'nykh algoritmov [Construction and analysis of computational algorithms]. Moskow: Mir, 1979, 536 p. (in Russian).

Basaker R. and Saati T. Konechnye grafy i seti [Finishing graphs and networks]. Moskow: Nauka, 1974, 368 p. (in Rusian).

GOST Style Citations

Современная логистика / Джеймс С. Джонсон, Дональд Ф. Вуд, Дэниел Л. Вордлоу, Поль Р. Мэрфи-мл. ; [пер. с англ. А. И. Мороза, С. Г. Тригуб]. – 7-е изд. – Москва : Вильямс, 2002. – 615 с.


Ловас Л. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии / Л. Ловас, М. Пламмер ; пер. с англ. Г. П. Гаврилова [и др.] ; под ред. Г. П. Гаврилова. – Москва : Мир, 1998. – 653 с. : ил.


Касьянов В. Н. Графы в программировании: обработка, визуализация и применение / В. Н. Касьянов, В. А. Евстигнеев. – Санкт-Петербург : БХВ-Петербург, 2003. – 1104 с. – (Научное издание).


Костюкова Н. И. Графы и их применение. Комбинаторные алгоритмы для программистов / Н. И. Костюкова. – Москва, 2007. – 310 с. – (Основы информационных технологий).


Майника Э. Алгоритмы оптимизации на сетях и графах : пер. с англ. / Э. Майника. – Москва : Мир, 1981. – 323 с.


Алгоритмы: построение и анализ : пер. с англ. / Т. Кормен, Ч. Лейзерсон, Р. Ривест, K. Штайн. – Москва : Виль- ямс, 2006. – 1296 с.


Зыков А. А. Основы теории графов / А. А. Зыков. – Москва : Вузовская книга, 2004. – 664 c.


Горбатов В. А. Фундаментальные основы дискретной математики. Информационная математика / В. А. Горбатов. – Москва : Наука : Физматлит, 2000. – 544 с.


Берж К. Теория графов и ее применение / К. Берж ; пер. с фр. и послесл. А. А. Зыкова ; под ред. И. А. Вайнштейна. – Москва : Иностран. лит., 1962. – 319 с.


Кофман А. Введение в прикладную комбинаторику / Кофман А. ; пер. с фр. В. П. Мякишева, В. Е. Тараканова ; под. ред. Б. А. Севастьянова. – Москва : Наука, 1975. – 479 с.


Ахо А. Построение и анализ вычислительных алгоритмов : пер. с англ. / А. Ахо, Дж. Хопкрофт, Дж. Ульман ; пер. с англ. А. О. Слисенко ; под ред. Ю. В. Матиясевича. – Москва : Мир, 1979. – 536 с.


Басакер Р. Конечные графы и сети : пер. с англ. / Р. Басакер, Т. Саати. – Москва : Наука, 1974. – 368 с.