WWW.KNIGI.KONFLIB.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

 
<< HOME
Научная библиотека
CONTACTS

Pages:     | 1 |   ...   | 63 | 64 || 66 | 67 |   ...   | 93 |

«ТРУДЫ XI МЕЖДУНАРОДНЫХ КОЛМОГОРОВСКИХ ЧТЕНИЙ Ярославль 2013 УДК 51; 51:372.8; 51(091) Печатается по решению редакционноББК 22.1 я434 издательского совета ЯГПУ им. К. Д. ...»

-- [ Страница 65 ] --

В то же время в конце 40-х годов ХХ столетия Дж. Данцингу (1914-2005) удалось создать простой и ясный метод решения задачи линейного программирования. Полное описание этого метода он опубликовал в своей монографии 1963 году (см. русский перевод [2]). Главное его достоинство – простая идея движения по ребрам выпуклого многогранника – ограниченного полиэдра (2)-(3) от одной вершины к другой. Эта идея, как отмечает Дж. Данциг [2], “ ранее была отвергнута как неэффективная. Однако в другой геометрии она оказалась полезной и, по счастливой случайности, была проверена и принята”.

Метод, разрабатываемый и испытанный Дж. Данцигом и получивший название Симплексметода показал прекрасные результаты, превзошедшие даже ожидания автора (“Меня неизменно удивляла потрясающая мощь симплекс-метода” – Дж. Данциг). Так в работе [4] С.И. Гасса приведена экспериментальная оценка числа итерации S (т.е. перебираемых вершин) симплекс-метода для его решения задачи линейного программирования в канонической форме (в условии (2) неравенства выполняются как равенства):

Ясно, что для числа вершин h многогранника условий задачи линейного программирования имеет место оценка:

Точных оценок сложности реализации симплекс-метода до настоящего времени не найдено.

В то же время сама идея симплекс-метода и гипотетические возможности оценок безусловно должны базироваться (и базировались) на анализе структур полиэдральных множеств (2), (3).

Исторические этапы такого этапа представляются следующим образом:

1. Вычисление объемов простых многогранников различного типа (математические результаты древних Китая и Египта). Работы Архимеда.

Если математические исследования в древнем Египте (2050-1800 гг. до н.э.) в основном касались определения объемов некоторых полиэдров, например пирамид и усеченных пирамид, а аналогичные исследования в Китае (книга V “Математика девяти книгах” приблизительно 100 г.

до н.э.) ограничивалась трехгранными призмами (цзянь-ду), усеченными конусами (цзой-чи), параллелепипедами и их модификациями [7], то в Греции были получены результаты практически полностью определяющие структуру( числа вершин,ребер, граней ),так называемых, правильных многогранников или тел Платона (427-347 гг. до н. э.) – выпуклых многогранников, все грани которых одинаковые правильные многоугольные и все многогранные углы при вершине равные.

Эти результаты были существенно дополнены Архимедом (ок. 287-212 гг. до н.э.), который полностью исследовал структуру не только пяти тел Платона, но и 13 из 16 полуправильных многогранников (выпуклых многогранников, все углы которого равны или равны все грани. Причем группа поворотов с отражениями вокруг центра тяжести переводит любую его вершину (грань) в любую его вершину (грань) [8, 10-11]).

2. Формула Л. Эйлера.

В 1752 г. Л. Эйлер (1701-1783) опубликовал результат:

Ласковая Т.А., Рыбников К.К., Чернобровина О.К. Исторические аспекты развития методов анализа структуры полиэдральных множеств и их значение в оценке эффективности методов линейного программирования где f0 – число вершин, f1 – число ребер и f2 – число граней выпуклого многогранника (см., например, [9]).

Как правило, отмечают, что это правило было известно еще Р. Декарду (1595-1650) (см., например, [13]).

3. Первые попытки анализа систем линейных неравенств произвольной размерности.

