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

В то же время в конце 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]. Истоки же более общих структур – магических квадратов – уходят к древнему Востоку.

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

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