Xreferat.com » Рефераты по информатике и программированию » Решение задачи линейного программирования графическим методом

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

Министерство образования Российской Федерации


ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)


Пояснительная записка к курсовому проекту по дисциплине

«СПЕЦКУРС-3. ИССЛЕДОВАНИЕ ОПЕРАЦИЙ»

Вариант №3


28 марта 2008 г.


ТОМСК 2008

Содержание.


ВВЕДЕНИЕ 3
1. ПОСТАНОВКА ЗАДАЧИ 6
Математическое программирование 6
1.2 Кратко о линейном программировании 6
1.3 Основная задача линейного программирования 8
2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 10
2.1 Теоретическое введение 10
2.2 Методика решения задач ЛП графическим методом 12
3.ПРИМЕНЕНИЕ ГРАФИЧЕСКОГО МЕТОДА РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ НА ПРАКТИКЕ 13
3.1 Экономическая постановка задачи линейного программирования 13
3.2 Построение математической модели 14
3.3 Нахождение оптимального решения задачи с помощью линейного метода. 16
4. АНАЛИЗ ЧУВСТВИТЕЛЬНОСТИ ОПТИМАЛЬНОГО РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 18
4.1 Теоретическое введение 18
4.2 Методика графического анализа чувствительности оптимального решения 19
4.2.1 Первая задача анализа на чувствительность (анализ на чувствительность к правой части ограничений) 19
4.2.2 Вторая задача анализа на чувствительность (увеличение запаса какого из ресурсов наиболее выгодно) 25
4.2.3 Третья задача анализа на чувствительность (в каких пределах допустимо изменение коэффициентов целевой функции) 26
ЗАКЛЮЧЕНИЕ 30
Список литературы 32

ВВЕДЕНИЕ


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

Термин "Исследование операций" ("Operation Research") заимствован из западной литературы. Сейчас, пожалуй, нельзя точно назвать, ни дату его возникновения, ни автора, да и вряд ли найдется исчерпывающее определение этого понятия.

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

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

История возникновения исследования операций уходит корнями в далекое прошлое. Так, еще в 1885 году Фредерик Тейлор пришел к выводу о возможности применения научного анализа в сфере производства. Проблема, рассмотренная им, на первый взгляд, кажется тривиальной: "как оптимальным образом организовать работу землекопов?" Казалось бы, ответ давно известен - "Бери больше, кидай дальше, отдыхай, пока летит". Однако применение математического аппарата показало несостоятельность этого принципа. Оказалось, что оптимальный вес груза, позволяющий максимизировать количество перебрасываемого материала (при разумной экономии рабочей силы) значительно меньше того, что может поднять человек при максимальной нагрузке.

Пионером в области перевода сложных военно-стратегических задач на язык математики стал Фредерик Ланчестер. Одним из наиболее значительных результатов, полученных ученым, стало открытие в 1916 г. так называемого квадратичного закона, количественно связывающего достижение победы с двумя основными факторами: численным превосходством живой силы и эффективностью оружия. Было показано, что при одновременном вступлении в бой численное превосходство в живой силе более важно, чем применение более совершенного вооружения, поскольку главную роль играет сосредоточение собственных войск и расчленение сил противника. Классическим примером использования квадратичного закона Ланчестера является тактика Нельсона в сражении при Трафальгаре.

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

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

В годы второй мировой войны исследование операций широко применялось для планирования боевых действий. Так, специалисты по исследованию операций работали в командовании бомбардировочной авиации США, дислоцированном в Англии. Ими исследовались многочисленные факторы, влияющие на эффективность бомбометания. Были выработаны рекомендации, приведшие к 4-х-кратному повышению эффективности бомбометания.

В начале войны боевое патрулирование самолетов союзников для обнаружения кораблей и подводных лодок противника носило неорганизованный характер. Привлечение к командованию специалистов по исследованию операций позволило установить такие маршруты патрулирования и такое расписание полетов, при которых вероятность оставить объект незамеченным была сведена до минимума. Полученные рекомендации были применены для организации патрулирования над Южной частью Атлантического океана с целью перехвата немецких кораблей с военными материалами. Из пяти вражеских кораблей, прорвавших блокаду, три были перехвачены на пути из Японии в Германию, один был обнаружен и уничтожен в Бискайском заливе и лишь одному удалось скрыться благодаря тщательной маскировке.

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

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

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

В США внедрение методов исследования операций в практику управления экономикой происходило несколько медленнее - но и там многие концерны вскоре стали привлекать специалистов такого рода для решения проблем, связанных с регулированием цен, повышением производительности труда, ускорением доставки товаров потребителям и пр. Лидерство в области применения научных методов управления принадлежало авиационной промышленности, которая не могла не идти в ногу с растущими требованиями к ВВС. В 50-е-60-е годы на Западе создаются общества и центры исследования операций, выпускающие собственные научные журналы, ряд американских университетов включает эту дисциплину в свои учебные планы.

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

1. ПОСТАНОВКА ЗАДАЧИ


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


Математическое программирование.


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


Кратко о линейном программировании.


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

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

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

  Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

рационального использования сырья и материалов; задачи оптимизации раскроя;

оптимизации производственной программы предприятий;

оптимального размещения и концентрации производства;

составления оптимального плана перевозок, работы транспорта;

