Министерство образования Российской Федерации

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

"УДМУРТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ"

Институт экономики и управления

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

по выполнению лабораторной работы

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

для студентов дневного и заочного отделений

Ижевск

2007

1

СОЖЕРЖАНИЕ

Стр.

Введение

Формальная постановка задачи оптимизации планирования производства

Пример формальной постановки задачи оптимизации планирования производства

Методика выполнения задачи оптимизации планирования производства в Microsoft Excel

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

Пример формальной постановки транспортной задачи Методика выполнения транспортной задачи в Microsoft Excel Требования к оформлению лабораторной работы Рекомендуемая литература

2

Введение

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

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

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

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

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

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

В результате изучения методического пособия студент должен научиться определять и использовать для экономического анализа:

•целевую функцию; •ограничения;

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

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

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

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

3

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

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

Модели

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

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

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

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

bi — количество имеющегося i-го ресурса; xj — объем выпуска j-го продукта.

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

ния:

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

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

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

xj — переменная (variable).

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

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

4

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

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

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

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

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

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

Соответственно, двойственной к задаче ЛП (7)–(9) является задача

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

Компонента yi* оптимального решения двойственной задачи (7)–(9)

называется двойственной оценкой (Dual Value) ограничения ån aij x j £ bi

j= 1

исходной задачи ЛП.

Пусть ϕ = max(ån c j x j ) , где хj – компонента допустимого решения за-

j = 1

дачи (1)–(3).

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

5

∂ ϕ = yi* , i=1, …, m

∂ bi

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

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

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

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

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

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

Пример решения задачи оптимизации планирования производства

Задача. Завод производит электронные приборы трех видов (прибор А, прибор В и прибор С), используя при сборке микросхемы трех видов (тип 1, тип2, тип3). Расход микросхем задается следующей таблицей:

Стоимость изготовленных приборов одинакова. Ежедневно на склад завода поступает 500 микросхем типа 1 и по 400 микросхем типов 2 и 3. Каково оптимальное соотношение дневного производства приборов раз-

6

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

Формальная математическая постановки задачи

Константы

1. Пусть mij – расход микросхем i для прибора j, где i=1,2,3; j=1,2,3.

2.Пусть Zi – ежедневный запас микросхем i на складе, где i=1,2,3.

Z1=500; Z2=400; Z3=400.

Переменные

1.Обозначим через xj дневное производство приборов j, j=1,2,3, то есть

x1 - дневной выпуск приборов А; x2 - дневной выпуск приборов В; x3 - дневной выпуск приборов С.

2.Обозначим через Ri расход микросхем i, где i=1,2,3, то есть

R1 - расход микросхем 1-го типа;

R2 – расход микросхем 2-го типа;

R3 – расход микросхем 3-го типа.

3. Обозначим через N дневное производство всех видов приборов.

Решение

1.Зададим математическую модель расхода микросхем

2. Зададим математическую модель нахождения общего количества приборов N=x1+x2+x3. Его максимизация является целью решения задачи. Следовательно, целевая функция будет иметь вид:

N = å3 x j ® max

j= 1

7

Ограничения

1. Расход микросхем не должен превышать их запас

(для микросхем 3-го

типа)

2.Количество выпускаемых приборов должно быть целым числом.

3.Поскольку x1, x2, x3 выражают объем выпускаемых приборов, то они не могут быть отрицательны, то есть

x1≥0; x2≥0; x3≥0; x4≥0

Методика выполнения в Microsoft Excel

1.Запустите программу Excel (Пуск ®Программы®Microsoft Excel) и создайте рабочую книгу Book.xls.

2.Создайте новый рабочий лист «Организация производства».

3.В ячейки E2, E3, и E4 занесите дневной запас микросхем – числа 500, 400, и 400 соответственно.

4.В ячейки B5, C5 и D5 занесите нули – в дальнейшем значения этих ячеек будут подобраны автоматически.

5.В ячейках диапазона A1:D4 разместите таблицу расхода комплектующих.

6.В ячейках F2:F4 нужно указать формулы для расчета расхода микросхем по типам. В ячейке F2 формула будет иметь вид =$B$5*B2+

8

$C$5*C2+$D$5*D2, а остальные формулы можно получить методом автозаполнения (обратите внимание на использование абсолютных и относительных ссылок).

7.В ячейку F5 занесите формулу, вычисляющую общее количество произведенных приборов: для этого выделите диапазон B5:D5 и щелкните на кнопке Автосумма на стандартной панели инструментов.

8.Дайте команду Сервис→Поиск решения – откроется диалоговое окно Поиск решения.

9.В поле Установить целевую укажите ячейку, содержащую оптимизируемое значение (F5). Установите переключатель Равной максимальному значению (требуется максимальный объем производства).

10.В поле Изменяя ячейки задайте диапазон подбираемых параметров – B5:D5.

11.Необходимо добавить ограничения:

Расход микросхем не должен превышать их запас.

Количество выпускаемых приборов должно быть целым числом.

Число производимых приборов неотрицательно

12. Чтобы определить набор ограничений, щелкните на кнопке Добавить. В диалоговом окне Добавление ограничения в поле Ссылка на ячейку укажите диапазон F2:F4. В качестве условия задайте <=. В поле Ограничение задайте диапазон E2:E4. Это условие указывает, что дневной расход комплектующих не должен превосходить запасов. Щелкните на кнопке ОК.

13.Снова щелкните на кнопке Добавить. В поле Ссылка на ячейку укажите диапазон B5:D5. В качестве условия задайте >=. В поле Ограничение задайте число 0. Это условие указывает, что число производимых приборов неотрицательно. Щелкните на кнопке ОК.

14.Снова щелкните на кнопке Добавить. В поле Ссылка на ячейку укажите диапазон B5:D5. В качестве условия выберите пункт цел. Это условие не позволяет производить доли приборов. Щелкните на кнопке

ОК.

9

15.Щелкните на кнопке Выполнить. По завершении оптимизации откроется диалоговое окно Результаты поиска решения.

16.Установите переключатель Сохранить найденное решение, после чего щелкните на кнопке ОК.

17.Проанализируйте полученное решение. Кажется ли оно очевидным? Проверьте его оптимальность, экспериментируя со значениями ячеек B5:D5. Чтобы восстановить оптимальные значения, можно в любой момент повторить операцию поиска решения.

18.Сохранить рабочую книгу Book.xls.

Транспортная задача

Под термином "транспортные задачи" понимается широкий круг задач не только транспортного характера. Общим для них является, как правило, распределение ресурсов, находящихся у m производителей (поставщиков), по n потребителям этих ресурсов.

Ни автомобильном транспорте наиболее часто встречаются следующие задачи, относящиеся к транспортным:

∙прикрепление потребителей ресурса к производителям;

∙привязка пунктов отправления к пунктам назначения;

∙взаимная привязка грузопотоков прямого и обратного направлений;

∙отдельные задачи оптимальной загрузки промышленного оборудования;

10