Технология решения задач оптимизации

Постановка задачи

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

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

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

В общем виде математическая модель задачи может быть представлена в виде при условии, что , , где f(x) – целевая функция; x – аргументы функции; а – коэффициенты при аргументах; А – матрица коэффициентов; b – вектор, содержащий значения ограничений; lb и mb – вектора ограничений на значения аргументов целевой функции.

Технология оптимизации

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

Технологическая последовательность решения задачи в табличном процессоре включает следующие шаги:

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

- в электронную таблицу вводятся исходные данные и формулы, реализующие разработанную математическую модель;

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

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

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

Рассмотрим технологию решения задачи линейного программирования на примере.

Пример 1. Требуется определить, в каком количестве надо выпускать продукцию четырех типов Прод1, Прод2, Прод3, Прод4, для изготовления которой требуются ресурсы трех видов: трудовые, финансовые, сырьевые. Количество ресурса каждого типа, необходимое для выпуска единицы продукции, называется нормой расхода. Нормы расхода, а также прибыль, получаемая от реализации единицы каждого типа продукции, приведены в таблице 1.

Таблица 1

Исходные данные

	Прод1	Прод2	Прод3	Прод4	Ограничения
Прибыль					=	max
Персонал					<=
Сырье					<=
Финансы					<=

Решение в MS Excel

1. Разработка математической модели.

Как следует из табл. 1, для выпуска единицы Прод1 требуется 6 единиц сырья, значит, для выпуска всей продукции Прод1 требуется 6x₁ единиц сырья, где x₁ – количество выпускаемой продукции Прод1. Для других видов продукции определяются соответствующие зависимости и ограничение по сырью будет иметь вид

.

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

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

Исходя из условия задачи, целевая функция будет иметь вид

при ограничениях

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

2. Формализация модели в электронной таблице.

На рабочем листе сформируем таблицу (рис. 1).

Рис. 1. Форма для ввода условия задачи

3. Настройка инструмента Поиск решения.

Выполнить команду меню Сервис/Поиск решения (рис. 2).

Примечание. При отсутствии команды Поиск решения в меню Сервис необходимо выполнить команду Сервис/Надстройки и в списке надстроек поставить флажок Поиск решения.

Рис. 2. Диалоговое окно Поиск решения

В диалоговом окне Поиск решения:

§ Установить параметры:

Установить целевую ячейку: $F$5;

Равной: максимальному значению;

Изменяя ячейки: $B$3:$E$3.

§ Нажать кнопку Добавить и в диалоговом окне Добавление ограничения ввести ограничения (рис. 3):

$B$3>=0

$C$3>=0

$D$3>=0

$E$3>=0

$F$8<=$H$8

$F$9<=$H$9

$F$10<=$H$10

$B$3: $E$3 = целое

Для ввода нового ограничения необходимо нажать кнопку Добавить на панели Добавление ограничения. После ввода всех ограничений нажать кнопку ОК для перехода в диалоговое окно Поиск решения.

Рис. 3. Диалоговое окно Добавление ограничения

§ Установить параметры поиска решения. Нажать кнопку Параметры. В диалоговом окне Параметры поиска решения установить флажок Линейная модель, что обеспечивает применение симплекс-метода, и флажок Неотрицательные значения (рис. 4). Нажать кнопку ОК для перехода в диалоговое окно Поиск решения.

Рис. 4. Диалоговое окно Параметры поиска решения

§ Нажать кнопку Выполнить. На экране появится диалоговое окно Результаты поиска решения. Решение найдено. Все ограничения и условия оптимальности выполнены (рис. 5).

Рис. 5. Диалоговое окно Результаты поиска решения

4. Результаты решения задачи.

В таблице (рис. 6) показано, что в оптимальном решении Прод1=10, Прод2=0, Прод3=6, Прод4=0. При этом максимальная прибыль будет составлять 1320, а количество использованных ресурсов:

Персонал = 16,

Сырье = 84,

Финансы = 100.

Рис. 6. Оптимальное решение задачи

5. Графическое представление результата оптимизации.

Построить диаграмму Оптимальный план по строкам Ресурс и Значение (рис. 7).

Рис. 7. Диаграмма оптимального плана

ЗАДАНИЕ

Компания производит два вида продукции: парты и столы. Процесс изготовления изделий происходит в цехах сборки и отделки. Данные по видам продукции приведены в табл.1.

Таблица 1

Название технологического процесса	Трудоемкость технологической операции для одной парты	Трудоемкость технологической операции для одного стола	Лимит производственного времени (в часах)
Сборка	2 ч/шт	4 ч/шт
Отделка	3 ч/шт	2 ч/шт
Маржинальная прибыль на единицу продукции	25 $/шт	40 $/шт

Найти наиболее выгодную структуру выпуска продукции (по критерию максимальной прибыли).

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. С помощью какого метода решаются задачи линейного программирования?

2. Назначение целевой функции.

3. Как определить ограничения целевой функции?

4. Опишите процесс решения задачи с помощью инструмента Поиск решения.