Основоположники математического программирования Данциг и Канторович

     Теория  графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые  дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.

 

Рис. 1 Граф с шестью вершинами и семью ребрами 

     При изображении графов чаще всего используется следующая система обозначений: каждой вершине сопоставляется точка  на плоскости, и если между вершинами существует ребро, то соответствующие точки соединяются отрезком. В случае ориентированного графа отрезки заменяют стрелками.

     Не  следует путать изображение графа  с собственно графом (абстрактной  структурой), поскольку одному графу  можно сопоставить не одно графическое представление. Изображение призвано лишь показать, какие пары вершин соединены рёбрами, а какие — нет. Часто на практике бывает трудно ответить на вопрос, являются ли два изображения моделями одного и того же графа или нет. В зависимости от задачи, одни изображения могут давать более наглядную картину, чем другие.

Алгоритм

     Шаг 1

     Пронумеровать вершины исходного графа целыми числами от 1 до N. Сформировать матрицу (размерностью NxN), каждый элемент i, j которой определяет длину кратчайшей дуги ведущей из вершины i в вершину j. В отсутствие такой дуги положить

     Шаг 2

     Здесь через обозначается матрица размерностью mxm с элементами Последовательно определить элементы матрицы D^m из элементов матрицы D^{m − 1} для m принимающих значения 1,2,...N:

 

Кроме того, для  всех i и m положить  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Заключение 
 

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

     «Математическое программирование было благословенно как минимум двумя исключительно творческими гениальными людьми: Джорджем Данцигом и Леонидом Канторовичем»(Белинский В.Г.)

     Леонид Витальевич Канторович вошел в плеяду выдающихся ученых двадцатого столетия благодаря своему капитальному вкладу в математику и экономику. Он по праву считается одним из основоположников современного математико-экономического направления, ядро которого составляют теория и модели линейных экстремальных задач. Это направление было затем переоткрыто и развито в трудах других ученых (прежде всего, Дж. Данцига) и получило название “линейное программирование”.

     Идеи  и методы, вызревшие в рамках линейного  программирования, положили начало глубоким математическим исследованиям, вышли далеко за пределы экономических приложений и используются в самых разнообразных сферах человеческой деятельности: физике, химии, энергетике, геологии, биологии, механике и теории управления. Линейное программирование оказывает существенное влияние также на прогресс вычислительной математики и вычислительной техники. А теперь и в сфере экономики.

     Леониду Витальевичу хватило не только таланта  выдающегося математика и экономиста, но и интеллектуальной решимости и гражданского мужества бороться за признание своих экономико-математических теорий.

Удивительно прозорливым  оказалось положение Л.В. Канторовича  о том, что элементы пространства Канторовича суть обобщенные числа. Эвристический принцип Канторовича нашел блестящее подтверждение в рамках современной математической логики.

     Для  огромного числа  его  учеников  и  последователей  работы  Л.В.  Канторовича определили характер научного мышления и деятельности на всю жизнь.

     К их числу относятся и пишущие эти строки.

     Безвозвратно  ушли в прошлое годы общения с  Л.В.  Канторовичем,

время его максимального  вклада в науку и воздействия  на жизнь.  Но

с  каждым днем все понятнее и значительнее становятся масштабы его

творчества.  Все  отчетливее проявляется значимость  его  научного

наследия для  грядущих времен.

     Своей  научной и человеческой судьбой  Л.В. Канторович  преподал

нам три величайших урока:

  -    задачи  организационного управления в нашем сложном мире,

чреватом   катастрофическими  последствиями  ошибок,   все   более

нуждаются  в  научном анализе и требуют  самых совершенных  (в  том

числе математических и компьютерных) средств современной  науки;

   -    научная методология, передовые идеи,  способные в корне

переустроить  и преобразовать управление обществом,  предотвратить

катастрофическое  развитие, побеждают не сами собой, а в результате

колоссального   напряжения   духовных   и   интеллектуальных   сил

конкретных личностей;

   -    каждый  человек наиболее всего способствует  благу всего

человечества,   если   он   в  меру  отпущенных   ему   творческих

возможностей   трудится   во   имя  разумного   и   благополучного

обустройства  своего собственного государтсва.

     Канторовича востребованы человечеством, что видно  по учебным планам любого экономического или математического факультета в мире. Аппарат математики и идея оптимальности стали подручными орудиями любого практикующего экономиста.

     Экономика как вечный партнер математики избежит  слияния с любой эзотерической  частью гуманитарных наук, политики или  беллетристики. Новые поколения  математиков будут смотреть на загадочные проблемы экономики как на бездонный  источник вдохновения и привлекательную арену приложения и совершенствования своих безупречно строгих методов.

Вычисление победит  гадание. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Список  используемой литературы 
 

1 Д. Данциг. Линейное программирование, его применения и обобщения.

2 Л.В. Канторович, А.Б. Горстко. Математическое оптимальное программирование в экономике.

3 Кутателадзе С.С., Макаров В.Л., Романовский И.В., Рубинштейн Г. Ш. Научное наследие Л.В. Канторовича (1912-1986).

4 Канторович     Л.В.    Математические    методы    организации и планирования производства.  5.Канторович  Л.В. Мой путь в науке.