Линейное программирование

реферат

2. Становление линейного программирования

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

Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. При решении простых задач допустимо было использовать методы, предложенные еще в Древнем Египте, при строительстве первой пирамиды в Саккаре, созданной Имхотепом. Известен достоверный источник - Папирус Ринда - коллекция математических задач, включающая в себя задачи расчета объема и число кирпичей, требуемых для пирамиды, расчет темпов строительства, разрешение обеспечения работников питанием, отдыхом, инструментами.

При решении задач больших, чем строительство пирамиды, можно действовать экстенсивным путем. Хорошим решением таких задач является бюрократия. Бюрократы, команда людей, составленная из отдельных людей, но взаимодействующая при обработке информации, при полном подчинении заданному управляющим органом (бюро) алгоритму, может решать задачи, которые не под силу одному человеку.

Однако, возрастающая сложность технологического производства, новые требования к скорости произведения расчетов, породили новое знание. Леонид Витальевич Канторович, консультируя в 1938 году фанерный трест, по проблеме эффективного использования лущильных станков понял, что дело сводится к задаче максимизации линейной формы многих переменных при наличии большого числа ограничений в форме линейных равенств и неравенств. Задача о наиболее выгодном распределении материала между станками сводилась к нахождению максимума линейной функции, заданной на многограннике. Максимум такой функции достигался в вершине, однако число вершин в этой задаче достигало миллиарда. Поэтому простой перебор вершин не годился. Фанерный трест налаживал выпуск военных самолетов, предназначенных на отражение фашистской агрессии, и крайняя нехватка времени подтолкнула 26 летнего профессора Ленинградского Государственного Университета, к совершению открытия.

Канторович модифицировал метод разрешающих множителей Лагранжа для её решения и понял, что к такого рода задачам сводится колоссальное количество проблем экономики. В 1939 году опубликовал работу «Математические методы организации и планирования производства», в которой описал задачи экономики, поддающиеся открытому им математическому методу и тем самым заложил основы линейного программирования. Алгоритмические методы, позволяющие решить более общую задачу, включающую связанное производство и множество возможных способов производства каждого продукта, которые позже стали известны как линейное программирование или линейная оптимизация, получили награды Сталинской, а в последствии, и Нобелевской премиями. О своём открытии он писал:

«…Я обнаружил, что широкий диапазон задач самого разнообразного характера, касающихся научной организации производства (вопросы оптимального распределения работы машин и механизмов, минимизации отходов, лучшего использования сырья и местных материалов, топлива, транспортировки, и так далее), приводит к формулировке единственной группы математических задач (экстремальные задачи). Эти задачи не могут быть напрямую сопоставлены задачам, рассматриваемым в математическом анализе. Если выражаться точнее, формально они подобны, и даже, как оказывается, с формальной точки зрения очень просты, но методы, применяемые для их решения в математическом анализе, фактически полностью непригодны для практики, так как требуют решения десятков тысяч или даже миллионов систем уравнений. Я преуспел в том, чтобы найти сравнительно простой общий метод решения этой группы задач, который применим ко всем задачам, которые я упомянул, и достаточно прост и эффективен для их решения, которое становится практически достижимым….»

Делись добром ;)