В учебнике представлены модели линейного и целочисленного программирования, классические методы оптимизации, задачи выпуклого и динамического программирования, модели управления запасами и сетевого планирования и управления, элементы теории игр и массового обслуживания, оптимизация финансового портфеля. В книге содержится большое количество задач. Задачи с решениями представлены на протяжении всего изложения учебного материала, а задачи для самостоятельной работы приведены в конце каждой главы.
Шаг 1. Выбирайте книги в каталоге и нажимаете кнопку «Купить»;
Шаг 2. Переходите в раздел «Корзина»;
Шаг 3. Укажите необходимое количество, заполните данные в блоках Получатель и Доставка;
Шаг 4. Нажимаете кнопку «Перейти к оплате».
На данный момент приобрести печатные книги, электронные доступы или книги в подарок библиотеке на сайте ЭБС возможно только по стопроцентной предварительной оплате. После оплаты Вам будет предоставлен доступ к полному тексту учебника в рамках Электронной библиотеки или мы начинаем готовить для Вас заказ в типографии.
Внимание! Просим не менять способ оплаты по заказам. Если Вы уже выбрали какой-либо способ оплаты и не удалось совершить платеж, необходимо переоформить заказ заново и оплатить его другим удобным способом.
Оплатить заказ можно одним из предложенных способов:
- Безналичный способ:
- Банковская карта: необходимо заполнить все поля формы. Некоторые банки просят подтвердить оплату – для этого на Ваш номер телефона придет смс-код.
- Онлайн-банкинг: банки, сотрудничающие с платежным сервисом, предложат свою форму для заполнения.
Просим корректно ввести данные во все поля.
Например, для " class="text-primary">Сбербанк Онлайн требуются номер мобильного телефона и электронная почта. Для " class="text-primary">Альфа-банка потребуются логин в сервисе Альфа-Клик и электронная почта. - Электронный кошелек: если у Вас есть Яндекс-кошелек или Qiwi Wallet, Вы можете оплатить заказ через них. Для этого выберите соответствующий способ оплаты и заполните предложенные поля, затем система перенаправит Вас на страницу для подтверждения выставленного счета.
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
1. Общие понятия и определения в и сследование операций
Следует усвоить основные понятия и определения исследования операций.
Операция -- любое управляемое мероприятие, направленное на достижение цели. Результат операции зависит от способа ее проведения, организации, иначе -- от выбора некоторых параметров. Всякий определенный выбор параметров называется решением. Оптимальными считают те решения, которые по тем или иным соображениям предпочтительнее других. Поэтому основной задачей исследования операций является предварительное количественное обоснование оптимальных решений.
Замечание 1
Следует обратить внимание на постановку проблемы: само принятие решений выходит за рамки исследования операций и относится к компетенции ответственного лица или группы лиц, которые могут учитывать и другие соображения, отличные от математически обоснованных.
Замечание 2
Если в одних задачах исследования операций оптимальным является решение, при котором выбранный критерий эффективности принимает максимальное или минимальное значение, то в других задачах это вовсе не обязательно. Так, в задаче оптимальным можно считать, например, такое количество торговых точек и персонала в них, при котором среднее время обслуживания покупателей не превысит, например, 5 мин, а длина очереди в среднем в любой момент окажется не более 3 человек (1, стр. 10-11).
Эффективность производственно-коммерческой деятельности в значительной степени определяется качеством решений, повседневно принимаемым менеджерами разного уровня. В связи с этим большое значение приобретают задачи совершенствования процессов принятия решений, решить которые позволяет исследование операций. Термин «исследование операций» впервые начал использоваться в 1939-1940 гг. в военной области. К этому времени военная техника и ее управление принципиально усложнилось вследствие научно-технической революции. И поэтому к началу Второй мировой войны возникла острая необходимость проведения научных исследований в области эффективного использования новой военной техники, количественной оценки и оптимизации принимаемых командованием решений. В послевоенный период успехи новой научной дисциплины были востребованы в мирных областях: в промышленности, предпринимательской и коммерческой деятельности, в государственных учреждениях, в учебных заведениях.
Исследование операций - это методология применения математических количественных методов для обоснования решений задач во всех областях целенаправленной человеческой деятельности. Методы и модели исследования операций позволяют получить решения, наилучшим образом отвечающие целям организации.
Исследование операций -- это наука, занимающаяся разработкой и практическим применением методов наиболее эффективного (или оптимального) управления организационными системами.
Основной постулат исследования операций состоит в следующем: оптимальным решением (управлением) является такой набор значений переменных, при котором достигается оптимальное (максимальное или минимальное) значение критерия эффективности (целевой функции) операции и соблюдаются заданные ограничения.
Предметом исследования операций являются задачи принятия оптимальных решений в системе с управлением на основе оценки эффективности ее функционирования. Характерными понятиями исследования операций являются: модель, изменяемые переменные, ограничения, целевая функция.
Предмет исследования операций в реальности -- это системы организационного управления (организации), которые состоят из большого числа взаимодействующих между собой подразделений, причем интересы подразделений не всегда согласуются между собой и могут быть противоположными.
Целью исследования операций является количественное обоснование принимаемых решений по управлению организациями.
Решение, которое оказывается наиболее выгодным для всей организации, называется оптимальным, а решение, наиболее выгодное одному или нескольким подразделениям, будет субоптимальным.
В качестве примера типичной задачи организационного управления, где сталкиваются противоречивые интересы подразделений, рассмотрим задачу управления запасами предприятия.
Производственный отдел стремится выпускать как можно больше продукции при наименьших затратах. Поэтому он заинтересован в возможно более длительном и непрерывном производстве, т. е. в выпуске изделий большими партиями, ибо такое производство снижает затраты на переналадку оборудования, а следовательно и общие производственные затраты. Однако выпуск изделий большими партиями требует создания больших объемов запасов материалов, комплектующих изделий и т. д.
Отдел сбыта также заинтересован в больших запасах готовой продукции, чтобы удовлетворить любые запросы потребителя в любой момент времени. Заключая каждый контракт, отдел сбыта, стремясь продать как можно больше продукции, должен предлагать потребителю максимально широкую номенклатуру изделий. Вследствие этого между производственным отделом и отделом сбыта часто возникает конфликт по поводу номенклатуры изделий. При этом отдел сбыта настаивает на включении в план многих изделий, выпускаемых в небольших количествах даже тогда, когда они не приносят большой прибыли, а производственный отдел требует исключения таких изделий из номенклатуры продукции.
Финансовый отдел, стремясь минимизировать объем капитала, необходимого для функционирования предприятия, пытается уменьшить количество «связанных» оборотных средств. Поэтому он заинтересован в уменьшении запасов до минимума. Как видим, требования к размерам запасов у разных подразделений организации оказываются различными. Возникает вопрос, какая стратегия в отношении запасов будет наиболее благоприятной для всей организации. Это типичная задача организационного управления. Она связана с проблемой оптимизации функционирования системы в целом и затрагивает противоречивые интересы ее подразделений.
Основные особенности исследования операций:
1. Системный подход к анализу поставленной проблемы. Системный подход, или системный анализ, является основным методологическим принципом исследования операций, который состоит в следующем. Любая задача, какой бы частной она не казалась на первый взгляд, рассматривается с точки зрения ее влияния на критерий функционирования всей системы. Выше системный подход был проиллюстрирован на примере задачи управления запасами.
2. Для исследования операций характерно, что при решении каждой проблемы возникают все новые и новые задачи. Поэтому если сначала ставятся узкие, ограниченные цели, применение операционных методов не эффективно. Наибольший эффект может быть достигнут только при непрерывном исследовании, обеспечивающем преемственность в переходе от одной задачи к другой.
3. Одной из существенных особенностей исследования операций является стремление найти оптимальное решение поставленной задачи. Однако часто такое решение оказывается недостижимым из-за ограничений, накладываемых имеющимися в наличии ресурсами (денежные средства, машинное время) или уровнем современной науки. Например, для многих комбинаторных задач, в частности задач календарного планирования при числе станков п > 4, оптимальное решение при современном развитии математики оказывается возможным найти лишь простым перебором вариантов. Тогда приходится ограничиваться поиском «достаточно хорошего», или субоптимального решения. Поэтому исследование операций один из его создателей -- Т. Саати -- определил как «...искусство давать плохие ответы на те практические вопросы, на которые даются еще худшие ответы другими методами».
4. Особенность операционных исследований состоит в том, что они проводятся комплексно, по многим направлениям. Для проведения такого исследования создается операционная группа. В ее состав входят специалисты разных областей знания: инженеры, математики, экономисты, социологи, психологи. Задачей создания подобных операционных групп является комплексное исследование всего множества факторов, влияющих на решение проблемы, и использование идей и методов различных наук.
Каждое операционное исследование проходит последовательно следующие основные этапы:
1) описание задачи планирования,
2) построение математической модели,
3) нахождение решения,
4) проверка и корректировка модели,
5) реализация найденного решения на практике.
Описание задачи планирования:
· Задачи сетевого планирования и управления
рассматривают соотношения между сроками окончания крупного комплекса операций (работ) и моментами начала всех операций комплекса. Эти задачи состоят в нахождении минимальной продолжительности комплекса операций, оптимального соотношения величин стоимости и сроков их выполнения.
· Задачи массового обслуживания посвящены изучению и анализу систем обслуживания с очередями заявок или требований и состоят в определении показателей эффективности работы систем, их оптимальных характеристик, например в определении числа каналов обслуживания, времени обслуживания и т.п.
· Задачи управления запасами состоят в отыскании оптимальных значений уровня запасов (точек заказа) и размеров заказа. Особенность таких задач заключается в том, что с увеличением уровня запасов, с одной стороны, увеличиваются затраты на их хранение, но, с другой стороны, уменьшаются потери вследствие возможного дефицита запасаемого продукта.
· Задачи распределения ресурсов возникают при определенном наборе операций (работ), которые необходимо выполнять при ограниченных наличных ресурсах, и требуется найти оптимальные распределения ресурсов между операциями или состав операций.
· Задачи ремонта и замены оборудования актуальны в связи с износом и старением оборудования и необходимостью его замены с течением времени. Задачи сводятся к определению оптимальных сроков, числа профилактических ремонтов и проверок, а также моментов замены оборудования модернизированным.
· Задачи составления расписания (календарного планирования) состоят в определении оптимальной очередности выполнения операций (например, обработки деталей) на различных видах оборудования.
· Задачи планировки и размещения состоят в определении числа и места размещения новых объектов с учетом их взаимодействия с существующими объектами и между собой.
· Задачи выбора маршрута, или сетевые задачи, чаще всего встречаются при исследовании разнообразных задач на транспорте и в системе связи и состоят в определении наиболее экономичных маршрутов (1, стр.15).
2. Математическая форма моде ли
Моделирование - процесс исследования реальной системы, включающий построение модели, изучение ее свойств и перенос полученных сведений на моделируемую систему.
Модель - это некоторый материальный или абстрактный объект, находящийся в определенном объективном соответствии с исследуемым объектом, несущий о нем определенную информацию и способный его замещать на определенных этапах познания.
Математическое моделирование - процесс установления соответствия реальному объекту некоторого набора символов и выражений, например математических. Математические модели наиболее удобны для исследования и количественного анализа, позволяют не только получить решение для конкретного случая, но и определить влияние параметров системы на результат решения.
В создание современного математического аппарата и развитие многих направлений исследования операций большой вклад внесли российские ученые Л. В. Канторович, Н. П. Бусленко, Е. С. Вентцель, Н. Н. Воробьев, Н. Н. Моисеев, Д. Б. Юдин и многие другие. Особо следует отметить роль академика Л. В. Канторовича, который в 1939 г., занявшись планированием работы агрегатов фанерной фабрики, решил несколько задач: о наилучшей загрузке оборудования, раскрое материалов с наименьшими потерями, о распределении грузов по нескольким видам транспорта и др. Л. В. Канторович сформулировал новый класс условно-экстремальных задач и предложил универсальный метод их решения, положив начало новому направлению прикладной математики -- линейному программированию.
Значительный вклад в формирование и развитие исследования операций внесли зарубежные ученые Р. Акоф, Р. Беллман, Г. Данциг, Г. Кун, Дж. Нейман, Т. Саати, Р. Черч мен, А. Кофман и др. (1, стр. 17)
Этапы построения математических моделей :
Сущность построения математической модели состоит в том, что реальная система упрощается, схематизируется и описывается с помощью того или иного математического аппарата. Выделяют следующие основные этапы построения моделей.
Словесно описывается объект моделирования, цели его функционирования, среда, в которой он функционирует, выявляются отдельные элементы, возможные состояния, характеристики объекта и его элементов, определяются взаимосвязи между элементами, состояниями, характеристиками. Такое предварительное, приближенное представление объекта исследования называется концептуальной моделью. Этот этап является основой для последующего формального описания объекта.
2. Формализация операций
На основе содержательного описания определяется и анализируется исходное множество характеристик объекта, выделяются наиболее существенные из них. Затем выделяют управляемые и неуправляемые параметры, вводят символьные обозначения. Определяется система ограничений, строится целевая функция модели. Таким образом, происходит замена содержательного описания формальным (символьным, упорядоченным).
3. Проверка адекватности модели
Исходный вариант модели необходимо проверить по следующим аспектам:
1) все ли существенные параметры включены в модель?
2) нет ли в модели несущественных параметров?
3) правильно ли отражены связи между параметрами?
4) правильно ли определены ограничения на значения параметров?
Главным путем проверки адекватности модели исследуемому объекту выступает практика. После предварительной проверки приступают к реализации модели и проведению исследований. Полученные результаты моделирования подвергаются анализу на соответствие известным свойствам исследуемого объекта. По результатам проверки модели на адекватность принимается решение о возможности ее практического использования или о проведении корректировки.
4. Корректировка модели
На этом этапе уточняются имеющиеся сведения об объекте и все параметры построенной модели. Вносятся изменения в модель, и вновь выполняется оценка адекватности.
5. Оптимизация модели
Сущность оптимизации (улучшения) моделей состоит в их упрощении при заданном уровне адекватности. В основе оптимизации лежит возможность преобразования моделей из одной формы в другую. Основными показателями, по которым возможна оптимизация модели, являются время и затраты средств для проведения исследований и принятия решений с помощью модели.
Типы моделей:
В самом общем случае математическая модель задачи имеет вид:
max Z=F(x, y) (1.1)
при ограничениях
где Z=F(x, y) - целевая функция (показатель качества или эффективность) системы; х -- вектор управляемых переменных; у -- вектор неуправляемых переменных; Gi(x, y)-- функция потребления i-го ресурса; bi -- величина i-го ресурса (например, плановый фонд машинного времени группы токарных автоматов в станко-часах).
Определение 1. Любое решение системы ограничений задачи называется допустимым решением.
Определение 2. Допустимое решение, в котором целевая функция достигает своего максимума или минимума называется оптимальным решением задачи.
Для нахождения оптимального решения задачи в зависимости от вида и структуры целевой функции и ограничений используют те или иные методы теории оптимальных решений (методы математического программирования).
1. Линейное программирование, если F(x, y), -- линейны относительно переменных х.
2. Нелинейное программирование, если F(x, y) или -- нелинейны относительно переменных х.
3. Динамическое программирование, если целевая функция F(x, y) имеет специальную структуру, являясь аддитивной или мультипликативной функцией от переменных х.
F(x)=F(x1, x2, …, xn) -- аддитивная функция, если F(x1, x2, …, xn)=, и функция F(x1, x2, …, xn) -- мультипликативная функция, если F(x1, x2, …, xn)=.
4. Геометрическое программирование, если целевая функция F(x) и ограничения представляют собой функции вида
Математическая модель задачи в этом случае записывается в виде
при условиях
где I=(m0, m0+1, …, n0); I[k]= (mk, mk+1, …, nk); mk+1=nk+1; m0=1; n0=n.
5. Стохастическое программирование, когда вектор неуправляемых переменных у случаен.
В этом случае математическая модель задачи (1.1--1.2) будет иметь
maxMyE=My{f(x, y)}
при ограничениях
или вероятностных ограничениях
где My -- математическое ожидание по у; Р{gi (х)Ј b} -- вероятность того, что выполняется условие gi (х)Ј b.
6. Дискретное программирование, если на переменные xj наложено условие дискретности (например, целочисленности): xj -- целое, j=1,2,…,n1Јп.
7. Эвристическое программирование применяют для решения тех задач, в которых точный оптимум найти алгоритмическим путем невозможно из-за огромного числа вариантов. В таком случае отказываются от поиска оптимального решения и отыскивают достаточно хорошее (или удовлетворительное с точки зрения практики) решение. При этом пользуются специальными приемами -- эвристиками, позволяющими существенно сократить число просматриваемых вариантов. Эвристические методы также применяют, когда оптимальное решение в принципе может быть найдено (т.е. задача алгоритмически разрешима), однако для этого требуются объемы ресурсов, значительно превышающие наличные.
Из перечисленных выше методов математического программирования наиболее развитым и законченным является линейное программирование. В его рамки укладывается широкий круг задач исследования операций.
3. Линейное программирование
Несмотря на требование линейности целевой функции и ограничений, в рамки линейного программирования укладываются задачи распределения ресурсов, управления запасами, сетевого и календарного планирования, транспортные задачи, задачи теории расписаний и т. д.
Основные теоремы линейного программирования
В основе методов решения задач линейного программирования лежат следующие теоремы.
Основная теорема линейного программирования, устанавливающая место нахождения оптимальных решений.
Теорема 2.1. Если целевая функция принимает максимальное значение в некоторой точке допустимого множества R, то она принимает это значение в крайней точке R (вершине выпуклого многогранника). Если целевая функция принимает максимальное значение более, чем в одной крайней точке, то она принимает это же значение в любой их выпуклой комбинации.
Из теоремы 2.1 следует, что при отыскании оптимального решения достаточно просмотреть только крайние точки допустимого множества решений R.
Теорема 2.2. Каждое допустимое базисное решение соответствует крайней точке R.
Справедлива также следующая теорема, обратная к теореме 2.2. Теорема 2.3. Если -- крайняя точка допустимого множества решений R, то соответствующее решение x0 -- является допустимым базисным решением системы ограничений задачи линейного программирования.
Используя результаты теорем 2.1 и 2.2, можно сделать вывод, что для отыскания оптимального решения задачи линейного программирования достаточно перебрать лишь допустимые базисные решения. Этот вывод лежит в основе многих методов решения задач линейного программирования.
Определение оптимального ассортимента. Имеется р видов ресурсов в количествах а1, а2, ..., аi, ..., аp и q видов изделий. Задана матрица А=||aik||, где аik характеризует нормы расхода i-го ресурса на единицу k-го изделия (k = 1, 2, ..., q).
Эффективность выпуска единицы k-го изделия характеризуется показателем сi, удовлетворяющим условию линейности.
Определить план выпуска изделий (оптимальный ассортимент), при котором суммарный показатель эффективности принимает наибольшее значение.
4. Нелинейное программирование
В данной главе описываются оптимизационные задачи нелинейного программирования (НЛП), математические модели которых содержат нелинейные зависимости от переменных. Источники нелинейности относятся в основном к одной из двух категорий:
1) реально существующие и эмпирически наблюдаемые нелинейные соотношения, например: непропорциональные зависимости между объемом производства и затратами; между количеством используемого в производстве компонента и некоторыми показателями качества готовой продукции; между затратами сырья и физическими параметрами (давление, температура и т.п.) соответствующего производственного процесса; между выручкой и объемом реализации и др.;
2) установленные (постулируемые) руководством правила поведения или задаваемые зависимости, например: формулы или правила расчета с потребителями энергии или других видов услуг; эвристические правила определения страховых уровней запаса продукции; гипотезы о характере вероятностного распределения рассматриваемых в модели случайных величин; различного рода договорные условия взаимодействия между партнерами по бизнесу и др.
Решать линейные задачи значительно проще, чем нелинейные, и если линейная модель обеспечивает адекватность реальным ситуациям, то ее и следует использовать. В практике экономического управления модели линейного программирования успешно применялись даже в условиях нелинейности. В одних случаях нелинейность была несущественной и ею можно было пренебречь, в других -- производилась линеаризация нелинейных соотношений или применялись специальные приемы, например строились так называемые линейные аппроксимационные модели, благодаря чему достигалась требуемая адекватность. Тем не менее имеется большое число ситуаций, где нелинейность является существенной и ее нужно учитывать в явном виде.
Основные понятия НЛП:
* целевую функция;
* ограничения;
* допустимый план;
* множество допустимых планов;
* модель нелинейного программирования;
* оптимальный план.
Необходимо уметь:
* определять, является ли функция выпуклой;
* строить функцию Лагранжа задачи НЛП;
* проверять оптимальность полученных решений.
Модели НЛП
В общем виде задача НЛП описывается с помощью следующей модели нелинейного программирования:
исследование операция моделирование математический
где х = (x1, х2, ..., хn) -- вектор переменных задачи.
Задача (1)--(3) называется задачей нелинейного программирования в стандартной форме на максимум.
Может быть сформулирована также задача НЛП на минимум.
Вектор х = (x1, х2, ..., хn), компоненты хj которого удовлетворяют ограничениям (2) и (3), называется допустимым решением или допустимым планом задачи НЛП.
Совокупность всех допустимых планов называется множеством допустимых планов.
Допустимое решение задачи НЛП, на котором целевая функция (1) достигает максимального значения, называется оптимальным решением задачи НЛП.
Возможное местонахождение максимального значения функции F(x) при наличии ограничений (2) и (3) определяется следующим общим принципом. Максимальное значение F(x), если оно существует, может достигаться в одной или более точках, которые могут принадлежать следующим множествам:
Внутренняя точка множества допустимых планов, в которой все первые частные производные
Точка границы множества допустимых планов};
Точка множества допустимых планов, в которой функция F(x) недифференцируема}.
В отличие от задач линейного программирования, любая из которых может быть решена симплекс-методом, не существует одного или нескольких алгоритмов, эффективных для решения любых нелинейных задач. Какой-то алгоритм может оказаться чрезвычайно эффективным для решения задач одного типа и неудачным для задач другого типа.
Эффективность алгоритма может даже существенно зависеть от постановки задачи, например от изменения масштабов измерения тех или иных переменных. Поэтому алгоритмы разрабатываются для каждого класса (типа) задач. Программы, ориентированные на решение определенного класса задач, как правило, не гарантируют правильность решения любых задач данного класса, и оптимальность решения рекомендуется проверять в каждом конкретном случае.
В экономических приложениях рассматриваются следующие классы задач НЛП.
На рисунке приводится классификация задач и методов нелинейного программирования.
Рисунок. Классификация задач и методов нелинейного программирования
Большинство существующих методов в нелинейном программировании можно разделить на два больших класса:
1. Прямые методы - методы непосредственного решения исходной задачи. Прямые методы порождают последовательность точек - решений, удовлетворяющих ограничениям, обеспечивающим монотонное убывание целевой функции.
2. Недостаток: трудно получить свойство глобальной сходимости.
3. Задачи с ограничениями в виде равенств.
4. Метод замены переменных (МЗП)
5. Двойственные методы - методы, использующие понятие двойственности. В этом случае легко получить глобальную сходимость.
6. Недостаток: не дают решения исходной задачи в ходе решения - оно реализуемо лишь в конце итерационного процесса.
o Метод множителей Лагранжа (ММЛ)
o Методы штрафов
o Метод множителей
o Методы линеаризации для задач условной оптимизации
o Алгоритм Франка-Вульфа
o Метод допустимых направлений Зойтендейка
o Метод условного градиента
o Метод проекции градиента
o Сепарабельное программирование.
o Квадратичное программирование
1. Оптимизация нелинейной функции с ограничениями на неотрицательность значений переменных:
где х = (х1, х2,..., хn) -- вектор переменных задачи.
Пусть F(x) -- дифференцируемая функция.
Необходимые условия того, что в точке х0 достигается максимум функции F(x):
Это означает, что:
Если F(x) вогнутая функция (для задачи минимизации -- выпуклая), то эти условия являются также достаточными.
Функция F(x) с числовыми значениями, определенная на выпуклом множестве точек К, называется вогнутой, если для любой пары точек х1, х2 и для всех чисел l, 0 Ј l Ј 1, выполняется неравенство
то функция F(x) называется выпуклой. Если имеют место строгие неравенства, то говорят, что функция строго вогнута или строго выпукла.
Данное определение вогнутости (выпуклости) годится для любого типа функции. Практически, однако, применять его трудно.
Для дважды дифференцируемой функции F(x) имеет место следующий критерий. Дифференцируемая функция F(x) строго вогнута в некоторой окрестности точки если выполняются следующие условия:
т.е. если знаки этих определителей чередуются указанным образом.
Здесь -- частная производная второго порядка, вычисленная в точке х0.
Матрица размера п ґ п, составленная из элементов, называется матрицей Хессе (Hesse). По значениям ее главных миноров можно судить о выпуклости или вогнутости функции. Функция F(x) строго выпукла в малой окрестности точки х0, если все главные миноры ее матрицы Хессе строго положительны. Если имеют место нестрогие неравенства (і), то функция в окрестности точки х0 выпукла. Если при этом главные миноры матрицы Хессе от х не зависят, то функция всюду (строго) выпукла.
Весьма распространены относящиеся к данному типу модели квадратичного программирования, в которых целевая функция F(x) является квадратичной функцией переменных х1, х2, ..., хn. Существует большое число алгоритмов решения такого типа задач, в которых функция F(x) вогнутая (для задач минимизации -- выпуклая).
2. Модели выпуклого программирования. К такого рода моделям относятся задачи НЛП (1)--(3), в которых F(x) -- вогнутая (выпуклая) функция, a gi(x) -- выпуклые функции. При данных условиях локальный максимум (минимум) является и глобальным.
Пусть F(x) и gi(x), i= 1,..., т, -- дифференцируемые функции.
Необходимые и достаточные условия оптимальности решения -- выполнение условий Куна -- Таккера.
Рассмотрим задачу НЛП (1)--(3) и функцию Лагранжа
Условия Куна -- Таккера оптимальности решения х0 для задачи максимизации F(x) имеют вид
где -- частная производная функции Лагранжа по переменной хj при х = х0 и l = l0. Пусть максимальное значение F(x) равно F(x0) = F0. Числа связаны с F0 следующими соотношениями:
Из этих соотношений видно, что числа характеризуют реакцию значения F0 на изменение значения соответствующего bi. Например, если < 0, то при уменьшении bi (в пределах устойчивости) значение F0 увеличится, а = 0 указывает на несущественность соответствующего ограничения gi(х) Ј bi, которое может быть без ущерба для оптимального решения из системы ограничений исключено.
3. Сепарабельное программирование. Специальный случай выпуклого программирования при условии, что F(x) и все gi(х) -- сепарабельные функции, т.е.
Задачи данного вида сводятся к задачам линейного программирования.
4. Дробно-нелинейное программирование. Максимизировать (минимизировать) функцию
F(x) = F1(x)/F2(x).
В частном случае, когда в числителе и знаменателе -- линейные функции (так называемая задача дробно-линейного программирования), задача сводится к линейной.
5. Невыпуклое программирование. Функция F(x) и (или) какие-либо gi(x) не выпуклы. Надежных методов решения задач такого типа пока не существует (3, стр. 74-77)
Как пример, рассмотрим нелинейную модель оптимального распределения ресурсов:
Описание задачи распределения ресурсов
Задача распределения ресурсов рассматривается для n предприятий. Центр осуществляет управление этими промышленными предприятиями, выпускающими однотипную продукцию. Обозначим через Рi объем продукции, выпускаемой предприятием i, i=1,. ..,n. Результат функционирования центра определяется результатами функционирования отдельных производителей, т.к. центр сам не производит продукции.
Считаем, что величина продукции, произведенной i-м предприятием, определяется объемом фондов Fi и количеством рабочей силы Li, согласие производственной функции Кобба- Дугласа:
Где i=1,..,n (4)
В выражении (4) di и ki характеристики предприятия i (i=1,.. .,n), удовлетворяющие условиям: di > 0 , i=1,...,n.
Пусть wi - ставка заработной платы на предприятии i. Тогда доля дохода предприятия i в общей сумме прибыли объединения определится так:
Gi =ci*Pi-wi*Li , i=1,. . .,n.
Если величина фондов предприятия фиксирована, то объем продукции Pi однозначно определяется количеством рабочей силы.
Центр влияет на работу предприятий распределением дополнительного ресурса, который полностью находиться в его распоряжении. Если предприятие i получит дополнительный ресурс в количестве Vi, то оно сможет произвести продукцию в объеме
Задача центра состоит в распределении имеющегося в его распоряжении ресурса В, т. е. в определении оптимальных значений величин Vi, i =1,...,n, обеспечивающих максимум суммарной прибыли объединения в целом.
Математическая форма модели
В данной задаче считаем, что используется схема централизованного планирования, в рамках которой центр рассчитывает оптимальное распределение ресурсов, оптимальные величины рабочей силы при заданных параметрах модели. Конкретно центр изменяет Vi и Li, i = 1,...,n, из условий:
z = max (G1 + G2 + ,..., + Gn) (6)
Vi, Vimin, Li 0,i=1,...,n (7)
Анализ чувствительности модели как способ восстановления финансового равновесия.
Основой сохранения и восстановления финансового равновесия предприятия и снижения уровня риска является анализ чувствительности предложенной модели. Анализ чувствительности состоит из следующих этапов:
1. Выбор ключевого показателя, т.е. такого параметра, относительно которого и рассчитывается чувствительность проекта (чаще всего это чистый приведенный доход и внутренняя норма доходности).
2. Выбор факторов, которые влияют на эти показатели.
3. Расчет значений ключевых показателей на разных этапах реализации проекта (поиск, проектирование, строительство, эксплуатация).
Чем выше чувствительность показателей к факторам внешней среды, тем более рискованным является проект. Для каждого показателя определяется чувствительность каждого момента времени или отрезка времени. Определяется эффективность проекта.
Часто во время анализа чувствительности определяется точка безубыточности проекта, т.е. определяется тот объем выпуска продукции, при котором предприятие выходит из зоны убытка.
Анализ чувствительности проекта разрешает специалистам учитывать риск и неопределенность. Например, если цена продукции оказалась критической, то возможно усилить программу маркетинга или снизить стоимость проекта. Если критическим окажется объем выпущенной продукции, то необходимо повысить квалификацию рабочих, уделить внимание обучению персонала, менеджерам и другим факторам повышения производительности.
Недостатки метода анализа чувствительности:
1. Метод не рассчитан на все случайное и возможное обстоятельства.
2. Метод не уточняет вероятность реализации альтернативных проектов.
Анализ чувствительности оптимального решения
Анализ чувствительности выполняется уже после получения оптимального решения задачи линейного программирования (ЛП). Его цель -- определить, приведет ли изменение коэффициентов исходной задачи к изменению текущего оптимального решения, и если да, то, как эффективно найти новое оптимальное решение (если оно существует).
В общем случае изменение коэффициентов исходной задачи может привести к одной из следующих четырех ситуаций.
1. Текущее базисное решение остается неизменным.
2. Текущее решение становится недопустимым.
3. Текущее решение становится неоптимальным.
4. Текущее решение становится неоптимальным и недопустимым.
Во второй ситуации можно использовать двойственный симплекс-метод для восстановления допустимости решения. В третьей ситуации мы используем прямой симплекс-метод для получения нового оптимального решения. В четвертой для получения нового оптимального и допустимого решения следует воспользоваться как прямым, так и двойственным симплекс-методом.
Список литературы
1. «Исследование операций в экономике» учебное пособие для Вузов, 3-е издание, переработанное и дополненное, под ред. Н.Ш.Кремера, М.: Юрайт, 2013.
2. T.В. Алесинская « Основы логистики. Общие вопросы логистического управления» .Учебное пособие. Таганрог: Изд-во ТРТУ, 2005.
3. Афанасьев М.Ю., Суворов Б.П. Исследование операций в экономике: модели, задачи, решения. Учебное пособие, М, Инфра-М, 2003 г.
4. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. -М.: Мир,1984.
5. Грешилов А.А. Как принять наилучшее решение в реальных условиях. - М.: Радио и связь, 1991.
6. Попов Ю.Д. Линейное и нелинейное программирование. Учебное пособие. - Киев, 1988.
7. Зайченко Ю.П. Исследование операций. Учебное пособие для студентов вузов. - Киев: Вища школа. Головное издательство, 1979
8. Таха Х.. Введение в исследование операций: в 2-х книгах. - М.: Мир, 1985.
9. Акоф Р., Сасиени М. Основы исследования операций. - М.: Мир, 1997.
10. Акулич И.Л. Математическое программирование в примерах и задачах. - М.: Высшая школа, 1986.
11. Данко. Высшая математика в примерах и задачах.
12. Алексеев В. М., Голеев В. М., Тихомиров В. М. Сборник задач по оптимизации: Теория, примеры, задачи. М., Наука, 1984.
13. Берман Г. Н. Сборник задач по курсу математического анализа. М., Наука, 1985.
14. Ильин В.А.., Позняк Э.Г. Линейная алгебра. М., Наука, 1983.
15. Ильин В.А.., Позняк Э.Г. Основы математического анализа. М., Наука, Ч.1,2, 1980.
16. Клетеник Д..В. Сборник задач по аналитической геометрии. М., Наука, 1984.
17. Кудрявцев Л.Д.. Курс математического анализа. М., Высш. шк., Т. 1-3, 1988.
18. Кудрявцев Л.Д.. Краткий курс математического анализа. М., Наука, 1989.
19. Кудрявцев Л.Д.., Кутасов А..Д., Чехлов В.И., Шабунин М.И. Сборник задач по математическому анализу. Предел. Непрерывность. Дифференцируемость. М., Наука, 1984.
20. Кремер Н. Ш., Путко Б. А.., Тришин И.М., Фридман М. Ф. Высшая математика для экономистов. М., Банки и биржи, ЮНИТИ, 1998.
21. Гмурман В.Е. Теория вероятностей и математическая статистика. Учебное пособие для вузов. М., Высш. шк., 1999.
22. Ниворожкина Л.И., Морозова З.А. Основы статистики с элементами теории вероятностей для экономистов. Руководство для решения задач. Ростов н/Д., Феникс., 1999.
23. Данко П.Е. Высшая математика в упражнениях и задачах. Ч.2. М., Высш. шк., 1997.
24. Чистяков В.П. Курс теории вероятностей. М., Наука., 1987.
25. Севастьянов Б. А. Курс теории вероятностей и математической статистики. М., Наука., 1982.
26. Севастьянов Б.А., Чистяков В.П., Зубков А.М. Сборник задач по теории вероятностей. М., Наука., 1980.
27. Вентцель Е.С Исследование операций. Задачи. Принципы. Методология, 1980.
28. Горелик В.А., Ушаков И.А. Исследование операций. - М.: Машиностроение, 1986.
29. Исследование операций/ Под редакцией М.А. Войтенко и Н.Ш. Кремера.-М.: Экономическое образование, 1992.
30. Карасев А.И., Аксютин З.М., Савельева Т.И. Математические методы и модели в планировании М.: Экономика, 1987.
31. Исследование операций / Н. Н. Писарук. Минск: БГУ, 2013.272 c.
Размещено на Allbest.ru
...Подобные документы
Графическое решение задач линейного программирования. Решение задач линейного программирования симплекс-методом. Возможности практического использования математического программирования и экономико-математических методов при решении экономических задач.
курсовая работа , добавлен 02.10.2014
Понятие и типы моделей. Этапы построения математической модели. Основы математического моделирования взаимосвязи экономических переменных. Определение параметров линейного однофакторного уравнения регрессии. Оптимизационные методы математики в экономике.
реферат , добавлен 11.02.2011
Изучение экономических приложений математических дисциплин для решения экономических задач: использование математических моделей в экономике и менеджменте. Примеры моделей линейного и динамического программирования как инструмента моделирования экономики.
курсовая работа , добавлен 21.12.2010
Основные понятия линейной алгебры и выпуклого анализа, применяемые в теории математического программирования. Характеристика графических методов решения задачи линейного программирования, сущность их геометрической интерпретации и основные этапы.
курсовая работа , добавлен 17.02.2010
Математическая формализация оптимизационной проблемы. Геометрическая интерпретация стандартной задачи линейного программирования, планирование товарооборота. Сущность и алгоритм симплекс-метода. Постановка транспортной задачи, последовательность решения.
учебное пособие , добавлен 07.10.2014
Теоретические основы экономико-математических методов. Этапы принятия решений. Классификация задач оптимизации. Задачи линейного, нелинейного, выпуклого, квадратичного, целочисленного, параметрического, динамического и стохастического программирования.
курсовая работа , добавлен 07.05.2013
Общая постановка задачи линейного программирования (ЛП). Приведение задачи ЛП к стандартной форме. Теоремы двойственности и их использование в задачах ЛП. Транспортная задача и её решение методом потенциалов. Интерполирование табличных функций.
курсовая работа , добавлен 31.03.2014
Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования. Математическая постановка задачи линейного программирования. Общий вид задачи линейного программирования.
реферат , добавлен 28.12.2008
Модель динамического программирования. Принцип оптимальности и уравнение Беллмана. Описание процесса моделирования и построения вычислительной схемы динамического программирования. Задача о минимизации затрат на строительство и эксплуатацию предприятий.
дипломная работа , добавлен 06.08.2013
Основные подходы к математическому моделированию систем, применение имитационных или эвристических моделей экономической системы. Использование графического метода решения задачи линейного программирования для оптимизации программы выпуска продукции.
Скачать книгу Н.Ш. Кремер и др. Исследование операций в экономике. Учебное пособие для вузов абсолютно бесплатно.
Для того, чтобы бесплатно скачать книгу с файлообменников нажмите на ссылки сразу за описанием бесплатной книги.
Цель исследования операций - количественное обоснование принимаемых решений по организации управления. В этом пособии представлены модели линейного и целочисленного программирования, классические методы оптимизации, задачи выпуклого и динамического программирования. Модели управления запасами и сетевого планирования и управления, элементы теории игр и массового обслуживания, оптимизация финансового портфеля. Приводится большое количество экономических задач с решениями и для самостоятельной работы. Рассмотрены некоторые вопросы применения ЭВМ для решения задач математического программирования. Для студентов экономических вузов, экономистов и лиц, обучающихся по программам второго высшего образования и проходящих профессиональную переподготовку или повышение квалификации.
Краткое содержание
Предисловие
Введение
Раздел I. Модели линейного программирования и его приложения
Глава 1. Общая постановка задачи линейного программирования
Глава 2. Элементы линейной алгебры и геометрии выпуклых множеств
Глава 3. Теоретические основы методов линейного программирования
Глава 4. Геометрический метод решения задач линейного программирования
Глава 5. Симплексный метод
Глава 6. Двойственные задачи
Глава 7. Транспортная задача
Глава 8. Модели целочисленного линейного программирования
Глава 9. Элементы теории игр
Раздел II. Модели нелинейного программирования
Глава 10. Классические методы оптимизации
Глава 11. Модели выпуклого программирования
Глава 12. Модели динамического программирования
Глава 13. Применение ЭВМ для решения задач математического программирования
Раздел III. Специальные модели исследования операций
Глава 14. Модели сетевого планирования и управления
Глава 15. Элементы теории массового обслуживания
Глава 16. Модели управления запасами
Литература
Предметный указатель.
Название: Исследование операций в экономике: Учебное пособие для вузов
Автор: Кремер Н.Ш., Путко Б.А., Тришин И.М., Фридман М.Н. Под ред. проф. Кремера Н.Ш.
Год: 2005
Страниц: 408
Формат: djvu
Размер: 12,73 Мб
Качество: хорошее, текстовый слой, оглавление.
Дорогие читатели если у Вас не получилось
скачать Н.Ш. Кремер и др. Исследование операций в экономике. Учебное пособие для вузов
напишите об этом в комментарияхи и мы обязательно вам поможем.
Серия: "Бакалавр. Академический курс" В учебнике представлены модели линейного и целочисленного программирования, классические методы оптимизации, задачи выпуклого и динамического программирования, модели управления запасами и сетевого планирования и управления, элементы теории игр и массового обслуживания, оптимизация финансового портфеля. Приводится большое количество экономических задач с решениями и для самостоятельной работы. Соответствует Федеральному государственному образовательному стандарту высшего профессионального образования третьего поколения. Для студентов, бакалавров, магистров и аспирантов экономических вузов, преподавателей, экономистов и лиц, обучающихся по программам МВА, второго высшего образования и проходящих профессиональную переподготовку или повышение квалификации. Издательство: "Юрайт" (2014) Формат: 84x108/32, 448 стр.
ISBN: 978-5-9916-3748-0 На Озоне |
Другие книги схожей тематики:
Автор | Книга | Описание | Год | Цена | Тип книги |
---|---|---|---|---|---|
Н. Ш. Кремер, Б. А. Путко, И. М. Тришин, М. Н. Фридман | Бакалавр. Академический курс | 2014 | 991 | бумажная книга | |
Кремер Н.Ш. | В учебнике представлены модели линейного и целочисленного программирования, классические методы оптимизации, задачи выпуклого и динамического программирования, модели управления запасами и сетевого… - Юрайт, (формат: 84x108/32, 448 стр.) Бакалавр. Академический курс | 1180 | бумажная книга | ||
Кремер Н.Ш. | Исследование операций в экономике. Учебник для академического бакалавриата | В учебнике представлены модели линейного и целочисленного программирования, классические методы оптимизации, задачи выпуклого и динамического программирования, модели управления запасами и сетевого… - ЮРАЙТ, (формат: 84x108/32, 448 стр.) Бакалавр. Академический курс | 1480 | бумажная книга | |
Б. А. Путко | Исследование операций в экономике 3-е изд., пер. и доп. Учебник для академического бакалавриата | В учебном пособии представлены модели линейного и целочисленного программирования, классические методы оптимизации, задачи выпуклого и динамического программирования, модели управления запасами и… - ЮРАЙТ, (формат: 84x108/32, 448 стр.) Бакалавр. Академический курс электронная книга | 2016 | 739 | электронная книга |
Мишенин А.И. | Теория экономических информационных систем Учебник | 240 стр. Дается характеристика компонентов экономических информационных систем (ЭИС) вычислительной системы, базы данных, программного обеспечения; рассматриваютсяэтапы их жизненного цикла… - ФИНАНСЫ И СТАТИСТИКА, (формат: 84x108/32, 448 стр.) | 2005 | 224 | бумажная книга |
Поршнев Сергей Владимирович, Овечкина Елена Владимировна, Мащенко Майя Владимировна | Компьютерный анализ и интерпретация эмпирических зависимостей. Учебник | 336 стр. Учебное пособие содержит изложение основ методов построения, анализа и интерпретации математических моделей эмпирических зависимостей. Каждый из рассмотренных в книге методов… - БИНОМ, (формат: 84x108/32, 448 стр.) | 2010 | 613 | бумажная книга |
См. также в других словарях:
Эту страницу предлагается объединить с Наука управления. Пояснение причин и обсуждение на странице Википедия:К объединению/18 декабря 2012 … Википедия
Эта статья или раздел описывает ситуацию применительно лишь к одному региону. Вы можете помочь Википедии, добавив информацию для других стран и регионов. Математические методы в экономике научное направление в экономике, посвящённое и … Википедия Энциклопедия инвестора
Виктор Васнецов. Витязь на распутье. 1878 Теория принятия решений область исследования, вовлекающая понятия и методы математики, статистики … Википедия
Теория принятия решений область исследования, вовлекающая понятия и методы математики, статистики, экономики, менеджмента и психологии; изучает закономерности выбора людьми путей решения разного рода задач, а также исследует способы поиска… … Википедия
Логистика стратегическое управление (менеджмент) закупкой, снабжением, перевозками и хранением материалов, деталей и готового инвентаря (техники и проч.). Понятие включает в себя также управление соответствующими потоками информации, а также… … Википедия
Логистика стратегическое управление (менеджмент) закупкой, снабжением, перевозками и хранением материалов, деталей и готового инвентаря (техники и проч.). Понятие включает в себя также управление соответствующими потоками информации, а также… … Википедия
И1
|Ш^ш^Я|
ШЯл
Определение показателей эффективности
многоканальной СМ О с отказами
Граф состояний С МО
лц
Предельные вероятности состояний
(формулы Эрланга)
2!
р_
А!
/I!
>
Р2
где р
Р
Р
=
/
7РО"
- "
Р/>
~7
/">*
" "
""~
^Г^О
I
/О
Я:
X/|i - интенсивность н.ир\ JKH каната
Вероятность отказа
Относительная пропускная
способность
Абсолютная пропускная
способность
Среднее число занятых
каналов
nl,/>о
Р
я!
п
Определение точки и размера заказа
в задачах управления запасами
Статическая модель без дефицита
вровень i-niac.i
3,пp.i 1ы
С
Л = nil = N / I I
2Т
НУ~Врс
Время
Оптимальный размер заказа
(формула Ушсона)
Оптимальный интервал
межд> поставками
л0 - J
\ С2
, *2 "~ количество кормов I и II, входящих в
дневной рацион. Тогда этот рацион (см. табл. 1.2) будет включать
(3*1 + 1-*2) единиц питательного вещества S\, (1-jq +2*2) единиц
вещества S2 и O"*i + ^Х2) единиц питательного вещества 5з- Так
как содержание питательных веществ S\, Si и S} в рационе должно быть не менее соответственно 9, 8 и 12 единиц, то получим
систему неравенств:
3*
! + 2x2 z 8,
(1.7)
+ 6х2 > 12.
Кроме того, переменные
xi > 0, х2 > 0.
(1.8)
Общая стоимость рациона составит (в руб.)
+
/ = 4xj 6x2(1-9)
Итак, экономико-математическая модель задачи: составить
дневной рацион X = (х\, х2), удовлетворяющий системе (1.7) и условию (1.8), при котором функция (1.9) принимает минимальное значение.^
Для формулировки задачи в общей постановке обозначим:
Xj (j = 1,2, ..., и) - число единиц корма я-го вида; 6, (/ = 1, 2, ...,
т), - необходимый минимум содержания в рационе питательного
1
вещества Sf, ay - число единиц питательного вещества 5 , в единице корма у"-го вида; с, - стоимость единицы корма у"-го вида.
Тогда экономико-математическая модель задачи примет вид:
найти такой рацион X - (х\, Х2, ..., х„), удовлетворяющий системе
(1.10)
+ am2X2+...+amnxnzbm
и условию
xi ;> 0, х2 ^ 0,..., хя > 0,
(1.11)
при котором функция
F= cix, + c2x2 +...+ с„хп
поинимает максимальное значение.
(1.12)
Общая постановка задач
21
3. Задача об использовании мощностей (задача о загрузке оборудования).
Предприятию задан план производства продукции по времени
и номенклатуре: требуется за время Г выпустить п\, П},..., nk единиц продукции Р\, Р^ ..., РЬ Продукция производится на станках
S\, .$2, > $т- Для каждого станка известны производительность ау
(т.е. число единиц продукции PJ, которое можно произвести на
станке 5/) и затраты by на изготовление продукции PJ на станке S/
в единицу времени.
Необходимо составить такой план работы станков (т.е. так
распределить выпуск продукции между станками), чтобы затраты
на производство всей продукции были минимальными.
Составим экономико-математическую модель задачи.
Обозначим \у - время, в течение которого станок /S/ будет занят изготовлением продукции PJ (i - I, 2,..., m\j = 1, 2, ..., k).
Так как время работы каждого станка ограничено и не превышает Т, то справедливы неравенства:
- "
(1.13)
x
ml + Xm2+---+xmk ^ Т.
Для выполнения плана выпуска по номенклатуре необходимо,
чтобы выполнялись следующие равенства:
+а
°11*11 + "21*21+- м1*и1 = "Ь
а
х
+а
х
Л
°12*12 + 22 22+--- т2 т2 = 2>
a
lkxlk
/j ^
+U
2kx2k+---+amkxmk =nk-
Кроме того,
zO(i = },2,...,m;j=\,2,...,k).
Xij
(1.15)
Затраты на производство всей продукции выразятся функцией
F= Ь\\Х\\ + Ь\2Х\2 +-+ bmkXmk.
(1"16)
Экономико-математическая модель задачи об использовании
мощностей примет вид: найти такое решение X = (хцрс^, -, хт/с),
22_
Глава 1
удовлетворяющее системам (1.13) и (1.14) и условию (1.15), при котором функция (1.16) принимает минимальное значение.
4. Задача о раскрое материалов.
На раскрой (распил, обработку) поступает материал одного
образца в количестве а единиц. Требуется изготовить из него /
разных комплектующих изделий в количествах, пропорциональных числам b\, bi, ...b/ (условие комплектности). Каждая единица
материала может быть раскроена и различными способами, причем использование /"-го способа (/ = 1,2, ..., п) дает <% единиц k-ro
изделия (k= 1,2, ..., /).
Необходимо найти план раскроя, обеспечивающий максимальное
число комплектов.
Составим экономико-математическую модель задачи.
Обозначим х/ - число единиц материала, раскраиваемых /-м
способом, чх - число изготавливаемых комплектов изделий.
Так как общее количество материала равно сумме его единиц,
раскраиваемых различными способами, то
ы
в.
(1.17)
Требование комплектности выразится уравнениями
Еде/ел»*** (k = 1,2, ...,/;.
(1.18)
*,>()(/ = 1,2,..., л).
(1.19)
ы
Очевидно, что
Экономико-математическая модель задачи: найти такое решение Х=(х\, Х2,..., х„), удовлетворяющее системе уравнений (1.17) -
(1.18) и условию (1.19), при котором функция F = х принимает максимальное значение.
1.3. Для изготовления брусьев длиной 1,2 м, 3 м и 5 м в соотношении 2:1:3 на распил поступают 195 бревен длиной 6 м. Определить план распила, обеспечивающий максимальное число комплектов. Составить экономико-математическую модель задачи.
Р е ш е н и е. Прежде всего определим всевозможные способы
распила бревен, указав соответствующее число получаемых при
этом брусьев (табл. 1.3).
Общая постановка задач
23
Т а б л и ц а 1.3
Число получаемых брусьев длиной, м
Способ
распила i
1,2
3,0
5,0
-
-
2
3
5
2
-
1
-
-
4
-
1
2
-
1
Обозначим: щ - число бревен, распиленных /-м способом
(/ = 1, 2, 3, 4); х - число комплектов брусьев.
Учитывая, что все бревна должны быть распилены, а число
брусьев каждого размера должно удовлетворять условию комплектности, экономико-математическая модель задачи примет вид:
F- х-» max
при ограничениях:
, + х2 + *з + *4 = 195,
5*1 + 2х2
= 2х,
Х^
=
jX)
х,;>0(/=1,2, 3, 4»
Задачу о раскрое легко обобщить на случай от раскраиваемых
материалов.
Пусть каждая единица у"-го материала (/" = 1, 2, ..., т) может
быть раскроена п различными способами, причем использование
i-го способа (/ = 1, 2, ... , л) дает а,д единиц k-го изделия (k = 1, 2,
..., t), а запас у"-го материала равен ду единиц.
Обозначим ху - число единиц у"-го материала, раскрываемого
i-м способом.
Экономико-математическая модель задачи о раскрое в общей
постановке примет вид: найти такое решение X = (х\\, x\i, ..., х„т),
удовлетворяющее системе
п
J^xy < fly (у = 1,2,..., т),
п т
/=1у=1
24
Глава 1
и условию x,j>Q, при котором функция F = х принимает максимальное значение.
5. Транспортная задача рассмотрена в гл. 7.
1.3. Общая задача линейного программирования
Рассмотренные выше примеры задач линейного программирования позволяют сформулировать общую задачу линейного программирования.
Дана система т линейных уравнений и неравенств с п переменными
а2\х\+а22х2+...+а2„х„
a
k+l,lxl + ak+l,2x2+- -+ak+\,nxn =
a
k+2,lxl
+a
k+2,2x2+---+ak+2,nxn = bk+2>
=bm
и линейная функция
F =
с„х„
Необходимо найти такое решение системы Х= (х\, х2,
где
(1.21)
j, ..., х„),
(1.22)
при котором линейная функция F (1.21) принимает оптимальное
(т.е. максимальное или минимальное) значение.
Система (1.20) называется системой ограничений, а функция F
- линейной функцией, линейной формой, целевой функцией или
функцией цели.
Более кратко общую задачу линейного программирования
можно представить в виде:
=
£ cjxj
(или -> min)
Общая постановка задач
25
при ограничениях:
2>„х, ,уху = *,(/ = k + \,k + 2,...,m),
=l
J
X j > Q (j = l, 2, .... /; / < л) .
Оптимальным решением (или оптимальным планом) задачи линейного программирования называется решение Х= (х\, х%, ..., х,
..., х„) системы офаничении (1 20), удовлетворяющее условию
(1.22), при котором линейная функция (1.21) принимает оптимальное (максимальное или минимальное) значение.
Термины "решение" и "план" - синонимы, однако первый
используется чаще, когда речь идет о формальной стороне задачи
(ее математическом решении), а второй - о содержательной стороне (экономической интерпретации).
При условии, что все переменные неотрицательны (х/ > 0,j=l, 2,
..., л), система офаничении (1.20) состоит лишь из одних неравенств,
- такая задача линейного профаммирования называется стандартной; если система офаничении состоит из одних уравнений, то задача называется канонической1. Так, в приведенных выше примерах
задач линейного профаммирования задачи 1 и 2 - стандартные,
задача 4 - каноническая, а задача 3 - общая.
Любая задача линейного профаммирования может быть сведена к канонической, стандартной или общей задаче. Рассмотрим
вначале вспомогательную теорему.
Теорема 1.1. Всякому решению (сц, <Х2,..., а„) неравенства
a,iX}+a. = (2/3; 5/3; 2; 5) является допустимым, а при q =2,
С2 =1, т.е. ^2 = (2/3; - 7/3; 2; 1) - недопустимым.
Среди бесконечного множества решений системы выделяют
так называемые базисные решения.
Базисным решением системы т линейных уравнений с п переменными называется решение, в котором все п-т неосновных переменных равны нулю.
В задачах линейного программирования особый интерес представляют допустимые базисные решения, или, как их еще называют,
опорные планы. Число базисных решений является конечным, так
как оно равно числу групп основных переменных, не превосходящему С^ . Базисное решение, в котором хотя бы одна из основных переменных равна нулю, называется вырожденным.
2.3. Найти все базисные решения системы, приведенной в задаче 2.1.
Р е ш е н и е. В задаче 2.1 было установлено, что существует
три группы основных переменных х\, х?, х\, хз; х\, х^, т.е. число
базисных решений равно 3.
Найдем первое базисное решение, взяв в качестве основных
переменные х\, Х2 и неосновных - переменные хз, Хф Приравняв
неосновные переменные нулю, т.е. при хз = Х4 = 0, получим систему уравнений в виде
х, - х2 = О,
2х! + х2 = 2,
откуда Х| = 2/3; Х2 = 2/3. Следовательно, первое базисное решение системы Х\ = (2/3; 2/3; 0; 0) - допустимое.
1
Именно такие решения представляют интерес в большинстве задач
линейного программирования.
32
Глава 2
Если взять за основные переменные х\, д/j и приравнять нулю
=
соответствующие неосновные переменные *2 *4 = 0, получим
второе базисное решение Х^ = (2/3; 0; 2/3; 0) - также допустимое. Аналогично можно найти и третье базисное решение
Х3 = (2/3; 0; 0; - 2/3) - недопустимое.*Совместная система (2.1) имеет бесконечно много решений, из
них базисных решений - конечное число, не превосходящее С™.
2.2. Выпуклые множества точек
В школьном курсе математики выпуклыми назывались многоугольники, целиком расположенные по одну сторону от прямых,
на которых лежат их стороны.
В
Рис. 2.1
Например, многоугольник на рис. 2.1, а - выпуклый, а многоугольник на рис. 2.1, б не является выпуклым (он расположен
по обе стороны от прямой ВС),
Общим определяющим свойством, которое отличает выпуклый многоугольник от невыпуклого, является то, что если взять
любые две его точки и соединить их отрезком, то весь отрезок
будет принадлежать этому многоугольнику. Это свойство может
быть принято за определение выпуклого множества точек.
Множество точек называется выпуклым, если оно вместе с любыми двумя своими точками содержит весь отрезок, соединяющий
эти точки.
Согласно этому определению многоугольник на рис. 2.1, о является выпуклым множеством, а многоугольник на рис. 2.1, б
таковым не является, ибо отрезок MN между двумя его точками М
и N не полностью принадлежит этому многоугольнику.
Элементы линейной алгебры и геометрии
33
/Г71
7
Выпуклыми множествами могут быть не только многоугольники. Примерами выпуклых множеств являются круг, сектор, отрезок,
многоугольная область, куб, пирамида (рис. 2.2, а-е), многогранная область, прямая, полуплоскость, полупространство и т.п.
Выпуклые множества обладают важным свойством, которое
устанавливается следующей теоремой.
Теорема 2.2. Пересечение (общая часть) любого числа выпуклых
множеств есть выпуклое множество.
D Пусть М и N - любые две точки пересечения двух1 множеств А и В (рис. 2.3). Так как точки М и N принадлежат пересечению множеств, т.е. одновременно и выпуклому множеству А, и
выпуклому множеству В, то согласно определению выпуклого
множества все точки отрезка MN будут принадлежать как множеству А, так и множеству В, т.е. пересечению этих множеств. А это и означает,
что пересечение данных множеств есть
выпуклое множество.
Среди точек выпуклого множества
можно выделить внутренние, граничные
и угловые точки.
Точка множества называется внутренней, если в некоторой ее окрестности2
содержатся точки только данного множества.
Рис. 2.3
Точка множества называется граничной,
если в любой ее окрестности содержатся как точки, принадлежащие
данному множеству, так и точки, не принадлежащие ему.
1
Для доказательства теоремы ограничимся случаем двух множеств.
Под окрестностью точки плоскости (пространства) подразумевается круг
(шар) с центром в этой точке.
2
34
Глава 2
Особый интерес в задачах линейного программирования представляют угловые точки.
Точка множества называется угловой (или крайней), если она не
является внутренней ни для какого отрезка, целиком принадлежащего данному множеству.
D
На рис. 2.4 приведены примеры различных точек многоугольника: внутренней (точки М), граничной (точка N) и угловых
(точки А, В, С, D, E). Точка А - угловая, так как для любого отрезка, целиком принадлежащего многоугольнику, например, отрезка АР, она не является внутренней; точка А - внутренняя для
отрезка KL, но этот отрезок не принадлежит целиком многоугольнику.
Для выпуклого множества угловые точки всегда совпадают с
вершинами многоугольника (многогранника), в то же время для
невыпуклого множества это не обязательно. Так, на рис. 2.5 точка
А является вершиной невыпуклого многоугольника, но не угловой
(она является внутренней для отрезка KL, целиком принадлежащего этому многоугольнику).
К
D
Рис. 2.5
Элементы линейной алгебры и геометрии
35
Множество точек называется замкнутым, если включает все
свои граничные точки. Множество точек называется ограниченным, если существует шар (круг) радиуса конечной длины с центром в любой точке множества, который полностью содержит в
себе данное множество; в противном случае множество называется неограниченным.
Если фигура ограничена только прямыми или их отрезками,
то число ее угловых точек конечно; в случае криволинейности
границ фигура содержит бесконечно много угловых точек, что
позволяет сделать следующее определение.
Выпуклое замкнутое множество точек пространства (плоскости),
имеющее конечное число угловых точек, называется выпуклым многогранником (многоугольником), если оно ограниченное, и выпуклой многогранной (многоугольной) областью, если оно неограниченное.
До сих пор рассматривались выпуклые множества точек на
плоскости и в пространстве. Аналитически такие точки изображаются упорядоченной парой чисел (х\, хз) или упорядоченной
тройкой чисел (х\, х^, *з)- Понятие точки можно обобщить, подразумевая под точкой (или вектором) упорядоченный набор п
чисел Х= (х\, *2> > *я)> в котором числа х\, х-^, ..., х„ называются
координатами точки (вектора). Такое обобщение имеет смысл, так
как если взять какой-либо экономический объект, то для его характеристики двух-трех чисел обычно бывает недостаточно и необходимо взять п чисел, где п > 3.
Множество всех точек Х = (х\, Х2,..., х„) образует n-мерное точечное (векторное) пространство. При п > 3 точки и фигуры «-мерного
пространства не имеют реального геометрического смысла и все исследования объектов этого пространства необходимо проводить в
аналитической форме. Тем не менее оказывается целесообразным и в
этом случае использовать геометрические понятия для облегчения
представлений об объектах л-мерного пространства.
2.3. Геометрический смысл решений
неравенств, уравнений и их систем
Рассмотрим решения неравенств.
Теорема 2.3. Множество решений неравенства с двумя переменными
а
\\х\ + al2x2£bi
(2.2)
Глава 2
36
является одной из двух полуплоскостей, на которые вся плоскость
делится прямой а\\х\ + 012*2 = °ь включая и эту прямую, а другая
полуплоскость с той же прямой есть множество решений неравенства
«11*1
_1_
х>
L.
«12*2 - "l-
УЪ *5\
V"^/
D Для произвольной абсциссы х\ ордината точки М (рис. 2.6),
лежащей на прямой а\\х\ + а\2х2 = Ь\, при условии 012 * 0, есть
а\\
Ъ\
,.
Ъ\
а\\
= -- xj +-- , т.е. координаты точки м х\\ -- jcj +-
-
a
\2
«12
\2
«12
а
Рис. 2.6
Через точку М проведем прямую, параллельную оси Qx2. Тогда
для любых точек Р и Q этой прямой, расположенных выше и ниже точки М, т.е. в верхней и нижней полуплоскостях, будут верны
и
Х
Х
или
-°11
неравенства х2п>х2м
2Р- 10
*2 ^--х\+-^«12 " «12
*2 ^ --*i +-- При условии «и >0 неравенства преобразуют«12
«12
ся соответственно к виду «njq + а\2х2 > Ь\ и а\\х\ + а\2х2 < Ь\, т.е
координаты всех точек верхней полуплоскости удовлетворяют
неравенству (2.2), а нижней полуплоскости - неравенству (2.3). В
случае а\2 < 0, наоборот, координаты всех точек верхней полу-
Элементы линейной алгебры и геометрии
37
плоскости удовлетворяют неравенству (2.3), а координаты нижней
полуплоскости - неравенству (2.2).
2.4. Построить множество решений неравенства:
а) Зх, - 4х2 + 12 <; 0; б) 3*i - 2х2 £ 0.
Р е ш е н и е. В соответствии с теоремой 2.3, множество решений неравенства есть полуплоскость.
а) Построим границу полуплоскости - прямую 3xi - 4x2+
+ 12 = 0, найдя точки ее пересечения с осями координат А (~4;0)
и В (0;3) на рис. 2.7, а.
/)(-4;0)
-3 -2 -
1
2
3
х,
Рис. 2.7
Для определения искомой полуплоскости (верхней или нижней) рекомендуется задать произвольную контрольную точку, не
лежащую на ее границе - построенной прямой. Если неравенство
выполняется в контрольной точке, то оно выполняется и во всех
точках полуплоскости, содержащей контрольную точку, и не выполняется во всех точках другой полуплоскости. И наоборот, в
случае невыполнения неравенства в контрольной точке, оно не
выполняется во всех точках полуплоскости, содержащей контрольную точку, и выполняется во всех точках другой полуплоскости.
В качестве контрольной точки удобно взять начало координат
О (0;0), не лежащее на построенной прямой. Координаты точки О
не удовлетворяют неравенству: 3 - 0 - 4 - 0 + 12 < О, следовательно,
решением данного неравенства является нижняя полуплоскость,
не содержащая контрольную точку О. Искомая полуплоскость
выделена штриховкой.
38
Глава 2
б) Построим границу полуплоскости - прямую Зх\ - 4x2 = Q по
двум точкам. Одной из этих точек является начало координат на рис.
2.7, б (в уравнении прямой отсутствует свободный член), а другую
точку берем на прямой произвольно, например, А (2; 3) на рис. 2.7, б.
В качестве контрольной возьмем, например, точку 5(1; 0). Самую
"простую" точку О (0; 0) здесь в качестве контрольной брать не
следует, ибо она лежит на построенной прямой. Так как координаты контрольной точки В (1; 0) удовлетворяют неравенству, т.е.
3 1 - 2 0 > 0, то решением данного неравенства является нижняя (правая) полуплоскость, содержащая эту точку >
Учитывая, что множество точек, удовлетворяющих уравнению
«п*1 + 012*2 + - + «1/А*и ~Ь\
(2-4)
при /1=3, является плоскостью, а при я>3 - ее обобщением в
«-мерном пространстве - гиперплоскостью, теорему 2.3 можно
распространить на случай трех и более переменных.
Теорема 2.4. Множество всех решений линейного неравенства с п
переменными
«12*2 + является одним из полупространств, на которые все пространство
делится плоскостью или гиперплоскостью (2.4), включая и эту плоскость (гиперплоскость).
Рассмотрим множество решений систем неравенств.
Теорема 2.5 Множество решений совместной системы т линейных неравенств с двумя переменными
anxi +al2x2