Мат.модели. 1. Методы оптимальных решений Постановка задачи оптимизации
 Скачать 0.5 Mb.
|
|
1 2
ВВЕДЕНИЕ Дисциплина «Методы оптимальных решений» входит в базовую часть математического и естественно-научного цикла дисциплин направления подготовки 080100.62 Экономика (профили Бухгалтерский учет, анализ и аудит. Экономика предприятий и организаций). Необходимыми условиями для освоения дисциплины является знание основных положений линейной алгебры, математического анализа, теории вероятностей и математической статистики. Целью изучения дисциплины «Методы оптимальных решений» является формирование представлений о методах, моделях и приёмах теории исследования операций с их последующим применением в экономико-математическом моделировании. Методы оптимальных решений - математическая основа усвоения специальных дисциплин на старших курсах. Предлагаемое издание содержит обзор рассматриваемой дисциплины и задачи для самостоятельного решения по основным разделам курса: экономико-математические оптимизационные модели, линейное программирование, теория игр. Каждая задача составлена в 25 вариантах. 1. Методы оптимальных решений 1.1. Постановка задачи оптимизации Оптимизационные задачи в экономике возникают в связи с широким спектром возможных вариантов функционирования конкретного экономического объекта, когда создается ситуация выбора варианта, наилучшего с точки зрения определенного критерия. Оптимизация – выбор наилучшего (оптимального) варианта из множества возможных. В основе построения оптимизационных моделей лежит допущение о том, что все компоненты модели количественно измеримы. Оптимальность – не абсолютное понятие: нельзя говорить об оптимальности вообще, вне условий и без точно определенных критериев оптимальности. Критерий оптимальности – показатель, выражающий предельную меру экономического эффекта принимаемого решения для сравнительной оценки возможных решений (альтернатив) и выбора наилучшего из них. Это может быть максимум прибыли или минимум трудовых затрат, кратчайшее время достижения цели и т. д. Критерий оптимальности носит обычно количественный характер, т.е. он применяется для того, чтобы качественный признак плана, выражаемый соотношением «лучше – хуже» переводить в количественно определенное «больше – меньше». В экономико-математических задачах критерию оптимальности соответствует математическая форма – целевая функция, экстремальное значение которой характеризует предельно достижимую эффективность моделируемого объекта (т.е. наилучшие в заданном отношении структуру, состояние, траекторию развития). В общем виде задача оптимизации состоит в следующем: найти такие значения неизвестных  , которые удовлетворяют системе ограничений (уравнений, неравенств)  ,  и обращают в максимум (или минимум) целевую функцию  , т.е.  Значения неизвестных , удовлетворяющие ограничениям и обращающие в максимум (минимум) целевую функцию, называются оптимальным решением (или оптимальным планом).Термины «решение» и «план» – синонимы, однако первый используется чаще, когда речь идет о формальной стороне задачи (ее математическом решении), а второй – о содержательной стороне (экономической интерпретации). Приведенная задача имеет единственный показатель эффективности Z. Однако в практической деятельности приходится иметь дело с несколькими показателями  . Такие задачи называются многокритериальными. Например, при организации производства товаров или услуг необходимо ориентироваться одновременно на себестоимость производства, количество продукции, ее качество, влияние производства на окружающую среду и т. д.В данной работе рассматриваются задачи оптимизации с одним критерием оптимальности. 1.2. Экономико-математическое моделирование Математическое моделирование изучаемого экономического объекта (процесса) лежит в основе экономических исследований, так как позволяет описать количественные закономерности этого процесса в виде математических выражений. Модель – это условный образ объекта, формирующий представление о нем в некоторой форме, отличной от реально существующего данного объекта. Модель отображает основные характерные свойства объекта в некоторой абстрактной форме. Экономико-математическое моделирование дает возможность изучения объекта не непосредственно, а через рассмотрение другого, подобного ему и более доступного объекта - его модели. Математическая модель экономического объекта – это его отображение в виде совокупности уравнений, неравенств, логических отношений, графиков. Алгоритм решения задачи оптимизации методами экономико-математического моделирования представлен в виде схемы на рис. 1.  Рис 1. Алгоритм решения задачи 1.3. Основные методы оптимизации Классические методы решения задачи оптимизации хорошо известны – поиск условных экстремумов с помощью производной. Однако подобные методы имеют ограниченное применение по ряду причин: – когда аргументовх1, х2 , … хn много, совместное решение системы уравнений оказывается зачастую очень сложным; – как правило, экстремум наблюдается не в точке, где производная обращается в ноль, а на границе области принятия решений; – производных, о которых идет речь, может не существовать, например, если аргументы х1, х2 , …, хnизменяются дискретно, или же сама функция имеет особенности. Поэтому приходится применять численные методы оптимизации. Одним из таких методов является математическое программирование. Математическое программирование – область математики, объединяющая различные математические методы и дисциплины: линейное программирование, нелинейное программирование, динамическое программирование, выпуклое программирование и др. Линейное программирование (ЛП) – область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между переменными (все ограничения и целевая функция – линейные). Линейное программирование находит применение в решении широкого класса экономических задач: – задача об использовании ресурсов (задача планирования производства): при заданных ограничениях на ресурсы составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной; – задача об использовании мощностей (задача о загрузке оборудования) – распределение выпуска продукции между станками, минимизирующего затраты на производство всей продукции; – транспортная задача – задача о прикреплении поставщиков к потребителям, минимизирующем суммарные расходы на перевозки; – задача составления рациона (задача о диете, задача о смесях): при заданном содержании питательных веществ в каждом виде продукта необходимо составить дневной рацион, имеющий минимальную стоимость, в котором содержание каждого вида питательных веществ было бы не менее установленного предела; – задача о назначениях – распределительная задача, в которой для выполнения каждой работы требуется один и только один ресурс (один человек, одна автомашина и т. д.). То есть ресурсы неделимы между работами, а работы неделимы между ресурсами. Задача о назначениях имеет место при распределении людей на должности или работы, автомашин на маршруты, водителей на машины, групп по аудиториям, научных тем по научно-исследовательским лабораториям и т.п. – задача о раскрое. Производство многих видов промышленной продукции начинается с раскроя материала. Кроят не только одежду и обувь, но и детали корпуса корабля, кузова автомобиля, фюзеляжа самолета. Раскраивают ткани и кожу, бумагу и стекло, металл и пластмассу. В масштабах предприятия, отрасли, страны рациональный раскрой позволяет сэкономить колоссальные средства. Общепринятое понятие оптимальности расширяет теория игр. Принципиальным достоинством теории игр считают то, что она включает в это понятие такие важные элементы, как, например, компромиссное решение, устраивающее разные стороны в споре (игре). Теория игр – математическая теория конфликтных ситуаций. В экономике конфликтные ситуации встречаются очень часто и имеют многообразный характер. К ним относятся, например, взаимоотношения между поставщиком и потребителем, покупателем и продавцом, банком и клиентом. Во всех этих примерах конфликтная ситуация порождается различием интересов партнеров и стремлением каждого из них принимать оптимальные решения, которые реализуют поставленные цели в наибольшей степени. При этом каждому приходится считаться не только со своими целями, но и с целями партнера, и учитывать неизвестные заранее решения, которые эти партнеры будут принимать. Целью теории игр является определение оптимальных стратегий игроков. При выборе оптимальной стратегии естественно предполагать, что игроки ведут себя разумно с точки зрения своих интересов. На практике игровые подходы используются при разработке микроэкономических моделей, в которых учитываются интересы различных звеньев (например, отраслей и экономических районов). Кроме того, математические приемы теории игр могут применяться для решения практических экономических задач на промышленных предприятиях. Например, для выбора оптимальных решений в области повышения качества продукции или определения запасов. «Противоборство» здесь происходит в первом случае между стремлением выпустить больше продукции (затратить на нее меньше труда) и сделать ее лучше, т. е. затратить больше труда; во втором случае – между желанием запасти ресурсов побольше, чтобы быть застрахованным от случайностей, и запасти поменьше, чтобы не замораживать средства. 2. ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ Экономико-математические оптимизационные модели 1.1.–1.25. Составить экономико-математическую модель задачи. 1.1. Фирма рекламирует свою продукцию с помощью телевидения, радио, газет и афиш. Из опыта известно, что эти средства приводят к увеличению прибыли соответственно на 10, 3, 7 и 4 у. е. в расчете на одну у. е., затраченную на рекламу. Распределение рекламного бюджета подчинено следующим ограничениям: полный бюджет не должен превосходить 500 000 у. е.; следует расходовать не более 40 % бюджета на телевидение и не более 20 % бюджета на афиши; на радио следует расходовать по крайней мере половину того, что планируется на телевидение. Как распределить средства на рекламу продукции? 1.2. Управляющему банка были предоставлены 4 проекта, претендующие на получение кредита в банке. Доступная наличность банка, потребности проектов и прибыль по ним приведены в таблице:
При оценке этих предложений следует принять во внимание потребность проектов в наличности и массу доступной наличности для соответствующих периодов. Какие проекты следует финансировать и какое количество наличности необходимо в течение каждого периода, если цель состоит в том, чтобы максимизировать прибыль? 1.3. В планируемом периоде предприятию необходимо обеспечить производство 300 тыс. однородных изделий, которые могут выпускать четыре филиала. Выделены капитальные вложения в размере 18 млн. руб. Разработанные для каждого филиала проекты освоения нового вида изделия характеризуются величинами удельных капитальных вложений и себестоимостью единицы продукции:
Необходимо найти такой вариант распределения объемов производства продукции и капитальных вложений по филиалам, при котором суммарная стоимость изделий будет минимальной. 1.4. Имеются два склада готовой продукции: А1 и А2 с запасами однородного груза 200 и 300 т. Этот груз необходимо доставить трем потребителям: В1, В2 и В3 в количестве 100, 150, 250 т соответственно. Стоимость перевозки 1 т груза из склада А1 потребителям В1, В2 и В3 равна 5, 3, 6 д.е., а из склада А2 тем же потребителям – 3, 4, 2 д.е. соответственно. Составьте план перевозок, минимизирующий суммарные транспортные расходы. 1.5. На двух автоматических линиях выпускают аппараты трех типов. Условия приведены в таблице.
Составить такой план загрузки станков, чтобы затраты были минимальными, а задание выполнено не более чем за 10 суток. 1.6. На заготовительный участок поступили стальные прутья длиной 111 см. Необходимо разрезать их на заготовки по 19, 23 и 30 см. Заготовок требуется соответственно 311, 215 и 190 штук. Сформулировать экстремальную задачу выбора варианта выполнения этой работы, при котором число разрезаемых прутьев минимально. 1.7. В сплав может входить не менее 4 % никеля и не более 80 % железа. Для составления сплава используются три вида сырья, содержащего никель, железо и прочие вещества.
Сформулировать экстремальную задачу для определения состава шихты таким образом, чтобы стоимость 1 кг сплава была минимальной. 1.8. Фирма производит два безалкогольных напитка – лимонад и тоник. Объем производства ограничен количеством основного ингредиента и производственной мощностью оборудования. Для производства 1 л лимонада требуется 0,02 час. работы оборудования, а для производства 1 л тоника – 0,04 час. Расход специального ингредиента составляет 0,01 и 0,04 кг на 1 л лимонада и тоника соответственно. Ежедневно в распоряжении фирмы имеется 24 часа времени работы оборудования и 16 кг специального ингредиента. Доход фирмы составляет 0,1 руб. за 1 л лимонада и 0,3 руб. за 1 л тоника. Сколько продукции каждого вида следует производить ежедневно, если цель фирмы состоит в максимизации ежедневного дохода? 1.9. В металлургический цех в качестве сырья поступает латунь (сплав меди с цинком) четырех типов с содержанием цинка 10, 20, 25 и 40% по цене 10, 30, 40, 60 руб. за 1 кг соответственно. Составить модель для определения пропорций, в которых следует переплавлять это сырье в цехе, чтобы получить сплав (латунь) с 30 %-м содержанием цинка и при этом самый дешевый. 1.10. Из листов проката, имеющих форму прямоугольника 5×10, необходимо выкроить заготовки двух типов: А – 650 штук размером 3×4, В – 325 штук – 2×2,5, израсходовав при этом возможно меньше материала. Каким образом следует производить раскрой? 1.11. Три типа самолетов следует распределить между двумя авиалиниями. В таблице заданы количество самолетов каждого типа, месячный объем перевозок и соответствующие эксплуатационные расходы.
Следует распределить самолеты по авиалиниям так, чтобы при минимальных суммарных эксплуатационных расходах перевести по каждой из них соответственно не менее 300 и 200 ед. груза. 1.12. Предприятию задан план производства по времени и номенклатуре: требуется не более чем за шесть единиц времени выпустить 30 единиц продукции П1 и 96 единиц продукции П2. Каждый из видов продукции может производится машинами А и Б, значения мощностей которых и затраты для изготовления каждого вида продукции заданы в таблице:
Требуется составить оптимальный план работы машин, а именно: найти, сколько времени каждая из машин А и Б должна быть занята изготовлением каждого из вида продукции П1 и П2, чтобы стоимость всей продукции предприятия оказалась минимальной и в то же время был бы выполнен заданный план как по времени, так и по номенклатуре. 1.13. На приобретение оборудования (печей) для выпечки хлеба предприятие может выделить 30 тыс. у. е. Оборудование нужно разместить на площади, не превышающей 36 кв. м. Можно заказать оборудование двух видов. Менее мощная печь типа А стоит 4 тыс. у. е., требует производственную площадь 4 кв. м и имеет производительность 200 кг за смену. Печь типа В стоит 5 тыс. у. е., требует площадь 9 кв. м, ее производительность 300 кг за смену. Требуется составить план приобретения оборудования, обеспечивающий максимальную общую производительность за смену. 1.14. Требуется раскроить 5000 прямоугольных листов фанеры размером 4 на 5 м каждый, с тем чтобы получить 2 вида прямоугольных деталей: деталь А должна иметь размер 2×2 м, деталь Б – размер 1×3 м. Необходимо чтобы деталей А оказалась не меньше, чем деталей Б. Каким образом следует производить раскрой, чтобы получить минимальное (по площади) количество отходов? 1.15. Фирма производит три модели электронных реле. Каждая модель требует две стадии сборки. Время (в мин.), необходимое для сборки на каждой стадии, и прибыль за шт. приведены в таблице:
Оборудование на каждой стадии работает 7,5 час в день. Менеджер хочет максимизировать прибыль за следующие 5 рабочих дней. Фирма может продать все, что произведет, и, кроме того, имеет оплаченный заказ на следующую неделю – 60 шт. изделий (по 20 шт. устройства каждого типа). Каков должен быть оптимальный производственный план? 1.16. На заводе выпускают изделия четырех типов. От реализации 1 ед. каждого изделия завод получает прибыль соответственно 2, 1, 3, 5 д.е. На изготовление изделий расходуются ресурсы трех типов: энергия, материалы, труд. Данные о технологическом процессе приведены в следующей таблице:
Спланируйте производство изделий так, чтобы прибыль от их реализации была наибольшей. 1.17. Имеются две почвенно-климатические зоны, площади которых соответственно равны 0,8 и 0,6 млн. га. Данные об урожайности зерновых культур приведены в следующей таблице:
Определите размеры посевных площадей озимых и яровых культур, необходимые для достижения максимального выхода продукции в стоимостном выражении. 1.18. Нефтеперерабатывающий завод производит за месяц 1 500 000 л алкилата, 1 200 000 л крекинг-бензина, 1 300 000 л изопентона. В результате смешивания этих компонентов в пропорциях 1:1:2 и 3:1:2 получается бензин сорта А и Б соответственно. Стоимость 1000 л бензина типа А и Б соответственно равна 90 руб. и 120 руб. Составить модель для определения месячного плана производства бензина сорта А и Б, максимизирующего стоимость выпущенной продукции. 1.19. На предприятии для производства запасных частей для автомобилей используется три вида ресурсов. Выпускаются три вида запасных частей. Организация производства на предприятии характеризуется следующей таблицей:
Составьте план производства запасных частей, обеспечивающий предприятию максимальную прибыль. 1.20. Цех выпускает три вида деталей – А, В, С. Каждая деталь обрабатывается тремя станками. Организация производства в цехе характеризуется следующей таблицей:
Составьте план загрузки станков, обеспечивающий цеху получение максимальной прибыли. 1.21. Из трех продуктов – I, II, III составляется смесь. В состав смеси должно входить не менее 6 ед. химического вещества А, 8 ед. – вещества В и не менее 12 ед. вещества С. Структура химических веществ приведена в следующей таблице:
Составьте наиболее дешевую смесь. 1.22. Рацион для питания животных на ферме состоит из двух видов кормов А и В. Один килограмм корма А стоит 80 у. е. и содержит: 1 ед. жиров, 3 ед. белков, 1 ед. углеводов, 2 ед. нитратов. Один килограмм корма В стоит 10 у. е. и содержит 3 ед. жиров, 1 ед. белков. 6 ед. углеводов, 4 ед. нитратов. Составить наиболее дешевый рацион питания, обеспечивающий жиров не менее 6 ед., белков не менее 9 ед., углеводов не менее 8 ед., нитратов не более 16 ед. 1.23. Хозяйство располагает следующими ресурсами: площадь – 100 ед., труд – 120 ед., тяга – 80 ед. Хозяйство производит четыре вида продукции П1, П2, П3, П4. Организация производства характеризуется следующей таблицей. Составьте план выпуска продукции, обеспечивающий хозяйству максимальную прибыль.
1.24. Сельскохозяйственное предприятие отвело 3 земельных массива площадью 5 000, 8 000 и 9 000 га под посевы ржи, пшеницы и кукурузы. Средняя урожайность по массивам указана в таблице.
За 1 ц ржи предприятие получает 2 у.е. прибыли, за 1 ц пшеницы – 2,5 у.е, за 1 ц кукурузы – 1,4 у.е. Сколько гектаров и на каких массивах следует отвести под каждую культуру, чтобы получить максимальную прибыль, если по плану необходимо сдать не менее 1 900 т ржи, 15 800 т пшеницы и 30 000 т кукурузы? 1.25. Для серийного производства некоторого изделия требуются комплекты заготовок профильного проката. Каждый комплект состоит из двух заготовок длиной 1800 мм и пяти заготовок длиной 1700 мм. Как следует раскроить 770 полос проката стандартной длины 6 000 мм, чтобы получить наибольшее количество указанных комплектов?  Линейное программирование2.1.–2.25. Построить на плоскости область решений системы линейных неравенств и геометрически найти наименьшее и наибольшее значения линейной функции.
1 2
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
