Введение. Для проведения лабораторных работ

МЕТОДИЧЕСКОЕ ПОСОБИЕ

Для проведения лабораторных работ

По курсу Информатика

Решение задач оптимизации в среде Microsoft Excel

Ижевск

Методические материалы обсуждены на заседании кафедры высшей математики и информатики ИЭиУ

Зав. кафедрой ВМиИ Сметанин Ю.М.

Утверждены учебно-методической комиссией ИЭиУ

Председатель УМК ИЭиУ Баскин А.С.

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

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

Ижевск: - ИЭиУ УдГУ, 2008, 61с

ÓИЭиУ УдГУ, 2008

Содержание

Введение

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

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

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

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

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

Однако самое главное – студент должен уметь анализировать эти результаты и делать выводы, адекватные поставленной экономической задаче.

Для решения задач оптимизации часто используют надстройку программы Microsoft Excel "Поиск решения". Цель методического пособия – научиться использовать возможности Microsoft Excel для нахождения оптимального решения экономических задач.

Материал в каждой главе изложен в следующей последовательности: цели, модели, пример решения задачи, включающий формальную математическую постановку и методику решения средствами Microsoft Excel. После изложения теоретической части приведен перечень вариантов задач для самостоятельного решения.

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

Цели

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

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

• целевую функцию;

• ограничения;

• модель линейного программирования;

• оптимальный план.

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

Модели

Введем обозначения:

п — количество выпускаемых продуктов;

т — количество используемых производственных ресурсов (например, производственные мощности, сырье, рабочая сила);

a_ij — объем затрат i -го ресурса на выпуск единицы j -й продукции;

c_j — прибыль от выпуска и реализации единицы j- го продукта;

b_i — количество имеющегося i -го ресурса;

x_j — объем выпуска j -го продукта.

Формально задача оптимизации производственной программы может быть описана с помощью следующей модели линейного программирования:

(1)

i=1,…, m (2)

j=1,…, n (3)

Здесь (1) – целевая функция (максимум прибыли);

(2) – система специальных ограничений (constraint) на объем фактически имеющихся ресурсов;

(3) – система общих ограничений (на неотрицательность переменных);

x_j – переменная (variable).

Задача (1)—(3) называется задачей линейного программирования в стандартной форме на максимум.

Задача линейного программирования в стандартной форме на минимум имеет вид

(4)

i=1,…, m (5)

j=1,…, n (6)

Вектор х = (x₁, x₂,..., x_п), компоненты x_j которого удовлетворяют ограничениям (2) и (3) (или (5) и (6) в задаче на минимум), называется допустимым решением или допустимым планом задачи линейного программирования (ЛП).

Совокупность всех допустимых планов называется множеством допустимых планов.

Допустимое решение задачи ЛП, на котором целевая функция (1) (или (3) в задаче на минимум) достигает максимального (минимального) значения, называется оптимальным решением задачи ЛП.

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

Двойственной к задаче ЛП (1)–(3) является задача

(7)

j=1,…, n (8)

i=1,…, m (9)

Соответственно, двойственной к задаче ЛП (7)–(9) является задача (1)–(3). Каждой переменной (специальному ограничению) исходной задачи соответствует специальное ограничение (переменная) двойственной задачи. Если исходная задача ЛП имеет решение, то имеет решение и двойственная к ней задача, при этом значения целевых функций для соответствующих оптимальных решений равны.

Компонента оптимального решения двойственной задачи (7)–(9) называется двойственной оценкой (Dual Value) ограничения исходной задачи ЛП.

Пусть , где х_j – компонента допустимого решения задачи (1)–(3).

Тогда при выполнении условий невырожденности оптимального решения имеют место следующие соотношения:

, i=1, …, m (10)

Изменим значение правой части b_i одного основного ограничения (RHS) исходной задачи ЛП.

Пусть – минимальное значение правой части основного ограничения, при котором решение у^* двойственной задачи не изменится. Тогда величину называют нижней границей (Lower Bound) устойчивости по правой части ограничения.

Пусть –максимальное значение правой части основного ограничения, при котором решение у^* двойственной задачи не изменится. Тогда величину называют верхней границей (Upper Bound) устойчивости по правой части ограничения.

Изменим значение одного коэффициента с_j целевой функции исходной задачи ЛП.

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

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

Поиск по сайту: