До середины ХХ в. экономисты-теоретики игнорировали математические модели исследования. Однако, несмотря на притеснения, математики продолжали работать и достигли блестящих результатов. Среди них - представители математической школы Л. Канторович и Т.-Ч. Купманс.
Канторович (Kantorovich) Леонид Витальевич (1912-1986) - советский экономист, лауреат Нобелевской премии (1975).
Теория оптимального распределения ресурсов - теория, которая предусматривает формулирование статистической и динамической моделей текущего и перспективного планирования использования ресурсов на базе новых математических подходов в сфере системного построения экономических показателей, используемых для анализа ценообразования, эффективности капитальных вложений.
Впервые основы теории оптимального распределения ресурсов он изложил в работе «Математические методы организации и планирования производства» (1939). В ней он представил принципиально новый класс экстремальных задач с ограничениями, разработав эффективный метод их решения. Именно в это время ученый сформулировал задачу составления плана и системы цен как взаимозависимых компонентов неделимой двойственности. Ведь время невозможно одновременно минимизировать издержки и максимизировать результаты. Одновременно эти два подхода взаимосвязаны: если найдем оптимальную схему перевозок, то ей соответствует определенная система цен. Если определим оптимальные значения цен, то сравнительно легко получить схему перевозок, что соответствует требованиям оптимальности.
Основой этой теории является метод линейного программирования. Линейное программирование - решение линейных уравнений (уравнений первой степени) путем сложения программ и внедрения разных методов их последовательного решения, что существенно облегчает расчеты и достижение результатов.
Л. Канторович обосновал экономическую сущность предлагаемых им решающих множителей. Они, собственно, являются предельными стоимостями ограничивающих факторов. То есть это объективные цены каждого из факторов производства относительно условий конкурентного рынка. Для решения задачи на оптимальность ученый использовал метод последовательных приближений, последовательного сопоставления вариантов с выбором наилучшего в соответствии с условиями задачи.
Задачи линейного программирования были известны еще в конце ХVIII в. Однако начали решать их только после публикаций работ Л. Канторовича. В США исследования по линейному программированию начались только в конце 40-х годов ХХ в. Транспортная задача Хичкока и симплекс-метод Данцига, которые близки по характеру к методу решения задач линейного программирования Канторовича, были разработаны на десятилетие позднее.
Целостность мышления проявлялась во всем творчестве Канторовича. Идеи линейного программирования были тесно связаны с его методологическими установками в области математики. В середине 1930 годов центральное место в математических исследованиях Канторовича занимал функциональный анализ.
Труды Канторовича заложили фундамент теории оптимального планирования социалистической экономики, вплоть до конца 80-х годов широко используемой в практике планирования экономического развития в СССР, а также в других социалистических странах. Основные идеи теории оптимального планирования изложены в монографии "Экономический расчет наилучшего использования ресурсов" (1959, 1960), являющейся наиболее известной работой ученого. Стержнем этой книги являлась формулировка основной задачи производственного планирования и динамической задачи оптимального планирования. Указанные задачи формулировались достаточно просто, но они учитывали основные черты планирования в советской экономике.
Похожая информация:
- amp; 1. Понятие следственного эксперимента, его видыи значение
Первые научные результаты были получены Л.В. Канторовичем в дескриптивной теории функций и множеств, в частности в теории проективных множеств. В 1939 г. ученый опубликовал работу «Математические методы организации и планирования производства». В ней он описал основные типы экономических задач, поддающиеся открытому им математическому методу, положив тем самым начало линейному программированию.
В 1949 г. Л.В. Канторович стал лауреатом Государственной премии СССР «За работы по функциональному анализу», в 1958 г. — был избран членом-корреспондентом АН СССР (экономика и статистика), а в 1964 г. — академиком АН СССР Он являлся одним из основателей Сибирского отделения АН СССР. В 1960 г. переехал в Новосибирск, где руководил Лабораторией по применению математических и статистических методов в экономических исследованиях и планировании, а также преподавал в Новосибирском университете. В 1965 г. ученый удостаивается Ленинской премии, затем становится почетным доктором многих университетов мира.
Свой путь в науке Канторович начинал как математик, но известность в науке он получил именно как математик-экономист, когда сформулировал и предложил решение задач, получивших название «задачи линейного программирования». В 1959 г. была опубликована работа, которую ученый считал главной: «Экономический расчет наилучшего использования ресурсов».
Но не все его предложения находили понимание у высших представителей власти. Поэтому в Академии наук СССР была создана специальная лаборатория по применению математики в экономике во главе с академиком B.C. Немчиновым. В 1965 г. Л.В. Канторович вместе с В.В. Новожиловым и B.C. Немчиновым стал лауреатом Ленинской премии за развитие математико-экономического направления. После этого нападки на Канторовича резко сократились, хотя не желавшие использовать оптимизационные методы руководители разного уровня остались. Здесь сказался еще непознанный тогда закон поведения экономических систем, обоснованный профессором К.А. Смирновым в 80-х гг.
В плановой экономике утвержденный план работы любой экономической системы (ЭС) становился законом. А оптимальный план, уже по самому его определению, был напряженным, в нем отсутствовали скрытые резервы, которые руководителям экономических систем все же удавалось находить.
В 1975 г. за разработку задачи линейного программирования и метода ее решения Л.В. Канторович был награжден Нобелевской премией с формулировкой «За разработку методов эффективного использования ресурсов».
В целом вклад ученого в науку можно коротко охарактеризовать следующим образом:
1) он впервые обратил внимание на то, что разнообразные проблемы можно сформировать как задачи оптимизации и предложил общий подход к их решению. Это задачи по загрузке оборудования, по раскрою материалов, распределению культур по площадям, транспортная задача;
2) создал теорию оптимального народно-хозяйственного планирования — по сути дела предложил модель рыночного социализма. Ввел новые показатели — разрешающие множители, объективно обусловленные оценки, двойственные оценки — эти показатели дают возможность отбирать проекты для составления оптимального плана, согласовывать народно-хозяйственные интересы с интересами отдельных экономических систем (хозяйственных единиц);
3) разработал систему оптимального планирования, которая вступила в противоречие с господствовавшей тогда трудовой теорией стоимости. Представители этой теории не признавали вводимые Канторовичем ограничения не только на объем труда, но и на объемы других невоспроизводимых ресурсов (земля, полезные ископаемые). Кроме того, задача разработки оптимального плана требовала для решения вычислительные средства большой мощности. Рекомендации, вытекавшие из теории оптимального планирования, предполагали использование оценок оптимальных цен, которых не было в реальности, — действовали цены, не балансировавшие спрос и предложение. Существовала и проблема глобального критерия, который должен учитывать интересы разных групп населения и экономических систем (предприятий, отраслей).
Л.В. Канторовича можно считать основоположником науки об управлении и принятии управленческих решений, основная задача которой — применение естественно-научного метода к анализу задач организационного управления с тем, чтобы снабдить тех, кто управляет, оптимальными решениями.
Развивая идею оптимальности в экономике, он установил взаимозависимость оптимальных цен и оптимальных производственных и управленческих решений и пришел к выводу, что каждое оптимальное решение взаимосвязано с оптимальной системой цен. Работая над общей теорией приближенных методов, он предложил эффективные способы решения операторных уравнений (в том числе метод наискорейшего спуска и метод Ньютона для таких уравнений).
Работы Л.В. Канторовича (он автор более 110 научных трудов) посвящены оптимизации организации и планирования производства, линейному программированию, экономической кибернетике, экономическим показателям, ценообразованию. Среди трудов ученого особо выделяют: «Экономический расчет наилучшего использования ресурсов» (1959), «Динамическая модель оптимального планирования» (1964), «Математика и экономика — взаимопроникновение наук» (1977, совместное М.К. Гавуриным).
Неоспоримым вкладом в теорию и практику оптимального планирования стало открытие Канторовичем методов линейного программирования. Предложив новый математический аппарат для экономической науки, он впервые поставил задачу хозяйственного планирования как задачу оптимизации. Именно за решение этой и других задач в 1975 г. ему совместно с американским экономистом Т. Купмансом была присуждена Нобелевская премия по экономике.
Л.В. Канторович также выявил необходимость введения оценок для всех видов затрачиваемых производственных факторов при составлении производственных планов. В связи с этим он предложил классификацию производственных факторов, выделяя четыре группы:
1) пропорционально зависимые (определенное количество шин для автомобиля);
2) неизменно расходуемые (охрана, управленческие расходы и т.д.);
3) нелимитирующие (избыточные);
4) существенно переменные, т.е. факторы, имеющиеся в ограниченном количестве, расход которых на единицу продукции зависит от организации и технологии производства. Наиболее значительными факторами являются рабочая сила, природные ресурсы и производственные площади.
В предложенной ученым системе экономических расчетов дефицитные ресурсы получают высокую оценку, а имеющиеся в избытке — нулевую. Система экономических расчетов, использующая объективно обусловленные оценки, позволяет на основе определения дефицитности, лимитированности и задолженности производственных факторов найти такой вариант их использования, который бы обеспечил при данных ресурсах максимальное выполнение программного задания с учетом ассортимента.
Особенно важным является вопрос о наилучшем использовании оборудования. Здесь ученый ввел весьма ценное понятие «прокатной оценки» — ренты с оборудования. Он писал: «Мы употребляем термин "прокатная оценка", так как это есть оценка той платы, которая была бы оправдана, если бы такая машина бралась на некоторый срок напрокат (в аренду). Можно ее рассматривать также как ренту с оборудования, которую мы хотя и не оплачиваем, но исчисляем ее возможный размер». Таким образом, если не использовать в течение дня данную машину, значит, потерять определенную сумму денег и, следовательно, количество труда, которые соответствуют прокатной оценке, а ее использование, напротив, позволит сэкономить эту же сумму. Например, Л.В. Канторович рассчитал, что использование каждого машино-дня дает экономию в себестоимости в сумме 600 руб., т.е. использование каждой лишней машины позволяет сэкономить в день 600 руб., а не использование приводит к потере этих 600 руб. В данном случае 600 руб. — это и есть прокатная оценка.
С вопросом о рациональном использовании оборудования тесно связана и проблема рационального использования природных ресурсов. Последние всегда ограниченны, поэтому значительное внимание ученый уделял теории дифференциальной ренты. Величина ренты определяется, как он утверждал, той экономией труда, которую дает использование этих источников в оптимальном плане. Рентные оценки, по его мнению, позволяют измерить стоимость использования природных ресурсов, в частности земли, воды, воздуха и т.д. Эта идея намного опередила свое время. Однако в конце 1930-х гг. она пришла в противоречие с концепцией общенародной собственности на природные ресурсы, из которой вытекало, что к ним не применимы стоимостные показатели, так как они выделялись «даром». Двойственные оценки материальных ресурсов были расценены как попытка подменить трудовую основу стоимости понятием полезности или дефицитности. Сам же Л.В. Канторович рассматривал созданную им теорию как научную базу для всей системы народно-хозяйственных расчетов.
Проблеме динамического программирования ученый посвятил свою работу «Динамическая модель оптимального планирования» (1964). Он впервые построил оптимальные статичные и динамические модели текущего и перспективного планирования. К постановке и анализу динамических задач он пришел, анализируя недостатки статичной оптимизации. Многие задачи оптимизационного программирования расчленяются, как известно, на этапы (шаги), и для их решения весьма эффективным является метод динамического программирования, развитый впоследствии Р. Беллманом и его школой. Следует отметить, что использование динамических экономико-математических моделей стало практиковаться в нашей стране лишь с середины 1960-х гг.
Обобщая сказанное, отметим, что Л.В. Канторович — яркий представитель петербургской математической школы, созданной талантливейшим русским математиком П.Л. Чебышевым (1821 — 1894), умевшим элементарными средствами получать фундаментальные результаты, связывать проблемы математики с принципиальными вопросами естествознания и техники, впервые доказавшим в теории вероятностей действие закона больших чисел (в общей форме), а в теории чисел — асимптотический закон распределения простых чисел и др.
|
|
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).
Князева А., Лыкова Н.П.
ГОУ ВПО «Российский государственный гуманитарный университет»
Филиал в г. Самаре
постановка Задач линейного программирования и их решение с помощью msexcel
Временем рождения линейного программирования принято считать 1939г., когда была напечатана брошюра Леонида Витальевича Канторовича "Математические методы организации и планирования производства". Поскольку методы, изложенные Л.В.Канторовичем, были мало пригодны для ручного счета, а быстродействующих вычислительных машин в то время не существовало, работа Л.В.Канторовича осталась почти не замеченной.
Свое второе рождение линейное программирование получило в начале пятидесятых годов с появлением ЭВМ. Тогда началось всеобщее увлечение линейным программированием, вызвавшее в свою очередь развитие других разделов математического программирования. В 1975 году академик Л.В.Канторович и американец профессор Т. Купманс получили Нобелевскую премию по экономическим наукам за "вклад в разработку теории и оптимального использования ресурсов в экономике".
Было осознано, что надо научиться решать задачи о нахождении экстремумов линейных функций на многогранниках, задаваемых линейными неравенствами. По предложению Купманса этот раздел математики получил название линейного программирования.
Американский математик А. Данциг в 1947 году разработал весьма эффективный конкретный метод численного решения задач линейного программирования (он получил название симплекс метода). Идеи линейного программирования в течении пяти шести лет получили грандиозное распространение в мире, и имена Купманса и Данцига стали повсюду широко известны.
Задачи оптимального планирования, связанные с отысканием оптимума заданной целевой функции (линейной формы) при наличии ограничений в виде линейных уравнений или линейных неравенств относятся к задачам линейного программирования.
Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования.
Круг задач, решаемых при помощи методов линейного программирования достаточно широк:
задача об оптимальном использовании ресурсов при производственном планировании;
задача о смесях (планирование состава продукции);
задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке");
транспортные задачи (анализ размещения предприятия, перемещение грузов).
Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных.
В общем виде модель записывается следующим образом:
целевая функция: F(x)= c 1 x 1 + c 2 x 2 + ... + cnxn → max(min) (1)
ограничения:
a 11 x 1 + a 12 x 2 + ... + a 1n xn {≤ = ≥} b 1 ,
a 21 x 1 + a 22 x 2 + ... + a 2n xn {≤ = ≥} b 2 , (2)
a m1 x 1 + a m2 x 2 + ... + a mn xn {≤ = ≥} b m ;
требование неотрицательности: x j ≥ 0, j = 1, 2,……, n (3)
При этом a ij , b i , c j (I = 1, 2, ….., m; j = 1, 2,……, n) - заданные постоянные величины .
Задача состоит в нахождении оптимального значения функции (1) при соблюдении ограничений (2) и (3).
Систему ограничений (2) называют функциональными ограничениями задачи , а ограничения (3) - прямыми .
Вектор, удовлетворяющий ограничениям (2) и (3), называется допустимым решением (планом) задачи линейного программирования. План, при котором функция (1) достигает своего максимального (минимального) значения, называется оптимальным .
Задачи линейного программирования можно решать вручную, т.е. алгебраически и графически, а можно при помощи MS Excel. Эта программа позволяет быстро и легко решить задачи линейного программирования.
Разберём решение таких задач на конкретном примере:
На звероферме могут выращиваться черно-бурые лисицы и песцы. Для обеспечения нормальных условий их выращивания используется три вида кормов. Количество корма каждого вида, которое должны ежедневно получать лисицы и песцы, приведено в таблице. В ней же указаны общее количество корма каждого вида, которое может быть использовано зверофермой, и прибыль от реализации одной шкурки лисицы и песца.
| Вид корма | Ежедневное количество корма усл. ед. | Общее количество корма, усл.ед. | |
| Прибыль от реализации одной шкурки, руб. | |||
Определить, сколько лисиц и песцов следует выращивать на звероферме, чтобы прибыль от реализации их шкурок была максимальной.
Запишем математическую модель:
Х шт – лисицы, У шт - песцы
16x+12y - max (1)
Решение данной задачи аналитически сводится к решению системы из трёх неравенств (2-4), выражая значение одной переменной через другую получаем:
х 90 – 1,5у
4(90 – 1,5у) + у 240
6(90 – 1,5у) + 7у 426
х 1 54 х 2 4,5
у 1 24 у 2 57
причём х 2 и у 2 не удовлетворяют решению, т.к. количество зверей не может быть дробным числом.
Следовательно, целевая функция будет равна: 1152
Однако, с помощью MS Excel решение гораздо проще и быстрее.
Для решения задачи в MS Excel, необходимо создать таблицу с исходными данными (рис. 1)
Рис.1 – Таблица с исходными данными (задача на оптимизацию производства)
Затем с помощью встроенных функций MS Excel (=СУММПРОИЗВ) ввести ограничения и целевую функцию (рис.2)
Рис. 2 – ограничения и целевая функция
После того, как все ограничения и целевая функция введены, следует воспользоваться встроенной программой MS Excel Поиск решения (рис. 3), в которой также вводятся целевая функция, ограничения, а также изменяемые ячейки (т.е. неизвестные переменные).
Рис. 3 – Поиск решения
Однако прежде чем приступить к решению необходимо также во вкладке параметры поиска решения задать: линейная модель, неотрицательные значения и автоматическое масштабирование (рис. 4)
Рис. 4 – Параметры поиска решения
После завершения ввода всех ограничений и параметров мы получаем искомое решение задачи (рис. 5)
Рис. 5 – Итоговая таблица, с полученным решением
На практике многие экономические параметры (цены на продукцию и сырье, запасы сырья, спрос на рынке, заработная плата и т.д.) с течением времени меняют свои значения. Поэтому оптимальное решение задачи ЛП, полученное для конкретной экономической ситуации, после ее изменения может оказаться непригодным или неоптимальным. В связи с этим возникает задача анализа чувствительности задачи ЛП, а именно того, как возможные изменения параметров исходной модели повлияют на полученное ранее оптимальное решение.
Связывающие ограничения проходят через оптимальную точку. Несвязывающие ограничения не проходят через оптимальную точку. Ресурс, представляемый связывающим ограничением, называют дефицитным, а ресурс, представляемый несвязывающим ограничением, – недефицитным. Ограничение называют избыточным в том случае, если его исключение не влияет на область допустимых решений и, следовательно, на оптимальное решение.
Выделяют следующие три задачи анализа на чувствительность.
1. Анализ сокращения или увеличения ресурсов:
1) на сколько можно увеличить или уменьшить запас дефицитного ресурса для улучшения оптимального значения ЦФ?
2) на сколько можно уменьшить или увеличить запас недефицитного ресурса при сохранении полученного оптимального значения ЦФ?
2. Увеличение (уменьшение) запаса какого из ресурсов наиболее выгодно?
3. Анализ изменения целевых коэффициентов: каков диапазон изменения коэффициентов ЦФ, при котором не меняется оптимальное решение?
MS Excel позволяет делать отчет по результатам, который состоит из 3 таблиц:
1 – Целевая ячейка. В ней отображается начальное значение целевой функции и оптимальное (результат).
2- Изменяемые ячейки. В ней отражены исходные значения переменных и результирующие (оптимальные). Если продукт не входит в оптимальное решение (равен 0), то он считается не рентабельным.
3- Ограничения. Кроме имени ограничения, ячейки, в которую вписана левая часть ограничения, в ней отображены столбцы:
Значение – значение левой части ограничения при оптимальном плане. Т.е. сколько фактически использовано ресурса.
Формула – отображается знак ограничения (больше или равно, меньше или равно и т.д.)
Статус – отображено Связанное или не связанное ограничение. Если статус связанное, то ресурс использован полностью. Если же статус – не связанное, то ресурс использован не полностью.
Разница – отображено количество оставшегося не использованным ресурса.
А также отчет по устойчивости, который состоит из 2 таблиц:
1 – изменяемые ячейки. Кроме имени переменных и адресов ячеек в ней присутствуют столбцы:
Результирующее значение – это оптимальный план.
Нормированная (редуцированная) стоимость – показывает, на сколько изменится целевая функция после принудительного включения единицы этой продукции в оптимальный план. Если продукт рентабелен, то нормированная стоимость будет равна 0.
Целевой коэффициент – значения коэффициентов целевой функции.
Допустимое увеличение, допустимое уменьшение – показывает границы изменений коэффициентов целевой функции, при которых сохраняется набор переменных, входящих в оптимальное решение.
2 – Ограничения. Кроме имени переменных и адресов ячеек в ней присутствуют столбцы:
Результирующее значение - значение левой части ограничения при оптимальном плане. Т.е. сколько фактически использовано ресурса.
Теневая цена – изменение целевой функции при изменении дефицитного ресурса на 1 единицу. Теневая цена недефицитного ресурса будет равна 0.
Ограничение Правая часть – запас ресурса.
Допустимое увеличение, допустимое уменьшение - показывает, на сколько можно изменить правую часть ограничения до того момента пока это будет влиять на целевую функцию.
Удобство использования MS Excel для решения задач линейного программирования заключается в том, что:
создав один раз таблицу, её можно применять для задач такого же типа изменяя только исходные данные;
все необходимые для решения задачи формулы уже представлены в MS Excel;
решение задачи занимает в несколько раз меньше времени, нежели её же решение вручную;
точность решения гораздо выше, чем вручную, а погрешности сведены к минимуму.
Единственным минусом решения задач линейного программирования с помощью MS Excel может быть: отсутствие полного решения, т.е. поиск решения сразу выдаёт готовый ответ, не показывая все вычисления, что в принципе не является целью решения задачи.
Список литературы:
А.Г.Трифонов. Примеры решения оптимизационных задач // 2008
Попова Н.В. Математические методы // М.:ВТК. – 2005
Лыкова Н.П., Князева А ПОСТАНОВКА ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ИХ РЕШЕНИЕ С ПОМОЩЬЮ MS EXCEL // Научный электронный архив.
URL: (дата обращения: 26.12.2019).
Одной из задач предшествующих глав было найти выход из этого двойственного положения и тесно связать теорию цен с теорией стоимости . Я считаю неправильным деление Экономической Науки на Теорию Стоимости и Распределения, с одной стороны, и Теорию Денег - с другой. Истинная граница, на мой взгляд, должна пролегать между Теорией Отдельной Отрасли или Фирмы, где рассматриваются вознаграждения факторов и распределение ресурс между различными способами использования данного их количества, и Теорией Производства и Занятости в целом. Пока мы ограничиваемся исследованием отдельной отрасли или фирмы, предполагая постоянным общее количество используемых ресурсов, а также допуская временно, что условия в других отраслях или фирмах остаются неизменными, нам, правда, не приходится иметь дело со специфическими особенностями денег. Но как только мы приступаем к выяснению того, чем же определяются объем производства и занятость в целом, нам необходима законченная теория Денежной Экономики.
По Смиту, рыночный автоматизм может оптимизировать распределение ресурсов . В отличие от распространенного мнения, будто частный интерес идет вразрез с интересами общества, Смит доказал, что децентрализация и свободная конкуренция способны обеспечивать максимальное удовлетворение потребностей . Свободная конкуренция стремится приравнивать цены к издержкам производства , оптимизируя распределение ресурсов внутри отраслей, а на рынках факторов производства - уравнивать чистые преимущества этих факторов во всех отраслях и тем самым устанавливать оптимальное распределение ресурсов между отраслями. Это был первый шаг к теории оптимизации распределения ресурсов в условиях совершенной конкуренции.
При этом необходимо учитывать, что прибыль, о чем говорилось ранее, имеет, во-первых, два определения (в бухгалтерском учете и в экономической теории), во-вторых, различные значения прибыль как неявный доход, получаемый фирмой за счет использования собственных факторов производства прибыль как вознаграждение за предпринимательский риск и нововведения (которая включается в экономические издержки) прибыль как монопольный доход в условиях несовершенной конкуренции . Каждое из приведенных значений прибыли обусловлено разнообразием ее источников, включающих соответственно альтернативность использования вмененных издержек, неопределенность в экономической среде и инновационной деятельности , наличие рыночной или монопольной власти над ценой. Прибыль, таким образом, выступает своего рода катализатором развития экономики, стимулом рационального распределения ресурсов , побудительным мотивом накопления капитала.
Среди важнейших классов задач И.о. можно назвать задачи управления запасами, распределения ресурсов и задачи назначения (распределительные задачи), задачи массового обслуживания , задачи замены оборудования , упорядочения и согласования (в том числе теории расписаний), состязательные (напр., игры), задачи поиска и др. Среди применяемых методов -математическое программирование (линейное, нелинейное и т.п.), дифференциальные и разностные уравнения , методы теории графов , марковские процессы , теория игр, теория (статистических) решений, теория распознавания образов и ряд других.
М. иногда называют теорией цен, поскольку ее предметом является механизм распределения ресурсов , а в рыночной экономике основным инструментом такого распределения служат цены.
В одном из них, работе Л.В.Канторовича "Математические методы организации и планирования производства " (1939 г.), были впервые изложены принципы новой отрасли математики, которая позднее получила название линейного программирования , а если смотреть шире, то этим были заложены основы фундаментальной для экономики теории оптимального распределения ресурсов . Л.В. Канторович четко сформулировал понятие экономического оптимума и ввел в науку оптимальные, объек-
Правило тождества эффекта" 280 "Преинституциональная" теория распределения ресурсов 301 "Прибор" 138 Признак оптимальности 71 "Принимающие цену" фирмы 390 "Принцип недостаточного основания" 112 "Природа" 281 "Продуктивная матрица" 189
Теории распределения ресурсов и формирования доходов в учебни микроэкономического анализа излагаются в рамках раздела Рынки ф торов производства. Общий план рассмотрения проблем в данном раз, ле остался неизменным со времени выхода в свет книги А. Марша Принципы экономической теории рынок труда , рынок капитала и рьи земли. Спрос на факторы со стороны фирм традиционно связываете предельным продуктом этих факторов, а предложение - с ожидаемым щ дельным доходом. Традиционно в учебниках рассматривается эластично спроса на каждый фактор, которая зависит как от взаимозаменяемое так и от взаимодополняемости факторов по технологии.
Или, может быть, мы могли бы провести деление между теорией стационарного равновесия и теорией подвижного равновесия, подразумевая под последней теорию системы , в которой меняющиеся представления о будущем способны оказывать влияние на нынешнее положение. Важность денег в основном как раз и вытекает из того, что они являются связующим звеном между настоящим и будущим. Мы можем анализировать, какое распределение ресурсов между различными видами использования совместимо с равновесием при действии нормальных экономических мотивов в мире, в котором наши представления о будущем неизменны и во всех отношениях надежны, причем возможно и дальнейшее деление между неизменяющейся экономикой и экономикой, подверженной изменениям, но где все события предвидятся с самого начала . С другой стороны, мы можем перейти от этой упрощенной модели к проблемам реального мира, в котором наши предварительные расчеты на будущее могут оказываться несбыточными и где предположения на будущее влияют на то, что мы делаем сегодня. Именно тогда, когда мы совершаем этот переход, в наши выкладки должны войти деньги с их особыми свойствами связующего звена между настоящим и будущим. Но хотя теория подвижного равновесия должна обязательно быть выражена в терминах денежной экономики, она остается теорией стоимости и распределения, а вовсе не обособленной "теорией денег". Деньги по своему существу являются прежде всего хитроумным средством связи между настоящим и будущим. Поэтому даже приступить к выяснению влияния меняющихся представлений о будущем на нашу текущую деятельность нельзя иначе, как в денежных терминах. Мы не можем избавиться от денег, даже уничтожив золото, серебро и другие законные платежные средства . Специфические проблемы денежной экономики будут возникать до тех пор, пока существуют какие бы то ни бьто ЯКФИБЫ длительного пользования, способные взять на себя функцию
Коронным достижением аксиоматического подхода является теория совершенной конкуренции . Невзирая на то, что она была впервые предложена около двухсот лет назад, она ни разу не была превзойдена усовершенствован был только метод анализа . Теория утверждает, что при некоторых, вполне определенных обстоятельствах неограниченное стремление к удовлетворению собственных интересов приводит к . Точка равновесия достигается, когда уровень производства компании таков, что предельные затраты равны рыночной цене товара, а каждый потребитель при покупке получает такое количество товара , что его общая предельная "полезность" равна его рыночной цене . Исследования показывают, что состояние равновесия максимизирует выгоды всех участников при условии, что ни один покупатель или продавец не может повлиять на рыночные цены . Именно этот способ рассуждении послужил теоретической основой для политики полной свободы действий - laissez faire, доминировавшей в девятнадцатом веке, а также служит основой современных представлений о "магической силе рынка".
Мировая капиталистическая система поддерживается идеологией, которая коренится в теории совершенной конкуренции . Согласно этой теории, рынки стремятся к равновесию, а равновесное положение означает наиболее эффективное распределение ресурсов . Любые ограничения свободы конкуренции снижают эффективность рыночного механизма, поэтому им следует противиться. Выше я охарактеризовал такой подход как идеологию свободного рынка (laissezfaire), но рыночный фундаментализм - более удачный термин. Дело в том, что фундаментализм предполагает своего рода веру, которую легко довести до крайностей. Это - вера в совершенство, вера в абсолют, вера в то, что любая проблема должна иметь решение. Фундаментализм предполагает наличие авторитета, обладающего совершенным знанием, даже если это знание недоступно обыкновенным смертным. Таким авторитетом является Бог, а в наше время его приемлемым заменителем стала Наука. Марксизм претендовал на наличие научной основы точно так же поступает рыночный фундаментализм . Научная основа обеих идеологий сложилась в XIX веке, когда наука все еще сулила обладание окончательной истиной. С тех пор мы многое осоз-
Поп пер атаковал марксизм и фрейдистский психоанализ на том основании, что эти теории, как и многие другие, провозглашали себя научными, но их ложность не могла быть доказана путем испытаний следовательно, их претензии были необоснованными. Я соглашаюсь с этим, но я пойду еще дальше. Я думаю, что аргумент, который он использовал против марксизма, также относится к таким многоуважаемым теориям, как теория совершенной конкуренции , которая провозглашает, что при определенных условиях неограниченное следование личным интересам ведет к наиболее эффективному распределению ресурсов . Я не хочу разрушать экономику я думаю, что это очень элегантная теоретическая конструкция. Я ставлю под вопрос ее применимость к реальной жизни и я не уверен, выдержит ли она испытание на финансовых рынках . Я полагаю, что деятельность Quantum Fund сама по себе доказывает ложность теории случайных блужданий.
Основателем данной теории является английский философ И. Бентам (1748-1832), считавший, что. у философии нет более достойного занятия, чем оказывать поддержку экономике в повседневной жизни2. Для утилитаристов удовольствие представляет собой цель всякого действия, а этика сводится к оптимальному распределению ресурсов ради цели наибольшего удовольствия. Они убеждены в
Д. р. - фундаментальное понятие современной экономической науки , в отечественную науку впервые привнесенное сторонниками
