МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«CАНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ЭКОНОМИКИ И ФИНАНСОВ»

КАФЕДРА СТАТИСТИКИ И ЭКОНОМЕТРИКИ

О.Ю. БОРОЗДИНА Н.В. ШКУРКО

УЧЕБНОЕ ПОСОБИЕ

ПО ДИСЦИПЛИНЕ

«МЕТОДЫ ОПТИМИЗАЦИИ»

2

ИЗДАТЕЛЬСТВО

САНКТ-ПЕТЕРБУРГСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА

ЭКОНОМИКИ И ФИНАНСОВ

Рекомендовано научно-методическим советом университета ББК 65. Б Бороздина О.Ю.

Б 83 Учебное пособие по дисциплине «Методы оптимизации» / О.Ю. Бороздина, Н.В. Шкурко. – СПб. : Изд-во СПбГУЭФ, 2012. – 42 с.

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

Применение формул проиллюстрировано конкретными примерами.

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

Предназначено для студентов очной и заочной форм обучения, изучающих дисциплину «Методы оптимизации» по специальности «Статистика».

ББК 65. Рецензенты: д-р техн. наук, профессор В.В. Трофимов канд. экон. наук, профессор, ЕУСПБ Ю.В. Вымятнина © СПбГУЭФ,

СОДЕРЖАНИЕ

Предисловие

1. Введение в теорию оптимизации

1.1. Классификация задач исследования операций

1.2. Определение целевой функции

1.3. Этапы определения оптимального решения

1.4. Оптимизация плана производства

1.5. Задача о распределении ресурсов

1.6. Из истории развития метода «Линейное программирование»...... 2. Оптимизация плана производства предприятия с учетом рациональности использования ресурсов

3. Планирование производства переработки мяса птицы с использованием метода линейного программирования

4. Задачи для самостоятельной работы

Глоссарий

Библиографический список

ПРЕДИСЛОВИЕ

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

Дисциплина «Методы оптимизации» предназначена студентам 3-го курса специальности «Статистика». Дисциплина направлена как на изучение теоретических основ применения экономико-математических моделей, так и на освоение навыков практического использования расчетных методов.

Лекционная часть курса охватывает основные разделы дисциплины в соответствии со стандартом специальности.

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

Инструментальной основой проведения практических занятий является табличный процессор Excel.

Целью изучения данной дисциплины является овладение, как необходимыми теоретическими основами экономико-математического моделирования в данной предметной области, так и практическими навыками:

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

1. ВВЕДЕНИЕ В ТЕОРИЮ ОПТИМИЗАЦИИ

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

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

В самом общем виде задача оптимального планирования ставится следующим образом. Пусть планируется мероприятие (процесс), которое обычно называют «операцией», преследующее некоторую цель.

Ставится вопрос: как нужно спланировать операцию, чтобы она в рамках существующих ограничений наилучшим образом удовлетворяла поставленной цели?

В задачах оптимального планирования можно выделить:

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

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

В задачах оптимизации должны быть выделены характеристики объекта (объектов), которые можно и нужно варьировать для достижения цели. Такие характеристики называются управляемыми переменными, или управляемыми параметрами.

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

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

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

Рыночная цена может сильно колебаться, и пренебрежение этой неуправляемой переменной может привести к совершенно ошибочным решениям.

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

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

Другой пример. Оптимизируя работу предприятия, с одной стороны, можно исходить из принципа максимизации прибыли; с другой стороны, из принципа минимизации затрат. Два эти принципа не эквивалентны. Это становится ясным, если обратить внимание на то, что затраты, как правило, определяются процессом производства, а прибыль зависит от конъюнктуры рынка.

При постановке задачи оптимизации важно:

- сформулировать преследуемую цель;

- установить, какие переменные можно варьировать для достижения цели (т.е. управляемые переменные и и неуправляемые параметры);

- определить, какие ограничения накладываются на переменные.

1.1. Классификация задач исследования операций Задачи исследования операций классифицируют по их информационным свойствам. Если субъект в ходе принятия решения не меняет своего информационного состояния, т.е. никакой информации не приобретает и не утрачивает, то принятие решения можно рассматривать как мгновенный акт. Такие задачи называются статистическими.

Если субъект в ходе принятия решения изменяет свое информационное состояние, получая или теряя информацию, то в этом случае решение целесообразно принимать поэтапно (многошаговое решение).

Такие задачи называются динамическими.

Задачи исследования операций классифицируют так же по виду целевой функции и по виду ограничений. Если функция цели и система ограничений является линейными, то говорят о линейном программировании, в противном случае возникает задача нелинейного программирования.

В случае квадратичной функции целей и линейной системы ограничений задачу оптимизации называют задачей квадратичного программирования.

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

Если функция цели является выпуклой функцией, то такая задача оптимизации называется задачей выпуклого программирования.

Если функция j определяющие ограничения j(x1, x2, …, xN) () bj, в задаче математического программирования являются выпуклыми (вогнутыми) функциями, то они порождают выпуклое множество допустимых решений. Другими словами, задача выпуклого программирования также возникает, когда функция цели – выпуклая функция и ограничения – выпуклые (вогнутые) функции.

Наиболее важными моделями, используемыми при исследовании операций, являются математические модели. Любая модель в задаче исследования операций включает искомые переменные, налагаемые на них ограничения и формулировку цели.

Цель модели определяет целевую функцию, которая задается на множестве допустимых решений D. Само множество D выражает меру осуществления цели:

- если D пусто, то решения не существует;

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

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

Если D счетно или D является континуумом, то оптимальное решение приходиться искать на бесконечном множестве допустимых решений.

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

Если переменные X=(x1, x2, …, xN) представляет собой N управляемых переменных, Z=(z1, z2, …, zK) – K неуправляемых параметров и условие функционирования исследуемой системы определяется M ограничениями, то математическая модель может быть записана в следующем виде: найти точку Y=(y1, y2, …, yN), в которой достигается экстремум, минимум или максимум, целевой функции (X,Z):

Еще раз подчеркнем, что задача на условный экстремум обычно