Министерствообразования Российской Федерации
ТОМСКИЙГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
СИСТЕМУПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Пояснительнаязаписка к курсовому проекту по дисциплине«СПЕЦКУРС-3.ИССЛЕДОВАНИЕ ОПЕРАЦИЙ»
Вариант№3
28марта 2008 г.
ТОМСК2008
Содержание.
ВВЕДЕНИЕ 3 1. ПОСТАНОВКА ЗАДАЧИ 6 1.1 Математическое программирование 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.ПОСТАНОВКА ЗАДАЧИ
Цельюнашего курсового проекта является решение задачи линейного программированияграфическим методом.
1.1 Математическоепрограммирование.
Математическоепрограммирование («планирование») – это разделматематики, занимающийся разработкой методов отыскания экстремальных значенийфункции, на аргументы которой наложены ограничения. Методы математическогопрограммирования используются в экономических, организационных, военных и др.системах для решения так называемых распределительных задач. Распределительныезадачи (РЗ) возникают в случае, когда имеющихся в наличии ресурсов не хватаетдля выполнения каждой из намеченных работ эффективным образом и необходимонаилучшим образом распределить ресурсы по работам в соответствии с выбраннымкритерием оптимальности.
1.2 Кратко о линейном программировании.
Что же такоелинейное программирование? Это один из первых и наиболее подробно изученныхразделов математического программирования. Именно линейное программированиеявилось тем разделом, с которого начала развиваться сама дисциплина «математическоепрограммирование». Термин «программирование» в названии дисциплины ничегообщего с термином «программирование (т.е. составление программ) для ЭВМ» неимеет, так как дисциплина «линейное программирование» возникла еще до тоговремени, когда ЭВМ стали широко применяться при решении математических,инженерных, экономических и других задач. Термин «линейное программирование»возник в результате неточного перевода английского «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. Методика решениязадач ЛП графическим методом.
I. В ограниченияхзадачи (1.2) заменить знаки неравенств знаками точных равенств и построитьсоответствующие прямые.
II. Найти и заштриховатьполуплоскости, разрешенные каждым из ограничений-неравенств задачи (1.2). Дляэтого нужно подставить в конкретное неравенство координаты какой-либо точки[например, (0;0)], и проверить истинность полученного неравенства.
Если неравенство истинное,
то надозаштриховать полуплоскость, содержащую данную точку;
иначе (неравенстволожное) надо заштриховать полуплоскость, не содержащую данную точку.
Поскольку /> и/> должны быть неотрицательными, то ихдопустимые значения всегда будут находиться выше оси /> иправее оси />, т.е. в I-м квадранте.
Ограничения-равенстваразрешают только те точки, которые лежат на соответствующей прямой. Поэтому необходимовыделить на графике такие прямые.
III. Определить ОДРкак часть плоскости, принадлежащую одновременно всем разрешенным областям, ивыделить ее. При отсутствии ОДР задача не имеет решений.
IV. Если ОДР –не пустое множество, то нужно построить целевую прямую, т.е. любую из линийуровня /> (где L –произвольное число, например, кратное /> и/>, т.е. удобное дляпроведения расчетов). Способ построения аналогичен построению прямыхограничений.
V. Построить вектор />, который начинается вточке (0;0) и заканчивается в точке />.Если целевая прямая и вектор /> построеныверно, то они будут перпендикулярны.
VI. При поиске максимумаЦФ необходимо передвигать целевую прямую в направлении вектора />, при поиске минимумаЦФ – против направления вектора />. Последняя по ходудвижения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки(точек) не существует, то можно сделать вывод о неограниченности ЦФ намножестве планов сверху (при поиске максимума) или снизу (при поиске минимум).
VII. Определитькоординаты точки max (min) ЦФ /> и вычислить значение ЦФ />. Для вычисления координатоптимальной точки /> необходимо решитьсистему уравнений прямых, на пересечении которых находится />.
3. ПРИМЕНЕНИЕ ГРАФИЧЕСКОГО МЕТОДА РЕШЕНИЯЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ НА ПРАКТИКЕ.
3.1 Экономическая постановка задачилинейного программирования
Предприятие электроннойпромышленности выпускает две модели радиоприемников, причем каждая модельпроизводится на отдельной технологической линии. Суточный объем первой линии — 60 изделий, второй линии — 80 изделий. На радиоприемник первоймодели расходуется 15 однотипных элементов электронных схем, на радиоприемниквторой модели — 10 таких жеэлементов. Максимальный суточный запас используемых элементов равен 950 единиц.Прибыли от реализации одного радиоприемника первой и второй моделей равны 40$ и20$ соответственно. Определите оптимальные суточные объемы производства первойи второй моделей на основе графического решения задачи.
3.2 Построение математической модели.
Переменныезадачи
В задаче требуетсяустановить, сколько радиоприемников первой и второй модели надо производить.Поэтому искомыми величинами, а значит, и переменными задачи являются суточныеобъемы производства каждого типа радиоприемников:
/> – суточный объем производства радиоприемниковпервой модели, [шт/сутки];
/> – суточный объем производстварадиоприемников второй модели, [шт/сутки];
Целеваяфункция
Цель задачи –добиться максимального дохода от реализации продукции. Т.е. критериемэффективности служит параметр суточного дохода, который долженстремиться к максимуму.Чтобы рассчитать величину суточного доходаот продажи радиоприемников обоих моделей, необходимо знать:
· их объемыпроизводства, т.е. /> и /> радиоприемников в сутки;
· прибыль от ихреализации – согласно условию, соответственно 40 и 20 $.
Таким образом, доход отпродажи суточного объема производства радиоприемников первой модели равен />$ в сутки, а отпродажи радиоприемников второй модели – />$ в сутки. Поэтому запишем ЦФ в виде суммы дохода от продажи радиоприемниковпервой и второй модели:
/> [$/сутки]
Ограничения
Возможные объемыпроизводства радиоприемников /> и /> ограничиваются следующимиусловиями:
· количествоэлементов электронных схем, израсходованное в течении суток на производство радиоприемниковобоих моделей, не может превышать суточного запаса этих элементов на складе;
· суточный объем первойтехнологической линии (производство радиоприемников первой модели) не можетпревышать 60 шт в сутки, второй (производство радиоприемников второй модели) –80 шт;
· объемыпроизводства радиоприемников не могут быть отрицательными.
Таким образом, всеограничения задачи делятся на 3 группы, обусловленные:
1) расходом элементовэлектронных схем;
2) суточным объемомтехнологических линий;
3)неотрицательностьюобъемов производства.
Запишем этиограничения в математическойформе:
1) Т.к.из условия на радиоприемники первой и второй модели необходимо 15 и 20элементов соответственно, то данное ограничение имеет вид:
/>[шт/сутки]
2) Ограниченияпо суточному объему первой и второй технологических линий имеют вид:
/> [шт/сутки]
3) Неотрицательность объемов производствазадается как
/>.
Такимобразом, математическая модель этой задачи имеет вид
/>
/>
3.3Нахождение оптимального решения задачи с помощью линейного метода.
Математическуюмодель задачи о радиоприёмниках мы нашли на предыдущем шаге:
/>
/>
Построимпрямые ограничений, для чего вычислим координаты точек пересечения этих прямыхс осями координат (рис.3.1).
/>
прямая (1) –точки (0;95) и (63,(3);0), прямая (2) проходит через точку /> параллельно оси />, прямая (3) проходит черезточку /> параллельно оси />.
/>
Рис.3.1. Графическоерешение задачи о производстве радиоприемников.
ОпределимОДР. Например, подставим точку (0;0) в исходное ограничение (1), получим />, что является истиннымнеравенством, поэтому стрелкой обозначим полуплоскость, содержащую точку(0;0), т.е. расположенную правее и ниже прямой (1). Аналогично определимдопустимые полуплоскости для остальных ограничений и укажем их стрелками усоответствующих прямых ограничений (см. рис.3.1). Общей областью, разрешеннойвсеми ограничениями, т.е. ОДР является многоугольник ABCDE.
Целевую прямую можнопостроить по уравнению
/>
Точки пересечения с осями– (0;75) и (37,5;0)
Строим вектор/> из точки (0;0) в точку (40;20).Точка D –это последняя вершина многоугольника допустимых решений ABCDE, через которую проходитцелевая прямая, двигаясь по направлению вектора />. Поэтому D – это точкамаксимума ЦФ. Определим координаты точки D из системы уравненийпрямых ограничений (1) и (2)
/>
Получилиточку D(60;5)[шт/сутки].
Максимальноезначение ЦФ равно />[$/сутки].
Такимобразом, наилучшим режимом работы предприятия является ежесуточное производстворадиоприемников первоймодели в количестве60 штук и радиоприемниковвторой моделив количестве 5 штук. Доход от продажи составит 2500$ в сутки.
4. АНАЛИЗЧУВСТВИТЕЛЬНОСТИ ОПТИМАЛЬНОГО РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 4.1. Теоретическое введение
Неизбежное колебаниезначений таких экономических параметров, как цены на продукцию и сырье, запасысырья, спрос на рынке и т.д. может привести к неоптимальности или непригодностипрежнего режима работы. Для учета подобных ситуаций проводится анализчувствительности, т.е. анализ того, как возможные изменения параметров исходноймодели повлияют на полученное ранее оптимальное решение задачи ЛП.
Для решения задач анализачувствительности ограничения линейной модели классифицируются следующимобразом. Связывающие ограничения проходят черезоптимальнуюточку. Несвязывающие ограничения не проходят черезоптимальнуюточку. Аналогично ресурс, представляемый связывающим ограничением, называют дефицитным,а ресурс, представляемый несвязывающим ограничением – недефицитным.Ограничениеназывают избыточным в том случае, если его исключениене влияет на ОДР и, следовательно, на оптимальное решение. Выделяют следующиетри задачи анализа на чувствительность.
1. Анализ сокращенияили увеличения ресурсов:
· на сколько можноувеличить (ограничения типа />) запас дефицитногоресурса для улучшения оптимального значения ЦФ?
· на сколько можноуменьшить (ограничения типа />) запас недефицитногоресурса при сохранении оптимального значения ЦФ?
2. Увеличение (ограничения типа />)запаса какого из ресурсов наиболеевыгодно?
3. Анализизменения коэффициентов ЦФ: каков диапазон изменения коэффициентов ЦФ, при которомне меняется оптимальное решение?
4.2.Методика графического анализа чувствительности оптимального решения.4.2.1. Перваязадача анализа на чувствительность (анализ на чувствительность к правой частиограничений)
Проанализируемчувствительность оптимального решения задачи о производстве радиоприемников. ОДР задачи (рис.3.1) –многоугольник ABCDE. В оптимальной точке D пересекаются прямые (1) и (2).Поэтому ограничения (1) и (2) являютсясвязывающими, асоответствующие им ресурсы (суточный объем элементов электронных схем и производительностьпервой технологической линии) – дефицитными.
Рассмотрим экономическийсмысл этих понятий. Точка максимума ЦФ D соответствует суточному производству 60 шт радиоприемниковпервой модели и 5 шт радиоприемников второй модели. В производстве радиоприемниковиспользуются однотипные элементы электронных схем. Суточный запас на складе этихэлементов – это правая часть связывающего ограничения (1) (950 шт/сутки).Согласно этому ограничению, на производство в точке D расходуется
/> [шт элементов/сутки](1).
Аналогично видим, что производительностьпервой технологической линии — это правая часть связывающего ограничения (2)(60 шт/сутки). Согласно этому ограничению в точке D данная линия производит 60 радиоприемников первой модели всутки.
Таким образом, понятие"связывающие ограничения" (1) и (2) означает, что припроизводстве радиоприемников в точке D(60;5) запасы элементов электронных схем расходуются полностью, атак же производительность первой технологической линии используется в полномобъеме. По этой причине невозможно дальнейшее наращиваниепроизводства. В этом заключается экономический смысл понятия дефицитностиресурсов, т.е. если предприятие сможет увеличить суточные запасы элементовэлектронных схем или производительность первой технологической линии, то этопозволит увеличить выпуск радиоприемников. В связи с этим возникает вопрос: докакого уровня целесообразно увеличить данные ресурсы, и на сколько при этомувеличится оптимальное производство радиоприемников?
Правило №1
Чтобы графически определить максимальноеувеличение запаса дефицитного ресурса, вызывающее улучшение оптимальногорешения,
необходимо передвигать соответствующую прямую внаправлении улучшения ЦФ до тех пор, пока это ограничение не станет избыточным.
При прохождении прямой(1) через точку К (рис.4.1) многоугольник ABKE становится ОДР, а ограничение (1) – избыточным.Действительно, если удалить прямую (1), проходящую через точку К, то ОДР ABKE не изменится. Точка К становится оптимальной,в этой точке ограничения (2) и (3) становятся связывающими.
/>
Рис.4.1. Анализувеличения суточного запаса элементов электронных схем
Правило №2
Чтобы численно определить максимальнуювеличину запаса дефицитного ресурса, вызывающую улучшение оптимального решения,
необходимо:
1) определитькоординаты точки />, в которойсоответствующее ограничение становится избыточным;
2) подставитькоординаты /> в левую частьсоответствующего ограничения.
Координаты точки К(60;80)находятся путем решения системы уравнений прямых (2) и (3). Т.е. в этой точке предприятиебудет производить 60 шт радиоприемников первой модели и 80 шт радиоприемниковвторой модели. Подставим /> и /> в левую часть ограничения(1) и получим максимально допустимый запас элементов электронных схем
/> [шт эл/сутки].
Дальнейшее увеличениезапаса элементов электронных схем нецелесообразно, потому что это не изменитОДР и не приведет к другому оптимальному решению (см. рис.4.1). Доход отпродажи радиоприемников в объеме, соответствующем точке К, можно рассчитать,подставив ее координаты в выражение ЦФ
/> [$/сутки].
Рассмотрим вопрос оцелесообразности увеличения производительности первой технологической линии.Согласно правилу №1, соответствующее ограничение (2) становится избыточным вточке J, в которой пересекаются прямая (1) иось переменной /> (рис.4.2).Многоугольник ABCJ становится ОДР, а точка J(63,33;0) (или (63;0)-целочисленноерешение) – оптимальным решением.
/>
Рис.4.2. Анализувеличения производительности первой технологической линии
В точке J выгодно производить только радиоприемникипервой модели (63 шт в сутки). Доход от продажи при этом составит
/> [$/сутки]
Чтобы обеспечить такойрежим работы, согласно правилу №2, производительность первой технологическойлинии надо увеличить до величины
/> [шт/сутки].
Ограничение (3) является несвязывающим,т.к. не проходит через оптимальную точку D (см. рис.4.3).Соответствующий ему ресурс (производительность второй технологической линии)является недефицитным. С экономической точки зрения это означает, что вданный момент уровень производительности второй технологической линиинепосредственноне определяет объемы производства. Поэтому некоторое его колебание может никакне повлиять на оптимальный режим производства в точке D.
Например, увеличение(уменьшение) суточного объема второй технологической линиибудетсоответствовать перемещению прямой ограничения /> (3)вверх (вниз). Перемещение прямой (3) вверх никак не может изменить точку D максимума ЦФ. Перемещение же прямой(3) вниз не влияет на существующее оптимальное решение только до пересеченияс точкой D (см. ниже правило №3). Из рис.4.3видно, что дальнейшее перемещение (3) приведет к тому, что точка D будет за пределами новой ОДР,выделенной более темным цветом. Кроме того, любое оптимальное решение для этойновой ОДР будет хуже точки D.
/>
Рис.4.3. Анализуменьшения производительности второй технологической линии
Правило№3
Чтобы определить максимальное уменьшениезапаса недефицитного ресурса, не меняющее оптимальное решение,
необходимо передвигать соответствующую прямую допересечения с оптимальной точкой.
Правило №4
Чтобы численно определитьминимальную величину запаса недефицитного ресурса, не меняющую оптимальноерешение,
необходимо подставить координаты оптимальнойточки в левую часть соответствующего ограничения.
Чтобы выяснить, до какихпределов уменьшение производительности второй технологической линии не повлияетна производство в точке D,используем правило №4 Подставляем в левую часть ограничения (3) координатыточки D, получаем
/>[шт/сутки].
Делаем вывод: предельныйуровень, до которого может уменьшиться объем второй технологической линии, ипри котором не изменится оптимальность полученного ранее решения, равен 5шт радиоприемников в сутки.
Результаты решения первой задачи анализа оптимальногорешения на чувствительность представлены в табл.4.1.
Таблица 4.1№ Тип ресурса
Max
изменение ресурса,
/>, шт/сутки
Max
изменение
дохода,
/>,
$/сутки
Ценность
дополнительной
единицы ресурса
/>, $/шт (1) Дефицитный 1700-950=+750 4000-2500=+1500
/> (2) Дефицитный 63-60=+3 2520-2500=+20
/> (3) Недефицитный 5-80=-75 2500-2500=0
/> 4.2.2. Вторая задачаанализа на чувствительность (увеличение запаса какого из ресурсов наиболеевыгодно)
Анализ табл.4.1показывает, что к улучшению оптимального решения, т.е. к увеличению суточногодохода приводит увеличение дефицитных ресурсов. Для определениявыгодности увеличения этих ресурсов используют понятие ценности дополнительной единицы i-го ресурса/>
/>
где/> – максимальное приращениеоптимального значения ЦФ; /> – максимально допустимый прирост объема i-го ресурса.
Например, из табл.4.1следует, что увеличение суточного запаса элементов электронных схем (ограничение(1)) на 1 шт позволит получить дополнительный доход, равный 2 $/сутки, вто время как увеличение производительности первой технологической линии (ограничение(2)) на 1 шт принесет 6,7 $/сутки. Недефицитные ресурсы имеют нулевыеценности, поскольку изменение этих ресурсов не приводит к увеличению дохода.
Вывод: дополнительные вложения в первуюочередь необходимо направлять на увеличение суточного объема первойтехнологической линии, а лишь потом на увеличение суточного запаса элементовэлектронных схем. Изменять недефицитные ресурсы нет необходимости.
4.2.3. Третьязадача анализа на чувствительность (в каких пределах допустимо изменениекоэффициентов целевой функции)
Изменение цен напродукцию, т.е. изменение коэффициентов ЦФ, представляется на графике вращениемцелевой прямой вокруг оптимальной точки. Так, при увеличении коэффициента ЦФ /> или уменьшении /> целевая прямая вращается почасовой стрелке. При уменьшении /> или жеувеличении /> целевая прямая вращается противчасовой стрелки (рис.4.4).
При таких поворотах точкаD будет оставаться оптимальной до техпор, пока наклон целевой прямой не выйдет за пределы, определяемыенаклонами прямых ограничений (1) и (2). Так, например, если наклон целевойпрямой совпадет с наклоном прямой (1), то оптимальным решением будут точкиотрезка СD. При совпадении c прямой (2) оптимальным решениембудут точки отрезка DE.
/>
Рис.3.4. Анализ измененияцен
Наличие альтернативныхоптимумов свидетельствует о том, что одно и то же оптимальное значение можетдостигаться при различных значениях переменных. Если целевая прямая выйдет запределы наклона (1), то оптимальной точкой станет точка C. Допустим, что цена на радиоприемникивторой модели не меняется, т.е. зафиксируем значение целевого коэффициента />. Проанализируем графическирезультаты изменения значения целевого коэффициента />,т.е. цены на радиоприемники первой модели. Оптимальное решение в точке D не будет меняться при увеличении /> до тех пор, пока целеваяпрямая не совпадет с прямой (2). Аналогично, оптимальное решение в точке D не будет меняться при уменьшении /> до тех пор, пока целеваяпрямая не совпадет с прямой (1).
Совпадение в процессевращения целевой прямой с прямой ограничения означает, что углы их наклонаотносительно горизонтальной оси сравнялись, а значит, стали равны тангенсыуглов наклона этих прямых.
Правило №5
Чтобы определить границы допустимогодиапазона изменения коэффициента ЦФ, например /> и/>,
необходимо приравнять тангенс угла наклонацелевой прямой /> поочередно ктангенсам углов наклона прямых связывающих ограничений, например />и /> (рис.4.5 и 4.6).
/>
Рис.4.5. Определение />
/>
Рис.4.6. Определение />
Определим, насколькомаксимально может снизиться цена на радиоприемники первой модели, не изменяя оптимальнуюточку D. Для этого применим правило №5.
Тангенсы угла наклона дляпрямых L(x) и (1) соответственно равны:
/> и />
Тогда из равенства /> находим /> [$/шт]
Теперь попробуемопределить, насколько максимально может увеличиться цена на радиоприемникипервой модели, чтобы не изменилась оптимальная точка D.
На рис 4.6 видно, чтозначение c1 можно увеличивать беспредельно, так как прямая L(x) при c2 = 20 и /> никогда не совпадает спрямой (2). Следовательно,точка D при всех значениях коэффициента /> будет единственнойоптимальной.
Из приведенных вышерасчетов и графической их иллюстрации следует, что если цена на радиоприемникипервой модели станет меньше 30 $/шт, то наиболее выгодным будет производстворадиоприемников в точке C (см.рис.4.5). При этом производительность первой технологической линии будетиспользоваться не в полном объеме, что приведет к недефицитности данного ресурса(2), а дефицитными будут ресурсы (1) и (3).
Проведем те же самыеисследования для радиоприемников второй модели. Для этого зафиксируем значение />. Ищем />:
/>
Тогда из равенства /> находим /> [$/шт]
На рис 4.6 видно, чтозначение c2 можно уменьшать до нуля, так как прямая L(x) при c1 = 40 и /> совпадает с прямой (2).Следовательно, точка D привсех значениях коэффициента /> будетоптимальной.
Аналогично делаем вывод,что если цена на радиоприемники второй модели станет выше 26,67 $/шт, тонаиболее выгодным будет производство радиоприемников в точке C.
С экономической точкизрения производство радиоприемников в точке С означает, что предприятию станетвыгоднее изготовлять радиоприемники второй модели, используя на полную мощностьпроизводительность второй технологической линии.
ЗАКЛЮЧЕНИЕ.
В ходе работы надкурсовым проектом была рассмотрена задача линейного программирования опроизводстве радиоприемников. Для решения задачи использовался графическийметод. Получены следующие результаты:
Оптимальнаяприбыль от реализации продукции достигается при следующем суточном производстверадиоприемников: 60 штрадиоприемников первой модели и 5 шт радиоприемников второй модели. При этом прибыль от реализации составит 2500$ в сутки.
Рассмотрев три задачи анализаполученного решения на чувствительность к принятой модели, мы можем ответить наследующие вопросы:
1. Определите пределувеличения производительности первой линии, превышение которого уже не будетулучшать значения целевой функции.
— предел увеличения производительности первой линии равен63 радиоприемника в сутки. Дальнейшее увеличение производительности не имеетсмысла, т.к. значение ЦФ не улучшится.
2. Определите пределуменьшения производительности второй линии, при котором полученное оптимальноерешение останется неизменным.
— предельный уровень, до которого может уменьшитьсяпроизводительность второй технологической линии, и при котором не изменитсяоптимальность полученного ранее решения, равен 5 радиоприемников в сутки.
3. Определите пределувеличения суточного запаса элементов электронных схем, при превышении которогоулучшить значение целевой функции оказывается невозможным.
— предел увеличения суточного запаса элементов электронныхсхем равен 1700 шт в сутки. Дальнейшее увеличение нецелесообразно, потому чтоэто не изменит ОДР и не приведет к другому оптимальному решению.
4. Определитьдефицитный ресурс, который имеет наибольший приоритет при возможностиувеличения запасов ресурсов.
— т.к. увеличение производительности первой технологическойлинии на 1 шт принесет 6,7 $/сутки (в отличии от 2$/сутки от увеличениясуточного запаса элементов электронных схем), то именно данный ресурс (2) имеетприоритет.
5. Определитеинтервал изменения прибыли от продажи радиоприемника первой модели, в которомоптимальное решение остается неизменным.
— интервал изменения прибыли от продажи радиоприемника первоймодели, в котором оптимальное решение остается неизменным, определяетсянеравенством /> $/шт.
6. Определитеаналогичный интервал для приемника второй модели.
— интервал измененияприбыли от продажи радиоприемника второй модели, в котором оптимальное решениеостается неизменным, определяется неравенством /> $/шт.
Решение данной задачипомогло более глубоко и основательно изучить и укрепить на практике всетонкости и моменты графического метода решения задач линейногопрограммирования, а так же разобраться с основами анализа на чувствительностьмодели к полученному оптимальному решению.
Список литературы
1. АстафуровВ.Г., Колодникова Н. — Компьютерное учебное пособие, раздел“Анализ на чувствительность с помощью двойственнойзадачи”, Томск-2002.
2. Алесинская Т.В. — Задачи поисследованию операций с решениями.
3. Смородинский С.С., Батин Н.В. — Оптимизациярешений на основе методов и моделей математического программирования: Учебноепособие.
4. Кононов В.А. — Исследование операций.Для продвинутых математиков.