|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Непропорциональности свободных членов (прямые параллельны)Примеры.
5. Методы условной оптимизации 5.1. Краткая история и суть вопроса В середине прошлого века начало интенсивно развиваться научно-прикладное направление, получившие название "Исследование операций" (ИО), занимающееся изучением систем различной природы с помощью методов математического моделирования. Результатом применения методов ИО является выработка рекомендаций по проектированию и изменению систем с целью повышения эффективности их функционирования в соответствии с определенными требованиями и реальной обстановкой. Этот раздел посвящен изучению объектов, эффективность функционирования которых оценивается некоторым критерием. Например: минимум затрат, максимум прибыли, минимум отходов, минимум затраченного времени и т.п. При этом реальная обстановка учитывается некоторой совокупностью ограничений на допустимые изменения параметров объекта. В результате такого подхода математическая модель исследуемого объекта формализуется в виде задачи условной оптимизации. По сути дела, назначение любой оптимизационной модели заключается в том, чтобы, располагая ограниченными возможностями, обеспечить достижение максимального эффекта, иными словами - из сложившейся реальной ситуации извлечь максимум желаемого. При условии адекватности математической модели (соответствия моделируемому объекту) расчеты по ее компьютерному аналогу позволяют выявить практически важные и далеко не очевидные аспекты функционирования исходного объекта - оригинала. В планировании и управлении чем выше ставки, тем более жесткие требования предъявляются к бизнес-планам. Поэтому при обосновании принимаемых решений математические методы играют исключительно важную роль. Одним из таких методов является математическое программирование (МП). Под названием МП объединяется целая группа методов условной оптимизации, и в их числе - линейное программирование (ЛП), представляющее собой наиболее простую модель оптимального использования ограниченных ресурсов с линейным критерием эффективности и системой условий, выраженной линейными неравенствами. В рамках моделей ЛП решается немало задач, в том числе не линей- ных, но допускающих линеаризацию соотношений с достаточно высокой степенью точности. Вследствие широкой применимости ЛП составляет в практических приложениях целое направление. Его основоположникам, в числе которых есть и наш соотечественник – академик Л.В. Канторович, в 1975 г. была присуждена Нобелевская премия. А это, как известно, является высшей формой всемирного признания научной и практической значимости достижений в любой области. Для понимания методологических и алгоритмических основ ЛП достаточно материала настоящего пособия, изложенного к настоящему моменту. Ввиду относительной простоты ЛП и возможности наглядной графической иллюстрации хода решения задач внимание будет сосредоточено именно на этом методе оптимизации.
5.2. Постановка задачи линейного программирования Для конкретности проанализируем функционирование фирмы, которая занимается производством и реализацией продукции хлебобулочной продукции. Пусть ежедневно выпекаются изделия n видов: батоны, бублики, пряники, печенье и др. При этом используется m ингредиентов: мука, соль, сахар, молоко, масло, яйца, изюм, кунжут, и т.п. Причем в калькуляциях каждого предприятия заложены нормы расхода сырья и прибыли по всем видам продукции. В дальнейшем виды продукции будем индексировать символом j, а сырье - i. Таким образом, известно, что на изготовление 1 кг j -й продукции расходуется кг i -го сырья, общее количество которого ограниченно величиной . Прибыль от реализации продукции также в расчете на 1 кг, обозначим . Исходные данные исчерпываются перечисленными выше показателями. В условиях реального производства естественным является стремление спланировать выпуск продукции с таким расчетом, чтобы обеспечить максимум прибыли, разумеется, с учетом действующих ограничений по сырью. Для полноты следовало бы ввести в рассмотрение ограничения по производственным мощностям с учетом использования одного и того же механизма при изготовлении разных видов продукции. Однако это привело бы к существенному усложнению модели. Обозначим - объем выпуска j -й продукции в кг. Тогда на этот объем придется прибыль в размере , а совокупная прибыль по всем видам продукции составит L () = . Расход i -го сырья при изготовлении j -й продукции в объеме равен , а в общей сложности оно будет израсходовано в количестве . Суммирование изложенных выше фактов в соответствии с принятой терминологией приводит к формулировке следующей задачи оптимального планирования
Последние неравенства выражают неотрицательность переменных как объемов производства. Таким образом, сформулирована задача оптимизации плана производства продукции на максимум прибыли при ограниченных ресурсах. В период реконструкции производства или в момент материальных затруднений разумным тактическим ходом является такое снижение объемов производства, которое позволило бы хоть и с потерями, но сохранить за собой в будущем занимаемый сектор рынка. Данной ситуации отвечает задача минимизации совокупной себестоимости произведенной продукции при поддержании производства на уровне не ниже заданного: ⟶ min,
Здесь - показатели удельной себестоимости продукции, а - минимально допустимый уровень удовлетворения спроса. Формализация связи параметров объекта (безотносительно к их экономическому содержанию) в форме линейных соотношений, представленных целевой функцией, критерием оптимальности и системой ограничений, называется задачей линейного программирования (ЛП). Суть задачи ЛП заключается в поиске решения, наилучшего в смысле принятого критерия оптимальности. Набор значений переменных, удовлетворяющих всем ограничениям, называется допустимым решением или планом. Совокупность допустимых решений задачи ЛП образует геометрическую фигуру М, называемую "многогранником допустимых решений". Допустимое решение, доставляющее оптимум ЦФ на М, называется оптимальным и обозначается
5.3. Дробно-линейное программирование Немалый практический интерес представляет наиболее эффективное использование денежных средств, выражаемое показателем рентабельности, играющим в экономике весьма важную роль. Данный показатель исчисляется отношением прибыли к себестоимости и характеризует величину прибыли, приходящуюся на единицу затрат, т.е. отдачу с одного рубля. Экономическое содержание рентабельности предопределяет стремление увеличивать ее по мере возможности. Применительно к рассмотренному выше примеру целевая функция задачи на максимум рентабельности будет дробно-линейной ⟶ max,
Сообразно этому обстоятельству такая задача называется дробно-линейной. Чисто формальным приемом ввода новых переменных =1/ и = соответствующим преобразованием ЦФ и умножением неравенств системы ограничений на дробно-линейная задача сводится к линейной: ⟶ max, Дополнительное условие-равенство в системе ограничений возникает в результате следующих преобразований =1/ ⇒ =1 ⇒ =1 ⇒ =1. В довершение ко всему сохраняется не отрицательность переменных. После решения задачи по найденным значениям переменных восстанавливается оптимальный план исходной задачи = / , Таким образом, использованная замена переменных является вполне конструктивной.
5.4. Транспортная задача Важный класс задач линейного программирования представляет так называемая транспортная задача. При планировании перевозок грузов естественным образом возникает стремление минимизировать транспортные расходы. Транспортная задача формулируется следующим образом. Имеется p баз, в которых находится единиц однородного продукта и q потребителей с потребностями в этом продукте. Стоимость перевозки единицы груза из i -го пункта j -му потребителю равна . Составить схему перевозок с минимальными транспортными расходами при условии сбалансированности спроса и потребления. Обозначим количество единиц груза, перевозимого из i -го пункта j -му потребителю. Суммарные транспортные затраты подлежат минимизации с учетом наличных запасов и потребностей: ⟶ min, Здесь первое условие в системе ограничений означает полное удовлетворение потребностей, а второе – полное использование запасов. В итоге имеем строгий баланс потребностей и запасов , при котором транспортная задача всегда имеет решение. Рассмотренная выше простейшая однопродуктовая транспортная модель может быть расширена до многопродуктовой. Кроме того, множество практических задач органично содержит транспортную составляющую. Применительно к примеру с пекарнями это может выглядеть следующим образом. Фирма располагает рядом пекарен и точек реализации произведенной продукции, которую развозит на своем транспорте. Требуется найти оптимальную схему прикрепления магазинов к пекарням, обеспечивающую минимум транспортных расходов. Поскольку в данном случае производитель сам же занимается и транспортировкой свой продукции, то целесообразно объединение производственной и транспортной составляющих в рамках одной модели минимизации суммарных производственных и транспортных затрат с учетом действующих ограничений. Симбиоз производственной и транспортной составляющих в рамках одной модели может быть реализован следующим образом. Заметим, что максимизация целевой функции L эквивалентна минимизации противоположной по знаку функции –L. По этой причине представляется возможным формирование гибридной целевой функции, в которой производственный сектор представлен показателем суммарной прибыли, взятым с обратным знаком, а транспортная составляющая содержит транспортные расходы. Обе эти компоненты целесообразно взять с весовыми коэффициентами, составляющими в своей сумме единицу. В результате критерий оптимальности "min" обеспечит максимальный совокупный эффект при определенной сбалансированности интересов производственной и транспортной составляющих. С помощью весовых коэффициентов можно варьировать интересами соответствующих секторов, склоняя их по своему усмотрению в ту или иную сторону.
5.5. Математическое программирование Если речь идет о производстве дорогостоящих изделий или о выборе стратегии поведения системы из некоторого множества возможностей (нулевое значение переменной означает отклонение соответствующей стратегии, а единица – её принятие), то дробный ответ устроить никак не может. В этом случае на переменные налагается дополнительное требование целочисленности. Такие задачи являются предметом целочисленного программирования, методы которого по сравнению с ЛП являются более сложными. В реальных условиях соотношения оптимизационной задачи нередко оказываются существенно нелинейными. В общем случае целевая функция и система ограничений выражаются некоторыми функциями. Такие задачи решаются методами нелинейного программирования. Отдельный класс составляет нелинейные задачи, являющиеся по своей сути многошаговыми, с последовательным принятием на каждом шаге решений, обеспечивающих оптимальное развитие некоторой начальной ситуации. Решением таких задач занимается динамическое программирование (ДП). Несмотря на то, что методология ДП находится за пределами настоящего курса, стоит привести её основу, известную под названием «принцип оптимальности Беллмана», который формулируется следующим образом: каково бы ни было начальное и текущее состояние системы перед очередным шагом (этапом) планирования, все последующие решения должны обеспечивать максимальный эффект (выигрыш) относительно состояния, сложившегося в результате решений, принятых на предыдущих шагах. Этот принцип позволяет построить алгоритм численного решения многошаговой задачи в виде рекуррентных соотношений. Кроме того, он представляет собой по сути дела руководство к действию в многошаговых процедурах принятия решений даже на интуитивном уровне, конечно, при наличии возможности хотя бы оценить последствия принимаемых решений. Стратегический многолетний план развития объекта складывается из последовательности этапов, на каждом из которых обозначаются тактические цели. В содержательном отношении эти частные цели и пути их реализации на каждом этапе могут отличаться друг от друга самым существенным образом. В то же время, в своей совокупности они должны быть согласованы между собой в интересах достижения глобальной конечной цели. Грамотное решение задачи согласования обеспечивает применение методологии системного анализа. Принцип оптимальности Беллмана находится в полном соответствии с практикой планирования и функционирования реальных систем. В самом деле, в процессе деятельности системы обстановка может меняться самым непредвиденным образом, вследствие чего коррекция планов становится неизбежной. Поэтому, находясь в условиях постфактум, в начале каждого шага разумно обеспечить оптимальное развитие последующих состояний системы все зависимости от её предыстории. Реалии бизнеса таковы, что, несмотря на наличие планов на перспективу, их реализация осуществляется поэтапно с корректировкой решений на последующую часть планового периода по мере поступления информации о фактических достижениях. При этом рынок по сути дела является противодействующей стороной с неясной и неоднозначной реакцией, что порождает неопределенность условий функционирования объекта. Такие задачи составляют предмет стохастического многошагового программирования и многошаговых игр, а также интенсивно развивающейся в последнее время методологии нечеткой логики и нейронных сетей. Изменение исходных данных может существенно повлиять на предсказываемое поведение объекта. Если сравнительно малым изменениям исходных данных отвечают малые изменения конечных результатов, то такая модель называется устойчивой. Устойчивость модели относительно возмущения исходных данных повышает надежность выводов и в этом смысле является безусловно положительным качеством. Рассмотренные выше обстоятельства ничуть не умоляют достоинств ЛП, которое с успехом применяется при решении большого числа практических задач. Поэтому в дальнейшем мы ограничимся изучением ЛП, образующего обширный и в то же время наиболее доступный для понимания класс линейных экономико-математических моделей. В заключение следует отметить, что в своей деятельности мы стараемся принимать решения, следуя именно принципу оптимальности - с наибольшей для себя выгодой. Другое дело, что в силу различных причин достигать оптимальности удается далеко не всегда. Однако это ничуть не снижает практической значимости оптимизационных задач.
5.6. Геометрические аспекты линейного программирования Часть плоскости по одну сторону от прямой линии называется полуплоскостью, т.е. прямая делит плоскость на две полуплоскости. Каждое линейное неравенство обращается в равенство на прямой линии. Неравенство ">" выполняется в той полуплоскости, на которую указывает нормальный вектор прямой. В другой полуплоскости действует противоположное неравенство "<".Для доказательства возьмем неравенство вида . Множеству точек, для которых имеет место равенство, отвечает прямая l: с нормальным вектором . Возьмем точку прямой , т.е. и сместимся из нее вдоль нормали на некоторую величину, что может быть выражено так → () + t = () + t = (), . Подставив координаты полученной таким образом точки в левую часть уравнения прямой, найдем, что для любого t >0 + = . Таким образом, неравенство ">" справедливо по ту сторону прямой, т.е. в той полуплоскости, на которую ориентирован ее нормальный вектор. Каждому ограничению задачи ЛП с двумя переменными отвечает своя полуплоскость, в которой оно выполняется. Множество точек М, где справедливы все ограничения задачи, как общая часть всех полуплоскостей представляет собой выпуклый многоугольник (вместе с любыми двумя своими точками содержит весьсоединяющий их отрезок). В дальнейшем пригодится то обстоятельство, что по аналогичной причине направление возрастания линейной целевой функции указывает вектор, составленный из её коэффициентов (нормальный вектор). В теории ЛП доказывается, что в многомерном случае (аналогично плоскости) множество М представляет собой выпуклый многогранник допустимых решений (МДР), а оптимум целевой функции достигается, по крайней мере, в одной из его вершин. Эта вершина вычисляется как решение соответствующей системы линейных уравнений, взятых из системы ограничений как равенства. Достижение оптимума возможно не только в одной вершине, но и на целом ребре (отрезке, соединяющем две смежные вершины) или даже грани М, и тогда задача имеет бесконечно много решений. Несовместность системы условий задачи означает отсутствие хотя бы одной вершины многогранника допустимых решений (М – пустое множество). В системе условий задачи, возможно, имеются несущественные, т.е. те, которые могут быть исключены без всякого ущерба. Вот собственно и все основные сведения, которых в совокупности с изложенным ранее материалом вполне достаточно для решения приведенной ниже простой задачи ЛП на плоскости:
L () = ⟶ max, Задачу ЛП с двумя переменными можно решить геометрическим методом, который реализуется следующим образом: строится многогранник допустимых решений М; находятся его вершины как пересечения соот-
L (2, 1)= -1, L (1, 2)=1, L (1, 36/7)= 29/7≈4.1, L (35/6, 1)= -29/6≈-4,8. Таким образом, ответ: =1, =36/7, = L ()=29/7. Этот результат можно было получить сразу после построения многоугольника М, если учесть, что он должен целиком располагаться под плоскостью = max. На рисунке изображена прямая L, отвечающая целевой функции, и построен нормальный вектор =(-1, 1), указывающий направление возрастания ЦФ. Очевидно, что вершина (1, 36/7) многоугольника М является искомой и дальнейший рост целевой функции на М невозможен, поскольку при любом сколь угодно малом смещении вдоль вектора контакт прямой (ЦФ) с М будет утрачен, а в ЦФ по условию задачи можно подставлять координаты точек только из М. Заметим, что очевидным следствием исключения из СУ задачи условий (II) и (V) будет неограниченность ЦФ на МДР.
5.7. Симплекс-метод Среди существующих алгоритмов решения общей задачи ЛП наибольшей известностью пользуется симплекс-метод. Формальная вычислительная схема этого метода в виде симплекс-таблиц (подобно расширенной матрице в методе Гаусса) детально изложена во многих источниках, поэтому ограничимся изучением его содержательной части. Для лучшего понимания симплекс-метода на идейном уровне рассмотрим решенную ранее геометрическим методом задачу ЛП, опустив несущественные ограничения: L () = ⟶ max, Преобразуем два последних неравенства в условия неотрицательности путем введения новых переменных = и = . В новых переменных задача примет вид L () = ⟶ max, Введением балансовых переменных и ограничения задачи превращаются в равенства с равноправными неотрицательными переменными: При этом целевая функция задачи формально может быть записана в виде L () = + 0 + 0 . Теперь из каждого уравнения выберем по одной переменной, которые будут называться базисными, и выразим их через остальные так называемые свободные переменные. В качестве базисных удобно принять переменные и и тогда и будут свободными: Полагая свободные переменные не отрицательными и обеспечивающими также неотрицательность базисных переменных, например, =0, =1, найдем начальное допустимое решение =(0, 1, 0, 22), =1. На этом заканчивается подготовительный шаг симплекс-метода. Первая итерация. ЦФ нашей задачи такова, что ее увеличение возможно только за счет роста переменной при =0. Однако рост ограничивает второе равенство, допускающее в качестве максимального значения =29/7 из расчета обращения в 0. Подставив в уравнения и ЦФ значения свободных переменных, найдем первое допустимое решение =(0, 29/7, 22/7, 0), = 29/7. Начиная с этого момента, на каждой итерации в качестве свободных будут приниматься переменные с нулевыми координатами в найденном допустимом решении. Преобразуя в соответствии с этим правилом систему ограничений и целевую функцию, получим сначала второго уравнения в первое и в ЦФ, найдем L = . Вторая итерация. Поскольку все коэффициенты ЦФ отрицательны, то ее дальнейший рост невозможен ни при каких положительных значениях свободных переменных, что свидетельствует об окончании решения задачи. Таким образом, =0, = 29/7 и возвращаясь к исходным переменным, получаем = +1=1, = +1=36/7, = 29/7. В отличие от системы линейных уравнений проверка правильности решения задачи ЛП в целом является весьма сложной вычислительной процедурой. Прямой подстановкой можно установить лишь то, что найденное решение удовлетворяет системе ограничений задачи. Для проверки оптимальности найденного решения достаточно воспользоваться аппаратом векторной алгебры.
При одном взгляде на рисунок очевидна аналогия ситуации максимума с достигшим вершины альпинистом, тело которого (от ног к голове) сориентировано в направлении нормального вектора целевой функции, и всю гору (МДР) он видит целиком под собой внизу. Приведенный выше численный вариант симплекс-метода без использования симплекс-таблиц годится лишь для задач с двумя-тремя переменными и столь же малоэффективен, как и решение системы линейных уравнений путем прямой замены неизвестной в одном уравнении ее выражением, полученным из другого уравнения. Этот алгоритм рассматривался исключительно с целью не упустить за формальными расчетами существо механизма поиска оптимума линейной задачи. Основная идея симплекс-метода заключается в переходе на каждом шаге алгоритма в такую вершину многогранника допустимых решений, чтобы значение целевой функции в смысле критерия оптимальности улучшилось или, по крайней мере, не ухудшилось. Далее процесс циклично повторяется. Содержанием каждой итерации является проверка возможности улучшения значения ЦФ и вычисление следующего допустимого решения путем пересчета коэффициентов системы. По сути дела симплекс-метод является методом последовательного улучшения допустимого решения. В процессе его применения реализуется одна из следующих ситуаций: - устанавливается факт несовместности системы ограничений; - вычисляется оптимальное решение задачи и определяется, единственно оно или нет; - выявляется неограниченность ЦФ на МДР. Вычислительная схема симплекс-метода такова. Сначала с помощью балансовых переменных система ограничений задачи ЛП сводится к системе равенств, и заполняется симплекс-таблица, которая подобно расширенной матрице системы линейных уравнений содержит все числовые коэффициенты ЦФ и СО, а также ряд вспомогательных параметров. Затем находится начальное допустимое решение, или выявляется несовместность системы ограничений задачи (М=∅). Весь процесс последующих вычислений представляет собой последовательность итераций, на каждой из которых по определенным правилам происходит преобразование симплекс-таблицы, обеспечивающее последовательное улучшение значения целевой функции до тех пор, пока не будет найдено оптимальное решение задачи или установлена неограниченность целевой функции задачи. Признаком неограниченности целевой функции на множестве допустимых решений является возможность улучшения её величины при отсутствии ограничений на значения фигурирующих в ней переменных. Применение симплекс-таблиц обеспечивает эффективное решение задач любой размерности и детально изучается в любом серьезном учебнике, содержащем раздел "Линейное программирование". Для найденного решения задачи может быть произведен после- оптимизационный анализ результатов расчетов, позволяющий в частности оценивать устойчивость моделей ЛП.
Практикум При решении задач в меру необходимости применяется логика рассуждений - практически такая же, каковой мы пользуемся в своей повседневной деятельности. Ход решения задач предопределяется исходными данными. Матрицы Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.025 сек.) |