На рубеже XVIII и XIX веков благодаря работам Ж. Лагранджа (1736-1813), Ж. Фурье (1768а позднее М. Остроградского (1801-1868) и П. Чебышева (1821-1894) возник к линейным неравенствам произвольной размерности, а, следовательно, к выпуклым многогранникам.

В 1827 г. Ж. Фурье опубликовал работу, связанную с определением низшей точки, так называемой впоследствии, “чаши Фурье” – выпуклой кусочно-линейной поверхности, направленной выпуклостью вниз. При решении этой задачи впервые был предложен итерационный метод движения по точкам полиэдральной поверхности (см., например, [14, 15]).

4. Обобщение формулы Эйлера.

Формула Эйлера (6) благодаря усилиям А. Пункаре (1854-1912) была обобщена для случая n-мерных выпуклых многогранников (см., например, [13]):

где fi – число граней размерности i (i = 0, 1,..., n 1).

Этот результат завершил исследования полиэдральных множеств в XIX веке.

5. Начало XX века. Результаты, предшествующие созданию симплекс-метода.

Еще в середине XIX века П.Чебышевым была поставлена задача определения точки x такой, что Метод решения этой задачи был предложен в 1907 году Ш. Валле-Пуссеном (1866-1962).

Как отмечает А. Схрейвер [5] это метод может рассматриваться как предшественник симплексметода. Именно в этой работе появились, по-существу, аналитические описания вершин и опорных плоскостей (граней размерности n 1). В совокупности с теоремой Вейля-Минковского (Г. Вейль (1885-1955), Г. Минковский (1864-1909)) о том, что множество является многогранником тогда и только тогда, когда множество является ограниченным полиэдром, структура множества условий (2)-(3) стала геометрически просто изучаемой.

Заметим, что в 1957 г. С. Зуховицкому удалось доказать, что задача (8) может быть интерпретирована как задача линейного программирования.

6. Анализ сложности реализации симплекс-метода.

Уже после создания симплекс-метода были предприняты попытки теоретического анализа его эффективности.

Несмотря на обнадеживающую экспериментальную оценку С. Гасса (2), после получения результата В. Кли и Дж. Минти [16] в 1972 г., которые построили пример, когда оценка сложности симплекс-метода является экспоненциальной от размеров исходных задачи, стало ясно, что некоторый скептицизм относительно идеи направленного перебора вершин был оправдан. Действительно, много позже в 1975 г. Х. Бартельсом [12, 17] были получены достижимые оценки числа вершин h для выпуклых многогранников (2)-(3):



254 Глава 4. История и философия математики и математического образования и для случая, когда в условиях (2) вместо неравенств фигурируют равенства:

Заметим, что h = n m + 1 в соотношениях (9) выполняется в случае, когда в число базисных переменных при определении вершины всегда входят одни и те же m 1 переменные и только одна переменная может замещаться внебазисными (симплекс-таблицы всех допустимых базисов невырожденной матрицы А={aij }mn 1-подобные) [ 13].

Результат Кли и Минти, упомянутый выше [16] показал, что возможен пример, когда h 2n 1, причем вершин входит в набор вершин, перебираемых симплекс-методом. Таким образом, симплекс-метод, реализуемый на многогранниках условий с достаточно большим числом вершин не является полиномиальным по сложности реализации.

В 1980 г. Л. Хачиян предложил для решения задачи линейного программирования иной метод (метод эллипсов), который является полиноминальным по сложности [18, 15]. Согласно результатам Л. Хачияна для реализации метода требуется O(n5 log(nT) арифметических операций под числами двоичной длины O(n log(nT), всего O(n5 log2 (nT) битовых операций.

Однако, вычислительные эксперименты с методами эллипсов оказались мало успешными.

Таким образом, идея направленного перебора вершин многогранника условий (2)-(3) (то есть реализация симплекс-метода) до настоящего времени является наиболее перспективной.

1. Канторович, В.Л. Математические методы организации и планирования производства [Текст]/ Л.В. Канторович. – Л.: ЛГУ, 1939.

2. Данциг, Дж. Линейное программирование, его применения и обобщения [Текст]/ Дж. Данциг.

– М.: Прогресс, 1966.

3. Тихомиров, В.М. Об истории выпуклой оптимизации [Текст]/ В.М. Тихомиров// Историкоматематические исследования. – 1995. – Секция 2. – Вып.1 (36). – №1. – 191 с. – C. 105-114.

4. Гасс, С.И. Линейное программирование (методы и приложения) [Текст]/ С.И. Гасс. – М.:

Физматгиз, 1961.

5. Схрейвер, А. Теория линейного программирования и целочисленного программирования [Текст]: в 2 т./ А. Схрейвер. – М.: Мир, 1991. – 703 с.

6. Полуправильные многогранники [Текст]// Математическая энциклопедия. – М.: АН СССР, 1984. – T.4. – 311 с.

7. Березкина, Э.И. Математика древнего Китая [Текст]/ Э.И. Березкина. – М.: Наука, 1980. – 8. Архимед. Сочинения [Текст]/ Архимед; пер. Н.Н. Веселовского и Б.А. Резенфельда. – М.:

ГИФМА, 1962. – C. 383-386.

9. Делоне, Б.Н. Эйлер как геометр [Текст]/ Б.Н. Делоне// В сб. Леонардо Эйлер (1707-1783) (к 250-летию со дня рождения). – М.: АН СССР, 1985. – 668 с. – C. 133-181.

10. Александров, А.Д. Выпуклые Архимеда многогранники [Текст]/ А.Д. Александров. – М-Л., 11. Люстерник, Л.А. Выпуклые фигуры и многогранники [Текст]/ Л.А. Люстреник. – М., 1956.

12. Ковалев, М.М. Дискретная оптимизация [Текст]/ М.М. Ковалев. – Минск: БГУ, 1977. – 191 с.

13. Емеличев, В.А. Многогранники, графы, оптимизация.[Текст]/ В.А. Емеличев [и др.] – М.:

Наука, 1981. – 344 с.

14. Рыбников, К.К. К истории развития теории решения систем линейных неравенств [Текст]/ К.К. Рыбников, Т.А. Ласковая// В сб. Трудов Международных научной конференции “Современная математика и математические образование, проблемы истории и философии математики”. – Тамбов: Изд-во Р.Першина, 2008. – 324 с. – C. 155-157.

Малых А.Е., Янкович Е.И. Формирование и развитие теории конструкций блочно-схемного типа 15. Ласковая, Т.А. История развития методов анализа полиэдральных математических моделей [Текст]/ Т.А. Ласковая, К.К. Рыбников, О.К. Чернобровина// В сб. Трудов Х международных Колмогоровских чтений. – Ярославль: Изд-во ЯГПУ, 2012. – 305 с. – C. 187-191.

16. Klee, V. Minty G. How good is the simplex algoritm? [Текст]/ V. Klee. – Inequalitionen III, Academic Press, 1972.

17. Bartels, H. Apriori informationen zur Linearen Programmierung. Uber Ecken und Hyperschen auf Polyhedern [Текст]/ H. Barters. – Anton Hain, 1975.

18. Хачиян, Л.Г. Полиноминальные алгоритмы в линейном программировании [Текст]/ Л.Г. Хачиян. – ХВМ и ФМ, 1980. – №1.

Формирование и развитие теории конструкций блочно-схемного типа А.Е. Малых, Е.И. Янкович В книге известных ученых М. Айгнера и Г. Циглера “Лучшие доказательства” со времен Евклида до наших дней” в гл. 27 “Дополнения до полных латинских квадратов” указано: “Одним из старейших комбинаторных объектов, изучение которых началось, по-видимому, еще в античные времена, являются латинские квадраты [1, с. 190]. Их впервые стал изучать Л. Эйлер, опубликовав в 1782 году объемный мемуар [2]. Истоки же более общих структур – магических квадратов – уходят к древнему Востоку.

Цель сообщения показать процесс формирования и развития теории магических квадратов (ниже м.к.).

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



Pages:     | 1 |   ...   | 63 | 64 || 66 | 67 |   ...   | 93 |
 



Похожие работы:

«IT'S ME О LORD DODD, MEAD AND COMPANY NEW YORK 1955 Перевод И. КУЛАКОВСКОЙ u К. ЧУГУНОВА Редактор H. БАННИКОВ Вступительная статья и подбор произведений Рокуэлла Кента А. ЧЕГОДАЕВА Заставки, рисунки на титуле и шмуцтитулах выполнены Року¬ эллом К е н т о м для американского издания 1955 года. В на­ стоящем издании инициальные буквицы в части заставок изменены. О РОКУЭЛЛЕ КЕНТЕ И ЕГО АВТОБИОГРАФИИ Рокуэлл Кент написал и издал свою большую автобиографию в 1955 году. Тогда ему было семьдесят три...»

«Программа вступительных испытаний по учебному предмету География для лиц, имеющих общее среднее образование, для получения высшего образования, 2014 год ПОЯСНИТЕЛЬНАЯ ЗАПИСКА На вступительных испытаниях по географии абитуриенты должны показать знания основных теоретических положений географии как одной из важнейших научных дисциплин. Абитуриенты должны владеть фактологическим материалом, понимать основные географические термины и понятия, уметь обобщать и анализировать, а также применять...»

«ГОСУДАРСТВЕННОЕ И МУНИЦИПАЛЬНОЕ УПРАВЛЕНИЕ _ СЛОВАРЬ ТЕРМИНОВ Бишкек УДК ББК КРекомендовано к изданию Ученым советом Академии управления при Президенте Кыргызской Республики Под общей редакцией: Ректора-Президента Академии управления при Президенте Кыргызской Республики, профессора Акматалиева А.А. Авторы-составители: Шадыбеков Куванычбек Баймуратович; Исраилов Азысбек Асымканович Рецензенты: Арабаев Ч.И. -член-корреспондент НАН КР, заслуженный юрист КР, доктор юридических наук, профессор;...»

«У. Основаніе кафедры славяновдгьнія въ Москв. Приготовленіе О. М. Бодянскаго къ занятію этой кафедры. Критическая статья О. М. Бодянскаго о сборнж еловацктъ псет Яна Коллара. Переводъ Славянскихъ Древностей Ш афарика. М аги­ стерская диссертація О. М. Бодянскаго О народной поэзіи славянскихъ племенъ. Критическая статья О. М. Бодянскаго объ изданной. Булгаринымъ книггь Россія въ историческомъ, статистическомъ, іеографическомъ и литературномъ отношеніяхг. Изъ воспоминаній К. С. Аксакова мы уже...»

«К ИСТОРИИ КОНВЕРСИКИ. К ИСТОРИЗМАМ В редколлегию ж. Энергетика Уважаемые коллеги! Предлагаемые материалы – труд нескольких 10-летий. Предназначены специалистам. Посвящены некоторым острым проблемам в КОНВЕРСИКЕ и некоторым моим изобретениям. На первый взгляд всё в них непривычно. Необычно. Во всех отношениях. И для любых оценщиков. Поэтому материалы беззащитны. Легко уязвимы. Утопляемы. Даже без камешка. А не только с тяжёлым булыжником регалиеносного рецензента. По этой же причине они долго...»

«Содержание Введение..4 Глава 1. Теоретико-методологические подходы к анализу процесса функционирования особо охраняемых природных территорий в Российской Федерации..7 Анализ нормативно-правовой базы обеспечения функционирования 1.1. особо охраняемых природных территорий в Российской Федерации..7 1.2. Общая характеристика правового режима особо охраняемых природных территорий..14 1.3. Система национальных парков Российской Федерации.17 1.4. Функциональное зонирование национальных парков.19 1.5....»

«Аннотация Продолжаются приключения Джеттеро Хеллера, стремящегося спасти погибающую Землю. Но на его пути стоят агенты коварного волтарианца Солтена Гриса и Делберт Джон Роксентер, самый могущественный и безумный человек на Земле. Рон Л. Хаббард Миссия: Земля Во мраке бытия перевод М. Брухнова, Н. Колышкиной ПРЕДУВЕДОМЛЕНИЕ ВОЛТАРИАНСКОГО ЦЕНЗОРА Лорд Инвей, Историограф Его Величества, Председатель Комитета Цензуры Двора Его Величества Конфедерации Волтар Учитывая то обстоятельство, что...»

«От редакции В этом году Россия празднует великую дату своей истории – 700-летие рождения Великого Игумена земли российской преподобного Сергия Радонежского. Предлагаем вниманию читателей фрагмент из статьи нашего безвременно ушедшего коллеги религиозного философа и культуролога А.Г. Шубакова Русская идея от преподобного Сергия (2003). Высокий уровень религиознофилософского осмысления роли и места Сергия Радонежского в русской истории и культуре, значимости великого подвига собирателя русских...»

«ПОДГОТОВКА СПОРТСМЕНА – ПАРАШЮТИСТА МОСКВА ОРДЕНА ЗНАКА ПОЧЕТА ИЗДАТЕЛЬСТВО ДОСААФ СССР 1979 В книге Подготовка спортсмена-парашютиста рассказывается об истории развития парашютизма, устройстве и правилах укладки находящихся в эксплуатации парашютов УТ-15, Д-1-5-У, З-5. Рассматриваются теоретические вопросы прыжка с парашютом, наземной подготовки парашютиста, практического выполнения прыжков с парашютом в пределах Программ по парашютной и парашютно-спасательной подготовке авиации ДОСААФ (М.,...»

«R eichert aus B ingen D eutschland - B ayern 2011 Фамильная книга семьи Райхерт Генрих Райхерт Райхерт из Бинген Германия – Бавария – Траунройт 2011 Предисловие На пороге своего пятидесятилетия, мне удалось закончить работу над фамильной книгой рода Райхерт. Три года понадобилось мне, чтобы раскрыть тайну историю моих предков. Если раньше люди занимающиеся генеалогией, тратили десятилетия на получение результатов, то сейчас с помощью интернета такие поиски, можно сделать намного быстрее....»






 
© 2013 www.knigi.konflib.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.