Использование графического метода и симплекс-метода в решении задач линейного программирования

Курсовая работа

по дисциплине «Модели и методы принятия решений»

на тему «Использование графического метода и симплекс-метода  в решении задач линейного программирования»

Брест 2011

СОДЕРЖАНИЕ

ВВЕДЕНИЕ…………………………………………………………………………..3

РАЗДЕЛ 1 Теоретический раздел

1.1 Общая постановка задачи линейного программирования…………………….5

1.2 Графический способ решения задачи линейного программирования……….7

1.3 Симплекс-метод………………………………………………………………….9

1.4 Симплексные таблицы…………………………………………………………11

РАЗДЕЛ 2 Практический раздел

2.1 Решение задачи линейного программирования аналитическим способом...13

2.2 Решение задачи линейного программирования графическим методом…....16

ЗАКЛЮЧЕНИЕ……………………………………………………………………..18

ЛИТЕРАТУРА……………………………………………………………………...19

ВВЕДЕНИЕ

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

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

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

   Начало линейному программированию было положено в 1939 г. советским математиком-экономистом Л.В.Канторовичем в работе «Математические методы организации и планирования производства». Появление этой работы открыло новый этап в применении математики в экономике. Спустя десять лет американский математик Дж. Данциг разработал эффективный метод решения данного класса задач – симплекс-метод. Термин «линейное программирование» впервые появился в 1951 г. в работах              Дж. Данцига и Т. Купманса. В 1975 году Л. В. Канторович и Т. Купманс получили Нобелевскую премию по экономическим наукам с формулировкой «за их вклад в теорию оптимального распределения ресурсов».

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

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

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

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

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

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

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

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

В общем виде математическая модель задачи линейного программирования (ЗЛП) записывается как

Z = c1x1 + c2x2 +…+ cjxj +…+ cnxnmax(min)

при ограничениях

ai1x1 + ai2x2 + … + ainxn bi , i=,

ai1x1 + ai2x2 + … + ainxn = bi , i =,

xj ,  j = .

Математическая модель в более краткой записи имеет вид:

Z =

при ограничениях

, i =,

=bi, i =,

xj 0,  j = .

Для составления математической модели ЗЛП необходимо выполнить следующие этапы:

– обозначить переменные;

– составить целевую функцию в соответствии с целью задачи;

– записать систему ограничений с учетом имеющихся в условии задачи показателей.

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

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

ai1x1 + ai2x2 + … + ainxn bi ,  i=,

преобразуется в равенство путем добавления к левой части соответствующих дополнительных неизвестных yi (i=):

ai1x1 + ai2x2 + … + ainxn + yi = bi ,  yi0, i =,

а неравенство

ai1x1 + ai2x2 + … + ainxn bi ,   i =,

после вычитания дополнительных неизвестных преобразуется в равенство вида

ai1x1 + ai2x2 + … + ainxn – yi = bi ,  yi0, i=.

В реальных практических задачах дополнительные неизвестные имеют определенный смысл. Например, если левая часть ограничений задачи отражает расход ресурсов на производство продукции в объемах хj , j=, а правые части – наличие производственных ресурсов, то числовые значения дополнительных неизвестных yi (i=) обозначают  объем неиспользованных ресурсов i-го вида.

1.2 Графический способ решения  задачи линейного программирования

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

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

Z = c1x1 + c2x2 +…+ cnxnmax(min),            (1.1)

                                  a11x1 + a12x2 + … + a1nxn b1 ,             (1.2)

                                 ……………………………….                                                    

                                 am1x1 + am2x2 + … + amnxn bm ,              

                                             xi0,   j = .                         (1.3)

Каждое из неравенств системы ограничений (1.2) и (1.3) определяет на координатной плоскости x1Оx2 некоторую полуплоскость, а система неравенств в целом – пересечение соответствующих плоскостей:

ai1x1 + ai2x2 + … + ainxn + yi = bi , i = и хj = 0,   j = .

Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком. В случае несовместимости системы ограничений задачи линейного программирования, ОДР является пустым множеством. Угловыми точками выпуклого многогранника являются его вершины, образованные пересечением полуплоскостей.

Любая внутренняя и граничная точка ОДР является решением задачи. Приравняем функцию (1.1) к нулю, тогда уравнение

Z = c1x1 + c2x2 +…+ cnxn=0

представляет собой полуплоскость, проходящую через начало координат и перпендикулярную вектору-градиенту (направляющему вектору) =(с1, с2,…, сn). Направление вектора-градиента показывает направление возрастания функции. Поэтому, чтобы найти максимум функции, необходимо передвигать гиперплоскость в направлении вектора как можно дальше от начала координат, но чтобы она имела с ОДР хотя бы одну общую точку. Чтобы найти минимум функции, нужно определить ближайшую точку в ОДР от начала координат.

На координатной плоскости x1Оx2  (рис. 1.1) показано, что в угловой точке А функция достигает максимального значения, а в точке В – минимального.

Рисунок 1.1                                                                         Рисунок 1.2

Рисунок 1.2 отражает случай, когда прямая функция параллельна отрезку АВ, принадлежащему ОДР. Максимум функции Z достигается в точке А и в точке В, следовательно, и в любой точке отрезка АВ, так как эти точки могут быть выражены в виде линейной комбинации угловых точек А и В.

На рисунке 1.3 изображен вариант, когда система ограничений образует неограниченное сверху множество. Функция Z при этом стремится к бесконечности, так как прямую функции можно передвигать в направлении вектора градиента как угодно далеко. На рис. 1.4 представлен случай несовместной системы ограничений.

Рисунок 1.3                                                                        Рисунок 1.4