Документ (1). Линейное программирование
 Скачать 21.17 Kb.
|
Линейное программирование ВВЕДЕНИЕ В 1820 году, французский математик и физик Жан Батист Фурье, после длительной и успешной работы в должности префекта департамента Изер (департамент на юго-востоке Франции), опубликовал ряд работ, посвященных изученными задачами поиска экстремума функций при наличии ограничений типа неравенств. Таким образом, можно считать, что руководство осушением болот и строительство новой дороги положило начало исследованиям задач линейного программирования. Дальнейшая история развития этой отрасли показывает, что потребность в разрешении насущных задач человечества, позволяла математикам прошлого делать открытия, имеющие интересную судьбу, большое будущее. И в перспективе, говоря словами Самсона Семёновича Кутателадзе, «вычисление победит гадание». Выделение класса экстремальных задач, определяемых линейным функционалом на множестве, задаваемом линейными ограничениями, следует отнести к 1930-м годам. Одними из первых, исследовавшими в общей форме задачи линейного программирования, были: Джон фон Нейман - математик и физик, доказавший основную теорему о матричных играх и изучивший экономическую модель, носящую его имя, и Леонид Витальевич Канторович - советский академик, лауреат Нобелевской премии (1975), сформулировавший ряд задач линейного программирования и предложивший в 1939 году метод их решения (метод разрешающих множителей), незначительно отличающийся от симплекс-метода. Кроме этого, наряду с Л.В. Канторовичем и фон Нейманом, одним из основоположников линейного программирования, считается и американский математик Джордж Бернард Данциг. Не смотря на то, что Данциг сделал свое открытие много позже, советского коллеги, к своим находкам пришел самостоятельно, дал хорошее название - «симплекс метод» алгоритму, применяемому в решениях задач линейного программирования, а также популяризировавшему достижения советских ученых в зарубежной среде. Предтечей же можно считать метод разрешающих множителей, описанный в 1797-1801 году Жозефом Луи Лагранжем и работы венгерских математиков Эйгена Эгервари и Денеша Кёнига в 1931 году разрешивших задачу, называемую проблемой выбора. А также труд американского ученого Г.У. Куй, обобщившего этот метод, после чего он получил название венгерского метода. |
Каждый человек ежедневно, не всегда осознавая это, решает проблему получения наибольшего эффекта, при затрате ограниченных средств. К сожалению, наши средства и ресурсы всегда ограничены, приходится действовать очень обдуманно, ответственно, для того чтобы добиться желаемого.
Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. При решении простых задач допустимо было использовать методы, предложенные еще в Древнем Египте, при строительстве первой пирамиды в Саккаре, созданной Имхотепом. Известен достоверный источник - Папирус Ринда - коллекция математических задач, включающая в себя задачи расчета объема и число кирпичей, требуемых для пирамиды, расчет темпов строительства, разрешение обеспечения работников питанием, отдыхом, инструментами.
При решении задач больших, чем строительство пирамиды, можно действовать экстенсивным путем. Хорошим решением таких задач является бюрократия. Бюрократы, команда людей, составленная из отдельных людей, но взаимодействующая при обработке информации, при полном подчинении заданному управляющим органом (бюро) алгоритму, может решать задачи, которые не под силу одному человеку.
Однако, возрастающая сложность технологического производства, новые требования к скорости произведения расчетов, породили новое знание. Леонид Витальевич Канторович, консультируя в 1938 году фанерный трест, по проблеме эффективного использования лущильных станков понял, что дело сводится к задаче максимизации линейной формы многих переменных при наличии большого числа ограничений в форме линейных равенств и неравенств. Задача о наиболее выгодном распределении материала между станками сводилась к нахождению максимума линейной функции, заданной на многограннике. Максимум такой функции достигался в вершине, однако число вершин в этой задаче достигало миллиарда. Поэтому простой перебор вершин не годился. Фанерный трест налаживал выпуск военных самолетов, предназначенных на отражение фашистской агрессии, и крайняя нехватка времени подтолкнула 26 летнего профессора Ленинградского Государственного Университета, к совершению открытия.
Канторович модифицировал метод разрешающих множителей Лагранжа для её решения и понял, что к такого рода задачам сводится колоссальное количество проблем экономики. В 1939 году опубликовал работу «Математические методы организации и планирования производства», в которой описал задачи экономики, поддающиеся открытому им математическому методу и тем самым заложил основы линейного программирования. Алгоритмические методы, позволяющие решить более общую задачу, включающую связанное производство и множество возможных способов производства каждого продукта, которые позже стали известны как линейное программирование или линейная оптимизация, получили награды Сталинской, а в последствии, и Нобелевской премиями. О своём открытии он писал:
«…Я обнаружил, что широкий диапазон задач самого разнообразного характера, касающихся научной организации производства (вопросы оптимального распределения работы машин и механизмов, минимизации отходов, лучшего использования сырья и местных материалов, топлива, транспортировки, и так далее), приводит к формулировке единственной группы математических задач (экстремальные задачи). Эти задачи не могут быть напрямую сопоставлены задачам, рассматриваемым в математическом анализе. Если выражаться точнее, формально они подобны, и даже, как оказывается, с формальной точки зрения очень просты, но методы, применяемые для их решения в математическом анализе, фактически полностью непригодны для практики, так как требуют решения десятков тысяч или даже миллионов систем уравнений. Я преуспел в том, чтобы найти сравнительно простой общий метод решения этой группы задач, который применим ко всем задачам, которые я упомянул, и достаточно прост и эффективен для их решения, которое становится практически достижимым….»
Необходимо сделать акцент на значении открытия Канторовича, на той роли, которую может играть линейное программирование в жизни общества. Кратко - это метод решения задачи осознанного, математически точного обеспечения счастья человечества.
Современное производство благ человечество обеспечивает благодаря институту частной собственности. Деньги, как важнейший компонент, являются пространством, на которое проецируется все многообразие жизни человечества, и разрешение оптимумов увеличения капиталов собственников, является основой жизни. Считается, что это и является обеспечением счастья человечества, что через некоторое количество итераций, человечество обретет счастье.
Однако, существуют и обратные предположения. С точки зрения науки, натуральная система содержащая информацию, необходимую для ценообразования, является пространством большей размерности и что цены - суть проекция натуральной системы на пространство меньшей размерности. Это означает, что значительнейший объем информации исключается из анализа оптимальных путей развития человечества. Весьма вероятно, что подобные преобразования (натуральных значений в идентификационные, в цены), уничтожат информацию, необходимую для разрешения задачи, что может приводить к необдуманным, пагубным решениям.
Дальнейшая история развития линейного программирования и его применения на практике показывает, что не всегда можно решать задачу, даже если ее решение уже найдено. Особо примечательным является тот факт, что отсутствие команды у Канторовича и неверные оценки в общественно политической сфере, могут привести к стагнации области науки линейного программирования коммуникационной информации.
Основой своего метода Канторович объявил цены. Причем указал на тот факт, что это «объективно обусловленные оценки». С точки зрения науки, деньги (и соответственно цены) не являются необходимым элементом, для обеспечения производства. И политические деятели того времени, опираясь на труды Маркса, считали так же. С высоты достижений современной науки, а в частности работ Пола Кокшотта, Аллина Коттрелла, можно количественно и качественно обосновать эту позицию. Но на тот момент, такой возможности не существовало. А работы Отто Нейрата, вероятно, не были известны Канторовичу, его кружению, ответственным работникам народного хозяйства.
Во-первых, особая специфика алгоритма Канторовича решения задач линейного программирования требовала наличия ООО («объективно обусловленные оценки»), как элемент для повторяющейся корректировки начальных оценок, пока оптимальный план не найден. С компьютерными алгоритмами процесс решения задачи линейного программирования превращается в "черный ящик". Пользователь не должен интересоваться деталями метода вычисления. Использует ли система подход Канторовича, Данцига или Кармаркара - не имеет значения, за исключением тех случаев, когда это затрагивает размер задачи, которая может быть обработана. С компьютерными пакетами ООО более не являются необходимыми для того, чтобы рассчитать план.
Во-вторых, ограниченность вычислительных возможностей того времени обуславливала ограниченную способность Госплана определять детализированные цели в натуральной форме. Предприятию, производящему несколько товаров, необходимо иметь одну цель. Если в случае с выпуском одной продукции все просто - цель задается в натуральных показателях. А при нескольких видах продукции цель не видна явно. Задание такой цели в рублях, в стоимости выпуска продукции, сразу ставит вопрос о «правильной» и «неправильной» ценовой структуре. Предприятие максимизирует производство продуктов, имеющих наиболее высокую стоимость, игнорируя продукты с меньшей стоимостью, и в итоге совокупная поставка всех товаров часто осуществлялась бы не в тех пропорциях, которые необходимы, что ставит под вопрос существование самого предприятия.
Самсон Семёнович Кутателадзе в Тезисах, опубликованных к 100-летию Л.В. Канторовича, обратил внимание на тот факт, что в прошлом экономическое благосостояние людей определялось на основе предположений, профессиональные же решения математиков не задевали обычную жизнь людей, являясь формами мышления, безупречными истинами и методами их получения. Однако сейчас существуют все предпосылки того, что «вычисление победит гадание».
Практический алгоритм решения экономических задач, предложенный Канторовичем, предполагает наличие карандаша и бумаги. Алгоритм достаточно удобен для этих инструментов при решении практических задач скромного масштаба. И методы Канторовича использовались либо для оптимизации производства на отдельных заводах. При решении более масштабных задач Канторович рекомендовал использовать приблизительные методы, такие как агрегацию подобных производственных процессов и рассмотрение их в качестве единого сложного процесса. Что и использовалось при составлении агрегированных отраслевых планов, создаваемых для экономики в целом.
В большой экономике необходимо создание нескольких миллионов различных видов промышленных продуктов, начиная от различных типов винтов, шайб и электронных компонентов и заканчивая большими конечными продуктами, такими как суда и авиалайнеры. Достаточна ли ныне скорость вычислений, мощны ли компьютеры настолько, чтобы решить задачу планирования всей экономики в целом?
В течение долгого времени не было известно, принадлежит ли линейное программирование к неполиномиальному классу задач, названному «трудные» или к полиномиальному классу «лёгкие». В 1970 Виктор Клее и Джордж Минти создали пример, показавший, что классический симплексный алгоритм потребует экспоненциального числа шагов при решении наихудшего случая задачи линейного программирования. В 1978 советский математик Леонид Генрихович Хачиян разработал алгоритм для решения задач линейного программирования, имеющий полиномиальное время выполнения. Это - метод внутренней точки, использующий эллипсоиды, вписанные в область допустимых значений. Хачиян доказал, что время вычисления будет гарантированно меньше, чем полиномиальная функция размерности задачи и количества входных данных. Однако степень полинома, которую он установил, оказалась слишком высокой для того, чтобы этот алгоритм можно было использовать при решении практических задач.
Алгоритм индийского математика, Нарендра Кармаркара был важным развитием теоретического вывода Хачияна. Кармаркар показал, как задача линейного программирования может быть решена за полиномиальное время. Кроме того, алгоритм Кармаркара был применим для решения задач линейного программирования на практике.
Современные пакеты для решения задач линейного программирования совмещают симплекс-метод Данцига с более современными методами внутренней точки. Это позволяет самым последним вариантам решать задачи, включающие до одного миллиарда переменных. Для таких огромных задач используются большие параллельные суперкомпьютеры с более чем тысячей процессоров. Но даже на намного более скромных 4-процессорных компьютерах задачи линейного программирования с миллионом переменных решались за полчаса, при использовании методов внутренней точки.
Серьезной проблемой при практическом применении линейного программирования в решении экономических задач называется большой объем информации, необходимый для передачи данных от субъектов хозяйствования к планирующему органу и обратно. Считается, что наличие денег позволяет уменьшить эти объемы, упростить передачу и обработку информации. В противоположность этому, считается, что расчет в натуральных показателях потребует не только больших вычислительных ресурсов, но и высоких требований к коммуникационным системам.
Отмеченная опытом тенденция - управляющие стараются облегчить себе жизнь, преувеличивая необходимые затраты и одновременно выгоды долгосрочных расходов в своей епархии. Если подразделения связаны между собой через внутренний план корпорации, а не через рынок, применим тот же подход, что и при социалистическом планировании. Но когда дело доходит до отношений между независимыми капиталистическими компаниями, эти тенденции сдерживаются силами конкуренции (в предположении, что рынок действительно конкурентный).
Время от времени капиталистические фирмы тоже могут желать легкой жизни; но если они расслабляются, а рынок легкодоступен для конкурентов, тогда более агрессивные фирмы включаются в конкуренцию на данном рынке и, лучше используя имеющуюся технологию, могут подорвать рыночную долю существующей компании. Тогда эта компания будет вынуждена производить более эффективно под угрозой потери своей доли рынка, снижения прибыльности и, в конечном счете, разорения. Что же касается слишком далеко идущих инвестиционных планов, очевидной сдержкой для капиталистических фирм служит необходимость платить процент на средства, которые они занимают для инвестиций, так что сверхинвестиции были бы "самоубийством". Так что существуют серьезные стимулы для реалистической оценки предполагаемой прибыльности инвестиционных проектов (разумеется, это не значит, что в капиталистической экономике не принимают постоянно ошибочных решений).
В работе Пола Кокшотта и Аллина Коттрелла «Научный статус трудовой теории стоимости», приводятся расчеты, показывающие, что использование денег, как средства, необходимого для координации действий хозяйствующих субъектов сомнительно. Они показывают, что использование натуральных показателей уменьшают потоки информации, повышая при этом осведомленность о системе производства в целом