управления производственными запасами;

и многие другие, принадлежащие сфере оптимального планирования.

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

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

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

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

1.3 Основная задача линейного программирования


Основная задача линейного программирования (ОЗЛП) ставится следующим образом: Имеется ряд переменных Решение задачи линейного программирования графическим методом. Требуется найти такие их неотрицательные значения, которые удовлетворяли бы системе линейных уравнений:


Решение задачи линейного программирования графическим методом {1.1}

и, кроме того, обращали бы в минимум линейную целевую функцию (ЦФ)

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

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

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

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

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

На практике ограничения в задаче линейного программирования часто заданы не уравнениями, а неравенствами. В этом случае можно перейти к основной задаче линейного программирования.

Рассмотрим задачу линейного программирования с ограничениями-неравенствами, которые имеют вид

Решение задачи линейного программирования графическим методом {1.2}

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

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

Введём уравнения:

Решение задачи линейного программирования графическим методом {1.3}
где Решение задачи линейного программирования графическим методом- добавочные переменные, которые также как и Решение задачи линейного программирования графическим методом являются неотрицательными.

Таким образом, имеем общую задачу линейного программирования - найти неотрицательные Решение задачи линейного программирования графическим методом, чтобы они удовлетворяли системе уравнений (1.3) и обращали в минимум Решение задачи линейного программирования графическим методом.

Коэффициенты в формуле (1.3) перед Решение задачи линейного программирования графическим методом равны нулю.

2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


2.1. Теоретическое введение


Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.

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

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

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

можно представить в виде системы двух неравенств (см. рис.2.1)

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

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

Это связано с тем, что изменение значения L повлечет изменение лишь длины отрезка, отсекаемого линией уровня на оси Решение задачи линейного программирования графическим методом (начальная ордината), а угловой коэффициент прямой Решение задачи линейного программирования графическим методом останется постоянным (см.рис.2.1). Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L.

Вектор Решение задачи линейного программирования графическим методом с координатами из коэффициентов ЦФ при Решение задачи линейного программирования графическим методом и Решение задачи линейного программирования графическим методом перпендикулярен к каждой из линий уровня (см. рис.2.1). Направление вектора Решение задачи линейного программирования графическим методом совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположно направлению вектора Решение задачи линейного программирования графическим методом.

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

При поиске оптимального решения задач линейного программирования возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений – единственная точка; задача не имеет решений.

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

Рисунок 2.1 Геометрическая интерпретация ограничений и ЦФ задачи.

2.2. Методика решения задач ЛП графическим методом.


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

Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи (1.2). Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверить истинность полученного неравенства.

Если  неравенство истинное,

то    надо заштриховать полуплоскость, содержащую данную точку;

иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.

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

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

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

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

Построить вектор Решение задачи линейного программирования графическим методом, который начинается в точке (0;0) и заканчивается в точке Решение задачи линейного программирования графическим методом. Если целевая прямая и вектор Решение задачи линейного программирования графическим методом построены верно, то они будут перпендикулярны.

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

Определить координаты точки max (min) ЦФ Решение задачи линейного программирования графическим методом и вычислить значение ЦФ Решение задачи линейного программирования графическим методом. Для вычисления координат оптимальной точки Решение задачи линейного программирования графическим методом необходимо решить систему уравнений прямых, на пересечении которых находится Решение задачи линейного программирования графическим методом.


3. ПРИМЕНЕНИЕ ГРАФИЧЕСКОГО МЕТОДА РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ НА ПРАКТИКЕ.


3.1 Экономическая постановка задачи линейного программирования


Предприятие электронной промышленности выпускает две модели радиоприемников, причем каждая модель производится на отдельной технологической линии. Суточный объем первой линии - 60 изделий, второй линии - 80 изделий. На радиоприемник первой модели расходуется 15 однотипных элементов электронных схем, на радиоприемник второй модели - 10 таких же элементов. Максимальный суточный запас используемых элементов равен 950 единиц. Прибыли от реализации одного радиоприемника первой и второй моделей равны 40$ и 20$ соответственно. Определите оптимальные суточные объемы производства первой и второй моделей на основе графического решения задачи.


3.2 Построение математической модели.


Переменные задачи

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

Решение задачи линейного программирования графическим методом – суточный объем производства радиоприемников первой модели, [шт/сутки];

Решение задачи линейного программирования графическим методом – суточный объем производства радиоприемников второй модели, [шт/сутки];


Целевая функция

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

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

прибыль от их реализации  – согласно условию, соответственно 40 и 20 $.

Таким образом, доход от продажи суточного объема производства радиоприемников первой модели равен Решение задачи линейного программирования графическим методом$ в сутки, а от продажи радиоприемников второй модели – Решение задачи линейного программирования графическим методом$  в сутки. Поэтому запишем ЦФ в виде суммы дохода от продажи радиоприемников первой и второй модели:

Решение задачи линейного программирования графическим методом [$/сутки]

Ограничения

Возможные объемы производства радиоприемников Решение задачи линейного программирования графическим методом и Решение задачи линейного программирования графическим методом ограничиваются следующими условиями:

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

суточный объем первой технологической линии (производство радиоприемников первой модели) не может превышать 60 шт в сутки, второй (производство радиоприемников второй

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

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: