Математическое программирование: Линейное программирование. Постановка задач, методы решения

КУРСОВАЯ РАБОТА

по дисциплине «Системный анализ»

на тему:

«Математическое программирование: Линейное программирование. Постановка задач, методы решения»

Работу выполнил:

студент группы УЗ-03

Работу проверил:

2010

СОДЕРЖАНИЕ

Обозначения и сокращения

Введение

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

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

• при наличии математической определенности и количественной ограниченности между изучаемыми переменными величинами и факторами;

• при взаимозаменяемости факторов из-за последовательности расчетов;

• в случае совмещения математической логики с пониманием сущности изучаемых явлений.

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

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

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

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

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

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

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

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

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

Актуальность линейного программирования и обусловила выбор темы данной курсовой работы. Значимость выбранного вопроса определяется также тем, что использование метода линейного программирования представляет собой важность и ценность – оптимальный вариант выбирается из достаточно значительного количества альтернативных вариантов. Также все экономические задачи, решаемые с применением линейного программирования, отличаются альтернативностью решения и определенными ограничивающими условиями

Цель курсовой работы – на практическом примере продемонстрировать использование методов линейного программирования.

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

Линейное программирование - один из первых и наиболее подробно изученных разделов математического программирования. Именно задачи линейного программирования явились тем разделом, с которого начала развиваться сама дисциплина «математическое программирование».

Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и др. задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми. Итак, линейное программирование возникло после Второй Мировой Войны и стал быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а так же математической «стройности». Можно сказать, что линейное программирование применимо для построения математических моделей тех процессов, в основу которых может быть положена гипотеза линейного представления реального мира: экономических задач, задач управления и планирования, оптимального размещения оборудования и пр. Задачами линейного программирования называются задачи, в которых линейны как целевая функция, так и ограничения в виде равенств и неравенств. Кратко задачу линейного программирования можно сформулировать следующим образом: найти вектор значений переменных, доставляющих экстремум линейной целевой функции при m ограничениях в виде линейных равенств или неравенств.

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи: рационального использования сырья и материалов; задачи оптимизации раскроя; оптимизации производственной программы предприятий; оптимального размещения и концентрации производства; составления оптимального плана перевозок, работы транспорта; управления производственными запасами; и многие другие, принадлежащие сфере оптимального планирования. Так, по оценкам американских экспертов, около 75% от общего числа применяемых оптимизационных методов приходится на линейное программирование. Около четверти машинного времени, затраченного в последние годы на проведение научных исследований, было отведено решению задач линейного программирования и их многочисленных модификаций.

Первые постановки задач линейного программирования были сформулированы известным советским математиком Л.В.Канторовичем, которому за эти работы была присуждена Нобелевская премия по экономике. Значительное развитие теория и алгоритмический аппарат линейного программирования получили с изобретением и распространением ЭВМ и формулировкой американским математиком Дж.Данцигом симплекс-метода. В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решения. Решение математических задач, относящихся к линейному программированию, связано с разработкой сложного программного обеспечения, дающее возможность эффективно и надежно решать практические задачи больших объемов. Эти программы и системы снабжены развитыми системами подготовки исходных данных, средствами их анализа и представления полученных результатов. В развитие и совершенствование этих систем вложен труд и талант многих математиков, аккумулирован опыт решения тысяч задач. Владение аппаратом линейного программирования необходимо каждому специалисту в области математического программирования. Линейное программирование тесно связано с другими методами математического программирования (например, нелинейного программирования, где целевая функция нелинейна).

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