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

«КОРОЛЕВСКИЙ ИНСТИТУТ УПРАВЛЕНИЯ, ЭКОНОМИКИ И  СОЦИОЛОГИИ»

 
Факультет инноватики и управления

Кафедра управления качеством, техники и  технологий 

Отметка о допуске  к защите  

Оценка за защиту   

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

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

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

Исполнитель:

студент факультета управления и инноватики, 4 курс, группа УО-04

студент (факультет, курс, группа)

Ульянкин  Кирилл Юрьевич____________

фамилия, имя, отчество

 
 
Руководитель:

Профессор КУКТТ,  д.т.н________

ученое  звание,        ученая  степень,        должность

_Антипова Татьяна Николаевна         _______________

фамилия, имя, отчество 

Королев  2011 г.

 

      СОДЕРЖАНИЕ

 

 

Введение

     Настоящая работа подготовлена в Королевском  институте управления, экономики  и социологии на кафедре Управление качеством и техники и технологий

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

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

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

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

     Эволюция  научных представлений и формирование направлений в области теории и практики системного подхода во многом определяется разработками ученых: Л. В. Канторовича, В. С. Немчинова, В. В. Новожилова, А. Л. Лурье, А. Брудно, А. Г. Аганбегяна, Д. Б. Юдина, Е. Г. Гольдштейна, Дж. Данцигом, Г. Куна, А. Таккера, Чарнеса   и др.

     Объектом исследования является раздел математического программирования – линейное программирование.

Предметом исследования выступают задачи линейного программирования и методы их решения.

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

Достижение  этой цели предопределяет постановку и решение следующих задач:

1. Рассмотреть сущность математического программирования.
2. Раскрыть понятие линейного программирования.
3. Ознакомиться с видами задач линейного программирования.
4. Показать применение симплексного и графического метода решения задач линейного программирования.

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

 

Глава 1. Сущность математического программирования

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

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

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

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

     Под принятием решений в исследовании операций понимают сложный процесс, в котором можно выделить следующие основные этапы:

     1-й  этап. Построение качественной модели  рассматриваемой проблемы, т. е.  выделение факторов, которые представляются  наиболее важными, и установление закономерностей, которым они подчиняются. Обычно этот этап выходит за пределы математики.

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

     3-й  этап. Исследование влияния переменных  на значение целевой функции.  Этот этап предусматривает владение  математическим аппаратом для  решения математических, задач, возникающих  на втором этапе процесса принятия, решения.

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

     4-й  этап. Сопоставление результатов  вычислений, полученных на 3-м этапе,  с моделируемым объектом, т. е.  экспертная проверка результатов (критерий практики). Таким образом, на этом этапе устанавливается степень адекватности модели и моделируемого объекта в пределах точности исходной информации. Здесь возможны два случая:

     1-й  случай. Если результаты сопоставления  неудовлетворительны (обычная ситуация на начальной стадии процесса моделирования), то переходят ко второму циклу процесса. При этом уточняется входная информация о моделируемом объекте и в случае необходимости уточняется постановка задачи (1-й этап), уточняется или строится заново математическая модель (2-й этап), решается соответствующая математическая задача (3-й этап) и, наконец, снова проводится сопоставление (4-й этап).

     2-й  случай. Если результаты сопоставления  удовлетворительны, то модель  принимается. Когда речь идет  о неоднократном использовании на практике результатов вычислений, возникает задача подготовки модели к эксплуатации. Предположим, например, что целью моделирования является создание календарных планов производственной деятельности предприятия. Тогда эксплуатация модели включает в себя сбор и обработку информации, ввод обработанной информации в ЭВМ, расчеты на основе разработанных программ календарных планов и, наконец, выдачу результатов вычислений (в удобном для пользователей виде) для их использования в сфере производственной деятельности.

     В математическом программировании можно  выделить два направления.

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

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

Традиционно в математическом программировании выделяют следующие основные разделы.

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