Теория оптимального использования ресурсов нобелевская премия. Теория распределения ресурсов
Министерство образования и науки, молодежи и спорта Украины
Севастопольский национальный технический университет
Факультет Экономики и менеджмента
На тему: Л.В. Канторович: разработка теории линейного программирования
по дисциплине «История экономики и экономической мысли»
Выполнила: ст. гр. МО-21
Ковалева С.Н.
Проверил: преподаватель
Керезь Е.С.
Севастополь 2009
1.2 Вклад в науку
1.3 Научные работы
Заключение
Введение
В этом реферате я напишу о деятельности Леонида Витальевича Канторовича, выдающегося ученого ХХ века, о его борьбе за признание своих экономико-математических теорий, о начальном этапе истории линейного программирования, о зарождении новой области математической деятельности, связанной с экономическими приложениями, называемой у нас то исследованием операций, то математической экономикой, то экономической кибернетикой и т. п., о ее месте и связях с современным математическим ландшафтом.
1. Леонид Витальевич Канторович
1.1 Биография Л.В. Канторовича
Леонид Витальевич Канторович (1912--1986) родился в Санкт-Петербурге в семье врача. Его выдающиеся способности проявились рано -- в 14 лет он поступил в Ленинградский государственный университет. Закончив ЛГУ за 4 года, он поступил в аспирантуру. В 1932 г. он становится доцентом, а в 1935 г. -- профессором ЛГУ. В 1935 г. ему присвоено звание доктора физико-математических наук без защиты диссертации. В 1958 г. он избран членом-корреспондентом АН СССР по экономике, а в 1964 г. -- академиком. За разработку метода линейного программирования и экономических моделей удостоен в 1965 году вместе с академиком В. С. Немчиновым и профессором В. В. Новожиловым Ленинской премии. С 1971 года работал в Москве, в институте управления народным хозяйством Государственного комитета Совета Министров СССР по науке и технике. 1975 год -Нобелевская премия по экономике (совместно с Т. Купмансом «за вклад в теорию оптимального распределения ресурсов»). С 1976 работал во ВНИИСИ ГКНТ и АН СССР, ныне Институт системного анализа РАН.
Награждён 2 орденами Ленина (1967, 1982), 3 орденами Трудового Красного Знамени (1949, 1953, 1975), орденом Отечественной войны 1-й степени (1985), орденом «Знак Почёта» (1944). Почётный доктор многих университетов мира.
1.2 Вклад в науку
Научное наследие Л. В. Канторовича огромно. Его исследования в области функционального анализа, вычислительной математики, теории экстремальных задач, дескриптивной теории функций оказали фундаментальное влияние на становление и развитие названных дисциплин. Л. В. Канторович по праву входит в число основоположников современного экономико-математического направления.
Л. В. Канторович -- автор более трехсот научных работ, которые при подготовке аннотированной библиографии его сочинений он сам предложил распределить по следующим девяти разделам: дескриптивная теория функций и теория множеств, конструктивная теория функций, приближенные методы анализа, функциональный анализ, функциональный анализ и прикладная математика, линейное программирование, вычислительная техника и программирование, оптимальное планирование и оптимальные цены, экономические проблемы плановой экономики.
Столь впечатляющее многообразие направлений исследований объединяется не только личностью Л. В. Канторовича, но и его методическими установками. Он всегда подчеркивал внутреннее единство науки, взаимопроникновение идей и методов, необходимых для решения самых разнообразных теоретических и прикладных проблем математики и экономики. Еще одной характерной чертой его творчества является тесная взаимосвязь с наиболее трудными проблемами и самыми перспективными идеями математики и экономики того времени.
Осветить творчество Леонида Витальевича в кратко невозможно. Сам он выделял из сделанного в науке две вещи: линейное программирование и K-пространства.
1.3 Научные работы Л.В. Канторовича
Научные работы:
Первые научные результаты получены в дескриптивной теории функций и множеств и, в частности, по проективным множествам.
В функциональном анализе ввёл и изучил класс полуупорядоченных пространств (К-пространств). Выдвинул эвристический принцип, состоящий в том, что элементы К-пространств суть обобщённые числа. Этот принцип был обоснован в 1970-е годы в рамках математической логики. Булевозначный анализ установил, что пространства Канторовича представляют новые нестандартные модели вещественной прямой.
Впервые применил функциональный анализ к вычислительной математике.
Развил общую теорию приближённых методов, построил эффективные методы решения операторных уравнений (в том числе метод наискорейшего спуска и метод Ньютона для таких уравнений).
В 1939-40 положил начало линейному программированию и его обобщениям.
Развил идею оптимальности в экономике. Установил взаимозависимость оптимальных цен и оптимальных производственных и управленческих решений. Каждое оптимальное решение взаимосвязано с оптимальной системой цен.
Канторович -- представитель петербургской математической школы П. Л. Чебышёва, ученик Г. М. Фихтенгольца и В. И. Смирнова. Канторович разделял и развивал взгляды П. Л. Чебышева на математику как на единую дисциплину, все разделы которой взаимосвязаны, взаимозависимы и играют особую роль в развитии науки, техники, технологии и производства. Канторович выдвигал тезис взаимопроникновения математики и экономики и стремился к синтезу гуманитарных и точных технологий знания. Творчество Канторовича стало образцом научного служения, базирующегося на универсализации математического мышления.
канторович математика вычислительный дескриптивный
2. Зарождение линейного программирования
Линейное программирование изучают десятки тысяч людей во всем мире. Под этим термином скрывается колоссальный раздел науки, посвященный линейным оптимизационным моделям. Иначе говоря, линейное программирование -- это наука о теоретическом и численном анализе и решении задач, в которых требуется найти оптимальное значение, т. е. максимум или минимум, некоторой системы показателей в процессе, поведение и состояние которого описывается той или иной системой линейных неравенств.
Одним из наиболее значительных и ярких достижений в области экономико-математических исследований было открытие Леонидом Витальевичем Канторовичем (1912--1986) метода линейного программирования. Линейное программирование -- решение линейных уравнений (уравнений первой степени) посредством составления программ и применения различных методов их последовательного решения, существенно облегчающих расчеты и достижение искомых результатов. Линейное программирование изучают десятки тысяч людей во всем мире. Под этим термином скрывается колоссальный раздел науки, посвященный линейным оптимизационным моделям. Иначе говоря, линейное программирование -- это наука о теоретическом и численном анализе и решении задач, в которых требуется найти оптимальное значение, т. е. максимум или минимум, некоторой системы показателей в процессе, поведение и состояние которого описывается той или иной системой линейных неравенств.
Сам термин «линейное программирование» был предложен в 1951 году американским экономистом Т. Купмансом. За разработку метода линейного программирования или, как сказано в дипломе Шведской академии наук, за «вклад в теорию оптимального распределения ресурсов Л.В.Канторович был удостоен Нобелевской премии по экономике (1975). Премия была присуждена ему совместно с американским экономистом Тьяллингом Чарльзом Купмансом, который несколько позже, независимо от Канторовича, предложил сходную методологию.
Разработка линейного программирования началась с поиска решения практической задачи. К Канторовичу обратились инженеры фанерного треста с просьбой найти эффективный способ распределения ресурсов, обеспечивающий наиболее высокую производительность оборудования. Работники предприятия ломали голову над тем, как при пяти станках и восьми видах сырья обеспечить оптимальный вариант выпуска фанеры. Иными словами, нужно было найти решение конкретной технико-экономической задачи с целевой функцией («функционалом») максимизировать выпуск готовой продукции.
Заслуга Канторовича состоит в том, что он предложил математический метод выбора оптимального варианта. Решая частную задачу наиболее рациональной загрузки оборудования, ученый разработал метод, получивший название метода линейного программирования. По сути дела, он открыл новый раздел математики, получивший широкое распространение в экономической практике, способствовавший развитию и использованию электронно-вычислительной техники.
С оптимальным планом любой линейной программы автоматически связаны оптимальные цены или «объективно обусловленные оценки». Последнее громоздкое словосочетание Леонид Витальевич выбрал из тактических соображений для повышения «критикоустойчивости» термина. Взаимозависимость оптимальных решений и оптимальных цен -- такова краткая суть экономического открытия Л. В. Канторовича.
В задаче по оптимизации выпуска фанеры Канторович представил переменную, которую следовало максимизировать в виде суммы стоимостей продукции, производимой всеми станками. Ограничители были представлены в форме уравнений, устанавливающих соотношения между всеми затрачиваемыми в производстве факторами (древесиной, клеем, электроэнергией, рабочим временем) и количеством выпускаемой продукции (фанеры) на каждом из станков.
Для показателей факторов производства были введены коэффициенты, названные разрешающими множителями, или мультипликаторами. С их помощью разрешается поставленная задача. Если известны значения разрешающих множителей, то искомые величины, в частности, оптимальный объем выпускаемой продукции, могут быть сравнительно легко найдены.
Канторович обосновал экономический смысл предложенных им коэффициентов (разрешающих множителей). Они представляют собой не что иное, как предельные стоимости ограничивающих факторов. Иначе говоря, это объективно значимые цены каждого из факторов производства применительно к условиям конкурентного рынка.
Для решения задачи на оптимум Канторович использовал метод последовательных приближений, метод последовательного сопоставления вариантов с выбором наилучшего в соответствии с условиями задачи.
Допустим, требуется решить транспортную задачу, обосновать наиболее рациональное распределение грузопотоков. Для примера, всего нужно перевести 180т груза из трех источников к трем потребителям, общий спрос которых также равен 180 т. Сложность в том, что груз распределен неравномерно: у одного поставщика имеется 50 т, у другого -- 60 т, у третьего -- 80 т.
Также неравнозначен спрос потребителей: он составляет соответственно 40, 85 и 55 т. Неодинаковы и расстояния -- плечи перевозки грузов -- от 1 до 6 км. Задача заключается в том, чтобы составить такой план перевозок, который отвечал бы требованию минимизации грузооборота (минимальному количеству тонно-километров).
В повседневной практике менеджеры могут заняться монотонной работой по длительному перебору возможных вариантов. Постепенно они смогут «пройти» от плана перевозок, скажем, в 750 т/км к плану в 655 т/км. Поиск потребует массу усилий, значительного количества расчетов. Главное же -- трудно установить, какой из предлагаемых вариантов является оптимальным. Допустим, найден вариант плана с грузооборотом в 575 т/км.
Но остается неизвестным, нет ли еще одного или нескольких более выгодных вариантов плана, требующих меньших затрат.
Задача становится совсем неразрешимой, если перейти от сравнительно простой схемы к составлению варианта перевозок одного или нескольких продуктов (угля, цемента, стройматериалов) в масштабе региона или страны. Даже в случае укрупнения, агрегирования исходных показателей расчеты и сопоставления вариантов потребуют проведения такого количества операций, для осуществления которых придется привлечь чуть ли не все население Украины.
Метод линейного программирования позволяет найти оптимальное решение. Линейным оно называется потому, что основывается на решении линейных уравнений. Неизвестные в них только первой степени; ни одно неизвестное не перемножается на другое неизвестное. Такие уравнения отражают зависимости, которые могут быть изображены на графике прямыми линиями.
Несколько иной целевой критерий в задаче о диете (кормовом рационе). Задача сводится к поиску оптимального рациона для кормления скотины или птицы. При постоянном изменении рыночных цен на корма фермеры подбирают оптимальный рацион при минимуме затрат, производя соответствующие расчеты на компьютере.
Впервые работа, в которой излагалось существо предложенного Канторовичем метода, была опубликована в 1939 г. под названием «Математические методы организации планирования производства». Продолжая исследования, ученый разрабатывает общую теорию рационального использования ресурсов.
В период Великой Отечественной войны, будучи профессором Военно-морской инженерной академии в блокадном Ленинграде, Канторович, опираясь на метод линейного программирования, обосновывает оптимальное размещение производственных и потребительских факторов. В 1942 г. он подготовил книгу «Экономический расчет наиболее целесообразного использования ресурсов», которая в тот период, к сожалению, не была опубликована.
Позже издается одна из наиболее крупных его работ «Экономический расчет наилучшего использования ресурсов» (1959). В этой книге, как отмечали члены Научного совета по применению математики в научных исследованиях и планировании, представлен углубленный анализ идей линейного программирования, разработанного автором ранее, и вместе с тем впервые ставится проблема разработки оптимального плана всего народного хозяйства как математической модели. Несомненной заслугой Канторовича является выявление двойственных оценок в задачах линейного программирования. Нельзя одно временно минимизировать затраты и максимизировать результаты. Одно противоречит другому. Вместе с тем оба этих подхода взаимосвязаны. Если, скажем, найдена оптимальная схема перевозок, то ей соответствует определенная система цен. Если найдены оптимальные значения цен, то сравнительно нетрудно получить схему перевозок, отвечающую требованию оптимальности.
Для любой задачи линейного программирования существует сопряженная ей, или двойственная задача. Если прямая задача заключается в минимизации целевой функции, то двойственная -- в максимизации.
Двойственные оценки дают принципиальную возможность соизмерять не только ценовые, затратные показатели, но и полезности. При этом двойственные, взаимосвязанные оценки соответствуют конкретным условиям. Если изменяются условия, меняются оценки. В известной мере поиск оптимума -- это определение общественно необходимых затрат, учитывающих, с одной стороны, трудовые, стоимостные затраты, а с другой-общественные потребности, полезности продукта для потребителей.
При непосредственном участии Канторовича и его ближайших коллег - В.В. Новожилова (автора идеи продуктово-трудового баланса) и В.С. Немчинова (обосновавшего глобальный критерий функционирования экономики) формировалась отечественная экономико-математическая школа.
Заключение
На первый взгляд, теории Л. В. Канторовича были, как он сам говорил приспособлены к плановой экономике, и т.д. Но это лишь внешняя сторона дела. Главное - учет скрытых параметров (рента), единый подход к ограничениям (труд - всего лишь одно из них) и все, что отсюда вытекает - делают его экономические приложения универсальными и необходимыми сейчас. Вообще, главный итог великого эксперимента Канторовича в том, что он подошел к экономическим проблемам вооруженный самыми современными для тех лет математическими средствами, и творчески применял их. Это не значит, что его выводы будут полностью работать и сегодня, но это, безусловно, значит, и в этом отношении Л.В. Канторович был, возможно, первым, что талант математика может в корне переустроить и преобразовать экономическую мысль.
Список использованных источников
1. История экономических учений: Учебное пособие / Под ред. А.Г. Худокормова. - М.: Изд-во МГУ, 1994. - Ч. II, гл. 30.
2. Канторович Л.В. Экономический расчет наилучшего использования ресурсов. - М.: Изд-во АН СССР, 1959.
3. Капустин В.Ф., Шабалин Г.В. Л.В. Канторович и экономико-математические исследования: итоги, проблемы, перспективы // Вестник Санкт-Петербургского университета. Сер. 5. Экономика. 1996. Вып. 2.
4. Пезенти А. Очерки политической экономии капитализма. В 2 т. - М.: Прогресс, 1976. Т. II , гл. 14.
5. Шаталин С.С. Функционирование экономики развитого социализма. - М.: Изд-во МГУ, 1982.
6. Шухов Н.С. Ценность и стоимость. - М.: Изд-во стандартов, 1994. - Ч. 2, вып. 1, гл. 8.
Подобные документы
Понятие экономической теории, предмет ее исследования, истоки возникновения и современные аспекты развития. Взаимосвязь реальной экономики и экономической теории. Кризис экономической науки. Влияние экономической теории на современную экономику России.
курсовая работа , добавлен 13.02.2008
История развития российской экономики в именах людей, внесших значительный вклад в развитие экономической науки, первыми разработавших различные методики, теории, стратегии в различных областях экономики: Л.В. Канторович, Н.Д. Кондратьев, А.В. Чаянов.
реферат , добавлен 28.02.2011
Этапы развития экономической теории. Методология научного исследования в экономической теории. Заслуга меркантилистов как первой школы экономического анализа. Сущность трудовой теории стоимости А. Смита. Положения кейнсианской экономической теории.
презентация , добавлен 22.03.2014
Изучение экономической теории, в соответствии с которой денежная масса играет определяющую роль в стабилизации и развитии рыночной экономики. Исследование деятельности и трудов основоположников теории монетаризма. Основные положения количественной теории.
презентация , добавлен 08.11.2013
Изучение теоретических аспектов истории возникновения экономической теории. Содержание предмета, этапы становления, основные функции и методы исследования экономической теории. Изучение ее современного состояния и определение перспектив развития.
курсовая работа , добавлен 11.01.2011
Вклад античных мыслителей в развитие экономической науки. История возникновения меркантилизма, классической политической экономии, марксизма, неоклассики - направлений экономической теории. Развитие теории регулируемого капитализма и институционализма.
реферат , добавлен 18.04.2012
Два основных направления общей экономической теории: изучение стоимости и прибавочной стоимости, а также эффективности производства. Общенаучные и специальные для экономической теории методы исследования. Количественный анализ и метод научной абстракции.
доклад , добавлен 11.02.2010
Знакомство с предметами и объектами исследования современной микроэкономики. Общая характеристика методов экономического анализа микроэкономической теории. Рассмотрение уровней экономической науки. Особенности специфики микроэкономического подхода.
дипломная работа , добавлен 08.01.2015
Предмет экономической теории. Зарождение и развитие экономической теории. Экономические законы и экономические категории. Различные подходы к анализу экономической динамики. Основные функции и методы исследования экономической теории.
курсовая работа , добавлен 21.04.2006
Экономические учения меркантилизма, марксизма, кейнсианства, неолиберализма, монетаризма и анституционализма. Изучение теории рынков и кризисов М. Туган-Барановского, основы инвестиционной теории циклов М. Кондратьева. Разработка методологии планирования.
До середины ХХ в. экономисты-теоретики игнорировали математические модели исследования. Однако, несмотря на притеснения, математики продолжали работать и достигли блестящих результатов. Среди них - представители математической школы Л. Канторович и Т.-Ч. Купманс.
Канторович (Kantorovich) Леонид Витальевич (1912-1986) - советский экономист, лауреат Нобелевской премии (1975). Родился в Петербурге, учился в Ленинградском университете. В 1930 г. Л. Канторович был участником Всесоюзного математического съезда. В этом же году закончил университет, а уже через четыре года ему присвоили звание профессора. В 1930-1939 гг. работал в Ленинградском институте инженеров промышленного строительства, потом (до 1948) - заведующим кафедрой Высшего инженерно-технического училища.
В 1935 г. стал доктором физико-математических наук; до 1960 г. он - профессор Ленинградского университета. Ему принадлежат первоклассные результаты по функциональному анализу, теории функций, вычислительной математике. Широкое признание приобрели его работы по дескриптивной теории функции и теории множества, по конструктивной теории функций, приблизительным методам анализа; он заложил основы нового направления функционального анализа - теории полуупорядоченных векторных пространств, которые названы «К-пространствами». Феномен Л. Канторовича в том, что он одновременно был талантливым математиком и экономистом, который внес коррективы в понимание экономических явлений, расширил экономическое мышление, стал основоположником оригинальной экономической школы.
В 1958 г. вместе с В. Немчиновым Л. Канторович создал Лабораторию по внедрению статистических и математических методов в экономике.
Л. Канторович принимал участие в создании Сибирского отделения Академии наук СССР. Осенью 1960 г. в Ленинграде возглавил группу математиков и экономистов, которая переехала в Новосибирск и вошла в состав Института математики Сибирского отделения АН СССР как математико-экономический отдел. Одновременно работал профессором Новосибирского университета. В 1971 г., переехав в Москву, ученый возглавлял Проблемную лабораторию в Институте управления народным хозяйством Государственного комитета Совета Министров СССР по науке и технике.
Является автором работ: «Методы приблизительного решения дифференциальных уравнений в частных производных» (в соавторстве с В. Крыловым) (1963), «Функциональный анализ в полуупорядоченных пространствах» (в соавторстве с Б. Вулихом и А. Пинскером) (1949), «Функциональный анализ и прикладная математика» (1948), «Экономический расчет наилучшего использования ресурсов» (1959), «Функциональный анализ в нормированных пространствах» (в соавторстве с Г. Акиловым), «Динамическая модель оптимального планирования» (1967), «Ценообразование и технический прогресс» (1979) и др.
Л. Канторович - почетный член Международного Эконометрического общества, почетный доктор Гренобльского, Хельсинского, Йельского, Парижского, Кембриджского, Пенсильванского университетов, а также университетов в Варшаве, Глазго, Мюнхене, Ницце и имени Мартина Лютера в Халле, Статистического института в Калькутте. Награжден двумя орденами Ленина.
Важнейшим вкладом Л. Канторовича явилась теория оптимального распределения ресурсов.
Теория оптимального распределения ресурсов - теория, которая предусматривает формулирование статистической и динамической моделей текущего и перспективного планирования использования ресурсов на базе новых математических подходов в сфере системного построения экономических показателей, используемых для анализа ценообразования, эффективности капитальных вложений.
Впервые основы теории оптимального распределения ресурсов он изложил в работе «Математические методы организации и планирования производства» (1939). В ней он представил принципиально новый класс экстремальных задач с ограничениями, разработав эффективный метод их решения. Именно в это время ученый сформулировал задачу составления плана и системы цен как взаимозависимых компонентов неделимой двойственности. Ведь время невозможно одновременно минимизировать издержки и максимизировать результаты. Одновременно эти два подхода взаимосвязаны: если найдем оптимальную схему перевозок, то ей соответствует определенная система цен. Если определим оптимальные значения цен, то сравнительно легко получить схему перевозок, что соответствует требованиям оптимальности.
Основой этой теории является метод линейного программирования.
Линейное программирование - решение линейных уравнений (уравнений первой степени) путем сложения программ и внедрения разных методов их последовательного решения, что существенно облегчает расчеты и достижение результатов.
Его началом стал поиск решения практической задачи. В 1937 г. к профессору Ленинградского университета Л. Канторовичу обратились инженеры местного фанерного треста с просьбой найти эффективный способ для обеспечения наивысшей производительности труда. Для обработки 5 видов материала выделили 8 станков с определенной производительностью каждого из них по каждому виду материала.
Другими словами, нужно было решить конкретную технико-экономическую задачу с целевой функцией («функционалом») - максимизировать выпуск готовой продукции. Известными на тот момент методами это сделать было трудно, поскольку было необходимо решить почти миллиард алгебраических уравнений. Л. Канторович предложил метод линейного программирования, который стал новым разделом в математике и получил признание в экономической практике, способствовал развитию и использованию электронно-вычислительной техники.
Ученый понимал важность создания математической основы для решений типовой хозяйственной задачи. Условия задачи на оптимальность и цель могут выражаться с помощью системы линейных уравнений. Неизвестные в них только первой степени; ни одно неизвестное не умножается на другое неизвестное. Такие уравнения выражают зависимости, которые можно изобразить на графике прямыми линиями. Поскольку уравнений меньше, чем неизвестных, то задача имеет несколько вариантов решения, а найти необходимо один.
В задаче по оптимизации выпуска фанеры Л. Канторович ввел переменную, которую следует максимизировать, в виде суммы стоимостей продукции, произведенной всеми станками. Ограничения были изложены в форме уравнений, устанавливающих соотношения между всеми факторами, затрачиваемыми в производстве (деревом, клеем, электроэнергией, рабочим временем), и количеством произведенной продукции (фанеры) на каждом станке. Для показателей факторов производства были введены коэффициенты, названные «решающими множителями» (мультипликаторами). С их помощью решается поставленная задача. Если значения решающих множителей известны, то необходимые величины, в частности оптимальный объем производимой продукции, можно сравнительно легко найти.
Л. Канторович обосновал экономическую сущность предлагаемых им решающих множителей. Они, собственно, являются предельными стоимостями ограничивающих факторов. То есть это объективные цены каждого из факторов производства относительно условий конкурентного рынка. Для решения задачи на оптимальность ученый использовал метод последовательных приближений, последовательного сопоставления вариантов с выбором наилучшего в соответствии с условиями задачи.
Внедренный Л. Канторовичем термин «решающие множители» в более поздних трудах получил несколько другую интерпретацию и другую формулировку - «объективно обусловленные оценки». Эти оценки не произвольны, их величины объективно обусловлены, они задаются конкретными условиями задачи. Значения этих оценок подходят только для конкретной задачи и, в отличие от цен, задаются не извне, а определяются самим предприятием для внутреннего пользования. Ученый предлагал рассчитать их в разработке планов; на эти показатели могут опираться предприятия при расчете затрат и объемов производства продукции. Объективно обусловленные оценки корректируются в зависимости от соотношения спроса и объемов производства. Внедренные
в практику планирования и управления такие расчеты должны оптимизировать использование ресурсов.
Задачи линейного программирования были известны еще в конце ХVIII в. Однако начали решать их только после публикаций работ Л. Канторовича. В США исследования по линейному программированию начались только в конце 40-х годов ХХ в. Транспортная задача Хичкока и симплекс-метод Данцига, которые близки по характеру к методу решения задач линейного программирования Канторовича, были разработаны на десятилетие позднее.
На оригинальный подход Л. Канторовича до 50-х годов почти не реагировали. Обобщив свои исследования, он расширил сферу анализа.
В работе «Экономический расчет наилучшего использования ресурсов» и в следующих работах он внедрил свой метод линейного программирования для исследования широкого круга проблем планирования, в том числе и на национальном уровне.
Несколько позднее, но независимо от Л. Канторовича подобную методологию предложил Т.-Ч. Купманс.
Купманс (Koopmans) Тъяллинг-Чарльз (1910-1985) - американский экономист, лауреат Нобелевской премии (1975). Родился в Гравеланде (Нидерланды). Получил образование в Утрехтском университете. Увлекался сначала математикой и физикой, работал физиком, а под впечатлением от Великой депрессии начал заниматься экономикой.
С 1934 г. в Амстердамском университете изучал проблему общего равновесия. Докторскую диссертацию на тему «Линейный регрессивный анализ экономических временных рядов» защитил в 1936 г. в Лейденском университете. Преподавал экономику и занимался научно-исследовательской деятельностью в Нидерландском экономическом институте в Роттердаме.
В 1938-1940 гг. работал экспертом Лиги Наций по вопросам денежного оборота. Эмигрировал в США. Преподавал в Нью-Йоркском, Чикагском, Гарвардском университетах. С 1955 г. - профессор экономики Йельского университета. В 1950 г. был избран президентом Международного эконометрического общества, а в 1978 г. - президентом Американской экономической ассоциации.
Т.-Ч. Купманс был редактором и соавтором одного из первых фундаментальных трудов по линейному программированию «Анализ деятельности производства и распределения» (1951).
Ученому принадлежат важные достижения в разработке теории капитала, операционного анализа. Отдельные свои труды он посвятил оптимальному распределению производственных ресурсов, статистической оценке параметров в экономико-математических моделях.
Его детище - работы по статистике и математической экономике. Наибольшее признание получили работа «Анализ деятельности производства и распределения», подготовленная группой авторов под его руководством, а также работы «Статистическое заключение в динамических моделях экономики» (1950), «Три эссе о состоянии экономической науки» (1957) и др.
Т.-Ч. Купманс - заслуженный член Американской экономической ассоциации, почетный профессор Йельского университета, ему присвоены почетные ученые степени Нидерландской школы экономики, Северо-Западного и Пенсильванского университетов, Католического университета Лувена.
В 1944-1945 гг. по поручению англо-американского объединенного совета по регулированию мореплавания Т.-Ч. Купманс разработал план торгового мореплавания, который минимизировал возможность опасного торпедирования пустых грузовых суден фашистскими подводными лодками. Целью была минимизация холостого пробега суден.
Эту тему он затронул в работе «Соотношение между грузопотоками по различным маршрутам» (1942). Ученый показал, что проблему следует рассматривать как линейную функцию максимизации в пределах многих ограничений. Ограничения представил математическими уравнениями, которые выражают отношение количества затраченных факторов производства (амортизации суден, времени, трудовых затрат) к количеству доставленных в разные пункты назначения грузов. При этом величина любых затрат не может превышать явную сумму стоимости грузов, доставленных в каждый порт. Ученый пришел к выводу, что суть принципа линейного программирования заключается в том, что в оптимальном случае и по идеальным оценкам всех ресурсов издержки и результаты будут равными.
Работая в британской торговой миссии в Вашингтоне, Т.-Ч. Купманс использовал математический инструментарий и создал метод определения оптимального распределения ресурсов между конкурирующими потребителями. По этому методу можно было, например, рассчитать издержки на доставку миллионов тонн грузов, которые перевозятся тысячами суден морскими путями в сотни портов. Метод Т.-Ч. Купманса, который был назван «анализом деятельности фирмы», вошел в общую методологию линейного программирования.
В 1947 г. ученый озвучил свои выводы на международной конференции по статистике. В то время он активно разрабатывал и популяризировал методы линейного программирования. При его содействии в 1949 г. в Чикаго была проведена первая специальная конференция по линейному программированию.
В 1950 г. Т.-Ч. Купманс вместе со своими сторонниками завершили формулирование метода анализа деятельности фирмы. Модели этого типа так же, как и межотраслевые, линейные, однако у них каждый вид производственной деятельности может быть связан с выпуском нескольких товаров. К тому же существует возможность выбора между разными технологиями производства каждого вида продукции. Производственная модель типа анализа деятельности фирмы, как правило, содержит больше степеней свободы, чем обычная модель межотраслевого баланса, благодаря чему появляются естественные возможности для оптимизации. Именно поэтому анализ деятельности фирмы развивался в тесной связи с линейным программированием.
Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
Размер: px
Начинать показ со страницы:
Транскрипт
1 Выходные сведения статьи: Наследие нобелевских лауреатов по экономике: Шестакова А.А., Забродова О.С. Наследие Леонида Канторовича, Тьяллинга Купманса: теория оптимального распределения ресурсов // Наследие нобелевских лауреатов по экономике: сб. ст. III Всерос. науч.-практ. конф. молод. учен. - Самара, Наследие Леонида Канторовича, Тьяллинга Купманса: теория оптимального распределения ресурсов 2016 Шестакова Александра Александровна студент Забродова Олеся Сергеевна студент 2016 Уфимцева Людмила Ивановна доцент 2016 Безгласная Елена Алексеевна доцент Самарский государственный экономический университет Описание модели Канторовича и модели "анализа деятельности фирмы" Купманса, практическое применение линейного программирования, рассмотрен метод оптимизации распределения ресурсов Канторовича на примере аналогичной задачи, с помощью графического, математического способов и симплекс-метода. Ключевые слова: Л.В. Канторович, Т. Ч. Купманс, нобелевская премия, оптимизация распределения ресурсов, линейное программирование. Heritage Leonid Kantorovich, Tjalling Koopmans: theory of optimal allocation of resources 2016 Shestakova Aleksandra Aleksandrovna student Zabrodova Olesya Sergeevna student 2016 Ufimtseva Lyudmila Ivanovna 2016 Bezglasnaya Elena Alekseevna Samara State University of Economics Description of the Kantorovich model and the Kupmans model of firm activity analysis, practical use of linear programming, a method of optimizing the resources allocation by Kantorovich is considered on an example of a similar problem, using graphical, mathematical method and simplex algorithm.
2 Keywords: L.V. Kantorovich, Tjalling Koopmans, Nobel prize, optimization of distribution a resources, linear programming. Вплоть до ХХ в. ученые-экономисты не уделяли должного внимания математическим методам как способам решения поставленных задач на макро и микро уровнях хозяйственной деятельности. Тем не менее, между этими науками наблюдается тесная связь, которую удалось продемонстрировать выдающимся ученым. Одними из них выступают Л.В. Канторович и Т.Ч. Купманс, советский и американский экономисты-математики, которые по результатам своей деятельности получили Нобелевскую премию в 1975 г. "за вклад в теорию оптимального распределения ресурсов". Модель Л.В. Канторовича, СССР. Л.В. Канторович стал одним из основателей важнейшего и наиболее часто применяемого метода оптимизации - линейного программирования. В 1937 г. перед Л. Канторовичем была поставлена задача выбора наилучшей производственной программы загрузки лущильных станков для фанерного треста. При этом известно количество станков, которые можно использовать для производства определенных изделий, а также количество деталей, из которых состоит изделие. Технические коэффициенты показывают, какое количество штук каждой детали станок может произвести в день. Другими словами, Канторовичу нужно было решить конкретную технико-экономическую задачу с целевой функцией максимизировать выпуск готовой продукции. Таким образом, ученый столкнулся с типичным представителем целого нового класса задач, к которым приводят вопросы нахождения наилучшего производственного плана. Свою идею, что впоследствии стало основой теории оптимального распределения ресурсов и ознаменовало открытие линейного программирования, Канторович изложил в работе «Математические методы организации и планирования производства» (1939). В ней профессор впервые продемонстрировал, что разнообразные производственные проблемы можно сформулировать как задачи оптимизации определенного вида и предложил общий подход к их решению, методом итерации. Для решения задачи Канторович ввел переменную, которую следует максимизировать, в виде суммы стоимостей продукции, произведенной всеми станками. Ограничения были изложены в форме уравнений, устанавливающих соотношения между всеми факторами, затрачиваемыми в производстве, и количеством произведенной продукции на каждом станке. Для показателей факторов производства были введены коэффициенты, названные «решающими множителями» (в дальнейшем объективно обусловленные оценки). С их помощью решается поставленная задача. Объективно обусловленные оценки являются ключевым моментом в методе Канторовича. Их связывают с интерпретацией, аналогичной множителям Лагранжа в классических задачах определения экстремума, и экономическая сущность заключается в том, что они являются предельными стоимостями ограничивающих факторов. То есть это объективные цены каждого из факторов производства относительно условий конкурентного рынка. Также эти оценки не произвольны, их величины объективно обусловлены, они задаются конкретными условиями задачи. Таким образом, было совершено открытие, которое позволяет оптимизировать производство, появляется возможность децентрализованным образом руководить деятельностью производственных секторов, технологическая структура которых может быть описана посредством линейных зависимостей (уравнений и неравенств). "Анализ деятельности" Т.Ч. Купманса, США. Несколько позже Канторовича, Купманс в своей работе «Соотношение между грузопотоками по различным маршрутам» (1942) рассмотрел проблему разработки плана торгово-
3 Наследие нобелевских лауреатов по экономике: го мореплавания с минимальной возможностью торпедирования суден подводными лодками. Он пришел к умозаключению, что задачу следует рассматривать как линейную функцию максимизации в пределах многих ограничений. Ограничения, в свою очередь, ученый представил математическими уравнениями, которые выражают отношение количества затраченных факторов производства (амортизации суден, времени, трудовых затрат) к количеству доставленных в разные пункты назначения грузов. При этом общая величина затрат не может превышать сумму стоимости доставленных в каждый порт грузов. Купманс сделал вывод, что суть принципа линейного программирования заключается в совпадении по идеальным оценкам ресурсов издержек и результатов производства в оптимальном случае. Метод Купманса, который был назван «анализом деятельности фирмы», вошел в общую методологию линейного программирования. Модели этого типа отличаются от линейных тем, что в них производство может быть связано с выпуском нескольких товаров. Также возможен выбор между разными технологиями изготовления каждого вида продукции. Важным является тот факт, что применение модели возможно как в экономической теории, так и в практике управления. Это связано с определением коэффициента, равного цене затрат в условиях идеального рынка, с помощью полученных уравнений. Модель Купманса представляет большую ценность не только для центральных планирующих органов, но и для любых децентрализованных процессов производства, где наблюдается необходимость действовать в условиях наличия ограничений по ресурсам. Центральные органы могут задавать условия цен на затраты, в свою очередь оставляя выбор оптимальных путей местным руководителям. Внутри фирмы метод "анализа деятельности" позволяет наиболее эффективно организовать работы. Действенность метода линейного программирования Чтобы оценить валидность метода, мы рассмотрели экономическую задачу, аналогичную поставленной перед Канторовичем. Предположим, некоторое предприятие выпускает пиломатериалы и фанеру. Для их изготовления используются еловые и пихтовые лесоматериалы на единицу продукции. Таблица 1 - Доход от реализации и запасы сырья лесоматериалы расход лесоматериалов на единицу продукции Запасы сырья пиломатериалы фанера еловые пихтовые количество продукции доход от единицы продукции Составим план выпуска пиломатериалов и фанеры, который приносит наибольшую прибыль: Пусть план выпуска - пиломатериалов, - фанеры. Тогда прибыль составит: Z(x)= max. Ограничения составим по запасам сырья: ;
4 Рассмотрим задачу графически: D-область решений системы ограничений; ; линии уровня Z(x)=c проходят перпендикулярно вектору с и на этих прямых значение прибыли равное. При перемещении линии уровня по направлению вектора с значение прибыли увеличивается и наибольшее значение будет в точке М. Точка М - пересечение прямых Итак, прибыль максимальна при производстве 20м пиломатериала и 1200м фанеры. При рассмотрении двух продуктов метод прост и легко может быть представлен в виде графика. Но он применим и для решения задач более высоких порядков, подразумевающих рассмотрение трех или более продуктов. В этих случаях мы не можем использовать графическое решение, но Канторович разработал алгоритмическое, при помощи которого решения могут быть получены путем последовательного приближения - симплекс-метод. Подобные задачи можно решить симплекс-методом с помощью компьютерных программ. Решение задачи с помощью редактора электронных таблиц Microsoft Office Excel: Таким образом, у нас получилось найти оптимальное решение с помощью линейного программирования. Полученные значения данное предприятие вполне может установить в план для организации производственной деятельности по выпуску фанеры и пиломатериалов. Из всего вышесказанного следует, что благодаря деятельности Канторовича и Купманса, не только математика, но и экономика приобрела новый, достаточно универсальный, удобный и необходимый раздел - линейное программирование и, таким образом, была заложена основа методов оптимизации. Изобретение линейного программирования помогает в решении главной проблемы экономики - оптимального распределения ограниченных ресурсов. Приведенные модели с помощью линейного программирования обеспечивают выбор из нескольких решений такого варианта, который максимизирует выпуск продукции, причем не
5 Наследие нобелевских лауреатов по экономике: только на уровне предприятия, но и на макроэкономическом уровне. Ведь спектр применения метода широк и разнообразен - в задачах рационального использовании сырья и материалов; оптимальной организации перевозок; оптимизации размещения предприятий; эффективного планирования многих процессов производства и т.д. Также линейное программирование стало прочной основой для возникновения множества других методов, которые позволяют найти оптимум для производства любой сложности, любой системы ограничений. Список литературы 1. Нобелевские лауреаты ХХ века. Автор - Васина Л.Л., 2001 г. 2. Экономико-математические методы и модели. Задачник. Авторы: Р.И. Горбунова Р.И., Макаров С.И., Уфимцева Л.И., 2008 г. 3. Йохансен Л., "Вклад Л. В. Канторовича в экономическую науку", 1976 г. 4. Канторович Л.В., "Экономический расчет наилучшего использования ресурсов", 1959 г. 5. Довбенко М. В., Осик Ю. И., "Современные экономические теории в трудах нобелиантов", Москва, 2011 г.
АНАЛИЗ УСТОЙЧИВОСТИ КОММЕРЧЕСКОЙ ДЕЯТЕЛЬНОСТИ ПРЕДПРИЯТИЯ Дегтярёва Нина Адамовна, к.э.н., доцент Коммерческая работа - это деятельность предприятия, направленная на решение особого комплекса задач. Изучение
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА ФЕДЕРАЛЬНО ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ» (МИИТ)
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА ФЕДЕРАЛЬНО ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ (МИИТ)
Князева А., Лыкова Н.П. ГОУ ВПО «Российский государственный гуманитарный университет» Филиал в г. Самаре ПОСТАНОВКА ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ИХ РЕШЕНИЕ С ПОМОЩЬЮ MS EXCEL Временем рождения линейного
ФЕДЕРАЛЬНОЕ АГЕНСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ
Борисова М.В., Недопёкина К.И. Компьютерная реализация процедур линейного программирования // Академия педагогических идей «Новация». Серия: Студенческий научный вестник. 2019. 3 (март). АРТ 195-эл. 0,2
SWorld - 2-12 October 2012 http://www.sworld.com.ua/index.php/ru/conference/the-content-of-conferences/archives-of-individual-conferences/oct-2012 SCIENTIFIC RESEARCHES AND THEIR PRACTICAL APPLICATIO N.
Задача. Решить графически ma F Находим точки пересечения прямых определяющих неравенства. Отсюда Точка пересечения не принадлежит области. Построим область допустимых решений. Построим вектор направления
Задачи оптимизации. Кольцов С.Н 2014 www.linis.ru Задачи линейного программирования Задачи оптимального планирования, связанные с отысканием оптимума заданной целевой функции (линейной формы) при наличии
5. Методические указания по подготовке к практическим занятиям при изучении дисциплины «Методы оптимальных решений» Направление подготовки 080100.62 «Экономика» Профиль «Экономика и управление инвестициями»
Федеральное агентство по образованию НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ЭКОНОМИКИ И УПРАВЛЕНИЯ - «НИНХ» Рег. 24-0/02 Кафедра Высшей математики МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНЫХ РАБОТ
МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ПРИ ПОМОЩИ СИМПЛЕКС-МЕТОДА НА ПРИМЕРЕ ХЛЕБОПЕКАРНОГО МАГАЗИНА «ШОКОЛАДНИЦА» Кирнозова И.Р. Ставропольский государственный аграрный университет, Ставрополь, Россия MATHEMATICAL
Методы оптимальных решений Контрольная работа Задача 1. Предприятие производит продукцию двух видов (A и Б), используя при изготовлении этой продукции ресурсы трех видов (первого, второго и третьего).
Математическое программирование Каждый человек ежедневно, не всегда осознавая это, решает проблему получения наибольшего эффекта, при затрате ограниченных средств. Чтобы достичь наибольшего эффекта, имея
ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ ГОРОДА МОСКВЫ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ПРОФЕССИОНАЛЬНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ГОРОДА МОСКВЫ «ПОЛИТЕХНИЧЕСКИЙ КОЛЛЕДЖ 50» Графический метод решения задач линейного программирования
MPRA Munich Personal RePEc Archive Use of tools of analytical geometry for search of an extremum of production function Natalia Aleksenko and Nadezhda Il ina and Victoriya Motrich Financial University
Экономические приложения теории экстремумов функций двух переменных Ляликова Е Р Ляликова Елена Реомировна / Ljalikova Elena Reomirovna - кандидат физико-математических наук, доцент, кафедра математического
Решение задачи линейного программирования графическим методом, симплекс-методом и через «Поиск решения» в Ecel ЗАДАНИЕ. Предприятие выпускает два вида продукции: Изделие и Изделие. На изготовление единицы
Для решения задач линейного программирования Арсений Мамошкин СПбГУ ИТМО Кафедра КТ 2010 г. Мамошкин А. М. (СПбГУ ИТМО КТ) http://rain.ifmo.ru/cat 1 / 28 Содержание Формулировка задачи 1. Формулировка
Исследование операций в экономике УЧЕБНОЕ ПОСОБИЕ 2-е издание, переработанное и дополненное Под редакцией профессора Í. Ø. Êðåìåðà Рекомендовано Министерством образования РФ в качестве учебного пособия
Министерство образования и науки Российской Федерации НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ЭКОНОМИКИ И УПРАВЛЕНИЯ «НИНХ» Рег. 754-16/02 Кафедра статистики МЕТОДИЧЕСКОЕ РУКОВОДСТВО ПО ОРГАНИЗАЦИИ САМОСТОЯТЕЛЬНОЙ
ВАРИАНТ 5 Для изготовления различных изделий А, В, С предприятие использует различных вида сырья. Используя данные таблицы: Вид сырья Нормы затрат сырья Кол-во сырья А В С I II III 18 6 5 15 4 12 8 540
Министерство образования и науки РФ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Уральский государственный лесотехнический университет Кафедра
Исследование операций Определение Операция - мероприятие, направленное на достижение некоторой цели, допускающее несколько возможностей и их управление Определение Исследование операций совокупность математических
ИЗ ИСТОРИИ ОТЕЧЕСТВЕННОЙ ШКОЛЫ ЭКОНОМИКО-МАТЕМАТИЧЕСКОГО И СТАТИСТИЧЕСКОГО МОДЕЛИРОВАНИЯ 1. Становление Применение математических методов в отечественных экономических исследованиях традиция, возникшая
Линейная производственная задача. Предприятие может выпускать четыре вида продукции, используя при этом три вида ресурсов. Известны технологическая матрица A затрат 7 8 ресурсов на производство единицы
ЛАБОРАТОРНАЯ РАБОТА СРЕДСТВА ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ КАК ФУНКЦИИ EXCEL Команда Подбор параметра Задание 1. Рассмотрим задачу, составленную на основании задачи по использованию функции ЧПС. Вас просят
Токарев К.С. Графическая интерпретация взаимосвязей решений исходной и двойственной задач линейного программирования // Академия педагогических идей «Новация». Серия: Студенческий научный вестник. 2018.
Динамическая задача определения оптимальной производственной программы Мищенко А.В., Джамай Е.В. В современной динамично меняющейся экономике прогрессивные изменения в народнохозяйственном комплексе страны
Практическая работа 8 Решение задач линейного программирования графическим методом. Цель работы: Научиться решать задачи линейного программирования графическим методом. Содержание работы: Основные понятия.
1 УДК: 004.032:633/635 ОПТИМИЗАЦИЯ ПЕРЕВОЗОК С ИСПОЛЬЗОВАНИЕМ АВТОМАТИЗИРОВАННОЙ ИНФОРМАЦИОННОЙ СИСТЕМЫ ВИЗУАЛЬНОГО РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ Замотайлова Дарья Александровна студентка Бурда Алексей Григорьевич
Тема 3: ТРАНСПОРТНАЯ ЗАДАЧА 2 План темы 3 «Транспортная задача»: 3.. Постановка задачи, основные определения 3.2. Закрытая и открытая транспортная задача 3.3. Метод северо-западного угла 3.4. Метод потенциалов
Сальникова Н. И. к.э.н., доцент, доцент кафедры экономической теории Институт экономики и управления КФУ им. В. И. Вернадского Росиия, г. Симферополь ЭФФЕКТИВНОСТЬ И ЕЕ ТРАКТОВКА В ОТЕЧЕСТВЕННОЙ И ЗАПАДНОЙ
Решение задачи по предмету «Теория принятия решений» Фирма «Х» производит три типа химикатов. На предстоящий месяц эта фирма заключила контракт на поставку следующих количеств трех типов химикатов; Тип
АНАЛИЗ ПОТРЕБИТЕЛЬСКОГО ВЫБОРА НА ПРИМЕРЕ ЛОГАРИФМИЧЕСКОЙ ФНКЦИИ ПОЛЕЗНОСТИ Логунова Ю.А. Самарский государственный экономический университет Самара, Россия THE ANALYSIS OF CONSUMER CHOICE BY THE EXAMPLE
Задание: Сделать математическую постановку задачи и графическим методом найти оптимальное решение. Вариант 2. Аудитории и лаборатории университета рассчитаны не более, чем на 5000 студентов. Университет
ФЕДЕРАЛЬНОЕ АГЕНСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА ФЕДЕРАЛЬНОЕ ГОСУДАСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ
ИНСТИТУТ МИРОВОЙ ЭКОНОМИКИ И ИНФОРМАТИЗАЦИИ НЕГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ Экономико-математические методы и модели. МОСКВА - 00 Практические задания
УДК 330.46 Прикладные возможности WolframAlpha для решения задач линейного программирования Соколов Арсентий Борисович Российский экономический университет им. Г.В.Плеханова Магистрант Научный руководитель:
Аналитическое задание фигур на плоскости. Задачи оптимизации Окружность с центром в точке A 0 (x 0,y 0) и радиусом R задается уравнением (x-x 0) 2 + (y-y 0) 2 = R 2. Круг, ограниченный этой окружностью,
САНКТ-ПЕТЕРБУРГСКИЙ ФИЛИАЛ НАЦИОНАЛЬНОГО ИССЛЕДОВАТЕЛЬСКОГО УНИВЕРСИТЕТА «ВЫСШАЯ ШКОЛА ЭКОНОМИКИ» Кафедра математики Н. П. Анисимова, Е. А. Ванина ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ Учебно-методическое пособие
УДК 519.852:330.4 Курышева А.С. студентка специальности «Экономическая безопасность», Институт экономики, НИУ «БелГУ», Россия, г. Белгород Зуева Е.О. студентка специальности «Экономическая безопасность»,
0 (75) 0 Экономико-математическое моделирование УДК 59.853.3 РЕШЕНИЕ РЯДА ЭКОНОМИЧЕСКИХ ЗАДАЧ АЛГОРИТМАМИ МЕТОДА ШТРАФНЫХ ФУНКЦИЙ С НЕПОЛНОЙ МИНИМИЗАЦИЕЙ ВСПОМОГАТЕЛЬНЫХ ФУНКЦИЙ А. Г. ИСАВНИН, доктор физико-математических
Глава 2 Линейное программирование В линейном программировании изучаются задачи об экстремуме линейной функции нескольких переменных при ограничениях типа равенств и неравенств, задаваемых также линейными
МЕТОДЫ ОПТИМИЗАЦИИ ЛОГИСТИЧЕСКИХ ИЗДЕРЖЕК ПРЕДПРИЯТИЯ Абрамкина Т.Н. Самарский государственный экономический университет Самара, Россия OPTIMIZATION METHODS OF FIRM LOGISTICAL COSTS Abramkina T. Samara
Двойственные задачи Содержание Экономическая интерпретация задачи, двойственной задаче об использовании ресурсов 2 Взаимно двойственные задачи линейного программирования и их свойства 5 Теоремы двойственности
Задача. (необходимо решить графическим методом) Найти максимум целевой функции L=4+y при следующих ограничениях: Решить задачу при дополнительном условии (ДУ): ДУ: Найти минимум целевой функции L=-y при
УДК 00.57: 004.94 М.Б. Котляревский доктор физико-математических наук, профессор П.В. Захарченко кандидат техничних технических наук, доцент Академия управления и информационных технологий «АРИУ», г.бердянск
УДК 5: 378 ИНФОРМАТИЗАЦИЯ ОБУЧЕНИЯ ДИСЦИПЛИНЕ «ИССЛЕДОВАНИЯ ОПЕРАЦИЙ» НА ОСНОВЕ ПРИМЕНЕНИЯ МОДЕЛЬНЫХ ОПЕРАЦИЙ В Г Гетманов докт техн наук, профессор профессор каф информатики и прикладной математики e-ml:
Глава Экстремумы функций нескольких переменных Локальные экстремумы функций двух переменных Условные экстремумы Функция z f) имеет максимум минимум) в точке M если можно найти такую окрестность точки
1. 2 ЦЕЛИ И ЗАДАЧИ ОСВОЕНИЯ ДИСЦИПЛИНЫ 1.1. Цели освоения дисциплины: ознакомить студентов с различными математическими моделями в экономике, такими, как модель межотраслевого баланса, модель экономического
Классическая транспортная задача, решенная методом потенциалов Лозгачёв И. А., Корепанов М. Ю., студенты. ФГБОУ ВПО «Уральский государственный горный университет» Екатеринбург, Россия The classical transport
Тема: Симплекс-метод решения задачи линейного программирования Общая математическая формулировка основной задачи линейного программирования: дана система m линейных уравнений с n неизвестными a11x1 a12
Московский государственный университет имени М. В. Ломоносова МОСКОВСКАЯ ШКОЛА ЭКОНОМИКИ РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ «Методы оптимальных решений» Направление 08000 Экономика для подготовки студентов бакалавров
ЛАБОРАТОРНАЯ РАБОТА 1 РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ Microsoft Excel и Mathcad ЦЕЛЬ РАБОТЫ Приобретение навыков решения задач линейного программирования (ЛП) в табличном редакторе
Практическая работа «Экономико-математические методы и модели» Вариант 2 Задание 1. Решить графически. 150x + 70x max, 30x1 + 75x2 900, 3x1 + 2x2 30, x, x 0. Решение. Построим область допустимых решений
XLI Студенческая международная заочная научно-практическая конференция «Молодежный научный форум: общественные и экономические науки» MS EXCEL КАК СРЕДСТВО РЕШЕНИЯ ЗАДАЧ ЭКОНОМИЧЕСКОГО МОДЕЛИРОВАНИЯ И
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования «Тихоокеанский государственный университет» Кафедра «Технология деревообработки» МОДЕЛИРОВАНИЕ
Нелинейная задача оптимизации. Кольцов С.Н 2014 www.linis.ru Задача безусловной оптимизации Задача оптимизации формулируется следующим образом: заданы множество Х (допустимое множество задачи) и функция
Грук Любовь Владимировна Государственное бюджетное общеобразовательное учреждение средняя общеобразовательная школа 603 Фрунзенского района Санкт-Петербурга ФУНКЦИИ И МАТЕМАТИЧЕСКИЕ МОДЕЛИ Функциональная
Леонид Витальевич Канторович (Kantorovich) (19.01.1912 г. 7.04.1986 г.) Нобелевская премия по экономике 1975 г. (совместно с Тьяллингом Купмансом) Российский экономист-математик Леонид Витальевич Канторович
Лекция 2. Основная задача линейного программирования. Все задачи линейного программирования могут быть приведены к стандартной форме, в которой целевая функция должна быть максимизирована, а все ограничения
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Ижевский государственный технический университет кафедра САПР МЕТОДИЧЕСКИЕ УКАЗАНИЯ к проведению практических занятий по дисциплине "Системный анализ" на тему
Контрольная работа Задача 5 На предприятии имеется сырье видов 1, 2, 3 Из него можно изготавливать изделия типов А и В Пусть запасы видов сырья на предприятии составляют b 1, b 2, b 3 ед соответственно,
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ ИМПЕРАТОРА
Линейное программирование в задачах управления производством Многие задачи управления, экономики и организации производства решаются с использованием метода линейного программирования. Модель линейного
«NAUKA- RASTUDENT.RU» Электронный научно-практический журнал График выхода: ежемесячно Языки: русский, английский, немецкий, французский ISSN: 2311-8814 ЭЛ ФС 77-57839 от 25 апреля 2014 года Территория
Банк заданий для промежуточного контроля Тест. Тема «Линейное программирование» Состоит из - 3 теоретических вопроса по теме и 4 6 практических заданий, предусматривающих умения и навыки: составлять математические
ISSN 1992-6502 (P ri nt)_
2014. Т. 18, № 1 (62). С. 186-197
Ъыьмт QjrAQnQj
ISSN 2225-2789 (Online) http://journal.ugatu.ac.ru
УДК 621.35, 004.02
Теория оптимального использования ресурсов Л. В. Канторовича в задачах раскроя-упаковки: обзор и история развития методов решения
Ю. И. Валиахметова, а. С. Филиппова
1 ФГБОУ ВПО «Башкирский государственный аграрный университет» (БГАУ) 2 ФГБОУ ВПО «Башкирский государственный педагогический университет им. М. Акмуллы» (БГПУ)
Поступила в редакцию 04.02.2014
Аннотация. Приводятся примеры постановок задач раскроя-упаковки, актуальность которых подтверждается их разнообразием и многогранностью прикладного значения. Основополагающими для развития методов решения подобных задач явились работы Л. В. Канторовича. Приведен обзор методов решения классических задач раскроя-упаковки, разработанных советскими и российскими учеными за последние 80 лет, в том числе и научными школами СССР и России. Даны краткие описания методов и история их развития.
Ключевые слова: раскрой; упаковка; рациональное использование ресурсов; оптимизация; точные методы; эвристические методы, алгоритмы
Посвящается 100-летию со дня рождения нобелевского лауреата Л. В. Канторовича
ВВЕДЕНИЕ
Вклад, сделанный замечательным и талантливым ученым Леонидом Витальевичем Канторовичем в различные области математики и экономики, имел огромное значение в развитии решения прикладных производственных задач. Кроме того, его концепция оптимальной экономической модели на макроэкономическом уровне и сегодня обладает огромным потенциалом. И в речи шведского профессора Рагнара Бентзеля, которую в 1975 г. он произнес, представляя лауреатов Нобелевской премии по экономике Л. В. Канторовича и Т. Купманса, отмечено всеобщее значение концепции для любой экономики, независимо от ее социально-политической формы: «Поскольку запас производственных ресурсов всюду ограничен, каждое общество сталкивается с кругом вопросов, касающихся оптимального использования имеющихся ресурсов и справедливого распределения доходов между гражданами. Точка зрения, с которой могут рассматриваться подобные нормативные вопросы, не зависит от политической организации рассматриваемого общества» . Поэтому исследование и разработка методов
Работа поддержана грантом РФФИ 12-07-00631-а.
решения задач рационального использования ресурсов актуальны и по сей день.
1. БАЗОВЫЕ МЕТОДЫ
ОПТИМАЛЬНОГО ИСПОЛЬЗОВАНИЯ РЕСУРСОВ
Основополагающую роль в становлении и развитии теории оптимального использования ресурсов и линейного программирования сыграла опубликованная профессором Л. В. Канторовичем в 1939 г. брошюра , где рассматривались различные практические задачи организации производства, в которых требовалось найти наилучший вариант решения. Книга была написана после консультации сотрудников Фанерного треста по вопросам решения задач, которые не удавалось решить традиционными в то время методами. Л. В. Канторович предложил метод разрешающих множителей (индексов), который устанавливает принципиальную возможность нахождения наилучшего решения для многих задач народного хозяйства, в том числе и для задачи массового раскроя. Несмотря на огромный круг научных интересов, в последующие годы Л. В. Канторович неоднократно возвращался к проблеме рационального раскроя, например .
В 30-х гг. прошлого века были заложены основы теории раскроя пиловочного сырья, основоположником которой стал Х. Л. Фельдман . Он предложил математический подход для
решения задачи о максимальных поставах при распиловке бревен. Вместе со своими последователями он создал систему, ориентированную на максимизацию объемного и качественного выхода обрезных пиломатериалов. Точная математическая схема решения не в полной мере учитывала реальные условия, такие как качественные характеристики сырья и пилопродукции, поэтому результаты на практике могли быть и неверными. Позднее В. А. Залгаллером разработан графический метод составления максимальных поставов, основанный на геометрическом признаке экстремума. Предложенный В. А. Залгаллером метод позволил приблизить теорию максимальных поставов к условиям производства .
Разработанная и усовершенствованная теория, однако, и в настоящее время не может дать ответа на многие проблемы технологии лесопиления, в связи с чем актуально ее дальнейшее совершенствование. Среди основных причин этого явления: технический прогресс, изменения размерно-качественной характеристики поступающего в раскрой пиловочного сырья и его породного состава, ужесточение требований экологов, изменение действующих стандартов на сырье и пиленую продукцию.
2. МНОГООБРАЗИЕ ЗАДАЧ РАСКРОЯ И УПАКОВКИ
Задачи раскроя представляют собой важную технологическую проблему, оптимальное решение которых позволяет минимизировать расход имеющихся ресурсов. Это такие задачи, как:
Раскрой линейного материала;
Продольная резка лент и рулонов;
Раскрой листов на прямоугольные заготовки;
Использование материалов смешанной длины;
Раскрой для серийных и несерийных изделий;
Упаковка трехмерных контейнеров;
Раскрой фигурных заготовок;
Размещение кругов;
Геометрическое покрытие областей с препятствиями элементами различной формы;
Задача о выборе наилучших размеров материала для последующего раскроя;
Упаковка/покрытие элементами случайных размеров,
и многие другие.
Подобные задачи встречаются на практике в машиностроении, металлургии, деревообраба-
тывающей и швейной промышленности, целлюлозно-бумажной индустрии и др.
Многие задачи, на первый взгляд не относящиеся к классу задач раскроя и упаковки, в конечном итоге сводятся к ним. Например, задачи о составлении расписания, задачи маршрутизации, задачи декомпозиции многосвязных ортогональных полигонов, а также многие другие прикладные задачи.
Если ценность раскраиваемого ресурса высока, на практике рассматривают также и остаточные задачи: производится попытка использовать отходы материала, получившиеся при решении предыдущих задач раскроя, упаковки или геометрического покрытия.
Задачи раскроя, упаковки или покрытия могут возникать как промежуточное звено в других задачах или же чередоваться в рамках одной задачи. Например, можно рассмотреть логистическую задачу, где каждому транспортному средству сопоставляется маршрут следования по потребителям и набор соответствующих этим потребителям грузов. Тогда поиск маршрута следования каждого транспортного средства, а также нахождение плана размещения грузов в грузовом отсеке являются задачами класса раскроя-упаковки. Дополнительно при размещении грузов можно учесть порядок следования транспортного средства - так, чтобы грузы, предназначенные последнему клиенту, загружались первыми .
Каждая из предметных областей вносит свои дополнительные требования в способ решения задач, и, следовательно, в способ адаптации известных алгоритмов.
В данной статье приведен краткий обзор методов решения классических задач раскроя-упаковки, разработанных советскими и российскими учеными за последние 80 лет. Под задачами раскроя-упаковки (Cutting and Packing, C&P) понимается широкий класс проблем, допускающих различное прикладное толкование. К ним можно отнести следующие задачи:
Раскрой запаса материала (при раскрое на определенные заготовки минимизация исходного материала);
Плотное размещение геометрических объектов в заданной области (размещение грузов, товаров на складе и т.п.);
Упаковка контейнеров (размещение предметов в ограниченную область);
Выбор ассортимента (выбор при заказе одного размера из стандартных);
Планировка помещений (максимизация полезных областей при планировании с учетом технологичных требований);
Обеспечение ритмичности производственного процесса (задачи о составлении расписания, составление расписания многопроцессорных систем);
Распределение производственных мощностей (распределение памяти вычислительной машины);
Задача о поставе в лесопилении (расположение пил при пилении бревна на доски разной толщины, выбор числа пил для максимизации выхода);
Раскрой древесного ствола по длине (максимизация продукции при раскрое ствола на круглые сортименты);
Раскрой досок (раскрой на заготовки, более близкие к окончательной продукции; обойти пороки и максимизировать суммарную кубатуру или суммарную коммерческую цену);
Раскрой листового материала на случайные заготовки (раскрой материала с учетом опережения-запаздывания производства заготовок);
Максимальное (минимальное) геометрическое покрытие (расстановка минимального количества единиц оборудования на заданной области) и др.
В свою очередь каждая из них может быть различным образом конкретизирована.
Общим для задач этого класса является наличие двух групп объектов. Между элементами этих групп устанавливается и оценивается соответствие. Различаются задачи линейного (одномерного), прямоугольного (двухмерного) и па-раллелепипедного (трехмерного) раскроя-упаковки. Среди этих задач выделяются гильотинный раскрой и упаковка. Особо выделены проблемы нестинга - размещения деталей сложной геометрической формы в заданных областях. Для них на первый план выступают информационные проблемы задания фигур, учета и обеспечения их непересечения, кодировки и др. Перечень геометрических свойств заготовок и материала может дополняться и учитываться в математической модели некоторыми физическими и/или экономическими показателями. Подробная классификация основных моделей задач С&Р в России приведена в .
В 40-х гг. методы для решения задач раскроя были направлены в первую очередь на задачи массового производства, где можно пренебречь целочисленностью результатов. Предложенный Л. В. Канторовичем способ решения подобных задач позволял найти оптимальный раскрой, однако трудоемкость процесса решения вручную требовала адаптации к производственным условиям и совершенствования вычислительного математического аппарата. Именно этому вопросу в основном и были посвящены научные разработки последователей и соратников Л. В. Канторовича до 50-60-х гг. Далее появилась возможность реализации алгоритмов на ЭВМ. Программы позволяли находить оптимальные планы раскроя мерных линейных материалов и оптимальных планов раскроя прямоугольных листов на прямоугольные заготовки. Начиная с 70-х гг. особое внимание исследователей этой области было направлено на решение задач единичного и мелокосерийно-го производства.
Впервые детально вопросы раскроя были проработаны Л. В. Канторовичем совместно с В. А. Залгаллером в Ленинградском отделении Математического института АН СССР в 40-х гг. . Практическая проверка успешности разработанных ими математических способов решения проведена на Ленинградском вагоностроительном заводе в 1948-1949 гг. Ввиду технологических требований и трудоемкости вычисления метода разрешающих множителей была проведена большая работа по развитию и адаптации математического аппарата к производственной действительности того времени за счет введения новых расчетных и технологичных приемов. Так, В. А. Залгаллер разработал способ подбора целочисленных индексов, предложил решение плоской задачи с помощью вспомогательной линейной задачи, приемы раскроя материала смешанной длины и различные технические приспособления. Все разработанные и практически апробированные методы того периода, методика их использования были описаны в книге «Рациональный раскрой промышленных материалов», изданной в начале 1951 г. . Задачи раскроя рассматривались авторами как примеры применения линейного программирования (Linear Programming, LP). При решении задач раскроя применяется модель LP с неявно заданной информацией о раскроях (столбцах матрицы). Фактически эта книга была отчетом об удачном практическом внедрении в 1948-1949 гг. линейного программирования для решения промышленных задач. Первые зарубежные же публикации, посвященные LP, отно-
сятся к 1949 г. Основные расчеты, приведенные в книге , были выполнены вручную. Для преодоления трудностей, связанных с построением допустимых карт раскроя, авторами были предложены приемы, которые, по существу, предвосхитили идеи динамического программирования.
Для решения задачи генерирования раскроя были разработаны основанные на динамическом программировании методы для задачи линейного раскроя , для гильотинного раскроя - сеточный метод генерирования раскроев с максимальной оценкой , считающие полную таблицу индексов. И. В. Романовский предложил метод склейки , ограничивающийся состояниями, соответствующими скачкам. Позднее Э. А. Мухачева разработала условные методы генерирования раскроев на каждом шаге процесса линейного программирования, учитывающие специфику реального производства . В то время основной целью этих и многих других работ являлось применение линейного программирования в сфере производственных задач. Эта цель в той или иной мере была достигнута в условиях массового и серийного производства.
3. ДЕЯТЕЛЬНОСТЬ СОВЕТСКИХ НАУЧНЫХ ШКОЛ ПО ИССЛЕДОВАНИЮ ЗАДАЧ РАСКРОЯ-УПАКОВКИ
Несомненно, развитие и широкое применение это направление получило с появлением ЭВМ: например, первая программная реализация на ЭВМ метода шкалы индексов . В приведен способ и программа для рационального решения массовой линейной задачи, затрачивающий приемлемое время для расчета. Расчет рациональных карт раскроя прямоугольных листов в 60-е гг. для большого числа заготовок (более 60) практически не представлялся возможным. А примеры меньшей размерности требовали многих часов работы программ на ЭВМ .
Так, применение ЭВМ для решения и исследования задачи массового раскроя в начале 60-х гг. прошлого века стало первым шагом для зарождения уфимской научной школы под руководством Э. А. Мухачевой. Элита Александровна Мухачева в 1962 г. поступила в аспирантуру Новосибирского академического городка института математики СО АН СССР в отдел к создателю теории линейного программирования Леониду Витальевичу Канторовичу и получила задание разработать программу для массового раскроя материала, результат описан в .
Приоритет Л. В. Канторовича в этой области уже был признан в мире, он заведовал матема-тико-экономическим отделом. Сотрудник отдела, ученик и соратник Л. В. Канторовича, доктор физико-математических наук Г. Ш. Рубинштейн стал научным руководителем Элиты Александровны. В начале 1967 г. она защитила диссертацию «Численные методы решения некоторых классов задач линейного программирования» на соискание ученой степени кандидата физико-математических наук1. С тех пор в Уфимском государственном авиационном техническом университете ведутся активные исследования в данной области.
Для задач штучного производства, являющихся по своей сути проблемами дискретной оптимизации, решение с помощью LP - это упрощение, позволяющее получить результат, близкий к оптимальному, при дополнительных ограничениях, возникающих в условиях серийного и массового производства. В дальнейшем задачи С&Р рассматривались уже без этого упрощения, как прикладные проблемы комбинаторных задач исследования операций. Задачи С&Р являются типичными представителями NP-трудных проблем. Ввиду неполиномиальной сложности точных алгоритмов для задач С&Р авторами многих работ и по сей день уделяется значительное внимание приближенным методам, а при разработке точных алгоритмов -процедурам сокращения полного перебора и вычислению нижних границ.
При решении задач С&Р необходимо минимизировать используемый материал (количест-
1 В 1983 г. Э. А. Мухачева (1930-2011) защищает докторскую диссертацию «Прикладные задачи комбинаторной оптимизации, в частности, задача раскроя и упаковки» и становится первой женщиной-доктором наук УАИ (Уфимского авиационного института). Работая над диссертацией, она консультировалась у Л. В. Канторовича, В. А. Залгаллера и в Новосибирском академическом городке. Из 59 лет работы в Уфимском авиационном университете (УАИ, УГАТУ) 34 года заведовала кафедрами. Научная значимость трудов Э. А. Мухачевой и ее учеников колоссальна. Студенты, аспиранты, ученые нашей страны изучали математическое программирование, математические методы исследования операций, теорию и методы расчета в задачах раскроя-упаковки по учебникам, монографиям и статьям, автором которых является Э. А. Мухачева. Многие из ее последователей по сей день продолжают разработки в России и за рубежом. Результаты многочисленных работ внедрены, например, на Кировском заводе (г. Ленинград), при производстве тракторов на Ижевском механическом заводе, в Ульяновском авиационном комплексе и др.
во, площадь или объем). При этом оптимальное значение будет больше либо равно нижней границы и меньше либо равно верхней границы.
С помощью границ оценивается решение, полученное тем или иным методом. Верхняя граница, например, полученная приближенно любым эвристическим методом и уточняемая в ходе вычислений, применяется в методе ветвей и границ для сокращения множества просматриваемых узлов дерева решений: отсеиваются узлы, у которых оценка не меньше верхней границы.
При решении задач точными методами использование границ позволяет сократить время работы алгоритма. Так, большее время работы точного алгоритма затрачивается на доказательство оптимальности найденного решения, возможно, полученного уже в начале вычислений. Для этого этапа как раз очень важна нижняя граница, значение которой должно быть максимально близко к оптимуму. Проблема подсчета нижних границ остается основной при разработке эффективных точных методов решения задач С&Р. Особый интерес для вычислений представляют уточняемые нижние оценки, они позволяют либо быстро отсекать «слабые» частичные решения либо просто остановить вычисления по достижении достаточно хорошего результата. В предложен метод построения нижних границ, основанный на линейной релаксации. Показано, что оптимальное значение исходной задачи можно оценить с помощью решения соответствующей задачи линейного раскроя. Предложено уточнение этой нижней границы, использующее метод фиксации определенных переменных.
Традиционными для единичных проблем С&Р являются математические модели целочисленного линейного программирования (ЦЛП). Но надо отметить и другие, например, предложенные в начале XXI в.: матричная модель - представление прямоугольной упаковки двумя бинарными матрицами, характеризующими всевозможные пересечения прямоугольников с сечениями контейнерной области параллельно координатным осям ; модель, предложенная В. Н. Марковым, в которой лист материала описывается растровой последовательностью точек .
Методы, основанные на ЦЛП, оказались приемлемыми для решения задач линейного (одномерного) и гильотинного раскроя. Что касается классов задач негильотинной упаковки, то алгоритмы LP вряд ли можно сейчас считать подходящими для их решения. Пока для этих задач большинство существующих точных ме-
тодов решения сводятся к перебору всего множества допустимых решений. Методы улучшенного перебора объединены и для этих задач под названием «метода ветвей и границ». Еще в 1973 г. И. В. Романовский и Н. П. Христова предложили для решения дискретных минимаксных задач метод дихотомии . Для получения нижней оценки в авторы предложили использовать релаксацию задачи, переходя от множества допустимых решений к некоторому его подмножеству.
В 60-х гг. в г. Харькове под руководством В. Л. Рвачева и Ю. Г. Стояна разрабатываются подходы к решению задач с фигурными заготовками . Для описания фигур, ограниченных контуром из конечного числа отрезков и дуг окружностей, вводятся специального типа Я-функции, которые позволяют определить принадлежность точки к фигуре одним неравенством, что позволяет упростить проверку непересечения фигур между собой. Поиск оптимальных размещений осуществляется методом составления большого числа случайных ненале-гающих положений, каждое из которых затем переводится градиентным методом в локально минимальное положение. Этот подход получил и дальнейшее развитие. Используемые как средство математического и компьютерного моделирования R-функции внесли существенный вклад в формализацию 2D- и 3D-задач С&Р и разработку методов их решения .
Следует отметить значительный вклад, внесенный в теорию и практику моделирования размещения геометрических объектов научной школой Ю. Г. Стояна (Украина, Институт проблем машиностроения НАН). В конце 60-х гг. на базе Уфимского авиационного института под руководством Э. А. Мухачевой зарождается еще одна научная школа, в которой активно и по сей день занимаются проблемами С&Р, в том числе и задачами с произвольной формой заготовок . Начиная с 60-х гг. ведутся исследования задач фигурного раскроя в Горьковском университете, в коллективе Л. Б. Беляковой, в Институте технической кибернетики АП БССР, г. Минск. В это же время упрощенными алгоритмами для решения задач фигурного раскроя с применением ЭВМ занимаются на многих производственных предприятиях СССР .
Подробнее обзор публикаций до 70-х гг. представлен в дополненном втором (1951 г.) и третьем (2012 г.) изданиях книги . Третье переиздание было подготовлено с участием В. А. Залгаллера.
альных условий, касающихся различных отраслей: металлургии, судостроения, деревообработки, бумажной и швейной промышленности. Например, в Карельском институте лесной промышленности под руководством И. В. Соболева , в Петрозаводском государственном университете под руководством В. А. Кузнецова ведется работа, связанная с применением методов оптимизации на промышленных предприятиях Карелии и Северо-Запада России. Здесь развиваются методики решения оптимизационных задач в целлюлозно-бумажной промышленности . Они реализованы в комплексах прикладных программ, направленных на решение проблем, связанных с раскроем и планированием работ в деревообрабатывающей промышленности. Помимо задач, связанных непосредственно с раскроем, рассматриваются технологические проблемы при организации производства: для удобства комплектации необходимо производить одновременно или почти одновременно все детали изделия, выпускаемого в данный момент, а особенности предварительного раскроя ограничивают возможности укладки этих деталей в прямоугольники, что приводит к большим отходам. Это, например, распиловка бревен, раскрой гофрокартона.
В 70-х гг. в Омском государственном университете под руководством А. А. Колоколова также начинаются исследования и разработки алгоритмов решения задач дискретной оптимизации, сводящихся к задачам раскроя-упаковки. Основное внимание этой научной группы уделено задачам линейного целочисленного программирования, прикладным задачам размещения, задачам раскроя, встречающимся в легкой промышленности и швейном производстве. Разработаны и исследованы новые алгоритмы и подходы, основанные на использовании регулярных разбиений релаксационных множеств, L-разбиений. Надо отметить, что решением проблем с автоматизацией процесса раскроя занимаются и по сей день в Омске , Новосибирске . Обзор существующих САПР конструкторской и технологической подготовки производства одежды представлен в . Хотя главной задачей этих систем является моделирование индивидуальной и мелкосерийной одежды, а процесс раскроя материала не использует сложных оптимизационных методов расчета. Можно отметить работы А. А. Петунина проводимые в Екатеринбурге с конца 70-х гг., которые направлены на автоматизацию проектирования раскроя листового материала, . Они позволили позже разработать универсальную систему «Сириус» с собствен-
ным графическим интерфейсом, ориентированную на широкий спектр оборудования для резки листовых материалов .
4. СОВРЕМЕННОЕ РАЗВИТИЕ МЕТОДОВ РЕШЕНИЯ ЗАДАЧ РАСКРОЯ-УПАКОВКИ
Новые эффективные точные методы развивались по нескольким направлениям. С одной стороны, совершенствовались инструменты ЦЛП: моделирование, методы ветвлений, секущие плоскости. С другой стороны, развивались чисто комбинаторные методы, получившие позже наиболее полное развитие в рамках методов искусственного интеллекта.
Например, в представлен гибридный метод непрерывной оптимизации и переборного алгоритма решения задачи упаковки многоугольников, где в качестве частного случая рассматривается задача упаковки прямоугольников в полосу, разработана стратегия построения множества систем уравнений и набора правил для отсечения бесперспективных вершин дерева решений. Этот метод получил и дальнейшее развитие в конце 90-х гг.
Задача одномерного раскроя с единичными комплектностями является наиболее подходящей для решения комбинаторными методами. Одним из первых был метод ветвей и границ на основе релаксации ЛП с генерацией столбцов. В большинстве вариантов метода ветвление осуществляется по отдельным столбцам. В работе автор для данной задачи применяет дихотомический вариант обобщенного метода решения дискретных минимаксных задач . В нем на каждом этапе ветвление по дереву решений происходит по двум подмножествам, что сокращает перебор допустимых решений. Для задач одномерного раскроя с целочисленными комплектностями - 1D cutting-stock problem (1DCSP) - методы ЦЛП являются более эффективными вследствие комбинаторного взрыва. В большинстве из них используется модель 1DCSP с генерацией столбцов, впервые предложенная в работе Л. В. Канторовича и А. А. Залгаллера . Эта модель имеет очень маленький эмпирический разрыв двойственности. Количество переменных модели не ограничено полиномиально от размерности задачи (количества предметов), поэтому довольно трудно оценить количество столбцов, генерируемых при поиске оптимума. На практике задача быстрого нахождения ЛП оптимума, т. е. вопрос ускорения сходимости процесса генерации столбцов, является очень актуальной.
Вопрос об эффективном применении точных комбинаторных методов решения задач раскроя-упаковки большой размерности остается открытым до сих пор. Ведутся исследования для определения отсечений, которые позволяют не рассматривать симметричные варианты правил сокращения перебора. Например, в рассмотрен метод с процедурами доминантности, группировки, определения допустимого резерва, позволяющий сократить перебор.
Математический аппарат, позволяющий вычислить оптимум в негильотинной задаче C&P за конечное число операций впервые предложен в , где задача упаковки прямоугольников сформулирована как проблема комбинаторной оптимизации и предложен «метод зон» для нахождения оптимального решения. На основе понятия «зоны» доказывается, что для любой упаковки прямоугольников можно указать такой их порядок, при котором каждый следующий прямоугольник не пересекается ни с одной из зон предыдущих (топологическая сортировка). Показано, что среди упаковок, построенных на ступенчатых границах, есть оптимальные. Для сокращения числа вариантов предложен ряд отсечений, позволяющих отбрасывать варианты, симметричные уже рассмотренным, или заведомо не лучше других.
Для решения комбинаторных задач из класса NP-трудных с успехом применяются эвристические методы. Среди эвристик высокого уровня выделяются жадные алгоритмы, позволяющие достигать верхние границы . К многопроходным эвристикам относится метод последовательного уточнения оценок (Sequential Value Correction, SVC), берущий начало от идеи объективно-обусловленных оценок Л. В. Канторовича . Метод SVC реализуется по модифицированной схеме «первый подходящий с упорядочиванием» с процедурами приоритета и повторения. Упорядочивание элементов основано на экономическом смысле двойственных переменных в линейном программировании. Метод можно назвать общим для решения задач C&P: он применим для задач линейного и гильотинного раскроя, 2D- и SD-упаковки, а также и для фигурного раскроя .
При реализации схем построения решений в комбинаторных задачах используют различные способы представления допустимого решения в виде кода, который с помощью соответствующего правила (декодера) однозначно преобразуется в план упаковки. Способы кодирования и декодирования существенным образом влияют на эффективность получаемых решений. При этом сам декодер является однопроходным ме-
тодом. Простым и популярным декодером является «нижний левый», который однозначно позволяет получить план упаковки по коду в виде последовательности (списка) прямоугольных деталей. В уфимском коллективе разработаны новые блочные декодеры , позволяющие представить прямоугольную упаковку в виде линейного раскроя специальной структуры, для которой используются линейные методы решения, за счет чего получают быстрые и эффективные решения. Аналогично представляется и 3D-упаковка.
Если при выбранном способе декодирования повторять решение, несколько изменяя уже использованный код, то значение целевой функции изменится в лучшую или худшую сторону. При многократном повторении можно получить достаточно хорошее решение. На этом принципе в сочетании с комбинацией различных декодеров разработаны технологии конструирования алгоритмов локального поиска для C&P .
Таким образом, внесение в детерминированный алгоритм элементов случайности повышает его результативность. Так, например, повысилась эффективность упомянутого выше алгоритма SVC после внесения в него элементов стохастики. Бурное развитие вероятностных методов локального поиска оптимума началось 20 лет назад с появлением метаэвристик для решения NP-трудных задач. В России обзор вероятностных методов локального поиска оптимума для NP-трудных задач сделан в . В обзоре обсуждаются общие схемы алгоритмов поиска с запретами, имитации отжига, эволюционного и генетических алгоритмов. Показано, что эти разные по своей структуре алгоритмы используют общую математическую конструкцию конечных цепей Маркова, а также доказывается, что при корректной реализации процедур поиска указанных метаэвристик, когда отсутствует эффект «застревания» в локальном оптимуме, будет наблюдаться сходимость по вероятности наилучшего найденного решения к оптимальному решению задачи.
Первыми среди сложных метаэвристик для задач C&P стали применяться генетические алгоритмы. Возможны различные способы кодирования и приемы идентификации простейших структур (ген, аллели, хромосома). Это порождает различные классы генетических алгоритмов . Генетические алгоритмы успешно разрабатываются и для решения задач фигурного раскроя . Исследуются и используются и другие метаэвристики. Кроме того, в последние
годы активно развивается применение искусственного интеллекта .
Изменения в стране, начатые в 80-х гг., позволили российским ученым активно публиковать свои работы за рубежом в изданиях, посвященных исследованиям операций, участвовать в международных конференциях. Сообщество под названием SICUP (Специальная группа по интересам в области раскроя-упаковки) объединяет многих исследователей, заинтересованных в данной проблеме по всему миру. SICUP организует сессии по проблемам С&Р в рамках международных конференций. Было принято решение об организации нового сообщества ESICUP (http://pagmas.fe.up.pt/~esicup/tiki-
index.php). И обратная ситуация - участие зарубежных исследователей в российских специальных изданиях , совместные исследования, например .
В СССР проводились научно-практические семинары и конференции в Ленинграде, Уфе, Звенигороде и других городах. В современный период организуются секции в рамках работы конференций: Математическое программирование и приложения (Екатеринбург, ИММ УРО АН РФ); Дискретный анализ и исследование операций (DAOR, Новосибирск, ИМ СО РАН); Компьютерные науки и информационные технологии (CSIT, Уфа, УГАТУ); Ресурсосберегающие технологии (ОПТИМ, С.-Петербург); Методы оптимизации и их приложения (Байкальская международная конференция по математическому программированию, Иркутск); Дискретная математика и экономические приложения (Омск, филиал ИМ СО РАН) и др.
В последнее десятилетие теоретические аспекты проблемы раскроя-упаковки и геометрического покрытия в виду их NP-сложности остаются актуальными. Основное внимание российских научных исследований методов и задач C&P связаны не только с усовершенствованием эффективности методов их решения, но и с проблемами в которых задачи раскроя и упаковки включены в качестве подзадач. Это накладывает дополнительные условия и ограничения в постановке задач. Например: в лесопромышленности, в легкой промышленности, при проектировании электронных схем, в транспортной и складской логистики, в строительной и судостроительной отраслях и др.
Так, например, в работах исследуются задачи планирования производства гофро-тары, выбора транспортных средств и размещения продукции, планирования производства пиломатериалов, планирования погрузки водного транспорта, раскроя и комплектовки в модели-
ровании технологических процессов в условиях стохастики производственного процесса, рассматриваются критерии эффективности подобных задач.
Теоретические предпосылки для создания автоматизированной системы управления раскроем в швейной промышленности описаны в работе , исследуется проблема параметрического моделирования сложных трехмерных объектов и его применения. В работе приведен краткий обзор существующих САПР конструкторской и технологической подготовки производства одежды. Одной из первых разработок в области САПР для конструктора швейных изделий явилась белорусская система «АВТОКРОЙ» (г. Минск), функционирующая в 80-е гг. в НПО «Белбыттехника». Первой системой, предназначенной специально для конструирования одежды с помощью персонального компьютера, стала система ЛЕКО, разработки Центрального научно-производственного института швейной промышленности (ЦНИИШП). В настоящее время систему используют небольшие швейные и трикотажные предприятия, а также вузы, ведущие подготовку специалистов в области проектирования швейных изделий. Вслед за ЛЕКО появляется серия САПР: Система АССОЛЬ (Центр компьютерных технологий при Московском физико-техническом институте); Система T-FLEX/ОДЕЖДА использует типовые методики конструирования; ГРАЦИЯ и др. Одной из последних разработок стала система ELEANDR-CAD (Научно-технический центр дизайна и технологии при МГУДТ и компания ООО «Элеандр», 2003). В работе авторы исследуют задачу о минимальном покрытии на примере проектирования меховых изделий.
Исследования показали, что задачи, в которых требуется сформировать в определенном смысле оптимальное множество объектов (машин, наборов моделей одежды, приемов, свойств), покрывающее «потребности» другой совокупности (работ, клиентов, заказов, характеристик) при выполнении некоторых условий, обусловленных спецификой задачи, могут быть сведены к задачам о покрытии и различным их модификациям. На основе разработан гибридный алгоритм для решения задач оптимизации выбора объектов в процессе технической подготовки производства, в том числе при определении доминирующих свойств материалов, на примере легкой промышленности. Оригинальный подход к исследованию связи проблем ортогонального раскроя и покрытия на примере задач построения маршрутов, удовлетворяющих определенным ограничениям, приведен Т. Па-
нюковой, . Автором замечено, что в задачах раскроя листового материала плоский граф является моделью раскройного плана, а маршрут, покрывающий все ребра, определяет траекторию режущего инструмента. В работе приведена модификация алгоритма построения покрытия с упорядоченным охватыванием на случай многосвязного графа. Построение покрытия графа с упорядоченным охватыванием решает поставленную задачу раскроя. Наибольший интерес представляют покрытия с минимальным числом цепей, поскольку переход от одной цепи к другой соответствует холостому проходу режущего инструмента.
Пример применения генетических алгоритмов для автоматизации размещения разногабаритных тепловыделяющих элементов в электронных модулях трехмерной компоновки на основе теплового критерия приведен в работе .
Решению задачи размещения грузов в грузовых отсеках транспортных средств, возникающей в качестве подзадачи в логистических системах, посвящены многие работы. Например, в решается задача управления загрузкой контейнеров с учетом их физических характеристик, в для этой задачи осуществляется учет условия технологичной загрузки-разгрузки потребительских товаров, т.е. последовательность посещения клиентов при доставке грузов.
В работе предложен алгоритм решения задачи, возникающей, например, в строительной индустрии - задачи геометрического покрытия многосвязного полигона ортогональным ресурсом. Исходной информацией являются размеры покрываемой области и имеющегося ортогонального ресурса, а размеры покрывающих элементов, которые необходимо впоследствии раскроить из ресурса, заранее не определены. Это обуславливает многокритериальную оптимизацию процесса построения взаимосвязанных рациональных планов геометрического покрытия прямоугольными элементами незаданных размеров и раскроя ортогонального ресурса на покрывающие элементы.
Технологические особенности раскройного оборудования обуславливают появление задач проектирования управляющих программ для машин листовой резки. В работе автором отмечается важность проблемы стоимости и значимости различных этапов процесса вырезания заготовок из материального ресурса, таких как, например, перемещение режущего инструмента в другое место раскраиваемого листа и новой резки. Таким образом, кроме плотного размещения заготовок на плане раскроя, целевая функция направлена на оптимизацию маршрута
режущего инструмента с учетом стоимости ре-зов, новой врезки.
Значительное внимание уделяется также и теоретическим разработкам проблемы раскроя и упаковки. Например, в работах рассмотрены задачи упаковки гофров (ортогональных связных многоугольников) с позиций общей теории проблемы оптимального размещения геометрических объектов, предложены алгоритмы упаковки «-мерных гофров на базе методов линейного программирования, а также модели и методы оптимизации упаковки «-мерных параллелепипедов.
ЗАКЛЮЧЕНИЕ
Многообразие раскройных задач вместе со значимостью их рационального решения обуславливает неугасающий интерес опытных и молодых исследователей всего мира к этой проблематике, с чем связана устойчивая тенденция роста численности новых методик для их решения.
В задачах C&P замечательным образом сочетается их широкая практическая применимость и их принадлежность к NP-трудным проблемам, что делает эту проблематику важным полигоном новых исследований. Благодаря этому идеи Л. В. Канторовича будут использоваться и развиваться в различных сферах научной и практической деятельности человека, связанной с проблемой раскроя.
СПИСОК ЛИТЕРАТУРЫ
1. Канторович Л. В. Математика, менеджмент, информатика: монография / ред.: Г. А. Леонов, В. С. Катькало, А. В. Бухвалов, СПб.: Высш. шк. менеджмента: Издательский дом Санкт-Петербургского ун-та, 2010. 575 с. [ L. V. Kantorovich, Mathematics, management, informatics: monograph, (in Russian). Edited by G. A. Leonov, V. S. Katcalo, and A. V. Buhvalov, St.Ptsb.: Management higher school: St. Petersbourg University Publishing House, 2010. ]
2. Канторович Л. В. Математические методы организации и планирования производства. ЛГУ, 1939. 67 с. . [ L. V. Kantorovich, Mathematical Methods of Production Management and Planning, (in Russian). Leningrad: Leningrad Univ., 1939.]
3. Канторович Л. В. Рациональные методы раскроя металла // Произв.-техн. бюл. НК Боеприпасов СССР. 1942. № 7-8. С. 21-29. [ L. V. Kantorovich, "Efficient Methods of Metal Cutting," (in Russian), Product.-techn. bulletin. of NK Ammunition of the USSR, no. 7-8, pp. 21-29, 1942. ]
4. Фельдман Х. Л. Система максимальных поставов на распиловку. М.: Гостехиздат, 1932. [ H. L. Feldman, Maximum delivery system for sawing, (in Russian). Moscow: Gostehizdat, 1932. ]
5. Залгаллер В. А. Новое в составлении поставов для распиловки бревен. Л.:ЦНИИЛ «Севзаплес», 1956. Вып. 67. [ V. A. Zalgaller, A step forward in delivery formation for timber sawing, (in Russian). Leningrad: CNIIL "Sevzaples", vol. 67, 1956. ]
6. Валиахметова Ю. И., Мухачева Э. А., Филиппова А. С., Гильманова Н. А., Карипов У. А. Мультиметодная
технология ортогональной упаковки и ее применение в задачах транспортной логистики // Приложение к журналу «Информационные технологии». 2009. № 12. 31 с. [ U. I. Valiahmetova, et al., "Multimethod technology of orthogonal bin-packing and its application in transport logistics problems," (in Russian), in Appendix to Magazine Information technologies, no. 12, 2009. ]
7. Мухачева Э. А., Мухачева А. С., Валеева А. Ф., Картак В. М. Методы локального поиска в задачах ортогонального раскроя и упаковки: аналитический обзор и перспективы развития // Информационные технологии. 2004. № 5. Приложение. С. 2-17. [ E. A. Mukhacheva, et al., "Local search methods in orthogonal cutting-packing problems: analytical survey and development outlook," (in Russian), in Appendix to magazine Information Technologies, no 5, pp. 2-17, 2004. ]
8. Канторович Л. В., Залгаллер В. А. Расчет рационального раскроя материалов. Лениздат, 1951. 198 с. [ L. V. Kantorovich and V. A. Zalgaller, Computation of effective material cutting , (in Russian). Lenizdat, 1951. ]
9. Булавский В. А., Яковлева М. А. О решении задачи оптимального раскроя линейных материалов на ЭВМ // Линейное программирование: Труды Науч. совещ. о применении матем. методов в экон. исслед и планировании. М.: АН СССР, 1961. Т. IV. С. 83-87. [ V. A. Bulavski and M. A. Jakovleva, "To solution of problems of linear material cutting on COMPUTER," (in Russian), in Linear programming. Papers of scientific conference on mathematical method application in econom. research and planning, vol. IV. Moscow: AS USSR, 1961, pp. 83-87. ]
10. Мухачева Э. А. Рациональный раскрой прямоугольных листов на прямоугольные заготовки // оптимальное планирование: c6. науч. тр. СО АН СССР. 1966. Вып. 6. С. 43-115. [ E. A. Mukhacheva, "Effective cutting of rectangular sheets to rectangular items," (in Russian), in Optimal planning: Collection of scientific papers SO AS USSR, Issue 6, pp. 43-115, 1966. ]
11. Романовский И. В. Решение задачи гильотинного раскроя методом переработки списка состояний // Кибернетика. 1969. № 1. С. 102-104. [ I. V. Romanovski, "Solution of guillotine cutting problem by the method of sorting out of the state list," (in Russian), Cybernetics, no. 1, pp. 102-104, 1969. ]
12. Мухачева Э. А. Методы условной оптимизации в задаче рационального раскроя листового проката // Оптимизация: c6. науч. тр. СО АН СССР. 1978. Вып. 22. С. 83-93. [ E. A. Mukhacheva, "Methods of conditional optimization in the problem of effective cutting of sheet rolling," (in Russian), in Optimization: Collection of scientific papers SO AS USSR, 1978, Issue 22, pp.83-93. ]
13. Романовский И. В. Программа решения задачи линейного раскроя. - Оптимальное планирование. Новосибирск. 1969. Вып.12. [ I. V. Romanovski, "Program of solving the linear cutting problem," (in Russian), in Optimal planning, Novosibirsk, 1969, Issue 12. ]
14. Картак В. М. Обновленная нижняя граница для задачи упаковки прямоугольников в полубесконечную полосу // Вестник УГАТУ. 2008. Т. 10, № 2 (27). С. 154-158. [ V. M. Kartak, "A new low bound for orthogonal packing problem," (in Russian), Vestnik UGATU, vol. 10, no. 2 (27), pp. 154158, 2008. ]
15. Belov G., Kartak V., Rohling H., Scheithauer G. One-dimensional relaxations and LP bounds for orthogonal packing // ITOR, 2009. Vol. 16. P. 745-766. [ G. Belov, et al. "One-dimensional relaxations and LP bounds for orthogonal packing," ITOR, vol. 16, p. 745-766, 2009. ]
16. Картак В. М. Матричный алгоритм поиска оптимального решения для задачи упаковки прямоугольников в полубесконечную полосу // Информационные технологии. 2008. № 2. С. 24-30. [ V. M. Kartak, "Matrix algorithm for searching the optimum solution of rectangular packing in a semi-endless strip," (in Russian), Information technologies, no. 2, pp.24-30, 2008. ]
17. Марков В. Н. База знаний для негильотинного раскроя-упаковки // Информационные технологии. 2007. № 4. С. 17-23. [ V. N. Markov, "Basic knowledge for nonguillotine cutting-packing," (in Russian), Information technologies, no 4, pp. 17-23, 2007. ]
18. Романовский И. В., Христова Н. П. Решение дискретных минимаксных задач методом дихотомии // Ж. вычислит. математики и матем. физики. 1973. Т. 13, № 5. С. 1200-1209. [ I. V. Romanovski and N. P. Hristova, "Solution of discrete minimax problems by dichotomy method," (in Russian), J. of calculat. math. and math. Physics, vol. 13, no. 5, pp. 1200-1209, 1973. ]
19. Стоян Ю. Г., Яковлев С. В. Математические модели и оптимизационные методы геометрического проектирования. Киев: Наукова думка, 1986. 268 с. [ U. G. Stojan and S. V. Jakovlev, Mathematical models and optimization methods of geometrical projecting, (in Russian). Kiev: Naukova dumka. 1986. ]
20. Рвачев В. Л., Стоян Ю. Г. К задаче об оптимальном размиещении круговых выкроек // Кибернетика. 1965. № 4. [ V. L. Rvachev and U. G. Stojan, "To the problem of optimal placement of round patterns," (in Russian), Cybernetics, no. 4, 1965. ]
21. Stoyan Y., Terno J., Romanova T., Scheithauer G.
Construction of a Ф-function for two convex polytopes // Applications Mathematicae. 2002. V. 2, No. 29. P. 199-218. [ Y. Stoyan, J. Terno, T. Romanova, and G. Scheithauer, "Construction of a Ф-function for two convex polytopes," Applications Mathematicae, vol. 2, no. 29, pp. 199-218, 2002. ]
22. Verhoturov M. A., Sergeyeva O. Y. The sequential value correction method for the two-dimensional irregular cutting stock problem // PO. 2000. Vol. 20, № 2. P. 233-247. [ M. A. Verhoturov and O. Y. Sergeyeva, "The sequential value correction method for the two-dimensional irregular cutting stock problem," vol. 20, no. 2, pp. 233-247, 2000. ]
23. Бабаев Ф. В. Рациональный раскрой листа на детали сложных геометрических конфигураций // Сварочное произв. 1968. № 8. [ F. V. Babaev, "Effective sheet cutting into items of complex geometric configurations," (in Russian), Welding production, no. 8, 1968. ]
24. Канторович Л. В., Залгаллер В. А. Рациональный раскрой промышленных материалов. 3-е изд. СПб: Невский Диалект, 2012. 304 с. [ L. V. Kantorovich and V. A. Zalgaller, Effective cutting of industrial material, Issue 3, (in Russian). St. Petersbourg: Nevskij dialect, 2012. ]
25. Соболев И. В. Управление производством пиломатериалов. М.: Лесн. пром-сть, 1981. 181 с. [ I. V. Sobolev, Timber production control, (in Russian). Moscow: Timber prod., 1981. ]
26. Кузнецов В. А., Шегельман И. Р. Применение математических методов и ПЭВМ на лесоразработках. СПб.: СПбЛТА, 1988. 68 с. [ V. A. Kuznetsov and I. R. Shegelman, Application of mathematical methods and PC in logging areas, (in Russian). St.Petersbourg: Publishing house St. Ptsb, LTA, 1988. ]
27. Кузнецов В. А. Задачи раскроя в целлюлозно-бумажной промышленности. СПб.: СПбЛТА, 2000. 132 с. [ V. A. Kuznetsov, Cutting problems in pulp and paper industry, (in Russian). St. Ptsb: Publishing house St. Ptsb. LTA, 2000. ]
28. Колоколов А. А. О числе отсекающих плоскостей в первом алгоритме Гомори // Проблемы анализа дискретной информации. Новосибирск: ИЭиОПП СО АН СССР, 1975. С. 84-96. [ A. A. Kolokolov, " About the number of cut-ting-off planes in the first algorithm of Gomory," (in Russian), in Problems of discrete information analysis, Novosibirsk: IEOIP SO AS USSR, 1975, pp.84-96. ]
29. Колоколов А. А. Регулярные разбиения и отсечения в целочисленном программировании // Сибирский журнал исследования операций. 1994. № 2. С. 18-39. [ A. A. Kolokolov, "Regular splitting and cutting off in integr programming," (in Russian), Siberian journal of operational research, no. 2, pp. 18-39, 1994. ]
30. Колоколов А. А., Коробова А. Б., Захарова Е. О., Привалова Ю.И. Разработка моделей дискретной оптимизации для формирования коллекции подростковой одежды // Омский научный вестник. 2006. № 7 (43). С. 138-140. [ A. A. Kolokolov, et al., "Development of discrete optimization models for designing teenagers" clothes," (in Russian), The Omsk scientific bulletin, no. 7 (43), pp. 138-140, 2006. ]
31. Фроловский В. Д., Фроловский Д. В. Моделирование и развертка сложных поверхностей в AutoCAD R14 // САПР и графика. 1998. № 3. С. 74-75. [ V. D. Frolovski and D. V. Frolovski, "Modeling and evolvent of complex surfaces in AutoCAD R14," (in Russian), SAD and graphics, no. 3, pp.74-75, 1998. ]
32. Ландовский В. В., Пищинская О. В., Фролов-ский В. Д. Моделирование процесса проектирования одежды на женские фигуры с нарушениями осанки. // Известия высших учебных заведений. Северо-Кавказский регион. Серия техн. наук. 2009. № 6. С. 114-118. [ V. V. Landovski, O. V. Pischinskaja, and V. D. Frolovski, "Modeling of the process of designing clothes for women"s figures of defect posture," (in Russian), Bulletin of highest schools, North-Caucasus region. Series tech. science, no. 6, pp. 114118, 2009. ]
33. Коробцева Н. А. САПР одежды: исторический экскурс и обзор существующих систем // Текстильная промышленность. 2003. № 5. С. 61-62; № 6. С. 63-65. [ N. A. Korobtsev, "SAD of clothing: historical excursus and present systems review," (in Russian), Textile industry, no. 5, pp. 61-62, no. 6, pp. 63-65, 2003. ]
34. Петунин А. А. Интегрированная САПР «Сириус» для автоматизации раскройно-заготовительного производства. Концепция. Опыт разработки и внедрения // Ресурсосберегающие технологии: математическое обеспечение оптимизационных задач в системах автоматизированного проектирования: сб. докл. 1-й Всерос. науч.-практ. конф. по вопросам решения оптимизационных задач в промышленности. СПб: ЦНИИТС, 2001. C. 126-129. [ A. A. Petunin, "Integrated SAD "Sinus" for automation of cutting--logging production. Concept. Experience of development and implementation," (in Russian), in Resource-saving technologies: Mathematical ensuring of optimization problems in systems of automat designing: Collection of reports 1st All-Union scientific--practical conference on solution of optimization problems in industry, St. Ptsb: CRITS, 2001, pp. 126-129. ]
35. Петунин А. А. Оптимизация маршрута инструмента для машин резки листового материала // Компьютерные науки и информационные технологии: Междунар. науч. изд.: матер. 13-й междунар. конф. CSIT"2011 (Гар-миш-Пантеркирхен, Германия, 27 сент. - 2 окт. 2011). Уфа, 2011. Т. 1. С. 179-182. [ A. A. Petunin, "Tool route optimization for structural sheet cutting machines," in Proc. 13th workshop on Computer Sciences and Informational Technologies, (CSIT"2011) Garmish-Panterkirhen, Germany, 2011, (in Russian), Ufa, 2011, vol. 1, pp. 179-182. ]
36. Новожилова М. В. Решение задачи поиска глобального экстремума линейной функции цели на структуре линейных неравенств: препринт. АН УССР, Ин-т проблем машиностр. Харьков, 1988. 48 с. [ M. V. Novozhilova, Solving the problem of global extremum search for linear goal function on the basis of linear inequality structure, (in Russian). Preprint. AS Ukr.SSR. Institute of engineering industry problems. Kharkov, 1988. ]
37. Кацев С. Б. Об одном классе дискретных минимаксных задач // Кибернетика. 1979. № 5. С. 139-141. [ S. B. Katsev, "About one class of discrete minimax problems," (in Russian), Cybernetics, no. 5, pp. 139-141, 1979. ]
38. Липовецкий А. И. К оптимизации свободного размещения прямоугольников // Автоматизация проектирования в машиностроении. 1985. С. 80-87. [ A. I. Lipovetski, "To optimization of rectangular free placement," (in Russian), Automation design in engineering industry, Minsk, pp. 80-87, 1985. ]
39. Аккуратов Г. В., Березнев В. А., Брежнева О. А.
О методе решения уравнения с булевыми переменными // Принятие решений в условиях неопределенности: межвуз. науч. сб. Уфа: УАИ, 1990. С. 145-154. [ G. V. Accuratov, V. A. Bereznev, and O. A. Brezhneva, "About the method of solving equation with Boolean variables," (in Russian), Making decision under uncertainty conditions. Interinstitute scientific collection, Ufa: USATU, pp. 145-154, 1990. ]
40. Mukhacheva E. A., Zalgaller V. A. Linear programming cutting problems // Int. J. of Software Engineering and Knowledge Engineering. 1993. V. 3, No. 4. P. 463-476. [ E. A. Mukhacheva and V. A. Zalgaller, "Linear programming cutting problems," Int. J. of Software Engineering and Knowledge Engineering, vol. 3, no. 4, pp. 463-476, 1993. ]
41. Мухачева А. С., Валеева А. Ф., Картак В. М. Задачи двумерной упаковки в контейнеры: новые подходы к разработке методов локального поиска оптимума. М.: МАИ, 2004. 193 с. [ A. S. Mukhacheva, A. F. Valeeva, and V. M. Kartack, Problems of 2D packings into containers: new approaches to development of local optimum search methods, (in Russian). Moscow: MAI, 2004. ]
42. Мухачева А. С. Технология блочных структур локального поиска оптимума в задачах прямоугольной упаковки // Информационные технологии. Приложение. 2004. № 5. С. 18-31. [ A. S. Mukhacheva, "Technology of block structures for optimumlocal search in rectangular bin-packing problems", (in Russian), in in Appendix to Magazine Information technologies. Appendix, no. 5, pp. 18-31, 2004. ]
43. Кочетов Ю. А. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискретная математика и ее приложения: c6. лекций молодежн. и науч. шк. по дискретной математике и ее приложениям. М.: Изд-во центра прикладных исследований при мех.-матем. ф-те МГУ, 2000. С. 87-117. [ U. A. Kochetov, "Probabilistic methods of local search for discrete optimization problems," (in Russian), in Discrete mathematics and its application. Collection of lectures of student and scientific schools on discrete mathematics and its applications, Moscow: Publishing house of the applied research center of the mech.-maths depart. MSU, 2000, pp. 87-117. ]
44. Норенков И. П. Эвристики и их комбинации в генетических методах дискретной оптимизации. // Информационные технологии. 1999. № 1. С. 2-7. [ I. P. Norenkov, "Heuristics and their combinations in discrete optimization genetic methods," (in Russian), in Appendix to Magazine Information technologies, no. 1, pp. 2-7, 1999. ]
45. Мухачева А. С., Чиглинцев А. В., Смагин М. А., Мухачева Э. А. Задачи двумерной упаковки: развитие генетических алгоритмов на базе смешанных процедур локального поиска оптимального решения // Информационные технологии. Приложение. 2001. № 9. 28 c. [ A. S. Mukhacheva, et al., "2D bin--packing problems: development of genetic algorithms based on compound procedures of local search for optimal solution," (in Russian), in Appendix to Magazine Information technologies, no. 9, 2001. ]
46. Frolovsky V. D., Pushkaryova G. V. Metal cutting motion optimization for NC-programs design, using genetic algorithms. Proc. of the 6th Int. Conf. on Computer Graphics and Artificial Intelligence, Limoges (France), May 14-15, 2003. P. 143-152. [ V. D. Frolovsky and G. V. Pushkaryova, "Metal cutting motion optimization for NC-programs design, using genetic algorithms," Proc. of the 6th Internat. Conf. on Computer Graphics and Artificial Intelligence, Limoges (France), May 14-15, 2003, pp. 143-152. ]
47. Корчевская О. В., Жуков Л. А. Получение нижних границ для задач двух и трехмерной ортогональной упаковки [Электронный ресурс] // Исследовано в России: электронный журнал. 2008. 62. С. 685-694. URL: http:// zhurnal.ape.relarn/articles/2008/062.pdf [ O. V. Korchevskaja, L. A. Zhukov, "Low boundaries procure for 2G and 3D orthogonal bin-packing problems," (in Russian), Electronic magazine "Investigated in Russia", 62, 2008. pp. 685-694, http:// zhurnal.ape.relarn/articles/2008/062.pdf ]
48. Mukhacheva E., ed. Special issue: Decision making under conditions of uncertainty (cutting-packing problems) // The International Scientific Collection. 1997. Ufa, Russia. [ E. Mukhacheva, ed. Special issue: Decision making under conditions of uncertainty (cutting-packing problems). The International Scientific Collection, Ufa, Russia, 1997. ]
49. Sergeyeva O., Scheithauer G., Terno J. The value correction method for packing of irregular shapes // Decision making under conditions of uncertainty (cutting-packing problems): The Int. Sci. Collection. Ufa, 1997. P. 261-270. [ O. Sergeyeva, G. Scheithauer, and J. Terno, "The value correction method for packing of irregular shapes," Decision making under conditions of uncertainty (cutting--packing problems). The International Scientific Collection, Ufa, 1997, pp. 261-270. ]
50. Belov G., Kartak V., Rohling H., Scheithauer G. One-dimensional relaxations and LP bounds for orthogonal packing. ITOR, 2009. V. 16. P. 745-766. [ G. Belov, et al., "One-dimensional relaxations and LP bounds for orthogonal packing," ITOR, vol. 16, pp. 745-766, 2009. ]
51. Фроловский В. Д. Параметрическое моделирование и идентификация трехмерных объектов со сложной структурой // Информационные системы и технологии: матер. Междунар. науч.-техн. конф.. Новосибирск: НГТУ, 2003. Т. 1. С. 153-155. [ V. D. Frolovski, "Parametric simulation and identification of 3D objects with complicated structure," (in Russian), in Proc. Int. Sci.-Tech. Conference "Informational Systems and Tecnnologies", Novosibirsk, NGTU, 2003, vol. 1, pp. 153-155. ]
52. Колоколов А. А., Нагорная З. Е., Архимен-ко М. Ю., Иванова С. Д. Проектирование меховых изделий с использованием математического моделирования // Динамика систем, механизмов и машин: матер. IV Междунар. науч.-техн. конф., посвящ. 60-летию ОмГТУ. Кн. 1. Омск: ОмГТУ, 2002. С. 297-299. [ A. A. Kolokolov, et al., "Fur goods design using mathematical modeling, Dynamics of systems, mechanisms and machines," (in Russian), in Proc. 4 Int. Sci.-Tech. Conference to the 60 anniversary of OmGTU, vol.1, Omsk, 2002, pp. 297-299. ]
53. Панюкова Т. А. Оптимальные Эйлеровы покрытия с упорядоченным охватыванием для плоских графов // Дискретный анализ и исследование операций. Март-апрель, 2011. Т. 18, № 2. С. 64-74. [ T. A. Panukova, "Optimal Euler coverings with ordered union for flat graphs," (in Russian), in Discrete analysis and operational research, MarchApril, vol. 18, no. 2, pp. 64-74, 2011. ]
54. Новиков И. С. Автоматическое размещение разногабаритных электронных элементов посредством генетического поиска с миграцией // Проектирование и технология электронных средств. 2007. № 1. C. 33-38. [ I. S. Novikova, "Automatical allocation of electronic elements of different sizes by genetic search with migration," (in Russian), in Design and technology of electronic facility, no. 1, pp. 33-38, 2007. ]
55. Мухачева Э. А., Валеев Р. С. Локальный поиск размещения товарных позиций на базе анализа их номенклатурной принадлежности // Информационные технологии. 2010. № 6. С. 18-23. [ E. A. Mukhacheva and R. S. Valeev, "Local search of Commodity allocation based on their product range," (in Russian), in Informational Technologies, no. 6, pp. 18-23, 2010. ]
56. Мухачева Э. А., Бухарбаева Л. Я., Филиппов Д. В., Карипов У. А. Оптимизационные проблемы транспортной логистики: оперативное размещение контейнеров при транспортировке грузов // Информационные технологии. 2008. № 7. С. 17-22. [ E. A. Mukhacheva, et al., "Optimization problems of transportation logistics; containers operational allocation while cargo conveying," (in Russian), Information Technologies, no. 7, pp. 17-23, 2008. ]
57. Телицкий С. В., Филиппова А. С. Комплексный подход к решению задачи покрытия области заготовками неопределенных размеров // Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации. Управле-
ние. 2 (145) / 2012, СПб., 2012. С. 61-67. [ S. V. Telitskiy and A. S. Filippova, "Complex approach to solving the problem of area covering with items of non-defined sizes," (in Russian), in Nauchno-tehnicheskye Vedomosty SPbGPU, Informatics. Telecommunication. Management, 2(145)/2012, StPsb, pp. 61-67, 2012. ]
58. Васильева Л. И. Алгоритмы упаковки N-мерных гофров на базе методов линейного программирования: дис. ... канд. техн. наук / УГАТУ, 2000. [ L. I. Vasilyeva, "Packing algorithms od N-dimensionv corrugations based on linear programming methods," (in Russian): Dissertation for scientific degree of a Cand. of Tech. Sci, UGATU, 2000. ].
59. Картак В. М. Модели и методы оптимизации упаковки n-мерных параллелепипедов: дис. ... канд. физ.-мат. наук / УГАТУ, 1999. [ V. M. Kartak, "Models and methods of optimization of n-dimensional parallelepiped packing," (in Russian): Dissertation for scientific degree of a Cand. of phisics-maths Sci, UGATU, 1999. ]
ВАЛИАХМЕТОВА Юлия Ильясовна, доц. каф. математики. Дипл. инж. (УГАТУ, 2004). Канд. техн. наук по мат. моде-лир., числ. методам и комплексам программ (УГАТУ, 2008). Иссл. в обл. оптимизац. задач раскроя-упаковки. ФИЛИППОВА Анна Сергеевна, проф. каф. прикладной информатики. Дипл. инж. (УГАТУ, 1996). Д-р техн. наук мат. моделир., числ. методам и комплексам программ (СГАУ, 2007). Иссл. в обл. комбинаторных алгоритмов.
Title: Theory of optimum resource utilization by L. V. Kanto-rovich in cutting-packing problems: overview and history of development of solving methods Authors: Yu. I. Valiakhmetova, A. S. Filippova. Affiliation:
1 Bashkir State Agrarian University (BSAU), Russia.
2 Bashkir State Pedagogical University of M. Akmulla(BSPU), Russia.
Email: [email protected], [email protected]. Language: Russian.
Source: Vestnik UGATU (scientific journal of Ufa State Aviation Technical University), vol. 18, no. 1 (62), pp. 186-197, 2014. ISSN 2225-2789 (Online), ISSN 1992-6502 (Print). Abstract: The article presents examples of solution techniques for cutting-packing problems, which are still relevant to this day taking into account their diversity and many-sided applicability. The scientific papers by L. V. Kantorovich are considered to be fundamental for the development of these procedures. The article gives an overview of procedures for solving cutting-packing problems that have been developed by Soviet and Russian scientists in the last 80 years, including various scientific schools of the USSR and Russia. Summary of solving procedures and the history of their development are also described. Key words: cutting, optimum use of resources, optimization, exact methods, heuristic methods.
VALIAKHMETOVA, Yuliya Ilyasovna, Associate Prof., Dept. of Mathematics, Dipl. Engineer-programmer (UGATU, 2004). Cand. of Tech. Sci. (UGATU, 2008). FILIPPOVA, Anna Sergeevna, Prof., Dept. of Applied Informatics. Dipl. Systems Engineer (UGATU, 1996). Cand. of Tech. Sci. (Ufa State Univ., 1999)., Dr. of Tech. Sci. (Samara State Aerospace Univ., 2007).
«за вклад в теорию оптимального распределения ресурсов»
Русский экономист Леонид Витальевич Канторович родился в 1912 г. в Санкт-Петербурге, Россия. Русская революция началась, когда ему было пять лет, во время гражданской войны его семья бежала на год в Белоруссию. В 1922 г. умер его отец, Виталий Канторович, оставив сына на воспитание матери, урожденной Паулины Сакс.
К. проявлял интерес к естественным наукам задолго до того, как он в 1926 г. в возрасте четырнадцати лет поступил в Ленинградский университет. Здесь он изучает не только естественные дисциплины, но и политэкономию, современную историю, математику. Его склонность к математике становится определяющей в работе по теории рядов, которую он представил на первом Всесоюзном математическом конгрессе в 1930 г. Закончив в том же году учебу, он остается в Ленинградском университете на преподавательской работе и продолжает свои исследования на кафедре математики. К 1934 г. он становится профессором, а годом позже, когда была восстановлена система академических степеней, получает докторскую степень.
В 30-е гг., в период интенсивного экономического и индустриального развития Советского Союза, К. был в авангарде математических исследований и стремился применить свои теоретические, разработки в практике растущей советской экономики. Такая возможность представилась в 1938 г., когда он был назначен консультантом в лабораторию фанерной фабрики. Перед ним была поставлена задача разработать такой метод распределения ресурсов, который мог бы максимизировать производительность оборудования, и К., сформулировав проблему с помощью математических терминов, произвел максимизацию линейной функции, подверженной большому количеству ограничителей. Не имея чистого экономического образования, он тем не менее знал, что максимизация при многочисленных ограничениях – это одна из основных экономических проблем и что метод, облегчающий планирование на фанерных фабриках, может быть использован во многих других производствах, будь то определение оптимального использования посевных площадей или наиболее эффективное распределение потоков транспорта.
Метод К., разработанный для решения проблем, связанных с производством фанеры, и известный сегодня как метод линейного программирования, нашел широкое экономическое применение во всем мире. В работе «Математические методы организации и планирования производства», опубликованной в 1939 г., К. показал, что все экономические проблемы распределения могут рассматриваться как проблемы максимизации при многочисленных ограничителях, следовательно, могут быть решены с помощью линейного программирования.
В случае с производством фанеры он представил переменную, подлежащую максимизации, в виде суммы стоимостей продукции, выпускаемой всеми машинами. Ограничители были представлены уравнениями, которые устанавливали соотношение между количеством каждого из расходуемых факторов производства (например, древесины, электроэнергии, рабочего времени) и количеством продукции, выпускаемой каждой из машин, где величина любой из затрат не должна превышать имеющуюся в распоряжении сумму.
Затем К. ввел новые переменные (разрешающие мультипликаторы) как коэффициенты к каждому из факторов производства в ограничительных уравнениях и показал, что значения как переменной затрачиваемых факторов, так и переменной выпускаемой продукции могут быть легко определены, если известны значения мультипликаторов. Затем он представил экономическую интерпретацию этих мультипликаторов, показав, что они, в сущности, представляют собой предельные стоимости (или «скрытые цены») ограничивающих факторов; следовательно, они аналогичны повышенной цене каждого из факторов производства в режиме полностью конкурентного рынка.
И хотя с тех пор разрабатывались более совершенные компьютерные методики для определения значений мультипликаторов (К. использовал метод последовательного приближения), его первоначальное понимание экономического и математического смысла мультипликаторов заложило основу для всех последующих работ в этой области в Советском Союзе. Впоследствии сходная методология была независимо разработана на Западе Тьяллингом Ч. Купмансом и другими экономистами.
Даже в тяжелые годы второй мировой войны, когда К. занимал должность профессора в Военно-морской инженерной академии в блокадном Ленинграде, он сумел создать значительное исследование «О перемещении масс» (1942). В этой работе он использовал линейное программирование для планирования оптимального размещения потребительских и производственных факторов.
Продолжая работать в Ленинградском университете, К. одновременно возглавил отдел приближенных методов в Институте математики АН СССР в Ленинграде. В последующие несколько лет он способствовал развитию новых математических методов планирования для советской экономики. В 1951 г. он (совместно с математиком, специалистом в области геометрии В.А. Залгаллером) опубликовал книгу, описывающую их работу по использованию линейного программирования для повышения эффективности транспортного строительства в Ленинграде. Через восемь лет он опубликовал самую, видимо, известную свою работу «Экономический расчет наилучшего использования ресурсов». В ней он сделал далеко идущие выводы по идеальной организации социалистической экономики для достижения высокой эффективности в использовании ресурсов. В особенности он рекомендовал шире использовать скрытые цены при распределении ресурсов по Союзу и даже применять процентную ставку для выражения скрытой цены времени при планировании капиталовложений.
Хотя некоторые советские ученые с опаской относились к этим новым методам планирования, постепенно методы К. были приняты советской экономикой. В 1949 г. он был удостоен Сталинской премии за работу в области математики, в 1958 г. избран членом-корреспондентом Академии наук СССР. Шестью годами позже он стал академиком. В 1960 г., переехав в Новосибирск, где был расположен самый передовой в СССР компьютерный центр, он стал руководителем отдела экономико-математических методов в Сибирском отделении АН СССР. Вместе со своими коллегами, экономистами-математиками В.В. Новожиловым и В.С. Немчиновым, К. стал лауреатом Ленинской премии в 1965 г., а в 1967 г. был награжден орденом Ленина. В 1971 г. он становится руководителем лаборатории в Институте управления народным хозяйством в Москве.
Премия памяти Нобеля 1975 г. по экономике была присуждена совместно К. и Тьяллингу Ч. Купмансу «за вклад в теорию оптимального распределения ресурсов». В своей речи на церемонии презентации представитель Шведской королевской академии наук Рагнар Бентцель отмечал очевидность того, о чем свидетельствовали работы двух лауреатов, – «основные экономические проблемы могут изучаться в чисто научном плане, независимо от политической организации общества, в котором они исследуются». Работы Купманса и К. по линейному программированию тесно соприкасались, а американский ученый подготовил в 1939 г. первую публикацию книги советского ученого на английском языке. В своей Нобелевской лекции «Математика в экономике: достижения, трудности, перспективы» К. говорил о «проблемах и опыте плановой экономики, особенно советской экономики».
В следующем году К. стал директором Института системных исследований АН СССР. Проводя собственные исследования, он в то же время поддерживал и обучил целое поколение советских экономистов.
В 1938 г. К. женился на Наталье Ильиной, враче по профессии. Их дети – сын и дочь – стали экономистами. К. скончался 7 апреля 1986 г. в возрасте 74 лет.
Кроме Нобелевской премии и наград, полученных в СССР, К. были присуждены почетные степени университетами Глазго, Гренобля, Ниццы, Хельсинки и Парижа; он был членом Американской академии наук и искусств.
