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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


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

Информация:

Тип работы: курсовая работа. Добавлен: 08.10.2012. Сдан: 2012. Страниц: 12. Уникальность по antiplagiat.ru: < 30%

Описание (план):



 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Курсовая работа
по дисциплине «Модели и методы принятия решений»
на тему «Использование графического метода и симплекс-метода  в решении задач линейного программирования»
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Брест 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
 
1.3 Симплекс-метод
 
 
Двумерные задачи линейного программирования решаются графически. Для случая n=3 можно рассмотреть трехмерное пространство и целевая функция будет достигать своё оптимальное значение в одной из вершин многогранника.
В общем виде, когда в задаче участвуют n-неизвестных, можно сказать, что область допустимых решений, задаваемая системой ограничивающих условий, представляется выпуклым многогранником в n-мерном пространстве и оптимальное значение целевой функции достигается в одной или нескольких вершинах. Решить данные задачи графически, когда количество переменных более трех, весьма затруднительно. Существует универсальный способ решения задач линейного программирования, называемый симплекс-методом.
Симплекс-метод является основным в линейном программировании. Решение задачи начинается с рассмотрений одной из вершин многогранника условий. Если исследуемая вершина не соответствует максимуму (минимуму), то переходят к соседней, увеличивая значение функции цели при решении задачи на максимум и уменьшая при решении задачи на минимум. Таким образом, переход от одной вершины к другой улучшает значение функции цели. Так как число вершин многогранника ограничено, то за конечное число шагов гарантируется нахождение оптимального значения или установление того факта, что задача неразрешима.
Этот метод является универсальным, применимым к любой задаче линейного программирования, которая с помощью элементарных преобразований может быть приведена к каноническому виду.
 
f (x) = c1x1+c2x2+...+cnxn max(min)
a11x1+a12x2+...+a1nxn +х n +1 = b1,
a21x1+a22x2+...+a2nxn+х n +2 = b2,                                                                   
...................................................
am1x1+am2x2+...+amnxn+х n +т = bm,
xi?0 i = .
Сущность симплекс-метода заключается в том, что если число неизвестных больше числа уравнений, то данная система неопределенная с бесчисленным множеством решений. Для решения системы все неизвестные произвольно подразделяют на базисные и свободные. Число базисных переменных определяется числом линейно-независимых уравнений. Остальные неизвестные свободные.
Выразим в системе ограничений базисные неизвестные через небазисные, т.е. разрешим систему относительно базисных неизвестных:
 
х n +1 = a11(–x1)+a12(–x2)+...+a1n(–xn) +b1,
х n +2 = a21(–x1)+a22(–x2)+...+a2n(–xn) + b2,                                                                   
...................................................
х n +т = am1(–x1)+am2(–x2)+...+amn(–xn)+bm.
Свободным неизвестным придают произвольные значения и подставляют в систему. Любому набору свободных неизвестных можно придать бесчисленное множество произвольных значений, которые дадут бесчисленное множество решений. Если все свободные неизвестные приравнять к нулю, то решение будет состоять из значений базисных неизвестных. Такое решение называется базисным.
В теории линейного программирования существует теорема, которая утверждает, что среди базисных решений системы можно найти оптимальное, а в некоторых случаях и несколько оптимальных решений, но все они обеспечат экстремум целевой функции. Таким образом, если найти какой-либо базисный план, а затем улучшить его, то получится оптимальное решение. На этом принципе и построен симплекс-метод.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1.4 Симплексные таблицы
 
Процесс нахождения экстремума с помощью симплекс-метода оформляется в виде специальных симплекс-таблиц. Симплекс-таблица составляется для каждой итерации по определенным правилам, что облегчает перебор базисных решений и позволяет избежать случайных ошибок.
Алгоритм решения задач симплексным методом.
1. Математическая модель задачи должна быть канонической. Если в исходной формулировке задача неканоническая, то ее надо привести к каноническому виду.
2. Находим исходное опорное решение и проверяем его на оптимальность. Для этого заполняем симплексную таблицу 1.1. Все строки таблицы 1-го шага заполняем по данным системы ограничений и целевой функции. Базисные неизвестные (Б.Н.) запишем в левый заглавный столбец, а небазисные неизвестные (Н.Н.)  – в верхнюю заглавную строку. Числовые значения правой части системы ограничений запишем в правом столбце таблицы (в столбце свободных членов), в месте пересечения верхней заглавной строки и этого столбца поставим единицу. Коэффициенты при небазисных неизвестных запишем под ними. Функцию запишем в последней строке таблицы. В правой клетке этой строки запишем значение функции (Z=0)
Пусть решение в табл. 1.1 неопорное (элемент br,<0). Чтобы получить опорное решение, воспользуемся правилом преобразования таблиц с помощью модифицированных жордановых исключений, в соответствии с которым элементы разрешающей строки делятся на разрешающий элемент и записываются в новой таблице с тем же знаком. Поэтому, чтобы вместо br <0 получить число положительное, необходимо, чтобы разрешающий элемент был в данной строке и имел отрицательный знак.
Если же в строке с отрицательным свободным членом нет отрицательных элементов, то задача не имеет опорного решения, система ограничения задачи несовместна.
Пусть в r-й строке имеются отрицательные элементы аr2 и аrk. Если за разрешающий момент принять аrk < 0 или  аr2 < 0 и рассчитать новую таблицу, то гарантировано, что вместо элемента br < 0 будет положительное число, равное br/аrk или br/аr2, однако в таблице свободных членов вместо положительных элементов может появится не один, а несколько отрицательных элементов. Чтобы этого не случилось, необходимо разрешающий элемент выбирать по наименьшему симплексному отношению, отношению элементов столбца. За разрешающий столбец выбирается тот, в котором находится отрицательный элемент в строке с отрицательным свободным членом. В данном случае за разрешающий столбец можно выбрать 2-й или k-й, так как  аr2 < 0 и аrk < 0. Выберем за разрешающий столбец k-й. Тогда, обозначив симплексные отношения буквой t, найдем наименьшее из них среди положительных отношений:
t = min (b1/a1k; … bi/aik; ... br/ark; ... bm/amk) = br/ark  > 0.
Это отношение определило разрешающую строку и разрешающий элемент ark. Симплексные отношения удобно рассчитывать в таблице (табл.1.1).
 
                                                                                                                  Таблица 1.1
