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

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

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

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

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

В общем виде математическая модель задачи может быть представлена в виде при условии, что , , где 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 требуется 6x1 единиц сырья, где x1 – количество выпускаемой продукции Прод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. Опишите процесс решения задачи с помощью инструмента Поиск решения.