Н.Н.
Б.Н.
–х1
 
–х2
 

 
–xk
 

–хn
 
1
 
t?0
 
y1 =
a11
a12

a1k

a1n
b1
b1/a1k
yi  =
ai1
ai2

aik

ain
bi
bi/aik
yr =
ar1
ar2

ark

arn
br
br/ark
ym =
am1
am2

amk

a1n
bm
bm/amk
Z=
–c1
–c2

–ck

–cn
0
 
 
Базисная переменная из ключевой строки переводится в разряд свободных, а свободная переменная в ключевом столбце переводится в разряд базисных. Строится новая таблица;
3. Заполняем симплексную таблицу 2-го шага:
– переписываем разрешающую строку, разделив ее на разрешающий элемент;
– заполняем базисные столбцы;
– остальные  коэффициенты таблицы находим по правилу «прямоугольника». Так, например, вместо bi в новой таблице будет элемент bi’:
bi’ = bi – br aik / ark .
Получаем новое опорное решение, которое проверяем на оптимальность и так действуем до тех пор, пока не найдем опорное решение или не убедимся, что его не существует.
 
 
 
 
 
 
 
 
 
 
 
 
 
2.1 Решение задачи линейного программирования аналитическим способом
 
 
Задача. Транспортное предприятие имеет возможность приобрести не более 19 трехтонных автомашин и не более 17 пятитонных. Отпускная цена трехтонного грузовика – 400 млн.руб., пятитонного –500 млн. руб. Предприятие может выделить для приобретения автомашин 14 100 млн.руб. Сколько нужно приобрести автомашин, чтобы их суммарная грузоподъемность была максимальной?
Решить задачу аналитическим способом.
 
Решение:
 
Составим математическую модель задачи. Пусть х1 – количество трехтонных автомашин, х2 – количество пятитонных автомашин.
По условию   0 х1 19, 0 х2 17. На приобретение грузовиков необходима сумма 400х1 + 500х2, при этом по условию она не должна превышать 14 100, т.е.  400х1+500 х2 14 100. Теперь введем целевую функцию – грузоподъемность автомашин, которая составляет 3х1+5х2.
Таким образом, задача заключается в следующем: максимизировать целевую функцию:
 
Z = 3х1+5х2max                     
при ограничениях
400 х1+500 х2 14 100,
0 х1 19,
0 х2 17.
 
Решим эту задачу симплекс-методом. Приведем задачу к каноническому виду, введя три дополнительные переменные х3, х4, х5:
 
Z = 3х1+5х2+0х3+ 0х4+0х5max     
400 х1+500 х2+х3 = 14 100,
х1 + х4 = 19,
х2 + х5  = 17,
х1 0,   х2 0.   
 
Дополнительные неизвестные х3, х4, х5 будут базисными, так как им соответствуют единичные векторы, которые образуют базис в трехмерном пространстве. Разрешив систему относительно базисных неизвестных, получим:
х3 = –400х1 – 500х2 +14 100 ? 0;
          х4 = –х1 + 19 ? 0;
х5 = –х2 + 17 ? 0;
 
Занесем коэффициенты системы ограничений и функции в симплексную таблицу (таблица 2.1).
 
                                                                                                            Таблица 2.1
Н.Н.
Б.Н.
–х1
 
–х2
 
1
 
t?0
 
х3 =
400
500
14100
28,2
х4=
1
0
19

х5=
0
1
17
17
Z=
–3
–5
0
 
 
Решение в таблице 2.1 опорное, так как базисные неизвестные принимают положительные значения. Переходим к поиску оптимального решения. В строке функции наибольший по абсолютной величине (среди отрицательных) элемент находится во втором столбце, поэтому этот столбец берем за разрешающий. Разрешающую строку находим по наименьшему симплексному отношению
t = min (14 100/500; 17/1) = 17
Наименьшее симплексное отношение соответствует третьей строке, следовательно, она будет разрешающей. Выделим в таблице разрешающий элемент, который находится на пересечении разрешающих строки и столбца.
Рассчитаем элементы новой симплексной таблицы (таблица 2.2).
                                      
                                                                                                             Таблица 2.2
Н.Н.
Б.Н.
–х1
 
–х5
 
1
 
t?0
 
х3=
400
0
5600
14
х4=
1
0
19
19
х2=
0
1
17

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

и т.д.................


Н.Н.
Б.Н.

Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.